Problem Statement

You are given a string S of length 12. How many occurrences of ZONes does it contain as contiguous substrings?

Constraints

• S is a string of length 12 consisting of English letters.

Sample Input 1

abcdZONefghi

Sample Output 1

1

The 5-th through 8-th characters of S form a ZONe.

Sample Input 2

ZONeZONeZONe

Sample Output 2

3

Sample Input 3

helloAtZoner

Sample Output 3

0

The 8-th through 11-th characters of S form a Zone, which is not a ZONe.

Problem Statement

You are now standing under a very high tower, of height 1000. At a position whose distance from the tower is D, there is a UFO up in the sky at height H (see the figure at Sample Input / Output 1), and you want to send it a radio wave.
There are N obstacles between the tower and the UFO. The i-th obstacle stands at the position d_i meters from the tower towards the UFO, and has a height of h_i. You want to climb up the tower so that no obstacle crosses the line between you and the UFO. Find the minimum height you need to climb.
We assume that the ground is a flat plane, and the towers and obstacles stand vertically from the ground.
Additionally, if the top of an obstacle lies exactly on the line connecting you and the UFO, we assume that the obstacle does not cross that line.

Constraints

• All values in input are integers.
• 1 ≤ N ≤ 100
• 1 ≤ d_i < D ≤ 1000
• 1 ≤ h_i < H ≤ 1000

Sample Input 1

1 10 10
3 5

Sample Output 1

2.857142857142857

If you climb the tower to the height of \frac{20}{7}, no obstacle will cross the line between you and the UFO, as shown below.

Sample Input 2

1 10 10
3 2

Sample Output 2

0.0

You can send a radio wave to the UFO without climbing up the tower.

Sample Input 3

5 896 483
228 59
529 310
339 60
78 266
659 391

Sample Output 3

245.3080684596577

Problem Statement

You want to choose three persons from N candidates to form a team.
Each candidate has five parameters: power, speed, technique, knowledge, and inventiveness.
The power, speed, technique, knowledge, and the inventiveness of the i-th candidate are A_i, B_i, C_i, D_i, and E_i, respectively.
Let us define your team's power as the maximum of the members' powers. The team's speed, technique, knowledge, and inventiveness are defined similarly.
Then, let us define your team's total strength as the minimum of the team's power, speed, technique, knowledge, and inventiveness.
Find the maximum possible value of your team's total strength.

Constraints

• All values in input are integers.
• 3 ≤ N ≤ 3000
• 1 ≤ A_i, B_i, C_i, D_i, E_i ≤ 10^9

Sample Input 1

3
3 9 6 4 6
6 9 3 1 1
8 8 9 3 7

Sample Output 1

4

We have no choice but to choose all three of them.
Then, the team's parameters will be as follows:

• power: \max(3, 6, 8) = 8;
• speed: \max(9, 9, 8) = 9;
• technique: \max(6, 3, 9) = 9;
• knowledge: \max(4, 1, 3) = 4;
• inventiveness: \max(6, 1, 7) = 7.

Thus, the team's total strength will be \min(8, 9, 9, 4, 7) = 4.

Sample Input 2

5
6 13 6 19 11
4 4 12 11 18
20 7 19 2 5
15 5 12 20 7
8 7 6 18 5

Sample Output 2

13

If we choose the 1-st, 2-nd, and 3-rd candidates, the team's total strength will be \min(20, 13, 19, 19, 18) = 13.

Sample Input 3

10
6 7 5 18 2
3 8 1 6 3
7 2 8 7 7
6 3 3 4 7
12 8 9 15 9
9 8 6 1 10
12 9 7 8 2
10 3 17 4 10
3 1 3 19 3
3 14 7 13 1

Sample Output 3

10

Problem Statement

You are given a ciphertext S. It can be decrypted by the following procedure:

• Let T be an empty string.
• For each i = 1, 2, \dots, |S| in this order, do the following: (|S| denotes the length of S)
  • if the i-th character of S is R, reverse T;
  • if the i-th character of S is not R, add that character to the end of T.
• After the operation above, if there are two consecutive same characters in T, remove those two characters. Repeat this operation as long as it can be done. (We can prove that the final string obtained does not depend on the order the characters are removed.)

Print the string T obtained by this procedure.

Constraints

• S consists of lowercase English letters and R.
• 1 ≤ |S| ≤ 5 \times 10^5

Sample Input 1

ozRnonnoe

Sample Output 1

zone

We can decrypt it as follows:

