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

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 an integer N and a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

Given Q queries, process them in the given order. Each query is of one of the following two kinds:

• 1 k x : set the value A _ k to x.
• 2 k : print the value A _ k.

Constraints

• 1 \leq N \leq 10 ^ 5
• 1 \leq Q \leq 10 ^ 5
• 0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
• 1\leq k\leq N for all queries.
• 0\leq x\leq 10 ^ 9 for all queries of the first kind.
• There is at least one query of the second kind.
• All values in the input are integers.

Sample Input 1

3
1 3 5
7
2 2
2 3
1 3 0
2 3
1 2 8
2 2
2 1

Sample Output 1

3
5
0
8
1

Initially, A=(1,3,5).

• For the 1-st query, A=(1,3,5), where A _ 2=3, so 3 should be printed.
• For the 2-nd query, A=(1,3,5), where A _ 3=5, so 5 should be printed.
• The 3-rd query sets the value A _ 3 to 0, making A=(1,3,0).
• For the 4-th query, A=(1,3,0), where A _ 3=0, so 0 should be printed.
• The 5-th query sets the value A _ 2 to 8, making A=(1,8,0).
• For the 6-th query, A=(1,8,0), where A _ 2=8, so 8 should be printed.
• For the 7-th query, A=(1,8,0), where A _ 1=1, so 1 should be printed.

Sample Input 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

Sample Output 2

2
16
0
0
16
100

Sample Input 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

Sample Output 3

478
317
838
838
176
595
468

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

• N is an integer between 1 and 1000, inclusive.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions.

• 1 \leq a \lt b \leq H
• 1 \leq c \lt d \leq W
• There was one cookie on each square (i, j) such that a \leq i \leq b, c \leq j \leq d, and no cookie on the other squares.

However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.

As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square (i, j) is given as the character S_{i,j}, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

Constraints

• 2 \leq H, W \leq 500
• S_{i,j} is # or ..

Sample Input 1

5 6
......
..#.#.
..###.
..###.
......

Sample Output 1

2 4

Initially, cookies were on the squares inside the rectangle with (2, 3) as the top-left corner and (4, 5) as the bottom-right corner, and Snuke ate the cookie on (2, 4). Thus, you should print (2, 4).

Sample Input 2

3 2
#.
##
##

Sample Output 2

1 2

Initially, cookies were placed on the squares inside the rectangle with (1, 1) as the top-left corner and (3, 2) as the bottom-right corner, and Snuke ate the cookie at (1, 2).

Sample Input 3

6 6
..####
..##.#
..####
..####
..####
......

Sample Output 3

2 5

Problem Statement

In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.

Constraints

