Problem Statement

We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.

We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?

Here, we distinguish all balls, even with the same numbers written on them.

Constraints

• N \geq 2
• L_i \geq 2
• The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
• 1 \leq a_{i,j} \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

2 40
3 1 8 4
2 10 5

Sample Output 1

2

When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.

Sample Input 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

Sample Output 2

45

Note that we distinguish all balls, even with the same numbers written on them.

Sample Input 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

Sample Output 3

0

There may be no way to make the product X.

Problem Statement

Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

• Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
1 2 4 6 7 271

Sample Output 1

4

Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

5

Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:

• Sell two books of Volume 1 and buy a book of Volume 2 instead.
• Sell two books of Volume 1 and buy a book of Volume 3 instead.
• Sell two books of Volume 1 and buy a book of Volume 4 instead.
• Sell two books of Volume 1 and buy a book of Volume 5 instead.

Sample Input 3

1
5

Sample Output 3

0

Takahashi cannot read Volume 1.

Problem Statement

You are given two grids, A and B, each with H rows and W columns.

For each pair of integers (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W, let (i, j) denote the cell in the i-th row and j-th column. In grid A, cell (i, j) contains the integer A_{i, j}. In grid B, cell (i, j) contains the integer B_{i, j}.

You will repeat the following operation any number of times, possibly zero. In each operation, you perform one of the following:

• Choose an integer i satisfying 1 \leq i \leq H-1 and swap the i-th and (i+1)-th rows in grid A.
• Choose an integer i satisfying 1 \leq i \leq W-1 and swap the i-th and (i+1)-th columns in grid A.

Determine whether it is possible to make grid A identical to grid B by repeating the above operation. If it is possible, print the minimum number of operations required to do so.

Here, grid A is identical to grid B if and only if, for all pairs of integers (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W, the integer written in cell (i, j) of grid A is equal to the integer written in cell (i, j) of grid B.

Constraints

• All input values are integers.
• 2 \leq H, W \leq 5
• 1 \leq A_{i, j}, B_{i, j} \leq 10^9

Sample Input 1

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

Sample Output 1

3

Swapping the fourth and fifth columns of the initial grid A yields the following grid:

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

Then, swapping the second and third rows yields the following grid:

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

Finally, swapping the second and third columns yields the following grid, which is identical to grid B:

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

You can make grid A identical to grid B with the three operations above and cannot do so with fewer operations, so print 3.

Sample Input 2

2 2
1 1
1 1
1 1
1 1000000000

Sample Output 2

-1

There is no way to perform the operation to make grid A match grid B, so print -1.

Sample Input 3

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

Sample Output 3

0

Grid A is already identical to grid B at the beginning.

Sample Input 4

5 5
710511029 136397527 763027379 644706927 447672230
979861204 57882493 442931589 951053644 152300688
43971370 126515475 962139996 541282303 834022578
312523039 506696497 664922712 414720753 304621362
325269832 191410838 286751784 732741849 806602693
806602693 732741849 286751784 191410838 325269832
304621362 414720753 664922712 506696497 312523039
834022578 541282303 962139996 126515475 43971370
152300688 951053644 442931589 57882493 979861204
447672230 644706927 763027379 136397527 710511029

Sample Output 4

20

Problem Statement

We have a grid with H rows and W columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left. Each square in the grid is one of the following: the start square, the goal square, an empty square, a wall square, and a candy square. (i,j) is represented by a character A_{i,j}, and is the start square if A_{i,j}= S, the goal square if A_{i,j}= G, an empty square if A_{i,j}= ., a wall square if A_{i,j}= #, and a candy square if A_{i,j}= o. Here, it is guaranteed that there are exactly one start, exactly one goal, and at most 18 candy squares.

Takahashi is now at the start square. He can repeat moving to a vertically or horizontally adjacent non-wall square. He wants to reach the goal square in at most T moves. Determine whether it is possible. If it is possible, find the maximum number of candy squares he can visit on the way to the goal square, where he must finish. Each candy square counts only once, even if it is visited multiple times.

Constraints

• 1\leq H,W \leq 300
• 1 \leq T \leq 2\times 10^6
• H, W, and T are integers.
• A_{i,j} is one of S, G, ., #, and o.
• Exactly one pair (i,j) satisfies A_{i,j}= S.
• Exactly one pair (i,j) satisfies A_{i,j}= G.
• At most 18 pairs (i,j) satisfy A_{i,j}= o.

Sample Input 1

3 3 5
S.G
o#o
.#.

Sample Output 1

1

If he makes four moves as (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3), he can visit one candy square and finish at the goal square. He cannot make five or fewer moves to visit two candy squares and finish at the goal square, so the answer is 1.

Note that making five moves as (1,1) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) to visit two candy squares is invalid since he would not finish at the goal square.

Sample Input 2

3 3 1
S.G
.#o
o#.

Sample Output 2

-1

He cannot reach the goal square in one or fewer moves.

Sample Input 3

5 10 2000000
S.o..ooo..
..o..o.o..
..o..ooo..
..o..o.o..
..o..ooo.G

Sample Output 3

18

Problem Statement

You are given sequences of length N, A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).
You are also given Q queries to process in order.

There are three types of queries:

• 1 l r x : Add x to each of A_l, A_{l+1}, \ldots, A_r.
• 2 l r x : Add x to each of B_l, B_{l+1}, \ldots, B_r.
• 3 l r : Print the remainder of \displaystyle\sum_{i=l}^r (A_i\times B_i) when divided by 998244353.

Constraints

• 1\leq N,Q\leq 2\times 10^5
• 0\leq A_i,B_i\leq 10^9
• 1\leq l\leq r\leq N
• 1\leq x\leq 10^9
• All input values are integers.
• There is at least one query of the third type.

Sample Input 1

5 6
1 3 5 6 8
3 1 2 1 2
3 1 3
1 2 5 3
3 1 3
1 1 3 1
2 5 5 2
3 1 5

Sample Output 1

16
25
84

Initially, A=(1,3,5,6,8) and B=(3,1,2,1,2). The queries are processed in the following order:

• For the first query, print (1\times 3)+(3\times 1)+(5\times 2)=16 modulo 998244353, which is 16.
• For the second query, add 3 to A_2,A_3,A_4,A_5. Now A=(1,6,8,9,11).
• For the third query, print (1\times 3)+(6\times 1)+(8\times 2)=25 modulo 998244353, which is 25.
• For the fourth query, add 1 to A_1,A_2,A_3. Now A=(2,7,9,9,11).
• For the fifth query, add 2 to B_5. Now B=(3,1,2,1,4).
• For the sixth query, print (2\times 3)+(7\times 1)+(9\times 2)+(9\times 1)+(11\times 4)=84 modulo 998244353, which is 84.

Thus, the first, second, and third lines should contain 16, 25, and 84, respectively.

Sample Input 2

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

Sample Output 2

716070898
151723988

Make sure to print the sum modulo 998244353 for the third type of query.