• Initially, T is an empty string.
• Add o at the end of T, making it o.
• Add z at the end of T, making it oz.
• Reverse T, making it zo.
• Add n at the end of T, making it zon.
• Add o at the end of T, making it zono.
• Add n at the end of T, making it zonon.
• Add n at the end of T, making it zononn.
• Add o at the end of T, making it zononno.
• Add e at the end of T, making it zononnoe.
• Delete two consecutive ns from T, making it zonooe.
• Delete two consecutive os from T, making it zone.

Sample Input 2

hellospaceRhellospace

Sample Output 2

The answer may be an empty string.

Problem Statement

On a two-dimensional plane, you are now at coordinate (1, 1) and want to get to (R, C), the coordinates of the UFO.
When you are at (r, c), you can make the following four kinds of moves:

• Move from (r, c) to (r, c + 1) at the cost of A_{r, c}. You can make this move when c < C.
• Move from (r, c) to (r, c - 1) at the cost of A_{r, c - 1}. You can make this move when c > 1.
• Move from (r, c) to (r + 1, c) at the cost of B_{r, c}. You can make this move when r < R.
• Choose an integer i such that 1 ≤ i < r and move from (r, c) to (r - i, c) at the cost of 1 + i.

Find the minimum cost needed to move from (1, 1) to (R, C).

Constraints

• All values in input are integers.
• 2 ≤ R, C ≤ 500
• 0 ≤ A_{i,j} < 10^3
• 0 ≤ B_{i,j} < 10^3

Sample Input 1

3 3
10 1
10 10
1 10
1 10 1
1 10 1

Sample Output 1

9

You can achieve the cost of 9 as follows:

• Move from (1, 1) to (2, 1) at the cost of 1.
• Move from (2, 1) to (3, 1) at the cost of 1.
• Move from (3, 1) to (3, 2) at the cost of 1.
• Move from (3, 2) to (1, 2) at the cost of 3.
• Move from (1, 2) to (1, 3) at the cost of 1.
• Move from (1, 3) to (2, 3) at the cost of 1.
• Move from (2, 3) to (3, 3) at the cost of 1.

Sample Input 2

7 11
42 77 94 76 40 66 43 28 66 23
27 34 41 31 83 13 64 69 81 82
23 81 0 22 39 51 4 37 84 43
62 37 82 86 26 67 45 78 85 2
79 18 72 62 68 84 69 88 19 48
0 27 21 51 71 13 87 45 39 11
74 57 32 0 97 41 87 96 17 98
69 58 76 32 51 16 38 68 86 82 64
53 47 33 7 51 75 43 14 96 86 70
80 58 12 76 94 50 59 2 1 54 25
14 14 62 28 12 43 15 70 65 44 41
56 50 50 54 53 34 16 3 2 59 88
27 85 50 79 48 86 27 81 78 78 64

Sample Output 2

498

Sample Input 3

4 4
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Sample Output 3

0

Problem Statement

As your startup's new product, you are planning to build warp gates that allow travel between all planets.
There are N planets, numbered 0 through N-1, where there is an integer n such that N = 2^n. To allow fast travel between all these planets, you want to make N - 1 warp gates, each of which allows instant travel between two planets. However, for some pairs of planets that are incompatible with each other, you cannot make a warp gate between them.
More specifically, such pairs of planets incompatible with each other are represented by a sequence A = (A_1, A_2, \dots, A_M). If and only if there is an integer i such that a\ \mathrm{xor}\ b = A_i, you cannot make a warp gate between Planet a and Planet b.
Determine whether it is possible to make a network of warp gates allowing travel between every two planets. If it is possible, find one such way to make N - 1 warp gates.

Constraints

• All values in input are integers.
• There exists an integer n such that 1 ≤ n ≤ 18 and N = 2^n.
• 0 ≤ M ≤ N - 1
• 0 < A_1 < A_2 < \dots < A_M < N

Sample Input 1

4 1
3

Sample Output 1

1 0
1 3
0 2

Since 1\ \mathrm{xor}\ 0 = 1,\ 1\ \mathrm{xor}\ 3 = 2,\ 0\ \mathrm{xor}\ 2 = 2, we can make those N - 1 warp gates, and they allow travel between every two planets, so this output will be considered correct.
There are many other possible outputs that will also be considered correct.

Sample Input 2

8 0

Sample Output 2

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

Sample Input 3

8 7
1 2 3 4 5 6 7

Sample Output 3

-1