Problem Statement

There are N piles of stones, and the i-th pile (1\le i\le N) has A_i stones.

Alice and Bob will play the following game using these piles:

• Starting with Alice, the two players take turns alternately.
• In each turn, the player chooses one non-empty pile and removes one or more stones from that pile. However, the player cannot make a move that changes the bitwise \mathrm{OR} of the numbers of stones of all piles.

The player who cannot make a move first loses.

Determine which player wins when both players play optimally.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 10^5
• 2\le N \le 2\times 10^5
• The sum of N over all test cases is at most 2\times 10^5.
• 1\le A_i \le 10^9
• All input values are integers.

Sample Input 1

4
3
3 4 6
3
7 7 7
3
9 3 5
10
1 9 1 3 7 9 10 9 7 3

Sample Output 1

Alice
Bob
Bob
Alice

Consider the first test case.

Initially, the bitwise \mathrm{OR} of the numbers of stones of all piles is 3\ \mathrm{OR}\ 4\ \mathrm{OR}\ 6=7.

The moves Alice can make are as follows:

• Remove two stones from the first pile.
• Remove one or more stones from the second pile.
• Remove one or more stones from the third pile.

For example, if Alice removes one stone from the first pile, the bitwise \mathrm{OR} of the numbers of stones of all piles becomes 2\ \mathrm{OR}\ 4\ \mathrm{OR}\ 6=6. Therefore, Alice cannot make the move of removing one stone from the first pile.

If Alice removes six stones from the third pile, Bob cannot make any move in the next turn. Therefore, the winner when both players play optimally is Alice.

Problem Statement

You are given positive integers N and K.

Find one length-N sequence of positive integers A=(A_1,A_2,\ldots,A_N) with the minimum value of A_N among the ones that satisfy all of the following conditions.

• A is non-decreasing. That is, A_i \le A_{i+1} for 1\le i\le N-1.
• \displaystyle \sum_{i=1}^{N-1} (A_{i+1} \bmod A_i)=K.

You are given T test cases; solve each of them.

Constraints

• 1\le T \le 10^5
• 2\le N \le 2\times 10^5
• The sum of N over all test cases is at most 2\times 10^5.
• 1\le K\le 10^9
• All input values are integers.

Sample Input 1

2
5 3
2 3

Sample Output 1

1 2 3 4 5
4 7

Consider the first test case.

A=(1,2,3,4,5) is non-decreasing and satisfies \displaystyle \sum_{i=1}^{N-1} (A_{i+1} \bmod A_i) = (2\bmod 1) + (3\bmod 2) + (4\bmod 3) + (5\bmod 4)=3=K, so it satisfies all conditions.

There does not exist an A that satisfies all conditions and has a value of A_N less than 5, so printing A=(1,2,3,4,5) will be accepted.

Other than this, printing A=(2,3,4,5,5) or A=(2,3,3,5,5) will also be accepted.

Problem Statement

You are given positive integers C and X that are less than 2^{30}.

Determine whether there exists a positive integer n that satisfies all of the following conditions, and if it exists, find one such n.

• 1\le n < 2^{60}
• (n \oplus C) \bmod n=X

Here, n \oplus C denotes the bitwise \mathrm{XOR} of n and C.

You are given T test cases, solve each of them.

Constraints

• 1\le T\le 2\times 10^5
• 1\le C,X < 2^{30}
• All input values are integers.

Sample Input 1

3
10 6
2 3
777 153

Sample Output 1

7
-1
208

Consider the first test case.

n=7 satisfies all conditions because (n\oplus C) \bmod n = (7 \oplus 10) \bmod 7 = 13\bmod 7 = 6=X. Therefore, printing 7 on the first line will be accepted.

Other than this, printing n=12,18,19 etc. will also be accepted.

Problem Statement

You are given an integer sequence Y=(Y_1,Y_2,\ldots,Y_N) of length N where each element is between 1 and N inclusive.

Determine whether there exists an N \times N integer matrix A=(A_{i,j}) (1\le i , j \le N) that satisfies all of the following conditions, and if it exists, find one such matrix.

• 1\le A_{i,j} \le N (1\le i \le N, 1\le j\le N)
• A_{i,j}=A_{j,i} (1\le i\le N, 1\le j\le N)
• A_{i,j_1}\neq A_{i,j_2} (1\le i\le N, 1\le j_1 < j_2 \le N)
• A_{i,Y_i}=1 (1\le i\le N)

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 5000
• 1\le N \le 500
• The sum of N^2 over all test cases is at most 500^2.
• 1\le Y_i\le N
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
1 2 3
2 3 1
3 1 2
No
Yes
1
Yes
1 2 5 4 3
2 3 1 5 4
5 1 4 3 2
4 5 3 2 1
3 4 2 1 5

Consider the first test case.

It can be verified that the A in the sample output satisfies all conditions. Other than this, for example, the following A will also be accepted:

1 3 2
3 2 1
2 1 3

Problem Statement

You are given positive integers N, X, Y and a length-N integer sequence A=(A_1,A_2,\ldots,A_N).

There are N piles of stones, and the i-th pile (1\le i\le N) has A_i stones.

Alice and Bob will play the following game using these piles:

• Starting with Alice, the two players take turns alternately.
• In each turn, the player chooses one non-empty pile and removes one or two stones from that pile. However, the player cannot make a move such that the number of stones in that pile becomes a multiple of X or a multiple of Y after removing stones.

The player who cannot make a move first loses.

Determine which player wins when both players play optimally.

You are given T test cases, solve each of them.

Constraints

• 1\le T \le 2\times 10^5
• 1\le N \le 2\times 10^5
• The sum of N over all test cases is at most 2\times 10^5.
• 1\le X < Y\le 10^9
• 1\le A_i \le 10^{18}
• All input values are integers.

Sample Input 1

3
2 3 5
4 12
5 1 2
1 2 3 4 5
6 530 879
17031 42909 97721 34323 39597 26999

Sample Output 1

Alice
Bob
Alice

Consider the first test case.

For example, the game proceeds as follows:

• Alice removes two stones from the first pile. The first pile has two stones remaining.
• Bob removes one stone from the second pile. The second pile has eleven stones remaining.
• Alice removes one stone from the first pile. The first pile has one stone remaining.
• Bob cannot make a move, so Bob loses and Alice wins.

In this test case, Alice always wins no matter how both players make their moves. Therefore, print Alice on the first line.