Problem Statement

Given eight integers S_1,S_2,\dots, and S_8, print Yes if they satisfy all of the following three conditions, and No otherwise.

• The sequence (S_1,S_2,\dots,S_8) is monotonically non-decreasing. In other words, S_1 \leq S_2 \leq \dots \leq S_8.
• S_1,S_2,\dots, and S_8 are all between 100 and 675, inclusive.
• S_1,S_2,\dots, and S_8 are all multiples of 25.

Constraints

• 0\leq S_i \leq 1000
• All input values are integers.

Sample Input 1

125 175 250 300 400 525 600 650

Sample Output 1

Yes

They satisfy all of the three conditions.

Sample Input 2

100 250 300 400 325 575 625 675

Sample Output 2

No

They violate the first condition because S_4 > S_5.

Sample Input 3

0 23 24 145 301 413 631 632

Sample Output 3

No

They violate the second and third conditions.

Problem Statement

Print the L-th through R-th characters of the string atcoder.

Constraints

• L and R are integers.
• 1 \le L \le R \le 7

Sample Input 1

3 6

Sample Output 1

code

The 3-rd through 6-th characters of atcoder are code.

Sample Input 2

4 4

Sample Output 2

o

Sample Input 3

1 7

Sample Output 3

atcoder

Problem Statement

Takahashi is health-conscious and concerned about whether he is getting enough of M types of nutrients from his diet.

For the i-th nutrient, his goal is to take at least A_i units per day.

Today, he ate N foods, and from the i-th food, he took X_{i,j} units of nutrient j.

Determine whether he has met the goal for all M types of nutrients.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 0 \leq A_i, X_{i,j} \leq 10^7
• All input values are integers.

Sample Input 1

2 3
10 20 30
20 0 10
0 100 100

Sample Output 1

Yes

For nutrient 1, Takahashi took 20 units from the 1-st food and 0 units from the 2-nd food, totaling 20 units, thus meeting the goal of taking at least 10 units.
Similarly, he meets the goal for nutrients 2 and 3.

Sample Input 2

2 4
10 20 30 40
20 0 10 30
0 100 100 0

Sample Output 2

No

The goal is not met for nutrient 4.

Problem Statement

N people numbered 1,2,\ldots,N were in M photos. In each of the photos, they stood in a single line. In the i-th photo, the j-th person from the left is person a_{i,j}.

Two people who did not stand next to each other in any of the photos may be in a bad mood.

How many pairs of people may be in a bad mood? Here, we do not distinguish a pair of person x and person y, and a pair of person y and person x.

Constraints

• 2 \leq N \leq 50
• 1 \leq M \leq 50
• 1 \leq a_{i,j} \leq N
• a_{i,1},\ldots,a_{i,N} contain each of 1,\ldots,N exactly once.
• All values in the input are integers.

Sample Input 1

4 2
1 2 3 4
4 3 1 2

Sample Output 1

2

The pair of person 1 and person 4, and the pair of person 2 and person 4, may be in a bad mood.

Sample Input 2

3 3
1 2 3
3 1 2
1 2 3

Sample Output 2

0

Sample Input 3

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

Sample Output 3

6

Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered 1.

You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.

For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?

Constraints

• 1 \leq N \leq 2\times 10^5
• The records are consistent. That is:
  • 1\leq A_i \leq 2i-1.
  • A_i are distinct integers.

Sample Input 1

2
1 2

Sample Output 1

0
1
1
2
2

From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.

• Amoeba 1 is zero generations away from amoeba 1.
• Amoeba 2 is one generation away from amoeba 1.
• Amoeba 3 is one generation away from amoeba 1.
• Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
• Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.

Sample Input 2

4
1 3 5 2

Sample Output 2

0
1
1
2
2
3
3
2
2

Problem Statement

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi's schedule for N days as a string S of length N consisting of 0, 1, and 2.
Specifically, for an integer i satisfying 1\leq i\leq N,

• if the i-th character of S is 0, he has no plan scheduled for the i-th day;
• if the i-th character of S is 1, he plans to go out for a meal on the i-th day;
• if the i-th character of S is 2, he plans to attend a competitive programming event on the i-th day.

Takahashi has M plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

• On days he goes out for a meal, he will wear a plain or logo T-shirt.
• On days he attends a competitive programming event, he will wear a logo T-shirt.
• On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
• Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the N days. If he does not need to buy new T-shirts, print 0.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

