Problem Statement

There is an integer sequence S of length N. Initially, all elements of S are 0.

You are also given two integer sequences of length Q: P=(P_1,P_2,\dots,P_Q) and V=(V_1,V_2,\dots,V_Q).

Snuke wants to perform Q operations on the sequence S in order. The i-th operation is as follows:

• Perform one of the following:
  • Replace each of the elements S_1, S_2, \dots, S_{P_i} with V_i. However, before this operation, if there is an element among S_1, S_2, \dots, S_{P_i} that is strictly greater than V_i, Snuke will start crying.
  • Replace each of the elements S_{P_i}, S_{P_i+1}, \dots, S_N with V_i. However, before this operation, if there is an element among S_{P_i}, S_{P_i+1}, \dots, S_N that is strictly greater than V_i, Snuke will start crying.

Find the number of sequences of Q operations where Snuke can perform all operations without crying, modulo 998244353.

Two sequences of operations are distinguished if and only if there is 1 \leq i \leq Q such that the choice for the i-th operation is different.

Constraints

• 2 \leq N \leq 5000
• 1 \leq Q \leq 5000
• 1 \leq P_i \leq N
• 1 \leq V_i \leq 10^9
• All input values are integers.

Sample Input 1

8 3
1 8
8 1
2 1

Sample Output 1

1

Snuke can perform the three operations without crying as follows:

• Replace S_1 with 8.
• Replace S_8 with 1.
• Replace S_2, S_3, \dots, S_8 with 1.

No other sequences of operations satisfy the conditions, so the answer is 1. For example, if he replaces S_1, S_2, \dots, S_8 with 8 in the first operation, he will cry in the second operation regardless of the choice.

Sample Input 2

8 3
8 1
1 8
1 2

Sample Output 2

0

No matter how he performs the first two operations, he will cry in the third operation.

Sample Input 3

241 82
190 3207371
229 3639088
61 4428925
84 17258698
34 42692503
207 59753183
180 67198566
78 99285033
60 102449991
234 122146510
111 126959145
141 152331579
78 159855439
11 169658471
22 189991287
37 204602946
73 209329065
72 215363269
152 236450854
175 237822921
22 261431608
144 252550201
54 268889550
238 276997357
69 313065279
226 330144323
6 335788783
126 345410019
220 348318997
166 365778763
142 382251905
200 406191336
234 392702679
83 409660987
183 410908761
142 445707116
205 470279207
230 486436406
156 494269002
113 495687706
200 500005738
162 505246499
201 548652987
86 449551554
62 459527873
32 574001635
230 601073337
175 610244315
174 613857555
181 637452273
158 637866397
148 648101378
172 646898076
144 682578257
239 703460335
192 713255331
28 727075136
196 730768166
111 751850547
90 762445737
204 762552166
72 773170159
240 803415865
32 798873367
195 814999380
72 842641864
125 851815348
116 858041919
200 869948671
195 873324903
5 877767414
105 877710280
150 877719360
9 884707717
230 880263190
88 967344715
49 977643789
167 979463984
70 981400941
114 991068035
94 991951735
141 995762200

Sample Output 3

682155965

Remember to take the count modulo 998244353.

Problem Statement

You are given positive integers N and K.

An integer sequence of length N where all elements are between 1 and 2^K - 1, inclusive, is called a good sequence.

The score of a good sequence A=(A_1,A_2,\ldots,A_N) is defined as follows:

• The number of distinct integers that can be expressed as \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor using an integer i between 1 and N, inclusive, and a non-negative integer k.

For example, for A=(3,5), five integers can be expressed as \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor: 0, 1, 2, 3, and 5, so the score is 5.

Find one good sequence with the maximum score.

For each input file, you are given T test cases to solve.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^5
• 1 \leq K \leq 30
• The sum of N across the test cases in a single input file is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
3 3
7 2
8 20

Sample Output 1

5 6 7
2 2 3 3 1 3 3
662933 967505 876482 840117 1035841 651549 543175 781219

Consider the first test case.

For A=(5,6,7), seven integers can be expressed as \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor: 0, 1, 2, 3, 5, 6, and 7, so its score is 7.

Outputs such as A=(7,4,5) and A=(6,5,4) would also be accepted.

Problem Statement

An integer sequence of length between 1 and N, inclusive, where each element is between 1 and M, inclusive, is called a good sequence.

The score of a good sequence is defined as the number of positive divisors of X, where X is the product of the elements in the sequence.

There are \displaystyle \sum_{k=1}^{N}M^k good sequences. Find the sum of the scores of all those sequences modulo 998244353.

Constraints

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

Sample Input 1

1 7

Sample Output 1

16

There are seven good sequences: (1),(2),(3),(4),(5),(6),(7). Their scores are 1,2,2,3,2,4,2, respectively, so the answer is 1+2+2+3+2+4+2=16.

Sample Input 2

3 11

Sample Output 2

16095

For example, (8,11) and (1,8,2) are good sequences. Here is the process of calculating their scores:

• The product of the elements in (8,11) is 8 \times 11 = 88. 88 has eight positive divisors: 1,2,4,8,11,22,44,88, so the score of (8,11) is 8.
• The product of the elements in (1,8,2) is 1 \times 8 \times 2 = 16. 16 has five positive divisors: 1,2,4,8,16, so the score of (1,8,2) is 5.

