Problem Statement

A dollar is worth A yen.

Determine if B dollars are worth more than C yen.

Constraints

• A, B, and C are integers between 1 and 1000, inclusive.

Sample Input 1

5 3 14

Sample Output 1

Yes

5 dollars are worth 15 yen, which is worth more than 14 yen.

Sample Input 2

1 1 1

Sample Output 2

No

Note that No should be printed if they are equal in value.

Sample Input 3

10 10 200

Sample Output 3

No

Problem Statement

Trains from AtCoder station have two destinations: Takahashi station and Aoki station.

You are given information on N trains. The i-th train (1\leq i\leq N) is described by a pair (S _ i,T _ i) of a string and a positive integer. It means that the train for station S _ i arrives at AtCoder station T _ i minutes later, where S _ i is equal to either Aoki or Takahashi.

You are going to take the train for Takahashi station that arrives earliest at AtCoder station. Which train are you taking?

Constraints

• 1\leq N\leq2\times10 ^ 5
• S _ i is equal to either Aoki or Takahashi (1\leq i\leq N).
• 1\leq T _ i\leq10 ^ 9\ (1\leq i\leq N)
• If i\neq j, then T _ i\neq T _ j\ (1\leq i,j\leq N).
• There exists i with S _ i={}Takahashi.
• N and T _ i\ (1\leq i\leq N) are all integers.

Sample Input 1

5
Aoki 2
Takahashi 3
Takahashi 5
Aoki 10
Takahashi 15

Sample Output 1

2

Information on five trains arriving at AtCoder station is given. Three of them are for Takahashi station: the 2-nd train arriving three minutes later, the 3-rd train arriving five minutes later, and the 5-th train arriving 15 minutes later.

The 2-nd train arrives earliest among them, so 2 should be printed.

Sample Input 2

8
Aoki 748
Aoki 436
Aoki 170
Aoki 587
Aoki 972
Aoki 331
Takahashi 532
Takahashi 523

Sample Output 2

8

Note that the given arrival times may not be sorted.

Problem Statement

You are given a string S consisting of lowercase English letters and exactly two X's.
Apply the following operation and print the resulting string.

Reverse the part between the two X's in S, namely the part starting from the character right after the first X through the character right before the second X, which may be empty. Then, remove the two X's and concatenate the remaining strings without changing their order to form a single string.

The string T' obtained by reversing a string T is defined as the string whose length equals that of T, where the i-th (1\leq i\leq \lvert T\rvert) character of T' equals the (\lvert T\rvert+1-i)-th character of T. Here, \lvert T\rvert denotes the length of the string T.

Constraints

• S is a string of length between 3 and 100, inclusive, consisting of lowercase English letters and X.
• X occurs exactly twice in S.

Sample Input 1

stXnirXg

Sample Output 1

string

The substring between the two X's is nir; reversing this part makes it stXrinXg.
After removing the two X's and concatenating the remaining strings preserving the order, it results in string.

Sample Input 2

samXXple

Sample Output 2

sample

Note that reversing an empty string makes it an empty string.

Sample Input 3

XesreverX

Sample Output 3

reverse

Problem Statement

There is a grid with N horizontal rows and N vertical columns.
Each cell in the grid has the character v written in various orientations. The orientation of v written on the cell in the i-th row from the top and j-th column from the left is described by c_{i, j}:

• if c_{i,j} = v, an ordinary v is written;
• if c_{i,j} = ^, an upside-down v is written;
• if c_{i,j} = <, a v rotated 90 degrees clockwise is written;
• if c_{i,j} = >, a v rotated 90 degrees counterclockwise is written.

Now you will rotate the grid 90 degrees clockwise.
Print the orientations of the characters in the resulting grid.

Constraints

• 1 \leq N \leq 100
• c_{i, j} is one of v, ^, <, or >.

Sample Input 1

1
v

Sample Output 1

<

Rotating v 90 degrees clockwise makes it <.

Sample Input 2

3
>>^
><>
v<^

Sample Output 2

<vv
^^v
>v>

Sample Input 3

5
^^>vv
v>^^v
<vv<v
>^><>
>>^v>

Sample Output 3

vv^<>
v><v>
>v<>v
<^^><
vv<<<

Problem Statement

Apples are dropping onto a number line.
A_i apples will drop onto the coordinate i for each i=1,2,\ldots,N; no other apples will drop.

