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 a length-N sequence A=(A_1,A_2,\ldots,A_N) of positive integers.

Determine whether A is a geometric progression.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5
3 6 12 24 48

Sample Output 1

Yes

A=(3,6,12,24,48).
A is a geometric progression with first term 3, common ratio 2, and five terms.
Therefore, print Yes.

Sample Input 2

3
1 2 3

Sample Output 2

No

A=(1,2,3).
Since A_1 : A_2 = 1 : 2 \neq 2 : 3 = A_2 : A_3, A is not a geometric progression.
Therefore, print No.

Sample Input 3

2
10 8

Sample Output 3

Yes

A is a geometric progression with first term 10, common ratio 0.8, and two terms.
Therefore, print Yes.

Problem Statement

You are given a grid of H rows and W columns.
Let (i,j) denote the cell at row i (1 \leq i \leq H) from the top and column j (1 \leq j \leq W) from the left.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H, each of length W, as follows:

• If the j-th character of S_i is #, cell (i,j) is painted black.
• If the j-th character of S_i is ., cell (i,j) is painted white.
• If the j-th character of S_i is ?, cell (i,j) is not yet painted.

Takahashi wants to paint each not-yet-painted cell white or black so that all the black cells form a rectangle.
More precisely, he wants there to exist a quadruple of integers (a,b,c,d) (1 \leq a \leq b \leq H, 1 \leq c \leq d \leq W) such that:

For each cell (i,j) (1 \leq i \leq H, 1 \leq j \leq W), if a \leq i \leq b and c \leq j \leq d, the cell is black;
otherwise, the cell is white.

Determine whether this is possible.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• Each S_i is a string of length W consisting of #, ., ?.
• There is at least one cell that is already painted black.

Sample Input 1

3 5
.#?#.
.?#?.
?...?

Sample Output 1

Yes

The grid is in the following state. ? indicates a cell that are not yet painted.

By painting cells (1,3), (2,2), and (2,4) black and cells (3,1) and (3,5) white, the black cells can form a rectangle as follows:

Therefore, print Yes.

Sample Input 2

3 3
?##
#.#
##?

Sample Output 2

No

To form a rectangle with all black cells, you would need to paint cell (2,2) black, but it is already painted white.
Therefore, it is impossible to make all black cells form a rectangle, so print No.

Sample Input 3

1 1
#

Sample Output 3

Yes

Problem Statement

There are N bags, labeled bag 1, bag 2, \ldots, bag N.
Bag i (1 \leq i \leq N) contains A_i stones.

Takahashi can perform the following operation any number of times, possibly zero:

Choose two bags A and B, and move all stones from bag A into bag B.

Find the number of different possible values for the following after repeating the operation.

• B_1 \oplus B_2 \oplus \cdots \oplus B_N, where B_i is the final number of stones in bag i.
  Here, \oplus denotes bitwise XOR.

It can be proved that under the constraints of this problem, the number of possible values is finite.

Constraints

• 2 \leq N \leq 12
• 1 \leq A_i \leq 10^{17}
• All input values are integers.

Sample Input 1

3
2 5 7

Sample Output 1

3

For example, if Takahashi chooses bags 1 and 3 for the operation, then the numbers of stones in bags 1, 2, 3 become 0, 5, 9.
If he stops at this point, the XOR is 0 \oplus 5 \oplus 9 = 12.

The other possible XOR values after repeating the operation are 0 and 14.
Therefore, the possible values are 0, 12, 14; there are three values, so the output is 3.

Sample Input 2

2
100000000000000000 100000000000000000

Sample Output 2

2

Sample Input 3

6
71 74 45 34 31 60

Sample Output 3

84

Problem Statement

There are N foods, each containing exactly one of vitamins 1, 2, and 3.
Specifically, eating the i-th food gives you A_i units of vitamin V_i, and C_i calories.

Takahashi can choose any subset of these N foods as long as the total calorie consumption does not exceed X.
Find the maximum possible value of this: the minimum intake among vitamins 1, 2, and 3.

Constraints

• 1 \leq N \leq 5000
• 1 \leq X \leq 5000
• 1 \leq V_i \leq 3
• 1 \leq A_i \leq 2 \times 10^5
• 1 \leq C_i \leq X
• All input values are integers.

Sample Input 1

5 25
1 8 5
2 3 5
2 7 10
3 2 5
3 3 10

Sample Output 1

3

Each food provides the following if eaten:

• 1st food: 8 units of vitamin 1, and 5 calories
• 2nd food: 3 units of vitamin 2, and 5 calories
• 3rd food: 7 units of vitamin 2, and 10 calories
• 4th food: 2 units of vitamin 3, and 5 calories
• 5th food: 3 units of vitamin 3, and 10 calories

Eating the 1st, 2nd, 4th, and 5th foods gives 8 units of vitamin 1, 3 units of vitamin 2, 5 units of vitamin 3, and 25 calories.
In this case, the minimum among the three vitamin intakes is 3 (vitamin 2).

It is impossible to get 4 or more units of each vitamin without exceeding 25 calories, so the answer is 3.

Sample Input 2

2 5000
1 200000 1
2 200000 1

Sample Output 2

0

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

For each integer pair (L,R) with 1 \le L \le R \le N, define f(L,R) as follows:

• Start with an empty blackboard. Write the R-L+1 integers A_L, A_{L+1}, \ldots, A_R on the blackboard in order.
• Repeat the following operation until all integers on the blackboard are erased:
  • Choose integers l, r with l \le r such that every integer from l through r appears at least once on the blackboard. Then, erase all integers from l through r that are on the blackboard.
• Let f(L,R) be the minimum number of such operations needed to erase all the integers from the blackboard.

Find \displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R).

Constraints

• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le N
• All input values are integers.

Sample Input 1

4
1 3 1 4

Sample Output 1

16

For example, in the case of (L,R)=(1,4):

• The blackboard has 1,3,1,4.
• Choose (l,r)=(1,1) and erase all occurrences of 1. The blackboard now has 3,4.
• Choose (l,r)=(3,4) and erase all occurrences of 3 and 4. The blackboard becomes empty.
• It cannot be done in fewer than two operations, so f(1,4) = 2.

Similarly, you can find f(2,4)=2, f(1,1)=1, etc.

\displaystyle \sum_{L=1}^N \sum_{R=L}^N f(L,R) = 16, so print 16.

Sample Input 2

5
3 1 4 2 4

Sample Output 2

23

Sample Input 3

10
5 1 10 9 2 5 6 9 1 6

Sample Output 3

129

Problem Statement

You are given a positive integer N.

For an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Let f(A) be the integer obtained as follows:

• Let S be an empty string.
• For i=1,2,\ldots,N in this order:
  • Let T be the decimal representation of A_i without leading zeros.
  • Append T to the end of S.
• Interpret S as a decimal integer, and let that be f(A).

For example, if A=(1,20,34), then f(A)=12034.

There are N! permutations P of (1,2,\ldots,N). Find the sum, modulo 998244353, of f(P) over all such permutations P.

Constraints

• 1 \le N \le 2 \times 10^5
• All input values are integers.

Sample Input 1

3

Sample Output 1

1332

The six permutations of (1,2,3) are (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Their f(P) values are 123,132,213,231,312,321. Therefore, print 123+132+213+231+312+321 = 1332.

Sample Input 2

390

Sample Output 2

727611652

Print the sum modulo 998244353.

Sample Input 3

79223

Sample Output 3

184895744