Problem Statement

A fruit store sells apples.
You may perform the following operations as many times as you want in any order:

• Buy one apple for X yen (the currency in Japan).
• Buy three apples for Y yen.

How much yen do you need to pay to obtain exactly N apples?

Constraints

• 1 \leq X \leq Y \leq 100
• 1 \leq N \leq 100
• All values in input are integers.

Sample Input 1

10 25 10

Sample Output 1

85

Buy three apples for 25 yen three times and one apple for 10 yen, and you will obtain exactly 10 apples for a total of 85 yen.
You cannot obtain exactly 10 apples for a lower cost, so the answer is 85 yen.

Sample Input 2

10 40 10

Sample Output 2

100

It is optimal to buy an apple for 10 yen 10 times.

Sample Input 3

100 100 2

Sample Output 3

200

The only way to obtain exactly 2 apples is to buy an apple for 100 yen twice.

Sample Input 4

100 100 100

Sample Output 4

3400

Problem Statement

There is a triangle ABC with positive area.
The lengths of the three sides of triangle ABC are a,b,c.

Determine whether triangle ABC is isosceles.

Constraints

• 1 \leq a,b,c \leq 10
• A triangle with side lengths a,b,c exists, and its area is positive.
• a,b,c are integers.

Sample Input 1

4 2 4

Sample Output 1

Yes

Since a=c, triangle ABC is isosceles. Thus, output Yes.

Sample Input 2

3 4 5

Sample Output 2

No

Since the three side lengths of triangle ABC are all different, it is not isosceles. Thus, output No.

Sample Input 3

10 10 10

Sample Output 3

Yes

Note that an equilateral triangle is a kind of isosceles triangle.

Problem Statement

There are N people standing in a row from left to right. The i-th person from the left (1\le i\le N) is called person i. The height of person i (1\le i\le N) is A_i.

For each i=1,2,\ldots,N, determine whether there exists a person to the left of person i who is taller than person i, and if so, find the person standing closest to person i among them.

Constraints

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

Sample Input 1

4
4 3 2 5

Sample Output 1

-1
1
2
-1

• There is no person to the left of person 1. Thus, output -1 on the first line.
• Among the people to the left of person 2, only person 1 is taller than person 2. Thus, output 1 on the second line.
• Among the people to the left of person 3, persons 1,2 are taller than person 3, and the person standing closest to person 3 is person 2. Thus, output 2 on the third line.
• There is no person to the left of person 4 who is taller than person 4. Thus, output -1 on the fourth line.

Sample Input 2

3
7 7 7

Sample Output 2

-1
-1
-1

There may be multiple people with the same height.

Sample Input 3

6
31 9 17 10 2 9

Sample Output 3

-1
1
1
3
4
4

Problem Statement

There are N birds of M types flying in the sky.
The bird types are numbered 1,2,\dots,M.
The N birds are numbered 1,2,\dots,N, and bird i is of type A_i and has size B_i.

For every k=1,2,\dots,M, find the average size of the flying birds of type k.
It is guaranteed that for every k=1,2,\dots,M, there is at least one bird of type k flying.

Constraints

• 1 \le M \le N \le 100
• 1 \le A_i \le M
• 1 \le B_i \le 100
• There exists at least one bird of type k ( 1 \le k \le M ).
• All input values are integers.

Sample Input 1

10 5
4 92
1 16
3 77
4 99
2 89
3 8
1 40
5 56
1 40
4 77

Sample Output 1

32.00000000000000000000
89.00000000000000000000
42.50000000000000000000
89.33333333333333333333
56.00000000000000000000

• The average size of birds of type 1 is (16+40+40)/3 = 32.
• The average size of birds of type 2 is 89.
• The average size of birds of type 3 is (77+8)/2 = 42.5.
• The average size of birds of type 4 is (92+99+77)/3 \approx 89.3333.
• The average size of birds of type 5 is 56.

Problem Statement

There is a 9\times 9 grid A, where each cell contains an integer between 1 and 9, inclusive.
Specifically, the cell at the i-th row from the top and j-th column from the left contains A_{i,j}.

If A satisfies all of the following conditions, print Yes. Otherwise, print No.

• For each row of A, the nine cells in that row contain each integer from 1 to 9 exactly once.
• For each column of A, the nine cells in that column contain each integer from 1 to 9 exactly once.
• Divide the rows of A into three groups, each of three rows, from top to bottom, and similarly divide the columns into three groups, each of three columns, from left to right. Each 3\times 3 grid obtained from A in this way contains each integer from 1 to 9 exactly once.

Constraints

• 1\leq A_{i,j}\leq 9
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

The grid A is shown below.

