A. Matrix Game

Ashish and Vivek play a game on a matrix consisting of $n$ rows and $m$ columns, where they take turns claiming cells. Unclaimed cells are represented by $0$ , while claimed cells are represented by $1$ . The initial state of the matrix is given. There can be some claimed cells in the initial state.
In each turn, a player must claim a cell. A cell may be claimed if it is unclaimed and does not share a row or column with any other already claimed cells. When a player is unable to make a move, he loses and the game ends.
If Ashish and Vivek take turns to move and Ashish goes first, determine the winner of the game if both of them are playing optimally.
Optimal play between two players means that both players choose the best possible strategy to achieve the best possible outcome for themselves.

Input

The first line consists of a single integer $t$ $(1≤t≤50)$ — the number of test cases. The description of the test cases follows.
The first line of each test case consists of two space-separated integers $n, m$ $(1≤n,m≤50)$ — the number of rows and columns in the matrix.
he following $n$ lines consist of m integers each, the $j$ -th integer on the $i$ -th line denoting $a_{ij}$ $(a_{ij}∈{0,1})$ .

Output

For each test case if Ashish wins the game print “Ashish” otherwise print “Vivek” (without quotes).

Example

input

4
2 2
0 0
0 0
2 2
0 0
0 1
2 3
1 0 1
1 1 0
3 3
1 0 0
0 0 0
1 0 0

output

Vivek
Ashish
Vivek
Ashish

Note

For the first case: One possible scenario could be: Ashish claims cell $(1,1)$ , Vivek then claims cell $(2,2)$ . Ashish can neither claim cell $(1,2)$ , nor cell $(2,1)$ as cells $(1,1)$ and $(2,2)$ are already claimed. Thus Ashish loses. It can be shown that no matter what Ashish plays in this case, Vivek will win.
For the second case: Ashish claims cell $(1,1)$ , the only cell that can be claimed in the first move. After that Vivek has no moves left.
For the third case: Ashish cannot make a move, so Vivek wins.
For the fourth case: If Ashish claims cell (2,3), Vivek will have no moves left.

Translation

给一个元素为 $0$ 和 $1$ 组成的矩阵，两个人轮流选择一个 $0$ 将其变成 $1$ ，可选的条件是这个 $0$ 所在的行和列上都没有 $1$ 。当某个人无法选择时，这个人就视为输家。

Idea

简单博弈论。
设不存在 $1$ 的行数为 $c_1$ ，不存在 $1$ 的列数为 $c_2$ ，则能够修改的位置的数量为 $c=\min(c_1,c_2)$ ，若 $c$ 为偶数，则后手胜，否则先手胜。

Code

#include<iostream>
#include<cstdio>
#define N 52
using namespace std;
int a[N][N];
int n,m;
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		int i,j;
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				scanf("%d",&a[i][j]);
			}
		}
		int c1=n,c2=m;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				if(a[i][j])//该行不可修改
				{
					c1--;
					break;
				}
			}
		}
		for(j=1;j<=m;j++)
		{
			for(i=1;i<=n;i++)
			{
				if(a[i][j])//该列不可修改
				{
					c2--;
					break;
				}
			}
		}
		puts(min(c1,c2)&1?"Ashish":"Vivek");
	}
	return 0;
}

B. Trouble Sort

Ashish has $n$ elements arranged in a line.
These elements are represented by two integers $a_i$ — the value of the element and $b_i$ — the type of the element (there are only two possible types: $0$ and $1$ ). He wants to sort the elements in non-decreasing values of $a_i$ .
He can perform the following operation any number of times:
Select any two elements $i$ and $j$ such that $b_i≠b_j$ and swap them. That is, he can only swap two elements of different types in one move.
Tell him if he can sort the elements in non-decreasing values of ai after performing any number of operations.

Input

The first line contains one integer $t$ $(1≤t≤100)$ — the number of test cases. The description of the test cases follows.
The first line of each test case contains one integer $n$ $(1≤n≤500)$ — the size of the arrays.
The second line contains $n$ integers $a_i$ $(1≤a_i≤10^5)$ — the value of the $i$ -th element.
The third line contains $n$ integers $b_i$ $(b_i∈\{0,1\})$ — the type of the $i$ -th element.

