Problem Statement

We will hand out a total of K cards to N people numbered 1, 2, \ldots, N.

Beginning with Person A, we will give the cards one by one to the people in this order: A, A+1, A+2, \ldots, N, 1, 2, \ldots. Who will get the last card?

Formally, after Person x(1 \leq x < N) gets a card, Person x+1 will get a card. After Person N gets a card, Person 1 gets a card.

Constraints

• 1 \leq N,K \leq 1000
• 1 \leq A \leq N
• All values in input are integers.

Sample Input 1

3 3 2

Sample Output 1

1

The cards are given to Person 2, 3, 1 in this order.

Sample Input 2

1 100 1

Sample Output 2

1

Sample Input 3

3 14 2

Sample Output 3

3

Problem Statement

Takahashi decided to make takoyaki (octopus balls) and serve it to Snuke. Takahashi instructed Snuke to raise only his left hand if he wants to eat takoyaki, and only his right hand otherwise.

You are given the information about which hand Snuke is raising as two integers L and R. He is raising his left hand if and only if L = 1, and raising his right hand if and only if R = 1. He might not follow the instructions and could raise both hands or not raise any hand at all.

If Snuke is raising only one hand, print Yes if he wants to eat takoyaki, and No if he does not. If he is raising both hands or not raising any hand, print Invalid.

Assume that if Snuke is raising only one hand, he is always following the instructions.

Constraints

• Each of L and R is 0 or 1.

Sample Input 1

1 0

Sample Output 1

Yes

Snuke wants to eat takoyaki, so he is raising only his left hand.

Sample Input 2

1 1

Sample Output 2

Invalid

Snuke is raising both hands.

Problem Statement

We have a board with R rows running horizontally and C columns running vertically. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

You are given characters B_{i,j} representing the current states of (i,j). . represents an empty square; # represents a square with a wall; 1, 2,\dots, 9 represent a square with a bomb of power 1,2,\dots,9, respectively.

At the next moment, all bombs will explode simultaneously. When a bomb explodes, every square whose Manhattan distance from the square with the bomb is not greater than the power of the bomb will turn into an empty square. Here, the Manhattan distance from (r_1,c_1) to (r_2,c_2) is |r_1-r_2|+|c_1-c_2|.

Print the board after the explosions.

Constraints

• 1\leq R,C \leq 20
• R and C are integers.
• Each B_{i,j} is one of ., #, 1, 2, \dots, 9.

Sample Input 1

4 4
.1.#
###.
.#2.
#.##

Sample Output 1

...#
#...
....
#...

• The explosion of the bomb at (1,2) will turn the blue squares and purple squares in the above figure into empty squares.
• The explosion of the bomb at (3,3) will turn the red squares and purple squares in the above figure into empty squares.

As seen in this sample, the explosion ranges of bombs may overlap.

Sample Input 2

2 5
..#.#
###.#

Sample Output 2

..#.#
###.#

There may be no bombs.

Sample Input 3

2 3
11#
###

Sample Output 3

...
..#

Sample Input 4

4 6
#.#3#.
###.#.
##.###
#1..#.

Sample Output 4

......
#.....
#....#
....#.

Problem Statement

Takahashi has a music player. Initially, the volume is 0 and the music is stopped.

From now on, Q operations will be performed in order. The i-th operation is represented by an integer A_i, which means the following:

• If A_i = 1, increase the volume by 1.
• If A_i = 2, if the current volume is 1 or more, decrease it by 1; if it is 0, do nothing.
• If A_i = 3, if the music is stopped, play it; if the music is playing, stop it.

For i = 1, 2, \ldots, Q, solve the following problem:

• Determine whether the music is playing at volume 3 or more immediately after the i-th operation.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• A_i \in \lbrace 1, 2, 3 \rbrace
• All input values are integers.

Sample Input 1

10
2
1
3
1
3
1
1
3
2
2

Sample Output 1

No
No
No
No
No
No
No
Yes
Yes
No

• After the 1-st operation, the volume is 0 and the music is stopped.

• After the 2-nd operation, the volume is 1 and the music is stopped.

• After the 3-rd operation, the volume is 1 and the music is playing.

