Problem Statement

You are given positive integers N and M.

If the following operation is repeated while the value of M is not 0, find the number of operations performed.

• Let x be the remainder when N is divided by M. Replace the value of M with x.

It can be proved that M becomes 0 after a finite number of operations.

Constraints

• 1 \leq N, M \leq 1000
• All input values are integers.

Sample Input 1

8 5

Sample Output 1

3

Initially, N = 8 and M = 5.

The remainder when 8 is divided by 5 is 3, so M = 3 after one operation.

The remainder when 8 is divided by 3 is 2, so M = 2 after two operations.

The remainder when 8 is divided by 2 is 0, so M = 0 after three operations.

Thus, output 3 as the answer.

Sample Input 2

14 6

Sample Output 2

2

Sample Input 3

460 33

Sample Output 3

5

Problem Statement

There are two circles C_1 and C_2 on the xy-plane. In this problem, a circle refers to the circumference.
Circle C_1 has its center at (X_1, Y_1) and radius R_1.
Circle C_2 has its center at (X_2, Y_2) and radius R_2.
Determine whether circles C_1 and C_2 have a common point. In other words, determine whether there exists at least one point whose distance from (X_1, Y_1) is R_1 and whose distance from (X_2, Y_2) is R_2.

You are given T test cases; solve each one.

Constraints

• 1 \leq T \leq 100
• 0 \leq X_1, Y_1, X_2, Y_2 \leq 10^9
• 1 \leq R_1, R_2 \leq 10^9
• All input values are integers.

Sample Input 1

7
0 0 2 2 3 2
0 0 2 2 3 1
1 2 5 3 2 1
5 4 2 8 8 3
2 1 5 5 1 2
0 0 1 0 0 1
0 0 500000000 1 1000000000 500000000

Sample Output 1

Yes
No
No
Yes
Yes
Yes
No

For example, in the first test case, the relative positions of C_1 and C_2 are as shown in the following figure.

Problem Statement

There are N pieces of shari (vinegared rice) and M pieces of neta (toppings) as ingredients for sushi.

The weight of the i-th shari is A_i, and the weight of the j-th neta is B_j.

You will make sushi by combining shari and neta.

To make one piece of sushi, you need to combine one shari with one neta. Here, the weight of the neta must be at most twice the weight of the shari. Also, the same shari or neta cannot be used in multiple pieces of sushi.

Find the maximum number of sushi that can be made.

Constraints

• 1 \leq N, M \leq 2 \times 10^5
• 1 \leq A_i, B_j \leq 10^9
• All input values are integers.

Sample Input 1

4 5
4 2 1 8
14 9 3 2 9

Sample Output 1

3

By combining the 1st shari with the 3rd neta, the 2nd shari with the 4th neta, and the 4th shari with the 1st neta, for example, you can make three pieces of sushi. It is impossible to make four or more pieces of sushi, so output 3.

Sample Input 2

3 3
5 5 3
11 1000 1000

Sample Output 2

0

Sample Input 3

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

Sample Output 3

5

Problem Statement

There is a grid with H rows and W columns. The cell at the i-th row from the top and the j-th column from the left is called cell (i, j).

Every cell is colored white or black. The grid is described by H strings S_1, S_2, \ldots, S_H, each of length W. If the j-th character of S_i is ., cell (i, j) is white; if the j-th character of S_i is #, cell (i, j) is black.

You perform the following operation 10^{100} times.

• Simultaneously apply the following rules to all cells.
  • A cell that is white before the operation becomes black if and only if there exists at least one black cell adjacent to it. Here, cells (x, y) and (x', y') are adjacent if and only if one of them is within the 8-neighborhood of the other, that is, \max(|x-x'|, |y-y'|) = 1.
  • A cell that is black before the operation becomes white.

Find the color of each cell after the operations.

Constraints

• 1 \leq H \times W \leq 10^6
• H and W are positive integers.
• S_i is a string of length W consisting of . and #.

Sample Input 1

3 4
#.#.
.#..
#...

Sample Output 1

#.#.
.#..
#..#

Initially, the grid is as follows.

After one operation, the grid is as follows.

After 10^{100} operations, the grid is as follows.

Sample Input 2

3 3
###
###
###

Sample Output 2

...
...
...

Sample Input 3

5 7
.#.....
.......
..#....
.......
....#..

Sample Output 3

.#.##.#
....#..
#.#.###
#.....#
###.#.#

Problem Statement

For positive integers a and b, define \mathrm{concat}(a, b) as the integer formed by writing a and b one after another. More formally, \mathrm{concat}(a, b) is defined as follows.

• Let A and B be the strings formed by writing a and b in decimal, respectively. Let C be the string formed by concatenating A and B in this order. The value of C interpreted as an integer in decimal notation is \mathrm{concat}(a, b).

