Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.
You perform the following operation exactly K times:

• remove the initial element of A and append a 0 to the tail of A.

Print all the elements of A after the operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 100
• 1 \leq A_i \leq 100
• All values in the input are integers.

Sample Input 1

3 2
2 7 8

Sample Output 1

8 0 0

Before the operations, A = (2, 7, 8).
After performing the operation once, A = (7, 8, 0).
After performing the operation twice, A = (8, 0, 0).
Thus, (8, 0, 0) is the answer.

Sample Input 2

3 4
9 9 9

Sample Output 2

0 0 0

Sample Input 3

9 5
1 2 3 4 5 6 7 8 9

Sample Output 3

6 7 8 9 0 0 0 0 0

Problem Statement

Takahashi had a report whose deadline was B minutes past A o'clock on May 17, 2025. He submitted it at D minutes past C o'clock on May 17, 2025.
It is guaranteed that "B minutes past A o'clock" and "D minutes past C o'clock" are different times.

Output Yes if Takahashi submitted the report before the deadline, and No otherwise.

Constraints

• 0 \leq A, C \leq 23
• 0 \leq B, D \leq 59
• (A, B) \neq (C, D)
• A, B, C, and D are integers.

Sample Input 1

22 40 22 30

Sample Output 1

Yes

The deadline is 22:40, and he submitted at 22:30, so he submitted before the deadline. Hence, output Yes.

Sample Input 2

22 40 22 45

Sample Output 2

No

The deadline is 22:40, and he submitted at 22:45, so he submitted after the deadline. Hence, output No.

Sample Input 3

12 0 11 30

Sample Output 3

Yes

Problem Statement

Takahashi has N teeth, one in each of the holes numbered 1, 2, \dots, N.
Dentist Aoki will perform Q treatments on these teeth and holes.
In the i-th treatment, hole T_i is treated as follows:

• If there is a tooth in hole T_i, remove the tooth from hole T_i.
• If there is no tooth in hole T_i (i.e., the hole is empty), grow a tooth in hole T_i.

After all treatments are completed, how many teeth does Takahashi have?

Constraints

• All input values are integers.
• 1 \le N, Q \le 1000
• 1 \le T_i \le N

Sample Input 1

30 6
2 9 18 27 18 9

Sample Output 1

28

Initially, Takahashi has 30 teeth, and Aoki performs six treatments.

• In the first treatment, hole 2 is treated. There is a tooth in hole 2, so it is removed.
• In the second treatment, hole 9 is treated. There is a tooth in hole 9, so it is removed.
• In the third treatment, hole 18 is treated. There is a tooth in hole 18, so it is removed.
• In the fourth treatment, hole 27 is treated. There is a tooth in hole 27, so it is removed.
• In the fifth treatment, hole 18 is treated. There is no tooth in hole 18, so a tooth is grown.
• In the sixth treatment, hole 9 is treated. There is no tooth in hole 9, so a tooth is grown.

The final count of teeth is 28.

Sample Input 2

1 7
1 1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

9 20
9 5 1 2 2 2 8 9 2 1 6 2 6 5 8 7 8 5 9 8

Sample Output 3

5

Problem Statement

In an xy-coordinate plane whose x-axis is oriented to the right and whose y-axis is oriented upwards, rotate a point (a, b) around the origin d degrees counterclockwise and find the new coordinates of the point.

Constraints

• -1000 \leq a,b \leq 1000
• 1 \leq d \leq 360
• All values in input are integers.

Sample Input 1

2 2 180

Sample Output 1

-2 -2

When (2, 2) is rotated around the origin 180 degrees counterclockwise, it becomes the symmetric point of (2, 2) with respect to the origin, which is (-2, -2).

Sample Input 2

5 0 120

Sample Output 2

-2.49999999999999911182 4.33012701892219364908

When (5, 0) is rotated around the origin 120 degrees counterclockwise, it becomes (-\frac {5}{2} , \frac {5\sqrt{3}}{2}).
This sample output does not precisely match these values, but the errors are small enough to be considered correct.

Sample Input 3

0 0 11

Sample Output 3

0.00000000000000000000 0.00000000000000000000

Since (a, b) is the origin (the center of rotation), a rotation does not change its coordinates.

Sample Input 4

15 5 360

Sample Output 4

15.00000000000000177636 4.99999999999999555911

A 360-degree rotation does not change the coordinates of a point.

Sample Input 5

-505 191 278

Sample Output 5

118.85878514480690171240 526.66743699786547949770

Problem Statement