• After the 4-th operation, the volume is 2 and the music is playing.

• After the 5-th operation, the volume is 2 and the music is stopped.

• After the 6-th operation, the volume is 3 and the music is stopped.

• After the 7-th operation, the volume is 4 and the music is stopped.

• After the 8-th operation, the volume is 4 and the music is playing.

• After the 9-th operation, the volume is 3 and the music is playing.

• After the 10-th operation, the volume is 2 and the music is playing.

Problem Statement

Takahashi sent a string T consisting of lowercase English letters to Aoki. As a result, Aoki received a string T' consisting of lowercase English letters.

T' may have been altered from T. Specifically, exactly one of the following four conditions is known to hold.

• T' is equal to T.
• T' is a string obtained by inserting one lowercase English letter at one position (possibly the beginning and end) in T.
• T' is a string obtained by deleting one character from T.
• T' is a string obtained by changing one character in T to another lowercase English letter.

You are given the string T' received by Aoki and N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters. Find all the strings among S_1, S_2, \ldots, S_N that could equal the string T sent by Takahashi.

Constraints

• N is an integer.
• 1 \leq N \leq 5 \times 10^5
• S_i and T' are strings of length between 1 and 5 \times 10^5, inclusive, consisting of lowercase English letters.
• The total length of S_1, S_2, \ldots, S_N is at most 5 \times 10^5.

Sample Input 1

5 ababc
ababc
babc
abacbc
abdbc
abbac

Sample Output 1

4
1 2 3 4

Among S_1, S_2, \ldots, S_5, the strings that could be equal to T are S_1, S_2, S_3, S_4, as explained below.

• S_1 could be equal to T, because T' = ababc is equal to S_1 = ababc.
• S_2 could be equal to T, because T' = ababc is obtained by inserting the letter a at the beginning of S_2 = babc.
• S_3 could be equal to T, because T' = ababc is obtained by deleting the fourth character c from S_3 = abacbc.
• S_4 could be equal to T, because T' = ababc is obtained by changing the third character d in S_4 = abdbc to b.
• S_5 could not be equal to T, because if we take S_5 = abbac as T, then T' = ababc does not satisfy any of the four conditions in the problem statement.

Sample Input 2

1 aoki
takahashi

Sample Output 2

0

Sample Input 3

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

Sample Output 3

6
1 2 4 7 8 9

Problem Statement

A string T is called a good bracket sequence if and only if it satisfies the following condition:

• T can be made into an empty string by repeating the following operation zero or more times:

  • Choose () contained in T as a (contiguous) substring and remove it.

For example, (), (()()), and the empty string are good bracket sequences, but )()( and ))) are not good bracket sequences.

There is a string S. Initially, S is an empty string.
Process Q queries in the order they are given. After each query, determine whether S is a good bracket sequence.
There are two types of queries:

• 1 c: A character c is given. c is either ( or ). Append c to the end of S.
• 2: Remove the last character of S. It is guaranteed that S is not an empty string at this time.

Constraints

• 1 \leq Q \leq 8 \times 10^5
• c in queries of the first type is ( or ).
• It is guaranteed that S is not empty when a query of the second type is given.
• Q is an integer.

Sample Input 1

8
1 (
2
1 (
1 )
2
1 (
1 )
1 )

Sample Output 1

No
Yes
No
Yes
No
No
No
Yes

