Problem Statement

You are given a real number X.Y, where Y is a single digit.

Print the following: (quotes for clarity)

• X-, if 0 \leq Y \leq 2;
• X, if 3 \leq Y \leq 6;
• X+, if 7 \leq Y \leq 9.

Constraints

• 1 \leq X \leq 15
• 0 \leq Y \leq 9
• X and Y are integers.

Sample Input 1

15.8

Sample Output 1

15+

Here, printing 15 + will not be accepted: do not print a space between X and +, or between X and -.

Sample Input 2

1.0

Sample Output 2

1-

You will not get inputs such as 1.00 and 1.

Sample Input 3

12.5

Sample Output 3

12

Problem Statement

Determine if there is a segment that directly connects the points numbered a and b in the figure below.

Constraints

• 1 \leq a \lt b \leq 15
• a and b are integers.

Sample Input 1

1 2

Sample Output 1

Yes

In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.

Sample Input 2

2 8

Sample Output 2

No

In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.

Sample Input 3

14 15

Sample Output 3

No

Problem Statement

There are N rectangular sheets spread out on a coordinate plane.

Each side of the rectangular region covered by each sheet is parallel to the x- or y-axis.
Specifically, the i-th sheet covers exactly the region satisfying A_i \leq x\leq B_i and C_i \leq y\leq D_i.

Let S be the area of the region covered by one or more sheets. It can be proved that S is an integer under the constraints.
Print S as an integer.

Constraints

• 2\leq N\leq 100
• 0\leq A_i<B_i\leq 100
• 0\leq C_i<D_i\leq 100
• All input values are integers.

Sample Input 1

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

Sample Output 1

20

The three sheets cover the following regions.
Here, red, yellow, and blue represent the regions covered by the first, second, and third sheets, respectively.

Therefore, the area of the region covered by one or more sheets is S=20.

Sample Input 2

2
0 100 0 100
0 100 0 100

Sample Output 2

10000

Note that different sheets may cover the same region.

Sample Input 3

3
0 1 0 1
0 3 0 5
5 10 0 10

Sample Output 3

65

Problem Statement

AtCoder currently holds four series of regular contests: ABC, ARC, AGC, and AHC.

What is the series of regular contests currently held by AtCoder in addition to S_1, S_2, and S_3?

Constraints

• Each of S_1, S_2, and S_3 is ABC, ARC, AGC, or AHC.
• S_1, S_2, and S_3 are pairwise different.

Sample Input 1

ARC
AGC
AHC

Sample Output 1

ABC

Given in input are ARC, AGC, and AHC. The rest is ABC.

Sample Input 2

AGC
ABC
ARC

Sample Output 2

AHC

Problem Statement

There are N people numbered from 1 to N.

Person i is wearing a bib with the number Q_i and is staring at person P_i.

For each i = 1,2,\ldots,N, find the number written on the bib of the person that the person wearing the bib with number i is staring at.

Constraints

• 2 \leq N \leq 3\times 10^5
• 1 \leq P_i \leq N
• The values of P_i are distinct.
• 1 \leq Q_i \leq N
• The values of Q_i are distinct.
• All input values are integers.

Sample Input 1

4
4 3 2 1
2 3 1 4

Sample Output 1

3 4 1 2

Person 3 is wearing the bib with the number 1, and the person that person 3 is staring at, person 2, is wearing the bib with the number 3. Thus, the answer for i = 1 is 3.

Sample Input 2

10
2 6 4 3 7 8 9 10 1 5
1 4 8 2 10 5 7 3 9 6

Sample Output 2

4 8 6 5 3 10 9 2 1 7

Problem Statement

There is a 10^9-story building with N ladders.
Takahashi, who is on the 1-st (lowest) floor, wants to reach the highest floor possible by using ladders (possibly none).
The ladders are numbered from 1 to N, and ladder i connects the A_i-th and B_i-th floors. One can use ladder i in either direction to move from the A_i-th floor to the B_i-th floor or vice versa, but not between other floors.
Takahashi can freely move within the same floor, but cannot move between floors without using ladders.
What is the highest floor Takahashi can reach?

Constraints

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

Sample Input 1

4
1 4
4 3
4 10
8 3

Sample Output 1

10

He can reach the 10-th floor by using ladder 1 to get to the 4-th floor and then ladder 3 to get to the 10-th floor.

Sample Input 2

6
1 3
1 5
1 12
3 5
3 12
5 12

Sample Output 2

12

Sample Input 3

3
500000000 600000000
600000000 700000000
700000000 800000000

Sample Output 3

1

He may be unable to move between floors.

Problem Statement

You are given the first N terms A _ 1,A _ 2,\dotsc,A _ N of an infinite sequence A=(A _ 1,A _ 2,A _ 3,\dotsc) that has period N.

Determine if there exists a non-empty contiguous subsequence of this infinite sequence whose sum is S.

