Problem Statement

Naohiro has a monster. The monster's current health is H.
He also has N kinds of potions, numbered from 1 to N in ascending order of effectiveness.
If you give the monster potion n, its health will increase by P_n. Here, P_1 \lt P_2 \lt \dots \lt P_N.

He wants to increase the monster's health to X or above by giving it one of the potions.
Print the number of the least effective potion that can achieve the purpose. (The constraints guarantee that such a potion exists.)

Constraints

• 2 \leq N \leq 100
• 1 \leq H \lt X \leq 999
• 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
• All input values are integers.

Sample Input 1

3 100 200
50 200 999

Sample Output 1

2

Below is the change in the monster's health when one of the potions is given to the monster.

• If potion 1 is given, the monster's health becomes 100 + 50 = 150.
• If potion 2 is given, the monster's health becomes 100 + 200 = 300.
• If potion 3 is given, the monster's health becomes 100 + 999 = 1099.

The potions that increase the monster's health to at least X = 200 are potions 2 and 3. The answer is the least effective of them, which is potion 2.

Sample Input 2

2 10 21
10 999

Sample Output 2

2

Sample Input 3

10 500 999
38 420 490 585 613 614 760 926 945 999

Sample Output 3

4

Problem Statement

There is a row of N people. They are described by a string S of length N. The i-th person from the front is male if the i-th character of S is M, and female if it is F.

Determine whether the men and women are alternating.

It is said that the men and women are alternating if and only if there is no position where two men or two women are adjacent.

Constraints

• 1 \leq N \leq 100
• N is an integer.
• S is a string of length N consisting of M and F.

Sample Input 1

6
MFMFMF

Sample Output 1

Yes

There is no position where two men or two women are adjacent, so the men and women are alternating.

Sample Input 2

9
FMFMMFMFM

Sample Output 2

No

Sample Input 3

1
F

Sample Output 3

Yes

Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

• -1000 \leq X,Y,Z \leq 1000
• X, Y, and Z are distinct, and none of them is 0.
• All values in the input are integers.

Sample Input 1

10 -10 1

Sample Output 1

10

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

40

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

Problem Statement

Takahashi is trying to create a game inspired by baseball, but he is having difficulty writing the code.
Write a program for Takahashi that solves the following problem.

There are 4 squares called Square 0, Square 1, Square 2, and Square 3. Initially, all squares are empty.
There is also an integer P; initially, P = 0.
Given a sequence of positive integers A = (A_1, A_2, \dots, A_N), perform the following operations for i = 1, 2, \dots, N in this order:

1. Put a piece on Square 0.
2. Advance every piece on the squares A_i squares ahead. In other words, if Square x has a piece, move the piece to Square (x + A_i).
   If, however, the destination square does not exist (i.e. x + A_i is greater than or equal to 4) for a piece, remove it. Add to P the number of pieces that have been removed.

Print the value of P after all the operations have been performed.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 4
• All values in input are integers.

Sample Input 1

4
1 1 3 2

Sample Output 1

3

The operations are described below. After all the operations have been performed, P equals 3.

• The operations for i=1:
  1. Put a piece on Square 0. Now, Square 0 has a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Square 1 has a piece.
• The operations for i=2:
  1. Put a piece on Square 0. Now, Squares 0 and 1 have a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Squares 1 and 2 have a piece.
• The operations for i=3:
  1. Put a piece on Square 0. Now, Squares 0, 1, and 2 have a piece.
  2. Advance every piece on the squares 3 squares ahead.
     Here, for the pieces on Squares 1 and 2, the destination squares do not exist (since 1+3=4 and 2+3=5), so remove these pieces and add 2 to P. P now equals 2. After these moves, Square 3 has a piece.
• The operations for i=4:
  1. Put a piece on Square 0. Now, Squares 0 and 3 have a piece.
  2. Advance every piece on the squares 2 squares ahead.
     Here, for the piece on Square 3, the destination square does not exist (since 3+2=5), so remove this piece and add 1 to P. P now equals 3.
     After these moves, Square 2 has a piece.

Sample Input 2

3
1 1 1

Sample Output 2

0

The value of P may not be updated by the operations.

Sample Input 3

10
2 2 4 1 1 1 4 2 2 1

Sample Output 3

8

Problem Statement

