Problem Statement

You are given positive integers N and M. Find the maximum positive integer X that satisfies all of the following conditions.

• X is a positive integer less than 10^N, and all digits in the decimal representation of X are the same.
• X is a multiple of M.

If no positive integer X satisfies the conditions, print -1.

Constraints

• 1\leq N\leq 10^5
• 1\leq M\leq 10^9

Sample Input 1

7 12

Sample Output 1

888888

Four positive integers X satisfy the conditions: 444, 888, 444444, 888888. The answer is the maximum of them, which is 888888.

Sample Input 2

9 12

Sample Output 2

888888888

Six positive integers X satisfy the conditions: 444, 888, 444444, 888888, 444444444, 888888888.

Sample Input 3

1 3

Sample Output 3

9

Three positive integers X satisfy the conditions: 3, 6, 9.

Sample Input 4

1000 25

Sample Output 4

-1

No positive integers X satisfy the conditions.

Sample Input 5

30 1

Sample Output 5

999999999999999999999999999999

Problem Statement

For a sequence P = (P_1, \ldots, P_N), let \mathrm{LIS}(P) denote the length of a longest increasing subsequence.

You are given permutations A = (A_1, \ldots, A_N) and B = (B_1, \ldots, B_N) of integers from 1 through N. You may perform the following operation on these sequences any number of times (possibly zero).

• Choose an integer i such that 1\leq i\leq N-1. Swap A_i and A_{i+1}, and swap B_i and B_{i+1}.

Find the maximum possible final value of \mathrm{LIS}(A) + \mathrm{LIS}(B).

Constraints

• 2\leq N\leq 3\times 10^5
• 1\leq A_i\leq N
• 1\leq B_i\leq N
• A_i\neq A_j and B_i\neq B_j, if i\neq j.

Sample Input 1

5
5 2 1 4 3
3 1 2 5 4

Sample Output 1

8

Here is one way to achieve \mathrm{LIS}(A) + \mathrm{LIS}(B) = 8.

• Do the operation with i = 2. Now, A = (5,1,2,4,3), B = (3,2,1,5,4).
• Do the operation with i = 1. Now, A = (1,5,2,4,3), B = (2,3,1,5,4).
• Do the operation with i = 4. Now, A = (1,5,2,3,4), B = (2,3,1,4,5).

Here, A has a longest increasing subsequence (1,2,3,4), so \mathrm{LIS}(A)=4, and B has a longest increasing subsequence (2,3,4,5), so \mathrm{LIS}(B)=4.

Sample Input 2

5
1 2 3 4 5
1 2 3 4 5

Sample Output 2

10

You can decide not to perform the operation at all to achieve \mathrm{LIS}(A) + \mathrm{LIS}(B) = 10.

Problem Statement

You are given a positive integer N.

Fill each square of a grid with N rows and N columns by writing a positive integer not greater than N^2 so that all of the following conditions are satisfied.

• Two positive integers written in horizontally or vertically adjacent squares never sum to a prime number.
• Every positive integer not greater than N^2 is written in one of the squares.

Under the Constraints of this problem, it can be proved that such a way to fill the grid always exists.

Constraints

• 3\leq N\leq 1000

Sample Input 1

4

Sample Output 1

15 11 16 12
13 3 6 9
14 7 8 1
4 2 10 5

In this grid, every positive integer from 1 through 16 is written once. Additionally, among the sums of two positive integers written in horizontally or vertically adjacent squares are 15+11=26, 11+16=27, and 15+13=28, none of which is a prime number.

Problem Statement

There are N pieces placed at integer coordinates on a number line. The coordinate of the i-th piece is X_i.

Let us move these pieces M times as follows.

• In the i-th move, given a positive integer D_i, we move each piece as follows.
  • A piece whose coordinate is a negative integer is moved a distance of D_i in the positive direction.
  • A piece whose coordinate is 0 is not moved.
  • A piece whose coordinate is a positive integer is moved a distance of D_i in the negative direction.

Determine whether each piece arrives at the origin. If it does, print the number of moves after which it arrives there for the first time. Otherwise, print its coordinate after the M moves.

Constraints

• 1\leq N\leq 3\times 10^5
• 1\leq M\leq 3\times 10^5
• 1\leq X_1 < \cdots < X_N \leq 10^6
• 1\leq D_i \leq 10^6

Sample Input 1

6 4
2 4 6 8 10 12
8 2 5 7

Sample Output 1

No -6
No -4
Yes 2
Yes 1
Yes 2
No 4

The coordinate of each piece changes as follows.

