Problem Statement

You have an unlimited number of the following two types of polyominoes:

• A rectangular polyomino of size 2 (height) × 1 (width)
• An L-shaped polyomino formed by removing one 1 \times 1 square from a 2 \times 2 square

You are given a grid of size 2 (height) × N (width). You want to completely tile all cells of the grid using these polyominoes under the following conditions:

• Each cell of the grid must be covered by exactly one polyomino.
• You may rotate the polyominoes when placing them.

Find the number of ways to place the polyominoes satisfying these conditions. Note that two arrangements are considered different even if one can be obtained from the other by rotating or flipping the entire grid. Also, polyominoes of the same shape are indistinguishable.

Constraints

• 1 \leq N \leq 40
• N is an integer

Sample Input 1

3

Sample Output 1

5

There are 5 valid tilings as shown below.

Sample Input 2

40

Sample Output 2

25366833951139

Problem Statement

You are given a simple directed graph with N vertices and M edges. The vertices are numbered from 1 to N. The i-th edge goes from vertex u_i to vertex v_i.
This graph has no cycles.

Find the number of paths from vertex 1 to vertex N, modulo 998244353.

You are given T test cases. Solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min\left(\frac{N(N-1)}{2}, 2 \times 10^5\right)
• 1 \leq u_i \leq N
• 1 \leq v_i \leq N
• If i \neq j, then (u_i, v_i) \neq (u_j, v_j)
• The given graph is a simple directed graph with no cycles
• 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
4 4
1 2
2 3
3 4
2 4
5 4
1 2
2 3
4 5
1 3
7 18
1 6
1 4
6 4
6 3
4 3
1 5
6 5
4 5
3 5
1 2
6 2
4 2
3 2
5 2
6 7
4 7
5 7
2 7

Sample Output 1

2
0
24

For the first test case, there are 2 paths from vertex 1 to vertex 4:

• vertex 1 \to vertex 2 \to vertex 3 \to vertex 4
• vertex 1 \to vertex 2 \to vertex 4

Problem Statement

You are given three strings S_1, S_2, S_3, each consisting of lowercase English letters.
Find the number of strings T of length N (also consisting of lowercase English letters) such that none of S_1, S_2, S_3 appear as a subsequence of T. Output the answer modulo 998244353.

Constraints

• 1 \leq N \leq 10^3
• S_1, S_2, S_3 are non-empty strings of lowercase English letters with length at most 10
• N is an integer

Sample Input 1

2
abc de f

Sample Output 1

624

There are 676 strings of length 2 consisting of lowercase English letters. Among them, 1 string contains S_2 = de, and 51 strings contain S_3 = f. These sets do not overlap. Therefore, the answer is 676 - 1 - 51 = 624.

Sample Input 2

4
ab ab ab

Sample Output 2

453125

Note that subsequence in the condition is different from substring.
For example, accb contains ab as a subsequence, so it does not satisfy the condition.

Sample Input 3

1000
atcoder algorithm lectures

Sample Output 3

669410767

Problem Statement

In the AtCoder Kingdom, banknotes of denominations 1 yen, 10 yen, 100 yen, \dots, 10^{100} yen are used.

Alice wants to pay N yen to Bob. Find the minimum possible total number of banknotes exchanged, which is the sum of:

• the number of banknotes Alice gives to Bob, and
• the number of banknotes Bob gives back as change.

More precisely, for any integer M \geq N, consider:

• the minimum number of banknotes needed to represent exactly M yen, and
• the minimum number of banknotes needed to represent exactly M - N yen.

Find the minimum possible value of their sum.

You are given T test cases. Solve each of them.

Constraints

• 1 \leq T \leq 10^4
• 1 \leq N \leq 10^{18}
• All input values are integers

Sample Input 1

3
7
34
123456789123456789

Sample Output 1

4
7
44

In the first test case:

• Alice pays 10 yen using one 10-yen banknote, and
• Bob returns 3 yen as change using three 1-yen banknotes.

In this case, the total number of banknotes exchanged is 4, which is optimal.