• 1\leq M\leq N\leq 1000
• S is a string of length N consisting of 0, 1, and 2.
• N and M are integers.

Sample Input 1

6 1
112022

Sample Output 1

2

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

• On the first day, he wears a logo T-shirt to go out for a meal.
• On the second day, he wears a plain T-shirt to go out for a meal.
• On the third day, he wears a logo T-shirt to attend a competitive programming event.
• On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
• On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
• On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print 2.

Sample Input 2

3 1
222

Sample Output 2

3

Sample Input 3

2 1
01

Sample Output 3

0

He does not need to buy new T-shirts.

Problem Statement

There is a grid of H \times W cells. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

Cell (i, j) is empty if S_{i,j} is ., and blocked if it is #.

Count the number of ways to start from an empty cell and make K moves to adjacent cells (up, down, left, or right), without passing through blocked squares and not visiting the same cell more than once.

Specifically, count the number of sequences of length K+1, ((i_0, j_0), (i_1, j_1), \dots, (i_K, j_K)), satisfying the following.

• 1 \leq i_k \leq H, 1 \leq j_k \leq W, and S_{i_k, j_k} is ., for each 0 \leq k \leq K.
• |i_{k+1} - i_k| + |j_{k+1} - j_k| = 1 for each 0 \leq k \leq K-1.
• (i_k, j_k) \neq (i_l, j_l) for each 0 \leq k < l \leq K.

Constraints

• 1 \leq H, W \leq 10
• 1 \leq K \leq 11
• H, W, and K are integers.
• Each S_{i,j} is . or #.
• There is at least one empty cell.

Sample Input 1

2 2 2
.#
..

Sample Output 1

2

Here are the two possible paths:

• (1,1) \rightarrow (2,1) \rightarrow (2,2)
• (2,2) \rightarrow (2,1) \rightarrow (1,1)

Sample Input 2

2 3 1
.#.
#.#

Sample Output 2

0

Sample Input 3

10 10 11
....#..#..
.#.....##.
..#...##..
...#......
......##..
..#......#
#........#
..##......
.###....#.
...#.....#

Sample Output 3

218070

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N. The elements of A are distinct.

Process Q queries in the order they are given. Each query is of one of the following two types:

• 1 x y : Insert y immediately after the element x in A. It is guaranteed that x exists in A when this query is given.
• 2 x : Remove the element x from A. It is guaranteed that x exists in A when this query is given.

It is guaranteed that after processing each query, A will not be empty, and its elements will be distinct.

Print A after processing all the queries.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq Q \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• A_i \neq A_j
• For queries of the first type, 1 \leq x,y \leq 10^9.
• When a query of the first type is given, x exists in A.
• For queries of the second type, 1 \leq x \leq 10^9.
• When a query of the second type is given, x exists in A.
• After processing each query, A is not empty, and its elements are distinct.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4 5 1 3

The queries are processed as follows:

• Initially, A=(2,1,4,3).
• The first query removes 1, making A=(2,4,3).
• The second query inserts 5 immediately after 4, making A=(2,4,5,3).
• The third query removes 2, making A=(4,5,3).
• The fourth query inserts 1 immediately after 5, making A=(4,5,1,3).

Sample Input 2

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

Sample Output 2

5 1 7 2 3

Problem Statement

This problem fully contains Problem C (Operate 1), with K \le 20.
You can solve Problem C by submitting a correct solution to this problem for Problem C.

Determine whether it is possible to perform the following operation on string S between 0 and K times, inclusive, to make it identical to string T.

• Choose one of the following three operations and execute it.
  • Insert any one character at any position in S (possibly the beginning or end).
  • Delete one character from S.
  • Choose one character in S and replace it with another character.

Constraints

• Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.
• K is an integer satisfying \color{red}{1 \le K \le 20}.

Sample Input 1

3
abc
awtf

Sample Output 1

Yes

For example, here is a way to convert abc to awtf with three operations:

• Replace the second character b with w. After the operation, the string becomes awc.
• Replace the third character c with f. After the operation, the string becomes awf.
• Insert t between the second and third characters. After the operation, the string becomes awtf.

Sample Input 2

2
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf with two or fewer operations.

Sample Input 3

17
twothousandtwentyfour
happynewyear

Sample Output 3

Yes