Problem Statement

Takahashi is planning to eat N dishes.

The i-th dish he plans to eat is sweet if S_i = sweet, and salty if S_i = salty.

If he eats two sweet dishes consecutively, he will feel sick and be unable to eat any more dishes.

Determine whether he can eat all the dishes.

Constraints

• N is an integer between 1 and 100, inclusive.
• Each S_i is sweet or salty.

Sample Input 1

5
salty
sweet
salty
salty
sweet

Sample Output 1

Yes

He will not eat two sweet dishes consecutively, so he can eat all the dishes without feeling sick.

Sample Input 2

4
sweet
salty
sweet
sweet

Sample Output 2

Yes

He will feel sick but can still eat all the dishes.

Sample Input 3

6
salty
sweet
sweet
salty
sweet
sweet

Sample Output 3

No

He feels sick when eating the 3rd dish and cannot eat the 4th and subsequent dishes.

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Cell (i, j) is empty if C_{i, j} is ., and not empty if C_{i, j} is #.

Takahashi is currently at cell (S_i, S_j), and he will act according to the following rules for i = 1, 2, \ldots, |X| in order.

• If the i-th character of X is L, and the cell to the left of his current cell exists and is empty, he moves to the cell to the left. Otherwise, he stays in the current cell.
• If the i-th character of X is R, and the cell to the right of his current cell exists and is empty, he moves to the cell to the right. Otherwise, he stays in the current cell.
• If the i-th character of X is U, and the cell above his current cell exists and is empty, he moves to the cell above. Otherwise, he stays in the current cell.
• If the i-th character of X is D, and the cell below his current cell exists and is empty, he moves to the cell below. Otherwise, he stays in the current cell.

Print the cell where he is after completing the series of actions.

Constraints

• 1 \leq H, W \leq 50
• 1 \leq S_i \leq H
• 1 \leq S_j \leq W
• H, W, S_i, S_j are integers.
• C_{i, j} is . or #.
• C_{S_i, S_j} = .
• X is a string of length between 1 and 50, inclusive, consisting of L, R, U, D.

Sample Input 1

2 3
2 1
.#.
...
ULDRU

Sample Output 1

2 2

Takahashi starts at cell (2, 1). His series of actions are as follows:

• The 1st character of X is U, and the cell above (2, 1) exists and is an empty cell, so he moves to the cell above, which is (1, 1).
• The 2nd character of X is L, and the cell to the left of (1, 1) does not exist, so he stays at (1, 1).
• The 3rd character of X is D, and the cell below (1, 1) exists and is an empty cell, so he moves to the cell below, which is (2, 1).
• The 4th character of X is R, and the cell to the right of (2, 1) exists and is an empty cell, so he moves to the cell to the right, which is (2, 2).
• The 5th character of X is U, and the cell above (2, 2) exists but is not an empty cell, so he stays at (2, 2).

Therefore, after completing the series of actions, he is at cell (2, 2).

Sample Input 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

Sample Output 2

2 4

Sample Input 3

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

Sample Output 3

1 1

Problem Statement

There are N dishes, and the i-th dish has a sweetness of A_i and a saltiness of B_i.

Takahashi plans to arrange these N dishes in any order he likes and eat them in that order.

He will eat the dishes in the arranged order, but he will stop eating as soon as the total sweetness of the dishes he has eaten exceeds X or the total saltiness exceeds Y.

Find the minimum possible number of dishes that he will end up eating.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq X, Y \leq 2 \times 10^{14}
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.

Sample Input 1

4 7 18
2 3 5 1
8 8 1 4

Sample Output 1

2

The i-th dish will be denoted as dish i.

If he arranges the four dishes in the order 2, 3, 1, 4, as soon as he eats dishes 2 and 3, their total sweetness is 8, which is greater than 7. Therefore, in this case, he will end up eating two dishes.

The number of dishes he will eat cannot be 1 or less, so print 2.

Sample Input 2

5 200000000000000 200000000000000
1 1 1 1 1
2 2 2 2 2

Sample Output 2

5

Sample Input 3

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

Sample Output 3

6

Problem Statement

There are N+Q points A_1,\dots,A_N,B_1,\dots,B_Q on a number line, where point A_i has a coordinate a_i and point B_j has a coordinate b_j.

For each j=1,2,\dots,Q, answer the following question:

• Let X be the point among A_1,A_2,\dots,A_N that is the k_j-th closest to point B_j. Find the distance between points X and B_j. More formally, let d_i be the distance between points A_i and B_j. Sort (d_1,d_2,\dots,d_N) in ascending order to get the sequence (d_1',d_2',\dots,d_N'). Find d_{k_j}'.

Constraints

• 1 \leq N, Q \leq 10^5
• -10^8 \leq a_i, b_j \leq 10^8
• 1 \leq k_j \leq N
• All input values are integers.

Sample Input 1

4 3
-3 -1 5 6
-2 3
2 1
10 4

Sample Output 1

7
3
13

Let us explain the first query.

The distances from points A_1, A_2, A_3, A_4 to point B_1 are 1, 1, 7, 8, respectively, so the 3rd closest to point B_1 is point A_3. Therefore, print the distance between point A_3 and point B_1, which is 7.

Sample Input 2

2 2
0 0
0 1
0 2

Sample Output 2

0
0

There may be multiple points with the same coordinates.

Sample Input 3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

Sample Output 3

11
66
59
54
88

Problem Statement

Takahashi has prepared N dishes for Snuke. The dishes are numbered from 1 to N, and dish i has a sweetness of A_i and a saltiness of B_i.

Takahashi can arrange these dishes in any order he likes. Snuke will eat the dishes in the order they are arranged, but if at any point the total sweetness of the dishes he has eaten so far exceeds X or the total saltiness exceeds Y, he will not eat any further dishes.

Takahashi wants Snuke to eat as many dishes as possible. Find the maximum number of dishes Snuke will eat if Takahashi arranges the dishes optimally.

Constraints

• 1 \leq N \leq 80
• 1 \leq A_i, B_i \leq 10000
• 1 \leq X, Y \leq 10000
• All input values are integers.

Sample Input 1

4 8 4
1 5
3 2
4 1
5 3

Sample Output 1

3

Consider the scenario where Takahashi arranges the dishes in the order 2, 3, 1, 4.

• First, Snuke eats dish 2. The total sweetness so far is 3, and the total saltiness is 2.
• Next, Snuke eats dish 3. The total sweetness so far is 7, and the total saltiness is 3.
• Next, Snuke eats dish 1. The total sweetness so far is 8, and the total saltiness is 8.
• The total saltiness has exceeded Y=4, so Snuke will not eat any further dishes.

Thus, in this arrangement, Snuke will eat three dishes.

No matter how Takahashi arranges the dishes, Snuke will not eat all four dishes, so the answer is 3.

Sample Input 2

2 1 1
3 2
3 2

Sample Output 2

1

Sample Input 3

2 100 100
3 2
3 2

Sample Output 3

2

Sample Input 4

6 364 463
230 381
154 200
328 407
339 94
193 10
115 309

Sample Output 4

3

Problem Statement

There is a graph with N + Q vertices, numbered 1, 2, \ldots, N + Q. Initially, the graph has no edges.

For this graph, perform the following operation for i = 1, 2, \ldots, Q in order:

• For each integer j satisfying L_i \leq j \leq R_i, add an undirected edge with cost C_i between vertices N + i and j.

Determine if the graph is connected after all operations are completed. If it is connected, find the cost of a minimum spanning tree of the graph.

A minimum spanning tree is a spanning tree with the smallest possible cost, and the cost of a spanning tree is the sum of the costs of the edges used in the spanning tree.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq N
• 1 \leq C_i \leq 10^9
• All input values are integers.

Sample Input 1

4 3
1 2 2
1 3 4
2 4 5

Sample Output 1

22

The following edges form a minimum spanning tree:

• An edge with cost 2 connecting vertices 1 and 5
• An edge with cost 2 connecting vertices 2 and 5
• An edge with cost 4 connecting vertices 1 and 6
• An edge with cost 4 connecting vertices 3 and 6
• An edge with cost 5 connecting vertices 3 and 7
• An edge with cost 5 connecting vertices 4 and 7

Since 2 + 2 + 4 + 4 + 5 + 5 = 22, print 22.

Sample Input 2

6 2
1 2 10
4 6 10

Sample Output 2

-1

The graph is disconnected.

Sample Input 3

200000 4
1 200000 1000000000
1 200000 998244353
1 200000 999999999
1 200000 999999999

Sample Output 3

199651870599998

Problem Statement

The Country of AtCoder consists of N cities and M roads connecting them, and one can travel between any two cities by traversing some roads. The cities are numbered from 1 to N, and the roads are numbered from 1 to M. Road i connects cities A_i and B_i bidirectionally.

Due to increasing traffic in the country, some roads are planned to be expanded. Currently, no roads have been expanded, and the cost to expand road i is C_i.

Since it is difficult to expand all roads at once, the plan is to first designate K out of the N cities as major cities and perform the minimum necessary expansion work so that one can travel between any two major cities using only expanded roads. It has already been decided that cities 1, 2, \dots, K-1 will be major cities, but the last major city has not yet been decided.

For each i=K, K+1, \dots, N, answer the following question:

• If city i is designated as the last major city, what is the minimum total cost of the expansion work required to ensure that one can travel between any two major cities using only expanded roads?

Constraints

• 2 \leq N \leq 4000
• N-1 \leq M \leq 8000
• 2\leq K \leq \min(N,\,10)
• 1 \leq A_i < B_i \leq N
• 1 \leq C_i \leq 10^9
• One can travel between any two cities by traversing some roads.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
6

In the above figure, circles with numbers represent cities with those numbers, and lines with numbers represent roads with the cost of expansion being that number. The left and right figures correspond to the cases i=3 and i=4, respectively. The colored circles represent the major cities, and the colored thick lines represent the roads that are expanded in an optimal solution.

• For i=3, expanding roads 4 and 5 results in a total cost of 2+1=3, which is the minimum.
• For i=4, expanding roads 1, 4, and 5 results in a total cost of 3+2+1=6, which is the minimum.

Sample Input 2

4 3 2
2 4 28
1 4 56
1 3 82

Sample Output 2

84
82
56

Sample Input 3

6 12 4
2 6 68
2 5 93
4 6 28
2 4 89
3 6 31
1 3 10
1 2 53
3 5 1
3 5 74
3 4 22
4 5 80
3 4 35

Sample Output 3

85
64
94

There may be multiple roads connecting the same pair of cities.