Problem Statement

We have five cards with integers A, B, C, D, and E written on them, one on each card.

This set of five cards is called a Full house if and only if the following condition is satisfied:

• the set has three cards with a same number written on them, and two cards with another same number written on them.

Determine whether the set is a Full house.

Constraints

• 1 \leq A,B,C,D,E\leq 13
• Not all of A, B, C, D, and E are the same.
• All values in input are integers.

Sample Input 1

1 2 1 2 1

Sample Output 1

Yes

The set has three cards with 1 written on them and two cards with 2 written on them, so it is a Full house.

Sample Input 2

12 12 11 1 2

Sample Output 2

No

The condition is not satisfied.

Problem Statement

There are 12 strings S_1, S_2, \ldots, S_{12} consisting of lowercase English letters.

Find how many integers i (1 \leq i \leq 12) satisfy that the length of S_i is i.

Constraints

• Each S_i is a string of length between 1 and 100, inclusive, consisting of lowercase English letters. (1 \leq i \leq 12)

Sample Input 1

january
february
march
april
may
june
july
august
september
october
november
december

Sample Output 1

1

There is only one integer i such that the length of S_i is i: 9. Thus, print 1.

Sample Input 2

ve
inrtfa
npccxva
djiq
lmbkktngaovl
mlfiv
fmbvcmuxuwggfq
qgmtwxmb
jii
ts
bfxrvs
eqvy

Sample Output 2

2

There are two integers i such that the length of S_i is i: 4 and 8. Thus, print 2.

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

• A_i \neq 0 ( 1 \le i \le N-1 )
• A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
• A_N = 0

Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

0

Sample Output 2

0

A=(0).

Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123

Problem Statement

Overview: Create an N \times N pattern as follows.

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

You are given a positive integer N.

Consider an N \times N grid. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left. Initially, no cell is colored.

Then, for i = 1,2,\dots,N in order, perform the following operation:

• Let j = N + 1 - i.
• If i \leq j, fill the rectangular region whose top-left cell is (i,i) and bottom-right cell is (j,j) with black if i is odd, or white if i is even. If some cells are already colored, overwrite their colors.
• If i > j, do nothing.

After all these operations, it can be proved that there are no uncolored cells. Determine the final color of each cell.

Constraints

• 1 \leq N \leq 50
• All input values are integers.

Sample Input 1

11

Sample Output 1

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

This matches the pattern shown in the Overview.

Sample Input 2

5

Sample Output 2

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

Colors are applied as follows, where ? denotes a cell not yet colored:

         i=1      i=2      i=3      i=4      i=5
?????    #####    #####    #####    #####    #####
?????    #####    #...#    #...#    #...#    #...#
????? -> ##### -> #...# -> #.#.# -> #.#.# -> #.#.#
?????    #####    #...#    #...#    #...#    #...#
?????    #####    #####    #####    #####    #####

Sample Input 3

8

Sample Output 3

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

Sample Input 4

2

Sample Output 4

##
##

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq D\leq 2\times 10^5
• 1\leq P\leq 10^9
• 1\leq F_i\leq 10^9
• All input values are integers.

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

6

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

• 1\leq N\leq 2\times 10^5
• S is a string of length N consisting of 0 and 1.
• 1\leq W_i\leq 10^9
• N and W_i are integers.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i,j) the cell at the i-th row from the top and j-th column from the left. Each cell in the grid has a lowercase English letter written on it. The letter written on (i,j) equals the j-th character of a given string S_i.

Snuke will repeat moving to an adjacent cell sharing a side to travel from (1,1) to (H,W). Determine if there is a path in which the letters written on the visited cells (including initial (1,1) and final (H,W)) are s \rightarrow n \rightarrow u \rightarrow k \rightarrow e \rightarrow s \rightarrow n \rightarrow \dots, in the order of visiting. Here, a cell (i_1,j_1) is said to be an adjacent cell of (i_2,j_2) sharing a side if and only if |i_1-i_2|+|j_1-j_2| = 1.

Formally, determine if there is a sequence of cells ((i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)) such that:

• (i_1,j_1) = (1,1),(i_k,j_k) = (H,W);
• (i_{t+1},j_{t+1}) is an adjacent cell of (i_t,j_t) sharing a side, for all t\ (1 \leq t < k); and
• the letter written on (i_t,j_t) coincides with the (((t-1) \bmod 5) + 1)-th character of snuke, for all t\ (1 \leq t \leq k).

Constraints

• 2\leq H,W \leq 500
• H and W are integers.
• S_i is a string of length W consisting of lowercase English letters.

Sample Input 1

2 3
sns
euk

Sample Output 1

Yes

The path (1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) satisfies the conditions because they have s \rightarrow n \rightarrow u \rightarrow k written on them, in the order of visiting.

Sample Input 2

2 2
ab
cd

Sample Output 2

No

Sample Input 3

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

Sample Output 3

Yes

Problem Statement

We have an integer sequence A and a notebook. The notebook has 10^9 pages.

You are given Q queries. Each query is of one of the following four kinds:

ADD x: append an integer x to the tail of A.

DELETE: remove the last term of A if A is not empty; do nothing otherwise.

SAVE y: erase the sequence recorded on the y-th page of the notebook, and record the current A onto the y-th page.

LOAD z: replace A with the sequence recorded on the z-th page of the notebook.

