Problem Statement

You are given strings X and Y of length N each, consisting of A, B, and C.

Determine if it is possible to make X coincide with Y by performing the following three kinds of operations on X any number of times, possibly zero.

• Operation (1)：Choose a character C in X and replace it with A.
• Operation (2)：Choose a character C in X and replace it with B.
• Operation (3)：Choose a substring AB in X and replace it with BA. More formally, choose an i such that the i-th and (i+1)-th characters of X are A and B, respectively, and replace the former with B and the latter with A.

You have T test cases to solve.

Constraints

• 1\leq T\leq 2\times 10^5
• 1\leq N\leq 2\times 10^5
• Each of X and Y is a string of length N consisting of A, B, and C.
• The sum of N over the test cases in a single input is at most 2\times 10^5.

Sample Input 1

6
3 ABC ABC
1 C B
1 B C
2 AB BA
2 BA AB
3 CCB ABA

Sample Output 1

Yes
Yes
No
Yes
No
Yes

• For the first test case, you can perform the operations zero times to make X coincide with Y.
• For the second test case, you can perform Operation (2) once to make X coincide with Y.
• For the fourth test case, you can perform Operation (3) once to make X coincide with Y.
• For the sixth test case, you can perform Operations (1), (3), (1) in this order at appropriate positions, for example, to make X change as CCB → CAB → CBA → ABA and coincide with Y.

Sample Input 2

7
5 ABABA BABAB
5 ABCBC BBABA
5 CCCCC CBABC
5 BBAAA AAABB
5 AAABB BBAAA
5 ACACB BAACB
5 ACACB BBACA

Sample Output 2

No
Yes
Yes
No
Yes
Yes
No

Problem Statement

You are given an integer sequence A=(A_1,\ldots,A_N) and positive integers a, b, and c.

You can perform the following operation on this sequence any number of times, possibly zero.

• Choose an integer i such that 1\leq i\leq N. Replace A_i with A_i+1.

Your objective is to make the sequence A contain at least one multiple of a, at least one multiple of b, and at least one multiple of c. Find the minimum number of operations required to achieve this objective.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq a, b, c \leq 10^6
• 1\leq A_i\leq 10^{18}

Sample Input 1

3 3 4 5
8 9 11

Sample Output 1

2

You can perform the operation twice so that A = (8,10,12) to achieve the objective.

Sample Input 2

3 3 4 5
14 11 59

Sample Output 2

1

You can perform the operation once so that A = (14,11,60) to achieve the objective.

Sample Input 3

6 10 20 30
8 17 5 28 39 13

Sample Output 3

3

You can perform the operation three times so that A = (8,17,5,30,40,13) to achieve the objective.

Sample Input 4

1 999997 999998 999999
123456789123456789

Sample Output 4

876537210887543205

You can perform the operation 876537210887543205 times so that A = (999994000010999994) to achieve the objective.

Problem Statement

There is a grid with H rows and W columns.

This grid has H(W+1) vertical edges and W(H+1) horizontal edges, for a total of H(W+1) + W(H+1) (see also the figures at Sample Input/Output). Consider marking these edges by the following two kinds of operations.

• Operation (1): Choose a square whose left and upper edges are unmarked when performing this operation. Mark the left and upper edges of that square.
• Operation (2): Choose a square whose right and lower edges are unmarked when performing this operation. Mark the right and lower edges of that square.

Find the number, modulo 998244353, of possible sets of edges that are eventually marked when Operations (1) and (2) can be performed any number of times, possibly zero.

You have T test cases to solve.

Constraints

• 1\leq T\leq 2\times 10^5
• 1\leq H, W\leq 10^6

Sample Input 1

2
1 1
2 3

Sample Output 1

4
800

For the case (H, W)=(1,1), there are four possible sets of edges that are eventually marked, as shown below. The marked edges are drawn in bold.

For the case (H, W)=(2,3), the following sets of marked edges are possible:

On the other hand, the following sets of marked edges are impossible:

Sample Input 2

3
123 456
654 321
1000000 1000000

Sample Output 2

60549740
298307903
656009181

Problem Statement

