Problem Statement

There are N people numbered 1, 2, \ldots, N, sitting in this clockwise order around a round table. In particular, person 1 is sitting next to person N in the clockwise direction.

For each i = 1, 2, \ldots, N, person i has a name S_i and an age A_i. Here, no two people have the same name or the same age.

Starting from the youngest person, print the names of all N people in the order of their seating positions in clockwise order.

Constraints

• 2 \leq N \leq 100
• N is an integer.
• S_i is a string of length between 1 and 10, consisting of lowercase English letters.
• i \neq j \implies S_i \neq S_j
• 0 \leq A_i \leq 10^9
• A_i is an integer.
• i \neq j \implies A_i \neq A_j

Sample Input 1

5
alice 31
bob 41
carol 5
dave 92
ellen 65

Sample Output 1

carol
dave
ellen
alice
bob

The youngest person is person 3. Therefore, starting from person 3, print the names in the clockwise order of their seating positions: person 3, person 4, person 5, person 1, and person 2.

Sample Input 2

2
takahashi 1000000000
aoki 999999999

Sample Output 2

aoki
takahashi

Problem Statement

You are given a positive integer N.
Output the sum of all integers from 1 to N, that is, 1+2+\cdots+N.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

5

Sample Output 1

15

Since 1+2+3+4+5=15, output 15.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

29

Sample Output 3

435

Problem Statement

Takahashi is participating in a gymnastic competition.
In the competition, each of 5N judges grades Takahashi's performance, and his score is determined as follows:

• Invalidate the grades given by the N judges who gave the highest grades.
• Invalidate the grades given by the N judges who gave the lowest grades.
• Takahashi's score is defined as the average of the remaining 3N judges' grades.

More formally, Takahashi's score is obtained by performing the following procedure on the multiset of the judges' grades S (|S|=5N):

• Repeat the following operation N times: choose the maximum element (if there are multiple such elements, choose one of them) and remove it from S.
• Repeat the following operation N times: choose the minimum element (if there are multiple such elements, choose one of them) and remove it from S.
• Takahashi's score is defined as the average of the 3N elements remaining in S.

The i-th (1\leq i\leq 5N) judge's grade for Takahashi's performance was X_i points. Find Takahashi's score.

Constraints

• 1\leq N\leq 100
• 0\leq X_i\leq 100
• All values in the input are integers.

Sample Input 1

1
10 100 20 50 30

Sample Output 1

33.333333333333336

Since N=1, the grade given by one judge who gave the highest grade, and one with the lowest, are invalidated.
The 2-nd judge gave the highest grade (100 points), which is invalidated.
Additionally, the 1-st judge gave the lowest grade (10 points), which is also invalidated.
Thus, the average is \displaystyle\frac{20+50+30}{3}=33.333\cdots.

Note that the output will be considered correct if the absolute or relative error from the true value is at most 10^{-5}.

Sample Input 2

2
3 3 3 4 5 6 7 8 99 100

Sample Output 2

5.500000000000000

Since N=2, the grades given by the two judges who gave the highest grades, and two with the lowest, are invalidated.
The 10-th and 9-th judges gave the highest grades (100 and 99 points, respectively), which are invalidated.
Three judges, the 1-st, 2-nd, and 3-rd, gave the lowest grade (3 points), so two of them are invalidated.
Thus, the average is \displaystyle\frac{3+4+5+6+7+8}{6}=5.5.

Note that the choice of the two invalidated judges from the three with the lowest grades does not affect the answer.

Problem Statement

There is an empty bag.

You are given Q queries. Process these queries in order and output the answer to each type-2 query.

Each query is of one of the following types.

• Type 1: Given as input in the format 1 x. Put a ball with the integer x written on it into the bag.

• Type 2: Given as input in the format 2. Pick out one ball with the minimum integer written on it from the balls in the bag, and report that integer as the answer. This query is not given when the bag contains no balls.

Constraints

• 2 \leq Q \leq 100
• In a type-1 query, 1 \leq x \leq 100.
• When a type-2 query is given, the bag is not empty.
• At least one type-2 query is given.
• All input values are integers.

Sample Input 1

5
1 6
1 7
2
1 1
2

Sample Output 1

6
1

Initially, the bag contains no balls.

The 1st query puts a ball with 6 written on it into the bag.

The 2nd query puts a ball with 7 written on it into the bag.

In the 3rd query, the bag contains a ball with 6 written on it and a ball with 7 written on it, so you pick out the ball with 6 written on it. The answer to this query is 6.

The 4th query puts a ball with 1 written on it into the bag.

In the 5th query, the bag contains a ball with 1 written on it and a ball with 7 written on it, so you pick out the ball with 1 written on it. The answer to this query is 1.

Sample Input 2

8
1 5
1 1
1 1
1 9
2
2
1 2
2

Sample Output 2

1
1
2

The bag may contain multiple balls with the same integer.

Problem Statement

We have N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

• 1 i j \colon Write the number i on a blank card and put it into box j.
• 2 i \colon Report all numbers written on the cards in box i, in ascending order.
• 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

• In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• For a query of the first kind:
  • 1 \leq i \leq 2 \times 10^5
  • 1 \leq j \leq N
• For a query of the second kind:
  • 1 \leq i \leq N
  • Box i contains some cards when this query is given.
• For a query of the third kind:
  • 1 \leq i \leq 2 \times 10^5
  • Some boxes contain a card with the number i when this query is given.
• At most 2 \times 10^5 numbers are to be reported.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write 1 on a card and put it into box 1.
• Write 2 on a card and put it into box 4.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1 and 2.
  • Print 1 and 2 in this order.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1, 1, and 2.
  • Note that you should print 1 twice.
• Boxes 1 and 4 contain a card with the number 1.
  • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
• Boxes 4 contains a card with the number 2.

Sample Input 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

Sample Output 2

1 2 200000
1