Problem Statement

Let us assume that water pressure depends only on depth and is \dfrac{x}{100} megapascal at a depth of x meters.

What is the water pressure in megapascals at a depth of D meters?

Constraints

• 1 \leq D \leq 10000
• D is an integer.

Sample Input 1

1000

Sample Output 1

10

The water pressure at a depth of 1000 meters is 10 megapascal. Outputs such as 10.0 and 9.999999 would also be accepted.

Sample Input 2

50

Sample Output 2

0.5

Sample Input 3

3141

Sample Output 3

31.41

Problem Statement

You are given N strings W_1,W_2,\dots,W_N consisting of lowercase English letters.
If one or more of these strings equal and, not, that, the, or you, then print Yes; otherwise, print No.

Constraints

• N is an integer between 1 and 100, inclusive.
• 1 \le |W_i| \le 50 (|W_i| is the length of W_i.)
• W_i consists of lowercase English letters.

Sample Input 1

10
in that case you should print yes and not no

Sample Output 1

Yes

We have, for instance, W_4= you, so you should print Yes.

Sample Input 2

10
in diesem fall sollten sie no und nicht yes ausgeben

Sample Output 2

No

None of the strings W_i equals any of and, not, that, the, and you.

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_1, A_2, \dots, A_N are all different.
• B_1, B_2, \dots, B_N are all different.
• All values in input are integers.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

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

Sample Output 3

3
2

Problem Statement

N players numbered 1 to N will play a soccer game.
When a player commits an offense, that player will receive a yellow card or a red card.
A player who satisfies one of the following conditions will be removed from the game.

• Accumulates two yellow cards.
• Receives a red card.

Once a player is removed, that player will no longer receive any cards.

You will watch this game. Initially, the players have not received any cards.
There will be Q events. Correctly answer the questions asked in the events.
There are three kinds of events, which are given in the format c x from the input, where c is 1, 2, or 3. The events are as follows.

• 1 x: Player x receives a yellow card.
• 2 x: Player x receives a red card.
• 3 x: You are asked whether player x has been removed from the game. Answer Yes or No.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \leq 100
• 1 \leq x \leq N in all events.
• There is at least one event of the third kind.
• A player who has been removed will no longer receive any cards.
• All values in the input are integers.

Sample Input 1

3 9
3 1
3 2
1 2
2 1
3 1
3 2
1 2
3 2
3 3

Sample Output 1

No
No
Yes
No
Yes
No

Here are all the events in chronological order.

In the 1-st event, you are asked whether player 1 has been removed from the game. Player 1 has not been removed, so you should print No.
In the 2-nd event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 3-rd event, player 2 receives a yellow card.
In the 4-th event, player 1 receives a red card and is removed from the game.
In the 5-th event, you are asked whether player 1 has been removed from the game. Player 1 has been removed, so you should print Yes.
In the 6-th event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No.
In the 7-th event, player 2 receives a yellow card and is removed from the game.
In the 8-th event, you are asked whether player 2 has been removed from the game. Player 2 has been removed, so you should print Yes.
In the 9-th event, you are asked whether player 3 has been removed from the game. Player 3 has not been removed, so you should print No.

Problem Statement

We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.

When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.

At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq T \leq 10^{18}
• 1 \leq A_i \leq 10^9
• The playlist does not change songs at exactly T seconds after it starts playing.
• All values in the input are integers.

Sample Input 1

3 600
180 240 120

Sample Output 1

1 60

When the playlist is played, the following happens. (Assume that it starts playing at time 0.)

• From time 0 to time 180, song 1 plays.
• From time 180 to time 420, song 2 plays.
• From time 420 to time 540, song 3 plays.
• From time 540 to time 720, song 1 plays.
• From time 720 to time 960, song 2 plays.
• \qquad\vdots

At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.

Sample Input 2

3 281
94 94 94

Sample Output 2

3 93

Sample Input 3

10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

6 678912340

Problem Statement

You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.

• For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
• For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.

You may perform the following operations on the matrix A any number of (possibly 0) times in any order:

• Choose an arbitrary row of A and remove it.
• Choose an arbitrary column of A and remove it.

