Problem Statement

Three people live in Takahashi's house: Takahashi, his father, and his mother. All of them wash their hair in the bathroom each night.
His father, his mother, and Takahashi take a bath in this order and use A, B, and C milliliters of shampoo, respectively.

This morning, the bottle contained V milliliters of shampoo. Without refilling, who will be the first to run short of shampoo to wash their hair?

Constraints

• 1 \leq V,A,B,C \leq 10^5
• All values in input are integers.

Sample Input 1

25 10 11 12

Sample Output 1

T

Now, they have 25 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 15.
• Next, Takahashi's mother uses 11 milliliters, leaving 4.
• Finally, Takahashi tries to use 12 milliliters and runs short of shampoo since only 4 is remaining.

Sample Input 2

30 10 10 10

Sample Output 2

F

Now, they have 30 milliliters of shampoo.

• First, Takahashi's father uses 10 milliliters, leaving 20.
• Next, Takahashi's mother uses 10 milliliters, leaving 10.
• Then, Takahashi uses 10 milliliters, leaving 0.
• Next day, Takahashi's father tries to use 10 milliliters and runs short of shampoo since only 0 is remaining.

Sample Input 3

100000 1 1 1

Sample Output 3

M

Problem Statement

A sport event is held in June of every year whose remainder when divided by 4 is 2.
Suppose that it is now January of the year Y. In what year will this sport event be held next time?

Constraints

• 2000 \leq Y \leq 3000
• Y is an integer.

Sample Input 1

2022

Sample Output 1

2022

The remainder when 2022 is divided by 4 is 2, so if it is now January of 2022, the next games will be held in June of the same year.

Sample Input 2

2023

Sample Output 2

2026

Sample Input 3

3000

Sample Output 3

3002

Problem Statement

There is an empty bag.

You are given Q queries. Process these queries in order and output the answer to each type-2 query.

Each query is of one of the following types.

• Type 1: Given as input in the format 1 x. Put a ball with the integer x written on it into the bag.

• Type 2: Given as input in the format 2. Pick out one ball with the minimum integer written on it from the balls in the bag, and report that integer as the answer. This query is not given when the bag contains no balls.

Constraints

• 2 \leq Q \leq 100
• In a type-1 query, 1 \leq x \leq 100.
• When a type-2 query is given, the bag is not empty.
• At least one type-2 query is given.
• All input values are integers.

Sample Input 1

5
1 6
1 7
2
1 1
2

Sample Output 1

6
1

Initially, the bag contains no balls.

The 1st query puts a ball with 6 written on it into the bag.

The 2nd query puts a ball with 7 written on it into the bag.

In the 3rd query, the bag contains a ball with 6 written on it and a ball with 7 written on it, so you pick out the ball with 6 written on it. The answer to this query is 6.

The 4th query puts a ball with 1 written on it into the bag.

In the 5th query, the bag contains a ball with 1 written on it and a ball with 7 written on it, so you pick out the ball with 1 written on it. The answer to this query is 1.

Sample Input 2

8
1 5
1 1
1 1
1 9
2
2
1 2
2

Sample Output 2

1
1
2

The bag may contain multiple balls with the same integer.

Problem Statement

You are given a positive integer N. If there are integers x and y such that N=2^x3^y, print Yes; otherwise, print No.

Constraints

• 1\leq N\leq10^{18}
• N is an integer.

Sample Input 1

324

Sample Output 1

Yes

For x=2,y=4, we have 2^x3^y=2^23^4=4\times81=324, so the condition is satisfied. Thus, you should print Yes.

Sample Input 2

5

Sample Output 2

No

There are no integers x and y such that 2^x3^y=5. Thus, you should print No.

Sample Input 3

32

Sample Output 3

Yes

For x=5,y=0, we have 2^x3^y=32\times1=32, so you should print Yes.

Sample Input 4

37748736

Sample Output 4

Yes

Problem Statement