Takahashi sent a string T consisting of lowercase English letters to Aoki. As a result, Aoki received a string T' consisting of lowercase English letters.

T' may have been altered from T. Specifically, exactly one of the following four conditions is known to hold.

• T' is equal to T.
• T' is a string obtained by inserting one lowercase English letter at one position (possibly the beginning and end) in T.
• T' is a string obtained by deleting one character from T.
• T' is a string obtained by changing one character in T to another lowercase English letter.

You are given the string T' received by Aoki and N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters. Find all the strings among S_1, S_2, \ldots, S_N that could equal the string T sent by Takahashi.

Constraints

• N is an integer.
• 1 \leq N \leq 5 \times 10^5
• S_i and T' are strings of length between 1 and 5 \times 10^5, inclusive, consisting of lowercase English letters.
• The total length of S_1, S_2, \ldots, S_N is at most 5 \times 10^5.

Sample Input 1

5 ababc
ababc
babc
abacbc
abdbc
abbac

Sample Output 1

4
1 2 3 4

Among S_1, S_2, \ldots, S_5, the strings that could be equal to T are S_1, S_2, S_3, S_4, as explained below.

• S_1 could be equal to T, because T' = ababc is equal to S_1 = ababc.
• S_2 could be equal to T, because T' = ababc is obtained by inserting the letter a at the beginning of S_2 = babc.
• S_3 could be equal to T, because T' = ababc is obtained by deleting the fourth character c from S_3 = abacbc.
• S_4 could be equal to T, because T' = ababc is obtained by changing the third character d in S_4 = abdbc to b.
• S_5 could not be equal to T, because if we take S_5 = abbac as T, then T' = ababc does not satisfy any of the four conditions in the problem statement.

Sample Input 2

1 aoki
takahashi

Sample Output 2

0

Sample Input 3

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

Sample Output 3

6
1 2 4 7 8 9

Problem Statement

There is a 3\times3 grid with numbers between 1 and 9, inclusive, written in each square. The square at the i-th row from the top and j-th column from the left (1\leq i\leq3,1\leq j\leq3) contains the number c _ {i,j}.

The same number may be written in different squares, but not in three consecutive cells vertically, horizontally, or diagonally. More precisely, it is guaranteed that c _ {i,j} satisfies all of the following conditions.

• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Takahashi will see the numbers written in each cell in random order. He will get disappointed when there is a line (vertical, horizontal, or diagonal) that satisfies the following condition.

• The first two squares he sees contain the same number, but the last square contains a different number.

Find the probability that Takahashi sees the numbers in all the squares without getting disappointed.

Constraints

• c _ {i,j}\in\lbrace1,2,3,4,5,6,7,8,9\rbrace\ (1\leq i\leq3,1\leq j\leq3)
• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Sample Input 1

3 1 9
2 5 6
2 7 1

Sample Output 1

0.666666666666666666666666666667

For example, if Takahashi sees c _ {3,1}=2,c _ {2,1}=2,c _ {1,1}=3 in this order, he will get disappointed.

On the other hand, if Takahashi sees c _ {1,1},c _ {1,2},c _ {1,3},c _ {2,1},c _ {2,2},c _ {2,3},c _ {3,1},c _ {3,2},c _ {3,3} in this order, he will see all numbers without getting disappointed.

The probability that Takahashi sees all the numbers without getting disappointed is \dfrac 23. Your answer will be considered correct if the absolute error from the true value is at most 10 ^ {-8}, so outputs such as 0.666666657 and 0.666666676 would also be accepted.

Sample Input 2

7 7 6
8 6 8
7 7 6

Sample Output 2

0.004982363315696649029982363316

Sample Input 3

3 6 7
1 9 7
5 7 5

Sample Output 3

0.4

Problem Statement

Takahashi is playing with toy trains, connecting and disconnecting them.
There are N toy train cars, with car numbers: Car 1, Car 2, \ldots, Car N.
Initially, all cars are separated.

You will be given Q queries. Process them in the order they are given. There are three kinds of queries, as follows.

• 1 x y: Connect the front of Car y to the rear of Car x.
  It is guaranteed that:

  • x \neq y
  • just before this query, no train is connected to the rear of Car x;
  • just before this query, no train is connected to the front of Car y;
  • just before this query, Car x and Car y belong to different connected components.

