Problem Statement

Print the L-th through R-th characters of the string atcoder.

Constraints

• L and R are integers.
• 1 \le L \le R \le 7

Sample Input 1

3 6

Sample Output 1

code

The 3-rd through 6-th characters of atcoder are code.

Sample Input 2

4 4

Sample Output 2

o

Sample Input 3

1 7

Sample Output 3

atcoder

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

• 1 \leq R, C \leq 15
• R and C are integers.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

Problem Statement

You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.

• For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
• For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.

You may perform the following operations on the matrix A any number of (possibly 0) times in any order:

• Choose an arbitrary row of A and remove it.
• Choose an arbitrary column of A and remove it.

Determine if it is possible to make the matrix A equal the matrix B.

Constraints

• 1 \leq H_2 \leq H_1 \leq 10
• 1 \leq W_2 \leq W_1 \leq 10
• 1 \leq A_{i, j} \leq 10^9
• 1 \leq B_{i, j} \leq 10^9
• All values in input are integers.

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
2 3
6 8 9
16 18 19

Sample Output 1

Yes

Removing the 2-nd column from the initial A results in:

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

Then, removing the 3-rd row from A results in:

1 3 4 5
6 8 9 10
16 18 19 20

Then, removing the 1-st row from A results in:

6 8 9 10
16 18 19 20

Then, removing the 4-th column from A results in:

6 8 9
16 18 19

Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.

Sample Input 2

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

Sample Output 2

No

Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B, so No should be printed.

Problem Statement

You are given a string S that is a permutation of atcoder.
On this string S, you will perform the following operation 0 or more times:

• Choose two adjacent characters of S and swap them.

Find the minimum number of operations required to make S equal atcoder.

Constraints

• S is a string that is a permutation of atcoder

Sample Input 1

catredo

Sample Output 1

8

You can make S equal atcoder in 8 operations as follows:
catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
This is the minimum number of operations achievable.

Sample Input 2

atcoder

Sample Output 2

0

In this case, the string S is already atcoder.

Sample Input 3

redocta

Sample Output 3

21

Problem Statement

A country has N cities and M power plants, which we collectively call places.
The places are numbered 1,2,\dots,N+M, among which Places 1,2,\dots,N are the cities and Places N+1,N+2,\dots,N+M are the power plants.

This country has E power lines. Power Line i (1 \le i \le E) connects Place U_i and Place V_i bidirectionally.
A city is said to be electrified if one can reach at least one of the power plants from the city using some power lines.

Now, Q events will happen. In the i-th (1 \le i \le Q) event, Power Line X_i breaks, making it unusable. Once a power line breaks, it remains broken in the succeeding events.

Find the number of electrified cities right after each events.

Constraints

• All values in input are integers.
• 1 \le N,M
• N+M \le 2 \times 10^5
• 1 \le Q \le E \le 5 \times 10^5
• 1 \le U_i < V_i \le N+M
• If i \neq j, then U_i \neq U_j or V_i \neq V_j.
• 1 \le X_i \le E
• X_i are distinct.

Sample Input 1

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

Sample Output 1

4
4
2
2
2
1

Initially, all cities are electrified.

• The 1-st event breaks Power Line 3 that connects Point 5 and Point 10.
  • Now City 5 is no longer electrified, while 4 cities remain electrified.
• The 2-nd event breaks Power Line 5 that connects Point 2 and Point 9.
• The 3-rd event breaks Power Line 8 that connects Point 3 and Point 6.
  • Now Cities 2 and 3 are no longer electrified, while 2 cities remain electrified.
• The 4-th event breaks Power Line 10 that connects Point 1 and Point 8.
• The 5-th event breaks Power Line 2 that connects Point 4 and Point 10.
• The 6-th event breaks Power Line 7 that connects Point 1 and Point 7.
  • Now City 1 is no longer electrified, while 1 city remains electrified.

Problem Statement

