Problem Statement

Alice and Bob play a game.

Initially, the pile has N stones. The two players alternately remove one stone from the pile.

If S is 0, Alice goes first; if it is 1, Bob goes first.
If T is 0, the player who removes the last stone wins; if it is 1, the player who removes the last stone loses (and the other player wins).

Determine which player will win.

Constraints

• 1 \leq N \leq 100
• N is an integer.
• S is 0 or 1, and so is T.

Sample Input 1

3 0 1

Sample Output 1

Bob

The game starts with Alice going first.

• The pile has initially 3 stones.
• Alice removes one stone from the pile. The pile has 2 remaining stones.
• Bob removes one stone from the pile. The pile has 1 remaining stone.
• Alice removes one stone from the pile. She loses because she has removed the last stone.

Sample Input 2

2 1 0

Sample Output 2

Alice

The game starts with Bob going first.

• The pile has 2 stones.
• Bob removes one stone from the pile. The pile has 1 remaining stone.
• Alice removes one stone from the pile. She wins because she has removed the last stone.

Problem Statement

You are given decimals A and B with D decimal places.
Precisely compute A+B and print the result in the same format.

Constraints

• 1 \leq D \leq 100
• D is an integer.
• 1 \leq A \lt 100
• 1 \leq B \lt 100
• Each of A and B is given as a concatenation of (the decimal part without leading zeros), ., and (the fractional part represented by D decimal places).

Sample Input 1

1
1.2
1.8

Sample Output 1

3.0

1.2 + 1.8 = 3, so 3.0 should be printed, which contains one decimal place. Representations like 3, 3.00, and 003.0 are not accepted, because they violate the specified format.

Sample Input 2

3
1.234
7.890

Sample Output 2

9.124

Sample Input 3

4
1.2345
8.7655

Sample Output 3

10.0000

Problem Statement

You are given a sequence P = (P_1, P_2, \ldots, P_N) that is a permutation of a length-N sequence (1, 2, 3, \ldots, N).

For each K = 1, 2, \ldots, N, find the integer X_K such that K is the X_K-th element of the sequence P.

Constraints

• 1 \leq N \leq 100
• 1 \leq P_i \leq N
• i \neq j \implies P_i \neq P_j
• All values in the input are integers.

Sample Input 1

5
5 2 4 1 3

Sample Output 1

4 2 5 3 1

• For K = 1, 1 is the 4-th element of the sequence P.
• For K = 2, 2 is the 2-nd element of the sequence P.
• For K = 3, 3 is the 5-th element of the sequence P.
• For K = 4, 4 is the 3-rd element of the sequence P.
• For K = 5, 5 is the 1-st element of the sequence P.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

10
10 2 3 7 8 6 1 9 5 4

Sample Output 3

7 2 3 10 9 6 4 5 8 1

Problem Statement

You are playing a game, where you buy and use items to beat an enemy with stamina H. There are two kinds of items.

• Item 1: when you use it, the enemy's stamina is reduced by A. The price is B yen (the currency in Japan).

• Item 2: when you use it, the enemy's stamina is reduced by C. Let h be the resulting stamina. Then, if h>0, the enemy's stamina is further reduced by \lfloor \frac{h}{2}\rfloor, where \lfloor A \rfloor denotes the value A rounded down to an integer.

An item disappears once you use it, but you may buy any number of the items. Also, you may use items in any order.

Find the minimum amount of money required to make the enemy's stamina 0 or less.

Constraints

• 1\leq H,A,B,C,D \leq 10^9
• All values in the input are integers.

Sample Input 1

13 6 5 1 7

Sample Output 1

12

You can buy one item 1 and one item 2 and use them in the following order:

• Use item 2 to reduce the enemy's stamina by 1, making it 12. Then, the enemy's stamina is further reduced by \lfloor \frac{12}{2}\rfloor=6 and becomes 6.

• Use item 1 to reduce the enemy's stamina by 6, making it 0.

This way, you can make the enemy's stamina 0 or less. The total amount of money required is 5 + 7 = 12, which we can prove is the minimum.

Sample Input 2

1000 1 1 1 10000

Sample Output 2

1000

Problem Statement

