Problem Statement

There are N people numbered 1, 2, \ldots, N, sitting in this clockwise order around a round table. In particular, person 1 is sitting next to person N in the clockwise direction.

For each i = 1, 2, \ldots, N, person i has a name S_i and an age A_i. Here, no two people have the same name or the same age.

Starting from the youngest person, print the names of all N people in the order of their seating positions in clockwise order.

Constraints

• 2 \leq N \leq 100
• N is an integer.
• S_i is a string of length between 1 and 10, consisting of lowercase English letters.
• i \neq j \implies S_i \neq S_j
• 0 \leq A_i \leq 10^9
• A_i is an integer.
• i \neq j \implies A_i \neq A_j

Sample Input 1

5
alice 31
bob 41
carol 5
dave 92
ellen 65

Sample Output 1

carol
dave
ellen
alice
bob

The youngest person is person 3. Therefore, starting from person 3, print the names in the clockwise order of their seating positions: person 3, person 4, person 5, person 1, and person 2.

Sample Input 2

2
takahashi 1000000000
aoki 999999999

Sample Output 2

aoki
takahashi

Problem Statement

You are given an integer N.
Print an approximation of N according to the following instructions.

• If N is less than or equal to 10^3-1, print N as it is.
• If N is between 10^3 and 10^4-1, inclusive, truncate the ones digit of N and print the result.
• If N is between 10^4 and 10^5-1, inclusive, truncate the tens digit and all digits below it of N and print the result.
• If N is between 10^5 and 10^6-1, inclusive, truncate the hundreds digit and all digits below it of N and print the result.
• If N is between 10^6 and 10^7-1, inclusive, truncate the thousands digit and all digits below it of N and print the result.
• If N is between 10^7 and 10^8-1, inclusive, truncate the ten-thousands digit and all digits below it of N and print the result.
• If N is between 10^8 and 10^9-1, inclusive, truncate the hundred-thousands digit and all digits below it of N and print the result.

Constraints

• N is an integer between 0 and 10^9-1, inclusive.

Sample Input 1

20230603

Sample Output 1

20200000

20230603 is between 10^7 and 10^8-1 (inclusive).
Therefore, truncate the ten-thousands digit and all digits below it, and print 20200000.

Sample Input 2

0

Sample Output 2

0

Sample Input 3

304

Sample Output 3

304

Sample Input 4

500600

Sample Output 4

500000

Problem Statement

There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).

Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.

Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.

After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.

Constraints

• 1 \leq N, D \leq 2000
• -1000 \leq X_i, Y_i \leq 1000
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All input values are integers.

Sample Input 1

4 5
2 -1
3 1
8 8
0 5

Sample Output 1

Yes
Yes
No
Yes

The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.

Sample Input 2

3 1
0 0
-1000 -1000
1000 1000

Sample Output 2

Yes
No
No

Sample Input 3

9 4
3 2
6 -1
1 6
6 5
-2 -3
5 3
2 -3
2 1
2 6

Sample Output 3

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No

Problem Statement

There is a rectangular cake with some strawberries on the xy-plane. The cake occupies the rectangular area \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace.

There are N strawberries on the cake, and the coordinates of the i-th strawberry are (p_i, q_i) for i = 1, 2, \ldots, N. No two strawberries have the same coordinates.

Takahashi will cut the cake into several pieces with a knife, as follows.

• First, cut the cake along A different lines parallel to the y-axis: lines x = a_1, x = a_2, \ldots, x = a_A.
• Next, cut the cake along B different lines parallel to the x-axis: lines y = b_1, y = b_2, \ldots, y = b_B.

As a result, the cake will be divided into (A+1)(B+1) rectangular pieces. Takahashi will choose just one of these pieces to eat. Print the minimum and maximum possible numbers of strawberries on the chosen piece.

Here, it is guaranteed that there are no strawberries along the edges of the final pieces. For a more formal description, refer to the constraints below.

Constraints

• 3 \leq W, H \leq 10^9
• 1 \leq N \leq 2 \times 10^5
• 0 \lt p_i \lt W
• 0 \lt q_i \lt H
• i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
• 1 \leq A, B \leq 2 \times 10^5
• 0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
• 0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
• p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
• q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
• All input values are integers.

Sample Input 1

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

Sample Output 1

0 2

There are nine pieces in total: six with zero strawberries, one with one strawberry, and two with two strawberries. Therefore, when choosing just one of these pieces to eat, the minimum possible number of strawberries on the chosen piece is 0, and the maximum possible number is 2.

Sample Input 2

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

Sample Output 2

1 1

Each piece has one strawberry on it.

Problem Statement

You are given an undirected graph G with N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge is an undirected edge connecting vertices u_i and v_i.

A graph with N vertices is called good if the following condition holds for all i = 1, 2, \ldots, K:

• there is no path connecting vertices x_i and y_i in G.

The given graph G is good.

You are given Q independent questions. Answer all of them. For i = 1, 2, \ldots, Q, the i-th question is as follows.

• Is the graph G^{(i)} obtained by adding an undirected edge connecting vertices p_i and q_i to the given graph G good?

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times10^5
• 1 \leq u_i, v_i \leq N
• 1 \leq K \leq 2 \times 10^5
• 1 \leq x_i, y_i \leq N
• x_i \neq y_i
• i \neq j \implies \lbrace x_i, y_i \rbrace \neq \lbrace x_j, y_j \rbrace
• For all i = 1, 2, \ldots, K, there is no path connecting vertices x_i and y_i.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq p_i, q_i \leq N
• p_i \neq q_i
• All input values are integers.