The grid A satisfies all three conditions, so print Yes.

Sample Input 2

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

Sample Output 2

No

The grid A is shown below.

For example, if you look at the top left 3\times 3 grid, you can see that the third condition is unsatisfied, so print No.

Sample Input 3

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

Sample Output 3

No

The grid A is shown below.

For example, if you look at the leftmost column, you can see that the second condition is unsatisfied, so print No.

Problem Statement

Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.

• The i-th element is between 1 and R_i, inclusive.
• The sum of all elements is a multiple of K.

Constraints

• All input values are integers.
• 1 \le N \le 8
• 2 \le K \le 10
• 1 \le R_i \le 5

Sample Input 1

3 2
2 1 3

Sample Output 1

1 1 2
2 1 1
2 1 3

There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.

Sample Input 2

1 2
1

Sample Output 2

There may be no sequences to print.
In this case, the output can be empty.

Sample Input 3

5 5
2 3 2 3 2

Sample Output 3

1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1

Problem Statement

We have an empty sequence A.
Given Q queries, process them in order.
Each query is of one of the following three types.

• 1 x : Insert x to A.

• 2 x k : Among the elements of A that are less than or equal to x, print the k-th largest value. (k is no more than \bf{5})
  If there are less than k elements of A that are less than or equal to x, then print -1.

• 3 x k : Among the elements of A that are greater than or equal to x, print the k-th smallest value. (k is no more than \bf{5})
  If there are less than k elements of A that are greater than or equal to x, then print -1.

Constraints

• 1\leq Q \leq 2\times 10^5
• 1\leq x\leq 10^{18}
• 1\leq k\leq 5
• All values in input are integers.

Sample Input 1

11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5

Sample Output 1

20
20
30
-1
-1
1

After \text{query}_{1,2,3,4} have been processed, we have A=(20,10,30,20).

For \text{query}_{5,6,7}, the elements of A greater than or equal to 15 are (20,30,20).
The 1-st smallest value of them is 20; the 2-nd is 20; the 3-rd is 30.

Problem Statement

We have an empty sequence A. You will be given Q queries, which should be processed in the order they are given. Each query is of one of the three kinds below:

• 1 x : Append x to the end of A.
• 2 : Print the element at the beginning of A. Then, delete that element. It is guaranteed that A will not empty when this query is given.
• 3 : Sort A in ascending order.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• 0 \leq x \leq 10^9
• A will not be empty when a query 2 is given.
• All values in input are integers.

Sample Input 1

8
1 4
1 3
1 2
1 1
3
2
1 0
2

Sample Output 1

1
2

The i-th line below shows the contents of A after the i-th query is processed in Sample Input 1.

• (4)
• (4, 3)
• (4, 3, 2)
• (4, 3, 2, 1)
• (1, 2, 3, 4)
• (2, 3, 4)
• (2, 3, 4, 0)
• (3, 4, 0)

Sample Input 2

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

Sample Output 2

5
3
5

The i-th line below shows the contents of A after the i-th query is processed in Sample Input 2.

• (5)
• (5, 5)
• (5, 5, 3)
• (5, 3)
• (3, 5)
• (5)
• (5, 6)
• (5, 6)
• (6)

Problem Statement

In the night sky seen from planet AtCoder, there are N stars, and these N stars are arranged in a line from east to west. The i-th star from the east (1\le i\le N) is the B _ i-th brightest among these stars.

Takahashi decided to take a picture of the night sky using the following procedure:

1. Choose a pair of integers (l,r) satisfying 1\le l\le r\le N, and set up the camera so that the l-th, (l+1)-th, \ldots, r-th stars from the east all fit in the frame, and no other stars enter the frame.
2. Choose an integer b satisfying 1\le b\le N, and open the shutter so that all stars among the N stars whose brightness ranks from 1st through b-th (and that fit in the frame) are captured, and no other stars are captured.

However, he may not take a picture with no stars captured.

Find the number of different sets of stars that can be captured in pictures taken in this way.

Constraints

• 1\le N\le5\times10 ^ 5
• 1\le B _ i\le N\ (1\le i\le N)
• B _ i\ne B _ j\ (1\le i\lt j\le N)
• All input values are integers.

Sample Input 1

4
3 1 4 2

Sample Output 1

12

For example, with (l,r)=(2,4),b=3, you can take a picture with two stars: the 2nd star from the east and the 4th star from the east.

Including this, you can take pictures with the following 12 different sets of stars. In each picture, stars further east are arranged further left, and the i-th brightest star is labeled with integer i.

No other sets can be captured, so print 12.

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

28

Sample Input 3

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

Sample Output 3

627