You are given figures S and T with H rows and W columns consisting of # and ..
The figure S is given as H strings S _ 1,S _ 2,\ldots,S _ H; the j-th character of S _ i represents the element at the i-th row and j-th column of S. The figure T is given similarly.

Determine whether one can rearrange each row of S to make S equal T.

Here, rearranging each row of a figure X is the following operation.

• For each i=1,2,\ldots,H, perform the following procedure independently.
  • Choose a permutation P=(P _ 1,P _ 2,\ldots,P _ W) of (1,2,\ldots,W).
  • For all integers j such that 1 \leq j \leq W, simultaneously replace the element at the i-th row and j-th column of X with the one at the i-th row and P_j-th column.

Note that you may choose different permutations P for different i.

Constraints

• H and W are integers.
• 1 \leq H,W
• 1 \leq H \times W \leq 4 \times 10 ^ 5
• S_i and T_i are strings of length W consisting of # and ..

Sample Input 1

3 4
##.#
##..
.#..
###.
#..#
...#

Sample Output 1

Yes

For example, if you choose (4,2,1,3),(1,3,4,2),(4,1,3,2) for i=1,2,3, respectively, you can make S equal T.

Sample Input 2

3 4
#...
#..#
.###
..##
#..#
##..

Sample Output 2

No

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

S=T may hold.

Sample Input 4

8 7
..#.#.#
..#....
#.#....
..#.#.#
..#..#.
..#...#
..#....
#.#....
##.#...
...#...
#..#...
..#..##
...#.#.
....#.#
......#
#....#.

Sample Output 4

Yes

Problem Statement

Given a set of N integers, S=\{S_1,S_2,\dots,S_N\}, answer Q queries in the following format:

• given a set of M integers, T=\{T_1,T_2,\dots,T_M\}, find how many integers the union of S and T contains.

Constraints

• All values in the input are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le S_i \le 10^9
• If i \neq j, then S_i \neq S_j.
• All queries satisfy the following conditions:
  • 1 \le M
  • If i \neq j, then T_i \neq T_j.
• The sum of M in an input does not exceed 2 \times 10^5.

Sample Input 1

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

Sample Output 1

7
10
5
8
12

In this input, S=\{2,3,5,7,11\}, and five queries are given.

• In the first query, T=\{1,3,5,7,9,11\}. The union of S and T is \{1,2,3,5,7,9,11\}, which contains seven integers.
• In the second query, T=\{12,10,8,6,4,2\}. The union of S and T is \{2,3,4,5,6,7,8,10,11,12\}, which contains ten integers.

Problem Statement

There is a grid with H horizontal rows and W vertical columns. The square at the i-th row from the top and j-th column from the left has a number A_{i,j} written on it.
A_{i,j} are distinct integers between 1 and HW.

Find all the integer pairs (x,y) satisfying 1\leq x < y \leq HW such that the square with x written on it is adjacent to the one with y.

A square is said to be adjacent to another if these two squares share a side.

Constraints

• 1 \leq H,W
• 2 \leq H \times W \leq 2\times 10^5
• 1 \leq A_{i,j} \leq H \times W
• H and W are integers.
• A_{i,j} are distinct integers.

Sample Input 1

2 3
2 3 4
1 6 5

Sample Output 1

1 2
1 6
2 3
3 4
3 6
4 5
5 6

The square with 1 written on it is adjacent to the one with 2.

Sample Input 2

3 1
1
2
3

Sample Output 2

1 2
2 3

Problem Statement

You have a hand of N cards. The i-th card (1 \leq i \leq N) has an integer A_i written on it. You can perform the following operation any number of times.

• Choose three cards with consecutive integers written on them, and discard them from hand. In other words, for some integer x, choose a card with x, a card with x+1, and a card with x+2 written on them, and discard them from hand.

What is the minimum possible number of cards in your final hand?

Constraints

• 3 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq 10^{18} \, (1 \leq i \leq N)
• All values in the input are integers.

Sample Input 1

7
2 4 2 1 6 3 5

Sample Output 1

1

After the following two operations, your hand will have one card, which is the minimum possible.

• Choose cards with 1, 2, 3 written on them, and discard them.
• Choose cards with 4, 5, 6 written on them, and discard them.

Sample Input 2

10
1 2 2 4 6 7 9 9 10 12