We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.

Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i,B_i \leq 1000
• All values in input are integers.

Sample Input 1

3
1 1
2 1
3 1

Sample Output 1

3.000000000000000

The two flames will meet at 3 centimeters from the left end of the object.

Sample Input 2

3
1 3
2 2
3 1

Sample Output 2

3.833333333333333

Sample Input 3

5
3 9
1 2
4 6
1 5
5 3

Sample Output 3

8.916666666666668

Problem Statement

We have N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

• 1 i j \colon Write the number i on a blank card and put it into box j.
• 2 i \colon Report all numbers written on the cards in box i, in ascending order.
• 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

• In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• For a query of the first kind:
  • 1 \leq i \leq 2 \times 10^5
  • 1 \leq j \leq N
• For a query of the second kind:
  • 1 \leq i \leq N
  • Box i contains some cards when this query is given.
• For a query of the third kind:
  • 1 \leq i \leq 2 \times 10^5
  • Some boxes contain a card with the number i when this query is given.
• At most 2 \times 10^5 numbers are to be reported.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write 1 on a card and put it into box 1.
• Write 2 on a card and put it into box 4.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1 and 2.
  • Print 1 and 2 in this order.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1, 1, and 2.
  • Note that you should print 1 twice.
• Boxes 1 and 4 contain a card with the number 1.
  • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
• Boxes 4 contains a card with the number 2.

Sample Input 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

Sample Output 2

1 2 200000
1

Problem Statement

You are given a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell is one of the following: a start cell, a goal cell, an empty cell, or an obstacle cell. This information is described by H strings S_1,S_2,\dots,S_H, each of length W. Specifically, the cell (i,j) is a start cell if the j-th character of S_i is S, a goal cell if it is G, an empty cell if it is ., and an obstacle cell if it is #. It is guaranteed that there is exactly one start cell and exactly one goal cell.

You are currently on the start cell. Your objective is to reach the goal cell by repeatedly moving to a cell adjacent by an edge to the one you are in. However, you cannot move onto an obstacle cell or move outside the grid, and you must alternate between moving vertically and moving horizontally each time. (The direction of the first move can be chosen arbitrarily.)

Determine if it is possible to reach the goal cell. If it is, find the minimum number of moves required.

More formally, check if there exists a sequence of cells (i_1,j_1),(i_2,j_2),\dots,(i_k,j_k) satisfying all of the following conditions. If such a sequence exists, find the minimum value of k-1.

• For every 1 \leq l \leq k, it holds that 1 \leq i_l \leq H and 1 \leq j_l \leq W, and (i_l,j_l) is not an obstacle cell.
• (i_1,j_1) is the start cell.
• (i_k,j_k) is the goal cell.
• For every 1 \leq l \leq k-1, |i_l - i_{l+1}| + |j_l - j_{l+1}| = 1.
• For every 1 \leq l \leq k-2, if i_l \neq i_{l+1}, then i_{l+1} = i_{l+2}.
• For every 1 \leq l \leq k-2, if j_l \neq j_{l+1}, then j_{l+1} = j_{l+2}.

Constraints

• 1 \leq H,W \leq 1000
• H and W are integers.
• Each S_i is a string of length W consisting of S, G, ., #.
• There is exactly one start cell and exactly one goal cell.

Sample Input 1

3 5
.S#.G
.....
.#...

Sample Output 1

7

