Problem Statement

In the Kingdom of AtCoder, there is a standardized test of competitive programming proficiency.

An examinee will get a score out of 100 and obtain a rank according to the score, as follows:

• Novice, for a score not less than 0 but less than 40;
• Intermediate, for a score not less than 40 but less than 70;
• Advanced, for a score not less than 70 but less than 90;
• Expert, for a score not less than 90.

Takahashi took this test and got X points.

Find the minimum number of extra points needed to go up one rank higher. If, however, his rank was Expert, print expert, as there is no higher rank than that.

Constraints

• 0 \leq X \leq 100
• X is an integer.

Sample Input 1

56

Sample Output 1

14

He got 56 points and was certified as Intermediate. In order to reach the next rank of Advanced, he needs at least 14 more points.

Sample Input 2

32

Sample Output 2

8

Sample Input 3

0

Sample Output 3

40

Sample Input 4

100

Sample Output 4

expert

He got full points and was certified as Expert. There is no rank higher than that, so print expert.

Problem Statement

You are given three strings S_1, S_2, S_3 consisting of lowercase English letters, and a string T consisting of 1, 2, 3.

Concatenate the three strings according to the characters in T and print the resulting string. Formally, conform to the following instructions.

• For each integer i such that 1 \leq i \leq |T|, let the string s_i be defined as follows:
  • S_1, if the i-th character of T is 1;
  • S_2, if the i-th character of T is 2;
  • S_3, if the i-th character of T is 3.
• Concatenate the strings s_1, s_2, \dots, s_{|T|} in this order and print the resulting string.

Constraints

• 1 \leq |S_1|, |S_2|, |S_3| \leq 10
• 1 \leq |T| \leq 1000
• S_1, S_2, and S_3 consist of lowercase English letters.
• T consists of 1, 2, and 3.

Sample Input 1

mari
to
zzo
1321

Sample Output 1

marizzotomari

We have s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari. Concatenate these and print the resulting string: marizzotomari.

Sample Input 2

abra
cad
abra
123

Sample Output 2

abracadabra

Sample Input 3

a
b
c
1

Sample Output 3

a

Problem Statement

Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.

The new alphabetical order is represented by a string X, which is a permutation of a, b, \ldots, z. The i-th character of X (1 \leq i \leq 26) would be the i-th smallest English lowercase letter in the new order.

The kingdom has N citizens, whose names are S_1, S_2, \dots, S_N, where each S_i (1 \leq i \leq N) consists of lowercase English letters.
Sort these names lexicographically according to the alphabetical order decided by Takahashi.

Constraints

• X is a permutation of a, b, \ldots, z.
• 2 \leq N \leq 50000
• N is an integer.
• 1 \leq |S_i| \leq 10 \, (1 \leq i \leq N)
• S_i consists of lowercase English letters. (1 \leq i \leq N)
• S_i \neq S_j (1 \leq i \lt j \leq N)

Sample Input 1

bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

Sample Output 1

bzz
bzy
abx
caa

In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.

Sample Input 2

zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

Sample Output 2

b
a
ac
ab
abc

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

There are villages at some number of points in the xy-plane.
Takahashi will construct a moat to protect these villages from enemies such as civil armies and witches.

You are given a 4 \times 4 matrix A = (A_{i, j}) consisting of 0 and 1.
For each pair of integers (i, j) (1 \leq i, j \leq 4) such that A_{i, j} = 1, there is a village at the coordinates (i-0.5, j-0.5).

The moat will be a polygon in the plane. Takahashi will construct it so that the following conditions will be satisfied. (See also the annotation at Sample Input/Output 1.)

1. There is no self-intersection.
2. All villages are contained in the interior of the polygon.
3. The x- and y-coordinates of every vertex are integers between 0 and 4 (inclusive).
4. Every edge is parallel to the x- or y-axis.
5. Every inner angle is 90 or 270 degrees.

Print the number of ways in which Takahashi can construct the moat.

Constraints

• A_{i, j} \in \lbrace 0, 1\rbrace
• There is at least one pair (i, j) such that A_{i, j} = 1.

Sample Input 1

1 0 0 0
0 0 1 0
0 0 0 0
1 0 0 0

Sample Output 1

1272

The two ways to construct the moat shown in the images below are valid.

The four ways to construct the moat shown in the images below are invalid.

Here are the reasons the above ways are invalid.

• The first way violates the condition: "There is no self-intersection."
• The second way violates the condition: "All villages are contained in the interior of the polygon."
• The third way violates the condition: "The x- and y-coordinates of every vertex are integers between 0 and 4." (Some vertices have non-integer coordinates.)
• The fourth way violates the condition: "Every edge is parallel to the x- or y-axis."

