Problem Statement

A positive integer x is said to be a beautiful integer if and only if x is a 9-digit integer whose decimal notation S_1\ldots S_9 (S_i is the i-th character) satisfies all of the following conditions:

• S_1 is not 0,
• S_1 = S_2,
• S_5 = S_6, and
• S_7 = S_9.

For instance, 998244353 and 333333333 are beautiful integers, while 111112222 is not, since S_5 \neq S_6.

You are given a positive integer N. Print the N-th smallest beautiful integer.

Constraints

• N is a positive integer.
• There are at least N beautiful integers.

Sample Input 1

3

Sample Output 1

110000020

The beautiful integers in ascending order are 110000000, 110000010, 110000020, \ldots.

Sample Input 2

882436

Sample Output 2

998244353

Sample Input 3

2023

Sample Output 3

110200222

Problem Statement

We have a grid with H rows from top to bottom and W columns from left and right. Initially, the square at the i-th row from the top and j-th column from the left has a lowercase English letter A_{i,j}.

Let us perform Q operations on this grid. In the i-th operation, we are given integers a_i and b_i such that 1\leq a_i \leq H-1 and 1\leq b_i\leq W-1, and do the following.

• Let R_1, R_2, R_3, and R_4 be rectangular regions within the grid defined as follows:
  • R_1 is the intersection of the top a_i rows and leftmost b_i columns;
  • R_2 is the intersection of the top a_i rows and rightmost W-b_i columns;
  • R_3 is the intersection of the bottom H-a_i rows and leftmost b_i columns;
  • R_4 is the intersection of the bottom H-a_i rows and rightmost W-b_i columns.
• Rotate 180 degrees each of R_1, R_2, R_3, and R_4.

Here, a 180-degree rotation of a rectangular region R within the grid moves the character on the square at the i-th from the top and j-th column from the left in R to the square at the i-th from the bottom and j-th column from the right in R. See also the figures for the samples.

Print the grid after all Q operations.

Constraints

• 2\leq H, W, and HW \leq 5\times 10^5.
• A_{i,j} is a lowercase English letter.
• 1\leq Q\leq 2\times 10^5
• 1\leq a_i\leq H - 1
• 1\leq b_i\leq W - 1

Sample Input 1

4 5
abcde
fghij
klmno
pqrst
1
3 3

Sample Output 1

mlkon
hgfji
cbaed
rqpts

The grid will change as follows.

Sample Input 2

3 7
atcoder
regular
contest
2
1 1
2 5

Sample Output 2

testcon
oderatc
ularreg

The grid will change as follows.

Sample Input 3

2 2
ac
wa
3
1 1
1 1
1 1

Sample Output 3

ac
wa

The grid will change as follows.

Problem Statement

You are given a sequence of length N, A = (A_1, \ldots, A_N), consisting of 1 and -1.

Determine whether there is an integer sequence x = (x_1, \ldots, x_N) that satisfies all of the following conditions, and print one such sequence if it exists.

• |x_i| \leq 10^{12} for every i (1\leq i\leq N).
• x is strictly increasing. That is, x_1 < \cdots < x_N.
• \sum_{i=1}^N A_ix_i = 0.

Constraints

• 1\leq N\leq 2\times 10^5
• A_i \in \lbrace 1, -1\rbrace

Sample Input 1

5
-1 1 -1 -1 1

Sample Output 1

Yes
-3 -1 4 5 7

For this output, we have \sum_{i=1}^NA_ix_i= -(-3) + (-1) - 4 - 5 + 7 = 0.

Sample Input 2

1
-1

Sample Output 2

Yes
0

Sample Input 3

2
1 -1

Sample Output 3

No

Problem Statement

For a positive integer x, let f(x) denote the sum of its digits. For instance, we have f(153) = 1 + 5 + 3 = 9, f(2023) = 2 + 0 + 2 + 3 = 7, and f(1) = 1.

You are given a sequence of positive integers A = (A_1, \ldots, A_N). Find the minimum possible value of \sum_{i=1}^N f(A_i + x) where x is a non-negative integer.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq A_i < 10^9

Sample Input 1

4
4 13 8 6

Sample Output 1

14

For instance, x = 7 makes \sum_{i=1}^N f(A_i+x) = f(11) + f(20) + f(15) + f(13) = 14.

Sample Input 2

4
123 45 678 90

Sample Output 2

34

For instance, x = 22 makes \sum_{i=1}^N f(A_i+x) = f(145) + f(67) + f(700) + f(112) = 34.

Sample Input 3

3
1 10 100

Sample Output 3

3

For instance, x = 0 makes \sum_{i=1}^N f(A_i+x) = f(1) + f(10) + f(100) = 3.

Sample Input 4

1
153153153

Sample Output 4

1

For instance, x = 9999846846847 makes \sum_{i=1}^N f(A_i+x) = f(10000000000000) = 1.

Problem Statement

For a positive integer X none of whose digits is 0, consider obtaining a positive integer Y as follows.

• Initialize S as an empty string.
• Let N be the number of digits in X. For i = 1, \ldots, N in this order, do the following: insert the i-th character in the decimal notation of X at the beginning or end of S.
• Let Y be the positive integer represented by the string S.

Let f(X) denote the minimum positive integer that can be obtained from X in this way.

You are given a positive integer Y none of whose digits is 0. Print the number, modulo 998244353, of positive integers X none of whose digits is 0 such that f(X) = Y.

Constraints

• Y is a positive integer none of whose digits is 0.
• 1\leq Y < 10^{200000}

Sample Input 1

1332

Sample Output 1

3

Three integers, 1332, 3132, and 3312, satisfy the conditions.

Sample Input 2

3312

Sample Output 2

0

Sample Input 3

12234433442

Sample Output 3

153

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertices A_i and B_i.

Find the number of ways to paint each edge of G in color 1, 2, or 3 so that the following condition is satisfied, modulo 998244353.

• There is a simple path in G that contains an edge in color 1, an edge in color 2, and an edge in color 3.

Constraints

• 3 \leq N\leq 2\times 10^5
• 3 \leq M\leq 2\times 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is simple and connected.

Sample Input 1

3 3
1 2
1 3
3 2

Sample Output 1

0

Any simple path in G contains two or fewer edges, so there is no way to satisfy the condition.

Sample Input 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

534

Sample Input 3

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

Sample Output 3

144

Sample Input 4

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

Sample Output 4

1794