Problem Statement

You are given an integer sequence A of length N and integers K and X.
Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A.

Constraints

• All input values are integers.
• 1 \le K \le N \le 100
• 1 \le A_i, X \le 100

Sample Input 1

4 3 7
2 3 5 11

Sample Output 1

2 3 5 7 11

For K=3, X=7, and A=(2,3,5,11), we get B=(2,3,5,7,11).

Sample Input 2

1 1 100
100

Sample Output 2

100 100

Sample Input 3

8 8 3
9 9 8 2 4 4 3 5

Sample Output 3

9 9 8 2 4 4 3 5 3

Problem Statement

Given integers A and B, find A+B.
This is a N-choice problem; the i-th choice is C_i.
Print the index of the correct choice.

Constraints

• All values in the input are integers.
• 1 \le N \le 300
• 1 \le A,B \le 1000
• 1 \le C_i \le 2000
• C_i are pairwise distinct. In other words, no two choices have the same value.
• There is exactly one i such that A+B=C_i. In other words, there is always a unique correct choice.

Sample Input 1

3 125 175
200 300 400

Sample Output 1

2

We have 125+175 = 300.
The first, second, and third choices are 200, 300, and 400, respectively.
Thus, the 2-nd choice is correct, so 2 should be printed.

Sample Input 2

1 1 1
2

Sample Output 2

1

The problem may be a one-choice problem.

Sample Input 3

5 123 456
135 246 357 468 579

Sample Output 3

5

Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

• -1000 \leq X,Y,Z \leq 1000
• X, Y, and Z are distinct, and none of them is 0.
• All values in the input are integers.

Sample Input 1

10 -10 1

Sample Output 1

10

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

40

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Define the number of occurrences of a string t of length K as the number of integers i that satisfy the following condition:

• 1 \leq i \leq N-K+1
• The substring of S from the i-th character to the (i+K-1)-th character matches t.

Find the maximum value x of the number of occurrences of a string of length K. Also, output all strings of length K with x occurrences in ascending lexicographical order.

Constraints

• N, K are integers.
• S is a string of length N consisting of lowercase English letters.
• 1 \leq K \leq N \leq 100

Sample Input 1

9 3
ovowowovo

Sample Output 1

2
ovo owo

The following strings have two occurrences:

• For the string ovo, i=1,7 satisfy the condition, so the number of occurrences of ovo is 2.
• For the string owo, i=3,5 satisfy the condition, so the number of occurrences of owo is 2.

There is no string of length 3 with more than two occurrences, so the maximum value is 2.

On the other hand, the following are examples of strings with fewer than two occurrences:

• For the string vow, i=2 satisfies the condition, so the number of occurrences of vow is 1.
• For the string ooo, there is no i that satisfies the condition, so the number of occurrences of ooo is 0.

Sample Input 2

9 1
ovowowovo

Sample Output 2

5
o

Sample Input 3

35 3
thequickbrownfoxjumpsoverthelazydog

Sample Output 3

2
the

Problem Statement

There is a grid of N^2 squares with N rows and N columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq N) and j-th column from the left (1\leq j\leq N).

Each square is either empty or has a piece placed on it. There are M pieces placed on the grid, and the k-th (1\leq k\leq M) piece is placed on square (a_k,b_k).

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy any of the following conditions:

• Placed on square (i+2,j+1)
• Placed on square (i+1,j+2)
• Placed on square (i-1,j+2)
• Placed on square (i-2,j+1)
• Placed on square (i-2,j-1)
• Placed on square (i-1,j-2)
• Placed on square (i+1,j-2)
• Placed on square (i+2,j-1)