Output

For each test case, print “Yes” or “No” (without quotes) depending on whether it is possible to sort elements in non-decreasing order of their value.
You may print each letter in any case (upper or lower).

Example

input

5
4
10 20 20 30
0 1 0 1
3
3 1 2
0 1 1
4
2 2 4 8
1 1 1 1
3
5 15 4
0 0 0
4
20 10 100 50
1 0 0 1

output

Yes
Yes
Yes
No
Yes

Note

For the first case: The elements are already in sorted order.
For the second case: Ashish may first swap elements at positions $1$ and $2$ , then swap elements at positions $2$ and $3$ .
For the third case: The elements are already in sorted order.
For the fourth case: No swap operations may be performed as there is no pair of elements $i$ and $j$ such that $b_i≠b_j$ . The elements cannot be sorted.
For the fifth case: Ashish may swap elements at positions $3$ and $4$ , then elements at positions $1$ and $2$ .

Translation

给一个数组，数组中第 $i$ 个元素的值为 $a_i$ ，第 $i$ 个元素的属性为 $b_i\in\{0,1\}$。
可以选择两个属性不同的元素进行交换，问能在进行若干次操作后，讲数组中元素的值排成非递减的序列。

Idea

①当 $a_i$ 本身非递减时，一定能满足要求。
②如果需要进行交换才能满足要求，结论是：只要数组中两种属性都存在，那么在经过若干次元素交换后，元素的值一定能形成非递减序列。下面给出证明：设想我们对数组中元素的值进行冒泡排序，假如要交换 $a$ 和 $b$ ，如果两者的属性不同，那么直接交换；如果两者属性相同，可以借助一个属性不同的元素，进行三次交换 a b x,a x b,x a b,b a x 使得 $a$ 和 $b$ 交换， $c$ 处在原位，按照冒泡排序的原理，一定能排成非递减的序列。

Code

#include<iostream>
#define N 503
using namespace std;
int a[N],b[N];
int n;
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		scanf("%d",&n);
		int i;
		bool cnt0=0,cnt1=0;
		bool ok;
		bool isNonDecreasing=1;
		for(i=1;i<=n;i++) scanf("%d",a+i);
		for(i=1;i<=n;i++) scanf("%d",b+i);
		for(i=1;i<n;i++)//检验数组的值是否非递减
		{
			if(a[i]>a[i+1])
			{
				isNonDecreasing=0;
				break;
			}
		}
		for(i=1;i<=n;i++) b[i]?cnt1=1:cnt0=1;//两种属性是否都存在
		puts((isNonDecreasing|cnt1&cnt0)?"Yes":"No");
	}
	return 0;
}

C. Rotation Matching

After the mysterious disappearance of Ashish, his two favourite disciples Ishika and Hriday, were each left with one half of a secret message. These messages can each be represented by a permutation of size $n$ . Let’s call them $a$ and $b$ .
Note that a permutation of $n$ elements is a sequence of numbers $a_1,a_2,…,a_n$ , in which every number from $1$ to $n$ appears exactly once.
The message can be decoded by an arrangement of sequence $a$ and $b$ , such that the number of matching pairs of elements between them is maximum. A pair of elements $a_i$ and $b_j$ is said to match if:

$i=j$ , that is, they are at the same index.
$a_i=b_j$

His two disciples are allowed to perform the following operation any number of times: choose a number $k$ and cyclically shift one of the permutations to the left or right $k$ times.
A single cyclic shift to the left on any permutation $c$ is an operation that sets $c_1:=c_2,c_2:=c_3,…,c_n:=c_1$ simultaneously. Likewise, a single cyclic shift to the right on any permutation $c$ is an operation that sets $c_1:=c_n,c_2:=c_1,…,c_n:=c_{n−1}$ simultaneously.
Help Ishika and Hriday find the maximum number of pairs of elements that match after performing the operation any (possibly zero) number of times.

Input

The first line of the input contains a single integer $n$ $(1≤n≤2⋅10^5)$ — the size of the arrays.
The second line contains n integers $a_1, a_2, ..., a_n$ $(1≤a_i≤n)$ — the elements of the first permutation.
The third line contains $n$ integers $b_1, b_2, ..., b_n (1≤b_i≤n)$ — the elements of the second permutation.

