Problem Statement

You are given an integer sequence A=(A_1,A_2,A_3,A_4,A_5) obtained by permuting (1,2,3,4,5).

Determine whether A can be sorted in ascending order by performing exactly one operation of swapping two adjacent elements in A.

Constraints

• A is an integer sequence of length 5 obtained by permuting (1,2,3,4,5).

Sample Input 1

1 2 4 3 5

Sample Output 1

Yes

By swapping A_3 and A_4, A becomes (1,2,3,4,5), so it can be sorted in ascending order. Therefore, print Yes.

Sample Input 2

5 3 2 4 1

Sample Output 2

No

No matter what operation is performed, it is impossible to sort A in ascending order.

Sample Input 3

1 2 3 4 5

Sample Output 3

No

You must perform exactly one operation.

Sample Input 4

2 1 3 4 5

Sample Output 4

Yes

Problem Statement

You are given an integer Y between 1583 and 2023.

Find the number of days in the year Y of the Gregorian calendar.

Within the given range, the year Y has the following number of days:

• if Y is not a multiple of 4, then 365 days;

• if Y is a multiple of 4 but not a multiple of 100, then 366 days;

• if Y is a multiple of 100 but not a multiple of 400, then 365 days;

• if Y is a multiple of 400, then 366 days.

Constraints

• Y is an integer between 1583 and 2023, inclusive.

Sample Input 1

2023

Sample Output 1

365

2023 is not a multiple of 4, so it has 365 days.

Sample Input 2

1992

Sample Output 2

366

1992 is a multiple of 4 but not a multiple of 100, so it has 366 days.

Sample Input 3

1800

Sample Output 3

365

1800 is a multiple of 100 but not a multiple of 400, so it has 365 days.

Sample Input 4

1600

Sample Output 4

366

1600 is a multiple of 400, so it has 366 days.

Problem Statement

You are given two strings S and T consisting of lowercase English letters. Determine if S is a prefix of T.

Constraints

• S and T are strings of lengths between 1 and 100 (inclusive) consisting of lowercase English letters.

Sample Input 1

atco
atcoder

Sample Output 1

Yes

atco is a prefix of atcoder. Thus, Yes should be printed.

Sample Input 2

code
atcoder

Sample Output 2

No

code is not a prefix of atcoder. Thus, No should be printed.

Sample Input 3

abc
abc

Sample Output 3

Yes

Note that a string is also a prefix of itself.

Sample Input 4

aaaa
aa

Sample Output 4

No

Problem Statement

In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?

Constraints

• 1 \leq N \leq 1000
• 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

6
1 4 1 2 2 1

Sample Output 1

3

There are three different integers: 1, 2, 4.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

11
3 1 4 1 5 9 2 6 5 3 5

Sample Output 3

7

Problem Statement

There are N squares arranged in a row from left to right. Initially, all squares are painted white.

Process Q queries in order. The i-th query gives an integer A_i between 1 and N, inclusive, and performs the following operation:

Flip the color of the A_i-th square from the left. Specifically, if the A_i-th square from the left is painted white, paint it black; if it is painted black, paint it white.
Then, find the number of intervals of consecutively painted black squares.

Here, an interval of consecutively painted black squares is a pair of integers (l,r) (1\leq l\leq r\leq N) that satisfy all of the following:

• The l-th, (l+1)-th, \ldots, r-th squares from the left are all painted black.
• Either l=1, or the (l-1)-th square from the left is painted white.
• Either r=N, or the (r+1)-th square from the left is painted white.

Constraints

• 1\leq N,Q\leq 5\times 10^5
• 1\leq A_i\leq N
• All input values are integers.

Sample Input 1

5 7
2 3 3 5 1 5 2

Sample Output 1

1
1
1
2
2
1
1

Below, the i-th square from the left is referred to as square i.
After each query, the state is as follows:

• After the 1st query, only square 2 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,2).
• After the 2nd query, squares 2,3 are painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,3).
• After the 3rd query, only square 2 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(2,2).
• After the 4th query, squares 2,5 are painted black. There are 2 intervals of consecutively painted black squares: (l,r)=(2,2), (5,5).
• After the 5th query, squares 1,2,5 are painted black. There are 2 intervals of consecutively painted black squares: (l,r)=(1,2), (5,5).
• After the 6th query, only squares 1,2 are painted black. There is 1 interval of consecutively painted black squares: (l,r)=(1,2).
• After the 7th query, only square 1 is painted black. There is 1 interval of consecutively painted black squares: (l,r)=(1,1).

Thus, output 1,1,1,2,2,1,1 separated by newlines.

