Problem Statement

Takahashi can combine a head part and a body part to create a robot. A robot falls over if the weight of the head part is greater than the weight of the body part.

Currently, he has one head part and one body part. The weight of the head part is H grams, and the weight of the body part is B grams.

He wants to make the body part heavier so that the robot does not fall over. Find how many more grams the body part needs to be made heavier so that his robot does not fall over.

Constraints

• 1\le H\le100
• 1\le B\le100
• All input values are integers.

Sample Input 1

43 1

Sample Output 1

42

By making the body part 42 grams heavier, Takahashi can make the weights of the head part and body part equal.

When the amount by which the body part is made heavier is less than 42 grams, his robot will fall over, so print 42.

Sample Input 2

4 31

Sample Output 2

0

Even if he creates the robot as is, the robot will not fall over, so print 0.

Sample Input 3

1 1

Sample Output 3

0

Problem Statement

There is a robot, and initially the weight of the robot is X. This robot has N types of parts that can be attached simultaneously: type 1, type 2,\ldots, type N. The weight of the type i\ (1\le i\le N) part is W _ i. Initially, none of the N types of parts are attached to the robot.

Process the following Q queries in order. The i-th query (1\le i\le Q) is represented by an integer P _ i and is as follows:

• If the type P _ i part is not currently attached to the robot, attach it; if it is attached, remove it. Then, print the current weight of the robot.

Constraints

• 1\le X\le100
• 1\le N\le100
• 1\le W _ i\le100\ (1\le i\le N)
• 1\le Q\le100
• 1\le P _ i\le N\ (1\le i\le Q)
• All input values are integers.

Sample Input 1

31
4
15 92 65 35
4
3
1
4
1

Sample Output 1

96
111
146
131

Initially, the weight of the robot is 31. For each query, the weight of the robot becomes as follows:

• In the 1-st query, attach the type 3 part to the robot. The weight of the robot becomes 31+65=96.
• In the 2-nd query, attach the type 1 part to the robot. The weight of the robot becomes 96+15=111.
• In the 3-rd query, attach the type 4 part to the robot. The weight of the robot becomes 111+35=146.
• In the 4-th query, remove the type 1 part from the robot. The weight of the robot becomes 146-15=131.

Sample Input 2

41
10
73 8 55 26 97 48 37 47 35 55
15
1
2
7
1
6
3
10
8
4
8
1
5
9
9
3

Sample Output 2

114
122
159
86
134
189
244
291
317
270
343
440
475
440
385

Problem Statement

Takahashi can combine a head part and a body part to create a robot. A robot falls over if the weight of the head part is greater than the weight of the body part.

Currently, he has N head parts and M body parts. The weight of the i-th (1\le i\le N) head part is H _ i grams, and the weight of the i-th (1\le i\le M) body part is B _ i grams.

He wants to create a total of K robots that do not fall over by appropriately combining the parts he has. Determine whether he can achieve his goal by combining the parts well.

