Problem Statement

1 foot is 12 inches.

How many inches is A feet B inches?

Constraints

• 1 \leq A \leq 8
• 0 \leq B \leq 11
• All input values are integers.

Sample Input 1

6 7

Sample Output 1

79

6 feet 7 inches is 6 \times 12 + 7 = 79 inches.

Sample Input 2

4 11

Sample Output 2

59

4 feet 11 inches is 4 \times 12 + 11 = 59 inches.

Sample Input 3

8 0

Sample Output 3

96

8 feet 0 inches is 8 \times 12 + 0 = 96 inches.

Problem Statement

There is a grid with H rows and W columns. Each square has one integer written on it, and these integers are distinct. The square at the i-th row from the top and j-th column from the left has the integer A_{i,j} written on it.

Now, the host called out N distinct integers B_1, \dots, B_N.

If you find, for each row, how many of the integers called out by the host are contained in that row, what is the maximum value among these?

Constraints

• 1 \leq H \leq 3
• 1 \leq W \leq 5
• 1 \leq N \leq 90
• 1 \leq A_{i,j} \leq 90
• A_{i,j} are distinct.
• 1 \leq B_i \leq 90
• B_i are distinct.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3

• Among the integers in the 1-st row from the top, 0 integers were called out by the host.
• Among the integers in the 2-nd row from the top, 3 integers 6,11,9 were called out by the host.
• Among the integers in the 3-rd row from the top, 2 integers 2,4 were called out by the host.

Thus, the answer is the maximum value among 0,3,2, which is 3.

Sample Input 2

3 5 2
81 63 31 16 15
30 3 6 54 24
26 41 48 64 66
44
79

Sample Output 2

0

Sample Input 3

3 5 12
78 19 70 58 83
12 30 80 20 27
48 71 8 43 82
82
30
43
8
80
70
20
78
12
71
19
48

Sample Output 3

5

Problem Statement

There are N reindeer and one sled. The i-th reindeer has weight W_i and strength P_i.

For each reindeer, choose either "pull the sled" or "ride on the sled". Here, the total strength of the reindeer pulling the sled must be greater than or equal to the total weight of the reindeer riding on the sled. What is the maximum number of reindeer that can ride on the sled?

You are given T test cases. Solve each of them.

Constraints

• 1\leq T\leq 10^5
• 1\leq N\leq 3\times 10^5
• 1\leq W_i,P_i\leq 10^9
• All input values are integers.
• The sum of N in one input file is at most 3\times 10^5.

Sample Input 1

3
3
3 1
4 1
5 9
5
1000000000 1
1000000000 1
1000000000 1
1000000000 1
1000000000 1
10
133180711 458704923
531424946 225863856
141986070 637075158
500770732 289806469
502866767 408857335
559714289 569084545
287444582 992432993
559747907 753133304
432846188 949871298
727072164 756020367

Sample Output 1

2
0
6

For the 1st test case, if the 3rd reindeer pulls the sled and the 1st and 2nd reindeer ride on the sled, the total strength of the reindeer pulling the sled is P_3=9, and the total weight of the reindeer riding on the sled is W_1+W_2=7, satisfying the condition. Since not all reindeer can ride on the sled, the answer is 2.

Problem Statement

You are given a length-N sequence of positive integers A = (A_1, A_2, \dots, A_N) and a length-M sequence of positive integers B = (B_1, B_2, \dots, B_M).

Find the value of \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} |A_i - B_j|, modulo 998244353.

Constraints

• 1 \leq N,M \leq 3 \times 10^5
• 1 \leq A_i, B_j < 998244353
• All input values are integers.

Sample Input 1

4 2
1 6 9 2
3 1

Sample Output 1

26

The answer is |1-3| + |1-1| + |6-3| + |6-1| + |9-3| + |9-1| + |2-3| + |2-1| = 2+0+3+5+6+8+1+1 = 26.

Sample Input 2

8 8
185991676 311812083 311812083 84357963 185991676 185991676 724020528 369175631
455049197 387671868 4361724 724020528 724020528 455049197 455049197 724020528

Sample Output 2

529117255

Problem Statement

There are N+1 sequences A_0, A_1, \ldots, A_{N}. A_i is defined as follows:

• A_0 is an empty sequence.
• A_i\ (1\leq i\leq N) is a sequence obtained by appending an integer y_i to the end of the sequence A_{x_i}\ (0\leq x_i\lt i).

Find the permutation P=(P_1, P_2,\ldots,P_N) of (1,2,\ldots,N) that satisfies the following condition:

• For i = 1,2,\ldots,N-1, one of the following holds:
  • A_{P_i} is lexicographically smaller than A_{P_{i+1}}.
  • A_{P_i}= A_{P_{i+1}} and P_i\lt P_{i+1}

In other words, when A_1,A_2,\ldots,A_N are arranged in lexicographical order (when there are multiple equal sequences, arrange those with smaller indices first), P is the sequence of indices that appears in that arrangement.

Constraints

• 1\leq N\leq 3\times 10^5
• 0\leq x_i\lt i
• 1\leq y_i\leq 10^9
• All input values are integers.

Sample Input 1

