Problem Statement

There is a rectangle in the xy-plane. Each edge of this rectangle is parallel to the x- or y-axis, and its area is not zero.

Given the coordinates of three of the four vertices of this rectangle, (x_1, y_1), (x_2, y_2), and (x_3, y_3), find the coordinates of the other vertex.

Constraints

• -100 \leq x_i, y_i \leq 100
• There uniquely exists a rectangle with all of (x_1, y_1), (x_2, y_2), (x_3, y_3) as vertices, edges parallel to the x- or y-axis, and a non-zero area.
• All values in input are integers.

Sample Input 1

-1 -1
-1 2
3 2

Sample Output 1

3 -1

The other vertex of the rectangle with vertices (-1, -1), (-1, 2), (3, 2) is (3, -1).

Sample Input 2

-60 -40
-60 -80
-20 -80

Sample Output 2

-20 -40

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

There are N people numbered Person 1, Person 2, \dots, and Person N. Person i has a family name s_i and a given name t_i.

Consider giving a nickname to each of the N people. Person i's nickname a_i should satisfy all the conditions below.

• a_i coincides with Person i's family name or given name. In other words, a_i = s_i and/or a_i = t_i holds.
• a_i does not coincide with the family name and the given name of any other person. In other words, for all integer j such that 1 \leq j \leq N and i \neq j, it holds that a_i \neq s_j and a_i \neq t_j.

Is it possible to give nicknames to all the N people? If it is possible, print Yes; otherwise, print No.

Constraints

• 2 \leq N \leq 100
• N is an integer.
• s_i and t_i are strings of lengths between 1 and 10 (inclusive) consisting of lowercase English alphabets.

Sample Input 1

3
tanaka taro
tanaka jiro
suzuki hanako

Sample Output 1

Yes

The following assignment satisfies the conditions of nicknames described in the Problem Statement: a_1 = taro, a_2 = jiro, a_3 = hanako. (a_3 may be suzuki, too.)
However, note that we cannot let a_1 = tanaka, which violates the second condition of nicknames, since Person 2's family name s_2 is tanaka too.

Sample Input 2

3
aaa bbb
xxx aaa
bbb yyy

Sample Output 2

No

There is no way to give nicknames satisfying the conditions in the Problem Statement.

Sample Input 3

2
tanaka taro
tanaka taro

Sample Output 3

No

There may be a pair of people with the same family name and the same given name.

Sample Input 4

3
takahashi chokudai
aoki kensho
snu ke

Sample Output 4

Yes

We can let a_1 = chokudai, a_2 = kensho, and a_3 = ke.

Problem Statement

There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.

The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.

Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?

Constraints

• 2 \leq H, W \leq 100
• H and W are integers.
• S_i \, (1 \leq i \leq H) is a string of length W consisting of o and -.
• There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} = o.

Sample Input 1

2 3
--o
o--

Sample Output 1

3

The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.

Sample Input 2

5 4
-o--
----
----
----
-o--

Sample Output 2

4

Problem Statement

We have a sequence of N numbers: A = (a_1, a_2, \dots, a_N).
Process the Q queries explained below.

• Query i: You are given a pair of integers (x_i, k_i). Let us look at the elements of A one by one from the beginning: a_1, a_2, \dots Which element will be the k_i-th occurrence of the number x_i?
  Print the index of that element, or -1 if there is no such element.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq a_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq x_i \leq 10^9 (1 \leq i \leq Q)
