Problem Statement

You are given a positive integer N.

Output N, N-1, \dots, 1 in this order, separated by commas ,.

Constraints

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

Sample Input 1

9

Sample Output 1

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

Sample Input 2

5

Sample Output 2

5,4,3,2,1

Sample Input 3

1

Sample Output 3

1

Problem Statement

There are N stations 1, 2, \dots, N, arranged in a straight line from west to east in this order.
The AtCoder Railway train passes through these N stations and runs from west to east.
For any two integers i, j satisfying 1 \leq i \lt j \leq N, the cost of boarding the train at station i and getting off at station j is C_{i,j}.

Determine whether there exist three integers a, b, c such that:

• 1 \leq a \lt b \lt c \leq N
• The total cost of boarding the train at station a, getting off at station b, then boarding the train again at station b, and getting off at station c is less than the cost of boarding the train at station a and getting off at station c.

Constraints

• 3 \leq N \leq 100
• 1 \leq C_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

3
45 450
45

Sample Output 1

Yes

Choosing (a, b, c) = (1, 2, 3),
C_{a,b}+C_{b,c}=C_{1,2}+C_{2,3}=45+45
C_{a,c}=C_{1,3}=450
so the conditions are satisfied.

Sample Input 2

4
25 40 65
30 55
25

Sample Output 2

No

No choice of (a, b, c) satisfies the conditions.

Problem Statement

There is a grid with H rows and W columns.
The cell at the i-th row from the top and j-th column from the left is painted black if S_{i,j} is #, and white if S_{i,j} is ..

Among the four-directionally connected regions consisting of white cells, find the number of those that are surrounded by black cells.

Below is a more formal statement.

We denote the cell at the i-th row from the top and j-th column from the left as cell (i, j).
Two cells (i, j) and (i', j') are said to be adjacent if and only if |i-i'|+|j-j'|=1.
A set C of white cells is said to be connected if and only if, for any two cells c and c' in C, it is possible to move from c to c' by repeatedly moving to an adjacent cell in C.
A non-empty connected set of white cells that is maximal is called a connected component of white cells.
Find the number of connected components of white cells that do not contain any cell on the outermost border of the grid (that is, in row 1, row H, column 1, or column W).

Constraints

• 3 \leq H, W \leq 10^3
• H and W are integers.
• S_{i,j} is # or ..

Sample Input 1

5 15
##########..###
#...#######.###
####....###..##
######.########
########....###

Sample Output 1

2

There are two such regions: the region consisting of the three cells in row 2 from the top and columns 2, 3, 4 from the left, and the region consisting of a total of five cells: columns 5, 6, 7, 8 from the left in row 3 from the top and column 7 from the left in row 4 from the top.

Sample Input 2

10 22
######################
####.#################
###...################
##.###.##.....########
##.....##.####.#######
.######.#......#.....#
.######.#.####.#.#####
#########.....##.#####
################.#####
################.....#

Sample Output 2

4

Problem Statement

You are given a sequence A of N positive integers and a positive integer K.
You can perform the following operation on the sequence A any number of times.

• Choose an integer i with 1 \leq i \leq N, and add K to A_i.

Find the minimum possible value of \max(A) - \min(A).

Constraints

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

Sample Input 1

3 10
3 21 9

Sample Output 1

4

First, choosing i=1 makes the sequence A=(13,21,9).
Next, choosing i=3 makes the sequence A=(13,21,19).
Next, choosing i=1 makes the sequence A=(23,21,19).
At this point, \max(A)-\min(A)=23-19=4.
It is impossible to make \max(A)-\min(A) at most 3, so the answer is 4.

Sample Input 2

5 6
4 100 5 10 450

Sample Output 2

2

Problem Statement

You are given strings X and Y. Define a sequence of strings S_1, S_2, \dots as follows.

• S_1 = X
• S_2 = Y
• For i \geq 3, S_i is the concatenation of S_{i-1} and S_{i-2} in this order.

For each i = 1, 2, \ldots, Q, answer the following problem.

Problem: You are given integers L_i, R_i and a character C_i. Find how many times character C_i appears in the L_i-th through R_i-th characters of S_{10^{18}}.

Constraints

• X and Y are strings of lowercase English letters of length between 1 and 10^4, inclusive.
• 1 \leq Q \leq 10^5
• 1 \leq L_i \leq R_i \leq 10^{18}
• C_i is a lowercase English letter.
• All given numerical values are integers.

Sample Input 1

a
b
6
2 7 a
1 3 b
3 7 b
1 9 c
1 1000000000000000000 b
1000000000000000000 1000000000000000000 a

Sample Output 1

3
2
3
0
618033988749894848
1

S_3, S_4, S_5 are ba, bab, babba, respectively.

S_{10^{18}} is babbababbabba..., and the second through seventh characters contain three occurrences of a.

Problem Statement

There is a directed graph with N vertices and N-1+M edges, with edges and vertices numbered.
For 1 \leq i \leq M, edge i is a directed edge from vertex X_i to vertex Y_i, and for 1 \leq i \leq N-1, edge M+i is a directed edge from vertex i+1 to vertex i.

There are 2^M ways to choose some (possibly zero) edges from among edges 1, 2, \dots, M. Among these ways, how many result in the graph being strongly connected after deleting the chosen edges? Find the count modulo 998244353.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1 \leq X_i < Y_i \leq N
• All input values are integers.

Sample Input 1

4 3
1 4
1 3
2 4

Sample Output 1

5

The graph is strongly connected when the set of chosen edge indices is one of \{\}, \{1\}, \{2\}, \{3\}, \{2,3\}, giving five ways.

Sample Input 2

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

Sample Output 2

1297

The given graph may have multi-edges.

Problem Statement

You are given a sequence A of N non-negative integers.
Repeat the following operation until A has exactly one element.

• Choose two distinct integers i and j satisfying 1 \leq i, j \leq |A| uniformly at random.
• Let a and b be A_i and A_j, respectively.
• Remove the i-th and j-th elements from A.
• Append a - b to the end of A.

Let x be the only element of A at the end. Find the expected value of x^2, modulo 998244353.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 998244352
• All input values are integers.

Sample Input 1

3
4 5 0

Sample Output 1

665496263

First, choosing (i, j) = (3, 1) makes the sequence (5, -4).
Next, choosing (i, j) = (1, 2) makes the sequence (9).
x^2 equals 81 with probability \frac{1}{3} and 1 with probability \frac{2}{3}, so the expected value is \frac{83}{3}.

Sample Input 2

5
450 2026 3 21 100

Sample Output 2

669406799