Problem Statement

Takahashi is in a building with 100 floors.

He uses the stairs for moving up two floors or less or moving down three floors or less, and uses the elevator otherwise.

Does he use the stairs to move from floor X to floor Y?

Constraints

• 1 \leq X,Y \leq 100
• X \neq Y
• All input values are integers.

Sample Input 1

1 4

Sample Output 1

No

The move from floor 1 to floor 4 involves going up three floors, so Takahashi uses the elevator.

Sample Input 2

99 96

Sample Output 2

Yes

The move from floor 99 to floor 96 involves going down three floors, so Takahashi uses the stairs.

Sample Input 3

100 1

Sample Output 3

No

Problem Statement

You are given an integer N. If N is between -2^{31} and 2^{31}-1 (inclusive), print Yes; otherwise, print No.

Constraints

• -2^{63} \leq N < 2^{63}
• N is an integer.

Sample Input 1

10

Sample Output 1

Yes

10 is between -2^{31} and 2^{31}-1, so Yes should be printed.

Sample Input 2

-9876543210

Sample Output 2

No

-9876543210 is less than -2^{31}, so No should be printed.

Sample Input 3

483597848400000

Sample Output 3

No

483597848400000 is greater than 2^{31}-1, so No should be printed.

Problem Statement

There are N people standing in a line. The person standing at the i-th position from the front is person P_i.

Process Q queries. The i-th query is as follows:

• You are given integers A_i and B_i. Between person A_i and person B_i, print the person number of the person standing further to the front.

Constraints

• All inputs are integers.
• 1 \leq N \leq 100
• 1 \leq P_i \leq N
• P_i \neq P_j\ (i \neq j)
• 1 \leq Q \leq 100
• 1 \leq A_i < B_i \leq N

Sample Input 1

3
2 1 3
3
2 3
1 2
1 3

Sample Output 1

2
2
1

In the first query, person 2 is at the first position from the front, and person 3 is at the third position, so person 2 is further to the front.

In the second query, person 1 is at the second position from the front, and person 2 is at the first position, so person 2 is further to the front.

In the third query, person 1 is at the second position from the front, and person 3 is at the third position, so person 1 is further to the front.

Sample Input 2

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

Sample Output 2

3
2
3
3
3
2
3
3
7
1
2
3
3

Problem Statement

There are N people, and the current hair length of the i-th person (1 \leq i \leq N) is L_i.
Each person's hair grows by 1 per day.

Print the number of days after which the number of people whose hair length is at least T becomes P or more for the first time.
If there are already P or more people whose hair length is at least T now, print 0.

Constraints

• 1 \leq N \leq 100
• 1 \leq L_i \leq 100
• 1 \leq T \leq 100
• 1 \leq P \leq N
• All input values are integers.

Sample Input 1

5 10 3
3 11 1 6 2

Sample Output 1

7

There are five people, and their current hair lengths are 3, 11, 1, 6, 2, so there is one person whose hair length is at least 10.

After seven days, the hair lengths of the people will be 10, 18, 8, 13, 9, respectively, and there will be three people whose hair length is at least 10.
After six days, there are only two people whose hair length is at least 10, not satisfying the condition, so print 7.

Sample Input 2

2 5 2
10 10

Sample Output 2

0

Since there are already two people whose hair length is at least 5 now, satisfying the condition, so print 0.

Sample Input 3

3 10 1
1 2 3

Sample Output 3

7

Problem Statement

A bus is in operation. The number of passengers on the bus is always a non-negative integer.

At some point in time, the bus had zero or more passengers, and it has stopped N times since then. At the i-th stop, the number of passengers increased by A_i. Here, A_i can be negative, meaning the number of passengers decreased by -A_i. Also, no passengers got on or off the bus other than at the stops.

Find the minimum possible current number of passengers on the bus that is consistent with the given information.

Constraints

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

Sample Input 1

4
3 -5 7 -4

Sample Output 1

