Problem Statement

You are given three digits A,B,C between 1 and 9, inclusive.

Find the maximum value among all 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them.

Constraints

• A,B,C are digits between 1 and 9, inclusive.

Sample Input 1

3 2 4

Sample Output 1

432

There are six 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them: 324, 342, 234, 243, 432, 423; the maximum value among them is 432.

Sample Input 2

7 7 7

Sample Output 2

777

Only 777 can be formed.

Sample Input 3

9 1 9

Sample Output 3

991

Problem Statement

You are given integers A, B, C. If A \neq B and B = C, output Yes; otherwise, output No.

Constraints

• 1 \leq A, B, C \leq 9
• All input values are integers.

Sample Input 1

4 5 5

Sample Output 1

Yes

Since 4 \neq 5 and 5 = 5, output Yes.

Sample Input 2

1 3 7

Sample Output 2

No

Although 1 \neq 3, we don't have 3 = 7, so output No.

Sample Input 3

6 6 6

Sample Output 3

No

Problem Statement

There are N people, called Person 1, Person 2, \ldots, Person N.

The parent of Person i (2 \le i \le N) is Person P_i. Here, it is guaranteed that P_i < i.

How many generations away from Person N is Person 1?

Constraints

• 2 \le N \le 50
• 1 \le P_i < i(2 \le i \le N)
• All values in input are integers.

Sample Input 1

3
1 2

Sample Output 1

2

Person 2 is a parent of Person 3, and thus is one generation away from Person 3.

Person 1 is a parent of Person 2, and thus is two generations away from Person 3.

Therefore, the answer is 2.

Sample Input 2

10
1 2 3 4 5 6 7 8 9

Sample Output 2

9

Problem Statement

There is a parking lot. The fee for parking in this lot is as follows:

• During the period from exactly L o'clock to exactly R o'clock, a fee of X is charged for each hour parked.
• During the period not covered above, a fee of Y is charged for each hour parked.

If a car is parked in this lot from exactly A o'clock to exactly B o'clock without crossing midnight, how much is the fee?

Constraints

• 1 \leq X, Y \leq 1000
• 1 \leq L < R \leq 23
• 1 \leq A < B \leq 23
• All input values are integers.

Sample Input 1

700 300 9 17 7 21

Sample Output 1

7400

If a car is parked from 7 o'clock to 21 o'clock, the fee is as follows.

• For the 2 hours from 7 o'clock to 9 o'clock, a fee of 300 \times 2 = 600 is charged.
• For the 8 hours from 9 o'clock to 17 o'clock, a fee of 700 \times 8 = 5600 is charged.
• For the 4 hours from 17 o'clock to 21 o'clock, a fee of 300 \times 4 = 1200 is charged.

The answer is 600 + 5600 + 1200 = 7400.

Sample Input 2

600 500 9 17 17 20

Sample Output 2

1500

If a car is parked from 17 o'clock to 20 o'clock, the fee is as follows.

• For the 3 hours from 17 o'clock to 20 o'clock, a fee of 500 \times 3 = 1500 is charged.

The answer is 1500.

Sample Input 3

900 200 12 14 11 13

Sample Output 3

1100

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries in order. There are two types of queries, given in the following formats:

• 1 c: Perform the operation of moving the first element of A to the end c times.
• 2 l r: Output the value of \displaystyle \sum_{i=l}^r A_i.

Constraints

• 1\le N\le 2\times 10^5
• 1\le Q\le 2\times 10^5
• 1\le A_i \le 10^9
• 1\le c\le N
• 1\le l\le r \le N
• At least one query of the second type exists.
• All input values are integers.

Sample Input 1

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

Sample Output 1

8
9

Each query is processed as follows:

• First query: A_1+A_2+A_3=3+1+4=8, so output 8.
• Second query: A=(3,1,4,5) changes to A=(1,4,5,3).
• Third query: A_2+A_3=4+5=9, so output 9.

Sample Input 2

5 7
1 2 4 8 16
2 1 5
1 4
1 5
2 1 5
2 2 4
1 1
2 3 3

Sample Output 2

31
31
7
4

Problem Statement

AtCoder Restaurant was open for N days after opening.

On day i (1\leq i\leq N) after opening, the following actions were performed.

• In the morning of day i, A_i eggs are purchased.
• At noon on day i, B_i eggs are used. Here, eggs in stock are used in the order they were purchased.
• In the evening of day i, all eggs that have been stocked for D or more days are discarded.

There were no eggs in stock before the morning of day 1, and eggs never ran out at noon on any day.

Find how many eggs remain in the restaurant after the evening action on day N.

T test cases are given; solve each.

Constraints

• 1 \leq T\leq 2\times 10^5
• 1 \leq D \leq N \leq 2\times 10^5
• 1 \leq A_i,B_i \leq 10
• Eggs never run out at noon on any of the N days.
• For each input, the sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
5
0

In the first test case, the following actions are performed.