• The 1-st piece: \phantom{0}2\quad \longmapsto \quad -6\quad \longmapsto \quad -4\quad \longmapsto \quad \phantom{-}1 \quad \longmapsto \quad -6.
• The 2-nd piece: \phantom{0}4 \quad \longmapsto \quad -4\quad \longmapsto \quad -2 \quad \longmapsto \quad \phantom{-}3 \quad \longmapsto \quad -4.
• The 3-rd piece: \phantom{0}6 \quad \longmapsto \quad -2\quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0.
• The 4-th piece: \phantom{0}8 \quad \longmapsto \quad \phantom{-}0\quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0.
• The 5-th piece: 10 \quad \longmapsto \quad \phantom{-}2\quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0 \quad \longmapsto \quad \phantom{-}0.
• The 6-th piece: 12 \quad \longmapsto \quad \phantom{-}4\quad \longmapsto \quad \phantom{-}2 \quad \longmapsto \quad -3 \quad \longmapsto \quad \phantom{-}4.

Problem Statement

You are given positive integers N, M, and K. Consider the following operation on a sequence of positive integers A = (A_0, \ldots, A_{N-1}).

• Do the following for k=0, 1, \ldots, K-1 in this order.
  • Sort A_{k\bmod N}, A_{(k+1)\bmod N}, \ldots, A_{(k+M-1)\bmod N} in ascending order. That is, replace A_{(k+j)\bmod N} with x_j for each 0\leq j < M, where (x_0, \ldots, x_{M-1}) is the result of sorting A_{k\bmod N}, A_{(k+1)\bmod N}, \ldots, A_{(k+M-1)\bmod N} in ascending order.

You are given a permutation B = (B_0, \ldots, B_{N-1}) of the integers from 1 through N. Find the number of sequences A of positive integers that will equal B after performing the operation above, modulo 998244353.

Constraints

• 2\leq N\leq 3\times 10^5
• 2\leq M\leq N
• 1\leq K\leq 10^9
• 1\leq B_i\leq N
• B_i\neq B_j if i\neq j.

Sample Input 1

6 3 5
6 4 2 3 1 5

Sample Output 1

18

For instance, A = (4,1,5,6,2,3) satisfies the condition. On this A, the operation will proceed as follows.

• The action for k=0 changes A to (1,4,5,6,2,3).
• The action for k=1 changes A to (1,4,5,6,2,3).
• The action for k=2 changes A to (1,4,2,5,6,3).
• The action for k=3 changes A to (1,4,2,3,5,6).
• The action for k=4 changes A to (6,4,2,3,1,5), which equals B.

Sample Input 2

6 3 5
6 5 4 3 2 1

Sample Output 2

0

No sequence A satisfies the condition.

Sample Input 3

20 20 149
13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12

Sample Output 3

401576539

All permutations of the integers from 1 through 20 satisfy the condition.

Problem Statement

Let r > 1 be a rational number, and p and q be the numerator and denominator of r, respectively. That is, p and q are positive integers such that r = \frac{p}{q} and \gcd(p,q) = 1.

Let the base-\boldsymbol{r} expansion of a positive integer n be the integer sequence (a_1, \ldots, a_k) that satisfies all of the following conditions.

• a_i is an integer between 0 and p-1.
• a_1\neq 0.
• n = \sum_{i=1}^k a_ir^{k-i}.

It can be proved that any positive integer n has a unique base-r expansion.

You are given positive integers p, q, N, L, and R. Here, p and q satisfy 1.01 \leq \frac{p}{q}.

Consider sorting all positive integers not greater than N in ascending lexicographical order of their base-\frac{p}{q} expansions. Find the L-th, (L+1)-th, \ldots, R-th positive integers in this list.

As usual, decimal notations are used in the input and output of positive integers.

Constraints

• 1\leq p, q \leq 10^9
• \gcd(p,q) = 1
• 1.01 \leq \frac{p}{q}
• 1\leq N\leq 10^{18}
• 1\leq L\leq R\leq N
• R - L + 1\leq 3\times 10^5

Sample Input 1

3 1 9 1 9

Sample Output 1

1
3
9
4
5
2
6
7
8

The base-3 expansions of the positive integers not greater than 9 are as follows.

1: (1),        2: (2),        3: (1, 0),
4: (1, 1),     5: (1, 2),     6: (2, 0),
7: (2, 1),     8: (2, 2),     9: (1, 0, 0).

Sample Input 2

3 2 9 1 9

Sample Output 2

1
2
3
4
6
9
7
8
5

The base-\frac32 expansions of the positive integers not greater than 9 are as follows.

1: (1),        2: (2),        3: (2, 0),     
4: (2, 1),     5: (2, 2),     6: (2, 1, 0),  
7: (2, 1, 1),  8: (2, 1, 2),  9: (2, 1, 0, 0).

One can see that the base-\frac32 expansion of 6 is (2,1,0), for instance, from 2\cdot \bigl(\frac32\bigr)^2 + 1\cdot \frac32 + 0\cdot 1 = 6.

Sample Input 3

3 2 9 3 8

Sample Output 3

3
4
6
9
7
8

This is the 3-rd through 8-th lines of the output to Sample Input 2.

Sample Input 4

10 9 1000000000000000000 123456789123456789 123456789123456799

Sample Output 4

806324968563249278
806324968563249279
725692471706924344
725692471706924345
725692471706924346
725692471706924347
725692471706924348
725692471706924349
653123224536231907
653123224536231908
653123224536231909