Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell A: puts one new ball into the box.
• Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

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

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

Problem Statement

You are given two sequences: A=(A_1,A_2, \ldots ,A_N) consisting of N positive integers, and B=(B_1, \ldots ,B_M) consisting of M positive integers.

Find the minimum difference of an element of A and an element of B, that is, \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert.

Constraints

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

Sample Input 1

2 2
1 6
4 9

Sample Output 1

2

Here is the difference for each of the four pair of an element of A and an element of B: \lvert 1-4\rvert=3, \lvert 1-9\rvert=8, \lvert 6-4\rvert=2, and \lvert 6-9\rvert=3. We should print the minimum of these values, or 2.

Sample Input 2

1 1
10
10

Sample Output 2

0

Sample Input 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

Sample Output 3

3

Problem Statement

Takahashi is trying to catch many Snuke.

There are five pits at coordinates 0, 1, 2, 3, and 4 on a number line, connected to Snuke's nest.

Now, N Snuke will appear from the pits. It is known that the i-th Snuke will appear from the pit at coordinate X_i at time T_i, and its size is A_i.

Takahashi is at coordinate 0 at time 0 and can move on the line at a speed of at most 1.
He can catch a Snuke appearing from a pit if and only if he is at the coordinate of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• 1 \leq N \leq 10^5
• 0 < T_1 < T_2 < \ldots < T_N \leq 10^5
• 0 \leq X_i \leq 4
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 0 100
3 3 10
5 4 1

Sample Output 1

101

The optimal strategy is as follows.

• Wait at coordinate 0 to catch the first Snuke at time 1.
• Go to coordinate 4 to catch the third Snuke at time 5.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

3
1 4 1
2 4 1
3 4 1

Sample Output 2

0

Takahashi cannot catch any Snuke.

Sample Input 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

Sample Output 3

2978279323

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N.
Respond to the following Q queries in the order they are given.

The k-th query is given in the following format:

i_k x_k

• First, change A_{i_k} to x_k. This change will carry over to subsequent queries.
• Then, print the \rm{mex} of A.
  • The \rm{mex} of A is the smallest non-negative integer not contained in A.

Constraints

• All input values are integers.
• 1 \le N,Q \le 2 \times 10^5
• 0 \le A_i \le 10^9
• 1 \le i_k \le N
• 0 \le x_k \le 10^9

Sample Input 1

8 5
2 0 2 2 1 1 2 5
4 3
4 4
6 3
8 1000000000
2 1

Sample Output 1

4
3
6
5
0

Initially, the sequence A is (2,0,2,2,1,1,2,5).
This input gives you five queries.

• The first query changes A_4 to 3, making A=(2,0,2,3,1,1,2,5).
  • At this point, the \rm{mex} of A is 4.
• The second query changes A_4 to 4, making A=(2,0,2,4,1,1,2,5).
  • At this point, the \rm{mex} of A is 3.
• The third query changes A_6 to 3, making A=(2,0,2,4,1,3,2,5).
  • At this point, the \rm{mex} of A is 6.
• The fourth query changes A_8 to 1000000000, making A=(2,0,2,4,1,3,2,1000000000).
  • At this point, the \rm{mex} of A is 5.
• The fifth query changes A_2 to 1, making A=(2,1,2,4,1,3,2,1000000000).
  • At this point, the \rm{mex} of A is 0.

Problem Statement

We have a grid with H rows and W columns.

We choose K cells in this grid uniformly at random. The score is the number of cells in the minimum rectangle (whose edges are parallel to the axes of the grid) that contains all of the chosen cells.

Find the expected score modulo 998244353.

Constraints

• 1\leq H,W \leq 1000
• 1\leq K \leq HW
• All values in the input are integers.

Sample Input 1

2 2 2

Sample Output 1

665496238

The score equals 4 in the following two cases: if cells (1,1) and (2,2) are chosen, or cells (1,2) and (2,1) are chosen. The other four cases yield a score of 2.

Thus, the expected score equals \frac{4 \times 2 + 2 \times 4} {6} = \frac{8}{3}. Since 665496238 \times 3 \equiv 8\pmod{998244353}, you should print 665496238.

Sample Input 2

10 10 1

Sample Output 2

1

Sample Input 3

314 159 2653

Sample Output 3

639716353