Problem Statement

You are given a string S consisting of lowercase English characters. The length of S is between 1 and 3, inclusive.

Print the string of length 6 that is a repetition of S.

It can be shown that there uniquely exists such a string under the Constraints of this problem.

Constraints

• S is a string consisting of lowercase English characters of length between 1 and 3, inclusive.

Sample Input 1

abc

Sample Output 1

abcabc

These are strings that are repetitions of S = abc: abc, abcabc, abcabcabc, abcabcabcabc, and so on. Among them, abcabc has the length of 6, so abcabc should be printed.

Sample Input 2

zz

Sample Output 2

zzzzzz

Problem Statement

There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:

• We can choose at most 3 different weights so that they have a total mass of n.

How many positive integers less than or equal to W are good integers?

Constraints

• 1 \leq N \leq 300
• 1 \leq W \leq 10^6
• 1 \leq A_i \leq 10^6
• All values in input are integers.

Sample Input 1

2 10
1 3

Sample Output 1

3

If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.

Sample Input 2

2 1
2 3

Sample Output 2

0

There are no good integers less than or equal to W.

Sample Input 3

4 12
3 3 3 3

Sample Output 3

3

There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.

Sample Input 4

7 251
202 20 5 1 4 2 100

Sample Output 4

48

Problem Statement

Poem Online Judge (POJ) is an online judge that gives scores to submitted strings.
There were N submissions to POJ. In the i-th earliest submission, string S_i was submitted, and a score of T_i was given. (The same string may have been submitted multiple times.)
Note that POJ may not necessarily give the same score to submissions with the same string.

A submission is said to be an original submission if the string in the submission is never submitted in any earlier submission.
A submission is said to be the best submission if it is an original submission with the highest score. If there are multiple such submissions, only the earliest one is considered the best submission.

Find the index of the best submission.

Constraints

• 1 \leq N \leq 10^5
• S_i is a string consisting of lowercase English characters.
• S_i has a length between 1 and 10, inclusive.
• 0 \leq T_i \leq 10^9
• N and T_i are integers.

Sample Input 1

3
aaa 10
bbb 20
aaa 30

Sample Output 1

2

We will refer to the i-th earliest submission as Submission i.
Original submissions are Submissions 1 and 2. Submission 3 is not original because it has the same string as that in Submission 1.
Among the original submissions, Submission 2 has the highest score. Therefore, this is the best submission.

Sample Input 2

5
aaa 9
bbb 10
ccc 10
ddd 10
bbb 11

Sample Output 2

2

Original submissions are Submissions 1, 2, 3, and 4.
Among them, Submissions 2, 3, and 4 have the highest scores. In this case, the earliest submission among them, Submission 2, is the best.
As in this sample, beware that if multiple original submissions have the highest scores, only the one with the earliest among them is considered the best submission.

Sample Input 3

10
bb 3
ba 1
aa 4
bb 1
ba 5
aa 9
aa 2
ab 6
bb 5
ab 3

Sample Output 3

8

Problem Statement

You are given an integer W.
You are going to prepare some weights so that all of the conditions below are satisfied.

• The number of weights is between 1 and 300, inclusive.
• Each weight has a mass of positive integer not exceeding 10^6.
• Every integer between 1 and W, inclusive, is a good integer. Here, a positive integer n is said to be a good integer if the following condition is satisfied:
  • We can choose at most 3 different weights from the prepared weights with a total mass of n.

Print a combination of weights that satisfies the conditions.

Constraints

• 1 \leq W \leq 10^6
• W is an integer.

Sample Input 1

6

Sample Output 1

3
1 2 3

In the output above, 3 weights with masses 1, 2, and 3 are prepared.
This output satisfies the conditions. Especially, regarding the 3-rd condition, we can confirm that every integer between 1 and W, inclusive, is a good integer.

• If we choose only the 1-st weight, it has a total mass of 1.
• If we choose only the 2-nd weight, it has a total mass of 2.
• If we choose only the 3-rd weight, it has a total mass of 3.
• If we choose the 1-st and the 3-rd weights, they have a total mass of 4.
• If we choose the 2-nd and the 3-rd weights, they have a total mass of 5.
• If we choose the 1-st, the 2-nd, and the 3-rd weights, they have a total mass of 6.

Sample Input 2

12

Sample Output 2

6
2 5 1 2 5 1

You may prepare multiple weights with the same mass.

Problem Statement

Takahashi is with N animals. The N animals are called Animal 1, Animal 2, \ldots, Animal N.

Takahashi will perform the following N kinds of action. Each action can be performed any number of (possibly zero) times.

