Problem Statement

On the xy-plane, there are N points with ID numbers from 1 to N. Point i is located at coordinates (X_i, Y_i), and no two points have the same coordinates.

From each point, find the farthest point and print its ID number. If multiple points are the farthest, print the smallest of the ID numbers of those points.

Here, we use the Euclidean distance: for two points (x_1,y_1) and (x_2,y_2), the distance between them is \sqrt{(x_1-x_2)^{2}+(y_1-y_2)^{2}}.

Constraints

• 2 \leq N \leq 100
• -1000 \leq X_i, Y_i \leq 1000
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All input values are integers.

Sample Input 1

4
0 0
2 4
5 0
3 4

Sample Output 1

3
3
1
1

The following figure shows the arrangement of the points. Here, P_i represents point i. The farthest point from point 1 are points 3 and 4, and point 3 has the smaller ID number.

The farthest point from point 2 is point 3.

The farthest point from point 3 are points 1 and 2, and point 1 has the smaller ID number.

The farthest point from point 4 is point 1.

Sample Input 2

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

Sample Output 2

6
6
6
6
6
4

Problem Statement

You are given a horizontally written text. Convert it to vertical writing, filling spaces with *.

You are given N strings S_1, S_2, \dots, S_N consisting of lowercase English letters. Let M be the maximum length of these strings.

Print M strings T_1, T_2, \dots, T_M that satisfy the following conditions:

• Each T_i consists of lowercase English letters and *.
• Each T_i does not end with *.
• For each 1 \leq i \leq N, the following holds:
  • For each 1 \leq j \leq |S_i|, the (N-i+1)-th character of T_j exists, and the concatenation of the (N-i+1)-th characters of T_1, T_2, \dots, T_{|S_i|} in this order equals S_i.
  • For each |S_i| + 1 \leq j \leq M, the (N-i+1)-th character of T_j either does not exist or is *.

Here, |S_i| denotes the length of the string S_i.

Constraints

• N is an integer between 1 and 100, inclusive.
• Each S_i is a string of lowercase English letters with length between 1 and 100, inclusive.

Sample Input 1

3
abc
de
fghi

Sample Output 1

fda
geb
h*c
i

Placing * as the 2nd character of T_3 puts the c in the correct position. On the other hand, placing * as the 2nd and 3rd characters of T_4 would make T_4 end with *, which violates the condition.

Sample Input 2

3
atcoder
beginner
contest

Sample Output 2

cba
oet
ngc
tio
end
sne
ter
*r

Problem Statement

You are playing a game.

There are N enemies lined up in a row, and the i-th enemy from the front has a health of H_i.

You will repeat the following action until the healths of all enemies become 0 or less, using a variable T initialized to 0.

• Increase T by 1. Then, attack the frontmost enemy with health 1 or more. If T is a multiple of 3, the enemy's health decreases by 3; otherwise, it decreases by 1.

Find the value of T when the healths of all enemies become 0 or less.

Constraints

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

Sample Input 1

3
6 2 2

Sample Output 1

8

The actions are performed as follows:

• T becomes 1. Attack the 1st enemy, and its health becomes 6-1=5.
• T becomes 2. Attack the 1st enemy, and its health becomes 5-1=4.
• T becomes 3. Attack the 1st enemy, and its health becomes 4-3=1.
• T becomes 4. Attack the 1st enemy, and its health becomes 1-1=0.
• T becomes 5. Attack the 2nd enemy, and its health becomes 2-1=1.
• T becomes 6. Attack the 2nd enemy, and its health becomes 1-3=-2.
• T becomes 7. Attack the 3rd enemy, and its health becomes 2-1=1.
• T becomes 8. Attack the 3rd enemy, and its health becomes 1-1=0.

Sample Input 2

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

Sample Output 2

82304529

Sample Input 3

5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

Beware of integer overflow.

Problem Statement

There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:

• M \geq 2
• The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
• The edge from vertex B_M to vertex B_1 exists.
• If i \neq j, then B_i \neq B_j.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le N
• A_i \neq i

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.

Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input:

Problem Statement

For real numbers L and R, let us denote by [L,R) the set of real numbers greater than or equal to L and less than R. Such a set is called a right half-open interval.

You are given N right half-open intervals [L_i,R_i). Let S be their union. Represent S as a union of the minimum number of right half-open intervals.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq L_i \lt R_i \leq 2\times 10^5
• All values in input are integers.

Sample Input 1

3
10 20
20 30
40 50

Sample Output 1

10 30
40 50

The union of the three right half-open intervals [10,20),[20,30),[40,50) equals the union of two right half-open intervals [10,30),[40,50).

Sample Input 2

3
10 40
30 60
20 50

Sample Output 2

10 60

The union of the three right half-open intervals [10,40),[30,60),[20,50) equals the union of one right half-open interval [10,60).