Problem Statement

Your summer vacation starts today and lasts for N days.
There are M events. The i-th event starts on the morning of day A_i and ends on the evening of day B_i.

You are given Q queries. In each query, you are given two integers L and R, and you need to answer the following:

You decide to attend as many events as possible during the period from day L to day R.
However, you cannot join or leave an event in the middle. Therefore, you cannot attend multiple events whose time periods overlap, and you also cannot attend any event that starts before day L or ends after day R.
If you choose the events optimally, what is the maximum number of events you can attend?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq B_i \leq N
• 1 \leq L \leq R \leq N
• All input values are integers

Sample Input 1

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

Sample Output 1

2
0
1

For example, in the first query, you can attend the 1st and 2nd events, and this is the maximum.

Sample Input 2

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

Sample Output 2

1
1
1
0
2
1
0
1

Problem Statement

You are given a permutation P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N) and an integer array A_1, A_2, \dots, A_N of length N.

A subset S of the set \lbrace 1,2,\dots,N \rbrace is called a good set if it satisfies the following condition:

• For every pair of integers (x, y) such that x < y and x, y \in S, the following holds:
  • Let z be the integer such that P_z = \min(P_x, P_{x+1}, \dots, P_y). (Such a z is uniquely determined.) Then, it must hold that z \in S.

The cost of a good set S is defined as \displaystyle \sum_{i \in S} A_i.

For each K = 1, 2, \dots, N, find the minimum possible cost among all good sets of size K.

You are given T test cases. Solve each of them.

Constraints

• 1 \leq T \leq 5000
• 1 \leq N \leq 5000
• 1 \leq A_i \leq 10^9
• (P_1, P_2, \dots, P_N) is a permutation of (1,2,\dots,N)
• The sum of N over all test cases is at most 5000
• All input values are integers

Sample Input 1

3
4
4 1 2 3
1 8 2 4
6
5 3 2 4 6 1
73 38 30 85 27 45
10
4 10 3 7 2 6 8 9 5 1
853822501 687675302 281611653 844033520 423210108 339630584 780395612 207907746 285523486 359061085

Sample Output 1

1 6 11 15
27 57 95 140 213 298
207907746 493431232 833061816 1192122901 1537883577 1896944662 2584619964 3365015576 4209049096 5062871597

In the first test case:

• For K=1, S=\lbrace 1 \rbrace is optimal,
• For K=2, S=\lbrace 3,4 \rbrace is optimal,
• For K=3, S=\lbrace 1,2,3 \rbrace is optimal,
• For K=4, S=\lbrace 1,2,3,4 \rbrace is optimal.

Problem Statement

You are given an integer sequence A = (A_1, A_2, \dots, A_N) of length N.
Process Q queries. In each query, you are given an integer i (1 \leq i \leq N) and a non-negative integer v. Update A_i to v, and then solve the following problem. (The updates are permanent.)

There are N people standing on a number line at positions 1 to N, each with their mouth open. Person i is at position i. Each person has a parameter called hunger, and the hunger of person i is A_i.
You have an unlimited number of candies. You decide to perform the following sequence of actions exactly once to feed them:

• First, choose an integer x such that 1 \leq x \leq N, and stand at position x.
• Then, perform the following operations any number of times (possibly zero):
  • Let your current position be y. Move to position y-1, y, or y+1. However, you cannot move to a position where no person is standing.
  • Throw one candy into the mouth of the person at your current position.

After finishing all operations, let B_i be the number of candies given to person i. Find the minimum possible value of \displaystyle \sum_{i=1}^N \vert A_i - B_i \vert.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq i \leq N
• 0 \leq v \leq 10^9
• All input values are integers

Partial Score

This problem has partial scoring.

• If you solve the dataset with Q \leq 10, you will get 2 points.

Sample Input 1

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

Sample Output 1

1
2
1

Consider processing the first query. You need to solve the problem for A = (1,0,0,2).
In this case, the following actions achieve a value of 1, which is optimal:

• Choose x=3 and stand at position 3.
• Move to position 4 and give one candy to person 4.
• Stay at position 4 again and give another candy to person 4.
• End the operations. The resulting B becomes (0,0,0,2).

Sample Input 2

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

Sample Output 2

5
3
3
5
5
3
2
0
1

Problem Statement

You are given an N \times N grid. Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

The state of each cell is described by N strings S_1, S_2, \dots, S_N, each of length N.
If the j-th character of S_i is @, then cell (i,j) contains one coin. If it is ., then the cell is empty.

You start at cell (1,1). It is guaranteed that (1,1) is empty.

You may perform the following action any number of times (including zero):

• Let your current position be (i,j). Move to either the right cell (i,j+1) or the down cell (i+1,j). You cannot move outside the grid. If the destination cell contains a coin, you must pick it up.

For each x = 0, 1, \dots, 2N-2, solve the following:

• After performing some actions (possibly zero), you reach a cell (i,j) while having exactly x coins. How many possible cells (i,j) are there?

Constraints

• 2 \leq N \leq 4000
• S_1, S_2, \dots, S_N are strings of length N consisting of @ and .
• The first character of S_1 is .
• N is an integer

Partial Score

This problem has partial scoring.

• If you solve the dataset with N \leq 1500, you will get 2 points.

Sample Input 1

3
.@@
..@
@..

Sample Output 1

5
6
3
2
0

For example, when x=0, the possible cells (i,j) are (1,1), (2,1), (2,2), (3,2), (3,3), so there are 5 such cells.

Sample Input 2

7
...@@@.
..@@@@@
@...@..
..@..@.
.....@@
.@@@@@@
@@.@.@.

Sample Output 2

15
29
28
23
19
13
6
5
3
0
0
0
0

Problem Statement

For a sequence B = (B_1, B_2, \dots, B_N) of length N, define prefix max update positions and suffix max update positions as follows:

• An index i is called a prefix max update position if for all 1 \leq j < i, we have B_j < B_i.
• An index i is called a suffix max update position if for all i < j \leq N, we have B_j < B_i.

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N, and integers L and R.

Consider all sequences obtained by rearranging the elements of A. Among them, count how many sequences have exactly L prefix max update positions and exactly R suffix max update positions. Output the answer modulo 998244353.

Two sequences are considered the same if they are identical as sequences.

Constraints

• 1 \leq N \leq 400
• 1 \leq L \leq N
• 1 \leq R \leq N
• 1 \leq A_i \leq N
• All input values are integers

Sample Input 1

4 2 1
1 2 3 4

Sample Output 1

2

There are 2 such sequences:

• (3,2,1,4)
• (3,1,2,4)

Sample Input 2

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

Sample Output 2

50424

Problem Statement

You are given a sequence of positive integers A = (A_1, A_2, \dots, A_N) of length N, and positive integers S and T.

Find the number of sequences of non-negative integers (c_1, c_2, \dots, c_N) that satisfy all of the following conditions, modulo 998244353:

• c_1 + c_2 + \dots + c_N = S
• A_1 c_1 + A_2 c_2 + \dots + A_N c_N = T

Constraints

• 1 \leq N \leq 20
• 1 \leq S \leq 10^{18}
• 1 \leq T \leq 10^{18}
• 1 \leq A_i \leq 200
• \displaystyle \sum_{i=1}^N A_i \leq 200
• All input values are integers

Sample Input 1

4 4 10
1 2 3 4

Sample Output 1

5

The following 5 sequences satisfy the conditions:

• (0,2,2,0)
• (0,3,0,1)
• (1,0,3,0)
• (1,1,1,1)
• (2,0,0,2)

Sample Input 2

10 34016955048482281 206283256471036323
38 35 28 54 3 15 4 16 6 1

Sample Output 2

230312634

Problem Statement

You are given an integer sequence A = (A_1, A_2, \dots, A_N) of length N.
You also have an integer x, which is initially 0.

You will perform the following N operations:

