Problem Statement

In AtCoder Land, there are N popcorn stands numbered 1 to N. They have M different flavors of popcorn, labeled 1, 2, \dots, M, but not every stand sells all flavors of popcorn.

Takahashi has obtained information about which flavors of popcorn are sold at each stand. This information is represented by N strings S_1, S_2, \dots, S_N of length M. If the j-th character of S_i is o, it means that stand i sells flavor j of popcorn. If it is x, it means that stand i does not sell flavor j. Each stand sells at least one flavor of popcorn, and each flavor of popcorn is sold at least at one stand.

Takahashi wants to try all the flavors of popcorn but does not want to move around too much. Determine the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Constraints

• N and M are integers.
• 1 \leq N, M \leq 10
• Each S_i is a string of length M consisting of o and x.
• For every i (1 \leq i \leq N), there is at least one o in S_i.
• For every j (1 \leq j \leq M), there is at least one i such that the j-th character of S_i is o.

Sample Input 1

3 5
oooxx
xooox
xxooo

Sample Output 1

2

By visiting the 1st and 3rd stands, you can buy all the flavors of popcorn. It is impossible to buy all the flavors from a single stand, so the answer is 2.

Sample Input 2

3 2
oo
ox
xo

Sample Output 2

1

Sample Input 3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

Sample Output 3

3

Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
• 1 \leq X \leq 10000
• All values in input are integers.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

4 12
1 8
5 7
3 4
2 6

Sample Output 3

Yes

Problem Statement

You are given a positive integer N, and an integer A_{x,y,z} for each triple of integers (x, y, z) such that 1 \leq x, y, z \leq N.

You will be given Q queries in the following format, which must be processed in order.

For the i-th query (1 \leq i \leq Q), you are given a tuple of integers (Lx_i, Rx_i, Ly_i, Ry_i, Lz_i, Rz_i) such that 1 \leq Lx_i \leq Rx_i \leq N, 1 \leq Ly_i \leq Ry_i \leq N, and 1 \leq Lz_i \leq Rz_i \leq N. Find:

\displaystyle{\sum_{x=Lx_i}^{Rx_i} \sum_{y=Ly_i}^{Ry_i} \sum_{z=Lz_i}^{Rz_i} A_{x,y,z}}.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \leq 2 \times 10^{5}
• 0 \leq A_{x,y,z} \leq 999 (1 \leq x, y, z \leq N)
• 1 \leq Lx_i \leq Rx_i \leq N (1 \leq i \leq Q)
• 1 \leq Ly_i \leq Ry_i \leq N (1 \leq i \leq Q)
• 1 \leq Lz_i \leq Rz_i \leq N (1 \leq i \leq Q)
• All input values are integers.

Sample Input 1

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

Sample Output 1

10
26

For the 1st query, the sought value is A_{1,2,1} + A_{2,2,1} = 3 + 7 = 10. Thus, print 10.

For the 2nd query, the sought value is A_{2,1,1} + A_{2,1,2} + A_{2,2,1} + A_{2,2,2} = 5 + 6 + 7 + 8 = 26. Thus, print 26.

Sample Input 2

3
733 857 714
956 208 257
123 719 648
840 881 245
245 112 746
306 942 694
58 870 849
13 208 789
687 906 783
8
3 3 3 3 1 1
1 3 2 3 3 3
2 2 2 3 1 1
1 3 1 1 1 1
2 3 2 3 2 3
1 2 1 1 1 2
3 3 2 2 1 3
1 2 2 3 2 3

Sample Output 2

687
3917
551
1631
5180
3311
1010
4326

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N. For each k = 1, 2, \dots, N, find the number, modulo 998244353, of (not necessarily contiguous) subsequences of A of length k that are arithmetic sequences. Two subsequences are distinguished if they are taken from different positions, even if they are equal as sequences.

Constraints

• 1 \leq N \leq 80
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5
1 2 3 2 3

Sample Output 1

5 10 3 0 0

• There are 5 subsequences of length 1, all of which are arithmetic sequences.
• There are 10 subsequences of length 2, all of which are arithmetic sequences.
• There are 3 subsequences of length 3 that are arithmetic sequences: (A_1, A_2, A_3), (A_1, A_2, A_5), and (A_1, A_4, A_5).
• There are no arithmetic subsequences of length 4 or more.

Sample Input 2

4
1 2 3 4

Sample Output 2

4 6 2 1

Sample Input 3

1
100

Sample Output 3

1

Problem Statement

There is a grid with N rows and N columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

Takahashi is initially at square (1,1) with zero money.

When Takahashi is at square (i,j), he can perform one of the following in one action:

• Stay at the same square and increase his money by P_{i,j}.
• Pay R_{i,j} from his money and move to square (i,j+1).
• Pay D_{i,j} from his money and move to square (i+1,j).

He cannot make a move that would make his money negative or take him outside the grid.

If Takahashi acts optimally, how many actions does he need to reach square (N,N)?

Constraints

• 2 \leq N \leq 80
• 1 \leq P_{i,j} \leq 10^9
• 1 \leq R_{i,j},D_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

8

It is possible to reach square (3,3) in eight actions as follows:

• Stay at square (1,1) and increase money by 1. His money is now 1.
• Pay 1 money and move to square (2,1). His money is now 0.
• Stay at square (2,1) and increase money by 3. His money is now 3.
• Stay at square (2,1) and increase money by 3. His money is now 6.
• Stay at square (2,1) and increase money by 3. His money is now 9.
• Pay 4 money and move to square (2,2). His money is now 5.
• Pay 3 money and move to square (3,2). His money is now 2.
• Pay 2 money and move to square (3,3). His money is now 0.

Sample Input 2

3
1 1 1
1 1 1
1 1 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

Sample Output 2

4000000004