Problem Statement

There is an N \times N grid. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.

You are given N \times N characters S_{1,1}, \dots , S_{N,N}. Each character is a digit (0 to 9) or ?. Determine if it is possible to replace each ? with a digit to satisfy the following condition, and if possible, output one such way of replacement.

For each 1 \le i,j \le N, write S_{i,j} as an integer in cell (i,j).
For a path from cell (1,1) to cell (N,N) by repeating moves only to adjacent cells to the right or down, let the score of the path be the sum of the integers written in the cells on the path (including the start and end points).
Then, for all \binom{2N-2}{N-1} possible paths, the scores are all equal.

Constraints

• 2 \le N \le 100
• S_{i,j} is a digit (0 to 9) or ?.

Sample Input 1

3
101
0??
1??

Sample Output 1

101
010
101

It is possible to replace ? with digits so that the scores of all paths are 3.

Sample Input 2

4
2026
?2?8
????
?214

Sample Output 2

-1

No replacement can satisfy the condition.

Sample Input 3

2
99
99

Sample Output 3

99
99

Problem Statement

There is a connected simple undirected graph with N vertices and M edges, where the vertices are numbered 1, \dots ,N and the edges are numbered 1, \dots ,M. Edge i connects vertices A_i and B_i. Also, there are a total of N+1 cards, one each with the integers from 0 to N written on them.

Snuke performed the following operations in order:

1. Place one card on each vertex, and eat the remaining one card.
2. For each i\ (1 \le i \le M), write on edge i the bitwise \mathrm{XOR} of the integers written on the two cards placed on vertices A_i and B_i. Let this integer be X_i.
3. Discard all cards placed on the vertices.

Given the information about the graph (N,M,A_1,\dots ,A_M,B_1,\dots ,B_M,X_1,\dots ,X_M), determine the integer written on the card that Snuke ate. If it cannot be uniquely determined, output -1. It is guaranteed that the given X can be obtained by the above operations.

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

Constraints

• 1 \le T \le 10^4
• 1 \le N \le 2 \times 10^5
• 0 \le M \le 2 \times 10^5
• 1 \le A_i,B_i \le N
• The given graph is a connected simple undirected graph.
• X_1,\dots ,X_M can be obtained by the operations in the problem statement.
• The sum of N over all test cases is at most 2 \times 10^5.
• The sum of M over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
2 1
1 2 3
1 0
4 4
2 1 4
1 3 5
1 4 7
2 3 1

Sample Output 1

0
-1
2

For the first test case, the graph is as shown below.

The possible pairs of integers written on the cards placed on vertices 1 and 2 are (1,2) and (2,1); in either case, the integer written on the card Snuke ate is 0.

For the second test case, there are two possible integers written on the card Snuke ate: 0 and 1.

For the third test case, the graph is as shown below.

Problem Statement

There are N people numbered 1, \dots ,N. The strength of person i is P_i.

Each person is assigned to one of the teams A,B,C,D to form four teams. There are 4^N ways to form teams; among these, find the number, modulo 998244353, of formations that satisfy all of the following conditions.

• Each of the teams A,B,C,D has at least one person.
• The sum of the strengths of the people in team A equals the sum of the strengths of the people in team B.
• The sum of the strengths of the people in team C equals the sum of the strengths of the people in team D.

Constraints

• 4 \le N \le 500
• 1 \le P_i
• \sum_{1 \le i \le N} P_i \le 10^5
• All input values are integers.

Sample Input 1

4
1 1 2 2

Sample Output 1

8

The following eight team formations satisfy the conditions.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

0

No formations satisfy the conditions.

Sample Input 3

24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Sample Output 3

289359125

Problem Statement

There is an N \times N grid. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.

Output one way to write a non-negative integer in each cell so that the following condition is satisfied.

For a path from cell (1,1) to cell (N,N) by repeating moves only to adjacent cells to the right or down, let the score of the path be the sum of the integers written in the cells on the path (including the start and end points).
Then, for all \binom{2N-2}{N-1} possible paths, the scores are all distinct and all at most 6 \times 10^6.

Constraints

• 2 \le N \le 13

Sample Input 1

2

Sample Output 1

1 2
3 4

The score of the path that moves right then down is 7, and the score of the path that moves down then right is 8, satisfying the condition in the problem statement.

Sample Input 2

5

Sample Output 2

10443 257776 131299 258759 153153
103533 63158 120370 132605 22808
206213 155047 237224 121264 96487
213665 51789 237311 239387 27085
229301 125534 154776 40898 210765

Problem Statement

You are given integer sequences of length N, A = (A_1, \dots ,A_N) and B = (B_1, \dots ,B_N), and a positive integer K.

Each time you pay a cost of 1, you can perform adjacent swaps exactly K times. An adjacent swap refers to the following operation:

• Choose an integer i between 1 and N-1, inclusive, and swap A_i and A_{i+1}.

Determine if it is possible to make A match B. If possible, find the minimum cost required to make them match.

You are given T test cases; find the answer for each of them.

Constraints

• 1 \le T \le 10^5
• 2 \le N \le 3 \times 10^5
• 1 \le K \le 10^9
• 1 \le A_i,B_i \le N
• \{A_1,\dots ,A_N\} and \{B_1,\dots ,B_N\} match as multisets.
• The sum of N over all test cases is at most 3 \times 10^5.
• All input values are integers.

Sample Input 1

3
5 4
3 1 4 1 5
5 1 3 1 4
2 1000000000
1 2
2 1
10 13
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

Sample Output 1

2
-1
5

For the first test case, it is possible to make A and B match with a cost of 2 by performing the following operations:

1. Pay a cost of 1, and choose i as 3,1,4,1 in order for each adjacent swap, making A = (3,1,1,5,4).
2. Pay a cost of 1, and choose i as 3,1,2,1 in order for each adjacent swap, making A = (5,1,3,1,4).

For the second test case, it is impossible to make A and B match regardless of the cost.

Problem Statement

There is an H \times W grid. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.

Each cell is an empty cell or a wall cell, and this information is represented by H \times W characters S_{1,1},\dots ,S_{H,W}. Cell (i,j) is an empty cell if S_{i,j} is ., and a wall cell if it is #.

Initially, Takahashi is at cell (1,1). He can move to a cell adjacent to his current cell in one of the four directions (up, down, left, right) any number of times. However, he cannot move in the same direction twice in a row. Also, he cannot move to a wall cell or outside the grid.

Before starting to move, he can destroy zero or more wall cells to change them into empty cells. What is the minimum number of wall cells he needs to destroy to reach cell (H,W)? Under the constraints of this problem, it can be proved that there exists a way to destroy wall cells so that he can reach cell (H,W).

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

Constraints

• 1 \le T \le 1000
• 2 \le H, W \le 100
• S_{i,j} is . or #.
• S_{1,1} and S_{H,W} are ..
• The sum of HW over all test cases is at most 3 \times 10^4.

Sample Input 1

3
3 5
..##.
.#...
##.#.
2 3
..#
#..
13 13
.############
##.##..###..#
#.#.#.#.#.###
#...#..##.###
#.#.#.#.#.###
#.#.#.#.##..#
#############
#...##.##.#.#
###.#..##.#.#
#...##.##...#
#.####.####.#
#...#...###.#
############.

Sample Output 1

2
0
13

For the first test case, Takahashi can reach cell (H,W) by destroying two wall cells as shown below.

The left side shows an example of wall cells to destroy, and the right side shows an example of a movement path. Note that it is not necessary to minimize the number of moves, and it is allowed to visit the same cell more than once.

For the second test case, he can reach cell (H,W) without destroying any wall cells.