Problem Statement

You are given N distinct strings S_1, \dots, S_N. Each of these strings is a string of length M consisting of 0 and 1.

Determine whether there exists a string T of length M consisting of 0 and 1 satisfying the following condition, and if so, construct one example.

• Every string S_i matches T in at least one position.
  • More formally, for every integer i (1 \le i \le N), there exists an integer x_i (1 \le x_i \le M) such that the x_i-th character of S_i and the x_i-th character of T are the same.

Constraints

• N and M are integers.
• 1 \leq N \leq 2 \times 10^4
• 1 \leq M \leq 100
• S_i is a string of length M consisting of 0 and 1.
• S_1, \dots, S_N are distinct.

Sample Input 1

5 3
000
111
110
100
011

Sample Output 1

Yes
101

If we set T to 101, the following holds:

• The 2nd character of S_1 and the 2nd character of T are the same.
• The 1st character of S_2 and the 1st character of T are the same.
• The 1st character of S_3 and the 1st character of T are the same.
• The 2nd character of S_4 and the 2nd character of T are the same.
• The 3rd character of S_5 and the 3rd character of T are the same.

Sample Input 2

4 2
00
01
10
11

Sample Output 2

No

No T satisfies the condition.

Sample Input 3

9 50
00001000011111100011111000011111000001000001111100
00010100010000010100000100100000100011000010000010
00100010010000010100000000000000100101000010000010
01000001011111100100000000011111000001000001111110
01111111010001000100000000100000000001000000000010
01000001010000100100000100100000000001000010000010
01000001010000010011111000111111100111110001111100
00000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111

Sample Output 3

Yes
10101010101010101010101011010101011010101101010101

Problem Statement

You are given an integer N and a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

For a permutation Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,\ldots,N), let Q'=(Q_1',Q_2',\ldots,Q_N') be the lexicographically smallest permutation obtainable by performing the following operation exactly once:

• Choose a pair of integers (l,r) satisfying 1\le l\le r\le N, and reverse Q_l,Q_{l+1},\ldots,Q_r. More precisely, replace Q with (Q_1,Q_2,\ldots,Q_{l-1},Q_r,Q_{r-1},\ldots,Q_l,Q_{r+1},Q_{r+2},\ldots,Q_N).

Find the number, modulo 998244353, of permutations Q of (1,2,\ldots,N) such that Q'=P.

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

Constraints

• 1\le T
• 1\le N\le 5\times 10^5
• P is a permutation of (1,2,\ldots,N).
• The sum of N over all test cases is at most 5\times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
1
0
9

Consider the first test case.

For example, when Q=(2,3,1), choosing (l,r)=(1,3) gives (1,3,2). No permutation lexicographically smaller than (1,3,2) can be obtained, so we have Q'=(1,3,2). Thus, Q=(2,3,1) satisfies Q'=P.

There are two permutations Q such that Q'=P: Q=(2,3,1),(3,1,2).

Problem Statement

Note: This problem has almost the same setting as Problem G. The differences in the problem statements are shown in red bold.

There is an underground apartment represented by a grid with H rows and W columns. The cell at the i-th row from the top and the j-th column from the left is denoted as cell (i,j).

The entrance to the underground apartment is at cell (1,1).

The underground apartment has N doors. The k-th door is located at cell (A_k, B_k).

Inside the underground apartment, a salesman can perform the following two types of moves any number of times, in any order:

• He can walk to a horizontally adjacent cell (left or right) from his current cell. The cost of this move is 1.
• If his current cell is in column 1 or column W, he can move to a vertically adjacent cell (up or down) by elevator. The cost of this move is \mathbf{0}.

His goal is to start from cell (1,1), repeat moves, visit all N cells with doors at least once, and then arrive at cell (1,1).

Find the minimum total cost needed to achieve his goal.

Constraints

• 1 \leq H \leq 10^9
• 2 \leq W \leq 10^9
• 1 \leq N \leq 3 \times 10^5
• 1 \leq A_k \leq H
• 1 \leq B_k \leq W
• (A_1, B_1), \dots, (A_N, B_N) are distinct.
• All input values are integers.

Sample Input 1

6 8
7
1 4
2 2
2 7
3 1
6 3
6 4
6 6

Sample Output 1

18

