Problem Statement

We have HW cards arranged in a matrix with H rows and W columns.
For each i=1, \ldots, N, the card at the A_i-th row from the top and B_i-th column from the left has a number i written on it. The other HW-N cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

• If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
• If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

• 1 \leq H,W \leq 10^9
• 1 \leq N \leq \min(10^5,HW)
• 1 \leq A_i \leq H
• 1 \leq B_i \leq W
• All pairs (A_i,B_i) are distinct.
• All values in input are integers.

Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with 1 is at the 2-nd row from the top and 1-st column from the left, and the card with 2 is at the 1-st row from the top and 2-nd column from the left.

Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

Problem Statement

You are given a sequence A of length N.
Freely choose exactly K elements from A and remove them, then concatenate the remaining elements in their original order to form a new sequence B.
Find the minimum possible value of this: the maximum value of B minus the minimum value of B.

Constraints

• All inputs are integers.
• 1 \le K < N \le 2 \times 10^5
• 1 \le A_i \le 10^9

Sample Input 1

5 2
3 1 5 4 9

Sample Output 1

2

Consider removing exactly two elements from A=(3,1,5,4,9).

• For example, if you remove the 2nd element 1 and the 5th element 9, the resulting sequence is B=(3,5,4).
  • In this case, the maximum value of B is 5 and the minimum value is 3, so (maximum value of B) - (minimum value of B) =2, which is the minimum possible value.

Sample Input 2

6 5
1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

8 3
31 43 26 6 18 36 22 13

Sample Output 3

18

Problem Statement

You are given length-N lowercase English strings S and T, and M pairs of integers (L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M).

Perform the following operation for i=1,2,\ldots,M in order:

• Swap the L_i-th through R_i-th characters of S and the L_i-th through R_i-th characters of T.
  • For example, if S is abcdef, T is ghijkl, and (L_i,R_i)=(3,5), then S and T become abijkf and ghcdel, respectively.

Find the string S after performing the M operations.

Constraints

• 1\leq N\leq 5\times 10^5
• 1\leq M\leq 2\times 10^5
• Each of S and T is a length-N lowercase English strings.
• 1\leq L_i\leq R_i\leq N
• N, M, L_i, and R_i are integers.

Sample Input 1

5 3
apple
lemon
2 4
1 5
5 5

Sample Output 1

lpple

Initially, S and T are apple and lemon, respectively.

• After the operation for i=1, S and T are aemoe and lppln, respectively.
• After the operation for i=2, S and T are lppln and aemoe, respectively.
• After the operation for i=3, S and T are lpple and aemon, respectively.

Thus, the string S after the three operations is lpple.

Sample Input 2

10 5
lemwrbogje
omsjbfggme
5 8
4 8
1 3
6 6
1 4

Sample Output 2

lemwrfogje

Problem Statement

We have an empty sequence A. You will be given Q queries, which should be processed in the order they are given. Each query is of one of the three kinds below:

• 1 x : Append x to the end of A.
• 2 : Print the element at the beginning of A. Then, delete that element. It is guaranteed that A will not empty when this query is given.
• 3 : Sort A in ascending order.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• 0 \leq x \leq 10^9
• A will not be empty when a query 2 is given.
• All values in input are integers.

Sample Input 1

8
1 4
1 3
1 2
1 1
3
2
1 0
2

Sample Output 1

1
2

The i-th line below shows the contents of A after the i-th query is processed in Sample Input 1.

• (4)
• (4, 3)
• (4, 3, 2)
• (4, 3, 2, 1)
• (1, 2, 3, 4)
• (2, 3, 4)
• (2, 3, 4, 0)
• (3, 4, 0)

Sample Input 2

9
1 5
1 5
1 3
2
3
2
1 6
3
2

Sample Output 2

5
3
5

The i-th line below shows the contents of A after the i-th query is processed in Sample Input 2.

• (5)
• (5, 5)
• (5, 5, 3)
• (5, 3)
• (3, 5)
• (5)
• (5, 6)
• (5, 6)
• (6)

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer M. Find the number, modulo 998244353, of non-empty and not necessarily contiguous subsequences of A such that the least common multiple (LCM) of the elements in the subsequence is M. Two subsequences are distinguished if they are taken from different positions in the sequence, even if they coincide as sequences. Also, the LCM of a sequence with a single element is that element itself.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^{16}
• 1 \leq A_i \leq 10^{16}
• All input values are integers.

Sample Input 1

4 6
2 3 4 6

Sample Output 1

5

The subsequences of A whose elements have an LCM of 6 are (2,3),(2,3,6),(2,6),(3,6),(6); there are five of them.

Sample Input 2

5 349
1 1 1 1 349

Sample Output 2

16

Note that even if some subsequences coincide as sequences, they are distinguished if they are taken from different positions.

Sample Input 3

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

Sample Output 3

2688