Here, an infinite sequence A has period N when A _ i=A _ {i-N} for every integer i>N.

Constraints

• 1\leq N\leq2\times10 ^ 5
• 1\leq A _ i\leq 10 ^ 9
• 1\leq S\leq 10 ^ {18}
• All input values are integers.

Sample Input 1

3 42
3 8 4

Sample Output 1

Yes

The sequence A is (3,8,4,3,8,4,3,8,4,\dotsc).

For the subsequence (A _ 2,A _ 3,A _ 4,A _ 5,A _ 6,A _ 7,A _ 8,A _ 9)=(8,4,3,8,4,3,8,4), we have 8+4+3+8+4+3+8+4=42, so print Yes.

Sample Input 2

3 1
3 8 4

Sample Output 2

No

All elements of A are at least 3, so the sum of any non-empty contiguous subsequence is at least 3.

Thus, there is no subsequence with sum 1, so print No.

Sample Input 3

20 83298426
748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772

Sample Output 3

Yes

Sample Input 4

20 85415869
748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772

Sample Output 4

No

Problem Statement

We have a sequence A=(A_1,A_2,\dots,A_N) of length N. Initially, all the terms are 0.
Using an integer K given in the input, we define a function f(A) as follows:

• Let B be the sequence obtained by sorting A in descending order (so that it becomes monotonically non-increasing).
• Then, let f(A)=B_1 + B_2 + \dots + B_K.

We consider applying Q updates on this sequence.
Apply the following operation on the sequence A for i=1,2,\dots,Q in this order, and print the value f(A) at that point after each update.

• Change A_{X_i} to Y_i.

Constraints

• All input values are integers.
• 1 \le K \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le X_i \le N
• 0 \le Y_i \le 10^9

Sample Input 1

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

Sample Output 1

5
6
8
8
15
13
13
11
1
0

In this input, N=4 and K=2. Q=10 updates are applied.

• The 1-st update makes A=(5, 0,0,0). Now, f(A)=5.
• The 2-nd update makes A=(5, 1,0,0). Now, f(A)=6.
• The 3-rd update makes A=(5, 1,3,0). Now, f(A)=8.
• The 4-th update makes A=(5, 1,3,2). Now, f(A)=8.
• The 5-th update makes A=(5,10,3,2). Now, f(A)=15.
• The 6-th update makes A=(0,10,3,2). Now, f(A)=13.
• The 7-th update makes A=(0,10,3,0). Now, f(A)=13.
• The 8-th update makes A=(0,10,1,0). Now, f(A)=11.
• The 9-th update makes A=(0, 0,1,0). Now, f(A)=1.
• The 10-th update makes A=(0, 0,0,0). Now, f(A)=0.

Problem Statement

There is a simple directed graph G with N vertices and N+M edges. The vertices are numbered 1 to N, and the edges are numbered 1 to N+M.

Edge i (1 \leq i \leq N) goes from vertex i to vertex i+1. (Here, vertex N+1 is considered as vertex 1.)
Edge N+i (1 \leq i \leq M) goes from vertex X_i to vertex Y_i.

Takahashi is at vertex 1. At each vertex, he can move to any vertex to which there is an outgoing edge from the current vertex.

Compute the number of ways he can move exactly K times.

That is, find the number of integer sequences (v_0, v_1, \dots, v_K) of length K+1 satisfying all of the following three conditions:

• 1 \leq v_i \leq N for i = 0, 1, \dots, K.
• v_0 = 1.
• There is a directed edge from vertex v_{i-1} to vertex v_i for i = 1, 2, \ldots, K.

Since this number can be very large, print it modulo 998244353.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 50
• 1 \leq K \leq 2 \times 10^5
• 1 \leq X_i, Y_i \leq N, X_i \neq Y_i
• All of the N+M directed edges are distinct.
• All input values are integers.

Sample Input 1

6 2 5
1 4
2 5

Sample Output 1

5

The above figure represents the graph G. There are five ways for Takahashi to move:

• Vertex 1 \to Vertex 2 \to Vertex 3 \to Vertex 4 \to Vertex 5 \to Vertex 6
• Vertex 1 \to Vertex 2 \to Vertex 5 \to Vertex 6 \to Vertex 1 \to Vertex 2
• Vertex 1 \to Vertex 2 \to Vertex 5 \to Vertex 6 \to Vertex 1 \to Vertex 4
• Vertex 1 \to Vertex 4 \to Vertex 5 \to Vertex 6 \to Vertex 1 \to Vertex 2
• Vertex 1 \to Vertex 4 \to Vertex 5 \to Vertex 6 \to Vertex 1 \to Vertex 4

Sample Input 2

10 0 200000

Sample Output 2

1

Sample Input 3

199 10 1326
122 39
142 49
164 119
197 127
188 145
69 80
6 120
24 160
18 154
185 27

Sample Output 3

451022766