• All values in input are integers.
• 3 \le N \le 300
• -10^9 \le X_i,Y_i \le 10^9
• (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

Sample Input 1

4
0 1
1 3
1 1
-1 -1

Sample Output 1

3

The figure below illustrates the points.

There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.

Sample Input 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

Sample Output 2

1124

Problem Statement

There is a perfect binary tree with 2^{10^{100}}-1 vertices, numbered 1,2,...,2^{10^{100}}-1.
Vertex 1 is the root. For each 1\leq i < 2^{10^{100}-1}, Vertex i has two children: Vertex 2i to the left and Vertex 2i+1 to the right.

Takahashi starts at Vertex X and performs N moves, represented by a string S. The i-th move is as follows.

• If the i-th character of S is U, go to the parent of the vertex he is on now.
• If the i-th character of S is L, go to the left child of the vertex he is on now.
• If the i-th character of S is R, go to the right child of the vertex he is on now.

Find the index of the vertex Takahashi will be on after N moves. In the given cases, it is guaranteed that the answer is at most 10^{18}.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq X \leq 10^{18}
• N and X are integers.
• S has a length of N and consists of U, L, and R.
• When Takahashi is at the root, he never attempts to go to the parent.
• When Takahashi is at a leaf, he never attempts to go to a child.
• The index of the vertex Takahashi is on after N moves is at most 10^{18}.

Sample Input 1

3 2
URL

Sample Output 1

6

The perfect binary tree has the following structure.

In the three moves, Takahashi goes 2 \to 1 \to 3 \to 6.

Sample Input 2

4 500000000000000000
RRUU

Sample Output 2

500000000000000000

During the process, Takahashi may be at a vertex whose index exceeds 10^{18}.

Sample Input 3

30 123456789
LRULURLURLULULRURRLRULRRRUURRU

Sample Output 3

126419752371

Problem Statement

There are N people gathered for an event called Flowing Noodles. The people are lined up in a row, numbered 1 to N in order from front to back.

During the event, the following occurrence happens M times:

• At time T_i, a quantity W_i of noodles is flown down. The person at the front of the row gets all of it (if no one is in the row, no one gets it). That person then steps out of the row and returns to their original position in the row at time T_i+S_i.

A person who returns to the row at time X is considered to be in the row at time X.

After all the M occurrences, report the total amount of noodles each person has got.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 0 <T_1 <\ldots < T_M \leq 10^9
• 1 \leq S_i \leq 10^9
• 1 \leq W_i \leq 10^9
• All input values are integers.

Sample Input 1

3 5
1 1 3
2 10 100
4 100 10000
10 1000 1000000000
100 1000000000 1

Sample Output 1

101
10
1000

The event proceeds as follows:

• At time 1, a quantity 1 of noodles is flown down. People 1, 2, and 3 are in the row, and the person at the front, person 1, gets the noodles and steps out of the row.
• At time 2, a quantity 10 of noodles is flown down. People 2 and 3 are in the row, and the person at the front, person 2, gets the noodles and steps out of the row.
• At time 4, person 1 returns to the row.
• At time 4, a quantity 100 of noodles is flown down. People 1 and 3 are in the row, and the person at the front, person 1, gets the noodles and steps out of the row.
• At time 10, a quantity 1000 of noodles is flown down. Only person 3 is in the row, and the person at the front, person 3, gets the noodles and steps out of the row.
• At time 100, a quantity 1000000000 of noodles is flown down. No one is in the row, so no one gets these noodles.
• At time 102, person 2 returns to the row.
• At time 10004, person 1 returns to the row.
• At time 1000000010, person 3 returns to the row.

The total amounts of noodles people 1, 2, and 3 have got are 101, 10, and 1000, respectively.

Sample Input 2

3 1
1 1 1

Sample Output 2

1
0
0

Sample Input 3

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

Sample Output 3

15

Problem Statement

We have a loaf of bread of length L, which we will cut and distribute to N children.
The i-th child (1\leq i\leq N) wants a loaf of length A_i.

Now, Takahashi will repeat the operation below to cut the loaf into lengths A_1, A_2, \ldots, A_N for the children.

Choose a loaf of length k and an integer x between 1 and k-1 (inclusive). Cut the loaf into two loaves of length x and k-x.
This operation incurs a cost of k regardless of the value of x.

Each child i must receive a loaf of length exactly A_i, but it is allowed to leave some loaves undistributed.

Find the minimum cost needed to distribute loaves to all children.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1\leq A_i\leq 10^9
• A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
• All values in input are integers.

Sample Input 1

5 7
1 2 1 2 1

Sample Output 1

16

Takahashi can cut the loaf for the children as follows.

• Choose the loaf of length 7 and x=3, cutting it into loaves of length 3 and 4 for a cost of 7.
• Choose the loaf of length 3 and x=1, cutting it into loaves of length 1 and 2 for a cost of 3. Give the former to the 1-st child.
• Choose the loaf of length 2 and x=1, cutting it into two loaves of length 1 for a cost of 2. Give them to the 3-rd and 5-th children.
• Choose the loaf of length 4 and x=2, cutting it into two loaves of length 2 for a cost of 4. Give them to the 2-nd and 4-th children.

This incurs a cost of 7+3+2+4=16, which is the minimum possible. There will be no leftover loaves.

Sample Input 2

3 1000000000000000
1000000000 1000000000 1000000000

Sample Output 2

1000005000000000

Note that each child i must receive a loaf of length exactly A_i.