For example, if a = 123 and b = 45, then \mathrm{concat}(a, b) = 12345.

You are given positive integers N and M.
Find the number, modulo 998244353, of pairs (x, y) of positive integers not greater than N such that \mathrm{concat}(x, y) \equiv x + y \pmod{M}.

You are given T test cases; solve each one.

Constraints

• 1 \leq T \leq 10^4
• 1 \leq N \leq 10^{18}
• 2 \leq M \leq 10^9
• All input values are integers.

Sample Input 1

4
3 2
123 456
20260530 460
123456789123456789 998244353

Sample Output 1

3
0
922576091
422081792

For the first test case, three pairs (x, y) satisfy the condition: (2, 1), (2, 2), (2, 3).

Problem Statement

There is a tree with N vertices. The vertices are numbered 1, 2, \ldots, N, and the i-th edge connects vertices U_i and V_i.

Initially, all vertices are painted black.

Process Q queries of the following form in order and find the answer for each query.

• An integer x (1 \leq x \leq N) is given. If vertex x is white, repaint it black; if vertex x is black, repaint it white. Then, find the maximum distance between two black vertices. Here, the distance between two vertices on a tree is the number of edges in the simple path between them.

In the given inputs, there are always at least two black vertices when processing the queries in order.

Constraints

• 3 \leq N \leq 10^5
• 1 \leq U_i, V_i \leq N
• The given graph is a tree.
• 1 \leq Q \leq 10^5
• For each query, 1 \leq x \leq N.
• There are always at least two black vertices.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4
3
3
2
2
3
2
3
4

• After the repainting in the 1st query, the black vertices are 2, 3, 4, 5, 6, 7. The distance between vertices 4 and 6 is 4, and the answer is 4.
• After the repainting in the 2nd query, the black vertices are 2, 3, 5, 6, 7. The distance between vertices 2 and 6 is 3, and the answer is 3.
• After the repainting in the 3rd query, the black vertices are 3, 5, 6, 7. The distance between vertices 5 and 6 is 3, and the answer is 3.
• After the repainting in the 4th query, the black vertices are 3, 5, 7. The distance between vertices 5 and 7 is 2, and the answer is 2.
• After the repainting in the 5th query, the black vertices are 5, 7. The distance between vertices 5 and 7 is 2, and the answer is 2.
• After the repainting in the 6th query, the black vertices are 1, 5, 7. The distance between vertices 1 and 5 is 3, and the answer is 3.
• After the repainting in the 7th query, the black vertices are 5, 7. The distance between vertices 5 and 7 is 2, and the answer is 2.
• After the repainting in the 8th query, the black vertices are 4, 5, 7. The distance between vertices 4 and 5 is 3, and the answer is 3.
• After the repainting in the 9th query, the black vertices are 4, 5, 6, 7. The distance between vertices 4 and 6 is 4, and the answer is 4.

Note that the examples given above are just one instance achieving the maximum value.

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge connects vertices a_i and b_i. Each vertex i has a weight W_i and a color C_i \in \lbrace 0,1 \rbrace.
Process Q queries. There are three types of queries as follows.

• 1 v: Change C_v to 1 - C_v for vertex v.
• 2 v x: Change W_v to W_v + x for vertex v.
• 3 v: Let c be the color of vertex v. Output the sum of weights of all vertices reachable from vertex v by traveling only through vertices of color c (including vertex v itself).

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9
• C_i \in \lbrace 0,1 \rbrace
• 1 \leq a_i \lt b_i \leq N
• The input graph is a tree.
• 1 \leq v \leq N
• 1 \leq x \leq 10^9
• All input values are integers.

Sample Input 1

5 9
1 10 100 1000 10000
0 0 0 0 0
1 2
2 3
3 4
2 5
3 1
1 2
3 1
3 2
3 3
1 3
1 2
2 1 1
3 5

Sample Output 1

11111
1
10
1100
10012

For example, for the first query, the set of vertices reachable from vertex 1 by traveling only through vertices of color 0 is \lbrace 1,2,3,4,5 \rbrace.

Sample Input 2

10 25
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
0 1 0 0 0 1 0 0 0 0
1 2
1 3
2 4
4 5
4 6
2 7
5 8
8 9
6 10
3 4
1 8
2 6 100000
3 3
1 3
1 7
1 7
1 7
3 8
2 1 1
2 6 100000
2 8 10000000
1 5
2 5 10000
1 9
2 7 1000000
1 7
2 10 1000000000
1 9
1 6
1 9
1 1
3 7
2 5 10000
3 6

Sample Output 2

110011000
101
10000000
2000000
2000301000