算法竞赛 Codeforces Round #648 (Div. 2)

算法竞赛 Codeforces Round #648 (Div. 2)

临时有事咕咕咕了Codeforces Round #648 (Div. 2),补题+翻译。

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.

The following n lines consist of m integers each, the j-th integer on the i-th line denoting ai,j (ai,j∈{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.


B. Trouble Sort

》英文原题《

Ashish has n elements arranged in a line.

These elements are represented by two integers ai — the value of the element and bi — 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 ai.

He can perform the following operation any number of times:

Select any two elements i and j such that bi≠bj 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 ai (1≤ai≤105) — the value of the i-th element.

The third line containts n integers bi (bi∈{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 bi≠bj. 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.


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 a1,a2,…,an, 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 ai and bj is said to match if:

i=j, that is, they are at the same index.
ai=bj
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 c1:=c2,c2:=c3,…,cn:=c1 simultaneously. Likewise, a single cyclic shift to the right on any permutation c is an operation that sets c1:=cn,c2:=c1,…,cn:=cn−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⋅105) — the size of the arrays.

The second line contains n integers a1, a2, ..., an (1≤ai≤n) — the elements of the first permutation.

The third line contains n integers b1, b2, ..., bn (1≤bi≤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

input1

5
1 2 3 4 5
2 3 4 5 1

output1

5

input2

5
5 4 3 2 1
1 2 3 4 5

output2

1

input3

4
1 3 2 4
4 2 3 1

output3

2

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.


D. Solve The Maze

》英文原题《

Vivek has encountered a problem. He has a maze that can be represented as an n×m grid. Each of the grid cells may represent the following:

Empty — '.'
Wall — '#'
Good person — 'G'
Bad person — 'B'
The only escape from the maze is at cell (n,m).

A person can move to a cell only if it shares a side with their current cell and does not contain a wall. Vivek wants to block some of the empty cells by replacing them with walls in such a way, that all the good people are able to escape, while none of the bad people are able to. A cell that initially contains 'G' or 'B' cannot be blocked and can be travelled through.

Help him determine if there exists a way to replace some (zero or more) empty cells with walls to satisfy the above conditions.

It is guaranteed that the cell (n,m) is empty. Vivek can also block this cell.

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 two integers n, m (1≤n,m≤50) — the number of rows and columns in the maze.

Each of the next n lines contain m characters. They describe the layout of the maze. If a character on a line equals '.', the corresponding cell is empty. If it equals '#', the cell has a wall. 'G' corresponds to a good person and 'B' corresponds to a bad person.

Output

For each test case, print "Yes" if there exists a way to replace some empty cells with walls to satisfy the given conditions. Otherwise print "No"

You may print every letter in any case (upper or lower).

Example

input

6
1 1
.
1 2
G.
2 2
#B
G.
2 3
G.#
B#.
3 3
#B.
#..
GG.
2 2
#B
B.

output

Yes
Yes
No
No
Yes
Yes

Note

For the first and second test cases, all conditions are already satisfied.

For the third test case, there is only one empty cell (2,2), and if it is replaced with a wall then the good person at (1,2) will not be able to escape.

For the fourth test case, the good person at (1,1) cannot escape.

For the fifth test case, Vivek can block the cells (2,3) and (2,2).

For the last test case, Vivek can block the destination cell (2,2).


E. Maximum Subsequence Value

》英文原题《

Ridhiman challenged Ashish to find the maximum valued subsequence of an array a of size n consisting of positive integers.

The value of a non-empty subsequence of k elements of a is defined as ∑2i over all integers i≥0 such that at least max(1,k−2) elements of the subsequence have the i-th bit set in their binary representation (value x has the i-th bit set in its binary representation if ⌊x2i⌋mod2 is equal to 1).

Recall that b is a subsequence of a, if b can be obtained by deleting some(possibly zero) elements from a.

Help Ashish find the maximum value he can get by choosing some subsequence of a.

Input

The first line of the input consists of a single integer n (1≤n≤500) — the size of a.

The next line consists of n space-separated integers — the elements of the array (1≤ai≤1018).

Output

Print a single integer — the maximum value Ashish can get by choosing some subsequence of a.

Examples

input1

3
2 1 3

output1

3

input2

3
3 1 4

output2

7

input3

1
1

output3

1

input4

4
7 7 1 1

output4

7

Note

For the first test case, Ashish can pick the subsequence {2,3} of size 2. The binary representation of 2 is 10 and that of 3 is 11. Since max(k−2,1) is equal to 1, the value of the subsequence is 20+21 (both 2 and 3 have 1-st bit set in their binary representation and 3 has 0-th bit set in its binary representation). Note that he could also pick the subsequence {3} or {2,1,3}.

For the second test case, Ashish can pick the subsequence {3,4} with value 7.

For the third test case, Ashish can pick the subsequence {1} with value 1.

For the fourth test case, Ashish can pick the subsequence {7,7} with value 7.


F. Swaps Again

》英文原题《

Ayush, Ashish and Vivek are busy preparing a new problem for the next Codeforces round and need help checking if their test cases are valid.

Each test case consists of an integer n and two arrays a and b, of size n. If after some (possibly zero) operations described below, array a can be transformed into array b, the input is said to be valid. Otherwise, it is invalid.

An operation on array a is:

select an integer k (1≤k≤⌊n2⌋)
swap the prefix of length k with the suffix of length k
For example, if array a initially is {1,2,3,4,5,6}, after performing an operation with k=2, it is transformed into {5,6,3,4,1,2}.

Given the set of test cases, help them determine if each one is valid or invalid.

Input

The first line contains one integer t (1≤t≤500) — the number of test cases. The description of each test case is as follows.

The first line of each test case contains a single integer n (1≤n≤500) — the size of the arrays.

The second line of each test case contains n integers a1, a2, ..., an (1≤ai≤109) — elements of array a.

The third line of each test case contains n integers b1, b2, ..., bn (1≤bi≤109) — elements of array b.

Output

For each test case, print "Yes" if the given input is valid. Otherwise print "No".

You may print the answer in any case.

Example

input

5
2
1 2
2 1
3
1 2 3
1 2 3
3
1 2 4
1 3 4
4
1 2 3 2
3 1 2 2
3
1 2 3
1 3 2

output

yes
yes
No
yes
No

Note

For the first test case, we can swap prefix a[1:1] with suffix a[2:2] to get a=[2,1].

For the second test case, a is already equal to b.

For the third test case, it is impossible since we cannot obtain 3 in a.

For the fourth test case, we can first swap prefix a[1:1] with suffix a[4:4] to obtain a=[2,2,3,1]. Now we can swap prefix a[1:2] with suffix a[3:4] to obtain a=[3,1,2,2].

For the fifth test case, it is impossible to convert a to b.


G.Secure Password

》英文原题《

版权声明:本文为 溪月阁 | MoBrook 博主「 皓月 」的原创文章遵循用 CC BY-NC-SA 4.0 版权协议进行许可,转载请附上原文出处链接及本声明。

本文链接https://mobrook.cn/index.php/codeforces-1365/

上一篇:

下一篇: