Problem Statement

You are given an integer S between 100 and 999 (inclusive).

If S is between 200 and 299 (inclusive), print Success; otherwise, print Failure.

Constraints

• 100 \le S \le 999
• S is an integer.

Sample Input 1

200

Sample Output 1

Success

200 is between 200 and 299, so print Success.

Sample Input 2

401

Sample Output 2

Failure

401 is not between 200 and 299, so print Failure.

Sample Input 3

999

Sample Output 3

Failure

Problem Statement

For a positive integer X, the Dragon String of level X is a string of length (X+3) formed by one L, X occurrences of o, one n, and one g arranged in this order.

You are given a positive integer N. Print the Dragon String of level N.
Note that uppercase and lowercase letters are distinguished.

Constraints

• 1 \leq N \leq 2024
• N is an integer.

Sample Input 1

3

Sample Output 1

Looong

Arranging one L, three os, one n, and one g in this order yields Looong.

Sample Input 2

1

Sample Output 2

Long

Problem Statement

There are A slimes.

Each time Snuke shouts, the slimes multiply by K times.

In order to have B or more slimes, at least how many times does Snuke need to shout?

Constraints

• 1 \leq A \leq B \leq 10^9
• 2 \leq K \leq 10^9
• All values in input are integers.

Sample Input 1

1 4 2

Sample Output 1

2

We start with one slime. After Snuke's first shout, we have two slimes; after his second shout, we have four slimes. Thus, he needs to shout at least twice to have four or more slimes.

Sample Input 2

7 7 10

Sample Output 2

0

We have seven slimes already at the start.

Sample Input 3

31 415926 5

Sample Output 3

6

Problem Statement

You are given strings S and T consisting of lowercase and uppercase English letters.

Determine whether the string S satisfies the following condition:

• Every uppercase letter in S that is not at the beginning is immediately preceded by a character contained in T. More formally, for all integers i such that 2 \leq i \leq |S|, if the i-th character of S is uppercase, then the (i-1)-th character of S is contained in T.

Constraints

• Each of S and T is a string consisting of lowercase and uppercase English letters with length between 1 and 100, inclusive.

Sample Input 1

AtCoder
Total

Sample Output 1

Yes

The only uppercase letter in S that is not at the beginning is the 3rd character C. The immediately preceding character t is contained in T, so output Yes.

Sample Input 2

aBCdE
abcdcba

Sample Output 2

No

The 3rd character of S is the uppercase letter C, and its immediately preceding character is B, but B is not contained in T.

Sample Input 3

abcde
XYZ

Sample Output 3

Yes

Problem Statement

We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.

We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?

Here, we distinguish all balls, even with the same numbers written on them.

Constraints

• N \geq 2
• L_i \geq 2
• The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
• 1 \leq a_{i,j} \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

2 40
3 1 8 4
2 10 5

Sample Output 1

2

When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.

Sample Input 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

Sample Output 2

45

Note that we distinguish all balls, even with the same numbers written on them.

Sample Input 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

Sample Output 3

0

There may be no way to make the product X.

Problem Statement

You are given a simple undirected graph with N vertices and M edges, where the vertices are labeled 1 to N. The i-th edge connects vertices u_i and v_i.
What is the minimum number of edges that need to be deleted from this graph so that the graph becomes a forest?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min \left( \frac{N(N-1)}{2}, 2 \times 10^5\right)
• 1 \leq u_i < v_i \leq N
• The given graph is simple.
• All input values are integers.

Sample Input 1

4 4
1 2
1 3
2 4
3 4

Sample Output 1

1

For example, if you delete the first edge, the graph becomes a forest.

Sample Input 2

5 0

Sample Output 2

0

Sample Input 3

10 10
7 9
4 6
6 10
2 5
5 6
5 9
6 8
4 8
1 5
1 4

Sample Output 3

2

Problem Statement

There are N houses numbered from 1 to N on a number line. House i is located at coordinate X_i. Multiple houses may be located at the same coordinate.

You place M base stations at arbitrary real coordinates on the number line. Then, you set a non-negative integer signal strength for each base station.

When the signal strength of a base station is set to x, The signal from that base station reaches a house if and only if the distance between the base station and the house is at most \displaystyle\frac{x}{2}. Particularly, when x=0, the signal reaches only houses located at the same coordinate as the base station.

Find the minimum possible sum of signal strengths when the positions and signal strengths of the base stations are set such that at least one base station's signal reaches every house.