Output

Print the maximum number of matching pairs of elements after performing the above operations some (possibly zero) times.

Examples

input

5
1 2 3 4 5
2 3 4 5 1

output

input

5
5 4 3 2 1
1 2 3 4 5

output

input

4
1 3 2 4
4 2 3 1

output

Note

For the first case: $b$ can be shifted to the right by $k=1$ . The resulting permutations will be $\{1,2,3,4,5\}$ and $\{1,2,3,4,5\}$.
For the second case: The operation is not required. For all possible rotations of $a$ and $b$ , the number of matching pairs won’t exceed $1$ .
For the third case: $b$ can be shifted to the left by $k=1$ . The resulting permutations will be ${1,3,2,4}$ and $\{2,3,1,4\}$. Positions $2$ and $4$ have matching pairs of elements. For all possible rotations of $a$ and $b$ , the number of matching pairs won’t exceed $2$ .

Translation

给两个长度为 $n$ 的全排列 $a$ 和 $b$ 。处于两个排列中的数对 $a_i$ 和 $b_j$ 相等当且仅当 $i=j$ 且 $a_i=b_j$ 。可以对其中一个排列进行若干次 $\text{cyclically shift}$ ，一次 $\text{cyclically shift}$ 的形式如下，将排列整体向左推， $c_1:=c_2$ $,c_2:=c_3$ $,…,c_n:=c_1$ ；或将排列整体向右推 $c_1:=c_n,c_2:=c_1,…,c_n:=c_{n−1}$ 。
问对其中一个排列进行若干次 $\text{cyclically shift}$ 后，相等数对的个数的最大值。

Idea

显然，在此题中，两个排列的运动是相对的，且左右对称；选择 $a$ 或 $b$ 操作结果是一样的，排列向左或向右推结果也是一样的；不妨假定，对 $b$ 进行操作，并将 $b$ 整体向右移动。
若 $a_i=b_j$ 且 $i\ne j$ ，要使该数对相等，需要移动 $b_j$ 至位置 $i$ ；假如 $i>j$ ，移动步数为 $i-j$ ；否则，移动步数为 $n-j+i$ 。设令数对 $a_i$ 和 $b_j $ 相等的移动步数为 $step$ ，显然 $0\le step\le n-1$ ，多余 $n-1$ 步的移动有一部分是无意义的。
设移动 $i$ 步后相等数对的个数为 $cnt_i$ 。对每一个 $b_j$ 求出其需要移动的步数（可以记录全排列 $a$ 中每个数的位置，就能轻易得到移动的步数），就能轻易得到 $cnt_i$ （每求的一个步数 $step$ ， $cnt_{step}$ 增加 $1$ ）。答案即为 $\max\limits_{0\le i\le n-1} cnt_i$ 。

Code

#include<iostream>
#include<cstdio>
#define N 200003
using namespace std;
int a[N],b[N];
int pos[N];
int cnt[N];
int n,ans;
int main()
{
	cin>>n;
	int i;
	for(i=1;i<=n;i++) scanf("%d",a+i);
	for(i=1;i<=n;i++) scanf("%d",b+i);
	for(i=1;i<=n;i++) pos[a[i]]=i;//记录排列a中数字的位置
	//计算步数需要移动的步数step=i>pos[b[i]]?n-i+pos[b[i]]:pos[b[i]]-i;
	//移动step步后相等数对个数加1
	for(i=1;i<=n;i++) cnt[i>pos[b[i]]?n-i+pos[b[i]]:pos[b[i]]-i]++;
	for(i=0;i<=n-1;i++) ans=max(cnt[i],ans);
	cout<<ans<<endl;
	return 0;
}

E

#include<iostream>
#include<cstdio>
using namespace std;
long long a[503];
int n;
long long ans;
int main()
{
	cin>>n;
	int i,j,k;
	for(i=1;i<=n;i++) scanf("%lld",a+i);
	for(i=1;i<=n;i++)
	{
		for(j=i;j<=n;j++)
		{
			for(k=j;k<=n;k++)
			{
				ans=max(ans,a[i]|a[j]|a[k]);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}