• 1 \leq k_i \leq N (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

6 8
1 1 2 3 1 2
1 1
1 2
1 3
1 4
2 1
2 2
2 3
4 1

Sample Output 1

1
2
5
-1
3
6
-1
-1

1 occurs in A at a_1, a_2, a_5. Thus, the answers to Query 1 through 4 are 1, 2, 5, -1 in this order.

Sample Input 2

3 2
0 1000000000 999999999
1000000000 1
123456789 1

Sample Output 2

2
-1

Problem Statement

We have HW cards arranged in a matrix with H rows and W columns.
For each i=1, \ldots, N, the card at the A_i-th row from the top and B_i-th column from the left has a number i written on it. The other HW-N cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

• If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
• If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

• 1 \leq H,W \leq 10^9
• 1 \leq N \leq \min(10^5,HW)
• 1 \leq A_i \leq H
• 1 \leq B_i \leq W
• All pairs (A_i,B_i) are distinct.
• All values in input are integers.

Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with 1 is at the 2-nd row from the top and 1-st column from the left, and the card with 2 is at the 1-st row from the top and 2-nd column from the left.

Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

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

Problem Statement

Your computer has a keyboard with three keys: 'a' key, Shift key, and Caps Lock key. The Caps Lock key has a light on it. Initially, the light on the Caps Lock key is off, and the screen shows an empty string.

You can do the following three actions any number of times in any order:

• Spend X milliseconds to press only the 'a' key. If the light on the Caps Lock key is off, a is appended to the string on the screen; if it is on, A is.
• Spend Y milliseconds to press the 'a' key and Shift key simultaneously. If the light on the Caps Lock key is off, A is appended to the string on the screen; if it is on, a is.
• Spend Z milliseconds to press the Caps Lock key. If the light on the Caps Lock key is off, it turns on; if it is on, it turns off.

Given a string S consisting of A and a, determine at least how many milliseconds you need to spend to make the string shown on the screen equal to S.

Constraints

• 1 \leq X,Y,Z \leq 10^9
• X, Y, and Z are integers.
• 1 \leq |S| \leq 3 \times 10^5
• S is a string consisting of A and a.

Sample Input 1

1 3 3
AAaA

Sample Output 1

9

The following sequence of actions makes the string on the screen equal to AAaA in 9 milliseconds, which is the shortest possible.

• Spend Z(=3) milliseconds to press the CapsLock key. The light on the Caps Lock key turns on.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.
• Spend Y(=3) milliseconds to press the Shift key and 'a' key simultaneously. a is appended to the string on the screen.
• Spend X(=1) milliseconds to press the 'a' key. A is appended to the string on the screen.

Sample Input 2

1 1 100
aAaAaA

Sample Output 2

6

Sample Input 3

1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

Sample Output 3

40

Problem Statement

We have a grid with 2 rows and L columns. Let (i,j) denote the square at the i-th row from the top (i\in\lbrace1,2\rbrace) and j-th column from the left (1\leq j\leq L). (i,j) has an integer x _ {i,j} written on it.

Find the number of integers j such that x _ {1,j}=x _ {2,j}.

Here, the description of x _ {i,j} is given to you as the run-length compressions of (x _ {1,1},x _ {1,2},\ldots,x _ {1,L}) and (x _ {2,1},x _ {2,2},\ldots,x _ {2,L}) into sequences of lengths N _ 1 and N _ 2, respectively: ((v _ {1,1},l _ {1,1}),\ldots,(v _ {1,N _ 1},l _ {1,N _ 1})) and ((v _ {2,1},l _ {2,1}),\ldots,(v _ {2,N _ 2},l _ {2,N _ 2})).

Here, the run-length compression of a sequence A is a sequence of pairs (v _ i,l _ i) of an element v _ i of A and a positive integer l _ i obtained as follows.

1. Split A between each pair of different adjacent elements.
2. For each sequence B _ 1,B _ 2,\ldots,B _ k after the split, let v _ i be the element of B _ i and l _ i be the length of B _ i.

Constraints

• 1\leq L\leq 10 ^ {12}
• 1\leq N _ 1,N _ 2\leq 10 ^ 5
• 1\leq v _ {i,j}\leq 10 ^ 9\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
• 1\leq l _ {i,j}\leq L\ (i\in\lbrace1,2\rbrace,1\leq j\leq N _ i)
• v _ {i,j}\neq v _ {i,j+1}\ (i\in\lbrace1,2\rbrace,1\leq j\lt N _ i)
• l _ {i,1}+l _ {i,2}+\cdots+l _ {i,N _ i}=L\ (i\in\lbrace1,2\rbrace)
• All values in the input are integers.

Sample Input 1

8 4 3
1 2
3 2
2 3
3 1
1 4
2 1
3 3

Sample Output 1

4

The grid is shown below.

We have four integers j such that x _ {1,j}=x _ {2,j}: j=1,2,5,8. Thus, you should print 4.

Sample Input 2

10000000000 1 1
1 10000000000
1 10000000000

Sample Output 2

10000000000

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

Sample Input 3

1000 4 7
19 79
33 463
19 178
33 280
19 255
33 92
34 25
19 96
12 11
19 490
33 31

Sample Output 3

380

Problem Statement

There is a directed graph with N vertices and M edges. Each edge has two positive integer values: beauty and cost.

For i = 1, 2, \ldots, M, the i-th edge is directed from vertex u_i to vertex v_i, with beauty b_i and cost c_i. Here, the constraints guarantee that u_i \lt v_i.

Find the maximum value of the following for a path P from vertex 1 to vertex N.

• The total beauty of all edges on P divided by the total cost of all edges on P.

Here, the constraints guarantee that the given graph has at least one path from vertex 1 to vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq u_i \lt v_i \leq N
• 1 \leq b_i, c_i \leq 10^4
• There is a path from vertex 1 to vertex N.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0.7500000000000000

For the path P that passes through the 2-nd, 6-th, and 7-th edges in this order and visits vertices 1 \rightarrow 3 \rightarrow 4 \rightarrow 5, the total beauty of all edges on P divided by the total cost of all edges on P is (b_2 + b_6 + b_7) / (c_2 + c_6 + c_7) = (9 + 4 + 2) / (5 + 8 + 7) = 15 / 20 = 0.75, and this is the maximum possible value.

Sample Input 2

3 3
1 3 1 1
1 3 2 1
1 3 3 1

Sample Output 2

3.0000000000000000

Sample Input 3

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

Sample Output 3

1.8333333333333333