Problem Statement

You are given a string S consisting of lowercase English letters and digits.

Extract only the digit characters from S and output the string formed by arranging them in their original order.

Constraints

• S is a string of length between 1 and 50, inclusive, consisting of lowercase English letters and digits.

Sample Input 1

abc462

Sample Output 1

462

The digits contained in abc462 are 4, 6, 2. Concatenating them in their original order gives 462. Thus, output 462.

Sample Input 2

codequeen

Sample Output 2

codequeen contains no digits, so output the empty string.

Sample Input 3

31415

Sample Output 3

31415

Sample Input 4

10plus2is12

Sample Output 4

10212

Problem Statement

You are given N integers A _ 1,A _ 2,\ldots,A _ N.

If their values are all equal, print Yes; otherwise, print No.

Constraints

• 2\leq N\leq100
• 1\leq A _ i\leq100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

3
3 2 4

Sample Output 1

No

We have A _ 1\neq A _ 2, so you should print No.

Sample Input 2

4
3 3 3 3

Sample Output 2

Yes

We have A _ 1=A _ 2=A _ 3=A _ 4, so you should print Yes.

Sample Input 3

10
73 8 55 26 97 48 37 47 35 55

Sample Output 3

No

Problem Statement

There are N people numbered 1 to N.

Person i guessed the building area of KEYENCE headquarters building to be S_i square meters.

The shape of KEYENCE headquarters building is shown below, where a and b are some positive integers.
That is, the building area of the building can be represented as 4ab+3a+3b.

Based on just this information, how many of the N people are guaranteed to be wrong in their guesses?

Constraints

• 1 \leq N \leq 20
• 1 \leq S_i \leq 1000
• All values in input are integers.

Sample Input 1

3
10 20 39

Sample Output 1

1

The area would be 10 square meters if a=1,b=1, and 39 square meters if a=2,b=3.

However, no pair of positive integers a and b would make the area 20 square meters.

Thus, we can only be sure that Person 2 guessed wrong.

Sample Input 2

5
666 777 888 777 666

Sample Output 2

3

Problem Statement

Locate a piece on a chessboard.

We have a grid with 8 rows and 8 columns of squares. Each of the squares has a 2-character name determined as follows.

• The first character of the name of a square in the 1-st column from the left is a. Similarly, the first character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th column from the left is b, c, d, e, f, g, h, respectively.
• The second character of the name of a square in the 1-st row from the bottom is 1. Similarly, the second character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th row from the bottom is 2, 3, 4, 5, 6, 7, 8, respectively.

For instance, the bottom-left square is named a1, the bottom-right square is named h1, and the top-right square is named h8.

You are given 8 strings S_1,\ldots,S_8, each of length 8, representing the state of the grid.
The j-th character of S_i is * if the square at the i-th row from the top and j-th column from the left has a piece on it, and . otherwise. The character * occurs exactly once among S_1,\ldots,S_8. Find the name of the square that has a piece on it.

Constraints

• S_i is a string of length 8 consisting of . and*.
• The character * occurs exactly once among S_1,\ldots,S_8.

Sample Input 1

........
........
........
........
........
........
........
*.......

Sample Output 1

a1

As explained in the problem statement, the bottom-left square is named a1.

Sample Input 2

........
........
........
........
........
.*......
........
........

Sample Output 2

b3

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

There are N people standing in a line: person 1, person 2, \ldots, person N.

You are given the arrangement of the people as a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

A _ i\ (1\leq i\leq N) represents the following information:

• if A _ i=-1, person i is at the front of the line;
• if A _ i\neq -1, person i is right behind person A _ i.

Print the people's numbers in the line from front to back.

Constraints

• 1\leq N\leq3\times10 ^ 5
• A _ i=-1 or 1\leq A _ i\leq N\ (1\leq i\leq N)
• There is exactly one way to arrange the N people consistent with the information given.
• All input values are integers.

Sample Input 1

6
4 1 -1 5 3 2

Sample Output 1

3 5 4 1 2 6

If person 3, person 5, person 4, person 1, person 2, and person 6 stand in line in this order from front to back, the arrangement matches the given information.

Indeed, it can be seen that:

• person 1 is standing right behind person 4,
• person 2 is standing right behind person 1,
• person 3 is at the front of the line,
• person 4 is standing right behind person 5,
• person 5 is standing right behind person 3, and
• person 6 is standing right behind person 2.