Sample Input 1

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

Sample Output 1

No
No
Yes
Yes

• For the first question, the graph G^{(1)} is not good because it has a path 1 \rightarrow 2 \rightarrow 5 connecting vertices x_1 = 1 and y_1 = 5. Therefore, print No.
• For the second question, the graph G^{(2)} is not good because it has a path 2 \rightarrow 6 connecting vertices x_2 = 2 and y_2 = 6. Therefore, print No.
• For the third question, the graph G^{(3)} is good. Therefore, print Yes.
• For the fourth question, the graph G^{(4)} is good. Therefore, print Yes.

As seen in this sample input, note that the given graph G may have self-loops or multi-edges.

Problem Statement

Takahashi and Aoki will work part-time for the next N days.
Takahashi's shift schedule is given by the string S, where the i-th character of S is # if he works on the i-th day, and . if he is absent on the i-th day.
Based on this, Aoki created his shift schedule as follows.

• First, take a positive divisor M of N that is not equal to N.
• Next, decide the attendance for the first M days.
• Finally, for i = 1, 2, \ldots, N - M in this order, decide the attendance for the (M + i)-th day so that it matches the attendance for the i-th day.

Note that different values of M may lead to the same final shift schedule.

Find the number of possible shift schedules for Aoki such that at least one of Takahashi and Aoki works on each of the N days, modulo 998244353.

Constraints

• N is an integer between 2 and 10^5, inclusive.
• S is a string of length N consisting of # and ..

Sample Input 1

6
##.#.#

Sample Output 1

3

Takahashi works on days 1, 2, 4, and 6.
Let T be the string representing Aoki's shift schedule, where the i-th character of T is # if he works on the i-th day, and . if he is absent on the i-th day.
There are three possible strings for T: ######, #.#.#., and .##.##.

The first shift schedule can be realized by choosing M = 1 or 2 or 3, the second by choosing M = 2, and the third by choosing M = 3.

Sample Input 2

7
...####

Sample Output 2

1

Sample Input 3

12
####.####.##

Sample Output 3

19

Problem Statement

You are given a sequence of length 2N: A = (A_1, A_2, \ldots, A_{2N}).

Find the maximum value that can be obtained as the median of the length-N sequence (A_1 \oplus A_2, A_3 \oplus A_4, \ldots, A_{2N-1} \oplus A_{2N}) by rearranging the elements of the sequence A.

Here, \oplus represents bitwise exclusive OR.

Also, for a sequence B of length L, the median of B is the value at the \lfloor \frac{L}{2} \rfloor + 1-th position of the sequence B' obtained by sorting B in ascending order.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq A_i < 2^{30}
• All input values are integers.

Sample Input 1

4
4 0 0 11 2 7 9 5

Sample Output 1

14

By rearranging A as (5, 0, 9, 7, 11, 4, 0, 2), we get (A_1 \oplus A_2, A_3 \oplus A_4, A_5 \oplus A_6, A_7 \oplus A_8) = (5, 14, 15, 2), and the median of this sequence is 14.
It is impossible to rearrange A so that the median of (A_1 \oplus A_2, A_3 \oplus A_4, A_5 \oplus A_6, A_7 \oplus A_8) is 15 or greater, so we print 14.

Sample Input 2

1
998244353 1000000007

Sample Output 2

1755654

Sample Input 3

5
1 2 4 8 16 32 64 128 256 512

Sample Output 3

192

Problem Statement

You are given a directed graph with N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge is directed from vertex s_i to vertex t_i.

Determine whether there is a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) that satisfies both of the following conditions, and if there is, provide an example.

• P_{s_i} \lt P_{t_i} for all i = 1, 2, \ldots, M.
• L_i \leq P_i \leq R_i for all i = 1, 2, \ldots, N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min\lbrace 4 \times 10^5, N(N-1) \rbrace
• 1 \leq s_i, t_i \leq N
• s_i \neq t_i
• i \neq j \implies (s_i, t_i) \neq (s_j, t_j)
• 1 \leq L_i \leq R_i \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
3 1 4 2 5

P = (3, 1, 4, 2, 5) satisfies the conditions. In fact,

• for the first edge (s_1, t_1) = (1, 5), we have P_1 = 3 \lt 5 = P_5;
• for the second edge (s_2, t_2) = (2, 1), we have P_2 = 1 \lt 3 = P_1;
• for the third edge (s_3, t_3) = (2, 5), we have P_2 = 1 \lt 5 = P_5;
• for the fourth edge (s_4, t_4) = (4, 3), we have P_4 = 2 \lt 4 = P_3.

Also,

• L_1 = 1 \leq P_1 = 3 \leq R_1 = 5,
• L_2 = 1 \leq P_2 = 1 \leq R_2 = 3,
• L_3 = 3 \leq P_3 = 4 \leq R_3 = 4,
• L_4 = 1 \leq P_4 = 2 \leq R_4 = 3,
• L_5 = 4 \leq P_5 = 5 \leq R_5 = 5.

Sample Input 2

2 2
1 2
2 1
1 2
1 2

Sample Output 2

No

No P satisfies the conditions, so print No.