Sample Input 2

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Sample Output 2

1

Problem Statement

There is a cleaning robot on the square (0, 0) in an infinite two-dimensional grid.

The robot will be given a program represented as a string consisting of four kind of characters L, R, U, D.
It will read the characters in the program from left to right and perform the following action for each character read.

1. Let (x, y) be the square where the robot is currently on.
2. Make the following move according to the character read:
   • if L is read: go to (x-1, y).
   • if R is read: go to (x+1, y).
   • if U is read: go to (x, y-1).
   • if D is read: go to (x, y+1).

You are given a string S consisting of L, R, U, D. The program that will be executed by the robot is the concatenation of K copies of S.

Squares visited by the robot at least once, including the initial position (0, 0), will be cleaned.
Print the number of squares that will be cleaned at the end of the execution of the program.

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of L, R, U, D.
• 1 \leq K \leq 10^{12}

Sample Input 1

RDRUL
2

Sample Output 1

7

The robot will execute the program RDRULRDRUL. It will start on (0, 0) and travel as follows:
(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (2, 0) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 0) \rightarrow (2, 0).
In the end, seven squares will get cleaned: (0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1).

Sample Input 2

LR
1000000000000

Sample Output 2

2

Sample Input 3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

Sample Output 3

219911485785

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The N vertices are called Vertex 1, Vertex 2, \ldots, Vertex N.
For each i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.
Additionally, for each i = 1, 2, \ldots, N, Vertex i has an integer i written on it.

You are also given Q queries.
For each i = 1, 2, \ldots, Q, the i-th query is represented as an integer x_i. This query involves the following operation.

1. Let X be the integer written on Vertex x_i.
2. For every vertex adjacent to Vertex x_i, replace the integer written on it with X.

Here, Vertex u and Vertex v are said to be adjacent when there is an edge connecting them.

Print the integer written on each vertex after all queries are processed in the order they are given from input.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min(2 \times 10^5, N(N-1)/2)
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N
• 1 \leq x_i \leq N
• The given graph is simple. In other words, it has no self-loops and no multi-edges.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1 3 3 3 3

Each query involves the following operation.

• The first query (x_1 = 1): Vertex 1 has the integer 1 written on it, and the vertices adjacent to Vertex 1 are Vertices 2 and 5. Thus, the integers on Vertices 2 and 5 get replaced with 1.
• The second query (x_2 = 3): Vertex 3 has the integer 3 written on it, and the vertices adjacent to Vertex 3 are Vertices 2 and 4. Thus, the integers on Vertices 2 and 4 get replaced with 3.
• The third query (x_3 = 4): Vertex 4 has the integer 3 written on it, and the vertices adjacent to Vertex 4 are Vertices 2, 3, and 5. Thus, the integers on Vertices 2, 3, and 5 get replaced with 3. (Vertices 2 and 3 already have 3 written on them, so the actual change takes place only on Vertex 5.)

Sample Input 2

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

Sample Output 2

1 6 1 1 6 6 1 9 9 10 11 12 10 14

Problem Statement

There are N candles on an infinite number line. The i-th candle is at the coordinate X_i. At time 0, it has a length of A_i and is lit. Each minute, the length of a lit candle decreases by 1. When the length becomes 0, it burns out, and its length does not change after that. Additionally, the length of an unlit candle does not change.

Takahashi is at the coordinate 0 at time 0. Each minute, he can move a distance of at most 1. If there is a candle at his current coordinate, he can put out that candle. (If there are multiple candles there, he can put out all of them.) The time it takes to put out a candle is negligible.

Find the maximum possible total length of the candles remaining at 10^{100} minutes after time 0, achieved by Takahashi's optimal course of actions.

Constraints

• 1 \leq N \leq 300
• -10^9 \leq X_i \leq 10^9
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
-2 10
3 10
12 10

Sample Output 1

11

The third candle, which is at coordinate 12, will burn out before Takahashi puts it out, regardless of Takahashi's behavior.
For the other two candles, if he goes to coordinate -2 in two minutes to put out the first and then goes to coordinate 3 in five minutes to put out the second, the lengths of those candles will not change after that. The lengths of those candles remaining are 10-2=8 and 10-2-5=3, for a total of 8+3=11, which is the maximum that can be achieved. Thus, print 11.

Sample Input 2

5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

Sample Output 2

4999999994

Note that two or more candles may occupy the same coordinate and that the answer may not fit into a 32-bit integer.