• For i = 1, 2, \dots, N, choose exactly one of the following three operations:
  • Replace x with x + A_i.
  • Replace x with \vert x - A_i \vert.
  • Do nothing.

Find the number of possible values of x after all N operations are completed.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq 2 \times 10^6
• \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 2 \times 10^6
• All input values are integers

Partial Score

This problem has partial scoring.

• If you solve the dataset with \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 5 \times 10^5, you will get 4 points.

Sample Input 1

3
2 7 5

Sample Output 1

10

For example, you can obtain x = 9 by performing the following operations:

• Initially, x = 0.
• At i = 1, replace x with \vert x - A_i \vert = \vert 0 - 2 \vert = 2.
• At i = 2, replace x with x + A_i = 2 + 7 = 9.
• At i = 3, do nothing.

Sample Input 2

10
49 85 36 30 71 65 38 45 73 27

Sample Output 2

454

Problem Statement

You are given a positive integer N and a permutation A = (A_1, A_2, \dots, A_N) of (1, 2, \dots, N).

Consider a directed graph G with N vertices numbered from 1 to N. For every pair of integers (i, j) such that 1 \leq i < j \leq N, there are \mathrm{LCM}(A_i, A_j) directed edges from vertex i to vertex j. (Here, \mathrm{LCM} denotes the least common multiple.) There are no other edges in G.

For each v = 2, 3, \dots, N, find the number of paths from vertex 1 to vertex v, modulo 998244353. Here, two paths are considered different if the sets of edges they pass through are different.

Constraints

• 2 \leq N \leq 2 \times 10^5
• (A_1, A_2, \dots, A_N) is a permutation of (1, 2, \dots, N)
• All input values are integers

Sample Input 1

4
3 2 1 4

Sample Output 1

6
15
96

The directed edges in G are as follows:

• From vertex 1 to vertex 2: 6 edges
• From vertex 1 to vertex 3: 3 edges
• From vertex 1 to vertex 4: 12 edges
• From vertex 2 to vertex 3: 2 edges
• From vertex 2 to vertex 4: 4 edges
• From vertex 3 to vertex 4: 4 edges

Sample Input 2

13
12 3 2 4 10 9 5 8 1 6 11 7 13

Sample Output 2

12
84
492
11100
1018368
45948480
913466263
559040529
720204824
935993195
339767199
889449065

Problem Statement

You are given a string S of length 2^N consisting of characters 1, 2, \dots, 9.

For each non-negative integer n such that 0 \leq n \leq 2^N - 1, define f(n) as follows:

• List all non-negative integers i such that n \ \mathrm{OR} \ i = n, and sort them in increasing order. Let them be i_1, i_2, \dots, i_k. Here, \mathrm{OR} denotes the bitwise OR operation.
• Let T be the string formed by taking the (i_1+1)-th, (i_2+1)-th, \dots, (i_k+1)-th characters of S in this order.
• Interpret T as a decimal integer, and let its value be X. Then define f(n) = X \bmod 998244353.

Compute all values f(0), f(1), \dots, f(2^N - 1), and output the value of the following expression. Here, \mathrm{XOR} denotes the bitwise exclusive OR operation.

Constraints

• 1 \leq N \leq 22
• S is a string of length 2^N consisting of 1, 2, \dots, 9

Sample Input 1

2
1234

Sample Output 1

1262

For all n such that 0 \leq n \leq 2^N-1, the values of f(n) are:

• When n=0, f(n) = 1
• When n=1, f(n) = 12
• When n=2, f(n) = 13
• When n=3, f(n) = 1234

Therefore, output (1 \ \mathrm{XOR} \ 0) + (12 \ \mathrm{XOR} \ 1) + (13 \ \mathrm{XOR} \ 2) + (1234 \ \mathrm{XOR} \ 3) = 1 + 13 + 15 + 1233 = 1262.

Sample Input 2

4
6415986517946482

Sample Output 2

790534415

Note

This problem requires more specialized knowledge compared to the others.
If you do not have an idea for a full solution, it is recommended to aim for partial points and then move on to the next problem.