Here, a part cannot be used to create multiple robots, and two or more head parts (or two or more body parts) cannot be used to create one robot.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le M\le2\times10 ^ 5
• 1\le K\le\min\lbrace N,M\rbrace
• 1\le H _ i\le10 ^ 9\ (1\le i\le N)
• 1\le B _ i\le10 ^ 9\ (1\le i\le M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

If we denote combining the i-th head part and the j-th body part as (i,j), then Takahashi can create three robots that do not fall over by combining them as (1,2),(2,4),(3,6), for example.

Thus, print Yes.

Sample Input 2

1 1 1
43
1

Sample Output 2

No

His head part is too heavy, so he cannot create any robot that does not fall over.

Sample Input 3

1 1 1
100
100

Sample Output 3

Yes

Note that a robot does not fall over if the head and body have equal weights.

Sample Input 4

12 15 12
748 169 586 329 972 529 432 519 408 587 138 249
656 114 632 299 984 755 404 772 155 506 832 854 353 465 387

Sample Output 4

Yes

Problem Statement

There is a robot consisting of a head and a body. This robot has N types of parts that can be attached simultaneously: type 1, type 2,\ldots, type N. The weight of the type i\ (1\le i\le N) part is W _ i. Each part has a different happiness when attached to the head versus when attached to the body. The happiness when the type i\ (1\le i\le N) part is attached to the head is H _ i, and the happiness when attached to the body is B _ i.

The robot falls over if the weight of the head is greater than the weight of the body. Here, the weight of the head and the weight of the body are the sums of the weights of the parts attached to the head or body, respectively.

Takahashi wants to attach all N types of parts to the robot, one of each. Find the maximum possible sum of the happiness of all parts when the parts are attached without causing the robot to fall over.

Constraints

• 1\le N\le500
• 1\le W _ i\le500\ (1\le i\le N)
• 1\le H _ i\le10 ^ 9\ (1\le i\le N)
• 1\le B _ i\le10 ^ 9\ (1\le i\le N)
• All input values are integers.

Sample Input 1

3
1 41 59
2 65 35
8 97 93

Sample Output 1

217

By attaching type 1 and type 3 parts to the body and type 2 part to the head, the robot does not fall over and the sum of happiness can be made 217.

It is not possible to attach the parts without causing the robot to fall over and make the sum of happiness 218 or more, so print 217.

Sample Input 2

1
1 1000000000 1

Sample Output 2

1

The robot will fall over if the only part is not attached to the body. Note that it is acceptable to attach no parts to the head.

Sample Input 3

2
1 1000000000 1
1 1 1000000000

Sample Output 3

2000000000

Note that the robot does not fall over if the head and body have equal weights.

Sample Input 4

20
483 984529882 299667119
372 428935469 104847758
467 709733529 102461200
421 659244277 110859936
231 786224280 773073478
351 334234040 193222121
119 404159408 772024933
302 519596088 432627257
433 910226244 337833733
184 406236461 530198622
335 465203041 353047747
418 656273464 114923636
482 972364803 329650748
453 748321854 169441643
105 138464898 587159653
401 832952051 506021805
403 810916971 468755944
231 798801044 749313343
292 631278033 556088607
366 567211596 374825770

Sample Output 4

12091388792

Note that the answer can exceed 2 ^ {32}.

Problem Statement

There is a grid with H rows and W columns. We will refer to the cell at the i-th row from the top and j-th column from the left as cell (i,j). Each cell has at most one mirror placed on it.

Takahashi is standing on the left side of cell (1,1), and Aoki is standing on the right side of cell (H,W). Takahashi has a flashlight and is shining light from the left side of cell (1,1) toward the right. Here, assume that the flashlight's light does not diffuse and is a light ray that travels straight.

Takahashi's goal is to deliver the flashlight's light to Aoki by using the mirrors in the grid.

There are three types of mirror placements. When light hits a mirror, the direction of the light changes according to the mirror placement. For each mirror placement, the exit direction for each entry direction is as shown in the figures below.

• Type A (no mirror is placed)

• Type B (a mirror is placed on the diagonal connecting the upper-left and lower-right)

• Type C (a mirror is placed on the diagonal connecting the upper-right and lower-left)

The mirror placement on the grid is represented by H strings of length W: S_1,S_2,\ldots,S_H. When the j-th character of S_i is A, cell (i,j) is type A; when it is B, cell (i,j) is type B; when it is C, cell (i,j) is type C.

Takahashi can perform the following operation any number of times to deliver the light to Aoki:

• Choose one cell and change the mirror placement of that cell to a different type.

Find the minimum number of operations needed to deliver the light to Aoki.

You are given T test cases; find the answer for each.

Constraints

• 1\leq T
• 1\leq H,W
• HW\leq 2\times 10^5
• S_i is a string of length W consisting of A, B, C.
• T, H, and W are integers.
• The sum of HW over all test cases is at most 2\times 10^5.

Sample Input 1

4
3 4
ABCB
CACC
BCBA
2 2
CB
AA
1 10
BCBCBCBCBC
10 10
CCAABACAAA
CCCBACACCA
BACAABCBBA
ACCCAACCCA
CCAAAACCBA
AACBBACCAA
BCCCACBBAB
CBBCAACCCC
CBBCCBCBCA
BBACABBACC

Sample Output 1

0
2
10
5

For the first test case, the light can be delivered to Aoki without performing any operations.

For the second test case, by changing the mirror placement of cell (1,1) to type A and the mirror placement of cell (2,2) to type B, the light can be delivered to Aoki as shown in the figure below. It is impossible to deliver the light to Aoki with one or fewer operations, so the answer is 2.

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and a positive integer D.

Find the number, modulo 998244353, of integer sequences B=(B_1, B_2, \ldots, B_N) that can be obtained by rearranging A and satisfy the following condition:

• B_{i+1}\geq B_i-D holds for all i\ (1\leq i\leq N-1).

Constraints

• 2\leq N\leq 2\times 10^5
• 1\leq D\leq 10^6
• 1\leq A_i\leq 10^6
• All input values are integers.

Sample Input 1

4 1
5 2 1 2

Sample Output 1

3

The integer sequences satisfying the condition are (1,2,2,5),(2,1,2,5),(2,2,1,5), which are three sequences.

Sample Input 2

5 10
20 40 60 80 100

Sample Output 2

1

Sample Input 3

15 12345
18270 31252 27543 31406 22271 13402 12279 25697 18349 27615 39360 22790 32581 23990 36154

Sample Output 3

858152905

Problem Statement

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

For a pair of integers (l, r) \ (1\leq l\lt r\leq N), let f(l,r) be the integer sequence obtained by swapping the l-th element and the r-th element of A.

Generate a sequence of integer sequences B=(B_1,B_2,\ldots,B_{\frac{N(N-1)}{2}}) of length \frac{N(N-1)}{2} by the following procedure:

• Prepare an empty sequence B=().
• For each pair of integers (l, r)\ (1\leq l\lt r\leq N), add f(l,r) to B.
• Sort B in lexicographical order of sequences.

You are given Q queries; process them in order. The i-th query is as follows:

• Given an integer k, find one pair of integers (l, r) \ (1\leq l\lt r\leq N) such that B_k=f(l,r) and output it.

Constraints

• 2\leq N\leq 2\times 10^5
• 1\leq Q\leq 2\times 10^5
• 1\leq A_i\leq N
• 1\leq k\leq \frac{N(N-1)}{2}
• All input values are integers.

Sample Input 1

4 3
1 2 1 2
1
3
5

Sample Output 1

2 3
2 4
1 2

f(1, 2) = (2, 1, 1, 2), f(1, 3) = (1, 2, 1, 2), f(1, 4) = (2, 2, 1, 1), f(2, 3) = (1, 1, 2, 2), f(2, 4) = (1, 2, 1, 2), f(3, 4) = (1, 2, 2, 1).

The sequence B obtained by sorting these six sequences in lexicographical order is B=((1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 2, 1, 1)).

• For the 1-st query, the only (l,r) such that B_1=(1,1,2,2)=f(l,r) is (l,r)=(2,3).
• For the 2-nd query, (l,r) such that B_3=(1,2,1,2)=f(l,r) are (l,r)=(1,3),(2,4). In this case, either one will be considered correct.
• For the 3-rd query, the only (l,r) such that B_5=(2,1,1,2)=f(l,r) is (l,r)=(1,2).

Sample Input 2

10 10
1 1 2 7 6 3 5 7 3 3
21
36
9
17
13
24
7
45
33
1

Sample Output 2

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