Problem Statement

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 2 types:

• 1 i x: Change A_i to x.
• 2 l r: Print \min(A_l,A_{l+1},\ldots,A_r).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• For type 1 queries, 1 \leq i \leq N, 0 \leq x \leq 10^9
• For type 2 queries, 1 \leq l \leq r \leq N
• All numerical values in the input are integers.

Sample Input 1

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

Sample Output 1

3
2
8

For query 1, print 3, the minimum of A_2,A_3,A_4.

Query 2 changes A to (5,3,2,9,1).

For query 3, print 2, the minimum of A_2,A_3,A_4.

Sample Input 2

3 4
0 1000000000 7
2 1 1
2 2 2
1 1 1000000000
2 1 3

Sample Output 2

0
1000000000
7

Problem Statement

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 2 types:

• 1 l r x: For each i=l,l+1,\ldots,r, add x to A_i.
• 2 l r: Print \min(A_l,A_{l+1},\ldots,A_r).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• For type 1 queries, 1 \leq l \leq r \leq N, 0 \leq x \leq 10^9
• For type 2 queries, 1 \leq l \leq r \leq N
• All numerical values in the input are integers.

Sample Input 1

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

Sample Output 1

3
8
11
7

For query 1, print 3, the minimum of A_2,A_3,A_4.

Query 2 changes A to (5,8,12,14,1).

For query 3, print 8, the minimum of A_2,A_3,A_4.

Sample Input 2

1 5
1000000000
2 1 1
1 1 1 1000000000
2 1 1
1 1 1 1000000000
2 1 1

Sample Output 2

1000000000
2000000000
3000000000

Problem Statement

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 3 types:

• 1 i x: Change A_i to x.
• 2 l t: Print the smallest integer r between l and N, inclusive, that satisfies \displaystyle \sum_{i=l}^{r} A_i \geq t. If no such integer r exists, print N+1.
• 3 r t: Print the largest integer l between 1 and r, inclusive, that satisfies \displaystyle \sum_{i=l}^{r} A_i \geq t. If no such integer l exists, print 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• For type 1 queries, 1 \leq i \leq N, 0 \leq x \leq 10^9
• For type 2 queries, 1 \leq l \leq N, 1 \leq t \leq 10^{15}
• For type 3 queries, 1 \leq r \leq N, 1 \leq t \leq 10^{15}
• All numerical values in the input are integers.

Sample Input 1

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

Sample Output 1

3
3
5
3
6
0
1

For query 1, A_2=1 \lt 4 while A_2+A_3=4, so print 3.

For query 2, A_3+A_4+A_5=7 while A_4+A_5=4, so print 3.

Query 3 changes A to (2,1,1,0,4).

For query 4, A_2+A_3+A_4=2 \lt 4 while A_2+A_3+A_4+A_5=6, so print 5.

For query 5, A_4+A_5=4 \lt 5 while A_3+A_4+A_5=5, so print 3.

For query 6, A_4+A_5=4 \lt 5, and no r satisfies the condition, so print 6.

For query 7, A_1+A_2=3 \lt 4, and no l satisfies the condition, so print 0.

For query 8, A_1=2, so print 1.

Sample Input 2

1 6
0
2 1 1
3 1 1
1 1 1000000000
2 1 1000000000
3 1 1000000000
2 1 1000000000000000

Sample Output 2

2
0
1
1
2

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of 0,1,2.

Process Q queries. Each query is of one of the following 2 types:

• 1 i x: Change A_i to x.
• 2 l r: Print the inversion count of the sequence (A_l,A_{l+1},\ldots,A_r).

Here, the inversion count of a sequence B=(B_1,B_2,\ldots,B_k) of length k is the number of pairs of integers (i,j) satisfying 1 \leq i \lt j \leq k and B_i \gt B_j.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 2
• For type 1 queries, 1 \leq i \leq N, 0 \leq x \leq 2
• For type 2 queries, 1 \leq l \leq r \leq N
• All numerical values in the input are integers.

Sample Input 1

5 5
2 0 1 2 0
2 1 5
2 2 4
1 2 2
2 1 3
2 2 5

Sample Output 1

