Problem Statement

Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.

The grid is said to be good if and only if the following condition is satisfied:

• From (1, 1), we can reach (H, W) by moving one square right or down repeatedly, while always being on a white square.

Note that (1, 1) and (H, W) must be white if the grid is good.

Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.

• Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) - that is, from white to black and vice versa.

Constraints

• 2 \leq H, W \leq 100

Sample Input 1

3 3
.##
.#.
##.

Sample Output 1

1

Do the operation with (r_0, c_0, r_1, c_1) = (2, 2, 2, 2) to change just the color of (2, 2), and we are done.

Sample Input 2

2 2
#.
.#

Sample Output 2

2

Sample Input 3

4 4
..##
#...
###.
###.

Sample Output 3

0

No operation may be needed.

Sample Input 4

5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.

Sample Output 4

4

Problem Statement

Given is a sequence of N digits a_1a_2\ldots a_N, where each element is 1, 2, or 3. Let x_{i,j} defined as follows:

• x_{1,j} := a_j \quad (1 \leq j \leq N)
• x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N and 1 \leq j \leq N+1-i)

Find x_{N,1}.

Constraints

• 2 \leq N \leq 10^6
• a_i = 1,2,3 (1 \leq i \leq N)

Sample Input 1

4
1231

Sample Output 1

1

x_{1,1},x_{1,2},x_{1,3},x_{1,4} are respectively 1,2,3,1.

x_{2,1},x_{2,2},x_{2,3} are respectively |1-2| = 1,|2-3| = 1,|3-1| = 2.

x_{3,1},x_{3,2} are respectively |1-1| = 0,|1-2| = 1.

Finally, x_{4,1} = |0-1| = 1, so the answer is 1.

Sample Input 2

10
2311312312

Sample Output 2

0

Problem Statement

Given are simple undirected graphs X, Y, Z, with N vertices each and M_1, M_2, M_3 edges, respectively. The vertices in X, Y, Z are respectively called x_1, x_2, \dots, x_N, y_1, y_2, \dots, y_N, z_1, z_2, \dots, z_N. The edges in X, Y, Z are respectively (x_{a_i}, x_{b_i}), (y_{c_i}, y_{d_i}), (z_{e_i}, z_{f_i}).

Based on X, Y, Z, we will build another undirected graph W with N^3 vertices. There are N^3 ways to choose a vertex from each of the graphs X, Y, Z. Each of these choices corresponds to the vertices in W one-to-one. Let (x_i, y_j, z_k) denote the vertex in W corresponding to the choice of x_i, y_j, z_k.

We will span edges in W as follows:

• For each edge (x_u, x_v) in X and each w, l, span an edge between (x_u, y_w, z_l) and (x_v, y_w, z_l).
• For each edge (y_u, y_v) in Y and each w, l, span an edge between (x_w, y_u, z_l) and (x_w, y_v, z_l).
• For each edge (z_u, z_v) in Z and each w, l, span an edge between (x_w, y_l, z_u) and (x_w, y_l, z_v).

Then, let the weight of the vertex (x_i, y_j, z_k) in W be 1,000,000,000,000,000,000^{(i +j + k)} = 10^{18(i + j + k)}. Find the maximum possible total weight of the vertices in an independent set in W, and print that total weight modulo 998,244,353.

Constraints

• 2 \leq N \leq 100,000
• 1 \leq M_1, M_2, M_3 \leq 100,000
• 1 \leq a_i, b_i, c_i, d_i, e_i, f_i \leq N
• X, Y, and Z are simple, that is, they have no self-loops and no multiple edges.

Sample Input 1

2
1
1 2
1
1 2
1
1 2

Sample Output 1

46494701

The maximum possible total weight of an independent set is that of the set (x_2, y_1, z_1), (x_1, y_2, z_1), (x_1, y_1, z_2), (x_2, y_2, z_2). The output should be (3 \times 10^{72} + 10^{108}) modulo 998,244,353, which is 46,494,701.

Sample Input 2

3
3
1 3
1 2
3 2
2
2 1
2 3
1
2 1

Sample Output 2

883188316

Sample Input 3

100000
1
1 2
1
99999 100000
1
1 100000

Sample Output 3

318525248

Problem Statement

Given is a positive integer N. Find the number of permutations (P_1,P_2,\cdots,P_{3N}) of (1,2,\cdots,3N) that can be generated through the procedure below. This number can be enormous, so print it modulo a prime number M.

• Make N sequences A_1,A_2,\cdots,A_N of length 3 each, using each of the integers 1 through 3N exactly once.
• Let P be an empty sequence, and do the following operation 3N times.
  • Among the elements that are at the beginning of one of the sequences A_i that is non-empty, let the smallest be x.
  • Remove x from the sequence, and add x at the end of P.

Constraints

• 1 \leq N \leq 2000
• 10^8 \leq M \leq 10^9+7
• M is a prime number.
• All values in input are integers.

Sample Input 1

1 998244353

Sample Output 1

6

All permutations of length 3 count.

Sample Input 2

2 998244353

Sample Output 2

261

Sample Input 3

314 1000000007

Sample Output 3

182908545

Problem Statement