You have a basket of width W.
You may freely choose an integer L to place the basket, aligning its left end at L, so that it collects apples falling onto the coordinates between L and L+W-1, inclusive.

At most how many apples can you collect?

Constraints

• 1 \leq W \leq N \leq 10^6
• 0 \leq A_i \leq 10^3
• All input values are integers.

Sample Input 1

5 3
3 1 4 1 5

Sample Output 1

10

If you set L=3, the basket collects 4+1+5=10 apples falling onto coordinates 3,4,5. This is the maximum.

Sample Input 2

10 10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

10

Sample Input 3

12 4
314 159 265 358 979 323 846 264 338 327 950 288

Sample Output 3

2506

Problem Statement

N students took a final exam. Each student has a student ID, which is a unique integer between 1 and N.

The student with ID i (1\leq i\leq N) marked E _ i points in English and M _ i points in math.

The students' ranks are determined based on their scores by the following criteria:

• Those with higher total (English and math) scores rank higher.
• Among those with the same total score, those with higher math scores rank higher.
• Among those with the same total score and math score, those with larger IDs rank higher.

Print the student IDs in the order of their ranks.

Constraints

• 1\leq N\leq100
• 0\leq E _ i\leq100\ (1\leq i\leq N)
• 0\leq M _ i\leq100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

4
80 70
40 100
60 80
60 80

Sample Output 1

1 2 4 3

Student 1 marked the highest total score of 150 points. Thus, student 1 ranks highest.

The other students marked the same total score of 140 points. Among them, student 2 marked the highest math score of 100 points. Thus, student 2 ranks the next.

Student 3 and 4 marked the same total and math scores. Among them, those with larger IDs rank higher. Thus, student 4 ranks the next, and student 3 ranks lowest.

Hence, 1 2 4 3 should be printed.

Sample Input 2

1
1 1

Sample Output 2

1

There may be only one student.

Sample Input 3

12
72 7
54 25
97 48
37 47
34 54
4 16
62 1
59 22
99 73
34 75
6 45
82 84

Sample Output 3

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

Problem Statement

There are N bowls of rice and M slices of bread. The i-th bowl of rice has a deliciousness of R_i, and the i-th slice of bread has a deliciousness of P_i.

For the next K days, you will choose to eat either rice or bread. You will get tired of it if you eat the same dish in a row, so you will never eat rice two days in a row, or eat bread two days in a row.

Determine if this plan is feasible. If it is, find the maximum possible total deliciousness.

Constraints

• 1\leq N,M \leq 1000
• 1\leq K \leq N+M
• 1\leq R_i, P_i \leq 1000
• All input values are integers.

Sample Input 1

3 3 3
2 5 4
3 6 1

Sample Output 1

15

By eating the third bowl of rice on day 1, the second slice of bread on day 2, and the second bowl of rice on day 3, the total deliciousness will be 15.

Sample Input 2

2 4 6
2 4
10 4 4 2

Sample Output 2

-1

The meal plan for the next K days is infeasible.

Problem Statement

N people came to use a hot spring. The i-th person will be satisfied if they bathe in a hot spring with temperature between L_i and R_i degrees, inclusive.

You can prepare any number of hot springs at any temperature. However, each hot spring can have only one set temperature.

At least how many hot springs do you need to prepare so that all the N people are satisfied?

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq L_i \leq R_i \leq 10^{9}
• All input values are integers.

Sample Input 1

5
37 40
43 45
40 42
35 39
39 43

Sample Output 1

3

If you prepare three hot springs at 39, 41, and 45 degrees, everyone will be satisfied. However, you can never satisfy everyone by preparing two hot springs or less. Thus, 3 should be printed.

Sample Input 2

7
27 50
40 43
55 60
25 30
33 49
35 39
32 45

Sample Output 2

4

Problem Statement

There is a grid with two horizontal rows and four vertical columns.
Each cell has a number written on it; the cell in the i-th row from the top and j-th column from the left has (i-1) \times 4 + j written on it.
You may perform the following two kinds of operations any number of times in any order.

• Choose two horizontally adjacent cells, and swap the numbers written on them.
• Choose two vertically adjacent cells, and swap the numbers written on them.

You are given A_{i,j} (1 \leq i \leq 2, 1 \leq j \leq 4) as the input.
At least how many operations are required to make the grid satisfy the following condition?

