Problem Statement

You are given a 3-character string S, which is a concatenation of integers a and b between 1 and 9 (inclusive) and the character x in this order: axb.

Find the product of a and b.

Constraints

• The length of S is 3.
• The 1-st and 3-rd characters are digits between 1 and 9 (inclusive).
• The 2-nd character is x.

Sample Input 1

3x7

Sample Output 1

21

We have 3 \times 7 = 21, which should be printed.

Sample Input 2

9x9

Sample Output 2

81

Sample Input 3

1x1

Sample Output 3

1

Problem Statement

Three people live in Takahashi's house: Takahashi, his father, and his mother. All of them wash their hair in the bathroom each night.
His father, his mother, and Takahashi take a bath in this order and use A, B, and C milliliters of shampoo, respectively.

This morning, the bottle contained V milliliters of shampoo. Without refilling, who will be the first to run short of shampoo to wash their hair?

Constraints

• 1 \leq V,A,B,C \leq 10^5
• All values in input are integers.

Sample Input 1

25 10 11 12

Sample Output 1

T

Now, they have 25 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 15.
• Next, Takahashi's mother uses 11 milliliters, leaving 4.
• Finally, Takahashi tries to use 12 milliliters and runs short of shampoo since only 4 is remaining.

Sample Input 2

30 10 10 10

Sample Output 2

F

Now, they have 30 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 20.
• Next, Takahashi's mother uses 10 milliliters, leaving 10.
• Then, Takahashi uses 10 milliliters, leaving 0.
• Next day, Takahashi's father tries to use 10 milliliters and runs short of shampoo since only 0 is remaining.

Sample Input 3

100000 1 1 1

Sample Output 3

M

Problem Statement

You are given a sequence of 26 integers P=(P_1,P_2, \ldots ,P_{26}) consisting of integers from 1 through 26. It is guaranteed that all elements in P are distinct.

Print a string S of length 26 that satisfies the following condition.

• For every i (1 \leq i \leq 26), the i-th character of S is the lowercase English letter that comes P_i-th in alphabetical order.

Constraints

• 1 \leq P_i \leq 26
• P_i \neq P_j (i \neq j)
• All values in input are integers.

Sample Input 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 1

abcdefghijklmnopqrstuvwxyz

Sample Input 2

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 2

bacdefghijklmnopqrstuvwxyz

Sample Input 3

5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21

Sample Output 3

eklpyqragjdwtcbxzsnifvhmou

Problem Statement

Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.

We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.

The following two operations are called a vertical shift and horizontal shift.

• For each j=1, 2, \dots, W, simultaneously do the following:
  • simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
• For each i = 1, 2, \dots, H, simultaneously do the following:
  • simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.

Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.

• After applying a vertical shift s times and a horizontal shift t times, A is equal to B.

Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.

Constraints

• 2 \leq H, W \leq 30
• A_{i,j} is # or ., and so is B_{i,j}.
• H and W are integers.

Sample Input 1

4 3
..#
...
.#.
...
#..
...
.#.
...

Sample Output 1

Yes

By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.

..#
...
.#.
...

We first apply a vertical shift to make A as follows.

...
.#.
...
..#

Then we apply another vertical shift to make A as follows.

.#.
...
..#
...

Finally, we apply a horizontal shift to make A as follows, which equals B.

#..
...
.#.
...

Sample Input 2

3 2
##
##
#.
..
#.
#.

Sample Output 2

No

No choice of (s, t) makes A equal B.

Sample Input 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

Sample Output 3

Yes

Sample Input 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

Sample Output 4

Yes

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

• Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

• 1\leq H \leq 100
• 2\leq W \leq 100
• H and W are integers.
• S_i is a string of length W consisting of . and T.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC

Problem Statement

You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.

Process Q queries. Each query is of one of the following two types.

• 1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.
• 2 x: Print the x-th character of S.

Constraints

• 2 \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le x \le N
• |S|=N
• S consists of lowercase English letters.
• At least one query in the format 2 x.
• N, Q, x are all integers.

Sample Input 1

