Problem Statement

There are N boxes numbered 1,2,\dots,N. Initially, all boxes are empty.

Q balls will come in order.
Takahashi will put the balls into the boxes according to the sequence X=(X_1,X_2,\dots,X_Q).
Specifically, he performs the following process for the i-th ball:

• If X_i \ge 1: Put this ball into box X_i.
• If X_i = 0: Put this ball into the box with the smallest number among those containing the fewest balls.

Find which box each ball was put into.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le Q \le 100
• 0 \le X_i \le N

Sample Input 1

4 5
2 0 3 0 0

Sample Output 1

2 1 3 4 1

There are 4 boxes, and 5 balls come.

• Initially, all boxes are empty.
  • The numbers of balls in box 1,2,3,4 are 0,0,0,0, respectively.
• Since X_1=2, put the 1st ball into box 2.
  • The numbers of balls in box 1,2,3,4 are 0,1,0,0, respectively.
• Since X_2=0, put the 2nd ball into box 1, which has the smallest number among those containing the fewest balls.
  • The numbers of balls in box 1,2,3,4 are 1,1,0,0, respectively.
• Since X_3=3, put the 3rd ball into box 3.
  • The numbers of balls in box 1,2,3,4 are 1,1,1,0, respectively.
• Since X_4=0, put the 4th ball into box 4, which has the smallest number among those containing the fewest balls.
  • The numbers of balls in box 1,2,3,4 are 1,1,1,1, respectively.
• Since X_5=0, put the 5th ball into box 1, which has the smallest number among those containing the fewest balls.
  • The numbers of balls in box 1,2,3,4 are 2,1,1,1, respectively.

The balls were put into boxes 2,1,3,4,1 in order. Thus, output 2 1 3 4 1.

Sample Input 2

3 7
1 1 0 0 0 0 0

Sample Output 2

1 1 2 3 2 3 1

Sample Input 3

6 20
4 6 0 3 4 2 6 5 2 3 0 3 2 5 0 3 5 0 2 0

Sample Output 3

4 6 1 3 4 2 6 5 2 3 1 3 2 5 1 3 5 4 2 6

Problem Statement

You are given a sequence of non-negative integers A=(A_1,A_2,\dots,A_N) of length N. Find the maximum non-negative integer x that satisfies the following:

• In A, elements greater than or equal to x appear at least x times (including duplicates).

Constraints

• 1 \leq N \leq 100
• 0 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

3
1 2 1

Sample Output 1

1

In A=(1,2,1):

• Elements greater than or equal to 0 appear 3 times.
• Elements greater than or equal to 1 appear 3 times.
• Elements greater than or equal to 2 appear 1 time.
• Elements greater than or equal to 3 appear 0 times.

The maximum non-negative integer that satisfies the condition is 1.

Sample Input 2

7
1 6 2 10 2 3 2

Sample Output 2

3

Problem Statement

We have N cups of ice cream.
The flavor and deliciousness of the i-th cup are F_i and S_i, respectively (S_i is an even number).

You will choose and eat two of the N cups.
Your satisfaction here is defined as follows.

• Let s and t (s \ge t) be the deliciousness of the eaten cups.
  • If the two cups have different flavors, your satisfaction is \displaystyle s+t.
  • Otherwise, your satisfaction is \displaystyle s + \frac{t}{2}.

Find the maximum achievable satisfaction.

Constraints

• All input values are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le F_i \le N
• 2 \le S_i \le 10^9
• S_i is even.

Sample Input 1

4
1 4
2 10
2 8
3 6

Sample Output 1

16

Consider eating the second and fourth cups.

• The second cup has a flavor of 2 and deliciousness of 10.
• The fourth cup has a flavor of 3 and deliciousness of 6.
• Since they have different flavors, your satisfaction is 10+6=16.

Thus, you can achieve the satisfaction of 16.
You cannot achieve a satisfaction greater than 16.

Sample Input 2

4
4 10
3 2
2 4
4 12

Sample Output 2

17

Consider eating the first and fourth cups.

• The first cup has a flavor of 4 and deliciousness of 10.
• The fourth cup has a flavor of 4 and deliciousness of 12.
• Since they have the same flavor, your satisfaction is 12+\frac{10}{2}=17.

Thus, you can achieve the satisfaction of 17.
You cannot achieve a satisfaction greater than 17.

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

• Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

• 1\leq H \leq 100
• 2\leq W \leq 100
• H and W are integers.
• S_i is a string of length W consisting of . and T.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC

Problem Statement

There is a sequence A = (A_0, A_1, \dots, A_{N - 1}) with N = 2^{20} terms. Initially, every term is -1.

Process Q queries in order. The i-th query (1 \leq i \leq Q) is described by an integer t_i such that t_i = 1 or t_i = 2, and another integer x_i, as follows.

• If t_i = 1, do the following in order.
  1. Define an integer h as h = x_i.
  2. While A_{h \bmod N} \neq -1, keep adding 1 to h. We can prove that this process ends after finite iterations under the Constraints of this problem.
  3. Replace the value of A_{h \bmod N} with x_i.
• If t_i = 2, print the value of A_{x_i \bmod N} at that time.

Here, for integers a and b, a \bmod b denotes the remainder when a is divided by b.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• t_i \in \{ 1, 2 \} \, (1 \leq i \leq Q)
• 0 \leq x_i \leq 10^{18} \, (1 \leq i \leq Q)
• There is at least one i (1 \leq i \leq Q) such that t_i = 2.
• All values in input are integers.

Sample Input 1

4
1 1048577
1 1
2 2097153
2 3

Sample Output 1

1048577
-1

We have x_1 \bmod N = 1, so the first query sets A_1 = 1048577.

In the second query, initially we have h = x_2, for which A_{h \bmod N} = A_{1} \neq -1, so we add 1 to h. Now we have A_{h \bmod N} = A_{2} = -1, so this query sets A_2 = 1.

In the third query, we print A_{x_3 \bmod N} = A_{1} = 1048577.

In the fourth query, we print A_{x_4 \bmod N} = A_{3} = -1.

Note that, in this problem, N = 2^{20} = 1048576 is a constant and not given in input.