3

If the initial number of passengers was 2, the current number of passengers would be 2 + 3 + (-5) + 7 + (-4) = 3, and the number of passengers on the bus would have always been a non-negative integer.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

0

Sample Input 3

4
-1 1000000000 1000000000 1000000000

Sample Output 3

3000000000

Problem Statement

For two strings A and B, let A+B denote the concatenation of A and B in this order.

You are given N strings S_1,\ldots,S_N. Modify and print them as follows, in the order i=1, \ldots, N:

• if none of S_1,\ldots,S_{i-1} is equal to S_i, print S_i;
• if X (X>0) of S_1,\ldots,S_{i-1} are equal to S_i, print S_i+ ( +X+ ), treating X as a string.

Constraints

• 1 \leq N \leq 2\times 10^5
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Sample Input 1

5
newfile
newfile
newfolder
newfile
newfolder

Sample Output 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

Sample Input 2

11
a
a
a
a
a
a
a
a
a
a
a

Sample Output 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

Problem Statement

We have a tree with N vertices numbered 1, 2, \dots, N.
The i-th edge (1 \leq i \leq N - 1) connects Vertex u_i and Vertex v_i and has a weight w_i.

For different vertices u and v, let f(u, v) be the greatest weight of an edge contained in the shortest path from Vertex u to Vertex v.

Find \displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j).

Constraints

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

Sample Input 1

3
1 2 10
2 3 20

Sample Output 1

50

We have f(1, 2) = 10, f(2, 3) = 20, and f(1, 3) = 20, so we should print their sum, or 50.

Sample Input 2

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

Sample Output 2

76

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges (a simple graph contains no self-loop and no multi-edges).
For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i bidirectionally.

Determine whether there is a way to paint each vertex black or white to satisfy both of the following conditions, and show one such way if it exists.

• At least one vertex is painted black.
• For every i = 1, 2, \ldots, K, the following holds:
  • the minimum distance between vertex p_i and a vertex painted black is exactly d_i.

Here, the distance between vertex u and vertex v is the minimum number of edges in a path connecting u and v.

Constraints

• 1 \leq N \leq 2000
• N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace
• 1 \leq u_i, v_i \leq N
• 0 \leq K \leq N
• 1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N
• 0 \leq d_i \leq N
• The given graph is simple and connected.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

Yes
10100

One way to satisfy the conditions is to paint vertices 1, 3 black and vertices 2, 4, 5 white.
Indeed, for each i = 1, 2, 3, 4, 5, let A_i denote the minimum distance between vertex i and a vertex painted black, and we have (A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2), where A_1 = 0, A_5 = 2.

Sample Input 2

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

Sample Output 2

No

There is no way to satisfy the conditions by painting each vertex black or white, so you should print No.

Sample Input 3

1 0
0

Sample Output 3

Yes
1

Problem Statement

Consider placing B black rooks and W white rooks on a grid with N horizontal rows and M vertical columns.

A placement of the rooks satisfying all of the following conditions is called a good placement.

• All B+W rooks are placed on the grid.
• At most one rook is placed in the same square.
• There is no pair of white rook and black rook attacking each other. That is, there is no pair of white rook and black rook such that one of them can reach the square in which the other is placed in one move.

Here, in one move, a rook can reach any square that is on a horizontal or vertical line from its current position and is reachable without jumping over another rook.

How many good placements are there? Since this count can be enormous, print it modulo 998244353.

Rooks in the same color are not distinguished.

Constraints

• 1 \leq N,M \leq 50
• 1 \leq B,W \leq 2500
• B+W \leq N \times M
• All values in input are integers.

Sample Input 1

2 2 1 1

Sample Output 1

4

There are four good placements as follows.

Sample Input 2

1 2 1 1

Sample Output 2

0

There may be no good placement.

Sample Input 3

40 40 30 30

Sample Output 3

467620384

Be sure to print the count modulo 998244353.