Problem Statement

Takahashi, who is A years old, is riding a Ferris wheel.

It costs B yen (B is an even number) to ride the Ferris wheel if you are 13 years old or older, but children between 6 and 12 years old (inclusive) can ride it for half the cost, and children who are 5 years old or younger are free of charge. (Yen is the currency of Japan.)

Find the cost of the Ferris wheel for Takahashi.

Constraints

• 0 ≤ A ≤ 100
• 2 ≤ B ≤ 1000
• B is an even number.

Sample Input 1

30 100

Sample Output 1

100

Takahashi is 30 years old now, and the cost of the Ferris wheel is 100 yen.

Sample Input 2

12 100

Sample Output 2

50

Takahashi is 12 years old, and the cost of the Ferris wheel is the half of 100 yen, that is, 50 yen.

Sample Input 3

0 100

Sample Output 3

0

Takahashi is 0 years old, and he can ride the Ferris wheel for free.

Problem Statement

The development of algae in a pond is as follows.

Let the total weight of the algae at the beginning of the year i be x_i gram. For i≥2000, the following formula holds:

• x_{i+1} = rx_i - D

You are given r, D and x_{2000}. Calculate x_{2001}, ..., x_{2010} and print them in order.

Constraints

• 2 ≤ r ≤ 5
• 1 ≤ D ≤ 100
• D < x_{2000} ≤ 200
• All values in input are integers.

Sample Input 1

2 10 20

Sample Output 1

30
50
90
170
330
650
1290
2570
5130
10250

For example, x_{2001} = rx_{2000} - D = 2 \times 20 - 10 = 30 and x_{2002} = rx_{2001} - D = 2 \times 30 - 10 = 50.

Sample Input 2

4 40 60

Sample Output 2

200
760
3000
11960
47800
191160
764600
3058360
12233400
48933560

Problem Statement

We have N ID cards, and there are M gates.

We can pass the i-th gate if we have one of the following ID cards: the L_i-th, (L_i+1)-th, ..., and R_i-th ID cards.

How many of the ID cards allow us to pass all the gates alone?

Constraints

• All values in input are integers.
• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq L_i \leq R_i \leq N

Sample Input 1

4 2
1 3
2 4

Sample Output 1

2

Two ID cards allow us to pass all the gates alone, as follows:

• The first ID card does not allow us to pass the second gate.
• The second ID card allows us to pass all the gates.
• The third ID card allows us to pass all the gates.
• The fourth ID card does not allow us to pass the first gate.

Sample Input 2

10 3
3 6
5 7
6 9

Sample Output 2

1

Sample Input 3

100000 1
1 100000

Sample Output 3

100000

Problem Statement

You have N cards. On the i-th card, an integer A_i is written.

For each j = 1, 2, ..., M in this order, you will perform the following operation once:

Operation: Choose at most B_j cards (possibly zero). Replace the integer written on each chosen card with C_j.

Find the maximum possible sum of the integers written on the N cards after the M operations.

Constraints

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

Sample Input 1

3 2
5 1 4
2 3
1 5

Sample Output 1

14

By replacing the integer on the second card with 5, the sum of the integers written on the three cards becomes 5 + 5 + 4 = 14, which is the maximum result.

Sample Input 2

10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4

Sample Output 2

338

Sample Input 3

3 2
100 100 100
3 99
3 99

Sample Output 3

300

Sample Input 4

11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000

Sample Output 4

10000000001

The output may not fit into a 32-bit integer type.

Problem Statement

We have a grid of squares with N rows and M columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. We will choose K of the squares and put a piece on each of them.

If we place the K pieces on squares (x_1, y_1), (x_2, y_2), ..., and (x_K, y_K), the cost of this arrangement is computed as:

\sum_{i=1}^{K-1} \sum_{j=i+1}^K (|x_i - x_j| + |y_i - y_j|)

Find the sum of the costs of all possible arrangements of the pieces. Since this value can be tremendous, print it modulo 10^9+7.

We consider two arrangements of the pieces different if and only if there is a square that contains a piece in one of the arrangements but not in the other.

Constraints

• 2 \leq N \times M \leq 2 \times 10^5
• 2 \leq K \leq N \times M
• All values in input are integers.

Sample Input 1

2 2 2

Sample Output 1

8

There are six possible arrangements of the pieces, as follows:

• ((1,1),(1,2)), with the cost |1-1|+|1-2| = 1
• ((1,1),(2,1)), with the cost |1-2|+|1-1| = 1
• ((1,1),(2,2)), with the cost |1-2|+|1-2| = 2
• ((1,2),(2,1)), with the cost |1-2|+|2-1| = 2
• ((1,2),(2,2)), with the cost |1-2|+|2-2| = 1
• ((2,1),(2,2)), with the cost |2-2|+|1-2| = 1

The sum of these costs is 8.

Sample Input 2

4 5 4

Sample Output 2

87210

Sample Input 3

100 100 5000

Sample Output 3

817260251

Be sure to print the sum modulo 10^9+7.

Problem Statement

There is a function f(x), which is initially a constant function f(x) = 0.

We will ask you to process Q queries in order. There are two kinds of queries, update queries and evaluation queries, as follows:

• An update query 1 a b: Given two integers a and b, let g(x) = f(x) + |x - a| + b and replace f(x) with g(x).
• An evaluation query 2: Print x that minimizes f(x), and the minimum value of f(x). If there are multiple such values of x, choose the minimum such value.

We can show that the values to be output in an evaluation query are always integers, so we ask you to print those values as integers without decimal points.

Constraints

• All values in input are integers.
• 1 \leq Q \leq 2 \times 10^5
• -10^9 \leq a, b \leq 10^9
• The first query is an update query.

Sample Input 1

4
1 4 2
2
1 1 -8
2

Sample Output 1

4 2
1 -3

In the first evaluation query, f(x) = |x - 4| + 2, which attains the minimum value of 2 at x = 4.

In the second evaluation query, f(x) = |x - 1| + |x - 4| - 6, which attains the minimum value of -3 when 1 \leq x \leq 4. Among the multiple values of x that minimize f(x), we ask you to print the minimum, that is, 1.

Sample Input 2

4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2

Sample Output 2

-1000000000 3000000000