Problem Statement

You are given a string S consisting of lowercase English letters and .. Find the string obtained by removing all . from S.

Constraints

• S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters and ..

Sample Input 1

.v.

Sample Output 1

v

Removing all . from .v. yields v, so print v.

Sample Input 2

chokudai

Sample Output 2

chokudai

There are cases where S does not contain ..

Sample Input 3

...

Sample Output 3

There are also cases where all characters in S are ..

Problem Statement

You are given an integer N at least 100. Print the last two digits of N.

Strictly speaking, print the tens and ones digits of N in this order.

Constraints

• 100 \le N \le 999
• N is an integer.

Sample Input 1

254

Sample Output 1

54

The last two digits of 254 are 54, which should be printed.

Sample Input 2

101

Sample Output 2

01

The last two digits of 101 are 01, which should be printed.

Problem Statement

There is a road that stretches infinitely to the east and west, and the coordinate of a point located x meters to the east from a certain reference point on this road is defined as x. In particular, the coordinate of a point located x meters to the west from the reference point is -x.

Snuke will set up Christmas trees at points on the road at intervals of M meters, starting from a point with coordinate A. In other words, he will set up a Christmas tree at each point that can be expressed as A+kM using some integer k.

Takahashi and Aoki are standing at points with coordinates L and R (L\leq R), respectively. Find the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).

Constraints

• -10^{18}\leq A \leq 10^{18}
• 1\leq M \leq 10^9
• -10^{18}\leq L\leq R \leq 10^{18}
• All input values are integers.

Sample Input 1

5 3 -1 6

Sample Output 1

3

Snuke will set up Christmas trees at points with coordinates \dots,-4,-1,2,5,8,11,14\dots. Three of them at coordinates -1, 2, and 5 are between Takahashi and Aoki.

Sample Input 2

-2 2 1 1

Sample Output 2

0

Sometimes, Takahashi and Aoki are standing at the same point.

Sample Input 3

-177018739841739480 2436426 -80154573737296504 585335723211047198

Sample Output 3

273142010859

Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

• If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.

• If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length N consisting of o, x, and -.
• S_1,\ldots,S_N conform to the format described in the problem statement.

Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.

Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

Problem Statement

As KEYENCE headquarters have more and more workers, they decided to divide the departments in the headquarters into two groups and stagger their lunch breaks.

KEYENCE headquarters have N departments, and the number of people in the i-th department (1\leq i\leq N) is K_i.

When assigning each department to Group A or Group B, having each group take lunch breaks at the same time, and ensuring that the lunch break times of Group A and Group B do not overlap, find the minimum possible value of the maximum number of people taking a lunch break at the same time.
In other words, find the minimum possible value of the larger of the following: the total number of people in departments assigned to Group A, and the total number of people in departments assigned to Group B.

Constraints

• 2 \leq N \leq 20
• 1 \leq K_i \leq 10^8
• All input values are integers.

Sample Input 1

5
2 3 5 10 12

Sample Output 1

17

When assigning departments 1, 2, and 5 to Group A, and departments 3 and 4 to Group B, Group A has a total of 2+3+12=17 people, and Group B has a total of 5+10=15 people. Thus, the maximum number of people taking a lunch break at the same time is 17.

It is impossible to assign the departments so that both groups have 16 or fewer people, so print 17.

Sample Input 2

2
1 1

Sample Output 2

1

Multiple departments may have the same number of people.

Sample Input 3

6
22 25 26 45 22 31

Sample Output 3

89

For example, when assigning departments 1, 4, and 5 to Group A, and departments 2, 3, and 6 to Group B, the maximum number of people taking a lunch break at the same time is 89.

Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:

   • (x+1,y) if S_i is R;
   • (x-1,y) if S_i is L;
   • (x,y+1) if S_i is U;
   • (x,y-1) if S_i is D.

2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

• 1\leq N,M,H,K\leq 2\times 10^5
• S is a string of length N consisting of R, L, U, and D.
• |x_i|,|y_i| \leq 2\times 10^5
• (x_i, y_i) are pairwise distinct.
• All values in the input are integers, except for S.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

• 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

• 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

• 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

• 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

• 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