By moving as follows, the goal can be achieved with a total cost of 18:

• Start from cell (1,1).
• Move 1 cell down and 1 cell right from cell (1,1) to visit cell (2,2) (cost 1).
• Move 1 cell left and 1 cell down from cell (2,2) to visit cell (3,1) (cost 1).
• Move 3 cells down and 2 cells right from cell (3,1) to visit cell (6,3) (cost 2).
• Move 1 cell right from cell (6,3) to visit cell (6,4) (cost 1).
• Move 2 cells right from cell (6,4) to visit cell (6,6) (cost 2).
• Move 2 cells right, 4 cells up, and 1 cell left from cell (6,6) to visit cell (2,7) (cost 3).
• Move 1 cell right, 1 cell up, and 4 cells left from cell (2,7) to visit cell (1,4) (cost 5).
• Move 3 cells left from cell (1,4) to arrive at cell (1,1) (cost 3).

Sample Input 2

1000000000 1000000000
2
888888888 600000000
1000000000 700000000

Sample Output 2

1999999998

Problem Statement

There is an N \times N grid. The cell at the i-th row from the top and the j-th column from the left is denoted as cell (i,j). Cell (i,j) initially contains A_{i,j} stones.

Alice and Bob play the following game using this grid.

• Starting with Alice, the two players alternate taking turns.
• On each turn, the player chooses a cell and moves at least 1 and at most K stones from it together to an adjacent cell above or to the left. Specifically, the following steps are performed in order:
  1. Choose a cell (i,j) that contains at least 1 stone. Cell (1,1) cannot be chosen.
  2. Let c be the number of stones in cell (i,j), and choose an integer x satisfying 1 \le x \le \min(c,K).
  3. Choose as the destination either cell (i-1,j) (if it exists) or cell (i,j-1) (if it exists), then remove x stones from cell (i,j) and move all of them to that cell.

The player who cannot take a turn first loses.

Determine which player wins when both play optimally.

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

Constraints

• 1\le T
• 2\le N\le 100
• 1\le K\le 10^9
• 0\le A_{i,j}\le 10^9
• The sum of N^2 over all test cases is at most 3\times 10^5.
• All input values are integers.

Sample Input 1

3
2 2
0 1
3 2
3 1
1 1 1
1 1 1
1 1 1
4 4
3 8 5 3
4 2 0 6
0 9 10 4
1 9 7 10

Sample Output 1

Alice
Bob
Alice

Consider the first test case.

For example, the game may proceed as follows (note that the players are not necessarily playing optimally):

• Alice's turn: Choose cell (2,2) and remove 2 stones. Move the removed stones to cell (1,2).
• Bob's turn: Choose cell (1,2) and remove 2 stones. Move the removed stones to cell (1,1).
• Alice's turn: Choose cell (2,1) and remove 2 stones. Move the removed stones to cell (1,1).
• Bob's turn: Choose cell (2,1) and remove 1 stone. Move the removed stone to cell (1,1).
• Alice's turn: Choose cell (1,2) and remove 1 stone. Move the removed stone to cell (1,1).
• Bob's turn: Bob cannot take a turn and loses.

By playing optimally, Alice can always beat Bob. Thus, output Alice on the first line.

Problem Statement

There is a shortcake in the shape of a 2H \times 2W grid. The cell at the i-th row from the top and the j-th column from the left is denoted as cell (i,j). Cell (i,j) has one strawberry on it if S_{i,j}= o, and nothing if S_{i,j}= x. It is guaranteed that exactly 2HW cells have strawberries.

Divide each cell of this shortcake into regions A and B so that all of the following conditions are satisfied:

• Every cell belongs to exactly one of regions A and B.
• Both regions A and B are connected. That is, for any two cells in the same region, one can move between them by repeatedly moving to an adjacent cell (sharing an edge) in the same region.
• Both regions A and B contain exactly 2HW cells each.
• Both regions A and B contain exactly HW strawberries each.

It can be proved that such a partition always exists.

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

Constraints

• 1\le T
• 1\le H\le W
• H\times W\le 10^6
• S_{i,j} is o or x.
• There are exactly 2HW pairs (i,j) with S_{i,j}= o.
• The sum of H\times W over all test cases is at most 10^6.
• T, H, W are integers.

Sample Input 1