It can be proved that the answer is an integer for any input satisfying the constraints.

Constraints

• 1 \leq M \leq N \leq 5 \times 10^5
• 1 \leq X_i \leq 10^{12} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

7 3
5 10 15 20 8 14 15

Sample Output 1

6

By placing three base stations as follows, signals reach all houses.

• Place a base station with signal strength 5 at coordinate 7.5. This base station reaches houses 1,2,5.
• Place a base station with signal strength 1 at coordinate 14.5. This base station reaches houses 3,6,7.
• Place a base station with signal strength 0 at coordinate 20. This base station reaches house 4.

The sum of signal strengths in this case is 6.

It is impossible to satisfy the condition with an arrangement where the sum of signal strengths is smaller than 6, so output 6.

Sample Input 2

7 7
5 10 15 20 8 14 15

Sample Output 2

0

Sample Input 3

7 1
5 10 15 20 8 14 15

Sample Output 3

15

Problem Statement

There are N towns numbered 1, \dots, N, and M roads numbered 1, \dots, M.
Every road is directed; road i (1 \leq i \leq M) leads you from Town A_i to Town B_i. The length of road i is C_i.

You are given a sequence E = (E_1, \dots, E_K) of length K consisting of integers between 1 and M. A way of traveling from town 1 to town N using roads is called a good path if:

• the sequence of the roads' numbers arranged in the order used in the path is a subsequence of E.

Note that a subsequence of a sequence is a sequence obtained by removing 0 or more elements from the original sequence and concatenating the remaining elements without changing the order.

Find the minimum sum of the lengths of the roads used in a good path.
If there is no good path, report that fact.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M, K \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N, A_i \neq B_i \, (1 \leq i \leq M)
• 1 \leq C_i \leq 10^9 \, (1 \leq i \leq M)
• 1 \leq E_i \leq M \, (1 \leq i \leq K)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4

There are two possible good paths as follows:

• Using road 4. In this case, the sum of the length of the used road is 5.
• Using road 1 and 2 in this order. In this case, the sum of the lengths of the used roads is 2 + 2 = 4.

Therefore, the desired minimum value is 4.

Sample Input 2

3 2 3
1 2 1
2 3 1
2 1 1

Sample Output 2

-1

There is no good path.

Sample Input 3

4 4 5
3 2 2
1 3 5
2 4 7
3 4 10
2 4 1 4 3

Sample Output 3

14

Problem Statement

You are given a grid with three rows and N columns. Denote the cell at the i-th row from the top and j-th column from the left as cell (i,j). Cell (i,j) is a wall cell if S_{i,j} is #, and an empty cell and passable if it is ..

You are given Q queries, which you should process in order.

Each query gives integers r and c, and you should flip the state of cell (r,c). That is, if cell (r,c) is a wall cell, make it an empty cell, and if it is an empty cell, make it a wall cell. Then, output the answer to the following problem:

Consider moving from cell (1,1) to cell (3,N) by repeatedly moving to an empty cell adjacent up, down, left, or right. Determine whether cell (3,N) is reachable, and if reachable, find the minimum number of moves.

Constraints

• 2\le N\le 2\times 10^5
• S_{i,j} is # or ..
• S_{1,1}=S_{3,N}= .
• 1\le Q\le 2\times 10^5
• 1\le r\le 3
• 1\le c\le N
• (r,c) \neq (1,1),(3,N)
• N,Q,r,c are integers.

Sample Input 1

5
.#...
.#.#.
...#.
3
1 2
1 2
2 3

Sample Output 1

6
10
-1

In the first query, flip the state of cell (1,2). As a result, the state of each cell becomes:

.....
.#.#.
...#.

At this time, by moving from cell (1,1) through cells (1,2),(1,3),(1,4),(1,5),(2,5),(3,5) in order, you can reach cell (3,5) in six moves.

In the second query, flip the state of cell (1,2). As a result, the state of each cell becomes:

.#...
.#.#.
...#.

At this time, by moving from cell (1,1) through cells (2,1),(3,1),(3,2),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5) in order, you can reach cell (3,5) in ten moves.

In the third query, flip the state of cell (2,3). As a result, the state of each cell becomes:

.#...
.###.
...#.

At this time, no matter how you move, you cannot reach cell (3,5) from cell (1,1).

Sample Input 2

7
.#.....
.#..#..
...#...
6
2 5
3 4
3 5
2 5
1 4
1 4

Sample Output 2

10
8
10
12
-1
12