Problem Statement

You are given a string S consisting of lowercase English letters.
Remove all occurrences of a, e, i, o, u from S and print the resulting string.
S contains at least one character other than a, e, i, o, u.

Constraints

• S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
• S contains at least one character other than a, e, i, o, u.

Sample Input 1

atcoder

Sample Output 1

tcdr

For S = atcoder, remove the 1-st, 4-th, and 6-th characters to get tcdr.

Sample Input 2

xyz

Sample Output 2

xyz

Sample Input 3

aaaabbbbcccc

Sample Output 3

bbbbcccc

Problem Statement

Takahashi is making a computer baseball game.
He will write a program that shows a batter's batting average with a specified number of digits.

There are integers A and B, which satisfy 1 \leq A \leq 10 and 0 \leq B \leq A.
Let S be the string obtained as follows.

• Round off \dfrac{B}{A} to three decimal digits, then write the integer part (1 digit), . (the decimal point), and the decimal part (3 digits) in this order, with trailing zeros.

For example, if A=7 and B=4, then \dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots rounded off to three decimal digits is 0.571. Thus, S is 0.571.

You are given A and B as the input and asked to print S.

Constraints

• 1 \leq A \leq 10
• 0 \leq B \leq A
• A and B are integers.

Sample Input 1

7 4

Sample Output 1

0.571

As explained in the Problem Statement, \dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots rounded off to three decimal digits is 0.571. Thus, S is 0.571.

Sample Input 2

7 3

Sample Output 2

0.429

\dfrac{B}{A} = \dfrac{3}{7} = 0.428571\dots rounded off to three decimal digits is 0.429. (Note that it got rounded up.)
Thus, S is 0.429.

Sample Input 3

2 1

Sample Output 3

0.500

\dfrac{B}{A} = \dfrac{1}{2} = 0.5 rounded off to three decimal digits is again 0.5.
Thus, S is 0.500. Note that it must have three decimal places.

Sample Input 4

10 10

Sample Output 4

1.000

Sample Input 5

1 0

Sample Output 5

0.000

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Each cell has a lowercase English letter written on it. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left.

The letters written on the grid are represented by H strings S_1,S_2,\ldots, S_H, each of length W. The j-th letter of S_i represents the letter written on (i, j).

There is a unique set of contiguous cells (going vertically, horizontally, or diagonally) in the grid with s, n, u, k, and e written on them in this order.
Find the positions of such cells and print them in the format specified in the Output section.

A tuple of five cells (A_1,A_2,A_3,A_4,A_5) is said to form a set of contiguous cells (going vertically, horizontally, or diagonally) with s, n, u, k, and e written on them in this order if and only if all of the following conditions are satisfied.

• A_1,A_2,A_3,A_4 and A_5 have letters s, n, u, k, and e written on them, respectively.
• For all 1\leq i\leq 4, cells A_i and A_{i+1} share a corner or a side.
• The centers of A_1,A_2,A_3,A_4, and A_5 are on a common line at regular intervals.

Constraints

• 5\leq H\leq 100
• 5\leq W\leq 100
• H and W are integers.
• S_i is a string of length W consisting of lowercase English letters.
• The given grid has a unique conforming set of cells.

Sample Input 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

Sample Output 1

5 2
5 3
5 4
5 5
5 6

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6)) satisfies the conditions.
Indeed, the letters written on them are s, n, u, k, and e;
for all 1\leq i\leq 4, cells A_i and A_{i+1} share a side;
and the centers of the cells are on a common line.

Sample Input 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

Sample Output 2

5 5
4 4
3 3
2 2
1 1

Tuple (A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1)) satisfies the conditions.
However, for example, (A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1)) violates the third condition because the centers of the cells are not on a common line, although it satisfies the first and second conditions.

Sample Input 3

10 10
kseeusenuk
usesenesnn
kskekeeses
nesnusnkkn
snenuuenke
kukknkeuss
neunnennue
sknuessuku
nksneekknk
neeeuknenk

Sample Output 3

9 3
8 3
7 3
6 3
5 3

Problem Statement

Consider an xy-plane. The positive direction of the x-axis is in the direction of east, and the positive direction of the y-axis is in the direction of north.
Takahashi is initially at point (x, y) = (0, 0) and facing east (in the positive direction of the x-axis).

You are given a string T = t_1t_2\ldots t_N of length N consisting of S and R. Takahashi will do the following move for each i = 1, 2, \ldots, N in this order.

