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

Print a number between A and B (inclusive) that is a multiple of C.

If there is no such number, print -1.

Constraints

• 1 \leq A \leq B \leq 1000
• 1 \leq C \leq 1000
• All values in input are integers.

Sample Input 1

123 456 100

Sample Output 1

200

300 or 400 would also be accepted.

Sample Input 2

630 940 314

Sample Output 2

-1

Problem Statement

There are N people numbered Person 1, Person 2, \dots, and Person N. Person i has a family name s_i and a given name t_i.

Consider giving a nickname to each of the N people. Person i's nickname a_i should satisfy all the conditions below.

• a_i coincides with Person i's family name or given name. In other words, a_i = s_i and/or a_i = t_i holds.
• a_i does not coincide with the family name and the given name of any other person. In other words, for all integer j such that 1 \leq j \leq N and i \neq j, it holds that a_i \neq s_j and a_i \neq t_j.

Is it possible to give nicknames to all the N people? If it is possible, print Yes; otherwise, print No.

Constraints

• 2 \leq N \leq 100
• N is an integer.
• s_i and t_i are strings of lengths between 1 and 10 (inclusive) consisting of lowercase English alphabets.

Sample Input 1

3
tanaka taro
tanaka jiro
suzuki hanako

Sample Output 1

Yes

The following assignment satisfies the conditions of nicknames described in the Problem Statement: a_1 = taro, a_2 = jiro, a_3 = hanako. (a_3 may be suzuki, too.)
However, note that we cannot let a_1 = tanaka, which violates the second condition of nicknames, since Person 2's family name s_2 is tanaka too.

Sample Input 2

3
aaa bbb
xxx aaa
bbb yyy

Sample Output 2

No

There is no way to give nicknames satisfying the conditions in the Problem Statement.

Sample Input 3

2
tanaka taro
tanaka taro

Sample Output 3

No

There may be a pair of people with the same family name and the same given name.

Sample Input 4

3
takahashi chokudai
aoki kensho
snu ke

Sample Output 4

Yes

We can let a_1 = chokudai, a_2 = kensho, and a_3 = ke.

Problem Statement

There are N countries numbered 1 to N. For each i = 1, 2, \ldots, N, Takahashi has A_i units of the currency of country i.

Takahashi can repeat the following operation any number of times, possibly zero:

• First, choose an integer i between 1 and N-1, inclusive.
• Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
  • Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).

Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Constraints

• All input values are integers.
• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq T_i \leq S_i \leq 10^9

Sample Input 1

4
5 7 0 3
2 2
4 3
5 2

Sample Output 1

5

In the following explanation, let the sequence A = (A_1, A_2, A_3, A_4) represent the numbers of units of the currencies of the countries Takahashi has. Initially, A = (5, 7, 0, 3).

Consider performing the operation four times as follows:

• Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (5, 3, 3, 3).
• Choose i = 1, pay two units of the currency of country 1, and gain two units of the currency of country 2. Now, A = (3, 5, 3, 3).
• Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (3, 1, 6, 3).
• Choose i = 3, pay five units of the currency of country 3, and gain two units of the currency of country 4. Now, A = (3, 1, 1, 5).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.

Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

45

Problem Statement

Artist Takasago has created an object in the shape of a fish skeleton.

The object consists of N ribs and one spine. The ribs are numbered 1 through N.

He wants to write one string on each of the N+1 bones, satisfying all of the following conditions.

• The length of the string written on the spine is N.
• For each rib i = 1, \dots, N, the following hold.
  • The length of the string written on rib i is A_i.
  • The B_i-th character of the string written on rib i equals the i-th character of the string written on the spine.
• Each of the strings written on the N+1 bones is one of S_1, \cdots, S_M (duplicates allowed).

S_1, \cdots, S_M are strings consisting of lowercase English letters, and they are all distinct.

For each j = 1, \cdots, M, answer the following question.

• Among the ways to write strings satisfying the conditions, is there one where the string written on the spine is S_j?

Constraints

• N is an integer.
• 1 \leq N \leq 10
• A_i and B_i are integers. (1 \leq i \leq N)
• 1 \leq B_i \leq A_i \leq 10 (1 \leq i \leq N)
• M is an integer.
• 1 \leq M \leq 200\,000
• S_j is a string consisting of lowercase English letters. (1 \leq j \leq M)
• 1 \leq |S_j| \leq 10 (1 \leq j \leq M)
• S_1, \cdots, S_M are pairwise distinct.

Sample Input 1

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 1

Yes
Yes
No
No
No
No
No
No

By writing chris, retro, tuna, retro, cod on ribs 1,2,3,4,5 respectively, the conditions are satisfied with retro written on the spine.