• 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.

Problem Statement

A shop sells N kinds of lunchboxes, one for each kind.
For each i = 1, 2, \ldots, N, the i-th kind of lunchbox contains A_i takoyaki (octopus balls) and B_i taiyaki (fish-shaped cakes).

Takahashi wants to eat X or more takoyaki and Y or more taiyaki.
Determine whether it is possible to buy some number of lunchboxes to get at least X takoyaki and at least Y taiyaki. If it is possible, find the minimum number of lunchboxes that Takahashi must buy to get them.

Note that just one lunchbox is in stock for each kind; you cannot buy two or more lunchboxes of the same kind.

Constraints

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

Sample Input 1

3
5 6
2 1
3 4
2 3

Sample Output 1

2

He wants to eat 5 or more takoyaki and 6 or more taiyaki.
Buying the second and third lunchboxes will get him 3 + 2 = 5 taiyaki and 4 + 3 = 7 taiyaki.

Sample Input 2

3
8 8
3 4
2 3
2 1

Sample Output 2

-1

Even if he is to buy every lunchbox, it is impossible to get at least 8 takoyaki and at least 8 taiyaki.
Thus, print -1.

Problem Statement

You are given an integer M and N pairs of integers (A_1, B_1), (A_2, B_2), \dots, (A_N, B_N).
For all i, it holds that 1 \leq A_i \lt B_i \leq M.

A sequence S is said to be a good sequence if the following conditions are satisfied:

• S is a contiguous subsequence of the sequence (1,2,3,..., M).
• For all i, S contains at least one of A_i and B_i.

Let f(k) be the number of possible good sequences of length k.
Enumerate f(1), f(2), \dots, f(M).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq M
• All values in input are integers.

Sample Input 1

3 5
1 3
1 4
2 5

Sample Output 1

0 1 3 2 1

Here is the list of all possible good sequences.

• (1,2)
• (1,2,3)
• (2,3,4)
• (3,4,5)
• (1,2,3,4)
• (2,3,4,5)
• (1,2,3,4,5)

Sample Input 2

1 2
1 2

Sample Output 2

2 1

Sample Input 3

5 9
1 5
1 7
5 6
5 8
2 6

Sample Output 3

0 0 1 2 4 4 3 2 1

Problem Statement

There are N points labeled 1, 2, \dots, N on the xy-plane. Point i is located at coordinates (X_i, Y_i).
You can perform the following operation between 0 and K times, inclusive.

• First, choose one of the N points. Let k be the selected point, and assume it is currently at (x, y).
• Next, choose and execute one of the following four actions:
  • Move point k along the x-axis by +1. The coordinates of point k become (x+1, y).
  • Move point k along the x-axis by -1. The coordinates of point k become (x-1, y).
  • Move point k along the y-axis by +1. The coordinates of point k become (x, y+1).
  • Move point k along the y-axis by -1. The coordinates of point k become (x, y-1).
• It is allowed to have multiple points at the same coordinates. Note that the input may already have multiple points at the same coordinates.

After all your operations, draw one square that includes all the N points inside or on the circumference, with each side parallel to the x- or y-axis.
Find the minimum possible value for the length of a side of this square. This value can be shown to be an integer since all points are always on lattice points.

In particular, if all points can be made to exist at the same coordinates, the answer is considered to be 0.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 0 \le K \le 4 \times 10^{14}
• 0 \le X_i, Y_i \le 10^9

Sample Input 1

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

Sample Output 1

3

The figure below illustrates this case with the horizontal x-axis and the vertical y-axis.

For example, after performing four moves following the arrows in the figure, you can include all points inside or on the circumference of the square shown in the figure with a side length of 3, and this can be shown to be the minimum value.

Sample Input 2

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Sample Output 2

0

All points already exist at the same coordinates from the beginning.
For example, by performing zero operations, all points can be made to exist at the same coordinates, so the answer for this input is 0.

Sample Input 3

10 998244353
489733278 189351894
861289363 30208889
450668761 133103889
306319121 739571083
409648209 922270934
930832199 304946211
358683490 923133355
369972904 539399938
915030547 735320146
386219602 277971612

Sample Output 3

484373824