3
1 1
ox
xo
1 2
oxxx
ooxo
2 3
oooxxx
oooxxx
xoxxxx
xooooo

Sample Output 1

AA
BB
AAAB
ABBB
AAABBB
AAAAAB
ABABAB
ABBBBB

Consider the first test case.

In the sample output, both regions A and B are connected and contain two cells each. Also, region A contains the strawberry at cell (1,1), and region B contains the strawberry at cell (2,2).

Additionally, for example, the following output is accepted:

AB
AB

Problem Statement

You are given a sequence of non-negative integers A=(A_1,A_2,\ldots,A_N) of length N.

You can perform the following operation on A zero or more times. In one operation, perform the following steps in order:

• Choose a pair of integers (l,r) satisfying all of the following conditions:
  • 1\le l\le r\le N
  • A_l,A_{l+1},\ldots,A_r all have the same parity (that is, they are all even or all odd).
• For each k=l,l+1,\ldots,r, replace A_k with \displaystyle\left\lfloor\frac{A_k}2 \right\rfloor.

Find the minimum number of operations needed to make all elements of A equal to 0.

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

Constraints

• 1\le T
• 1\le N\le 30
• 0\le A_i< 2^{60}
• The sum of N over all test cases is at most 30.
• All input values are integers.

Sample Input 1

4
2
9 12
3
3 1 2
1
0
7
6 28 24 18 12 22 1

Sample Output 1

5
3
0
10

Consider the first test case.

By performing operations as follows, all elements of A can be made 0 in five operations:

• Choose (l,r)=(1,1). A becomes (4,12).
• Choose (l,r)=(1,2). A becomes (2,6).
• Choose (l,r)=(1,2). A becomes (1,3).
• Choose (l,r)=(1,2). A becomes (0,1).
• Choose (l,r)=(2,2). A becomes (0,0).

It is impossible to make all elements of A equal to 0 in fewer than five operations, so output 5.

Problem Statement

Note: This problem has almost the same setting as Problem C. The differences in the problem statements are shown in red bold.

There is an underground apartment represented by a grid with H rows and W columns. The cell at the i-th row from the top and the j-th column from the left is denoted as cell (i,j).

The entrance to the underground apartment is at cell (1,1).

The underground apartment has N doors. The k-th door is located at cell (A_k, B_k).

Inside the underground apartment, a salesman can perform the following two types of moves any number of times, in any order:

• He can walk to a horizontally adjacent cell (left or right) from his current cell. The cost of this move is 1.
• If his current cell is in column 1 or column W, he can move to a vertically adjacent cell (up or down) by stairs. The cost of this move is \mathbf{1}.

His goal is to start from cell (1,1), repeat moves, visit all N cells with doors at least once, and then arrive at cell (1,1).

Find the minimum total cost needed to achieve his goal.

Constraints

• 1 \leq H \leq 10^9
• 2 \leq W \leq 10^9
• 1 \leq N \leq 3 \times 10^5
• 1 \leq A_k \leq H
• 1 \leq B_k \leq W
• (A_1, B_1), \dots, (A_N, B_N) are distinct.
• All input values are integers.

Sample Input 1

6 8
7
1 4
2 2
2 7
3 1
6 3
6 4
6 6

Sample Output 1

28

By moving as follows, the goal can be achieved with a total cost of 28:

• Start from cell (1,1).
• Move 1 cell down and 1 cell right from cell (1,1) to visit cell (2,2) (cost 2).
• Move 1 cell left and 1 cell down from cell (2,2) to visit cell (3,1) (cost 2).
• Move 3 cells down and 2 cells right from cell (3,1) to visit cell (6,3) (cost 5).
• Move 1 cell right from cell (6,3) to visit cell (6,4) (cost 1).
• Move 2 cells right from cell (6,4) to visit cell (6,6) (cost 2).
• Move 2 cells right, 4 cells up, and 1 cell left from cell (6,6) to visit cell (2,7) (cost 7).
• Move 1 cell right, 1 cell up, and 4 cells left from cell (2,7) to visit cell (1,4) (cost 6).
• Move 3 cells left from cell (1,4) to arrive at cell (1,1) (cost 3).

Sample Input 2

1000000000 1000000000
2
888888888 600000000
1000000000 700000000

Sample Output 2

3999999996