• The length of retro is 5.
• For each rib, the following hold.
  • The string written on rib 1 is chris, which has length 5. Its third character is r, which equals the first character of retro.
  • The string written on rib 2 is retro, which has length 5. Its second character is e, which equals the second character of retro.
  • The string written on rib 3 is tuna, which has length 4. Its first character is t, which equals the third character of retro.
  • The string written on rib 4 is retro, which has length 5. Its first character is r, which equals the fourth character of retro.
  • The string written on rib 5 is cod, which has length 3. Its second character is o, which equals the fifth character of retro.

By writing itchy, chris, rock, itchy, ash on ribs 1,2,3,4,5 respectively, the conditions are satisfied with chris written on the spine.

Sample Input 2

5
5 1
5 2
5 3
5 4
5 5
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 2

Yes
Yes
Yes
No
No
No
No
No

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

• 1 \leq N \leq 200000
• 1 \leq S_i,T_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

1
1
1
1

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

1
2
4
7

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4

50
22
63
28
44
60
64
27

Problem Statement

You are given N intervals of real numbers. The i-th (1 \leq i \leq N) interval is [l_i, r_i]. Find the number of pairs (i, j)\,(1 \leq i < j \leq N) such that the i-th and j-th intervals intersect.

Constraints

• 2 \leq N \leq 5 \times 10^5
• 0 \leq l_i < r_i \leq 10^9
• All input values are integers.

Sample Input 1

3
1 5
7 8
3 7

Sample Output 1

2

The given intervals are [1,5], [7,8], [3,7]. Among these, the 1-st and 3-rd intervals intersect, as well as the 2-nd and 3-rd intervals, so the answer is 2.

Sample Input 2

3
3 4
2 5
1 6

Sample Output 2

3

Sample Input 3

2
1 2
3 4

Sample Output 3

0

Problem Statement

You are given a sequence of length M consisting of integers between 1 and N-1, inclusive: A=(A_1,A_2,\dots,A_M). Answer the following question for i=1, 2, \dots, M.

• There is a sequence B=(B_1,B_2,\dots,B_N). Initially, we have B_j=j for each j. Let us perform the following operation for k=1, 2, \dots, i-1, i+1, \dots, M in this order (in other words, for integers k between 1 and M except i in ascending order).
  • Swap the values of B_{A_k} and B_{A_k+1}.
• After all the operations, let S_i be the value of j such that B_j=1. Find S_i.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1 \leq A_i \leq N-1\ (1\leq i \leq M)
• All values in the input are integers.

Sample Input 1

5 4
1 2 3 2

Sample Output 1

1
3
2
4

For i = 2, the operations change B as follows.

• Initially, B = (1,2,3,4,5).
• Perform the operation for k=1. That is, swap the values of B_1 and B_2, making B = (2,1,3,4,5).
• Perform the operation for k=3. That is, swap the values of B_3 and B_4, making B = (2,1,4,3,5).
• Perform the operation for k=4. That is, swap the values of B_2 and B_3, making B = (2,4,1,3,5).

After all the operations, we have B_3=1, so S_2 = 3.

Similarly, we have the following.

• For i=1: performing the operation for k=2,3,4 in this order makes B=(1,4,3,2,5), so S_1=1.
• For i=3: performing the operation for k=1,2,4 in this order makes B=(2,1,3,4,5), so S_3=2.
• For i=4: performing the operation for k=1,2,3 in this order makes B=(2,3,4,1,5), so S_4=4.

Sample Input 2

3 3
2 2 2

Sample Output 2

1
1
1

Sample Input 3

10 10
1 1 1 9 4 4 2 1 3 3

Sample Output 3

2
2
2
3
3
3
1
3
4
4

Problem Statement

A positive integer X is called a good integer if and only if it satisfies the following condition:

• When X is written in decimal notation, the ones digit, tens digit, \ldots form a non-increasing sequence.
  • More formally, the unique non-negative integer sequence (d_0,d_1,\ldots) satisfying \displaystyle X=\sum_{i=0}^{\infty} d_i10^i (0\le d_i < 10) forms a non-increasing sequence.

For example, 112389, 1, and 777 are good integers, but 443 and 404 are not good integers.

You are given a positive integer N.

Determine whether there exists a good integer that is a multiple of N, and if it exists, find its minimum value.

Constraints

• 1\le N\le 3\times 10^6
• All input values are integers.

Sample Input 1

21

Sample Output 1

126

126 is a multiple of 21, and we have 6 \geq 2 \geq 1 \geq 0 \geq \ldots, so it is a good integer. There does not exist a good integer less than 126 that is a multiple of 21, so output 126.

Sample Input 2

10

Sample Output 2

-1

Sample Input 3

3

Sample Output 3

3

Sample Input 4

1089

Sample Output 4

9999999999999999999999

The answer may be 2^{64} or greater.