Problem Statement

A sport event is held in June of every year whose remainder when divided by 4 is 2.
Suppose that it is now January of the year Y. In what year will this sport event be held next time?

Constraints

• 2000 \leq Y \leq 3000
• Y is an integer.

Sample Input 1

2022

Sample Output 1

2022

The remainder when 2022 is divided by 4 is 2, so if it is now January of 2022, the next games will be held in June of the same year.

Sample Input 2

2023

Sample Output 2

2026

Sample Input 3

3000

Sample Output 3

3002

Problem Statement

You are given an integer K.

Print a string that is a concatenation of the first K uppercase English letters in ascending order, starting from A.

Constraints

• K is an integer between 1 and 26, inclusive.

Sample Input 1

3

Sample Output 1

ABC

The uppercase English letters in ascending order are A, B, C, ...

By concatenating the first three uppercase English letters, we get ABC.

Sample Input 2

1

Sample Output 2

A

Problem Statement

In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?

Constraints

• 1 \leq N \leq 1000
• 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

6
1 4 1 2 2 1

Sample Output 1

3

There are three different integers: 1, 2, 4.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

11
3 1 4 1 5 9 2 6 5 3 5

Sample Output 3

7

Problem Statement

AtCoder Kingdom uses a calendar whose year has N months. Month i (1\leq i\leq N) has D _ i days, from day 1 of month i to day D _ i of month i.

How many days in a year of AtCoder have "repdigits" dates?

Here, day j of month i (1\leq i\leq N,1\leq j\leq D _ i) is said to have a repdigit date if and only if all digits in the decimal notations of i and j are the same.

Constraints

• 1\leq N\leq100
• 1\leq D _ i\leq100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

12
31 29 31 30 31 30 31 31 30 31 30 31

Sample Output 1

13

In AtCoder Kingdom, the days that have repdigit dates are January 1, January 11, February 2, February 22, March 3, April 4, May 5, June 6, July 7, August 8, September 9, November 1, and November 11, for a total of 13 days.

Sample Input 2

10
10 1 2 3 4 5 6 7 8 100

Sample Output 2

1

In AtCoder Kingdom, only January 1 has a repdigit date.

Sample Input 3

30
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

Sample Output 3

15

Problem Statement

There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

• Each of S_1,\ldots,S_9 is a string of length 9 consisting of # and ..

Sample Input 1

##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........

Sample Output 1

2

The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.

The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.

Thus, the answer is 2.

Sample Input 2

.#.......
#.#......
.#.......
.........
....#.#.#
.........
....#.#.#
........#
.........

Sample Output 2

3

Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

There is a deck consisting of N face-down cards with an integer from 1 through N written on them. The integer on the i-th card from the top is P_i.

Using this deck, you will perform N moves, each consisting of the following steps:

• Draw the topmost card from the deck. Let X be the integer written on it.
• Stack the drawn card, face up, onto the card with the smallest integer among the face-up topmost cards on the table with an integer greater than or equal to X written on them. If there is no such card on the table, put the drawn card on the table, face up, without stacking it onto any card.
• Then, if there is a pile consisting of K face-up cards on the table, eat all those cards. The eaten cards all disappear from the table.

For each card, find which of the N moves eats it. If the card is not eaten until the end, report that fact.

Constraints

• All values in input are integers.
• 1 \le K \le N \le 2 \times 10^5
• P is a permutation of (1,2,\dots,N) (i.e. a sequence obtained by rearranging (1,2,\dots,N)).

Sample Input 1

5 2
3 5 2 1 4

Sample Output 1

4
3
3
-1
4

In this input, P=(3,5,2,1,4) and K=2.

• In the 1-st move, the card with 3 written on it is put on the table, face up, without stacked onto any card.
• In the 2-nd move, the card with 5 written on it is put on the table, face up, without stacked onto any card.
• In the 3-rd move, the card with 2 written on it is stacked, face up, onto the card with 3 written on it.
  • Now there is a pile consisting of K=2 face-up cards, on which 2 and 3 from the top are written, so these cards are eaten.
• In the 4-th move, the card with 1 written on it is stacked, face up, onto the card with 5 written on it.
  • Now there is a pile consisting of K=2 face-up cards, on which 1 and 5 from the top are written, so these cards are eaten.
• In the 5-th move, the card with 4 written on it is put on the table, face up, without stacked onto any card.
• The card with 4 written on it was not eaten until the end.

Sample Input 2

5 1
1 2 3 4 5

Sample Output 2

1
2
3
4
5

If K=1, every card is eaten immediately after put on the table within a single move.

Sample Input 3

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

Sample Output 3

9
9
9
15
15
6
-1
-1
6
-1
-1
-1
-1
6
15

Problem Statement

There are N boxes numbered 0 to N-1. Initially, box i contains A_i balls.

Takahashi will perform the following operations for i=1,2,\ldots,M in order:

• Set a variable C to 0.
• Take out all the balls from box B_i and hold them in hand.
• While holding at least one ball in hand, repeat the following process:
  • Increase the value of C by 1.
  • Put one ball from hand into box (B_i+C) \bmod N.

Determine the number of balls in each box after completing all operations.

Constraints

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

Sample Input 1

5 3
1 2 3 4 5
2 4 0

Sample Output 1

0 4 2 7 2

The operations proceed as follows:

Sample Input 2

3 10
1000000000 1000000000 1000000000
0 1 0 1 0 1 0 1 0 1

Sample Output 2

104320141 45436840 2850243019

Sample Input 3

1 4
1
0 0 0 0

Sample Output 3

1

Problem Statement

We have a grid with N rows and M columns. The square (i,j) at the i-th row from the top and j-th column from the left has an integer (i-1) \times M + j written on it.
Let us perform the following operation on this grid.

• For every square (i,j) such that i+j is odd, replace the integer on that square with 0.

Answer Q questions on the grid after the operation.
The i-th question is as follows:

• Find the sum of the integers written on all squares (p,q) that satisfy all of the following conditions, modulo 998244353.
  • A_i \le p \le B_i.
  • C_i \le q \le D_i.

Constraints

• All values in the input are integers.
• 1 \le N,M \le 10^9
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i \le B_i \le N
• 1 \le C_i \le D_i \le M

Sample Input 1

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

Sample Output 1

28
27
36
14
0
104

The grid in this input is shown below.

This input contains six questions.

• The answer to the first question is 0+3+0+6+0+8+0+11+0=28.
• The answer to the second question is 1+0+9+0+17=27.
• The answer to the third question is 17+0+19+0=36.
• The answer to the fourth question is 14.
• The answer to the fifth question is 0.
• The answer to the sixth question is 104.

Sample Input 2

1000000000 1000000000
3
1000000000 1000000000 1000000000 1000000000
165997482 306594988 719483261 992306147
1 1000000000 1 1000000000

Sample Output 2

716070898
240994972
536839100

For the first question, note that although the integer written on the square (10^9,10^9) is 10^{18}, you are to find it modulo 998244353.

Sample Input 3

999999999 999999999
3
999999999 999999999 999999999 999999999
216499784 840031647 84657913 415448790
1 999999999 1 999999999

Sample Output 3

712559605
648737448
540261130