Sample Output 2

10

Sample Input 3

3
999999998 999999999 1000000000

Sample Output 3

0

Problem Statement

N players numbered 1, \dots, N sitting around a table play a card game. There are 26 kinds of cards, each of which has A, B, …, or Z written on it. Five cards are placed on the table, and four are dealt to each player.

The cards on the table are represented by a string X of length five, and the cards dealt to player i \, (1 \leq i \leq N) are represented by a string S_i of length four. X, S_1, \dots, and S_N consist of uppercase English letters, representing the kinds of the cards.

Each player chooses two cards from those dealt to the player and three from those on the table to make a set of five cards. This set is called the player's hand.

For each i \, (1 \leq i \leq N), define n_i and c_i as follows:

• let n_i = n and c_i = c, where n is the maximum integer such that player i's hand contains n cards of the same kind, and c is the character written on them. If there are multiple candidates, choose the alphabetically smallest c.

The superiority between two players A and B (A \neq B) is determined as follows:

• A is superior if n_A > n_B, and B is superior if n_B > n_A.
• If n_A = n_B, it is determined as follows:
  • If c_A \neq c_B, A is superior if c_A is alphabetically smaller than c_B, and B is superior if it is larger.
  • If c_A = c_B, A is superior if A < B, and B is superior if B > A.

Find the supreme player if all players play optimally. In other words, find i such that:

• for all j \neq i, player i is superior to player j.

Constraints

• 2 \leq N \leq 1000
• N is an integer.
• X is a string of length 5 consisting of uppercase English letters.
• S_i \, (1 \leq i \leq N) is a string of length 4 consisting of uppercase English letters.

Sample Input 1

3
AABCD
DDBC
ABBQ
XYZA

Sample Output 1

2

Here, a hand is represented by a string consisting of the five uppercase English letters written on the cards.

For example, suppose that player 1 chooses the cards with D and B from the dealt ones and those with A, B, and C from those on the table; then the hand is represented by, for instance, DBABC or ABBCD (both represent the same hand).

The following are examples of (not necessarily optimal) plays.

• If player 1 makes a hand BCDDD and player 2 makes AABBQ, we have n_1 = 3, c_1 = D, n_2 = 2, and c_2 = A. In this case, player 1 is superior.
• If player 1 makes a hand BCDDD and player 2 makes AAABB, we have n_1 = 3, c_1 = D, n_2 = 3, and c_2 = A. In this case, player 2 is superior.
• If player 2 makes a hand AAABB and player 3 makes AAABZ, we have n_2 = 3, c_2 = A, n_3 = 3, and c_3 = A. In this case, player 2 is superior.

One possible optimal hand of each player is as follows: player 1 makes ABDDD, player 2 makes AAABB, and player 3 makes AAABZ. Since player 2 is superior to both players 1 and 3, the answer is 2.

Sample Input 2

4
ABBDE
ADDZ
BEEZ
DDDD
BDDE

Sample Output 2

2

Problem Statement

You are given figures S and T with H rows and W columns consisting of # and ..
The figure S is given as H strings S _ 1,S _ 2,\ldots,S _ H; the j-th character of S _ i represents the element at the i-th row and j-th column of S. The figure T is given similarly.

Determine whether it is possible to shift the columns of S so that S will equal T.

Here, shifting the columns of S is the following operation.

• Choose an integer s between 1 and W, inclusive.
• Then, for every integer i such that 1 \leq i \leq H, simultaneously perform the following:
  • for every integer j such that 1 \leq j \leq W, simultaneously replace the element at the i-th row and j-th column with that of the i-th row and (j+s)-th column of X.

Here, for x such that W \gt x, the x-th column means the y-th column where y\ (1\leq y\leq W) is the only integer such that x-y is a multiple of W.

Constraints

• H and W are integers.
• 1 \le H,W
• 1 \le H \times W \le 4 \times 10^5
• S_i and T_i are strings of length W consisting of # and ..

Sample Input 1

3 4
##.#
##..
.#..
.###
..##
...#

Sample Output 1

Yes

Choosing s=2 will make S equal T.

Sample Input 2

3 4
##..
#..#
..##
..##
#..#
##..

Sample Output 2

No

