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