S immediately after processing the 1st query is (, which is not a good bracket sequence.
S immediately after processing the 2nd query is an empty string, which is a good bracket sequence.
S immediately after processing the 3rd query is (, which is not a good bracket sequence.
S immediately after processing the 4th query is (), which is a good bracket sequence.
S immediately after processing the 5th query is (, which is not a good bracket sequence.
S immediately after processing the 6th query is ((, which is not a good bracket sequence.
S immediately after processing the 7th query is ((), which is not a good bracket sequence.
S immediately after processing the 8th query is (()), which is a good bracket sequence.

Problem Statement

You are given an integer W.
You are going to prepare some weights so that all of the conditions below are satisfied.

• The number of weights is between 1 and 300, inclusive.
• Each weight has a mass of positive integer not exceeding 10^6.
• Every integer between 1 and W, inclusive, is a good integer. Here, a positive integer n is said to be a good integer if the following condition is satisfied:
  • We can choose at most 3 different weights from the prepared weights with a total mass of n.

Print a combination of weights that satisfies the conditions.

Constraints

• 1 \leq W \leq 10^6
• W is an integer.

Sample Input 1

6

Sample Output 1

3
1 2 3

In the output above, 3 weights with masses 1, 2, and 3 are prepared.
This output satisfies the conditions. Especially, regarding the 3-rd condition, we can confirm that every integer between 1 and W, inclusive, is a good integer.

• If we choose only the 1-st weight, it has a total mass of 1.
• If we choose only the 2-nd weight, it has a total mass of 2.
• If we choose only the 3-rd weight, it has a total mass of 3.
• If we choose the 1-st and the 3-rd weights, they have a total mass of 4.
• If we choose the 2-nd and the 3-rd weights, they have a total mass of 5.
• If we choose the 1-st, the 2-nd, and the 3-rd weights, they have a total mass of 6.

Sample Input 2

12

Sample Output 2

6
2 5 1 2 5 1

You may prepare multiple weights with the same mass.

Problem Statement

There is a 3 \times 3 grid. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left (1 \leq i, j \leq 3). Cell (i, j) contains an integer A_{i,j}. It is guaranteed that \sum_{i=1}^3 \sum_{j=1}^3 A_{i,j} is odd. Additionally, all cells are initially painted white.

Takahashi and Aoki will play a game using this grid. Takahashi goes first, and they take turns performing the following operation:

• Choose a cell (i, j) (1\leq i, j \leq 3) that is still painted white (it can be shown that such a cell always exists at the time of the operation). The player performing the operation scores A_{i,j} points. Then, if the player is Takahashi, he paints the cell (i, j) red; if the player is Aoki, he paints it blue.

After each operation, the following checks are made:

• Check if there are three consecutive cells painted the same color (red or blue) in any row, column, or diagonal. If such a sequence exists, the game ends immediately, and the player whose color forms the sequence wins.
• Check if there are white cells left. If no white cells remain, the game ends, and the player with the higher total score wins.

It can be shown that the game will always end after a finite number of moves, and either Takahashi or Aoki will win. Determine which player wins if both play optimally for victory.

Constraints

• |A_{i,j}| \leq 10^9
• \sum_{i=1}^3 \sum_{j=1}^3 A_{i,j} is odd.
• All input values are integers.

Sample Input 1

0 0 0
0 1 0
0 0 0

Sample Output 1

Takahashi

If Takahashi chooses cell (2,2) in his first move, no matter how Aoki plays afterward, Takahashi can always act to prevent three consecutive blue cells. If three consecutive red cells are formed, Takahashi wins. If the game ends without three consecutive red cells, at that point, Takahashi has scored 1 point and Aoki 0 points, so Takahashi wins either way.

Sample Input 2

-1 1 0
-4 -2 -5
-4 -1 -5

Sample Output 2

Aoki

Problem Statement

Consider placing B black rooks and W white rooks on a grid with N horizontal rows and M vertical columns.

A placement of the rooks satisfying all of the following conditions is called a good placement.

• All B+W rooks are placed on the grid.
• At most one rook is placed in the same square.
• There is no pair of white rook and black rook attacking each other. That is, there is no pair of white rook and black rook such that one of them can reach the square in which the other is placed in one move.

Here, in one move, a rook can reach any square that is on a horizontal or vertical line from its current position and is reachable without jumping over another rook.

How many good placements are there? Since this count can be enormous, print it modulo 998244353.

Rooks in the same color are not distinguished.

Constraints

• 1 \leq N,M \leq 50
• 1 \leq B,W \leq 2500
• B+W \leq N \times M
• All values in input are integers.

Sample Input 1

2 2 1 1

Sample Output 1

4

There are four good placements as follows.

Sample Input 2

1 2 1 1

Sample Output 2

0

There may be no good placement.

Sample Input 3

40 40 30 30

Sample Output 3

467620384

Be sure to print the count modulo 998244353.