Problem Statement

You are given an integer X between 1 and 3, inclusive.

Output an integer between 1 and 3, inclusive, that is different from X.

Constraints

• X is an integer between 1 and 3, inclusive.

Sample Input 1

1

Sample Output 1

2

The integers between 1 and 3, inclusive, that are different from X(=1) are 2 and 3.

Thus, outputing either 2 or 3 will be accepted.

Sample Input 2

2

Sample Output 2

3

Sample Input 3

3

Sample Output 3

2

Problem Statement

There is a movie theater with N seats numbered 1 through N, and one customer is sitting in each seat.
As a measure against congestion, this theater has customers leave according to the following rule.

• Divide the customers into groups of 10 people each, in increasing order of the seat number they are sitting in.
• The groups leave in order, starting from the group consisting of customers with the smallest seat numbers. Customers within the same group may leave in any order.

Here, the last group may have fewer than 10 customers.

The customer who left i-th was the one sitting in seat P_i.
Determine whether the N customers left according to the rule.

Constraints

• 10 \leq N \leq 100
• (P_1,P_2,\dots,P_N) is a permutation of (1,2,\dots,N).
• All input values are integers.

Sample Input 1

25
1 6 5 7 8 10 2 4 3 9 15 17 12 11 19 20 18 13 14 16 21 23 24 22 25

Sample Output 1

Yes

The 25 customers were divided into three groups, with seat numbers 1 to 10, 11 to 20, and 21 to 25.
First, the 10 customers in the first group, with seat numbers 1 to 10, left.
Next, the 10 customers in the second group, with seat numbers 11 to 20, left.
Finally, the 5 customers in the third group, with seat numbers 21 to 25, left.
Thus, the 25 customers left according to the rule.

Sample Input 2

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

Sample Output 2

No

Problem Statement

You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).
For q=1,2,\dots,Q in this order, perform the following operation.

• Remove the element with value a_q from P, and append it to the end of P.

Find the value of each element of P after performing the Q operations.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• (P_1,P_2,\dots,P_N) is a permutation of (1,2,\dots,N).
• 1 \leq a_q \leq N
• All input values are integers.

Sample Input 1

4 2
2 4 3 1
3
2

Sample Output 1

4 1 3 2

Initially, P=(2,4,3,1).
After the first operation, P=(2,4,1,3).
After the second operation, P=(4,1,3,2).

Sample Input 2

3 3
1 2 3
1
1
1

Sample Output 2

2 3 1

Sample Input 3

2 5
2 1
1
1
2
2
1

Sample Output 3

2 1

Problem Statement

There are N types of stones, 1,2,\dots,N. Stones of the same type all have the same weight.
Takahashi and Aoki have A_i and B_i stones of type i, respectively.
Determine whether there exists a sequence of positive integers W=(W_1,W_2,\dots,W_N) satisfying the following conditions, and if it exists, construct one such sequence.

• 1 \leq W_i \leq 10^{18}
• If the weight of a type-i stone is W_i, the total weight of the stones Takahashi has is strictly greater than the total weight of the stones Aoki has.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All input values are integers.

Sample Input 1

3
4 7 4
5 5 5

Sample Output 1

Yes
4 7 4

If W=(4,7,4),
the total weight of the stones Takahashi has is 4 \times 4 + 7 \times 7 + 4 \times 4=81.
The total weight of the stones Aoki has is 4 \times 5 + 7 \times 5 + 4 \times 5=75.

Sample Input 2

3
3 3 3
4 7 4

Sample Output 2

No

Sample Input 3

1
2
2

Sample Output 3

No

Problem Statement

A certain shop sells N types of products. Each product can be purchased any number of times.

The i-th type of product (1\le i\le N) can be bought in the following two ways:

• Buy it for A_i yen without using a coupon, and receive one coupon.
• Use one coupon and buy it for B_i yen.

Initially, you have no coupons.

Find the minimum amount of money required to buy every product at least once.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 2\times 10^5
• 1\le N\le 2\times 10^5
• 1\le B_i < A_i \le 10^9
• The sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

3
5
11 6
6 5
2 1
8 3
7 4
4
5 1
5 2
5 3
5 4
6
24 13
24 2
50 12
35 25
28 26
10 1

Sample Output 1

23
13
100

Consider the first test case.

For example, by acting as follows, you can buy every product at least once for 23 yen:

• Buy the second type of product for 6 yen without using a coupon. You now have 1 coupon.
• Buy the third type of product for 2 yen without using a coupon. You now have 2 coupons.
• Buy the third type of product for 2 yen without using a coupon. You now have 3 coupons.
• Use a coupon to buy the first type of product for 6 yen. You now have 2 coupons.
• Use a coupon to buy the fourth type of product for 3 yen. You now have 1 coupon.
• Use a coupon to buy the fifth type of product for 4 yen. You now have 0 coupons.

It is impossible to buy every product at least once for less than 23 yen, so output 23 on the first line.

Problem Statement

You are given a length-N integer sequence A=(A_1,A_2,\dots,A_N).
You can perform the following operation on A any number of times.

• Choose an integer i with 1 \leq i \leq N. For every integer j that is a positive divisor of i, add 1 to A_j.

Determine whether it is possible to make all elements of A equal, and if it is possible, find the minimum number of operations required to do so.

Constraints

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

Sample Input 1

3
4 7 4

Sample Output 1

3

If you choose i=3 for the first operation, you get A=(5,7,5).
If you choose i=3 for the second operation, you get A=(6,7,6).
If you choose i=3 for the third operation, you get A=(7,7,7).
It is impossible to make all elements of A equal with fewer than three operations, so the answer is 3.

Sample Input 2

5
1 3 4 5 6

Sample Output 2

5

Sample Input 3

2
5 2

Sample Output 3

-1

Problem Statement

You are given positive integers N and K.

There is an N\times N grid. The cell at the r-th row from the top and the c-th column from the left is denoted as cell (r,c).

Initially, a piece is placed on cell (1,1).

You will perform the following operation exactly N^2-1 times so that the piece ends up in cell (N,N):

• Move the piece one cell to a cell vertically or horizontally adjacent to the cell it is currently on.

Here, over the course of the movement, each of the N^2 cells must be visited exactly once. Cell (1,1), where the piece is initially placed, is considered visited.

Determine whether there exists a sequence of operations where the piece moves one cell to the right exactly K times, and if it exists, find one such sequence.

You are given T test cases; solve each of them.

Constraints

• 1\le T\le 5\times 10^3
• 2\le N\le 10^3
• 0\le K\le N^2-1
• The sum of N^2 over all test cases is at most 10^6.
• All input values are integers.

Sample Input 1

3
3 4
2 1
5 10

Sample Output 1

Yes
RRDLLDRR
No
Yes
RRRRDDDLLLURRULLLDDDRRRR

Consider the first test case.

By moving from cell (1,1) in order to cells (1,2),(1,3),(2,3),(2,2),(2,1),(3,1),(3,2),(3,3), you can move one cell to the right four times and reach cell (3,3).