We have a grid with H rows and W columns. Each square is painted either white or black. For each integer pair (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, the color of the square at the i-th row from the top and j-th column from the left (we simply denote this square by Square (i, j)) is represented by A_{i, j}. Square (i, j) is white if A_{i, j} = 0, and black if A_{i, j} = 1.

You may perform the following operations any number of (possibly 0) times in any order:

• Choose an integer i such that 1 \leq i \leq H, pay R_i yen (the currency in Japan), and invert the color of each square in the i-th row from the top in the grid. (White squares are painted black, and black squares are painted white.)
• Choose an integer j such that 1 \leq j \leq W, pay C_j yen, and invert the color of each square in the j-th column from the left in the grid.

Print the minimum total cost to satisfy the following condition:

• There exists a path from Square (1, 1) to Square (H, W) that can be obtained by repeatedly moving down or to the right, such that all squares in the path (including Square (1, 1) and Square (H, W)) have the same color.

We can prove that it is always possible to satisfy the condition in a finite number of operations under the Constraints of this problem.

Constraints

• 2 \leq H, W \leq 2000
• 1 \leq R_i \leq 10^9
• 1 \leq C_j \leq 10^9
• A_{i, j} \in \lbrace 0, 1\rbrace
• All values in input are integers.

Sample Input 1

3 4
4 3 5
2 6 7 4
0100
1011
1010

Sample Output 1

9

We denote a white square by 0 and a black square by 1. On the initial grid, you can pay R_2 = 3 yen to invert the color of each square in the 2-nd row from the top to make the grid:

0100
0100
1010

Then, you can pay C_2 = 6 yen to invert the color of each square in the 2-nd row from the left to make the grid:

0000
0000
1110

Now, there exists a path from Square (1, 1) to Square (3, 4) such that all squares in the path have the same color (such as the path (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)). The total cost paid is 3+6 = 9 yen, which is the minimum possible.

Sample Input 2

15 20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78
39 97 12 53 62 32 38 84 49 93 53 26 13 25 2 76 32 42 34 18
01011100110000001111
10101111100010011000
11011000011010001010
00010100011111010100
11111001101010001011
01111001100101011100
10010000001110101110
01001011100100101000
11001000100101011000
01110000111011100101
00111110111110011111
10101111111011101101
11000011000111111001
00011101011110001101
01010000000001000000

Sample Output 2

125

Problem Statement

In a string fair, they determine the beauty of a non-empty string S consisting of lowercase English letters.

The beauty of string S equals the sum of N scores determined by N criteria. For i = 1, 2, \ldots, N, the score determined by the i-th criterion is "the number of occurrences of a string T_i (of length at most 3 given in the Input) in S as a consecutive subsequence" multiplied by P_i.

Print the maximum possible beauty of a non-empty string S consisting of lowercase English letters. If it is possible to obtain infinitely large beauty, print Infinity instead.

Here, the number of occurrences of a string V in a string U = U_1U_2\ldots U_{|U|} as a consecutive subsequence is defined to be the number of integers i such that 1 \leq i \leq |U|-|V|+1 and U_iU_{i+1}\ldots U_{i+|V|-1} = V.

Constraints

• 1 \leq N \leq 18278
• N is an integer.
• T_i is a string of length between 1 and 3 consisting of lowercase English letters.
• i \neq j \Rightarrow T_i \neq T_j
• -10^9 \leq P_i \leq 10^9
• P_i is an integer.

Sample Input 1

3
a -5
ab 10
ba -20

Sample Output 1

Infinity

For example, if S = abzabz:

• The score determined by the 1-st criterion is 2 \times (-5) = -10 points, because a occurs twice in S as a consecutive subsequence.
• The score determined by the 2-nd criterion is 2 \times 10 = 20 points, because ab occurs twice in S as a consecutive subsequence.
• The score determined by the 3-rd criterion is 0 \times (-20) = 0 points, because ba occurs 0 times in S as a consecutive subsequence.

Thus, the beauty of S is (-10) + 20 + 0 = 10.

As another example, if S = abzabzabz:

• The score determined by the 1-st criterion is 3 \times (-5) = -15 points, because a occurs 3 times in S as a consecutive subsequence.
• The score determined by the 2-nd criterion is 3 \times 10 = 30 points, because ab occurs 3 times in S as a consecutive subsequence.
• The score determined by the 3-rd criterion is 0 \times (-20) = 0 points, because ba occurs 0 times in S as a consecutive subsequence.

Thus, the beauty of S is (-15) + 30 + 0 = 15.

In general, for a positive integer X, if S is a concatenation of X copies of abz, then the beauty of S is 5X. Since you can obtain as large beauty as you want, Infinity should be printed.

Sample Input 2

28
a -5
ab 10
ba -20
bb -20
bc -20
bd -20
be -20
bf -20
bg -20
bh -20
bi -20
bj -20
bk -20
bl -20
bm -20
bn -20
bo -20
bp -20
bq -20
br -20
bs -20
bt -20
bu -20
bv -20
bw -20
bx -20
by -20
bz -20

Sample Output 2

5

S = ab achieves the maximum beauty possible.

Sample Input 3

26
a -1
b -1
c -1
d -1
e -1
f -1
g -1
h -1
i -1
j -1
k -1
l -1
m -1
n -1
o -1
p -1
q -1
r -1
s -1
t -1
u -1
v -1
w -1
x -1
y -1
z -1

Sample Output 3

-1

Note that S should be a non-empty string.

Problem Statement

We have a rooted tree with N vertices numbered 1,2,\dots,N.
The tree is rooted at Vertex 1, and the parent of Vertex i \ge 2 is Vertex P_i(<i).
For each integer k=1,2,\dots,N, solve the following problem:

There are 2^{k-1} ways to choose some of the vertices numbered between 1 and k so that Vertex 1 is chosen.
How many of them satisfy the following condition: the subgraph induced by the set of chosen vertices forms a perfect binary tree (with 2^d-1 vertices for a positive integer d) rooted at Vertex 1?
Since the count may be enormous, print the count modulo 998244353.

Constraints

• All values in input are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le P_i < i

Sample Input 1

10
1 1 2 1 2 5 5 5 1

Sample Output 1

1
1
2
2
4
4
4
5
7
10

The following ways of choosing vertices should be counted:

• \{1\} when k \ge 1
• \{1,2,3\} when k \ge 3
• \{1,2,5\},\{1,3,5\} when k \ge 5
• \{1,2,4,5,6,7,8\} when k \ge 8
• \{1,2,4,5,6,7,9\},\{1,2,4,5,6,8,9\} when k \ge 9
• \{1,2,10\},\{1,3,10\},\{1,5,10\} when k = 10

Sample Input 2

1

Sample Output 2

1

If N=1, the 2-nd line of the Input is empty.

Sample Input 3

10
1 2 3 4 5 6 7 8 9

Sample Output 3

1
1
1
1
1
1
1
1
1
1

Sample Input 4

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

Sample Output 4

1
1
2
4
4
4
4
4
7
13
13
19
31