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

The programming contest World Tour Finals is underway, where N players are participating, and half of the competition time has passed. There are M problems in this contest, and the score A_i of problem i is a multiple of 100 between 500 and 2500, inclusive.

For each i = 1, \ldots, N, you are given a string S_i that indicates which problems player i has already solved. S_i is a string of length M consisting of o and x, where the j-th character of S_i is o if player i has already solved problem j, and x if they have not yet solved it. Here, none of the players have solved all the problems yet.

The total score of player i is calculated as the sum of the scores of the problems they have solved, plus a bonus score of i points.
For each i = 1, \ldots, N, answer the following question.

• At least how many of the problems that player i has not yet solved must player i solve to exceed all other players' current total scores?

Note that under the conditions in this statement and the constraints, it can be proved that player i can exceed all other players' current total scores by solving all the problems, so the answer is always defined.

Constraints

• 2\leq N\leq 100
• 1\leq M\leq 100
• 500\leq A_i\leq 2500
• A_i is a multiple of 100.
• S_i is a string of length M consisting of o and x.
• S_i contains at least one x.
• All numeric values in the input are integers.

Sample Input 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

Sample Output 1

0
1
1

The players' total scores at the halfway point of the competition time are 2001 points for player 1, 1502 points for player 2, and 1703 points for player 3.

Player 1 is already ahead of all other players' total scores without solving any more problems.

Player 2 can, for example, solve problem 4 to have a total score of 3502 points, which would exceed all other players' total scores.

Player 3 can also, for example, solve problem 4 to have a total score of 3703 points, which would exceed all other players' total scores.

Sample Input 2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

Sample Output 2

1
1
1
1
0

Sample Input 3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

Sample Output 3

7
6
5
4
3
2
0

Problem Statement

Given is a sequence of length N: A=(A_1,A_2,\ldots,A_N), and an integer K.

How many of the contiguous subsequences of A have the sum of K?
In other words, how many pairs of integers (l,r) satisfy all of the conditions below?

• 1\leq l\leq r\leq N
• \displaystyle\sum_{i=l}^{r}A_i = K

Constraints

• 1\leq N \leq 2\times 10^5
• |A_i| \leq 10^9
• |K| \leq 10^{15}
• All values in input are integers.

Sample Input 1

6 5
8 -3 5 7 0 -4

Sample Output 1

3

(l,r)=(1,2),(3,3),(2,6) are the three pairs that satisfy the conditions.

Sample Input 2

2 -1000000000000000
1000000000 -1000000000

Sample Output 2

0

There may be no pair that satisfies the conditions.

Problem Statement

Integer Sequence Exhibition is taking place, where integer sequences are gathered in one place and evaluated. Here, every integer sequence of length N consisting of integers between 1 and K (inclusive) is evaluated and given an integer score between 1 and M (inclusive).

Print the number, modulo 998244353, of ways to give each of the evaluated sequences a score between 1 and M.

Here, two ways are said to be different when there is an evaluated sequence A = (A_1, A_2, \ldots, A_N) that is given different scores by the two ways.

Constraints

• 1 \leq N, K, M \leq 10^{18}
• N, K, and M are integers.

Sample Input 1

2 2 2

Sample Output 1

16

Four sequences are evaluated: (1, 1), (1, 2), (2, 1), and (2, 2). There are 16 ways to give each of these sequences a score between 1 and 2, as follows.

• Give 1 to (1, 1), 1 to (1, 2), 1 to (2, 1), and 1 to (2, 2)
• Give 1 to (1, 1), 1 to (1, 2), 1 to (2, 1), and 2 to (2, 2)
• Give 1 to (1, 1), 1 to (1, 2), 2 to (2, 1), and 1 to (2, 2)
• Give 1 to (1, 1), 1 to (1, 2), 2 to (2, 1), and 2 to (2, 2)
• \cdots
• Give 2 to (1, 1), 2 to (1, 2), 2 to (2, 1), and 2 to (2, 2)

Thus, we print 16.

Sample Input 2

3 14 15926535

Sample Output 2

109718301

Be sure to print the count modulo 998244353.

Problem Statement

You are given a permutation P=(P _ 1,P _ 2,\ldots,P _ N) of (1,2,\ldots,N).

Find the following value for all i\ (1\leq i\leq N):

• D _ i=\displaystyle\min_{j\neq i}\left\lparen\left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert\right\rparen.

Constraints

• 2 \leq N \leq 2\times10^5
• 1 \leq P _ i \leq N\ (1\leq i\leq N)
• i\neq j\implies P _ i\neq P _ j
• All values in the input are integers.

Sample Input 1

4
3 2 4 1

Sample Output 1

2 2 3 3 

For example, for i=1,

• if j=2, we have \left\lvert P _ i-P _ j\right\rvert=1 and \left\lvert i-j\right\rvert=1;
• if j=3, we have \left\lvert P _ i-P _ j\right\rvert=1 and \left\lvert i-j\right\rvert=2;
• if j=4, we have \left\lvert P _ i-P _ j\right\rvert=2 and \left\lvert i-j\right\rvert=3.

Thus, the value is minimum when j=2, where \left\lvert P _ i-P _ j\right\rvert+\left\lvert i-j\right\rvert=2, so D _ 1=2.

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

2 2 2 2 2 2 2 

Sample Input 3

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

Sample Output 3

3 3 3 5 3 4 3 3 4 2 2 4 4 4 4 7