Sample Input 3

81131 14

Sample Output 3

182955659

Remember to take the result modulo 998244353.

Problem Statement

An integer sequence where no two adjacent elements are the same is called a good sequence.

You are given two good sequences of length N: A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N). Each element of A and B is between 0 and M-1, inclusive.

You can perform the following operations on A any number of times, possibly zero:

• Choose an integer i between 1 and N, inclusive, and perform one of the following:
  • Set A_i \leftarrow (A_i + 1) \bmod M.
  • Set A_i \leftarrow (A_i - 1) \bmod M. Here, (-1) \bmod M = M - 1.

However, you cannot perform an operation that makes A no longer a good sequence.

Determine if it is possible to make A equal to B, and if it is possible, find the minimum number of operations required to do so.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 10^6
• 0\leq A_i,B_i< M(1\leq i\leq N)
• A_i\ne A_{i+1}(1\leq i\leq N-1)
• B_i\ne B_{i+1}(1\leq i\leq N-1)
• All input values are integers.

Sample Input 1

3 9
2 0 1
4 8 1

Sample Output 1

3

You can achieve the goal in three operations as follows:

• Set A_1 \leftarrow (A_1 + 1) \bmod M. Now A = (3, 0, 1).
• Set A_2 \leftarrow (A_2 - 1) \bmod M. Now A = (3, 8, 1).
• Set A_1 \leftarrow (A_1 + 1) \bmod M. Now A = (4, 8, 1).

It is impossible to achieve the goal in two or fewer operations, so the answer is 3.

For example, you cannot set A_2 \leftarrow (A_2 + 1) \bmod M in the first operation, because it would make A = (2, 1, 1), which is not a good sequence.

Sample Input 2

3 9
1 8 2
1 8 2

Sample Output 2

0

A and B might be equal from the beginning.

Sample Input 3

24 182
128 115 133 52 166 92 164 119 143 99 54 162 86 2 59 166 24 78 81 5 109 67 172 99
136 103 136 28 16 52 2 85 134 64 123 74 64 28 85 161 19 74 14 110 125 104 180 75

Sample Output 3

811

Problem Statement

You are given positive integers N, M, K, a non-negative integer C, and an integer sequence A=(A_1, A_2, \ldots, A_N) of length N.

Find \displaystyle \sum_{k=0}^{K-1}\min_{1\le i\le N}\lbrace(Ck+A_i)\ \mathrm{mod}\ M \rbrace.

Constraints

• 1 \le N \le 10^5
• 1 \le M \le 10^9
• 0 \le C < M
• 1 \le K \le 10^9
• 0 \le A_i < M
• All input values are integers.

Sample Input 1

2 5 3 3
1 3

Sample Output 1

4

For k=0, \lbrace(3k+1)\ \mathrm{mod}\ 5 \rbrace=1 and \lbrace(3k+3)\ \mathrm{mod}\ 5 \rbrace=3, so \displaystyle \min_{1\le i\le N}\lbrace(Ck+A_i)\ \mathrm{mod}\ M \rbrace=1.

For k=1, \lbrace(3k+1)\ \mathrm{mod}\ 5 \rbrace=4 and \lbrace(3k+3)\ \mathrm{mod}\ 5 \rbrace=1, so \displaystyle \min_{1\le i\le N}\lbrace(Ck+A_i)\ \mathrm{mod}\ M \rbrace=1.

For k=2, \lbrace(3k+1)\ \mathrm{mod}\ 5 \rbrace=2 and \lbrace(3k+3)\ \mathrm{mod}\ 5 \rbrace=4, so \displaystyle \min_{1\le i\le N}\lbrace(Ck+A_i)\ \mathrm{mod}\ M \rbrace=2.

Therefore, the answer is 1+1+2=4. Hence, print 4.

Sample Input 2

5 4 3 182
0 3 2 1 2

Sample Output 2

0

Sample Input 3

5 718 651 193855
3 532 44 109 58

Sample Output 3

29484897

Problem Statement

You are given integers N and Q, and two integer sequences of length Q: A=(A_1,A_2,\ldots,A_Q) and B=(B_1,B_2,\ldots, B_Q).

For each k=1,2,\ldots,Q, solve the following problem:

There is an undirected graph with N vertices numbered from 0 to N-1 and N edges. The i-th edge (0 \le i < N) connects vertices i and (A_k \times i + B_k) \mod N bidirectionally. Find the number of connected components in this undirected graph.

Constraints

• 1 \le N \le 10^6
• 1 \le Q \le 10^5
• 0 \le A_k < N
• 0 \le B_k < N
• All input values are integers.

Sample Input 1

6 3
2 1
0 1
1 0

Sample Output 1

2
1
6

For k=1, the graph has the following two connected components:

• A connected component with vertices 0,1,3,4.
• A connected component with vertices 2,5.

Thus, the answer for k=1 is 2.

Sample Input 2

11 3
9 1
5 3
8 0

Sample Output 2

3
3
2

For k=1, the graph has the following three connected components:

• A connected component with vertices 0,1,3,6,10.
• A connected component with vertices 2,5,7,8,9.
• A connected component with vertex 4.

Thus, the answer for k=1 is 3.

Sample Input 3

182 3
61 2
77 88
180 55

Sample Output 3

36
14
9