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