Initially, A is an empty sequence, and an empty sequence is recorded on each page of the notebook. Process Q queries successively in the given order and print the last term of A after processing each query.

The use of fast input and output methods is recommended because of potentially large input and output.

Constraints

• 1 \leq Q \leq 5 \times 10^5
• 1 \leq x, y, z \leq 10^9
• Q, x, y, and z are integers.
• Each of the given queries is of one of the four kinds in the Problem Statement.

Sample Input 1

11
ADD 3
SAVE 1
ADD 4
SAVE 2
LOAD 1
DELETE
DELETE
LOAD 2
SAVE 1
LOAD 3
LOAD 1

Sample Output 1

3 3 4 4 3 -1 -1 4 4 -1 4

Initially, A is an empty sequence, so A = (), and an empty sequence is recorded on each page of the notebook.

• By the 1-st query, 3 is appended to the tail of A, resulting in A = (3).
• By the 2-nd query, the sequence recorded on the 1-st page of the notebook becomes (3). It remains that A = (3).
• By the 3-rd query, 4 is appended to the tail of A, resulting in A = (3, 4).
• By the 4-th query, the sequence recorded on the 2-nd page of the notebook becomes (3, 4). It remains that A = (3, 4).
• By the 5-th query, A is replaced by (3), which is recorded on the 1-st page of the notebook, resulting in A = (3).
• By the 6-th query, the last term of A is removed, resulting in A = ().
• By the 7-th query, nothing happens because A is already empty. It remains that A = ().
• By the 8-th query, A is replaced by (3,4), which is recorded on the 2-nd page of the notebook, resulting in A = (3, 4).
• By the 9-th query, the sequence recorded on the 1-st page of the notebook becomes (3, 4). It remains that A = (3, 4).
• By the 10-th query, A is replaced by (), which is recorded on the 3-rd page of the notebook, resulting in A = ().
• By the 11-th query, A is replaced by (3, 4), which is recorded on the 1-st page of the notebook, resulting in A = (3, 4).

Sample Input 2

21
ADD 4
ADD 3
DELETE
ADD 10
LOAD 7
SAVE 5
SAVE 5
ADD 4
ADD 4
ADD 5
SAVE 5
ADD 2
DELETE
ADD 1
SAVE 5
ADD 7
ADD 8
DELETE
ADD 4
DELETE
LOAD 5

Sample Output 2

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

Problem Statement

There are N balls arranged from left to right. The color of the i-th ball from the left is Color C_i, and an integer X_i is written on it.

Takahashi wants to rearrange the balls so that the integers written on the balls are non-decreasing from left to right. In other words, his objective is to reach a situation where, for every 1\leq i\leq N-1, the number written on the (i+1)-th ball from the left is greater than or equal to the number written on the i-th ball from the left.

For this, Takahashi can repeat the following operation any number of times (possibly zero):

Choose an integer i such that 1\leq i\leq N-1.
If the colors of the i-th and (i+1)-th balls from the left are different, pay a cost of 1. (No cost is incurred if the colors are the same).
Swap the i-th and (i+1)-th balls from the left.

Find the minimum total cost Takahashi needs to pay to achieve his objective.

Constraints

• 2 \leq N \leq 3\times 10^5
• 1\leq C_i\leq N
• 1\leq X_i\leq N
• All values in input are integers.

Sample Input 1

5
1 5 2 2 1
3 2 1 2 1

Sample Output 1

6

Let us represent a ball as (Color, Integer). The initial situation is (1,3), (5,2), (2,1), (2,2), (1,1). Here is a possible sequence of operations for Takahashi:

• Swap the 1-st ball (Color 1) and 2-nd ball (Color 5). Now the balls are arranged in the order (5,2), (1,3), (2,1), (2,2), (1,1).
• Swap the 2-nd ball (Color 1) and 3-rd ball (Color 2). Now the balls are arranged in the order (5,2), (2,1), (1,3), (2,2), (1,1).
• Swap the 3-rd ball (Color 1) and 4-th ball (Color 2). Now the balls are in the order (5,2), (2,1), (2,2), (1,3), (1,1).
• Swap the 4-th ball (Color 1) and 5-th ball (Color 1). Now the balls are in the order (5,2), (2,1), (2,2), (1,1), (1,3).
• Swap the 3-rd ball (Color 2) and 4-th ball (Color 1). Now the balls are in the order(5,2), (2,1), (1,1), (2,2), (1,3).
• Swap the 1-st ball (Color 5) and 2-nd ball (Color 2). Now the balls are in the order (2,1), (5,2), (1,1), (2,2), (1,3).
• Swap the 2-nd ball (Color 5) and 3-rd ball (Color 1). Now the balls are in the order (2,1), (1,1), (5,2), (2,2), (1,3).

After the last operation, the numbers written on the balls are 1,1,2,2,3 from left to right, which achieves Takahashi's objective.

The 1-st, 2-nd, 3-rd, 5-th, 6-th, and 7-th operations incur a cost of 1 each, for a total of 6, which is the minimum. Note that the 4-th operation does not incur a cost since the balls are both in Color 1.

Sample Input 2

3
1 1 1
3 2 1

Sample Output 2

0

All balls are in the same color, so no cost is incurred in swapping balls.

Sample Input 3

3
3 1 2
1 1 2

Sample Output 3

0

Takahashi's objective is already achieved without any operation.