• If t_i = S, Takahashi advances in the current direction by distance 1.
• If t_i = R, Takahashi turns 90 degrees clockwise without changing his position. As a result, Takahashi's direction changes as follows.
  • If he is facing east (in the positive direction of the x-axis) before he turns, he will face south (in the negative direction of the y-axis) after he turns.
  • If he is facing south (in the negative direction of the y-axis) before he turns, he will face west (in the negative direction of the x-axis) after he turns.
  • If he is facing west (in the negative direction of the x-axis) before he turns, he will face north (in the positive direction of the y-axis) after he turns.
  • If he is facing north (in the positive direction of the y-axis) before he turns, he will face east (in the positive direction of the x-axis) after he turns.

Print the coordinates Takahashi is at after all the steps above have been done.

Constraints

• 1 \leq N \leq 10^5
• N is an integer.
• T is a string of length N consisting of S and R.

Sample Input 1

4
SSRS

Sample Output 1

2 -1

Takahashi is initially at (0, 0) facing east. Then, he moves as follows.

1. t_1 = S, so he advances in the direction of east by distance 1, arriving at (1, 0).
2. t_2 = S, so he advances in the direction of east by distance 1, arriving at (2, 0).
3. t_3 = R, so he turns 90 degrees clockwise, resulting in facing south.
4. t_4 = S, so he advances in the direction of south by distance 1, arriving at (2, -1).

Thus, Takahashi's final position, (x, y) = (2, -1), should be printed.

Sample Input 2

20
SRSRSSRSSSRSRRRRRSRR

Sample Output 2

0 1

Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

• Choose two same-colored socks that are not paired yet, and pair them.

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2

You can do the operation twice as follows.

• Choose two socks with the color 1 and pair them.
• Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

Problem Statement

Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.

Constraints

• All values in input are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le W \le 3 \times 10^8
• 1 \le A_i \le 10^9
• 1 \le B_i \le 1000

Sample Input 1

3 5
3 1
4 2
2 3

Sample Output 1

15

The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.

Sample Input 2

4 100
6 2
1 5
3 9
8 7

Sample Output 2

100

There may be less than W grams of cheese in total.

Sample Input 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Sample Output 3

2357689932073

Problem Statement

Takahashi and Aoki are playing a game.

• First, Takahashi chooses an integer between A and B (inclusive) and tells it to Aoki.
• Next, Aoki chooses an integer between C and D (inclusive).
• If the sum of these two integers is a prime, then Aoki wins; otherwise, Takahashi wins.

When the two players play optimally, which player will win?

Constraints

• 1 \leq A \leq B \leq 100
• 1 \leq C \leq D \leq 100
• All values in input are integers.

Sample Input 1

2 3 3 4

Sample Output 1

Aoki

For example, if Takahashi chooses 2, Aoki can choose 3 to make the sum 5, which is a prime.

Sample Input 2

1 100 50 60

Sample Output 2

Takahashi

If they play optimally, Takahashi always wins.

Sample Input 3

3 14 1 5

Sample Output 3

Aoki

Problem Statement

Find \displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor.

Notes

\lfloor A \rfloor denotes the value of A truncated to an integer.

Constraints

• X is an integer.
• 1 \le X < 10^{500000}

Sample Input 1

1225

Sample Output 1

1360

The value we seek is 1225+122+12+1+0+0+\dots+0=1360.

Sample Input 2

99999

Sample Output 2

111105

Beware of carries.

Sample Input 3

314159265358979323846264338327950288419716939937510

Sample Output 3

349065850398865915384738153697722542688574377708317

The values in input and output can both be enormous.

Problem Statement

2^N people, numbered 1 to 2^N, will participate in a rock-paper-scissors tournament.

The tournament proceeds as follows:

• The participants are arranged in a row in the order Person 1, Person 2, \ldots, Person 2^N from left to right.
• Let 2M be the current length of the row. For each i\ (1\leq i \leq M), the (2i-1)-th and (2i)-th persons from the left play a game against each other. Then, the M losers are removed from the row. This process is repeated N times.

Here, if Person i wins exactly j games, they receive C_{i,j} yen (Japanese currency). A person winning zero games receives nothing. Find the maximum possible total amount of money received by the 2^N people if the results of all games can be manipulated freely.

Constraints

• 1 \leq N \leq 16
• 1 \leq C_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

2
2 5
6 5
2 1
7 9

Sample Output 1

15

The initial row of the people is (1,2,3,4).

If Person 2 wins the game against Person 1, and Person 4 wins the game against Person 3, the row becomes (2,4).

Then, if Person 4 wins the game against Person 2, the row becomes (4), and the tournament ends.

Here, Person 2 wins exactly 1 game, and Person 4 wins exactly 2 games, so they receive 0+6+0+9=15 yen in total, which is the maximum possible sum.

Sample Input 2

3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

Sample Output 2

4