You can only shift the columns and not turn over the figure.

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It may be the case that S=T.

Sample Input 4

8 7
.#.....
..#....
....#..
#.....#
.#.....
..#....
....#..
#.....#
.....#.
......#
.#.....
...##..
.....#.
......#
.#.....
...##..

Sample Output 4

Yes

Problem Statement

Takahashi and Aoki are playing a game with N rounds. For i=1,\ldots,N, the i-th round consists of the following steps in the order from top to bottom.

• If i \geq 2 and Takahashi received a penalty in the (i-1)-th round, the i-th round ends without performing the steps below.
• Takahashi is dealt a_i gold coins.
• Takahashi does one of the following actions.
  • Put \left \lfloor \frac{a_i \times t}{100} \right \rfloor gold coins into a bag and show it to Aoki. (\lfloor x \rfloor is the greatest integer not exceeding x.) Here, it is guaranteed that \left \lfloor \frac{a_i \times t}{100} \right \rfloor \geq 1.
  • Show an empty bag to Aoki.
• Aoki chooses an integer x between 1 and 100, inclusive, with equal probability.
  • If x\leq p, he examines the bag. If it contains no gold coins, Takahashi puts \left \lfloor \frac{a_i \times t}{100} \right \rfloor gold coins into the bag and receives a penalty.
  • If x \gt p, he does nothing.
• Takashi earns all gold coins dealt in this round that are not in the bag now.

Here, Aoki chooses x independently in each round.

Takahashi will make his choice in each round to maximize the expected value E of the total number of gold coins earned in all N rounds. Find this maximized value of E.

Constraints

• 1 \leq N \leq 100
• 1 \leq t,p \leq 99
• 1 \leq a_i \leq 10^9
• \left \lfloor \frac{a_i \times t}{100} \right \rfloor \geq 1
• All values in the input are integers.

Sample Input 1

3 10 50
100 10 300

Sample Output 1

384.50000000000000000000

Here is a way for Takahashi to maximize the expected value of the total number of gold coins earned.

• In the first round, put nothing into the bag.
• In the second round, put the specified number of gold coins into the bag (if he did not receive a penalty in the first round).
• In the third round, put nothing into the bag.

Sample Input 2

3 1 10
192 191 190

Sample Output 2

570.89999999999997726263

The true answer to this input is 570.9. The above output is not identical to this value, but the error is small enough to be considered correct.

Sample Input 3

4 17 55
32 10 77 1000000000

Sample Output 3

906500100.00000000000000000000

Problem Statement

There are N players numbered 1,2,\dots, and N.

These N players are playing the same game. In this game, two players play a match against each other. The N players have distinct strengths; the player with the greater strength always wins a match.

There were M matches. The i-th match was between players A_i and B_i, and player A_i won.

Find the lexicographically smallest possible sequence of the N players sorted by their strengths in descending order.

Constraints

• 2 \le N \le 2 \times 10^5
• 0 \le M \le 2 \times 10^5
• 1 \le A_i,B_i \le N
• A_i \neq B_i
• All values in the input are integers.
• The M conditions are consistent.

Sample Input 1

3 1
3 1

Sample Output 1

2 3 1

(2,3,1), (3,1,2), and (3,2,1) are the possible sequences of the N players sorted by their strengths in descending order that satisfy the conditions. The answer is (2,3,1), which is the lexicographically smallest one among them.

Sample Input 2

7 0

Sample Output 2

1 2 3 4 5 6 7

Problem Statement

We have N parcels numbered 1 to N. Parcel i has a size of A_i.
There are M boxes numbered 1 to M arranged in a row in numerical order: box 1 is the leftmost, and box M is the rightmost. Box i has a size of B_i.
Each box can contain any number of parcels as long as the total size of the parcels is not greater than the size of the box.

For each parcel in the order from parcel 1 to parcel N, Takahashi will try to do the following:

• put the parcel into the leftmost box that can contain it.

Determine whether Takahashi can put all parcels into boxes.

Additionally, if he can, find the total size of parcels in each box after putting all parcels into boxes; otherwise, find the smallest number of a parcel that he cannot put into a box.

Constraints

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

Sample Input 1

3 3
4 7 3
10 4 8

Sample Output 1

Yes
7 0 7

