Problem Statement

For a positive integer X, the Dragon String of level X is a string of length (X+3) formed by one L, X occurrences of o, one n, and one g arranged in this order.

You are given a positive integer N. Print the Dragon String of level N.
Note that uppercase and lowercase letters are distinguished.

Constraints

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

Sample Input 1

3

Sample Output 1

Looong

Arranging one L, three os, one n, and one g in this order yields Looong.

Sample Input 2

1

Sample Output 2

Long

Problem Statement

For a positive integer X, let \text{ctz}(X) be the (maximal) number of consecutive zeros at the end of the binary notation of X.
If the binary notation of X ends with a 1, then \text{ctz}(X)=0.

You are given a positive integer N. Print \text{ctz}(N).

Constraints

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

Sample Input 1

2024

Sample Output 1

3

2024 is 11111101000 in binary, with three consecutive 0s from the end, so \text{ctz}(2024)=3.
Thus, print 3.

Sample Input 2

18

Sample Output 2

1

18 is 10010 in binary, so \text{ctz}(18)=1.
Note that we count the trailing zeros.

Sample Input 3

5

Sample Output 3

0

Problem Statement

A non-negative integer n is called a good integer when it satisfies the following condition:

• All digits in the decimal notation of n are even numbers (0, 2, 4, 6, and 8).

For example, 0, 68, and 2024 are good integers.

You are given an integer N. Find the N-th smallest good integer.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

8

Sample Output 1

24

The good integers in ascending order are 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots.
The eighth smallest is 24, which should be printed.

Sample Input 2

133

Sample Output 2

2024

Sample Input 3

31415926535

Sample Output 3

2006628868244228

Problem Statement

For a positive integer k, the Pyramid Sequence of size k is a sequence of length (2k-1) where the terms of the sequence have the values 1,2,\ldots,k-1,k,k-1,\ldots,2,1 in this order.

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N.
Find the maximum size of a Pyramid Sequence that can be obtained by repeatedly choosing and performing one of the following operations on A (possibly zero times).

• Choose one term of the sequence and decrease its value by 1.
• Remove the first or last term.

It can be proved that the constraints of the problem guarantee that at least one Pyramid Sequence can be obtained by repeating the operations.

Constraints

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

Sample Input 1

5
2 2 3 1 1

Sample Output 1

2

Starting with A=(2,2,3,1,1), you can create a Pyramid Sequence of size 2 as follows:

• Choose the third term and decrease it by 1. The sequence becomes A=(2,2,2,1,1).
• Remove the first term. The sequence becomes A=(2,2,1,1).
• Remove the last term. The sequence becomes A=(2,2,1).
• Choose the first term and decrease it by 1. The sequence becomes A=(1,2,1).

(1,2,1) is a Pyramid Sequence of size 2.
On the other hand, there is no way to perform the operations to create a Pyramid Sequence of size 3 or larger, so you should print 2.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

3

Sample Input 3

1
1000000000

Sample Output 3

1

Problem Statement

The digit sum of a positive integer n is defined as the sum of the digits in the decimal notation of n. For example, the digit sum of 2024 is 2+0+2+4=8.
A positive integer n is called a good integer when n is divisible by its digit sum. For example, 2024 is a good integer because it is divisible by its digit sum of 8.
You are given a positive integer N. How many good integers are less than or equal to N?

Constraints

• 1 \leq N \leq 10^{14}
• N is an integer.

Sample Input 1

20

Sample Output 1

13

There are 13 good integers less than or equal to 20: 1,2,3,4,5,6,7,8,9,10,12,18,20.

Sample Input 2

2024

Sample Output 2

409

Sample Input 3

9876543210

Sample Output 3

547452239

Problem Statement

There is a grid with H rows and W columns. Initially, each integer from 1 to (H \times W) is written exactly once in the grid.
Specifically, for 1 \leq i \leq H and 1 \leq j \leq W, the cell at the i-th row from the top and the j-th column from the left contains S_{i,j}.
Below, let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Determine if it is possible to reach a state where, for all pairs of integers (i,j) (1 \leq i \leq H, 1 \leq j \leq W),
the cell (i,j) contains the integer ((i-1) \times W + j) by repeating the following operation at most 20 times (possibly zero).
If it is possible, print the minimum number of operations required.
If it is impossible in 20 or fewer operations (including the case where it is impossible no matter how many times the operation is repeated), print -1.

Operation: Choose a rectangle of size (H-1) \times (W-1) from the grid and rotate it 180 degrees.
More precisely, choose integers x and y (0 \leq x, y \leq 1),
and for all pairs of integers (i,j) satisfying 1 \leq i \leq H-1 and 1 \leq j \leq W-1,
simultaneously replace the integer written in cell (i+x,j+y) with the number written in cell (H-i+x,W-j+y).

Note that it is only necessary for the integers written in the cells to satisfy the condition; the orientation in which they are written does not matter.

Constraints

• 3 \leq H,W \leq 8
• 1 \leq S_{i,j} \leq H \times W
• If (i,j) \neq (i',j'), then S_{i,j} \neq S_{i',j'}
• All input values are integers.

Sample Input 1

3 3
9 4 3
2 1 8
7 6 5

Sample Output 1

2

Operating in the following order will satisfy the conditions of the problem statement in 2 operations.

• Operate by choosing the rectangle in the top-left corner. That is, by choosing x=0 and y=0.
• Operate by choosing the rectangle in the bottom-right corner. That is, by choosing x=1 and y=1.

On the other hand, it is impossible to satisfy the conditions with one or fewer operations, so print 2.

Sample Input 2

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

Sample Output 2

-1

It is impossible to satisfy the conditions with 20 or fewer operations, so print -1.

Sample Input 3

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

Sample Output 3

20

Sample Input 4

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

Sample Output 4

0

Problem Statement

You are given 16 non-negative integers X_{i, j, k, l} (i, j, k, l \in \lbrace 0, 1 \rbrace) in ascending order of (i, j, k, l).
Let N = \displaystyle \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 \sum_{l=0}^1 X_{i,j,k,l}.
Find the number, modulo 998244353, of sequences (A_1, A_2, ..., A_{N+3}) of length N + 3 consisting of 0s and 1s that satisfy the following condition.

• For every quadruple of integers (i, j, k, l) (i, j, k, l \in \lbrace 0, 1 \rbrace), there are exactly X_{i,j,k,l} integers s between 1 and N, inclusive, that satisfy:
  • A_s = i, A_{s + 1} = j, A_{s + 2} = k, and A_{s + 3} = l.

Constraints

• X_{i, j, k, l} are all non-negative integers.
• 1 \leq \displaystyle \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 \sum_{l=0}^1 X_{i,j,k,l} \leq 10^6

Sample Input 1

0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0

Sample Output 1

1

This input corresponds to the case where X_{1, 0, 1, 0} and X_{1, 1, 0, 1} are 1 and all others are 0.
In this case, only one sequence satisfies the condition, which is (1, 1, 0, 1, 0).

Sample Input 2

1 1 2 0 1 2 1 1 1 1 1 2 1 0 1 0

Sample Output 2

16

Sample Input 3

21 3 3 0 3 0 0 0 4 0 0 0 0 0 0 0

Sample Output 3

2024

Sample Input 4

62 67 59 58 58 69 57 66 67 50 68 65 59 64 67 61

Sample Output 4

741536606