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

Problem Statement

We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.

We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?

Here, we distinguish all balls, even with the same numbers written on them.

Constraints

• N \geq 2
• L_i \geq 2
• The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
• 1 \leq a_{i,j} \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

2 40
3 1 8 4
2 10 5

Sample Output 1

2

When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.

Sample Input 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

Sample Output 2

45

Note that we distinguish all balls, even with the same numbers written on them.

Sample Input 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

Sample Output 3

0

There may be no way to make the product X.

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Initially, there is one wall in each cell.
After processing Q queries explained below in the order they are given, find the number of remaining walls.

In the q-th query, you are given two integers R_q and C_q.
You place a bomb at (R_q, C_q) to destroy walls. As a result, the following process occurs.

• If there is a wall at (R_q, C_q), destroy that wall and end the process.
• If there is no wall at (R_q, C_q), destroy the first walls that appear when looking up, down, left, and right from (R_q, C_q). More precisely, the following four processes occur simultaneously:
  • If there exists an i \lt R_q such that a wall exists at (i, C_q) and no wall exists at (k, C_q) for all i \lt k \lt R_q, destroy the wall at (i, C_q).
  • If there exists an i \gt R_q such that a wall exists at (i, C_q) and no wall exists at (k, C_q) for all R_q \lt k \lt i, destroy the wall at (i, C_q).
  • If there exists a j \lt C_q such that a wall exists at (R_q, j) and no wall exists at (R_q, k) for all j \lt k \lt C_q, destroy the wall at (R_q, j).
  • If there exists a j \gt C_q such that a wall exists at (R_q, j) and no wall exists at (R_q, k) for all C_q \lt k \lt j, destroy the wall at (R_q, j).

Constraints

• 1 \leq H, W
• H \times W \leq 4 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq R_q \leq H
• 1 \leq C_q \leq W
• All input values are integers.

Sample Input 1

2 4 3
1 2
1 2
1 3

Sample Output 1

2

The process of handling the queries can be explained as follows:

• In the 1st query, (R_1, C_1) = (1, 2). There is a wall at (1, 2), so the wall at (1, 2) is destroyed.
• In the 2nd query, (R_2, C_2) = (1, 2). There is no wall at (1, 2), so the walls at (2,2),(1,1),(1,3), which are the first walls that appear when looking up, down, left, and right from (1, 2), are destroyed.
• In the 3rd query, (R_3, C_3) = (1, 3). There is no wall at (1, 3), so the walls at (2,3),(1,4), which are the first walls that appear when looking up, down, left, and right from (1, 3), are destroyed.

After processing all queries, there are two remaining walls, at (2, 1) and (2, 4).

Sample Input 2

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

Sample Output 2

10

Sample Input 3

4 3 10
2 2
4 1
1 1
4 2
2 1
3 1
1 3
1 2
4 3
4 2

Sample Output 3

2

Problem Statement

There are N people and N buckets. Both the people and buckets are numbered 1, 2, \ldots, N.

Initially, person i holds only bucket i, and bucket i is empty.

From now on, the following operation will be performed 10^9 times:

• For i = 1, 2, \ldots, N simultaneously, person i adds i units of water to each of the buckets they are holding and passes those buckets to person A_i.

Here, there is no limit on the amount of water that can be put in a bucket.

For i = 1, 2, \ldots, Q, answer the following queries:

• Find the amount of water in bucket B_i immediately after the T_i-th operation.

Constraints

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

Sample Input 1

5 6
3 4 2 2 5
4 3
6 5
1 4
10 1
10 2
1000000000 1

Sample Output 1

11
30
4
28
30
2999999998

We will explain the first query.

Initially, bucket 3 is held by person 3.

Immediately after the 1-st operation, bucket 3 is held by person 2 and contains 3 units of water.

Immediately after the 2-nd operation, bucket 3 is held by person 4 and contains 5 units of water.

Immediately after the 3-rd operation, bucket 3 is held by person 2 and contains 9 units of water.

Immediately after the 4-th operation, bucket 3 is held by person 4 and contains 11 units of water.

Thus, the answer to the first query is 11.

Problem Statement

You are given N integers A_1, A_2, \dots, A_N.
Find the number of triples of integers (i, j, k) that satisfy the following conditions:

• 1 \le i, j, k \le N
• A_i \times A_j = A_k

Constraints

• 1 \le N \le 1000
• \color{red}{1 \le A_i < 10^{1000}}

Sample Input 1

5
2
3
6
12
24

Sample Output 1

6

The following six triples (i, j, k) satisfy the conditions in the problem statement:

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

Sample Input 2

11
1
2
3
4
5
6
123456789123456789
123456789123456789
987654321987654321
987654321987654321
121932631356500531347203169112635269

Sample Output 2

40

Note that the values of each integer A_i can be huge.

Sample Input 3

9
4
4
4
2
2
2
1
1
1

Sample Output 3

162

Note that there may be duplicates among the values of A_i.