Problem Statement

You are given a length-N integer sequence A=(A_1,A_2,\dots,A_N) and an integer X.
For i=1,2,\dots,N in this order, do the following.

• If A_i<X, update X=A_i and output 1.
• Otherwise, output 0.

Constraints

• All input values are integers.
• 1 \le N,X,A_i \le 100

Sample Input 1

5 10
6 4 7 1 3

Sample Output 1

1
1
0
1
0

• Initially, X=10.
• For i=1: since A_1=6<X=10, update X=6 and output 1.
• For i=2: since A_2=4<X=6, update X=4 and output 1.
• For i=3: since A_3=7 \ge X=4, output 0.
• For i=4: since A_4=1<X=4, update X=1 and output 1.
• For i=5: since A_5=3 \ge X=1, output 0.

Sample Input 2

1 1
1

Sample Output 2

0

Sample Input 3

8 20
9 19 14 17 17 4 18 4

Sample Output 3

1
0
0
0
0
1
0
0

Problem Statement

Takahashi loves pepper.

A restaurant has M types of pepper, called type 1,2,\dots,M. There are C_j grams of type j (1 \le j \le M) pepper at this restaurant.

He ordered N dishes at this restaurant.
Due to compatibility, only type A_i pepper can be sprinkled on dish i (1 \le i \le N), and the upper limit on the amount of pepper that can be sprinkled on dish i is B_i grams.
Also, he can only use the pepper available at the restaurant. That is, the total amount of type j pepper sprinkled cannot exceed C_j grams.

He decides how much pepper to sprinkle on each dish to maximize the total amount of pepper sprinkled on the dishes.
How many grams of pepper in total can he sprinkle on the dishes?

Constraints

• All input values are integers.
• 1 \le N,M \le 1000
• 1 \le A_i \le M
• 1 \le B_i,C_i \le 10^6

Sample Input 1

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

Sample Output 1

15

In this input, there are five types of pepper, with 4,4,8,3,7 grams of type 1,2,3,4,5 pepper respectively.
The following gives a total of 15 grams of pepper sprinkled on the dishes, which is the maximum achievable.

• Sprinkle 2 grams of type 1 pepper on dish 1.
• Sprinkle no pepper on dish 2.
• Sprinkle 2 grams of type 5 pepper on dish 3.
• Sprinkle 3 grams of type 4 pepper on dish 4.
• Sprinkle 1 gram of type 2 pepper on dish 5.
• Sprinkle 4 grams of type 5 pepper on dish 6.
• Sprinkle 3 grams of type 2 pepper on dish 7.

Sample Input 2

1 1
1
1 1

Sample Output 2

1

Sample Input 3

15 10
7 94 100 82 63 81 75 2 76 73
10 44
5 77
10 47
7 32
2 82
5 90
3 37
6 70
6 28
3 25
2 26
10 56
1 69
5 46
7 26

Sample Output 3

438

Problem Statement

A bag contains N balls numbered 1 to N. Ball i has the integer A_i written on it.
Process Q queries.
For each query, a sequence B_1, B_2, \dots, B_{K} of length K is given, and you should perform the following sequence of operations. Here, all B_i are between 1 and N inclusive and are distinct.

• First, remove balls B_1, B_2, \dots, B_K from the bag.
• Then, output the minimum value among the integers written on the balls currently in the bag. (It is guaranteed by the constraints that the bag is not empty at this point.)
• Afterwards, return all K removed balls to the bag.

Constraints

• 6 \leq N \leq 3 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq K \leq 5
• 1 \leq B_1 \lt B_2 \lt \dots \lt B_K \leq N
• The sum of K over all queries is at most 4 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
1
3
5
2
1

For example, in the first query, balls 4 and 5 are removed from the bag. At this point, the following four balls remain in the bag:

• Ball 1 with 3 written on it
• Ball 2 with 2 written on it
• Ball 3 with 5 written on it
• Ball 6 with 2 written on it

Thus, the minimum value among the integers written on the balls in the bag is 2.

Problem Statement

You are given a tree with N vertices numbered 1,2,\dots,N. The i-th edge connects vertices U_i and V_i.
Each vertex i has an integer A_i written on it.

Answer the following problem for all k=1,2,\dots,N.

• Problem: Among the vertices on the simple path (a path that does not visit the same vertex more than once) from vertex 1 to vertex k, if there exist two distinct vertices with the same integer written on them, output Yes; otherwise, output No.
  • It can be proved that the simple path connecting two vertices on a tree is unique.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 1 \le U_i, V_i \le N
• The given graph is a tree.

Sample Input 1

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

Sample Output 1

No
No
No
Yes
Yes

• For k=1: the path from vertex 1 to vertex 1 contains only vertex 1. Since the path consists of only one vertex, the answer is No.
• For k=2: the path from vertex 1 to vertex 2 contains vertices 1,2, with integers 1,3 written on them respectively. Thus, the answer is No.
• For k=3: the path from vertex 1 to vertex 3 contains vertices 1,3, with integers 1,2 written on them respectively. Thus, the answer is No.
• For k=4: the path from vertex 1 to vertex 4 contains vertices 1,3,4, with integers 1,2,1 written on them respectively. Since vertices 1 and 4 on the path have the same integer 1 written on them, the answer is Yes.
• For k=5: the path from vertex 1 to vertex 5 contains vertices 1,3,5, with integers 1,2,2 written on them respectively. Since vertices 3 and 5 on the path have the same integer 2 written on them, the answer is Yes.

Sample Input 2

2
1000000000 1000000000
2 1

Sample Output 2

No
Yes

Sample Input 3

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

Sample Output 3