Problem Statement

There are infinitely many items of each of N types. The i-th type of item has weight i and value v_i.

You are given Q queries. In each query, you are given a positive integer W.
Find the maximum possible total value when you choose some items such that the total weight is exactly W.

Constraints

• 1 \leq N \leq 4000
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq v_i \leq 10^9
• 1 \leq W \leq 10^9
• All input values are integers

Partial Score

This problem has partial scoring.

• If you solve the dataset with N \leq 300, you will get 4 points.

Sample Input 1

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

Sample Output 1

2
4
7
9
11
14
16
18
21

For example, in the 6th query, W=6.
If you take two items of type 3, the total value becomes 7 + 7 = 14, which is the maximum.

Sample Input 2

10 10
104 231 361 478 661 765 963 1132 1402 1552
1
10
15
27
48
100
853822501
687675302
281611653
844033520

Sample Output 2

104
1552
2213
4206
7460
15572
133006571782
107124530332
43868837466
131481666104

Problem Statement

You are going to play a game. The game consists of actions over N days. Each day, you choose an integer x \in {0,1,2}, pay x yen, and perform action x. If you perform action x on day i, you gain A_{i,x} experience points. You cannot perform more than one action per day.

You are given Q queries. In each query, you are given a pair of integers (d, b) such that 1 \leq d \leq N and 0 \leq b \leq 2d. Solve the following problem:

• Suppose you spend exactly b yen in total from day 1 to day d. What is the maximum possible total experience you can gain during these d days?

You are given T test cases. Solve each of them.

Constraints

• 1 \leq T \leq 10^4
• 1 \leq N \leq 2.5 \times 10^5
• 1 \leq Q \leq 10^4
• 0 \leq A_{i,x} \leq 10^9
• 1 \leq d \leq N
• 0 \leq b \leq 2d
• The sum of N over all test cases is at most 2.5 \times 10^5
• The sum of Q over all test cases is at most 10^4
• All input values are integers

Partial Score

This problem has partial scoring.

• If all queries satisfy d = N, you will get 5 points.

Sample Input 1

2
3 3
1 3 2
4 8 1
1 6 9
1 1
2 3
3 3
5 5
45 58 82
47 39 94
36 54 74
80 61 95
61 57 69
2 4
5 7
4 1
5 5
3 0

Sample Output 1

3
10
18
176
387
226
371
128

For example, consider the 3-rd query of the first test case: d=3, b=3.
You can achieve a total experience of 18 in the following way, which is optimal:

• Day 1: choose x=0. Pay 0 yen and gain A_{1,0}=1 experience.
• Day 2: choose x=1. Pay 1 yen and gain A_{2,1}=8 experience.
• Day 3: choose x=2. Pay 2 yen and gain A_{3,2}=9 experience.

Sample Input 2

1
10 10
76 30 16
30 94 48
60 67 90
43 63 47
49 33 66
14 49 79
39 62 37
34 79 96
29 86 85
59 42 69
10 16
10 13
10 8
10 20
10 2
10 5
10 4
10 0
10 15
10 19

Sample Output 2

764
770
724
633
554
664
634
433
780
679

Problem Statement

For a positive integer n, define f(n) as follows:

• Let n have d digits in decimal representation. Define a sequence A = (A_1, \dots, A_d) of length d as follows:
  • A_i is the i-th digit from the left in the decimal representation of n.
• Let f(n) be the length of the longest strictly increasing subsequence of A.

For example, f(347) = 3, f(1192) = 2, f(10123456789) = 10, and f(11111) = 1.

You are given a positive integer N.
Count the number of positive integers x such that by repeatedly applying the operation x \to x + f(x) zero or more times, you can obtain N.

You are given T test cases. Solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^4
• 1 \leq N \leq 10^{18}
• All input values are integers

Sample Input 1

6
7
110
1000000000000000000
567784738694904180
555056967895592095
942135357890920474

Sample Output 1

7
5
1000000000000000000
23644
22551
60795