Here, conditions involving non-existent squares are considered to never be satisfied.

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• 1\leq N\leq10^9
• 1\leq M\leq2\times10^5
• 1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)
• (a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

38

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece on the remaining 38 squares.

Sample Input 2

1000000000 1
1 1

Sample Output 2

999999999999999997

Out of 10^{18} squares, only 3 squares cannot be used: squares (1,1), (2,3), and (3,2).

Note that the answer may be 2^{32} or greater.

Sample Input 3

20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15

Sample Output 3

338

Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

• Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_i \leq N
• All values in input are integers.

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

• Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
• Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
• Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9

Problem Statement

There is an N \times N grid. Takahashi wants to color each cell black or white so that all of the following conditions are satisfied:

• For every row, the following condition holds:
• There exists an integer i\ (0\leq i\leq N) such that the leftmost i cells are colored black, and the rest are colored white.
• For every column, the following condition holds:
• There exists an integer i\ (0\leq i\leq N) such that the topmost i cells are colored black, and the rest are colored white.

Out of these N^2 cells, M of them have already been colored. Among them, the i-th one is at the X_i-th row from the top and the Y_i-th column from the left, and it is colored black if C_i is B and white if C_i is W.

Determine whether he can color the remaining uncolored N^2 - M cells so that all the conditions are satisfied.

Constraints

• 1\leq N\leq 10^9
• 1\leq M\leq \min(N^2,2\times 10^5)
• 1\leq X_i,Y_i\leq N
• (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
• C_i is B or W.
• All input numbers are integers.

Sample Input 1

4 3
4 1 B
3 2 W
1 3 B

Sample Output 1

Yes

For example, one can color the grid as in the following figure to satisfy the conditions. The cells already colored are surrounded by red borders.

Sample Input 2

2 2
1 2 W
2 2 B

Sample Output 2

No

No matter how the remaining two cells are colored, the conditions cannot be satisfied.

Sample Input 3

1 1
1 1 W

Sample Output 3

Yes

Sample Input 4

2289 10
1700 1083 W
528 967 B
1789 211 W
518 1708 W
1036 779 B
136 657 B
759 1497 B
902 1309 B
1814 712 B
936 763 B

Sample Output 4

No

Problem Statement

There are N islands and M bidirectional bridges connecting two islands. The islands and bridges are numbered 1, 2, \ldots, N and 1, 2, \ldots, M, respectively.
Bridge i connects islands U_i and V_i, and the time it takes to cross it in either direction is T_i.
No bridge connects an island to itself, but it is possible for two islands to be directly connected by more than one bridge.
One can travel between any two islands using some bridges.

You are given Q queries, so answer each of them. The i-th query is as follows:

You are given K_i distinct bridges: bridges B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}.
Find the minimum time required to travel from island 1 to island N using each of these bridges at least once.
Only consider the time spent crossing bridges.
You can cross the given bridges in any order and in any direction.

Constraints

• 2 \leq N \leq 400
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq U_i < V_i \leq N
• 1 \leq T_i \leq 10^9
• 1 \leq Q \leq 3000
• 1 \leq K_i \leq 5
• 1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M
• All input values are integers.
• It is possible to travel between any two islands using some bridges.

Sample Input 1

3 5
1 2 10
1 3 20
1 3 30
2 3 15
2 3 25
2
1
1
2
3 5

Sample Output 1

25
70

For the first query, we need to find the minimum time to travel from island 1 to island 3 while using bridge 1. The minimum time is achieved by using bridge 1 to move from island 1 to island 2, then using bridge 4 to move from island 2 to island 3. The time taken is 10 + 15 = 25. Hence, print 25 on the first line.

For the second query, we need to find the minimum time to travel from island 1 to island 3 while using both bridges 3 and 5. The minimum time is achieved by using bridge 3 to move from island 1 to island 3, then using bridge 5 to move to island 2, and finally using bridge 4 to return to island 3. The time taken is 30 + 25 + 15 = 70. Hence, print 70 on the second line.

Sample Input 2

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

Sample Output 2

5
3

For each query, you can cross the specified bridges in either direction.

Sample Input 3

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

Sample Output 3

4000000000

Beware that the answer may not fit in a 32-bit integer.

Problem Statement

You will play a game against a dealer. The game uses a D-sided die (dice) that shows an integer from 1 to D with equal probability, and two variables x and y initialized to 0. The game proceeds as follows:

• You may perform the following operation any number of times: roll the die and add the result to x. You can choose whether to continue rolling or not after each roll.

• Then, the dealer will repeat the following operation as long as y < L: roll the die and add the result to y.

• If x > N, you lose. Otherwise, you win if y > N or x > y and lose if neither is satisfied.

Determine the probability of your winning when you act in a way that maximizes the probability of winning.

Constraints

• All inputs are integers.
• 1 \leq L \leq N \leq 2 \times 10^5
• 1 \leq D \leq N

Sample Input 1

3 2 2

Sample Output 1

0.468750000000000

It can be proved that the optimal strategy is to continue rolling as long as x is not greater than 2.

Sample Input 2

200000 200000 200000

Sample Output 2

0.999986408692793