Determine if it is possible to make the matrix A equal the matrix B.

Constraints

• 1 \leq H_2 \leq H_1 \leq 10
• 1 \leq W_2 \leq W_1 \leq 10
• 1 \leq A_{i, j} \leq 10^9
• 1 \leq B_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

Sample Output 1

Yes

Removing the 2-nd column from the initial A results in:

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

Then, removing the 3-rd row from A results in:

1 3 4 5
6 8 9 10
16 18 19 20

Then, removing the 1-st row from A results in:

6 8 9 10
16 18 19 20

Then, removing the 4-th column from A results in:

6 8 9
16 18 19

Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.

Sample Input 2

3 3
1 1 1
1 1 1
1 1 1
1 1
2

Sample Output 2

No

Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B, so No should be printed.

Problem Statement

Takahashi has decided to give one gift to Aoki and one gift to Snuke.
There are N candidates of gifts for Aoki, and their values are A_1, A_2, \ldots,A_N.
There are M candidates of gifts for Snuke, and their values are B_1, B_2, \ldots,B_M.

Takahashi wants to choose gifts so that the difference in values of the two gifts is at most D.

Determine if he can choose such a pair of gifts. If he can, print the maximum sum of values of the chosen gifts.

Constraints

• 1\leq N,M\leq 2\times 10^5
• 1\leq A_i,B_i\leq 10^{18}
• 0\leq D \leq 10^{18}
• All values in the input are integers.

Sample Input 1

2 3 2
3 10
2 5 15

Sample Output 1

8

The difference of values of the two gifts should be at most 2.
If he gives a gift with value 3 to Aoki and another with value 5 to Snuke, the condition is satisfied, achieving the maximum possible sum of values.
Thus, 3+5=8 should be printed.

Sample Input 2

3 3 0
1 3 3
6 2 7

Sample Output 2

-1

He cannot choose gifts to satisfy the condition. Note that the candidates of gifts for a person may contain multiple gifts with the same value.

Sample Input 3

1 1 1000000000000000000
1000000000000000000
1000000000000000000

Sample Output 3

2000000000000000000

Note that the answer may not fit into a 32-bit integer type.

Sample Input 4

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

Sample Output 4

14

Problem Statement

Given integers A, X, and M, find \displaystyle \sum_{i = 0}^{X-1} A^i, modulo M.

Constraints

• 1 \leq A, M \leq 10^9
• 1 \leq X \leq 10^{12}
• All values in the input are integers.

Sample Input 1

3 4 7

Sample Output 1

5

3^0 + 3^1 + 3^2 + 3^3 = 40, which equals 5 modulo 7, so 5 should be printed.

Sample Input 2

8 10 9

Sample Output 2

0

Sample Input 3

1000000000 1000000000000 998244353

Sample Output 3

919667211

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N consisting of digits from 1 through 9 and the character X.

We will choose a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) to construct a string T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}, where + denotes a concatenation of strings.

Then, we will calculate the "score" of the string T = T_1T_2\ldots T_{|T|} (where |T| denotes the length of T).
The score is calculated by the following 9 steps, starting from the initial score 0:

• Add 1 point to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 1.
• Add 2 points to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 2.
• Add 3 points to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 3.
• \cdots
• Add 9 points to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 9.

Find the maximum possible score of T when P can be chosen arbitrarily.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N is an integer.
• S_i is a string of length at least 1 consisting of digits from 1 through 9 and the character X.
• The sum of lengths of S_1, S_2, \ldots, S_N is at most 2 \times 10^5.

Sample Input 1

3
1X3
59
XXX

Sample Output 1

71

When P = (3, 1, 2), we have T = S_3 + S_1 + S_2 = XXX1X359. Then, the score of T is calculated as follows:

• there are 3 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 1;
• there are 4 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 3;
• there are 4 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 5;
• there are 4 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 9.

Therefore, the score of T is 1 \times 3 + 3 \times 4 + 5 \times 4 + 9 \times 4 = 71, which is the maximum possible value.

Sample Input 2

10
X63X395XX
X2XX3X22X
13
3716XXX6
45X
X6XX
9238
281X92
1XX4X4XX6
54X9X711X1

Sample Output 2

3010