For example, in the second test case, starting from x = 102 and repeatedly applying the operation x \to x + f(x):

• 102 \to 104 \to 106 \to 108 \to 110

we can obtain N = 110. The only values of x satisfying the condition are x = 102, 104, 106, 108, 110, so there are 5 in total.

Note

This problem has a very strict memory limit.

Problem Statement

You are given an integer M and N pairs of integers (L_1, R_1), \dots, (L_N, R_N). For each i (1 \leq i \leq N), it holds that 1 \leq L_i \leq R_i \leq M.

For each K = 1, 2, \dots, M, solve the following problem:

There are 2^N possible subsets S \subseteq \lbrace 1,2,\dots,N\rbrace. Among them, how many satisfy the following condition? Output the answer modulo 998244353.

• The number of integers m (1 \leq m \leq M) satisfying the following condition is exactly K:
  • There exists an integer i \in S such that L_i \leq m \leq R_i.

Constraints

• 1 \leq N \leq 2000
• 1 \leq M \leq 4000
• 1 \leq L_i \leq R_i \leq M
• All input values are integers

Sample Input 1

3 4
1 2
3 4
2 4

Sample Output 1

0
2
2
3

When K=1, there are 0 subsets S that satisfy the condition.
When K=2, there are 2 such subsets: \lbrace 1\rbrace , \lbrace 2\rbrace.
When K=3, there are 2 such subsets: \lbrace 3\rbrace , \lbrace 2,3\rbrace.
When K=4, there are 3 such subsets: \lbrace 1,2\rbrace , \lbrace 1,3\rbrace , \lbrace 1,2,3\rbrace.

Sample Input 2

8 10
6 10
1 4
5 9
6 8
1 5
7 9
4 6
4 8

Sample Output 2

0
0
3
2
15
25
26
20
72
92

Problem Statement

For non-negative integers u, v, we write u \subseteq v to mean u\ \mathrm{OR}\ v = v. Here, \mathrm{OR} denotes the bitwise OR operation.

A sequence of triples of non-negative integers ((u_1,v_1,w_1),(u_2,v_2,w_2),\dots,(u_k,v_k,w_k)) is called a good sequence if it satisfies all of the following conditions:

• k \geq 2.
• For all integers i such that 1 \leq i \leq k-1, it holds that u_i \subseteq w_{i+1} \subseteq v_i.

You are given a sequence of triples A = ((x_1,y_1,z_1), (x_2,y_2,z_2), \dots, (x_N,y_N,z_N)).
For all i such that 1 \leq i \leq N, it holds that x_i \subseteq y_i.

There are 2^N - N - 1 subsequences of A with length at least 2 (counting different choices of indices separately).
Among them, find the number of good sequences, modulo 998244353.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 0 \leq x_i < 2^{24}
• 0 \leq y_i < 2^{24}
• 0 \leq z_i < 2^{24}
• x_i \ \mathrm{OR}\ y_i = y_i
• All input values are integers

Partial Score

This problem has partial scoring.

• If you solve the dataset where \max(x_i, y_i, z_i) < 2^{18} holds for every integer i such that 1 \leq i \leq N, you will get 4 points.

Sample Input 1

3
2 6 3
0 7 4
1 5 2

Sample Output 1

2

There are 2 sequences that satisfy the condition:

• ((2,6,3),(1,5,2))
• ((0,7,4),(1,5,2))

Sample Input 2

8
0 9 5
0 16 3
0 8 4
0 5 23
0 20 29
0 12 26
0 6 0
0 19 8

Sample Output 2

9

Sample Input 3

13
0 16777215 14827221
8390656 12582911 5535137
4325888 16711679 2641072
8849409 16776703 15212885
8389632 16514814 9612654
0 12517373 13419138
0 16777215 5271292
14464 16236535 6997452
131072 15727483 10218943
16 16646111 15524257
1181961 14647295 5595336
8388768 16775147 5472548
0 16777215 297940

Sample Output 3

34

Problem Statement

You are given an N \times N grid. Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