Sample Input 2

1 2
1 1

Sample Output 2

1
0

After the 2nd query, all squares are painted white, so output 0 on the 2nd line.

Sample Input 3

3 3
1 3 2

Sample Output 3

1
2
1

Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

• Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N-1
• 1 \leq a_i \leq 10^9
• All values in input are integers.

Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

• Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
• Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.

Problem Statement

You are given an integer W.
You are going to prepare some weights so that all of the conditions below are satisfied.

• The number of weights is between 1 and 300, inclusive.
• Each weight has a mass of positive integer not exceeding 10^6.
• Every integer between 1 and W, inclusive, is a good integer. Here, a positive integer n is said to be a good integer if the following condition is satisfied:
  • We can choose at most 3 different weights from the prepared weights with a total mass of n.

Print a combination of weights that satisfies the conditions.

Constraints

• 1 \leq W \leq 10^6
• W is an integer.

Sample Input 1

6

Sample Output 1

3
1 2 3

In the output above, 3 weights with masses 1, 2, and 3 are prepared.
This output satisfies the conditions. Especially, regarding the 3-rd condition, we can confirm that every integer between 1 and W, inclusive, is a good integer.

• If we choose only the 1-st weight, it has a total mass of 1.
• If we choose only the 2-nd weight, it has a total mass of 2.
• If we choose only the 3-rd weight, it has a total mass of 3.
• If we choose the 1-st and the 3-rd weights, they have a total mass of 4.
• If we choose the 2-nd and the 3-rd weights, they have a total mass of 5.
• If we choose the 1-st, the 2-nd, and the 3-rd weights, they have a total mass of 6.

Sample Input 2

12

Sample Output 2

6
2 5 1 2 5 1

You may prepare multiple weights with the same mass.

Problem Statement

An election is being held with N candidates numbered 1, 2, \ldots, N. There are K votes, some of which have been counted so far.

Up until now, candidate i has received A_i votes.

After all ballots are counted, candidate i (1 \leq i \leq N) will be elected if and only if the number of candidates who have received more votes than them is less than M. There may be multiple candidates elected.

For each candidate, find the minimum number of additional votes they need from the remaining ballots to guarantee their victory regardless of how the other candidates receive votes.

Formally, solve the following problem for each i = 1,2,\ldots,N.

Determine if there is a non-negative integer X not exceeding K - \displaystyle{\sum_{i=1}^{N}} A_i satisfying the following condition. If it exists, find the minimum possible such integer.

• If candidate i receives X additional votes, then candidate i will always be elected.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{12}
• 0 \leq A_i \leq 10^{12}
• \displaystyle{\sum_{i=1}^{N} A_i} \leq K
• All input values are integers.

Sample Input 1

5 2 16
3 1 4 1 5

Sample Output 1

2 -1 1 -1 0

14 votes have been counted so far, and 2 votes are left.
The C to output is (2, -1, 1, -1, 0). For example:

• Candidate 1 can secure their victory by obtaining 2 more votes, while not by obtaining 1 more vote. Thus, C_1 = 2.
• Candidate 2 can never (even if they obtain 2 more votes) secure their victory, so C_2 = -1.

Sample Input 2

12 1 570
81 62 17 5 5 86 15 7 79 26 6 28

Sample Output 2

79 89 111 117 117 74 112 116 80 107 117 106

Problem Statement

There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is black or white, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:

• if the j-th character of S_i is ., square (i,j) is white;
• if the j-th character of S_i is #, square (i,j) is black.

The grid is said to be beautiful when the following condition is satisfied.

• For every pair of integers (i,j) such that 1 \le i \le N, 1 \le j \le M, if square (i,j) is black, the square under (i,j) and the square to the immediate lower right of (i,j) are also black (if they exist).
• Formally, all of the following are satisfied.
  • If square (i,j) is black and square (i+1,j) exists, square (i+1,j) is also black.
  • If square (i,j) is black and square (i+1,j+1) exists, square (i+1,j+1) is also black.

Takahashi can paint zero or more white squares black, and he will do so to make the grid beautiful.
Find the number of different beautiful grids he can make, modulo 998244353.
Two grids are considered different when there is a square that has different colors in those two grids.

Constraints

• 1 \le N,M \le 2000
• S_i is a string of length M consisting of . and #.

Sample Input 1

2 2
.#
..

Sample Output 1

3

He can make the following three different beautiful grids:

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

Sample Input 2

5 5
....#
...#.
..#..
.#.#.
#...#

Sample Output 2

92

Sample Input 3

25 25
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................

Sample Output 3

604936632

Find the count modulo 998244353.