5
0
2
4

Initially, A=(2,0,1,2,0).

After processing query 3, A=(2,2,1,2,0).

Sample Input 2

6 6
0 2 1 0 2 1
2 1 6
1 1 2
2 1 4
1 4 2
2 3 6
2 4 4

Sample Output 2

5
5
2
0

Problem Statement

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N and a string S of length N consisting of R, G, and B. Let S_i denote the i-th character of S.

Process Q queries. Each query is of one of the following 2 types:

• 1 i x: Change A_i to x.
• 2 l r: Print the sum of A_iA_jA_k over all triples of integers (i,j,k) such that l\leq i\lt j\lt k\leq r and S_i,S_j,S_k are R, G, B in this order, modulo 998244353.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq Q\leq 2\times 10^5
• 0\leq A_i\leq 10^9
• S is a string of length N consisting of R, G, and B.
• For type 1 queries, 1\leq i\leq N, 0\leq x\leq 10^9
• For type 2 queries, 1\leq l\leq r\leq N
• All numerical values in the input are integers.

Sample Input 1

5 5
1 2 3 4 5
RGBGB
2 1 5
1 2 10
2 1 5
2 2 4
2 1 3

Sample Output 1

36
100
0
30

For the first query, the 3 triples satisfying the conditions are (1,2,3),(1,2,5),(1,4,5). The sum of their products is 1\times2\times3+1\times2\times5+1\times4\times5=36.

Sample Input 2

3 5
1000000000 1000000000 1000000000
RGB
2 1 3
1 2 998244353
2 1 3
1 2 998244354
2 1 3

Sample Output 2

747068572
0
716070898

Problem Statement

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 2 types:

• 1 i x: Change A_i to x.
• 2 l r: Print the largest positive integer k satisfying the following condition:
  • There exists an integer p such that l \leq p \leq p+k-1 \leq r and A_p=A_{p+1}=\cdots=A_{p+k-1}.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• For type 1 queries, 1 \leq i \leq N, 0 \leq x \leq 10^9
• For type 2 queries, 1 \leq l \leq r \leq N
• All numerical values in the input are integers.

Sample Input 1

8 7
1 1 2 2 2 3 2 2
2 1 8
2 4 8
1 6 2
2 3 8
1 4 7
2 1 8
2 4 4

Sample Output 1

3
2
6
4
1

The answers to the first 2 queries are 3,2, respectively.

After processing query 3, A=(1,1,2,2,2,2,2,2), so the answer to the next query is 6.

Sample Input 2

6 7
0 1000000000 1000000000 0 0 0
2 1 6
2 2 5
1 3 0
2 2 6
1 2 0
2 1 6
1 6 1000000000

Sample Output 2

3
2
4
6

Problem Statement

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 2 types:

• 1 l r x: For each i=l,l+1,\ldots,r, add x to A_i.
• 2 l r k: Print \displaystyle \sum_{i=l}^{r} A_i^k modulo 998244353.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• For type 1 queries, 1 \leq l \leq r \leq N, 0 \leq x \leq 10^9
• For type 2 queries, 1 \leq l \leq r \leq N, 1 \leq k \leq 4
• All numerical values in the input are integers.

Sample Input 1

4 5
1 2 3 4
2 1 4 1
2 2 4 2
1 2 3 5
2 1 3 3
2 2 4 4

Sample Output 1

10
29
856
6753

For query 1, print 1+2+3+4=10.

After query 3, A=(1,7,8,4). Therefore, for query 4, print 1^3+7^3+8^3=856.

Sample Input 2

3 5
998244352 0 2
2 1 3 2
1 1 2 1
2 1 3 4
1 2 3 1000000000
2 1 3 1

Sample Output 2

5
17
3511297

Problem Statement

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 2 types:

• 1 i x: Change A_i to x.
• 2 l r x: Starting with the given x, perform the following operation for i=l,l+1,\ldots,r in this order, and print the final value of x.
  • If A_i=0, change x to x \bmod{998244353}.
  • If A_i\gt 0, change x to x+A_i.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq Q\leq 2\times 10^5