The state between adjacent cells (sharing an edge) is represented by a character c:

• If c = ., there is nothing between the cells, and you can pass freely.
• If c = D, there is a door, and you can pass freely.
• If c = A, there is a special door called A, and you can pass freely.
• If c = B, there is a special door called B, and you can pass freely.
• If c = #, there is a wall, and you cannot pass.

Here, there is exactly one door A and one door B in the grid.

The states between adjacent cells are given by strings S_1, S_2, \dots, S_{N-1} and T_1, T_2, \dots, T_N:

• For 1 \leq i \leq N-1, 1 \leq j \leq N, the state between (i,j) and (i+1,j) is S_{i,j}.
• For 1 \leq i \leq N, 1 \leq j \leq N-1, the state between (i,j) and (i,j+1) is T_{i,j}.

A grid is called a good state if you can start from (1,1) and reach (N,N) by moving up, down, left, or right without passing through walls.

You will block some of the doors (except A and B), making them impassable, so that the following conditions are satisfied:

• The grid is in a good state.
• Even if you additionally block exactly one of A or B, the grid is still in a good state.
• If you additionally block both A and B, the grid is no longer in a good state.

Is it possible to satisfy these conditions? If it is possible, find the minimum number of doors you need to block.

You are given T test cases. Solve each of them.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 40
• Each S_i is a string of length N consisting of ., D, A, B, #
• Each T_i is a string of length N-1 consisting of ., D, A, B, #
• A and B each appear exactly once among all S_{i,j} and T_{i,j}
• The sum of N^2 over all test cases is at most 2 \times 10^5
• The sum of N^4 over all test cases is at most 40^4

Sample Input 1

6
2
.A
.
B
2
.A
#
B
3
#D.
#BD
.A
.#
..
4
DDBD
..#D
#D.D
#DD
#DD
.A.
#.#
4
D.#D
DD#.
D.B.
#D.
.#D
...
.DA
9
DDD.D#DDD
DDDADDDDD
DD.DDDDDD
DDDD#.DDD
DD#DDDD.#
DDDDD#.#D
DD.#..DDD
DDDDD#D.D
DDD...DD
D#.D#D#D
D#DD#D.#
DDD#DD##
BDDD.D#D
DD#DDDDD
DDDDD#DD
DDD#DDDD
##DDD.#D

Sample Output 1

0
-1
0
3
-1
7

For example, in the first test case, the conditions are already satisfied.

Problem Statement

You are given a tree with N vertices, numbered from 1 to N. The i-th edge connects vertices u_i and v_i.

A set of vertices S is called an independent set if it satisfies the following condition:

• For any two distinct vertices u, v \in S, u and v are not adjacent in the tree.

For a vertex v, let F_v be the set of all independent sets S such that v \in S.

You are given Q queries. In each query, you are given an integer v (1 \leq v \leq N) and an integer q. Compute:

Here, |S| denotes the size of the set S.

Constraints

• 2 \leq N \leq 1.3 \times 10^5
• 1 \leq Q \leq 1.3 \times 10^5
• 1 \leq u_i < v_i \leq N
• The given graph is a tree
• 1 \leq v \leq N
• 1 \leq q < 998244353
• All input values are integers

Partial Score

This problem has partial scoring.

• If all queries satisfy v=1, you will get 5 points.

Sample Input 1

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

Sample Output 1

2
12

Consider the first query. The independent sets that contain vertex 1 are {1} and {1, 4}, so there are 2 such sets. Therefore, output 1^1 + 1^2 = 2.

Sample Input 2

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

Sample Output 2

16
162
768
2500
6480
14406
28672
52488
90000
146410

Sample Input 3

10 10
1 2
1 3
2 4
4 5
4 6
2 7
5 8
8 9
6 10
5 844033520
8 780395612
2 285523486
6 13801767
3 487663185
3 667406485
7 672229269
7 207478896
5 769551740
7 806405364

Sample Output 3

665599367
675643489
193550820
987507475
230555342
555586355
204648376
83113599
299301383
545057926