Problem Statement

You are given a string S consisting of A, B, and C. S is guaranteed to contain all of A, B, and C.

If the characters of S are checked one by one from the left, how many characters will have been checked when the following condition is satisfied for the first time?

• All of A, B, and C have appeared at least once.

Constraints

• 3 \leq N \leq 100
• S is a string of length N consisting of A, B, and C.
• S contains all of A, B, and C.

Sample Input 1

5
ACABB

Sample Output 1

4

In the first four characters from the left, A, B, and C appear twice, once, and once, respectively, satisfying the condition.
The condition is not satisfied by checking three or fewer characters, so the answer is 4.

Sample Input 2

4
CABC

Sample Output 2

3

In the first three characters from the left, each of A, B, and C appears once, satisfying the condition.

Sample Input 3

30
AABABBBABABBABABCABACAABCBACCA

Sample Output 3

17

Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

• First, he painted the part from X=L_1 to X=R_1 red.
• Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

• 0\leq L_1<R_1\leq 100
• 0\leq L_2<R_2\leq 100
• All values in input are integers.

Sample Input 1

0 3 1 5

Sample Output 1

2

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

0

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

0

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

Problem Statement

AtCoder Shop has N products. The price of the i-th product (1\leq i\leq N) is P _ i. The i-th product (1\leq i\leq N) has C_i functions. The j-th function (1\leq j\leq C _ i) of the i-th product (1\leq i\leq N) is represented as an integer F _ {i,j} between 1 and M, inclusive.

Takahashi wonders whether there is a product that is strictly superior to another. If there are i and j (1\leq i,j\leq N) such that the i-th and j-th products satisfy all of the following conditions, print Yes; otherwise, print No.

• P _ i\geq P _ j.
• The j-th product has all functions of the i-th product.
• P _ i\gt P _ j, or the j-th product has one or more functions that the i-th product lacks.

Constraints

• 2\leq N\leq100
• 1\leq M\leq100
• 1\leq P _ i\leq10^5\ (1\leq i\leq N)
• 1\leq C _ i\leq M\ (1\leq i\leq N)
• 1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

5 6
10000 2 1 3
15000 3 1 2 4
30000 3 1 3 5
35000 2 1 5
100000 6 1 2 3 4 5 6

Sample Output 1

Yes

(i,j)=(4,3) satisfies all of the conditions.

No other pair satisfies them. For instance, for (i,j)=(4,5), the j-th product has all functions of the i-th one, but P _ i\lt P _ j, so it is not strictly superior.

Sample Input 2

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

Sample Output 2

No

Multiple products may have the same price and functions.

Sample Input 3

20 10
72036 3 3 4 9
7716 4 1 2 3 6
54093 5 1 6 7 8 10
25517 7 3 4 5 6 7 9 10
96930 8 2 3 4 6 7 8 9 10
47774 6 2 4 5 6 7 9
36959 5 1 3 4 5 8
46622 7 1 2 3 5 6 8 10
34315 9 1 3 4 5 6 7 8 9 10
54129 7 1 3 4 6 7 8 9
4274 5 2 4 7 9 10
16578 5 2 3 6 7 9
61809 4 1 2 4 5
1659 5 3 5 6 9 10
59183 5 1 2 3 4 9
22186 4 3 5 6 8
98282 4 1 4 7 10
72865 8 1 2 3 4 6 8 9 10
33796 6 1 3 5 7 9 10
74670 4 1 2 6 8

Sample Output 3

Yes

Problem Statement

A supermarket sells egg packs.

A pack of 6 eggs costs S yen, a pack of 8 eggs costs M yen, and a pack of 12 eggs costs L yen.

When you can buy any number of each pack, find the minimum amount of money required to purchase at least N eggs.

Constraints

• 1 \leq N \leq 100
• 1 \leq S,M,L \leq 10^4
• All input values are integers.

Sample Input 1

16 120 150 200

Sample Output 1

300

It is optimal to buy two 8-egg packs.

Sample Input 2

10 100 50 10

Sample Output 2

10

It is optimal to buy one 12-egg pack.

Sample Input 3

99 600 800 1200

Sample Output 3

10000

It is optimal to buy five 8-egg packs and five 12-egg packs.

Problem Statement

There are N dominoes standing in a row on a number line. The i-th domino is standing at coordinate i and has height A_i.

When the i-th domino falls to the right, all dominoes in the range between coordinates i and i+A_i-1, inclusive, fall to the right.

How many dominoes will fall in total when the first domino falls to the right?

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq A_i \leq N
• All input values are integers.

Sample Input 1

4
3 1 4 1

Sample Output 1

4

When the first domino falls to the right, the second and third dominoes also fall to the right. When the third domino falls to the right, the fourth domino also falls.

Sample Input 2

9
1 4 1 4 2 1 3 5 6

Sample Output 2

1

When the first domino falls to the right, no other dominoes will fall.

Sample Input 3

10
5 4 3 2 1 1 2 3 4 5

Sample Output 3

5

Problem Statement

You are given three sequences A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), and C=(C_1,\ldots,C_L).

Additionally, a sequence X=(X_1,\ldots,X_Q) is given. For each i=1,\ldots,Q, solve the following problem:

Problem: Is it possible to select one element from each of A, B, and C so that their sum is X_i?

Constraints

• 1 \leq N,M,L \leq 100
• 0 \leq A_i, B_i ,C_i \leq 10^8
• 1 \leq Q \leq 2\times 10^5
• 0 \leq X_i \leq 3\times 10^8
• All input values are integers.

Sample Input 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

Sample Output 1

No
Yes
Yes
No

• It is impossible to select one element from each of A, B, and C so that their sum is 1.
• Selecting 1, 2, and 2 from A, B, and C, respectively, makes the sum 5.
• Selecting 2, 4, and 4 from A, B, and C, respectively, makes the sum 10.
• It is impossible to select one element from each of A, B, and C so that their sum is 50.

Problem Statement

You are given a directed graph with N vertices and M edges. The j-th directed edge goes from vertex u_j to vertex v_j and has a weight of w_j.

Find one way to write an integer between -10^{18} and 10^{18}, inclusive, to each vertex such that the following condition is satisfied.

• Let x_i be the value written on vertex i. For all edges j=1,2,\dots,M, it holds that x_{v_j} - x_{u_j} = w_j.

It is guaranteed that at least one such assignment exists for the given input.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq \min\{2 \times 10^5,N(N-1)/2\}
• 1 \leq u_j, v_j \leq N
• u_j \neq v_j
• If i \neq j, then (u_i, v_i) \neq (u_j, v_j) and (u_i, v_i) \neq (v_j, u_j)
• |w_j| \leq 10^9
• All input values are integers.
• There exists at least one assignment satisfying the conditions.

Sample Input 1

3 3
1 2 2
3 2 3
1 3 -1

Sample Output 1

3 5 2

By setting x = (3, 5, 2), we have x_2 - x_1 = w_1 = 2, x_2 - x_3 = w_2 = 3, x_3 - x_1 = w_3 = -1, satisfying the conditions.

For example, x = (-1, 1, -2) is also a valid answer.

Sample Input 2

4 2
2 1 5
3 4 -3

Sample Output 2

5 0 6 3

For example, x = (0, -5, 4, 1) and x = (5, 0, 4, 1) are also valid answers.

Sample Input 3

5 7
2 1 18169343
3 1 307110901
4 1 130955934
2 3 -288941558
2 5 96267410
5 3 -385208968
4 3 -176154967

Sample Output 3

200401298 182231955 -106709603 69445364 278499365

Problem Statement

You are given a permutation P=(P_0,P_1,\ldots,P_{2^{N}-1}) of (1,2,3,\ldots,2^{N}).

You can perform the following operation any number of times (possibly zero):

• Choose non-negative integers a,b satisfying 0 \leq a \times 2^{b} < (a+1) \times 2^{b} \leq 2^{N}, and reverse P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1}. Here, reversing P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} means simultaneously replacing P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} with P_{(a+1) \times 2^{b}-1}, P_{(a+1) \times 2^{b}-2},\ldots,P_{a \times 2^{b}}.

Find the lexicographically smallest permutation P that can be obtained by repeating the operation.

You are given T test cases, so find the answer for each.

Constraints

• 1 \leq T \leq 10^{5}
• 1 \leq N \leq 18
• P is a permutation of (1,2,3,\ldots,2^{N}).
• For each input file, the sum of 2^N over all test cases is at most 3 \times 10^{5}.
• All input values are integers.

Sample Input 1

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

Sample Output 1

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

In the first test case, when no operation is performed on P, P=(1,2). This is the lexicographically smallest permutation. Thus, the answer is (1,2).

In the second test case, when we perform the operation with a=1,b=1, P becomes (1,3,2,4). No matter how many operations we perform on P, we cannot obtain a permutation lexicographically smaller than (1,3,2,4). Thus, the answer is (1,3,2,4).

In the third test case, by performing operations in the following order, we can obtain P=(1,4,2,3):

• Perform the operation with a=0,b=1. P becomes (3,2,4,1).
• Perform the operation with a=0,b=2. P becomes (1,4,2,3).

No matter how many operations we perform on P, we cannot obtain a permutation lexicographically smaller than (1,4,2,3). Thus, the answer is (1,4,2,3).

Problem Statement

You are given N, Q, and A=(A_1,\ldots,A_N).
Process Q queries, each of which is of one of the following two kinds:

• 1 x v: update A_x to v.
• 2 x: let B_i=\sum_{j=1}^{i}A_j, C_i=\sum_{j=1}^{i}B_j, and D_i=\sum_{j=1}^{i}C_j. Print D_x modulo 998244353.

Constraints

• 1 \leq N \leq 2\times10^5
• 1 \leq Q \leq 2\times10^5
• 0 \leq A_i \leq 10^9
• 1 \leq x \leq N
• 0 \leq v \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

15
9

When the 1-st query is given, A=(1,2,3), so B=(1,3,6), C=(1,4,10), and D=(1,5,15); thus, D_3=15.

When the 3-rd query is given, A=(1,0,3), so B=(1,1,4), C=(1,2,6), and D=(1,3,9); thus, D_3=9.

Sample Input 2

2 1
998244353 998244353
2 1

Sample Output 2

0