• For all i and j, A_{i,j} is written on the cell in the i-th row from the top and j-th column from the left.

Constraints

• 1 \leq A_{i,j} \leq 8
• A_{i,j} are distinct.
• All input values are integers.

Sample Input 1

5 2 4 3
1 6 7 8

Sample Output 1

2

For example, the condition in the problem statement can be satisfied with two operations as follows:

• Swap the number written on the cell in the 1-st row from the top and 1-st column from the left, and the number written on the cell in the 2-nd row from the top and 1-st column from the left.
• Swap the number written on the cell in the 1-st row from the top and 3-rd column from the left, and the number written on the cell in the 1-st row from the top and 4-th column from the left.

The condition cannot be satisfied with one operation or less, so 2 is the answer.

Sample Input 2

1 2 3 4
5 6 7 8

Sample Output 2

0

Sample Input 3

7 4 5 8
2 6 3 1

Sample Output 3

8

Problem Statement

There is an N \times N grid with N horizontal rows and N vertical columns. Let (i, j) denote the cell in the i-th row from the top and j-th column from the left. Initially, each cell is painted black or white; cell (i, j) is painted black if S_{i, j} is #, and white if S_{i, j} is ..

You will repeatedly choose one cell to paint black so that the grid satisfies the following condition:

• for any cell (x, y) painted white, at most two of cells (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1) (except for non-existent ones) are painted black.

At least how many operations are required to meet the condition?

Constraints

• 1 \leq N \leq 2000
• S_{i, j} is . or #.

Sample Input 1

3
###
#.#
###

Sample Output 1

1

Cell (2, 2) is painted white, and all of the four adjacent cells are painted black. By repainting cell (2, 2) black, the grid satisfies the condition.

Sample Input 2

3
...
#.#
.#.

Sample Output 2

1

By repainting cell (2, 2) black, the grid satisfies the condition.

Sample Input 3

5
#####
#....
#.###
#...#
#####

Sample Output 3

8

The grid satisfies the condition only when all the white cells are repainted black.

Problem Statement

Consider a 4\times 4 grid with a number written on each cell. Let (i,j) be the cell in the i-th row from the top and j-th column from the left, and a_{i,j} be the number written on it. We say this grid is good if both of the following conditions are met:

• The numbers written on each row increase strictly monotonically from left to right. That is, a_{i,j} < a_{i,j+1} for all i,j\ (1\leq i\leq N, 1\leq j< N).
• The numbers written on each column increase strictly monotonically from top to bottom. That is, a_{i,j} < a_{i+1,j} for all i,j\ (1\leq i< N, 1\leq j\leq N).

You are given an integer A_{i,j} for each 1\leq i,j\leq 4. Find the number, modulo 998244353, of good grids such that:

• an integer between 1 and M, inclusive, is written on each cell, and
• for 1\leq i,j\leq 4, if A_{i,j}\neq -1, then A_{i,j} is written on cell (i,j).

Constraints

• 1\leq M \leq 30
• A_{i,j}=-1 or 1\leq A_{i,j}\leq M.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

Two grids satisfy the conditions:

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

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

Sample Input 2

30
1 1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

Sample Output 2

0

Sample Input 3

21
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1

Sample Output 3

248851853

Be sure to find the count modulo 998244353.

Problem Statement

You are given a tree with N vertices. The i-th edge connects vertices A_i and B_i.

The distance between two vertices x and y on the tree is the minimum possible number of edges in a path from x to y. The diameter of the tree is the maximum distance between two vertices.

Let D be the diameter of this tree. Find the number of pairs of vertices (a, b) \ (a < b) such that the distance between a and b equals D.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is a tree.

Sample Input 1

5
1 2
1 3
1 4
4 5

Sample Output 1

2

The diameter of this tree is 3. The pairs of vertices distant by 3 are (2, 5) and (3, 5). Thus, 2 should be printed.

Sample Input 2

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

Sample Output 2

4

Problem Statement

You are given a length-N sequence of positive integers A=(A_1,A_2,\dots,A_N). Among the N(N-1) integers (including duplicates) obtained by choosing two distinct elements from A and concatenating them as strings, find the median, or the \left( N(N-1)/2 \right)-th smallest value.

Constraints

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

Sample Input 1

3
1 23 45

Sample Output 1

231

By choosing two distinct elements from A=(1, 23, 45) and concatenating them as strings, six integers can be obtained: (123, 145, 231, 451, 2345, 4523). Print the 3-rd smallest integer 231.

