Problem Statement

You are given a string S of length N consisting of A, B, and C.
Find the position where ABC first appears as a (contiguous) substring in S. In other words, find the smallest integer n that satisfies all of the following conditions.

• 1 \leq n \leq N - 2.
• The string obtained by extracting the n-th through (n+2)-th characters of S is ABC.

If ABC does not appear in S, print -1.

Constraints

• 3 \leq N \leq 100
• S is a string of length N consisting of A, B, and C.

Sample Input 1

8
ABABCABC

Sample Output 1

3

ABC first appears in S at the 3-rd through 5-th characters of S. Therefore, the answer is 3.

Sample Input 2

3
ACB

Sample Output 2

-1

If ABC does not appear in S, print -1.

Sample Input 3

20
BBAAABBACAACABCBABAB

Sample Output 3

13

Problem Statement

You are given a 3-character string S, which is a concatenation of integers a and b between 1 and 9 (inclusive) and the character x in this order: axb.

Find the product of a and b.

Constraints

• The length of S is 3.
• The 1-st and 3-rd characters are digits between 1 and 9 (inclusive).
• The 2-nd character is x.

Sample Input 1

3x7

Sample Output 1

21

We have 3 \times 7 = 21, which should be printed.

Sample Input 2

9x9

Sample Output 2

81

Sample Input 3

1x1

Sample Output 3

1

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

• L\leq X_i \leq R.
• For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

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

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

• |4-3|=1
• |5-3|=2
• |6-3|=3
• |7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10

Problem Statement

There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them. The i-th operation is as follows:

• If the L_i-th piece from the left is on its rightmost square, do nothing.
• Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.

Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.

Constraints

• 1\leq K\leq N\leq 200
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1\leq Q\leq 1000
• 1\leq L_i\leq K
• All values in input are integers.

Sample Input 1

5 3 5
1 3 4
3 3 1 1 2

Sample Output 1

2 4 5

At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:

• The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
• The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
• The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
• The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
• The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.

Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.

Sample Input 2

2 2 2
1 2
1 2

Sample Output 2

1 2

Sample Input 3

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

Sample Output 3

2 5 6 7 9 10

Problem Statement

You are given a length-N sequence of non-negative integers.
When B is a sequence obtained by choosing K elements from A and concatenating them without changing the order, find the maximum possible value of MEX(B).

Here, for a sequence X, we define MEX(X) as the unique non-negative integer m that satisfies the following conditions:

• Every integer i such that 0 \le i < m is contained in X.
• m is not contained in X.

Constraints

• All values in the input are integers.
• 1 \le K \le N \le 3 \times 10^5
• 0 \le A_i \le 10^9

Sample Input 1

7 3
2 0 2 3 2 1 9

Sample Output 1

3

In this input, A=(2,0,2,3,2,1,9), and you obtain the sequence B by picking K=3 elements. For example,

• If the 1-st, 2-nd, and 3-rd elements are chosen, MEX(B)=MEX(2,0,2)=1.
• If the 3-rd, 4-th, and 6-th elements are chosen, MEX(B)=MEX(2,3,1)=0.
• If the 2-nd, 6-th, and 7-th elements are chosen, MEX(B)=MEX(0,1,9)=2.
• If the 2-nd, 3-rd, and 6-th elements are chosen, MEX(B)=MEX(0,2,1)=3.

The maximum possible MEX is 3.

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq A_i \leq 10^{9}
• 1 \leq C_i \leq 10^{9}
• All input values are integers.

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

You are given an integer K greater than or equal to 2.
Find the minimum positive integer N such that N! is a multiple of K.

Here, N! denotes the factorial of N. Under the Constraints of this problem, we can prove that such an N always exists.

Constraints

• 2\leq K\leq 10^{12}
• K is an integer.

Sample Input 1

30

Sample Output 1

5

• 1!=1
• 2!=2\times 1=2
• 3!=3\times 2\times 1=6
• 4!=4\times 3\times 2\times 1=24
• 5!=5\times 4\times 3\times 2\times 1=120

Therefore, 5 is the minimum positive integer N such that N! is a multiple of 30. Thus, 5 should be printed.

Sample Input 2

123456789011

Sample Output 2

123456789011

Sample Input 3

280

Sample Output 3

7

Problem Statement

We have an empty sequence A. You will be given Q queries, which should be processed in the order they are given. Each query is of one of the three kinds below:

• 1 x : Append x to the end of A.
• 2 : Print the element at the beginning of A. Then, delete that element. It is guaranteed that A will not empty when this query is given.
• 3 : Sort A in ascending order.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• 0 \leq x \leq 10^9
• A will not be empty when a query 2 is given.
• All values in input are integers.

Sample Input 1

8
1 4
1 3
1 2
1 1
3
2
1 0
2

Sample Output 1

1
2

The i-th line below shows the contents of A after the i-th query is processed in Sample Input 1.

• (4)
• (4, 3)
• (4, 3, 2)
• (4, 3, 2, 1)
• (1, 2, 3, 4)
• (2, 3, 4)
• (2, 3, 4, 0)
• (3, 4, 0)

Sample Input 2

9
1 5
1 5
1 3
2
3
2
1 6
3
2

Sample Output 2

5
3
5

The i-th line below shows the contents of A after the i-th query is processed in Sample Input 2.

• (5)
• (5, 5)
• (5, 5, 3)
• (5, 3)
• (3, 5)
• (5)
• (5, 6)
• (5, 6)
• (6)

Problem Statement

Takahashi and Aoki have N and M bottles of sugar water, respectively.
Takahashi's i-th sugar water is composed of A_i grams of sugar and B_i grams of water.
Aoki's i-th sugar water is composed of C_i grams of sugar and D_i grams of water.
There are NM ways to choose one from Takahashi's sugar waters and one from Aoki's and mix them. Among the NM sugar waters that can be obtained in this way, find the concentration of sugar in the sugar water with the K-th highest concentration of sugar.
Here, the concentration of sugar in sugar water composed of x grams of sugar and y grams of water is \dfrac{100x}{x+y} percent. We will ignore saturation.

Constraints

• 1 \leq N, M \leq 5 \times 10^4
• 1 \leq K \leq N \times M
• 1 \leq A_i, B_i, C_i, D_i \leq 10^5
• All values in the input are integers.

Sample Input 1

3 1 1
1 2
4 1
1 4
1 4

Sample Output 1

50.000000000000000

Let (i, j) denote the sugar water obtained by mixing Takahashi's i-th sugar water and Aoki's j-th.
Below are the sugar waters that can be obtained and their concentrations of sugar.

• (1, 1) : 100 \times \frac{1 + 1}{(1 + 1) + (2 + 4)} = 25 \%
• (2, 1) : 100 \times \frac{1 + 4}{(4 + 1) + (1 + 4)} = 50 \%
• (3, 1) : 100 \times \frac{1 + 1}{(1 + 1) + (4 + 4)} = 20 \%

Among them, the sugar water with the highest concentration of sugar is (2, 1), with a concentration of 50 percent.

Sample Input 2

2 2 2
6 4
10 1
5 8
9 6

Sample Output 2

62.500000000000000

Sample Input 3

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

Sample Output 3

54.166666666666664