Problem Statement

You are given positive integers X,Y,Z.

Takahashi and Aoki are currently X years old and Y years old, respectively.

Takahashi and Aoki age by 1 year simultaneously on every January 1st.

Determine whether there is a moment in the future (including this year) when Takahashi's age becomes exactly Z times Aoki's age.

Constraints

• 1\le X,Y \le 100
• 2\le Z\le 10
• All input values are integers.

Sample Input 1

44 20 2

Sample Output 1

Yes

Four years from now, Takahashi will be 48 years old and Aoki will be 24 years old, so Takahashi's age will be exactly twice Aoki's age. Thus, output Yes.

Sample Input 2

28 10 3

Sample Output 2

No

There will never be a moment when Takahashi's age becomes exactly three times Aoki's age. Thus, output No.

Sample Input 3

50 5 10

Sample Output 3

Yes

Currently, Takahashi's age is exactly 10 times Aoki's age.

Note that you need to determine whether there will be such a moment in the future including this year.

Sample Input 4

1 100 2

Sample Output 4

No

Problem Statement

There is a train consisting of N cars. What is the position, counted from the back, of the car that is K-th from the front of this train?

Constraints

• 1 \leq K \leq N \leq 100
• All input values are integers.

Sample Input 1

5 2

Sample Output 1

4

For a train consisting of five cars, the car that is second from the front is fourth from the back.

Sample Input 2

1 1

Sample Output 2

1

Sample Input 3

99 50

Sample Output 3

50

Problem Statement

Among the 81 integers that appear in the 9-by-9 multiplication table, find the sum of those that are not X.

There is a grid of size 9 by 9.
Each cell of the grid contains an integer: the cell at the i-th row from the top and the j-th column from the left contains i \times j.
You are given an integer X. Among the 81 integers written in this grid, find the sum of those that are not X. If the same value appears in multiple cells, add it for each cell.

Constraints

• X is an integer between 1 and 81, inclusive.

Sample Input 1

1

Sample Output 1

2024

The only cell with 1 in the grid is the cell at the 1st row from the top and 1st column from the left. Summing all integers that are not 1 yields 2024.

Sample Input 2

11

Sample Output 2

2025

There is no cell containing 11 in the grid. Thus, the answer is 2025, the sum of all 81 integers.

Sample Input 3

24

Sample Output 3

1929

Problem Statement

You are given an H-by-W matrix A.
The element at the i-th row from the top and j-th column from the left of A is A_{i,j}.

Let B be a W-by-H matrix whose element at the i-th row from the top and j-th column from the left equals A_{j, i}.
That is, B is the transpose of A.

Print B.

Constraints

• 1\leq H,W \leq 10^5
• H \times W \leq 10^5
• 1 \leq A_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

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

For example, we have A_{2,1}=4, so the element at the 1-st row from the top and 2-nd column from the left of the transpose B is 4.

Sample Input 2

2 2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

1000000000 1000000000
1000000000 1000000000

Problem Statement

You are given a string S of length N. You are also given Q queries, which you should process in order.

The i-th query is as follows:

• Given an integer X_i and a character C_i, replace the X_i-th character of S with C_i. Then, print the number of times the string ABC appears as a substring in S.

Here, a substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab is a substring of abc, but ac is not a substring of abc.

Constraints

• 3 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• S is a string of length N consisting of uppercase English letters.
• 1 \le X_i \le N
• C_i is an uppercase English letter.

Sample Input 1

7 4
ABCDABC
4 B
3 A
5 C
4 G

Sample Output 1

2
1
1
0

After processing each query, S becomes as follows.

• After the first query: S= ABCBABC. In this string, ABC appears twice as a substring.
• After the second query: S= ABABABC. In this string, ABC appears once as a substring.
• After the third query: S= ABABCBC. In this string, ABC appears once as a substring.
• After the fourth query: S= ABAGCBC. In this string, ABC appears zero times as a substring.

Sample Input 2

3 3
ABC
1 A
2 B
3 C

Sample Output 2

1
1
1

There are cases where S does not change through processing a query.

Sample Input 3

15 10
BBCCBCACCBACACA
9 C
11 B
5 B
11 B
4 A
8 C
8 B
5 B
7 B
14 B

Sample Output 3

0
0
0
0
1
1
2
2
1
1

Problem Statement

You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).
For q=1,2,\dots,Q in this order, perform the following operation.

• Remove the element with value a_q from P, and append it to the end of P.

Find the value of each element of P after performing the Q operations.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• (P_1,P_2,\dots,P_N) is a permutation of (1,2,\dots,N).
• 1 \leq a_q \leq N
• All input values are integers.

Sample Input 1

4 2
2 4 3 1
3
2

Sample Output 1

4 1 3 2

Initially, P=(2,4,3,1).
After the first operation, P=(2,4,1,3).
After the second operation, P=(4,1,3,2).

Sample Input 2

3 3
1 2 3
1
1
1

Sample Output 2

2 3 1

Sample Input 3

2 5
2 1
1
1
2
2
1

Sample Output 3

2 1

Problem Statement

There are N dice. The i-th die has K_i faces, with the numbers A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} written on them. When you roll this die, each face appears with probability \frac{1}{K_i}.

You choose two dice from the N dice and roll them. Determine the maximum probability that the two dice show the same number, when the dice are chosen optimally.

Constraints

• 2 \leq N \leq 100
• 1 \leq K_i
• K_1 + K_2 + \dots + K_N \leq 10^5
• 1 \leq A_{i,j} \leq 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

0.333333333333333

• When choosing the 1st and 2nd dice, the probability that the outcomes are the same is \frac{1}{3}.
• When choosing the 1st and 3rd dice, the probability is \frac{1}{6}.
• When choosing the 2nd and 3rd dice, the probability is \frac{1}{6}.

Therefore, the maximum probability is \frac{1}{3} = 0.3333333333\ldots.

Sample Input 2

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

Sample Output 2

0.666666666666667

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 is a town represented as an xy-plane, where Santa lives, along with N children numbered 1 to N. Santa's house is at coordinates (S_X,S_Y), and the house of child i\ (1\leq i\leq N) is at (X_i,Y_i).

Santa wants to deliver one present to each of the N children in numerical order. To deliver a present to child i, Santa must visit the house of child i with at least one present in hand. However, Santa can only carry up to K presents at a time, and he must return to his own house to replenish presents (there are enough presents at Santa's house).

Find the minimum distance Santa must travel to leave his house, deliver presents to all N children, and return to his house.

Constraints

• 1\leq K\leq N \leq 2\times 10^5
• -10^9\leq S_X,S_Y,X_i,Y_i \leq 10^9
• (S_X,S_Y)\neq (X_i,Y_i)
• (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
• All input values are integers.

Sample Input 1

3 2
1 1
3 1
1 2
3 2

Sample Output 1

9.236067977499790

In the figure above, the red circle represents Santa's house, and the circles with numbers represent the houses of the children with those numbers.

Consider Santa acting as follows:

1. Leave his house with two presents.
2. Go to child 1's house and deliver a present.
3. Return to his house and replenish one present.
4. Go to child 2's house and deliver a present.
5. Go to child 3's house and deliver a present.
6. Return to his house.

In this case, Santa travels the distance of 2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots, which is the minimum.

Sample Input 2

2 1
0 1
-1 1
1 1

Sample Output 2

4.000000000000000

Sample Input 3

8 3
735867677 193944314
586260100 -192321079
95834122 802780784
418379342 -790013317
-445130206 189801569
-354684803 -49687658
-204491568 -840249197
853829789 470958158
-751917965 762048217

Sample Output 3

11347715738.116592407226562