Problem Statement

You are given N strings S_1,S_2,\ldots,S_N in this order.

Print S_N,S_{N-1},\ldots,S_1 in this order.

Constraints

• 1\leq N \leq 10
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters, uppercase English letters, and digits.

Sample Input 1

3
Takahashi
Aoki
Snuke

Sample Output 1

Snuke
Aoki
Takahashi

We have N=3, S_1= Takahashi, S_2= Aoki, and S_3= Snuke.

Thus, you should print Snuke, Aoki, and Takahashi in this order.

Sample Input 2

4
2023
Year
New
Happy

Sample Output 2

Happy
New
Year
2023

The given strings may contain digits.

Problem Statement

You are given an integer X between 1 and 10, inclusive.

Output the string obtained by deleting only the X-th character from the string HelloWorld.

Constraints

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

Sample Input 1

5

Sample Output 1

HellWorld

Deleting the 5-th character of HelloWorld gives HellWorld. Thus, output HellWorld.

Sample Input 2

9

Sample Output 2

HelloWord

Sample Input 3

1

Sample Output 3

elloWorld

Problem Statement

We have 4 cards with an integer 1 written on it, 4 cards with 2, \ldots, 4 cards with N, for a total of 4N cards.

Takahashi shuffled these cards, removed one of them, and gave you a pile of the remaining 4N-1 cards. The i-th card (1 \leq i \leq 4N - 1) of the pile has an integer A_i written on it.

Find the integer written on the card removed by Takahashi.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
• For each k \, (1 \leq k \leq N), there are at most 4 indices i such that A_i = k.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

Takahashi removed a card with 3 written on it.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

2

Problem Statement

In a certain measurement, the sensor readings at times 0,1,\dots,T are recorded according to the following rules.

• At time 0, the reading is saved.
• At times 1,2,\dots,T, the reading is saved if and only if the absolute difference between the current reading and the most recently saved reading is at least X.

The sensor reading at time i=0,1,\dots,T was A_i.

Output the times at which readings were saved and the saved values, in ascending order of time.

Constraints

• 1 \le T \le 100
• 1 \le X \le 100
• 0 \le A_i \le 100
• All input values are integers.

Sample Input 1

6 10
30 35 40 21 30 12 31

Sample Output 1

0 30
2 40
3 21
6 31

The measurement proceeds as follows.

• The reading at time 0 is 30. Save it.
• The reading at time 1 is 35. The most recently saved reading is 30, and the absolute difference is less than 10, so it is not saved.
• The reading at time 2 is 40. The most recently saved reading is 30, and the absolute difference is at least 10, so it is saved.
• The reading at time 3 is 21. The most recently saved reading is 40, and the absolute difference is at least 10, so it is saved.
• The reading at time 4 is 30. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
• The reading at time 5 is 12. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
• The reading at time 6 is 31. The most recently saved reading is 21, and the absolute difference is at least 10, so it is saved.

Problem Statement

There are N gems. The color (represented as an integer) of the i-th gem is C_i and its value is V_i.

Choose K gems from these N gems. Here, the chosen gems must have at least M distinct colors.

Find the maximum possible total value of the chosen gems. (Such a choice is always possible in the given input.)

Constraints

• 1 \leq M \leq K \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq N
• 1 \leq V_i \leq 10^9
• There exist gems of at least M distinct colors.
• All input values are integers.

Sample Input 1

5 3 2
1 30
1 40
1 50
2 10
3 20

Sample Output 1

110

In this sample, choose three gems from five gems. The chosen gems must have at least two distinct colors.

Choosing gems 2, 3, 5 gives colors 1, 1, 3, which are two distinct colors. Their total value is 40 + 50 + 20 = 110, and this is the maximum possible value.

Sample Input 2

5 3 3
1 30
1 40
1 50
2 10
3 20

Sample Output 2

80

The gems and the number to choose are the same as in Sample Input 1, but the chosen gems must have at least three distinct colors.

Choosing gems 3, 4, 5 gives colors 1, 2, 3, which are three distinct colors. Their total value is 50 + 10 + 20 = 80, and this is the maximum possible value.

Sample Input 3

5 5 1
4 1000000000
5 1000000000
4 1000000000
5 1000000000
4 1000000000

Sample Output 3

5000000000

Beware of overflow.

Problem Statement

AtCoder Restaurant was open for N days after opening.

On day i (1\leq i\leq N) after opening, the following actions were performed.

• In the morning of day i, A_i eggs are purchased.
• At noon on day i, B_i eggs are used. Here, eggs in stock are used in the order they were purchased.
• In the evening of day i, all eggs that have been stocked for D or more days are discarded.

There were no eggs in stock before the morning of day 1, and eggs never ran out at noon on any day.

Find how many eggs remain in the restaurant after the evening action on day N.

T test cases are given; solve each.

Constraints

• 1 \leq T\leq 2\times 10^5
• 1 \leq D \leq N \leq 2\times 10^5
• 1 \leq A_i,B_i \leq 10
• Eggs never run out at noon on any of the N days.
• For each input, the sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

3
3 1
7 2 3
1 3 2
3 2
7 2 3
1 3 2
2 1
2 1
1 2

Sample Output 1

3
5
0

In the first test case, the following actions are performed.

