Problem Statement

Print all non-negative integers less than or equal to N in descending order.

Constraints

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

Sample Input 1

3

Sample Output 1

3
2
1
0

We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.

Sample Input 2

22

Sample Output 2

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

Problem Statement

You are given a string S consisting of uppercase English letters and digits. Determine whether S satisfies the following condition.

• S is a concatenation of the following characters and string in the order listed.
  • An uppercase English letter
  • A string of length 6 that is a decimal representation of an integer between 100000 and 999999, inclusive
  • An uppercase English letter

Constraints

• S consists of uppercase English letters and digits.
• The length of S is between 1 and 10, inclusive.

Sample Input 1

Q142857Z

Sample Output 1

Yes

S is a concatenation of Q, 142857, and Z in this order.
Q and Z are uppercase English letters, and 142857 is a string of length 6 that is a decimal representation of an integer between 100000 and 999999, so S satisfies the condition.

Sample Input 2

AB912278C

Sample Output 2

No

AB is not an uppercase English letter, so S does not satisfy the condition.

Sample Input 3

X900000

Sample Output 3

No

The last character of S is not an uppercase English letter, so S does not satisfy the condition.

Sample Input 4

K012345K

Sample Output 4

No

012345 is not a string of length 6 that is a decimal representation of an integer between 100000 and 999999, so S does not satisfy the condition.

Problem Statement

We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.

When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.

At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq T \leq 10^{18}
• 1 \leq A_i \leq 10^9
• The playlist does not change songs at exactly T seconds after it starts playing.
• All values in the input are integers.

Sample Input 1

3 600
180 240 120

Sample Output 1

1 60

When the playlist is played, the following happens. (Assume that it starts playing at time 0.)

• From time 0 to time 180, song 1 plays.
• From time 180 to time 420, song 2 plays.
• From time 420 to time 540, song 3 plays.
• From time 540 to time 720, song 1 plays.
• From time 720 to time 960, song 2 plays.
• \qquad\vdots

At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.

Sample Input 2

3 281
94 94 94

Sample Output 2

3 93

Sample Input 3

10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

6 678912340

Problem Statement

You are given a sequence of non-negative integers A=(a_1,a_2,\ldots,a_N).

Let S be the set of non-negative integers that can be the sum of K terms in A (with distinct indices).

Find the greatest multiple of D in S. If there is no multiple of D in S, print -1 instead.

Constraints

• 1 \leq K \leq N \leq 100
• 1 \leq D \leq 100
• 0 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4 2 2
1 2 3 4

Sample Output 1

6

Here are all the ways to choose two terms in A.

• Choose a_1 and a_2, whose sum is 1+2=3.
• Choose a_1 and a_3, whose sum is 1+3=4.
• Choose a_1 and a_4, whose sum is 1+4=5.
• Choose a_2 and a_3, whose sum is 2+3=5.
• Choose a_2 and a_4, whose sum is 2+4=6.
• Choose a_3 and a_4, whose sum is 3+4=7.

Thus, we have S=\{3,4,5,6,7\}. The greatest multiple of 2 in S is 6, so you should print 6.

Sample Input 2

3 1 2
1 3 5

Sample Output 2

-1

In this example, we have S=\{1,3,5\}. Nothing in S is a multiple of 2, so you should print -1.

Problem Statement

You are given an integer sequence A = (A_1, \dots, A_N) of length N, and integers M and K.
For each i = 1, \dots, N - M + 1, solve the following independent problem.

Find the sum of the first K values in the sorted list of the M integers A_i, A_{i + 1}, \dots, A_{i + M - 1} in ascending order.

Constraints

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

Sample Input 1

6 4 3
3 1 4 1 5 9

Sample Output 1

5 6 10

• For i = 1, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 1, 3, 4, where the sum of the first three values is 5.
• For i = 2, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 1, 4, 5, where the sum of the first three values is 6.
• For i = 3, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 4, 5, 9, where the sum of the first three values is 10.

Sample Input 2

10 6 3
12 2 17 11 19 8 4 3 6 20

Sample Output 2

21 14 15 13 13

Problem Statement

You are given a sequence of non-negative integers A=(a_1,\ldots,a_N).

Let us perform the following operation on A just once.

• Choose a non-negative integer x. Then, for every i=1, \ldots, N, replace the value of a_i with the bitwise XOR of a_i and x.

Let M be the maximum value in A after the operation. Find the minimum possible value of M.

Constraints

• 1 \leq N \leq 1.5 \times 10^5
• 0 \leq a_i \lt 2^{30}
• All values in the input are integers.

Sample Input 1

3
12 18 11

Sample Output 1

16

If we do the operation with x=2, the sequence becomes (12 \oplus 2,18 \oplus 2, 11 \oplus 2) = (14,16,9), where the maximum value M is 16.
We cannot make M smaller than 16, so this value is the answer.

Sample Input 2

10
0 0 0 0 0 0 0 0 0 0

Sample Output 2

0

Sample Input 3

5
324097321 555675086 304655177 991244276 9980291

Sample Output 3

805306368

Problem Statement

You are given positive integers N and M.
Find the number, modulo M, of simple connected undirected graphs with N vertices numbered 1, \dots, N that satisfy the following condition.

• For every u = 2, \dots, N-1, the shortest distance from vertex 1 to vertex u is strictly smaller than the shortest distance from vertex 1 to vertex N.

Here, the shortest distance from vertex u to vertex v is the minimum number of edges in a simple path connecting vertices u and v.
Two graphs are considered different if and only if there are two vertices u and v that are connected by an edge in exactly one of those graphs.

Constraints

• 3 \leq N \leq 500
• 10^8 \leq M \leq 10^9
• N and M are integers.

Sample Input 1

4 1000000000

Sample Output 1

8

The following eight graphs satisfy the condition.

Sample Input 2

3 100000000

Sample Output 2

1

Sample Input 3

500 987654321

Sample Output 3

610860515

Be sure to find the number modulo M.

Problem Statement

Takahashi has A kinds of level-1 gems, and 10^{10^{100}} gems of each of those kinds.
For an integer n greater than or equal to 2, he can put n gems that satisfy all of the following conditions into a cauldron to generate a level-n gem in return.

• No two gems are of the same kind.
• Every gem's level is less than n.
• For every integer x greater than or equal to 2, there is at most one level-x gem.

Find the number of kinds of level-N gems that Takahashi can obtain, modulo 998244353.

Here, two level-2 or higher gems are considered to be of the same kind if and only if they are generated from the same set of gems.

• Two sets of gems are distinguished if and only if there is a gem in one of those sets such that the other set does not contain a gem of the same kind.

Any level-1 gem and any level-2 or higher gem are of different kinds.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A \leq 10^9
• N and A are integers.

Sample Input 1

3 3

Sample Output 1

10

Here are ten ways to obtain a level-3 gem.

• Put three kinds of level-1 gems into the cauldron.
  • Takahashi has three kinds of level-1 gems, so there is one way to choose three kinds of level-1 gems. Thus, he can obtain one kind of level-3 gem in this way.
• Put one kind of level-2 gem and two kinds of level-1 gems into the cauldron.
  • A level-2 gem can be obtained by putting two kinds of level-1 gems into the cauldron.
    • Takahashi has three kinds of level-1 gems, so there are three ways to choose two kinds of level-1 gems. Thus, three kinds of level-2 gems are available here.
  • There are three kinds of level-2 gems, and three ways to choose two kinds of level-1 gems, so he can obtain 3 \times 3 = 9 kinds of level-3 gems in this way.

Sample Input 2

1 100

Sample Output 2

100

Sample Input 3

200000 1000000000

Sample Output 3

797585162