You are given positive integers x_1, \ldots, x_N such that x_1 < \cdots < x_N, and positive integers y_1, \ldots, y_N.

Consider a tuple (M, L_1, R_1, \ldots, L_M, R_M) that satisfies all of the following conditions.

• M is a positive integer.
• For each j \ (1\leq j\leq M), L_j and R_j are integers such that L_j\leq R_j.
• For each i \ (1\leq i\leq N), exactly y_i integers j \ (1\leq j\leq M) satisfy L_j\leq x_i\leq R_j.

It can be proved that such a tuple always exists. Find the maximum value of \min \lbrace R_j-L_j\mid 1\leq j\leq M\rbrace for such a tuple. If there is no maximum value, print -1.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq x_1 < \cdots < x_N \leq 10^9
• 1\leq y_i \leq 10^9

Sample Input 1

3
1 3 5
1 3 1

Sample Output 1

2

For example, we have \min \lbrace R_j-L_j\mid 1\leq j\leq M\rbrace = 2 for the tuple (3, 1, 4, 2, 4, 3, 5).

Sample Input 2

3
1 10 100
2 3 2

Sample Output 2

-1

For example, we have \min \lbrace R_j-L_j\mid 1\leq j\leq M\rbrace = 990 for the tuple (3, -1000, 10, -1000, 1000, 10, 1000). There is no maximum value of \min \lbrace R_j-L_j\mid 1\leq j\leq M\rbrace.

Sample Input 3

7
10 31 47 55 68 73 90
3 7 4 6 3 4 4

Sample Output 3

56

Problem Statement

You are given positive integers n, a, and b such that a<b.

An integer pair (L,R) such that 1\leq L\leq R is said to be a good pair when the following condition holds.

• Let n_a and n_b be respectively the number of multiples of a and the number of multiples of b among the integers between L and R, inclusive. Then, n_a - n_b = n.

It can be proved that a good pair always exists. Report the good pair with the largest value of R-L. If multiple such pairs exist, report the one with the smallest L (from 1\leq L, the sought (L, R) with the smallest L exists and is unique).

You have T test cases to solve.

Constraints

• 1\leq T\leq 2\times 10^5
• 1\leq n \leq 10^6
• 1\leq a < b \leq 10^6

Sample Input 1

1
3 3 5

Sample Output 1

4 35

(L,R)=(4,35) is a good pair since n_a=10, n_b=7.

Some other good pairs are (1,26) and (10,41). (1,26) is not the answer because it does not have the largest R-L. (10,41) is not the answer because, although it has the largest R-L, it does not have the smallest L.

Sample Input 2

5
4 3 5
6 2 4
1 1 2
123 456 789
9876 54 321

Sample Output 2

10 50
3 29
2 4
5473 140447
163 641411

Problem Statement

You are given a prime number p and non-negative integers a and b.

Determine if there is an infinite sequence of non-negative integers t = \bigl(t(0), t(1), t(2), \ldots) that satisfies all of the following conditions.

• 0\leq t(x) < p for every non-negative integer x.
• t(x+y)\bigl(1-t(x)t(y)\bigr)\equiv t(x)+t(y)\pmod{p} for all non-negative integers x and y.
• t(a)=b.

You have T test cases to solve.

Constraints

• 1\leq T\leq 2\times 10^5
• p is a prime number such that 1\leq p\leq 10^9.
• 0\leq a\leq 10^{9}
• 0\leq b < p

Sample Input 1

4
11 1 0
11 1 1
11 1 3
11 1 5

Sample Output 1

Yes
No
No
Yes

• For p=11, a=1, b=0, a constant sequence t = (0,0,0,0,\ldots) satisfies the conditions.
• For p=11, a=1, b=5, a sequence t = (0,5,6,0,5,6,\ldots) of period 3 satisfies the conditions.

Sample Input 2

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

Sample Output 2

Yes
No
Yes
Yes
No

Sample Input 3

7
2 3 1
2 5 0
5 0 1
5 0 2
7 1 4
11 12345 5
13 12345 5

Sample Output 3

Yes
Yes
No
Yes
No
No
Yes