• Pay A_1 yen (the currency in Japan) to feed Animals 1 and 2.
• Pay A_2 yen to feed Animals 2 and 3.
• Pay A_3 yen to feed Animals 3 and 4.
• \cdots
• Pay A_i yen to feed Animals i and (i+1).
• \cdots
• Pay A_{N-2} yen to feed Animals (N-2) and (N-1).
• Pay A_{N-1} yen to feed Animals (N-1) and N.
• Pay A_N yen to feed Animals N and 1.

Note that the N-th action above feeds "Animals N and 1."

Print the minimum possible total cost to feed every animal at least once.

Constraints

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

Sample Input 1

5
2 5 3 2 5

Sample Output 1

7

If Takahashi performs the 1-st, 3-rd, and 4-th actions once each, Animals 1, 2, 3, 4, and 5 are fed once, once, once, twice, once, respectively, so every animal is fed at least once. The total cost to do so is A_1 + A_3 + A_4 = 2 + 3 + 2 = 7 yen, which is the minimum possible.

Sample Input 2

20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62

Sample Output 2

426

Problem Statement

You are given an undirected graph G with N vertices and M edges. G is simple (it has no self-loops and multiple edges) and connected.

For i = 1, 2, \ldots, M, the i-th edge is an undirected edge \lbrace u_i, v_i \rbrace connecting Vertices u_i and v_i.

Construct two spanning trees T_1 and T_2 of G that satisfy both of the two conditions below. (T_1 and T_2 do not necessarily have to be different spanning trees.)

• T_1 satisfies the following.

  If we regard T_1 as a rooted tree rooted at Vertex 1, for any edge \lbrace u, v \rbrace of G not contained in T_1, one of u and v is an ancestor of the other in T_1.

• T_2 satisfies the following.

  If we regard T_2 as a rooted tree rooted at Vertex 1, there is no edge \lbrace u, v \rbrace of G not contained in T_2 such that one of u and v is an ancestor of the other in T_2.

We can show that there always exists T_1 and T_2 that satisfy the conditions above.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace
• 1 \leq u_i, v_i \leq N
• All values in input are integers.
• The given graph is simple and connected.

Sample Input 1

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

Sample Output 1

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

In the Sample Output above, T_1 is a spanning tree of G containing 5 edges \lbrace 1, 4 \rbrace, \lbrace 4, 3 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 4, 2 \rbrace, \lbrace 6, 2 \rbrace. This T_1 satisfies the condition in the Problem Statement. Indeed, for each edge of G not contained in T_1:

• for edge \lbrace 5, 1 \rbrace, Vertex 1 is an ancestor of 5;
• for edge \lbrace 1, 2 \rbrace, Vertex 1 is an ancestor of 2;
• for edge \lbrace 1, 6 \rbrace, Vertex 1 is an ancestor of 6.

T_2 is another spanning tree of G containing 5 edges \lbrace 1, 5 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 1, 4 \rbrace, \lbrace 2, 1 \rbrace, \lbrace 1, 6 \rbrace. This T_2 satisfies the condition in the Problem Statement. Indeed, for each edge of G not contained in T_2:

• for edge \lbrace 4, 3 \rbrace, Vertex 4 is not an ancestor of Vertex 3, and vice versa;
• for edge \lbrace 2, 6 \rbrace, Vertex 2 is not an ancestor of Vertex 6, and vice versa;
• for edge \lbrace 4, 2 \rbrace, Vertex 4 is not an ancestor of Vertex 2, and vice versa.

Sample Input 2

4 3
3 1
1 2
1 4

Sample Output 2

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

Tree T, containing 3 edges \lbrace 1, 2\rbrace, \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace, is the only spanning tree of G. Since there are no edges of G that are not contained in T, obviously this T satisfies the conditions for both T_1 and T_2.

Problem Statement

The vertices of a convex N-gon P in an xy-plane are given as (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) in the counterclockwise order. (Here, the positive direction of the x-axis is right, and the positive direction of the y-axis is up.)

Based on this polygon P, we consider M convex N-gons P_1, P_2, \ldots, P_M.
For i = 1, 2, \ldots, M, the polygon P_i is obtained by shifting P in the positive direction of the x-axis by u_i and in the positive direction of the y-axis by v_i. In other words, P_i is a convex N-gon whose vertices are (x_1+u_i, y_1+v_i), (x_2+u_i, y_2+v_i), \ldots, (x_N+u_i, y_N+v_i).