As shown in the left figure, you can move as (1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(3,3)\rightarrow(3,4)\rightarrow(2,4)\rightarrow(2,5)\rightarrow(1,5), reaching the goal cell in 7 moves. It is impossible in 6 moves or fewer, so the answer is 7.

Note that you cannot take a path that moves horizontally (or vertically) consecutively without alternating as shown in the right figure.

Sample Input 2

3 5
..#.G
.....
S#...

Sample Output 2

-1

It is not possible to reach the goal cell.

Sample Input 3

8 63
...............................................................
..S...#............................#####..#####..#####..####G..
..#...#................................#..#...#......#..#......
..#####..####...####..####..#..#...#####..#...#..#####..#####..
..#...#..#..#...#..#..#..#..#..#...#......#...#..#..........#..
..#...#..#####..####..####..####...#####..#####..#####..#####..
................#.....#........#...............................
................#.....#........#...............................

Sample Output 3

148

Problem Statement

You are given an integer N. You can perform the following two types of operations:

• Pay X yen to replace N with \displaystyle\left\lfloor\frac{N}{A}\right\rfloor.
• Pay Y yen to roll a die (dice) that shows an integer between 1 and 6, inclusive, with equal probability. Let b be the outcome of the die, and replace N with \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.

Here, \lfloor s \rfloor denotes the greatest integer less than or equal to s. For example, \lfloor 3 \rfloor=3 and \lfloor 2.5 \rfloor=2.

Determine the minimum expected cost paid before N becomes 0 when optimally choosing operations.
The outcome of the die in each operation is independent of other rolls, and the choice of operation can be made after observing the results of the previous operations.

Constraints

• 1 \leq N \leq 10^{18}
• 2 \leq A \leq 6
• 1 \leq X, Y \leq 10^9
• All input values are integers.

Sample Input 1

3 2 10 20

Sample Output 1

20.000000000000000

The available operations are as follows:

• Pay 10 yen. Replace N with \displaystyle\left\lfloor\frac{N}{2}\right\rfloor.
• Pay 20 yen. Roll a die. Let b be the outcome, and replace N with \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.

The optimal strategy is to perform the first operation twice.

Sample Input 2

3 2 20 20

Sample Output 2

32.000000000000000

The available operations are as follows:

• Pay 20 yen. Replace N with \displaystyle\left\lfloor\frac{N}{2}\right\rfloor.
• Pay 20 yen. Roll a die. Let b be the outcome, and replace N with \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.

The optimal strategy is as follows:

• First, perform the second operation to roll the die.
  • If the outcome is 4 or greater, then N becomes 0.
  • If the outcome is 2 or 3, then N becomes 1. Now, perform the first operation to make N = 0.
  • If the outcome is 1, restart from the beginning.

Sample Input 3

314159265358979323 4 223606797 173205080

Sample Output 3

6418410657.7408381

Problem Statement

You are given N strings S_1, S_2, \ldots, S_N consisting of digits from 1 through 9 and the character X.

We will choose a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) to construct a string T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}, where + denotes a concatenation of strings.

Then, we will calculate the "score" of the string T = T_1T_2\ldots T_{|T|} (where |T| denotes the length of T).
The score is calculated by the following 9 steps, starting from the initial score 0:

• Add 1 point to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 1.
• Add 2 points to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 2.
• Add 3 points to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 3.
• \cdots
• Add 9 points to the score as many times as the number of integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 9.

Find the maximum possible score of T when P can be chosen arbitrarily.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N is an integer.
• S_i is a string of length at least 1 consisting of digits from 1 through 9 and the character X.
• The sum of lengths of S_1, S_2, \ldots, S_N is at most 2 \times 10^5.

Sample Input 1

3
1X3
59
XXX

Sample Output 1

71

When P = (3, 1, 2), we have T = S_3 + S_1 + S_2 = XXX1X359. Then, the score of T is calculated as follows:

• there are 3 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 1;
• there are 4 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 3;
• there are 4 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 5;
• there are 4 integer pairs (i, j) such that 1 \leq i \lt j \leq |T|, T_i = X, and T_j = 9.

Therefore, the score of T is 1 \times 3 + 3 \times 4 + 5 \times 4 + 9 \times 4 = 71, which is the maximum possible value.

Sample Input 2

10
X63X395XX
X2XX3X22X
13
3716XXX6
45X
X6XX
9238
281X92
1XX4X4XX6
54X9X711X1

Sample Output 2

3010