Thus, print 3, 5, 4, 1, 2, and 6 in this order, separated by spaces.

Sample Input 2

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

Sample Output 2

1 2 3 4 5 6 7 8 9 10

Sample Input 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

Sample Output 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

Problem Statement

On a certain planet, there are N aliens, all of whom are minors.

The i-th alien currently has A_i stones, and will become an adult exactly i years later.

When someone becomes an adult on this planet, every adult who has at least one stone gives exactly one stone as a congratulatory gift to the alien who has just become an adult.

Find how many stones each alien will have after N years.

Assume that no new aliens will be born in the future.

Constraints

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

Sample Input 1

4
5 0 9 3

Sample Output 1

2 0 10 5

Let C_i be the number of stones that the i-th alien has at a given time.

Initially, (C_1, C_2, C_3, C_4) = (5, 0, 9, 3).

After 1 year, (C_1, C_2, C_3, C_4) = (5, 0, 9, 3).

After 2 years, (C_1, C_2, C_3, C_4) = (4, 1, 9, 3).

After 3 years, (C_1, C_2, C_3, C_4) = (3, 0, 11, 3).

After 4 years, (C_1, C_2, C_3, C_4) = (2, 0, 10, 5).

Sample Input 2

5
4 6 7 2 5

Sample Output 2

0 4 7 4 9

Sample Input 3

10
2 9 1 2 0 4 6 7 1 5

Sample Output 3

0 2 0 0 0 4 7 10 4 10

Problem Statement

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

Takahashi is on one of the cells in this grid, and there is trash on some cells of the grid.

The states of the cells are given by H strings S_1, S_2, \ldots, S_H of length W, where S_{i, j} denotes the j-th character of S_i and represents the following state:

• If S_{i, j} = T, cell (i, j) is the cell where Takahashi is.
• If S_{i, j} = #, cell (i, j) is a cell with trash.
• If S_{i, j} = ., cell (i, j) is an empty cell without trash.

There is no trash on the cell where Takahashi is.

He can repeatedly perform the following operation:

• Choose one of the four directions (up, down, left, or right), and move all trash simultaneously one cell in that direction. Here, if trash goes outside the grid, the trash disappears, and if trash moves to the cell where he is, he gets dirty.

Determine whether it is possible for him to make all trash disappear without getting dirty, and if possible, find the minimum possible number of operations.

Constraints

• 2 \leq H, W \leq 12
• S_i is a string of length W consisting of T, #, and ..
• There is exactly one (i, j) such that S_{i, j} = T.
• There is at least one (i, j) such that S_{i, j} = #.

Sample Input 1

3 4
###.
#.T.
...#

Sample Output 1

3

Takahashi can make all trash disappear in three operations as follows:

• Choose up. After this operation, trash is on cells (1, 1) and (2, 4).

• Choose right. After this operation, trash is on cell (1, 2).

• Choose up. After this operation, all trash has disappeared.

Sample Input 2

3 3
###
#T#
###

Sample Output 2

-1

Sample Input 3

5 5
###..
#T...
..##.
##..#
#..#.

Sample Output 3

5

Problem Statement

A sequence X = (X_1, X_2, \ldots) of positive integers (possibly empty) is called a 1122 sequence if and only if it satisfies all of the following three conditions: (The definition of a 1122 sequence is the same as in Problem D.)

• \lvert X \rvert is even. Here, \lvert X \rvert denotes the length of X.
• For each integer i satisfying 1\leq i\leq \frac{|X|}{2}, X_{2i-1} and X_{2i} are equal.
• Each positive integer appears in X either not at all or exactly twice. That is, every positive integer contained in X appears exactly twice in X.

Given a sequence A = (A_1, A_2, \ldots, A_N) of length N consisting of positive integers, print the maximum length of a subsequence (not necessarily contiguous) of A that is a 1122 sequence.

Constraints

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

Sample Input 1

7
1 3 3 1 2 2 1

Sample Output 1

4

For example, choosing the 1-st, 4-th, 5-th, and 6-th elements of A, we get (1, 1, 2, 2), which is a 1122 sequence of length 4.
There is no longer subsequence that satisfies the conditions for a 1122 sequence, so the answer is 4.

Sample Input 2

1
20

Sample Output 2

0