Sample Input 2

3
2 2 4

Sample Output 2

24

By choosing two distinct elements from A=(2, 2, 4) and concatenating them as strings, six integers can be obtained: (22, 22, 24, 24, 42, 42). Print the 3-rd smallest integer 24.

Sample Input 3

2
100000000 100000000

Sample Output 3

100000000100000000

Note that the answer may not fit into a 32-bit integer type.

Problem Statement

There is a 10^9 \times 10^9 grid. Let (i, j) denote the cell in the i-th row from the top and j-th column from the left.
The hero is initially at (1, 1). He can move to one of the four adjacent cells: up, down, left, or right. Once he reaches cell (A, B), the hero powers up, after which he can move to one of the eight adjacent cells.

• The eight cells adjacent to (i, j) are (i-1, j-1), (i-1, j), (i-1, j+1), (i,j-1), (i,j+1), (i+1,j-1), (i+1,j), (i+1,j+1) (except for non-existent ones).

Besides, there are N coins. Coin i is at cell (C_i, D_i). He can collect the coin when he reaches the cell.
He wants to collect all the coins. At least how many moves are required to collect them?

Constraints

• 1 \leq N \leq 16
• 1 \leq A, B, C_i, D_i \leq 10^9
• (1, 1), (A, B), (C_1, D_1), \dots, (C_N, D_N) are pairwise distinct.
• All input values are integers.

Sample Input 1

3 5 2
4 1
1 7
6 3

Sample Output 1

11

The hero can make the following 11 moves to collect all the coins.

• The hero is initially at (1, 1).
• He makes three moves to collect the coin at (4, 1).
• He makes two moves to reach (5, 2) and power up.
• He makes one move to collect the coin at (6, 3).
• He makes five moves to collect the coin at (1, 7).

Since he cannot collect all the coins with 10 moves or less, the answer is 11.

Sample Input 2

3 500000000 500000000
1 1000000000
1000000000 1
1000000000 1000000000

Sample Output 2

2999999997

Sample Input 3

8 36 49
73 52
38 86
30 52
85 48
27 60
45 40
65 98
71 37

Sample Output 3

228

Problem Statement

There is an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Initially, all elements of A are 0. At time i=1,2,\ldots,T, the following operation is performed against A:

• add V_i to each of A_{L_i},A_{L_i+1},\dots, and A_{R_i}.

Given Q queries, process them in order. The i-th query is described as follows.

• Given integers l_i,r_i, and x_i, print the first time that A_{l_i}+A_{l_i+1}+\dots+A_{r_i} becomes x_i or greater. If A_{l_i}+A_{l_i+1}+\dots+A_{r_i} is less than x_i at time T, print -1.

Constraints

• 1\leq N\leq 10^5
• 1\leq T,Q\leq 10^5
• 1\leq L_i\leq R_i\leq N
• 1\leq V_i\leq 10^5
• 1\leq l_i\leq r_i\leq N
• 1\leq x_i\leq 10^{15}
• All input values are integers.

Sample Input 1

6 3 4
3 5 3
1 4 2
2 6 4
2 5 15
3 4 5
6 6 5
1 6 30

Sample Output 1

2
1
-1
3

The sequence A transitions as follows:

• Time 1: (0,0,3,3,3,0).
• Time 2: (2,2,5,5,3,0).
• Time 3: (2,6,9,9,7,4).

The answer to each query is as follows.

• Query 1: the value A_2+A_3+A_4+A_5 becomes 15 or greater for the first time at time 2.
• Query 2: the value A_4+A_5 becomes 5 or greater for the first time at time 1.
• Query 3: the value A_6 at time 3 is less than 5, so -1 should be printed.
• Query 4: the value A_1+A_2+A_3+A_4+A_5+A_6 becomes 30 or greater for the first time at time 3.

Sample Input 2

100 10 10
54 77 89179
3 23 9999
35 58 58890
38 66 74496
27 49 86313
12 59 86105
23 91 9688
55 74 55468
53 61 36846
4 46 25191
23 48 6659862
6 59 2233031
38 73 9618591
65 86 801679
20 73 3689737
2 19 1320865
27 100 13177888
27 65 762017
80 96 6436
35 66 7954927

Sample Output 2

-1
4
9
1
4
-1
-1
1
7
6