• 2 x y: Disconnect the front of Car y from the rear of Car x.
  It is guaranteed that:

  • x \neq y;
  • just before this query, the front of Car y is directly connected to the rear of Car x.

• 3 x: Print the car numbers of the cars belonging to the connected component containing Car x, from front to back.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq x \leq N
• 1 \leq y \leq N
• All values in input are integers.
• All queries satisfy the conditions in the Problem Statement.
• The queries of the format 3 x ask to print at most 10^6 car numbers in total.

Sample Input 1

7 14
1 6 3
1 4 1
1 5 2
1 2 7
1 3 5
3 2
3 4
3 6
2 3 5
2 4 1
1 1 5
3 2
3 4
3 6

Sample Output 1

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

The figure below shows the cars when the first 5 queries are processed.
For example, Car 2 belongs to the same connected component as Cars 3, 5, 6, 7, which is different from the connected component containing Cars 1, 4.

The figure below shows the cars when the first 11 queries are processed.

Problem Statement

A string consisting of 0 and 1 is called a good string if two consecutive characters in the string are always different.
You are given a string S of length N consisting of 0 and 1. Q queries will be given and must be processed in order.
There are two types of queries:

• 1 L R: Flip each of the L-th to R-th characters of S. That is, for each integer i satisfying L\leq i\leq R, change the i-th character of S to 0 if it is 1, and vice versa.
• 2 L R: Let S' be the string of length (R-L+1) obtained by extracting the L-th to R-th characters of S (without changing the order). Print Yes if S' is a good string and No otherwise.

Constraints

• 1\leq N, Q\leq 5\times 10^5
• S is a string of length N consisting of 0 and 1.
• 1\leq L\leq R\leq N for queries of types 1 and 2.
• There is at least one query of type 2.
• N, Q, L, and R are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes
No

Initially, S=10100. When processing the queries in the order they are given, the following occurs:

• For the first query, the string obtained by extracting the 1-st to 3-rd characters of S is S'=101. This is a good string, so print Yes.
• For the second query, the string obtained by extracting the 1-st to 5-th characters of S is S'=10100. This is not a good string, so print No.
• For the third query, flip each of the 1-st to 4-th characters of S. The string S becomes S=01010.
• For the fourth query, the string obtained by extracting the 1-st to 5-th character of S is S'=01010. This is a good string, so print Yes.
• For the fifth query, flip the 3-rd character of S. The string S becomes S=01110.
• For the sixth query, the string obtained by extracting the 2-nd to 4-th character of S is S'=111. This is not a good string, so print No.

Sample Input 2

1 2
1
1 1 1
2 1 1

Sample Output 2

Yes

Note that a string of a single character 0 or 1 satisfies the condition of being a good string.

Problem Statement

A monster with health H has appeared in front of you, and a turn-based battle has started.

In each turn 1,2,…, you cast one of N spells, spells 1,…,N.

If you cast spell i in turn j, the monster's health reduces by d_i in each turn j,j+1,…,j+t_i －1.

Find the earliest turn that you can make the monster's health 0 or less.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq H \leq 10^{18}
• 1 \leq t_i,d_i \leq 10^9
• All values in the input are integers.

Sample Input 1

2 20
2 2
5 1

Sample Output 1

6

The following procedure makes the monster's health 0 or less in turn 6, which is the earliest.

• Cast spell 1 in turn 1. Due to the spell cast in turn 1, the monster's health reduces by 2 and becomes 18.
• Cast spell 2 in turn 2. Due to the spells cast in turns 1 and 2, the monster's health reduces by 2+1=3 and becomes 15.
• Cast spell 1 in turn 3. Due to the spells cast in turns 2 and 3, the monster's health reduces by 1+2=3 and becomes 12.
• Cast spell 2 in turn 4. Due to the spells cast in turns 2,3 and 4, the monster's health reduces by 1+2+1=4 and becomes 8.
• Cast spell 1 in turn 5. Due to the spells cast in turns 2,4 and 5, the monster's health reduces by 1+1+2=4 and becomes 4.
• Cast spell 2 in turn 6. Due to the spells cast in turns 2,4,5 and 6, the monster's health reduces by 1+1+2+1=5 and becomes -1.

Sample Input 2

10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4

Sample Output 2

9