Takahashi will do the following.

• Parcel 1 can be put into box 1, 2, or 3. He puts it into the leftmost of them, box 1.
• Parcel 2 can be put into box 3. He puts it into this box.
• Parcel 3 can be put into box 1 or 2. He puts it into the leftmost of them, box 1.

Note that when he tries to put parcel 2, parcel 1 is already in box 1, so parcel 2 cannot be put into this box.

When all parcels are in boxes,

• box 1 contains parcels 1 and 3, for a total size of 3+4=7,
• box 2 contains no parcels, for a total size of 0, and
• box 3 contains parcel 2, for a total size of 7.

Sample Input 2

3 2
4 7 3
10 4

Sample Output 2

No
2

Takahashi will do the following.

• Parcel 1 can be put into box 1 or 2. He puts it into the leftmost of them, box 1.
• Parcel 2 cannot be put into any box.

Sample Input 3

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

Sample Output 3

Yes
1 2 3 4 5

Problem Statement

Consider the following problem.

Takahashi has X kilograms of garbage in the morning of some day (let us call it day 1). Each night, the amount of garbage increases by 1 kilogram.

There will be N days when he can take out the garbage. For i = 1, 2, \dots, N, if he has a_i or more kilograms of garbage in the morning of day d_i, he can take out a_i kilograms of garbage at the cost of 1 yen zero times or once.

Takahashi wants to have at most C kilograms of garbage in the morning of day D. Find the minimum amount of money needed to achieve this.

You are given N, C, D, d_i, a_i as the input. Now, consider X as a non-negative integer variable.

Find the minimum answer to the above problem for an X such that Takahashi can have at most C kilograms of garbage in the morning of day D. If there is no X such that he can have at most C kilograms of garbage in the morning of day D, print -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq C \leq 10^9
• 1 \leq d_1 \lt d_2 \lt \dots \lt d_N \lt D \leq 10^9
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

2 1 4
1 3
3 4

Sample Output 1

1

For instance, below is an optimal sequence of actions for X = 2.

• In the morning of day 1, he has X = 2 kilograms of garbage. We have d_1 = 1, but the amount of garbage is less than a_1 = 3 kilograms, so he cannot take out the garbage this day.
• After the night of day 1, he has 3 kilograms of garbage.
• After the night of day 2, he has 4 kilograms of garbage.
• In the morning of day 3, he takes out a_2 = 4 kilograms of garbage at the cost of 1 yen, wihch is allowed because d_2 = 3 and he has not less than a_2 = 4 kilograms of garbage. Then, he has 0 kilograms of garbage.
• After the night of day 3, he has 1 kilogram of garbage.
• In the morning of day 4, he has 1 kilogram of garbage, which is not more than C kilograms and thus satisfies the objective. He paid 1 yen in total.

Sample Input 2

3 10 100
10 20
20 20
30 20

Sample Output 2

-1

There is no X such that he can have at most C kilograms of garbage in the morning of day D.

Sample Input 3

4 4 10
2 3
4 5
6 1
8 4

Sample Output 3

2

Problem Statement

There is a sequence of N integers between 0 and 10, inclusive: A = (A_1, A_2, \dots, A_N).
Process Q queries described below in the order they are given.

Each query has three integers C, L, and R. Do the following according to the value of C.

• If C = 1: sort A_L, A_{L+1}, \dots, A_R in ascending order.
• If C = 2: sort A_L, A_{L+1}, \dots, A_R in descending order.
• If C = 3: print \displaystyle \sum_{i=L}^R A_i.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 2 \times 10^4
• 0 \leq A_i \leq 10
• 1 \leq C \leq 3
• 1 \leq L \leq R \leq N
• All values in the input are integers.

Sample Input 1

5 5
1 0 8 2 10
3 2 4
1 1 4
3 2 4
2 3 5
3 2 4

Sample Output 1

10
11
19

Initially, A = (1, 0, 8, 2, 10).
For the first query, the answer is 0 + 8 + 2 = 10.
After the second query, A is (0, 1, 2, 8, 10).
For the third query, the answer is 1 + 2 + 8 = 11.
After the fourth query, A is (0, 1, 10, 8, 2).
For the fifth query, the answer is 1 + 10 + 8 = 19.