• Initially, AtCoder Restaurant has no eggs.
• In the morning of day 1, 7 eggs are purchased. The restaurant has 7 eggs stocked on day 1.
• At noon on day 1, 1 egg is used. The restaurant has 6 eggs stocked on day 1 remaining.
• In the evening of day 1, no eggs are discarded. The restaurant has 6 eggs stocked on day 1 remaining.
• In the morning of day 2, 2 eggs are purchased. The restaurant has 6 eggs stocked on day 1 and 2 eggs stocked on day 2.
• At noon on day 2, 3 eggs are used. The restaurant has 3 eggs stocked on day 1 and 2 eggs stocked on day 2 remaining.
• In the evening of day 2, the eggs stocked on day 1 are discarded. The restaurant has 2 eggs stocked on day 2 remaining.
• In the morning of day 3, 3 eggs are purchased. The restaurant has 2 eggs stocked on day 2 and 3 eggs stocked on day 3.
• At noon on day 3, 2 eggs are used. The restaurant has 3 eggs stocked on day 3 remaining.
• In the evening of day 3, no eggs are discarded. (This is because all eggs stocked on day 2 have already been used.) The restaurant has 3 eggs stocked on day 3 remaining.

Thus, 3 eggs remain after the evening action on day 3, so output 3 on the first line.

For the second test case, remember to output the number of eggs after discarding the eggs stocked on day 1 in the evening of day 3.

Problem Statement

We have an undirected graph with (N_1+N_2) vertices and M edges. For i=1,2,\ldots,M, the i-th edge connects vertex a_i and vertex b_i.
The following properties are guaranteed:

• Vertex u and vertex v are connected, for all integers u and v with 1 \leq u,v \leq N_1.
• Vertex u and vertex v are connected, for all integers u and v with N_1+1 \leq u,v \leq N_1+N_2.
• Vertex 1 and vertex (N_1+N_2) are disconnected.

Consider performing the following operation exactly once:

• choose an integer u with 1 \leq u \leq N_1 and an integer v with N_1+1 \leq v \leq N_1+N_2, and add an edge connecting vertex u and vertex v.

We can show that vertex 1 and vertex (N_1+N_2) are always connected in the resulting graph; so let d be the minimum length (number of edges) of a path between vertex 1 and vertex (N_1+N_2).

Find the maximum possible d resulting from adding an appropriate edge to add.

Constraints

• 1 \leq N_1,N_2 \leq 1.5 \times 10^5
• 0 \leq M \leq 3 \times 10^5
• 1 \leq a_i \leq b_i \leq N_1+N_2
• (a_i,b_i) \neq (a_j,b_j) if i \neq j.
• Vertex u and vertex v are connected for all integers u and v such that 1 \leq u,v \leq N_1.
• Vertex u and vertex v are connected for all integers u and v such that N_1+1 \leq u,v \leq N_1+N_2.
• Vertex 1 and vertex (N_1+N_2) are disconnected.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

If we set u=2 and v=5, the operation yields d=5, which is the maximum possible.

Sample Input 2

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

Sample Output 2

4

Problem Statement

You are given a matrix A with H rows and W columns. The value of each of its elements is 0 or 1. For an integer pair (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, we denote by A_{i,j} the element at the i-th row and j-th column.

You can perform the following operation on the matrix A any number of times (possibly zero):

• Choose an integer i such that 1 \leq i \leq H. For every integer j such that 1 \leq j \leq W, replace the value of A_{i,j} with 1-A_{i,j}.

A_{i,j} is said to be isolated if and only if there is no adjacent element with the same value; in other words, if and only if none of the four integer pairs (x,y) = (i-1,j),(i+1,j),(i,j-1),(i,j+1) satisfies 1 \leq x \leq H, 1 \leq y \leq W, and A_{i,j} = A_{x,y}.

Determine if you can make the matrix A in such a state that no element is isolated by repeating the operation. If it is possible, find the minimum number of operations required to do so.

Constraints

• 2 \leq H,W \leq 1000
• A_{i,j} = 0 or A_{i,j} = 1
• All values in the input are integers.

Sample Input 1

3 3
1 1 0
1 0 1
1 0 0

Sample Output 1

1

An operation with i = 1 makes A = ((0,0,1),(1,0,1),(1,0,0)), where there is no longer an isolated element.

Sample Input 2

4 4
1 0 0 0
0 1 1 1
0 0 1 0
1 1 0 1

Sample Output 2

2

Sample Input 3

2 3
0 1 0
0 1 1

Sample Output 3

-1

Problem Statement

There are N scaffolds numbered from 1 to N arranged in a line. The height of scaffold i(1 \leq i \leq N) is H_i.

Takahashi decides to play a game of moving on the scaffolds. Initially, he freely chooses an integer i(1 \leq i \leq N) and gets on scaffold i.

When he is on scaffold i at some point, he can choose an integer j(1 \leq j \leq N) satisfying the following condition and move to scaffold j:

• H_j \leq H_i - D and 1 \leq |i-j| \leq R.

Find the maximum number of moves he can make when he repeats moving until he can no longer move.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq D,R \leq N
• H is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5 2 1
5 3 1 4 2

Sample Output 1

2

Takahashi initially gets on scaffold 1 and can move between the scaffolds as follows:

• First move: Since H_2 \leq H_1 -D and |2-1| \leq R, he can move to scaffold 2. Move from scaffold 1 to scaffold 2.
• Second move: Since H_3 \leq H_2 -D and |3-2| \leq R, he can move to scaffold 3. Move from scaffold 2 to scaffold 3.
• Since the height of scaffold 3 is 1, he can no longer move.

As shown above, he can move 2 times. Also, no matter how he chooses the scaffolds to move to, he cannot move 3 or more times. Therefore, output 2.

Sample Input 2

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

Sample Output 2

3