Problem Statement

You are given integers L,R (L < R).

Snuke is looking for a pair of integers (x,y) that satisfy both of the conditions below.

• L \leq x < y \leq R
• \gcd(x,y)=1

Find the maximum possible value of (y-x) in a pair that satisfies the conditions. It can be proved that at least one such pair exists under the Constraints.

Constraints

• 1 \leq L < R \leq 10^{18}
• All values in input are integers.

Sample Input 1

2 4

Sample Output 1

1

For (x,y)=(2,4), we have \gcd(x,y)=2, which violates the condition. For (x,y)=(2,3), the conditions are satisfied. Here, the value of (y-x) is 1. There is no such pair with a greater value of (y-x), so the answer is 1.

Sample Input 2

14 21

Sample Output 2

5

Sample Input 3

1 100

Sample Output 3

99

Problem Statement

You are given an integer sequence of length N consisting of 0 and 1: A=(A_1,A_2,\cdots,A_N).

You will do the operation below exactly once.

• Choose a contiguous subsequence of A and flip the elements in it: convert 0 to 1 and vice versa. Here, you may choose an empty subsequence, in which case the elements of A do not change.

Your score will be the number of 1's in A. How many values are there that your score can take?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq A_i \leq 1
• All values in input are integers.

Sample Input 1

4
0 1 1 0

Sample Output 1

4

There are four possible values for your score: 0, 1, 2, 3. For example, if you flip the 2-nd through 4-th elements of A, you will get A=(0,0,0,1), for a score of 1.

Sample Input 2

5
0 0 0 0 0

Sample Output 2

6

Sample Input 3

6
0 1 0 1 0 1

Sample Output 3

3

Problem Statement

You are given a non-negative integer sequence of length N: A=(A_1,A_2,\cdots,A_N). Here, all elements of A are pairwise distinct.

Alice and Bob will play a game. They will alternately play a turn, with Alice going first. In each turn, the player does the operation below.

• Choose the largest element in A at the moment, and replace it with a smaller non-negative integer. Here, all elements in A must still be pairwise distinct after this operation.

The first player to be unable to do the operation loses. Determine the winner when both players play optimally.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 0 \leq A_1 < A_2 < \cdots < A_N \leq 10^9
• All values in input are integers.

Sample Input 1

2
2 4

Sample Output 1

Alice

In Alice's first turn, she may replace 4 with 0, 1, or 3. If she replaces 4 with 0 or 1, Bob's move in the next turn will make Alice unable to do the operation and lose. On the other hand, if she replaces 4 with 3, she can win regardless of Bob's subsequent moves. Thus, Alice wins in this input.

Sample Input 2

3
0 1 2

Sample Output 2

Bob

Problem Statement

You are given an integer sequence of length N: A=(A_1,A_2,\cdots,A_N), and an integer M.

For each k=1,2,\cdots,M, find the value of A_N after doing the operation below k times.

• For every i (1 \leq i \leq N), simultaneously, replace the value of A_i with A_1 \oplus A_2 \oplus \cdots \oplus A_i.

Here, \oplus denotes bitwise \mathrm{XOR}.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 10^6
• 0 \leq A_i < 2^{30}
• All values in input are integers.

Sample Input 1

3 2
2 1 3

Sample Output 1

0 1

Each operation changes A as follows.

• Initially: A=(2,1,3).
• After the first operation: A=(2,3,0).
• After the second operation: A=(2,1,1).

Sample Input 2

10 12
721939838 337089195 171851101 1069204754 348295925 77134863 839878205 89360649 838712948 918594427

Sample Output 2

716176219 480674244 678890528 642764255 259091950 663009497 942498522 584528336 364872846 145822575 392655861 844652404

Problem Statement

Snuke runs a bakery. He is planning for the next N days. Let us call these days Day 1,2,\cdots,N.

At the moment, the bakery hires nobody. There are M bakers that Snuke can hire, numbered 1 to M.

C_i yen must be paid to hire Baker i. If Baker i is hired, they will work on Day L_i, L_i+1, \cdots, R_i, baking one loaf of bread each day.

For each j (1 \leq j \leq N), there is a limit A_j to the number of loaves of bread that can be sold on Day j. If x_j loaves of bread are baked on Day j, \min(x_j, A_j) loaves will be sold on that day.

Each loaf of bread sold will yield a profit of D yen.

Snuke wants to choose the set of bakers to hire to maximize the final profit: (The total number of loaves sold) \times D - (The total cost of hiring bakers). Find the maximum possible value of this.

Constraints

• 1 \leq N \leq 2000
• 1 \leq M \leq 2000
• 1 \leq D \leq 10^9
• 1 \leq A_j \leq M
• 1 \leq L_i \leq R_i \leq N
• 1 \leq C_i \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

11

Snuke should hire Baker 1, 3, 4. In this case, the total cost to hire bakers is 7, and the number of loaves baked on Day 1, 2, \cdots, N will be 1,1,0,1,1,2,1, respectively. A total of 6 loaves will be sold, for a final profit of 6 \times 3-7=11.

Sample Input 2

3 1 5
1 1 1
2 2 10

Sample Output 2

0

It is optimal to hire no baker.

Sample Input 3

10 10 42
6 5 1 5 2 4 2 7 10 9
3 4 4
3 7 136
9 9 14
2 7 152
3 3 33
2 4 100
3 3 38
1 10 28
3 5 66
8 8 15

Sample Output 3

543

Problem Statement

We have a bar of length 1. A point on the bar whose distance from the left end of the bar is x is said to have a coordinate x.

Snuke will do the operation below N times.

• Choose two real numbers x and y uniformly at random from [0, 1]. Put a sticker covering the range from the coordinate \min(x,y) to the coordinate \max(x,y).

Here, all random choices are independent of each other.

Stickers can overlap. The bar is said to be good when no point is covered by K+1 or more stickers.

Find the probability, modulo 998244353, of having a good bar after putting N stickers.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq \min(N,10^5)
• All values in input are integers.

Sample Input 1

2 1

Sample Output 1

332748118

We are to find the probability that the two stickers do not overlap, which is 1/3.

Sample Input 2

5 3

Sample Output 2

66549624

Sample Input 3

10000 5000

Sample Output 3

642557092