3 3
abc
2 2
1 1
2 2

Sample Output 1

b
a

In the 1-st query, S is abc, so the 2-nd character b should be printed. In the 2-nd query, S is changed from abc to cab. In the 3-rd query, S is cab, so the 2-nd character a should be printed.

Sample Input 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Sample Output 2

c
u
c
u

Problem Statement

There are N trampolines on a two-dimensional planar town where Takahashi lives. The i-th trampoline is located at the point (x_i, y_i) and has a power of P_i. Takahashi's jumping ability is denoted by S. Initially, S=0. Every time Takahashi trains, S increases by 1.

Takahashi can jump from the i-th to the j-th trampoline if and only if:

• P_iS\geq |x_i - x_j| +|y_i - y_j|.

Takahashi's objective is to become able to choose a starting trampoline such that he can reach any trampoline from the chosen one with some jumps.

At least how many times does he need to train to achieve his objective?

Constraints

• 2 \leq N \leq 200
• -10^9 \leq x_i,y_i \leq 10^9
• 1 \leq P_i \leq 10^9
• (x_i, y_i) \neq (x_j,y_j)\ (i\neq j)
• All values in input are integers.

Sample Input 1

4
-10 0 1
0 0 5
10 0 1
11 0 1

Sample Output 1

2

If he trains twice, S=2, in which case he can reach any trampoline from the 2-nd one.

For example, he can reach the 4-th trampoline as follows.

• Jump from the 2-nd to the 3-rd trampoline. (Since P_2 S = 10 and |x_2-x_3| + |y_2-y_3| = 10, it holds that P_2 S \geq |x_2-x_3| + |y_2-y_3|.)

• Jump from the 3-rd to the 4-th trampoline. (Since P_3 S = 2 and |x_3-x_4| + |y_3-y_4| = 1, it holds that P_3 S \geq |x_3-x_4| + |y_3-y_4|.)

Sample Input 2

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

Sample Output 2

18

Problem Statement

Takahashi has N pieces of chocolate. The i-th piece has a rectangular shape with a width of A_i centimeters and a length of B_i centimeters.
He also has M boxes. The i-th box has a rectangular shape with a width of C_i centimeters and a length of D_i centimeters.

Determine whether it is possible to put the N pieces of chocolate in the boxes under the conditions below.

• A box can contain at most one piece of chocolate.
• A_i \leq C_j and B_i \leq D_j must hold when putting the i-th piece of chocolate in the j-th box (they cannot be rotated).

Constraints

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

Sample Input 1

2 3
2 4
3 2
8 1 5
2 10 5

Sample Output 1

Yes

We can put the first piece of chocolate in the third box and the second piece in the first box.

Sample Input 2

2 2
1 1
2 2
100 1
100 1

Sample Output 2

No

A box can contain at most one piece of chocolate.

Sample Input 3

1 1
10
100
100
10

Sample Output 3

No

Sample Input 4

1 1
10
100
10
100

Sample Output 4

Yes

Problem Statement

You are in a store to buy N items. The regular price of the i-th item is P_i yen (the currency in Japan).

You have M coupons. You can use the i-th coupon to buy an item whose regular price is at least L_i yen at a D_i-yen discount.

Here, each coupon can be used only once. Besides, multiple coupons cannot be used for the same item.

If no coupon is used for an item, you will buy it for a regular price. Find the minimum possible total amount of money required to buy all the N items.

Constraints

• 1\leq N,M\leq 2\times 10^5
• 1\leq P_i\leq 10^9
• 1\leq D_i \leq L_i \leq 10^9
• All input values are integers.

Sample Input 1

3 3
4 3 1
4 4 2
2 3 1

Sample Output 1

4

Consider using the 2-nd coupon for the 1-st item, and the 3-rd coupon for the 2-nd item.

Then, you buy the 1-st item for 4-3=1 yen, 2-nd item for 3-1=2 yen, and 3-rd item for 1 yen. Thus, you can buy all the items for 1+2+1=4 yen.

Sample Input 2

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

Sample Output 2

37