4
0 2
0 1
2 2
0 1

Sample Output 1

2 4 3 1

A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1), so P=(2,4,3,1).

Sample Input 2

5
0 1
0 1
0 1
0 1
0 1

Sample Output 2

1 2 3 4 5

A_1 = A_2 = A_3 = A_4 = A_5 = (1).

Sample Input 3

10
0 305186313
1 915059758
0 105282054
1 696409999
3 185928366
3 573289179
6 254538849
3 105282054
5 696409999
8 168629803

Sample Output 3

3 8 10 5 9 6 7 1 4 2

Problem Statement

There are N Christmas trees on a two-dimensional plane. The i-th (1\le i\le N) Christmas tree is located at coordinates (X_i,Y_i).

You are given Q queries. Process the queries in order. Each query is one of the following:

• Type 1 : Given in the form 1 i x y. Change the coordinates of the i-th Christmas tree to (x,y).
• Type 2 : Given in the form 2 L R x y. Output the Manhattan distance from the coordinates (x,y) to the farthest Christmas tree among the L,L+1,\ldots,R-th Christmas trees.

Here, the Manhattan distance between coordinates (x_1,y_1) and coordinates (x_2,y_2) is defined as |x_1-x_2|+|y_1-y_2|.

Constraints

• 1\le N,Q\le 2\times 10^5
• -10^9\le X_i,Y_i\le 10^9
• 1\le i\le N
• 1\le L\le R\le N
• -10^9\le x,y\le 10^9
• All input values are integers.

Sample Input 1

3 4
-1 -1
1 2
-2 1
2 1 2 0 0
2 1 3 -1 2
1 1 0 1
2 1 3 -1 2

Sample Output 1

3
3
2

Initially, the 1st, 2nd, 3rd Christmas trees are located at coordinates (-1,-1), (1,2), (-2,1), respectively.

Each query is processed as follows:

• The Manhattan distances from the 1st and 2nd Christmas trees to coordinates (0,0) are 2 and 3, respectively. Thus, output 3, which is the maximum value among 2,3.
• The Manhattan distances from the 1st, 2nd, 3rd Christmas trees to coordinates (-1,2) are 3, 2, 2, respectively. Thus, output 3, which is the maximum value among 3,2,2.
• Change the coordinates of the 1st Christmas tree to (0,1). The coordinates of the 1st, 2nd, 3rd Christmas trees become (0,1),(1,2),(-2,1), respectively.
• The Manhattan distances from the 1st, 2nd, 3rd Christmas trees to coordinates (-1,2) are 2, 2, 2, respectively. Thus, output 2, which is the maximum value among 2,2,2.

Sample Input 2

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

Sample Output 2

24
24
22
30
9

Problem Statement

The Christmas season this year is over, and it is finally time for the new year. Takahashi is busy with the big cleanup of putting away the Christmas tree.

There is a Christmas tree decorated with bulbs in three colors: red, blue, and green. The Christmas tree has N bulbs, and they are connected by N-1 ribbons. When viewing the bulbs as vertices and the ribbons as edges, this graph is a tree.

The bulbs are numbered from 1 to N, and the ribbons are numbered from 1 to N-1. Ribbon i connects bulbs u_i and v_i. Bulb i is initially lit in red if c_i is R, in green if it is G, and in blue if it is B.

Takahashi is considering performing the following operation N-1 times to remove all ribbons.

1. Choose one ribbon among those not yet removed where the bulbs at both ends have different colors, and remove that ribbon.
2. Let bulbs u and v be the bulbs at both ends of the removed ribbon. For each of the bulbs u and v, change the color they are lit in according to the following rule:
   • If it was lit in red, light it in green.
   • If it was lit in green, light it in blue.
   • If it was lit in blue, light it in red.

Determine whether it is possible for Takahashi to remove all ribbons by repeating this operation. If possible, output one such method.

You are given T test cases. Solve each of them.

Constraints

• 1\leq T\leq 20000
• 2\leq N\leq 2000
• c_i is R, G, or B.
• 1\leq u_i,v_i\leq N
• When viewing the bulbs as vertices and the ribbons as edges, the given graph is a tree.
• T,N,u_i,v_i are integers.
• The sum of N^2 in one input file is at most 2000^2.

Sample Input 1

3
4
GBBR
1 2
1 3
1 4
3
RRR
1 2
2 3
5
RGBRG
1 2
2 3
3 4
3 5

Sample Output 1

Yes
1 3 2
No
Yes
1 4 2 3

For the first test case, for example, all ribbons can be removed by performing the operations as follows:

• Initially, the colors of the bulbs are green, blue, blue, red, in order (from bulb 1).
• Remove ribbon 1. After removal, the colors of the bulbs are blue, red, blue, red, in order.
• Remove ribbon 3. After removal, the colors of the bulbs are red, red, blue, green, in order.
• Remove ribbon 2. After removal, the colors of the bulbs are green, red, red, green, in order.

The (e_1, e_2, e_3) satisfying the condition are (1, 3, 2) and (2, 3, 1), and either one will be accepted as correct.

For the second test case, it is impossible to remove all ribbons no matter how you perform the operations.