• 0\leq A_i\leq 10^9
• For type 1 queries, 1\leq i\leq N, 0\leq x\leq 10^9
• For type 2 queries, 1\leq l\leq r\leq N, 0\leq x\leq 10^9
• All numerical values in the input are integers.

Sample Input 1

4 5
8 0 11 5
2 1 4 998244350
1 2 6
2 2 4 10
1 4 0
2 3 4 1000000000

Sample Output 1

21
32
1755658

For the first query, x changes as 998244350,998244358,5,16,21, so print 21.

After query 2, A=(8,6,11,5).

For query 3, x changes as 10,16,27,32, so print 32.

Sample Input 2

6 7
650000000 0 910000007 123456789 0 870000013
2 3 4 750000021
2 2 6 987654321
1 5 420000009
2 3 6 314159265
1 1 0
2 1 3 271828182
2 6 6 1000000000

Sample Output 2

1783456817
894622424
2637616083
1181828189
1870000013

Problem Statement

You are given a sequence of integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 2 types:

• 1 i x: Change A_i to x.
• 2 l r: Choose between 0 and 2 nonempty contiguous subsequences of the sequence (A_l,A_{l+1},\ldots,A_r) that do not share any elements. Print the maximum possible sum of the elements in the chosen contiguous subsequences.

Here, a nonempty contiguous subsequence of (A_l,A_{l+1},\ldots,A_r) is a sequence (A_s,A_{s+1},\ldots,A_t) obtained by choosing integers s,t satisfying l\leq s\leq t\leq r.

Also, when choosing 2 contiguous subsequences, the positions they contain must not overlap.

Constraints

• 1\leq N\leq 10^5
• 1\leq Q\leq 10^5
• -10^9\leq A_i\leq 10^9
• For type 1 queries, 1\leq i\leq N, -10^9\leq x\leq 10^9
• For type 2 queries, 1\leq l\leq r\leq N
• All numerical values in the input are integers.

Sample Input 1

7 7
4 -5 3 -1 2 -6 5
2 1 7
2 2 6
1 4 10
2 1 7
1 6 1
2 1 7
2 2 2

Sample Output 1

9
5
20
25
0

For the first type 2 query, choosing (A_3,A_4,A_5)=(3,-1,2) and (A_7)=(5) gives a sum of 9. This is the maximum.

For query 4, A is (4,-5,3,10,2,-6,5). In this case, choosing (A_3,A_4,A_5) and (A_7) gives a sum of 20, which is the maximum.

For query 7, choosing no contiguous subsequences gives a sum of 0. This is the maximum.

Sample Input 2

4 5
-8 -3 -5 -2
2 1 4
1 2 7
2 1 4
1 4 6
2 1 4

Sample Output 2

0
7
13

Problem Statement

There is a string S of length 10^{18} consisting of 0 and 1. Let S_i denote the i-th character of S.

Initially, all characters of S are 0.

Process Q queries. Each query is of one of the following 2 types:

• 1 l r: Flip S_l,S_{l+1},\ldots,S_r. That is, change each 0 to 1 and each 1 to 0.
• 2 l r: Print the number of 1s among S_l,S_{l+1},\ldots,S_r.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• 1 \leq l \leq r \leq 10^{18}
• All numerical values in the input are integers.

Sample Input 1

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

Sample Output 1

0
5
3
7
7

Initially, all characters of S are 0.

After processing query 2, the characters that are 1 are S_3,S_4,S_5,S_6,S_7.

After processing query 4, the characters that are 1 are S_3,S_4,S_8,S_9,S_{10},S_{11},S_{12}.

Sample Input 2

6
1 999999999999999998 1000000000000000000
2 999999999999999997 1000000000000000000
1 1 1000000000000000000
2 1 1000000000000000000
2 999999999999999997 1000000000000000000
2 1 1

Sample Output 2

3
999999999999999997
1
1

Problem Statement

There is a multiset S of integers. Initially, S has N elements A_1,A_2,\ldots,A_N.

Process Q queries. Each query is of one of the following 3 types:

• 1 x: Add 1 occurrence of x to S.
• 2 x: Remove 1 occurrence of x from S. It is guaranteed that immediately before this query is processed, S contains at least 1 occurrence of x.
• 3: Let x_1,x_2,\ldots,x_k be the sequence obtained by sorting all elements of S in ascending order, including duplicates. Print \displaystyle \sum_{i=1}^{k} i x_i modulo 998244353.

When S is empty, k=0, and the sum above is defined to be 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• For queries of types 1 and 2, 0 \leq x \leq 10^9
• Immediately before each type 2 query, S contains at least 1 occurrence of x.
• All numerical values in the input are integers.

Sample Input 1

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

Sample Output 1

26
35
20
8

Sorting the initial elements of S in ascending order gives (1,2,3,3), so for the first query, print 1 \times 1+2 \times 2+3 \times 3+4 \times 3=26.

Sample Input 2

1 5
998244353
3
2 998244353
3
1 1000000000
3

Sample Output 2

0
0
1755647

For query 3, S is empty at that time, so print 0.

Problem Statement

You are given sequences of integers A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N), and C=(C_1,C_2,\ldots,C_N), each of length N.

Process Q queries. Each query is of one of the following 4 types:

• 1 l r: For every integer k satisfying l\leq k\leq r, swap A_k and B_k.
• 2 l r: For every integer k satisfying l\leq k\leq r, swap B_k and C_k.
• 3 l r: For every integer k satisfying l\leq k\leq r, swap C_k and A_k.
• 4 i: Print the smallest integer j satisfying i\leq j\leq N and \displaystyle\sum_{k=i}^{j}A_k\gt0. If no such j exists, print N+1.

Constraints

• 1\leq N\leq 10^5
• 1\leq Q\leq 10^5
• -10^9\leq A_i,B_i,C_i\leq 10^9
• For queries of types 1,2,3, 1\leq l\leq r\leq N
• For type 4 queries, 1\leq i\leq N
• All numerical values in the input are integers.

Sample Input 1

5 7
3 -4 5 -2 1
-1 6 -3 4 -5
2 -7 1 8 -6
4 2
1 2 4
4 1
2 3 5
4 3
3 1 3
4 2

Sample Output 1

3
1
4
4

For query 1, A_2=-4\leq 0 and A_2+A_3=1>0, so print 3.

After processing query 2, A=(3,6,-3,4,1).

For query 3, A_1=3\gt0, so print 1.

Sample Input 2

6 7
0 -3 3 -5 7 -2
-4 2 -1 0 5 -8
6 -2 0 4 -3 1
4 1
4 6
2 2 6
1 3 5
4 3
3 6 6
4 6

Sample Output 2

5
7
4
7

Problem Statement

For integers a,b that are at least 0 and less than 2^{30}, define the NAND of a and b as follows:

• Represent each of a,b using 30 digits in base 2, adding leading 0s if necessary. For each digit, set the resulting digit to 0 if the corresponding digits of both numbers are 1, and to 1 otherwise. This gives an integer represented by 30 digits in base 2. This integer is the NAND of a and b.

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of integers that are at least 0 and less than 2^{30}.

Process Q queries. Each query is of one of the following 2 types:

• 1 p x: Change A_p to the integer x, which is at least 0 and less than 2^{30}.
• 2 l r: Set B_l=A_l, and then, for i=l+1,l+2,\ldots,r in this order, define B_i as the NAND of B_{i-1} and A_i. Print B_r.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \lt 2^{30}
• For type 1 queries, 1 \leq p \leq N, 0 \leq x \lt 2^{30}
• For type 2 queries, 1 \leq l \leq r \leq N
• All numerical values in the input are integers.

Sample Input 1

4 3
5 3 12 10
2 1 4
2 2 3
2 3 3

Sample Output 1

1073741821
1073741823
12

For query 1, the answer can be calculated as follows:

1. B_1=A_1=5.
2. The NAND of B_1 (=5) and A_2 (=3) is 1073741822, so B_2=1073741822.
3. The NAND of B_2 (=1073741822) and A_3 (=12) is 1073741811, so B_3=1073741811.
4. The NAND of B_3 (=1073741811) and A_4 (=10) is 1073741821, so B_4=1073741821. Print this value.

