Problem Statement

Keyence has a culture of addressing everyone with the honorific "san," regardless of their role, age, or position. Even a new employee would call the president "Nakata-san." [Translator's note: this is a bit unusual in Japan.]

You are given a person's surname and first name as strings S and T, respectively.

Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.

Constraints

• Each of S and T is a string that satisfies the following conditions.
  • The length is between 1 and 10, inclusive.
  • The first character is an uppercase English letter.
  • All characters except the first one are lowercase English letters.

Sample Input 1

Takahashi Chokudai

Sample Output 1

Takahashi san

Print the concatenation of the surname (Takahashi), a space ( ), and the honorific (san) in this order.

Sample Input 2

K Eyence

Sample Output 2

K san

Problem Statement

Print an arithmetic sequence with first term A, last term B, and common difference D.

You are only given inputs for which such an arithmetic sequence exists.

Constraints

• 1 \leq A \leq B \leq 100
• 1 \leq D \leq 100
• There is an arithmetic sequence with first term A, last term B, and common difference D.
• All input values are integers.

Sample Input 1

3 9 2

Sample Output 1

3 5 7 9

The arithmetic sequence with first term 3, last term 9, and common difference 2 is (3,5,7,9).

Sample Input 2

10 10 1

Sample Output 2

10

The arithmetic sequence with first term 10, last term 10, and common difference 1 is (10).

Problem Statement

You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.

Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.

Constraints

• A_i is 0 or 1.

Sample Input 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

13

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.

Sample Input 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

Sample Output 2

766067858140017173

Problem Statement

There is an infinitely long piano keyboard. Is there a continuous segment within this keyboard that consists of W white keys and B black keys?

Let S be the string formed by infinitely repeating the string wbwbwwbwbwbw.

Is there a substring of S that consists of W occurrences of w and B occurrences of b?

Constraints

• W and B are integers.
• 0\leq W,B \leq 100
• W+B \geq 1

Sample Input 1

3 2

Sample Output 1

Yes

The first 15 characters of S are wbwbwwbwbwbwwbw. You can take the 11-th through 15-th characters to form the string bwwbw, which is a substring consisting of three occurrences of w and two occurrences of b.

Sample Input 2

3 0

Sample Output 2

No

The only string consisting of three occurrences of w and zero occurrences of b is www, which is not a substring of S.

Sample Input 3

92 66

Sample Output 3

Yes

Problem Statement

For a positive integer L, a level-L dango string is a string that satisfies the following conditions.

• It is a string of length L+1 consisting of o and -.
• Exactly one of the first character and the last character is -, and the other L characters are o.

For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).

You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.

• There is a contiguous substring of S that is a level-X dango string.

If there is no such integer, print -1.

Constraints

• 1\leq N\leq 2\times10^5
• S is a string of length N consisting of o and -.

Sample Input 1

10
o-oooo---o

Sample Output 1

4

For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string. No substring of S is a level-5 dango string or above, so you should print 4.

Sample Input 2

1
-

Sample Output 2

-1

Only the empty string and - are the substrings of S. They are not dango strings, so you should print -1.

Sample Input 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

Sample Output 3

7

Problem Statement

There are N sellers and M buyers in an apple market.

The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).

The i-th buyer may buy an apple for B_i yen or less.

Find the minimum integer X that satisfies the following condition.

Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.

Constraints

• 1 \leq N,M \leq 2\times 10^5
• 1\leq A_i,B_i \leq 10^9
• All input values are integers.

Sample Input 1

3 4
110 90 120
100 80 120 10000

Sample Output 1

110

Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.

Since an integer less than 110 does not satisfy the condition, this is the answer.

Sample Input 2

5 2
100000 100000 100000 100000 100000
100 200

Sample Output 2

201

Sample Input 3

3 2
100 100 100
80 120

Sample Output 3

100

Problem Statement

There is an online game with N registered players.
Today, which is the 10^{100}-th day since its launch, the developer Takahashi examined the users' login history. It turned out that the i-th player logged in for B_i consecutive days from Day A_i, where Day 1 is the launch day, and did not log in for the other days. In other words, the i-th player logged in on Day A_i, A_i+1, \ldots, A_i+B_i-1, and only on those days.
For each integer k such that 1\leq k\leq N, find the number of days on which exactly k players logged in.

Constraints

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

Sample Input 1

3
1 2
2 3
3 1

Sample Output 1

2 2 0

The first player logged in on Day 1, 2, the second player logged in on Day 2, 3, 4, and the third player logged in on Day 3 only.