Given are a positive integer N and a sequence of length 2^N consisting of 0s and 1s: A_0,A_1,\ldots,A_{2^N-1}. Determine whether there exists a closed curve C that satisfies the condition below for all 2^N sets S \subseteq \{0,1,\ldots,N-1 \}. If the answer is yes, construct one such closed curve.

• Let x = \sum_{i \in S} 2^i and B_S be the set of points \{ (i+0.5,0.5) | i \in S \}.
• If there is a way to continuously move the closed curve C without touching B_S so that every point on the closed curve has a negative y-coordinate, A_x = 1.
• If there is no such way, A_x = 0.

For instruction on printing a closed curve, see Output below.

Notes

C is said to be a closed curve if and only if:

• C is a continuous function from [0,1] to \mathbb{R}^2 such that C(0) = C(1).

We say that a closed curve C can be continuously moved without touching a set of points X so that it becomes a closed curve D if and only if:

• There exists a function f : [0,1] \times [0,1] \rightarrow \mathbb{R}^2 that satisfies all of the following.
  • f is continuous.
  • f(0,t) = C(t).
  • f(1,t) = D(t).
  • f(x,t) \notin X.

Constraints

• 1 \leq N \leq 8
• A_i = 0,1 \quad (0 \leq i \leq 2^N-1)
• A_0 = 1

Sample Input 1

1
10

Sample Output 1

Possible
4
0 0
0 1
1 1
1 0
0 0

When S = \emptyset, we can move this curve so that every point on it has a negative y-coordinate.

When S = \{0\}, we cannot do so.

Sample Input 2

2
1000

Sample Output 2

Possible
6
1 0
2 0
2 1
1 1
0 1
0 0
1 0

The output represents the following curve:

Sample Input 3

2
1001

Sample Output 3

Impossible

Sample Input 4

1
11

Sample Output 4

Possible
0
1 1

Problem Statement

There are N jewelry shops numbered 1 to N.

Shop i (1 \leq i \leq N) sells K_i kinds of jewels. The j-th of these jewels (1 \leq j \leq K_i) has a size and price of S_{i,j} and P_{i,j}, respectively, and the shop has C_{i,j} jewels of this kind in stock.

A jewelry box is said to be good if it satisfies all of the following conditions:

• For each of the jewelry shops, the box contains one jewel purchased there.
• All of the following M restrictions are met.
  • Restriction i (1 \leq i \leq M): (The size of the jewel purchased at Shop V_i)\leq (The size of the jewel purchased at Shop U_i)+W_i

Answer Q questions. In the i-th question, given an integer A_i, find the minimum total price of jewels that need to be purchased to make A_i good jewelry boxes. If it is impossible to make A_i good jewelry boxes, report that fact.

Constraints

• 1 \leq N \leq 30
• 1 \leq K_i \leq 30
• 1 \leq S_{i,j} \leq 10^9
• 1 \leq P_{i,j} \leq 30
• 1 \leq C_{i,j} \leq 10^{12}
• 0 \leq M \leq 50
• 1 \leq U_i,V_i \leq N
• U_i \neq V_i
• 0 \leq W_i \leq 10^9
• 1 \leq Q \leq 10^5
• 1 \leq A_i \leq 3 \times 10^{13}
• All values in input are integers.

Sample Input 1

3
2
1 10 1
3 1 1
3
1 10 1
2 1 1
3 10 1
2
1 1 1
3 10 1
2
1 2 0
2 3 0
3
1
2
3

Sample Output 1

3
42
-1

Let (i,j) represent the j-th jewel sold at Shop i. The answer to each query is as follows:

• A_1=1: Making a box with (1,2),(2,2),(3,1) costs 1+1+1=3, which is optimal.
• A_2=2: Making a box with (1,1),(2,1),(3,1) and another with (1,2),(2,3),(3,2) costs (10+10+1)+(1+10+10)=42, which is optimal.
• A_3=3: We cannot make three good boxes.

Sample Input 2

5
5
86849520 30 272477201869
968023357 28 539131386006
478355090 8 194500792721
298572419 6 894877901270
203794105 25 594579473837
5
730211794 22 225797976416
842538552 9 420531931830
871332982 26 81253086754
553846923 29 89734736118
731788040 13 241088716205
5
903534485 22 140045153776
187101906 8 145639722124
513502442 9 227445343895
499446330 6 719254728400
564106748 20 333423097859
5
332809289 8 640911722470
969492694 21 937931959818
207959501 11 217019915462
726936503 12 382527525674
887971218 17 552919286358
5
444983655 13 487875689585
855863581 6 625608576077
885012925 10 105520979776
980933856 1 711474069172
653022356 19 977887412815
10
1 2 231274893
2 3 829836076
3 4 745221482
4 5 935448462
5 1 819308546
3 5 815839350
5 3 513188748
3 1 968283437
2 3 202352515
4 3 292999238
10
510266667947
252899314976
510266667948
374155726828
628866122125
628866122123
1
628866122124
510266667949
30000000000000

Sample Output 2

26533866733244
13150764378752
26533866733296
19456097795056
-1
33175436167096
52
33175436167152
26533866733352
-1