For two strings A and B, let A+B denote the concatenation of A and B in this order.

You are given N strings S_1,\ldots,S_N. Modify and print them as follows, in the order i=1, \ldots, N:

• if none of S_1,\ldots,S_{i-1} is equal to S_i, print S_i;
• if X (X>0) of S_1,\ldots,S_{i-1} are equal to S_i, print S_i+ ( +X+ ), treating X as a string.

Constraints

• 1 \leq N \leq 2\times 10^5
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Sample Input 1

5
newfile
newfile
newfolder
newfile
newfolder

Sample Output 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

Sample Input 2

11
a
a
a
a
a
a
a
a
a
a
a

Sample Output 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

Problem Statement

N students are taking a 4-day exam.

There is a 300-point test on each day, for a total of 1200 points.

The first three days of the exam are already over, and the fourth day is now about to begin. The i-th student (1 \leq i \leq N) got P_{i, j} points on the j-th day (1 \leq j \leq 3).

For each student, determine whether it is possible that he/she is ranked in the top K after the fourth day.
Here, the rank of a student after the fourth day is defined as the number of students whose total scores over the four days are higher than that of the student, plus 1.

Constraints

• 1 \leq K \leq N \leq 10^5
• 0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
• All values in input are integers.

Sample Input 1

3 1
178 205 132
112 220 96
36 64 20

Sample Output 1

Yes
Yes
No

If every student scores 100 on the fourth day, the 1-st student will rank 1-st.
If the 2-nd student scores 100 and the other students score 0 on the fourth day, the 2-nd student will rank 1-st.
The 3-rd student will never rank 1-st.

Sample Input 2

2 1
300 300 300
200 200 200

Sample Output 2

Yes
Yes

Sample Input 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

Sample Output 3

Yes
Yes
No
Yes

Problem Statement

There are N equally spaced points on a circle labeled clockwise as 1,2,\ldots,N.

There are M distinct lines, where the i-th line passes through two distinct points A_i and B_i (1 \leq i \leq M).

Find the number of pairs (i,j) satisfying:

• 1 \le i < j \le M, and
• the i-th and j-th lines intersect.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq M \leq 3 \times 10^{5}
• 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
• (A_i,B_i) \neq (A_j,B_j) (i \neq j)
• All input values are integers.

Sample Input 1

8 3
1 5
1 8
2 4

Sample Output 1

2

As shown in the diagram below, there are eight points and three lines on the circle.

The 1st and 2nd lines intersect. The 1st and 3rd lines do not intersect. The 2nd and 3rd lines intersect. Since the pairs (i,j)=(1,2),(2,3) satisfy the conditions, print 2.

Sample Input 2

5 10
2 5
1 5
1 2
2 4
2 3
1 3
1 4
3 5
3 4
4 5

Sample Output 2

40

Problem Statement

You are given a sequence of non-negative integers A = (A_1,\dots,A_{2N}) of length 2N.

Define the score of a parenthesis sequence s of length 2N as follows:

• For every position i where the i-th character of s is ), set A_i to 0, then take the sum of all elements of A.

Find the maximum possible score of a correct parenthesis sequence of length 2N.

You are given T test cases; solve each.

Constraints

• 1 \le T \le 500
• 1 \le N \le 2 \times 10^{5}
• For each input file, the sum of N over all test cases is at most 2 \times 10^{5}.
• 0 \le A_i \le 10^{9} (1 \le i \le 2N)
• All input values are integers.

Sample Input 1

2
3
400
500
200
100
300
600
6
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

Sample Output 1

1200
6000000000

In the first test case, choosing the correct parenthesis string (())() gives a score of 400+500+0+0+300+0=1200.

No correct parenthesis string yields a higher score, so the answer is 1200.

Note that, as in the second test case of this sample, the answer may exceed the 32-bit integer range.

Problem Statement

Let the similarity f(X,Y) between two strings X and Y be the length of their longest common prefix.
For example, the similarity between abc and axbc is 1, and the similarity between aaa and aaaa is 3.

You are given a string S of length N. Let S_i be the suffix of S beginning with the i-th character of S. For each k=1,\ldots,N, find f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N).

Constraints

• 1 \leq N \leq 10^6
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

3
abb

Sample Output 1

3
3
2

S_1 is abb, S_2 is bb, and S_3 is b.

• For k=1: f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3.
• For k=2: f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3.
• For k=3: f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2.

Sample Input 2

11
mississippi

Sample Output 2

11
16
14
12
13
11
9
7
4
3
4