Thus, we can see that Day 1, 4 had 1 player logged in, Day 2, 3 had 2 players logged in, and the other days had no players logged in.

The answer is: there were 2 days with exactly 1 player logged in, 2 days with exactly 2 players logged in, and 0 days with exactly 3 players logged in.

Sample Input 2

2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

0 1000000000

There may be two or more players who logged in during the same period.

Problem Statement

You are given a rooted tree with N vertices. The root is Vertex 1.
For each i = 1, 2, \ldots, N-1, the i-th edge connects Vertex u_i and Vertex v_i.

For each i = 1, 2, \ldots, N, let S_i denote the set of all vertices in the subtree rooted at Vertex i. (Each vertex is in the subtree rooted at itself, that is, i \in S_i.)

Additionally, for integers l and r, let [l, r] denote the set of all integers between l and r, that is, [l, r] = \lbrace l, l+1, l+2, \ldots, r \rbrace.

Consider a sequence of N pairs of integers \big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)\big) that satisfies the conditions below.

• 1 \leq L_i \leq R_i for every integer i such that 1 \leq i \leq N.
• The following holds for every pair of integers (i, j) such that 1 \leq i, j \leq N.
  • [L_i, R_i] \subseteq [L_j, R_j] if S_i \subseteq S_j
  • [L_i, R_i] \cap [L_j, R_j] = \emptyset if S_i \cap S_j = \emptyset

It can be shown that there is at least one sequence \big((L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)\big). Among those sequences, print one that minimizes \max \lbrace L_1, L_2, \ldots, L_N, R_1, R_2, \ldots, R_N \rbrace, the maximum integer used. (If there are multiple such sequences, you may print any of them.)

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• All values in input are integers.
• The given graph is a tree.

Sample Input 1

3
2 1
3 1

Sample Output 1

1 2
2 2
1 1

(L_1, R_1) = (1, 2), (L_2, R_2) = (2, 2), (L_3, R_3) = (1, 1) satisfies the conditions.
Indeed, we have [L_2, R_2] \subseteq [L_1, R_1], [L_3, R_3] \subseteq [L_1, R_1], [L_2, R_2] \cap [L_3, R_3] = \emptyset.
Additionally, \max \lbrace L_1, L_2, L_3, R_1, R_2, R_3 \rbrace = 2 is the minimum possible value.

Sample Input 2

5
3 4
5 4
1 2
1 4

Sample Output 2

1 3
3 3
2 2
1 2
1 1

Sample Input 3

5
4 5
3 2
5 2
3 1

Sample Output 3

1 1
1 1
1 1
1 1
1 1

Problem Statement

There are 2N students standing in a row, numbered 1, 2, \ldots, 2N from left to right. For all pairs of two students, they are on good or bad terms. Specifically, for each 1\leq i\leq M, Student A_i and Student B_i are on good terms; for the remaining pairs of two students, they are on bad terms.

The teacher is going to do the following operation N times to form N pairs of two students.

• Choose two adjacent students who are on good terms, pair them, and remove them from the row.
• If the removed students were not at an end of the row, close up the gap so that the two students who were to the left and right of the removed students are now adjacent.

Find the number, modulo 998244353, of possible ways to do the operation N times. Two ways to do the operation N times are considered different when there exists 1\leq i\leq N such that the pair of students chosen in the i-th operation is different in those two ways.

Constraints

• 1 \leq N \leq 200
• 0 \leq M \leq N(2N-1)
• 1 \leq A_i < B_i \leq 2N
• All pairs (A_i, B_i) are distinct.
• All values in input are integers.

Sample Input 1

2 3
1 2
1 4
2 3

Sample Output 1

1

The only way to complete the procedure is to choose Students 2 and 3 in the first and Students 1 and 4 in the second. If Students 1 and 2 are chosen in the first operation, Students 3 and 4 will remain, who are on bad terms and thus cannot be paired in the second operation.
Thus, you should print 1.

Sample Input 2

2 2
1 2
3 4

Sample Output 2

2

There are two ways to complete the procedure: one way is to choose Students 1 and 2 in the first operation and Students 3 and 4 in the second, and the other way is to choose Students 3 and 4 in the first operation and Students 1 and 2 in the second. Note that these two ways are distinguished.

Sample Input 3

2 2
1 3
2 4

Sample Output 3

0

Since no pair can be chosen in the first operation, there is no way to complete the procedure, so you should print 0.