For each of Q points (a_1, b_1), (a_2, b_2), \ldots, (a_Q, b_Q), determine if "the point is contained in all of the M polygons P_1, P_2, \ldots, P_M."

Here, we regard a point is also contained in a polygon if the point is on the polygon's boundary.

Constraints

• 3 \leq N \leq 50
• 1 \leq M \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• -10^8 \leq x_i, y_i \leq 10^8
• -10^8 \leq u_i, v_i \leq 10^8
• -10^8 \leq a_i, b_i \leq 10^8
• All values in input are integers.
• (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) forms a convex N-gon in the counterclockwise order.
• Each interior angle of the polygon P is less than 180 degrees.

Sample Input 1

5
-2 -3
0 -2
1 0
0 2
-2 1
2
0 1
1 0
6
0 0
1 0
0 1
1 1
-1 -1
-1 -2

Sample Output 1

Yes
No
Yes
Yes
Yes
No

Polygon P is a pentagon (5-gon) whose vertices are (-2, -3), (0, -2), (1, 0), (0, 2), (-2, 1).

• Polygon P_1 is a pentagon (5-gon) obtained by shifting P in the positive direction of the x-axis by 0 and in the positive direction of the y-axis by 1, so its vertices are (-2, -2), (0, -1), (1, 1), (0, 3), (-2, 2).
• Polygon P_2 is a pentagon (5-gon) obtained by shifting P in the positive direction of the x-axis by 1 and in the positive direction of the y-axis by 0, so its vertices are (-1, -3), (1, -2), (2, 0), (1, 2), (-1, 1).

Thus, the following 6 lines should be printed.

• The 1-st line should be Yes because (a_1, b_1) = (0, 0) is contained in both P_1 and P_2.
• The 2-nd line should be No because (a_2, b_2) = (1, 0) is contained in P_2 but not in P_1.
• The 3-rd line should be Yes because (a_3, b_3) = (0, 1) is contained in both P_1 and P_2.
• The 4-th line should be Yes because (a_4, b_4) = (1, 1) is contained in both P_1 and P_2.
• The 5-th line should be Yes because (a_5, b_5) = (-1, -1) is contained in both P_1 and P_2.
• The 6-th line should be No because (a_6, b_6) = (-1, -2) is contained in P_2 but not in P_1.

Note that a point on the boundary of a polygon is also considered to be contained in the polygon.

Sample Input 2

10
45 100
-60 98
-95 62
-95 28
-78 -41
-54 -92
-8 -99
87 -94
98 23
87 91
5
-57 -40
-21 -67
25 39
-30 25
39 -20
16
4 5
-34 -8
-63 53
78 84
19 -16
64 9
-13 7
13 53
-20 4
2 -7
3 18
-12 10
-69 -93
2 9
27 64
-92 -100

Sample Output 2

Yes
Yes
No
No
Yes
No
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
No

Problem Statement

Blocks are stacked in a triangle. The i-th column from the top has i blocks.

You are given a sequence P = ((a_1, c_1), (a_2, c_2), ..., (a_M, c_M)) which is a result of the run-length compression of a sequence A = (A_1, A_2, ..., A_N) consisting of non-negative integers less than or equal to 6.

• For example, when A = (2, 2, 2, 5, 5, 1), you are given P = ((2, 3), (5, 2), (1, 1)).

You will write a number on each block so that the following conditions are satisfied, where B_{i,j} denotes the number to write on the j-th block from the left in the i-th column from the top:

• For all integers i such that 1 \leq i \leq N, it holds that B_{N,i} = A_{i}.
• For all pairs of integers (i, j) such that 1 \leq j \leq i \leq N-1, it holds that B_{i,j}= (B_{i+1,j}+B_{i+1,j+1})\bmod 7.

Enumerate the numbers written on the blocks in the K-th column from the top.

Constraints

• 1 \leq N \leq 10^9
• 1 \leq M \leq \min(N, 200)
• 1 \leq K \leq \min(N,5 \times 10^5)
• 0 \leq a_i \leq 6
• 1 \leq c_i \leq N
• \sum_{i=1}^M c_i = N
• All values in input are integers.

Sample Input 1

6 3 4
2 3
5 2
1 1

Sample Output 1

1 4 3 2

We have A = (2,2,2,5,5,1). The number written on the blocks are as follows.

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

Sample Input 2

1 1 1
6 1

Sample Output 2

6

Sample Input 3

111111111 9 9
0 1
1 10
2 100
3 1000
4 10000
5 100000
6 1000000
0 10000000
1 100000000

Sample Output 3

1 0 4 2 5 5 5 6 3