• Initially, AtCoder Restaurant has no eggs.
• In the morning of day 1, 7 eggs are purchased. The restaurant has 7 eggs stocked on day 1.
• At noon on day 1, 1 egg is used. The restaurant has 6 eggs stocked on day 1 remaining.
• In the evening of day 1, no eggs are discarded. The restaurant has 6 eggs stocked on day 1 remaining.
• In the morning of day 2, 2 eggs are purchased. The restaurant has 6 eggs stocked on day 1 and 2 eggs stocked on day 2.
• At noon on day 2, 3 eggs are used. The restaurant has 3 eggs stocked on day 1 and 2 eggs stocked on day 2 remaining.
• In the evening of day 2, the eggs stocked on day 1 are discarded. The restaurant has 2 eggs stocked on day 2 remaining.
• In the morning of day 3, 3 eggs are purchased. The restaurant has 2 eggs stocked on day 2 and 3 eggs stocked on day 3.
• At noon on day 3, 2 eggs are used. The restaurant has 3 eggs stocked on day 3 remaining.
• In the evening of day 3, no eggs are discarded. (This is because all eggs stocked on day 2 have already been used.) The restaurant has 3 eggs stocked on day 3 remaining.

Thus, 3 eggs remain after the evening action on day 3, so output 3 on the first line.

For the second test case, remember to output the number of eggs after discarding the eggs stocked on day 1 in the evening of day 3.

Problem Statement

A shop sells N kinds of lunchboxes, one for each kind.
For each i = 1, 2, \ldots, N, the i-th kind of lunchbox contains A_i takoyaki (octopus balls) and B_i taiyaki (fish-shaped cakes).

Takahashi wants to eat X or more takoyaki and Y or more taiyaki.
Determine whether it is possible to buy some number of lunchboxes to get at least X takoyaki and at least Y taiyaki. If it is possible, find the minimum number of lunchboxes that Takahashi must buy to get them.

Note that just one lunchbox is in stock for each kind; you cannot buy two or more lunchboxes of the same kind.

Constraints

• 1 \leq N \leq 300
• 1 \leq X, Y \leq 300
• 1 \leq A_i, B_i \leq 300
• All values in input are integers.

Sample Input 1

3
5 6
2 1
3 4
2 3

Sample Output 1

2

He wants to eat 5 or more takoyaki and 6 or more taiyaki.
Buying the second and third lunchboxes will get him 3 + 2 = 5 taiyaki and 4 + 3 = 7 taiyaki.

Sample Input 2

3
8 8
3 4
2 3
2 1

Sample Output 2

-1

Even if he is to buy every lunchbox, it is impossible to get at least 8 takoyaki and at least 8 taiyaki.
Thus, print -1.

Problem Statement

The digit sum of a positive integer n is defined as the sum of its digits when n is written in decimal. For example, the digit sum of 2025 is 2 + 0 + 2 + 5 = 9.
A positive integer n is called a good integer if it is divisible by its digit sum. For example, 2025 is a good integer because it is divisible by its digit sum of 9.
A pair of positive integers (a, a+1) is called twin good integers if both a and a+1 are good integers. For example, (2024, 2025) is twin good integers.

You are given a positive integer N. Find a pair of twin good integers (a, a + 1) such that N \leq a and a + 1 \leq 2N. If no such pair exists, report that fact.

Constraints

• N is an integer at least 1 and less than 10^{100000}.

Sample Input 1

5

Sample Output 1

8

(8, 9) is a valid pair of twin good integers satisfying the conditions. Other examples include (5, 6), (6, 7), (7, 8), (9, 10).

Sample Input 2

21

Sample Output 2

-1

No pair of twin good integers satisfies the conditions.

Sample Input 3

1234

Sample Output 3

2024

(2024, 2025) is a valid pair of twin good integers.

Sample Input 4

1234567890123456789012345678901234567890

Sample Output 4

1548651852734633803438094164372911259190

Problem Statement

ABC 250 is a commemorable quarter milestone for Takahashi, who aims to hold ABC 1000, so he is going to celebrate this contest by eating as close to 1/4 of a pizza he bought as possible.

The pizza that Takahashi bought has a planar shape of convex N-gon. When the pizza is placed on an xy-plane, the i-th vertex has coordinates (X_i, Y_i).

Takahashi has decided to cut and eat the pizza as follows.

• First, Takahashi chooses two non-adjacent vertices from the vertices of the pizza and makes a cut with a knife along the line passing through those two points, dividing the pizza into two pieces.
• Then, he chooses one of the pieces at his choice and eats it.

Let a be the quarter (=1/4) of the area of the pizza that Takahashi bought, and b be the area of the piece of pizza that Takahashi eats. Find the minimum possible value of 8 \times |a-b|. We can prove that this value is always an integer.

Constraints

• All values in input are integers.
• 4 \le N \le 10^5
• |X_i|, |Y_i| \le 4 \times 10^8
• The given points are the vertices of a convex N-gon in the counterclockwise order.

Sample Input 1

5
3 0
2 3
-1 3
-3 1
-1 -1

Sample Output 1

1

Suppose that he makes a cut along the line passing through the 3-rd and the 5-th vertex and eats the piece containing the 4-th vertex.
Then, a=\frac{33}{2} \times \frac{1}{4} = \frac{33}{8}, b=4, and 8 \times |a-b|=1, which is minimum possible.

Sample Input 2

4
400000000 400000000
-400000000 400000000
-400000000 -400000000
400000000 -400000000

Sample Output 2

1280000000000000000

Sample Input 3

6
-816 222
-801 -757
-165 -411
733 131
835 711
-374 979

Sample Output 3

157889