No
Yes
Yes
Yes
Yes
No
No
No
No
Yes

Problem Statement

You are given integers N and M. Find the remainder when \lfloor N/M \rfloor is divided by \color{red}{10007}.
Here, \lfloor x \rfloor denotes the largest integer not exceeding x. For example, \lfloor 3.14 \rfloor=3 and \lfloor 10 \rfloor = 10.

In this problem, N is not given directly; instead, it is given in run-length encoded form.
Specifically, N is represented by a sequence of K pairs of a digit c_i and an integer l_i.
To recover the original N, use the following procedure.

• Initially, let string S be the empty string.
• For i=1,2,\dots,K, repeat the following.
  • Append l_i copies of digit c_i to the end of S.
• Interpret the final S as a single integer; that integer is N.

Constraints

• 1 \le M \le 10^4
• 1 \le K \le 10^5
• c_i is one of the digits 0,1,2,3,4,5,6,7,8,9.
• 1 \le l_i \le 10^9
• c_1 \neq 0
• M,K,l_i are integers.

Sample Input 1

6 7
3 1
1 1
6 1
2 2
7 2
6 2

Sample Output 1

3797

In this input, N=316227766 and M=7.
\lfloor 316227766/7 \rfloor = 45175395, and the remainder when this is divided by 10007 is 3797, which is the final answer.

Sample Input 2

1 1
1 1

Sample Output 2

1

Sample Input 3

10 9999
9 419921892
9 923650333
6 476449815
1 8837775
2 141135534
5 462618481
3 202652735
0 771538044
4 321458589
0 570032864

Sample Output 3

8437

Problem Statement

There are N locations numbered 1 to N on a two-dimensional plane. Location i is at coordinates (X_i, Y_i).
You will start from location 1, visit every location exactly once, and return to location 1.
Moving from location i to location j takes \vert X_i - X_j \vert + \vert Y_i - Y_j \vert seconds.
Output a route that visits all locations and returns to location 1 within 10^{10} seconds of starting from location 1. It is guaranteed that at least one such route exists under the given constraints.

Constraints

• 1 \leq N \leq 6 \times 10^4
• 0 \leq X_i \leq 2 \times 10^7
• 0 \leq Y_i \leq 2 \times 10^7
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j
• All input values are integers.

Sample Input 1

3
0 6
3 5
2 4

Sample Output 1

1 3 2

\displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1}) = 4 + 2 + 4 = 10, so the output satisfies the condition.

Sample Input 2

10
9706344 19786176
19341349 15565412
5711023 19068083
12521132 14054301
14767612 17088029
14961700 18526945
13801766 5740101
6581153 8643675
13176196 16586661
4086263 5172719

Sample Output 2

1 5 2 6 4 7 9 8 3 10

Problem Statement

Takahashi and Aoki play a card game. The game proceeds according to the following rules.

• Takahashi presents decks A_1, A_2, \dots, A_N. Here N \geq 3.
• Aoki presents decks B_1, B_2, B_3.
• Takahashi chooses one deck from Aoki's decks and bans it. Aoki also chooses one deck from Takahashi's decks and bans it. These two ban operations are performed simultaneously. (That is, neither player can act based on the other's choice.)
• Then, Takahashi and Aoki each simultaneously declare which deck from their own presented decks they will use. However, the banned deck cannot be declared.
• Then, the two players battle exactly once using their declared decks. As a result, one of them wins.

You are given integers X_{i,j} (1 \leq i \leq N, 1 \leq j \leq 3). Let p_{i,j} = \dfrac{X_{i,j}}{10^6}. p_{i,j} is Takahashi's win rate when Takahashi uses deck A_i and Aoki uses deck B_j. Both Takahashi and Aoki know the values of p_{i,j} in advance.
Find Takahashi's win rate when both players act to maximize their own win rate.

T test cases are given; solve each of them.

Constraints

• 1 \leq T \leq 500
• 3 \leq N \leq 5 \times 10^4
• 0 \leq X_{i,j} \leq 10^6
• The sum of N over all test cases is at most 5 \times 10^4.
• All input values are integers.

Sample Input 1

1
3
600000 500000 100000
400000 700000 300000
800000 200000 900000

Sample Output 1

0.5272727272727272

Takahashi's win rate when both players act to maximize their own win rate is 0.5272727 \cdots.

Sample Input 2

3
6
402522 269943 705465
529104 292257 262398
598965 708517 393767
10680 760196 459175
163269 555933 100458
252724 762224 143581
4
720086 398924 165990
446155 678065 592893
674921 176800 484411
222632 81476 633357
5
212176 543920 484352
23874 760886 95861
291354 504948 790821
523486 327166 289413
621589 178581 628701

Sample Output 2

0.5136657634439492
0.5120053615937050
0.5396248345565982

Sample Input 3

6
3
600000 300000 100000
0 400000 600000
700000 400000 100000
3
700000 700000 200000
0 0 900000
500000 600000 900000
5
1000000 658525 1000000
867635 1000000 259903
727305 342912 1000000
995128 432824 1000000
69492 105991 1000000
6
900000 700000 300000
600000 300000 500000
900000 100000 900000
900000 1000000 0
800000 200000 900000
700000 800000 900000
7
300000 900000 800000
600000 1000000 700000
700000 200000 1000000
1000000 200000 200000
200000 400000 1000000
500000 800000 900000
900000 500000 800000
5
500000 500000 41274
270488 520436 605863
247128 522516 149943
502751 491747 516407
503752 488744 31814

Sample Output 3

0.3520000000000000
0.5571428571428572
0.9951279999999999
0.8478260869565216
0.8336956521739129
0.4988562153245037