Sample Input 2

5 6
7 10 12 3 5
2 2 4
1 3 6
2 1 5
2 3 3
1 1 1073741823
2 1 2

Sample Output 2

1073741820
1073741819
6
1073741813

Sample Input 3

3 5
1073741823 0 536870912
2 1 2
2 1 3
1 2 1073741823
2 1 3
2 2 2

Sample Output 3

1073741823
536870911
1073741823
1073741823

Problem Statement

There is a grid with N rows and N columns. Let cell (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

Initially, cell (i,j) contains the integer i \times j.

Perform the following operation Q times. In operation k, overwrite the integer in every cell (i,j) satisfying a_k \leq i \leq c_k and b_k \leq j \leq d_k with 0.

Find the sum of the integers in all cells of the grid after all operations, modulo 998244353.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq a_k \leq c_k \leq N
• 1 \leq b_k \leq d_k \leq N
• All numerical values in the input are integers.

Sample Input 1

3 1
2 2 3 3

Sample Output 1

11

Initially, the integers in the cells of the grid are as follows:

1 2 3
2 4 6
3 6 9

After all operations, the integers in the cells are as follows:

1 2 3
2 0 0
3 0 0

Sample Input 2

3 2
1 2 2 3
2 1 3 2

Sample Output 2

10

Sample Input 3

4 3
1 1 2 4
3 1 4 2
3 3 4 4

Sample Output 3

0

Problem Statement

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. In each query, you are given integers l,r. Find

\[ \sum_{l \leq s \leq t \leq r} \min(A_s,A_{s+1},\ldots,A_t) \]

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^6
• 1 \leq l \leq r \leq N
• All numerical values in the input are integers.

Sample Input 1

4 4
3 1 4 2
1 1
1 2
2 4
1 4

Sample Output 1

3
5
11
17

For query 1, only the case s=t=1 needs to be considered, so the answer is 3.

For query 2, the minimum values for (s,t)=(1,1),(1,2),(2,2) are 3,1,1, respectively, so the answer is 5.

Sample Input 2

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

Sample Output 2

14
20
15

Sample Input 3

6 4
0 1000000 2 999999 3 4
1 6
2 5
2 2
4 6

Sample Output 3

2000031
2000017
1000000
1000015

Problem Statement

There are 2N vertices on a circle, arranged clockwise in the order vertex 1, vertex 2, \ldots, vertex 2N.

You are given a sequence of N pairs of integers ((A_1,B_1),(A_2,B_2),\ldots,(A_N,B_N)). The 2N values A_1,\ldots,A_N,B_1,\ldots,B_N are all distinct.

Process Q queries. In the j-th query, you are given integers l_j,r_j. Determine whether curves can be drawn satisfying all of the following conditions:

• For each i=l_j,l_j+1,\ldots,r_j, draw 1 curve connecting vertex A_i and vertex B_i.
• Every curve lies inside the circle or on its circumference.
• No 2 distinct curves intersect.

Each query is independent. Curves drawn in one query do not affect other queries.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq 2N
• (A_1,\ldots,A_N,B_1,\ldots,B_N) is a permutation of (1,2,\ldots,2N).
• 1 \leq l_j \leq r_j \leq N
• All numerical values in the input are integers.

Sample Input 1

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

Sample Output 1

Yes
Yes
No
No
Yes
Yes

For query 1, curves connecting vertices 1 and 10, vertices 2 and 5, and vertices 3 and 4 can be drawn without intersecting each other.

For query 3, a curve connecting vertices 6 and 8 and a curve connecting vertices 7 and 9 cannot be drawn without intersecting each other.

Sample Input 2

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

Sample Output 2

No
Yes
No
Yes

Problem Statement

You are given positive integers N,M,Q, a string S of length N consisting of 0 and 1, and a sequence of positive integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 2 types:

• 1 i: Change the i-th character S_i of S from 0 to 1, or from 1 to 0.
• 2 x l r: Find the amount of money obtained by the following procedure:
  • You start at coordinate x on a number line with 0 yen.
  • For i=l,l+1,\ldots,r in this order, do the following:
    • Face in the negative direction if S_i is 0, and in the positive direction if it is 1.
    • Repeat the following operation A_i times:
      • If the coordinate 1 unit ahead in the direction you are facing is between 0 and M, inclusive, move there and receive 1 yen. Otherwise, keep your position and the amount of money unchanged.

For each type 2 query, start the procedure at the specified coordinate x with 0 yen, without carrying over your movement or money from other queries.

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le M \le 10^9
• 1 \le Q \le 2 \times 10^5
• S is a string of length N consisting of 0 and 1.
• 1 \le A_i \le 10^9
• For type 1 queries, 1 \le i \le N
• For type 2 queries, 0 \le x \le M, 1 \le l \le r \le N
• All numerical values in the input are integers.

Sample Input 1

5 10 8
10100
4 8 3 6 2
2 5 1 5
1 2
2 5 1 5
2 0 2 4
1 5
2 10 4 5
2 3 3 3
1 1

Sample Output 1

19
13
16
8
3

For query 1, starting at coordinate 5, you attempt to move in the positive, negative, positive, negative, and negative directions in this order. Your coordinates after the respective stages are 9,1,4,0,0, and you receive 19 yen.

For query 3, starting at coordinate 5, you attempt to move in the positive, positive, positive, negative, and negative directions in this order. Your coordinates after the respective stages are 9,10,10,4,2, and the amount of money obtained is 13 yen.

Sample Input 2

3 4 5
010
10 1 10
2 0 1 3
2 4 1 3
1 1
2 2 1 2
2 2 2 3

Sample Output 2

2
6
2
4

Problem Statement

There is a grid with N rows and W columns. Let cell (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

Each cell of the grid contains 1 digit. Initially, cell (i,j) contains the j-th character of the string S_i.

Process Q queries. Each query is of one of the following 2 types:

• 1 i T: For j=1,2,\ldots,W, change the digit in cell (i,j) to the j-th character of T.
• 2 a b c d: Determine whether you can reach cell (c,d) from cell (a,b) by repeatedly moving to a cell that shares an edge with the current cell and contains the same digit as the current cell.

Constraints

• 2 \le N \le 10^5
• 2 \le W \le 10
• 1 \le Q \le 5 \times 10^4
• S_i is a string of length W consisting of digits.
• For type 1 queries, 1 \le i \le N
• For type 1 queries, T is a string of length W consisting of digits.
• For type 2 queries, 1 \le a,c \le N, 1 \le b,d \le W
• For type 2 queries, (a,b) \ne (c,d)
• When a type 2 query is given, cells (a,b) and (c,d) contain the same digit.
• All numerical values in the input are integers.

Sample Input 1

4 5 5
01010
00000
99999
01010
2 1 1 2 5
2 1 1 4 1
1 3 00000
2 1 1 4 1
2 1 2 4 2

Sample Output 1

Yes
No
Yes
No

Initially, you can reach cell (2,5) from cell (1,1) by passing only through cells containing the digit 0. However, you cannot reach cell (4,1) from cell (1,1).

After changing row 3 to 00000, you can reach cell (4,1) from cell (1,1).

Sample Input 2

4 7 1
1112111
1212121
1211121
1222222
2 4 1 3 7

Sample Output 2

Yes

You can reach cell (3,7) from cell (4,1) by moving in the following order, for example:

\[ (4,1),(3,1),(2,1),(1,1),(1,2),(1,3),(2,3),(3,3),(3,4),(3,5),(2,5),(1,5),(1,6),(1,7),(2,7),(3,7) \]

Problem Statement

You are given a sequence of integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. Each query is of one of the following 2 types:

• 1 i x: Change A_i to x.
• 2 l r: Over all choices of an integer m and a sequence of integers (i_1,i_2,\ldots,i_m) satisfying 3 \leq m and l \leq i_1 \lt i_2 \lt \cdots \lt i_m \leq r, print the maximum value of the following expression:

\[ \sum_{k=1}^{m-2} \left|A_{i_k}+2A_{i_{k+1}}+3A_{i_{k+2}}\right| \]

Constraints

• 1 \leq N \leq 5 \times 10^4
• 1 \leq Q \leq 5 \times 10^4
• -10^9 \leq A_i \leq 10^9
• For type 1 queries, 1 \leq i \leq N, -10^9 \leq x \leq 10^9
• For type 2 queries, 1 \leq l \lt r \leq N, r-l \geq 2
• All numerical values in the input are integers.

Sample Input 1

5 5
1 -2 3 -1 2
2 1 3
2 1 5
1 2 4
2 1 3
2 2 5

Sample Output 1

6
16
18
16

For query 1, the only choice is m=3,(i_1,i_2,i_3)=(1,2,3), and the value sought is 6.

For query 2, choosing m=4,(i_1,i_2,i_3,i_4)=(1,2,3,5) gives a value of 16. This is the maximum.

Query 3 changes A_2 to 4.

Sample Input 2

6 4
-3 1 -4 1 -5 9
2 1 6
1 4 -2
2 2 5
2 3 6

Sample Output 2

52
36
38

Sample Input 3

3 3
-1000000000 -1000000000 -1000000000
2 1 3
1 2 1000000000
2 1 3

Sample Output 3

6000000000
2000000000

Problem Statement

For a positive integer K and a sequence of integers C=(C_1,C_2,\ldots,C_L) of length L, define the K-inversion count of C as the number of pairs of integers (i,j) satisfying both of the following conditions:

• 1 \le i \lt j \le L
• C_j \lt C_i \le C_j+K

You are given positive integers N,Q,K and a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries. In the i-th query, you are given positive integers m_i,x_i.

Choose an integer t between 0 and m_i, inclusive, and insert x_i immediately after the first t elements of the sequence (A_1,A_2,\ldots,A_{m_i}). That is, the resulting sequence is

\[ (A_1,\ldots,A_t,x_i,A_{t+1},\ldots,A_{m_i}) \]

Here, x_i is inserted at the beginning if t=0, and at the end if t=m_i.

Find the minimum possible K-inversion count of the resulting sequence. Each query is independent.

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• 1 \le K \le N
• 1 \le A_i \le N
• 1 \le m_i \le N
• 1 \le x_i \le N
• All numerical values in the input are integers.

Sample Input 1

4 3 2
3 1 4 2
4 2
3 4
1 1

Sample Output 1

4
1
0

For query 1, inserting 2 with t=0 gives the sequence (2,3,1,4,2), whose 2-inversion count is 4. There is no insertion position that makes the 2-inversion count at most 3, so the answer is 4.

Sample Input 2

5 5 1
2 5 1 4 3
5 3
4 1
2 5
3 2
1 2

Sample Output 2

3
2
0
1
0

Problem Statement

For a sequence B=(B_1,B_2,\ldots,B_M) of length M, let C=(C_1,C_2,\ldots,C_M) be the sequence obtained by sorting it in ascending order. When M\geq 4, define the score of B as C_{M-1}-C_2.

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N (4\leq N). Partition A into 1 or more contiguous subsequences, each of length at least 4.

Find the maximum possible sum of the scores of all contiguous subsequences obtained by the partition.

Each input file contains T test cases. Solve all of them.

Constraints

• 1 \leq T \leq 10^5
• 4 \leq N \leq 4 \times 10^5
• 0 \leq A_i \leq 10^9
• The sum of N over all test cases in a single input file is at most 4 \times 10^5.
• All numerical values in the input are integers.

Sample Input 1

3
4
1 2 10 20
8
0 0 1 1 0 0 1 1
5
5 5 5 5 5

Sample Output 1

8
2
0

For test case 1, take the entire sequence as 1 contiguous subsequence. Sorting it in ascending order gives (1,2,10,20), so its score is 10-2=8. This is the maximum.

For test case 2, partitioning A into (0,0,1,1) and (0,0,1,1) gives a total score of 2. This is the maximum.

Sample Input 2

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

Sample Output 2

10

Sample Input 3

2
9
1000000000 0 7 6 5 4 3 2 1
11
4 9 1 8 2 7 3 6 0 5 10

Sample Output 3

6
10

Problem Statement

There is a tree with N vertices numbered from 1 to N. Edge i connects vertices u_i and v_i.

An integer interval [a,b] is good if the subgraph induced by vertices a,a+1,\ldots,b is connected.

Process Q queries. In the i-th query, you are given integers L_i,R_i. Find the number of pairs of integers (a,b) satisfying both of the following conditions:

• L_i \leq a \leq b \leq R_i
• The interval [a,b] is good.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq u_i \lt v_i \leq N
• The given graph is a tree.
• 1 \leq L_i \leq R_i \leq N
• All numerical values in the input are integers.

Sample Input 1

5 4
1 4
2 4
3 5
4 5
1 5
2 5
1 3
4 4

Sample Output 1

9
7
3
1

The following 9 intervals are good:

[1,1], [1,5], [2,2], [2,5], [3,3], [3,5], [4,4], [4,5], [5,5]

Sample Input 2

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

Sample Output 2

17
3
9

Problem Statement

For a sequence of integers B=(B_1,B_2,\ldots,B_k) of length k, consider performing the following operation 0 or more times:

• Choose an integer i satisfying 1 \le i \le k-1 and an integer x (x may be negative).
• Add x to B_i and 2x to B_{i+1}.

We call B a good sequence if all elements of B can be made equal by these operations.

You are given a sequence of nonnegative integers A=(A_1,A_2,\ldots,A_N) of length N. Process Q queries. Each query is of one of the following 2 types:

• 1 i x: Change A_i to x.
• 2 l r: Determine whether the sequence (A_l,A_{l+1},\ldots,A_r) is a good sequence.

Constraints

• 1 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• 0 \le A_i \le 10^9
• For type 1 queries, 1 \le i \le N, 0 \le x \le 10^9
• For type 2 queries, 1 \le l \le r \le N
• All numerical values in the input are integers.

Sample Input 1

5 7
1 2 5 4 0
2 1 1
2 1 2
2 1 3
1 3 3
2 1 3
2 2 5
2 1 5

Sample Output 1

Yes
Yes
No
Yes
No
No

The sequence obtained in the first type 2 query is (1). All its elements are already equal without any operations, so it is a good sequence.

The sequence obtained in the 2-nd type 2 query is (1,2). Performing an operation with i=1,x=-1 gives (0,0), so it is a good sequence.

Sample Input 2

6 6
1000000000 0 999999999 1 500000000 42
2 1 6
2 2 4
1 4 1000000000
2 2 4
2 4 6
2 3 3

Sample Output 2

No
No
No
Yes
Yes

Problem Statement

You are given sequences of nonnegative integers A=(A_1,A_2,\ldots,A_N) and g=(g_1,g_2,\ldots,g_N) of length N, and a sequence of integers d=(d_1,d_2,\ldots,d_{N-1}) of length N-1. Note that g_j satisfies 1 \leq g_j \leq 2.

Using the sequences g,d, define f(B) for a sequence of integers B=(B_1,B_2,\ldots,B_N) of length N as follows.

You may freely choose a sequence of integers C=(C_1,C_2,\ldots,C_N) of length N. Define the cost of B and C as

\[ \sum_{j=1}^{N} g_j |B_j-C_j|+\sum_{j=1}^{N-1} d_j |C_j-C_{j+1}| \]

Then, f(B) is the minimum cost over all possible choices of the integer sequence C.

Process the following Q queries in order.

In query k, you are given integers i_k,x_k. Change A_{i_k} to x_k and calculate f(A).

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_j \leq 10^9
• 1 \leq g_j \leq 2
• 1 \leq d_j \leq 10^9
• 1 \leq i_k \leq N
• 0 \leq x_k \leq 10^9
• All numerical values in the input are integers.

Sample Input 1

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

Sample Output 1

3
4
6

After query 1, A=(1,3,2). For example, choosing C=(2,2,2) gives a cost of 3. The cost cannot be made less than 3, so f(A)=3.

Sample Input 2

2 4
0 10
2 2
1
1 10
2 0
1 0
2 10

Sample Output 2

0
10
0
10

When all elements of A are equal, choosing C=A gives a cost of 0.

Sample Input 3

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

Sample Output 3

30
18
4
10
15