Problem Statement

Takahashi is commanding a mission as the commander of the Space Defense Force to intercept an enemy spaceship that is moving away from Earth.

There is a straight route in outer space, and Earth is located at coordinate 0. The enemy spaceship is at coordinate D and has begun fleeing at a constant speed V in the direction away from Earth (the direction of increasing coordinates).

Takahashi is preparing to launch N interceptor missiles. The i-th missile can fly at speed S_i. Missiles can only fly in the same direction as the enemy spaceship (the direction of increasing coordinates), and are launched from coordinate 0 at time 0.

Takahashi needs to determine which missiles can reach the enemy spaceship. A missile reaching the enemy spaceship means that at some time t \geq 0, the missile's coordinate becomes greater than or equal to the enemy spaceship's coordinate.

Find the number of missiles among the N missiles that can reach the enemy spaceship.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq D \leq 10^9
• 1 \leq V \leq 10^9
• 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 10 3
2 3 4 5 10

Sample Output 1

3

Sample Input 2

4 7 5
1 5 4 2

Sample Output 2

0

Sample Input 3

12 100 20
5 20 21 19 100 1 25 20 30 18 22 40

Sample Output 3

6

Sample Input 4

30 123456789 500000000
499999999 500000000 500000001 600000000 700000000 1 999999999 250000000 800000000 450000000 510000000 490000000 520000000 530000000 540000000 550000000 560000000 570000000 580000000 590000000 400000000 300000000 200000000 100000000 750000000 650000000 350000000 150000000 900000000 1000000000

Sample Output 4

18

Sample Input 5

1 1000000000 1000000000
1000000000

Sample Output 5

0

Problem Statement

Takahashi works at a fruit shop. There are N fruits displayed in the shop, and the sweetness of the i-th fruit is A_i.

Then, Aoki delivers M new fruits from the supplier. The sweetness of the j-th new fruit is B_j.

Takahashi decides to select K fruits from among these N + M fruits in descending order of sweetness to make a gift assortment.

Find the total sweetness of the K selected fruits.

Note that even if there are multiple fruits with the same sweetness, the total sweetness will be the same regardless of which K fruits are chosen.

Constraints

• 1 \leq N, M
• N + M \leq 150000
• 1 \leq K \leq N + M
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq B_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers

Sample Input 1

3 2 3
4
1
7
5
2

Sample Output 1

16

Sample Input 2

2 3 4
5
5
5
1
0

Sample Output 2

16

Sample Input 3

7 6 8
12
3
25
8
17
6
14
9
30
2
17
11
20

Sample Output 3

146

Sample Input 4

12 10 15
100
250
400
50
600
700
150
350
800
450
550
650
500
300
900
200
1000
750
125
875
425
575

Sample Output 4

9525

Sample Input 5

1 1 2
0
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi runs an online shop and handles N products. The products are numbered from 1 to N, and product i (1 \leq i \leq N) has the name S_i and a price of V_i yen. Different products may have the same name or the same price.

Aoki is a customer of this shop and has sent Q search requests. In the j-th request (1 \leq j \leq Q), he specifies an integer X_j and asks: "Please tell me all products whose price is exactly X_j yen."

However, Aoki may not remember the exact price. Therefore, for Aoki's convenience, Takahashi decided to return search results according to the following rules:

• If there exist one or more products whose price is exactly X_j yen, output all of their names on a single line, separated by spaces, in ascending order of product number. Even if multiple matching products have the same name, each is output once as a separate product (meaning names may appear duplicated in the output).
• If no product has a price of exactly X_j yen, as a suggestion of "Did you mean this product?", select and output one product whose price is closest to X_j. Specifically, the candidates are the products that minimize the absolute difference |V_i - X_j|. If there are multiple candidates (for example, a product that is equally cheaper and one that is equally more expensive than X_j), choose the one with the smallest product number among them. Output only one name of the selected product on a single line.

Determine the search results for each request.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• S_i is a string of length between 1 and 20 inclusive, consisting only of lowercase English letters.
• 1 \leq V_i \leq 10^9
• 1 \leq X_j \leq 10^9
• N, Q, V_i, X_j are all integers.
• It is guaranteed that the total number of characters of product names output across all requests (excluding separating spaces and newlines) does not exceed 10^6.

Sample Input 1

5 4
apple 100
banana 200
cherry 100
date 300
elderberry 500
100
250
300
150

Sample Output 1

apple cherry
banana
date
apple

Sample Input 2

4 5
milk 150
bread 150
cheese 300
butter 300
150
300
200
225
450

Sample Output 2

milk bread
cheese butter
milk
milk
cheese

Sample Input 3

10 8
notebook 1200
pen 300
eraser 100
ruler 500
pencil 300
marker 800
tape 250
glue 250
scissors 1500
stapler 1200
300
1200
100
700
2000
1
250
999

Sample Output 3

pen pencil
notebook stapler
eraser
marker
scissors
eraser
tape glue
marker

Sample Input 4

15 10
alpha 1000
beta 2000
gamma 3000
delta 4000
epsilon 5000
zeta 6000
eta 7000
theta 8000
iota 9000
kappa 10000
lambda 1000
mu 5000
nu 5000
xi 15000
omicron 20000
5000
1000
7500
1
1000000000
10000
15000
12000
20000
3500

Sample Output 4

epsilon mu nu
alpha lambda
eta
alpha
omicron
kappa
xi
kappa
omicron
gamma

Sample Input 5

1 1
a 1000000000
1000000000

Sample Output 5

a

Problem Statement

Takahashi is growing N fruit trees on his farm. The initial growth level of the i-th tree (1 \leq i \leq N) is A_i.

In preparation for the harvest season, Takahashi plans to distribute exactly K bags of fertilizer in total among these fruit trees. Let B_i denote the number of bags of fertilizer given to the i-th tree. The distribution must satisfy the following conditions:

• Each B_i is a non-negative integer. (There is no upper limit on the number of bags given to a single tree. It is also acceptable for some trees to receive no bags at all.)
• B_1 + B_2 + \cdots + B_N = K

After distributing the fertilizer, the growth level of the i-th tree becomes A_i + B_i. In this farm, it is known that the harvest yield is determined by the product of the growth levels of all fruit trees, so the harvest yield is

(A_1 + B_1) \times (A_2 + B_2) \times \cdots \times (A_N + B_N)

When Takahashi distributes the fertilizer optimally to maximize the harvest yield, find the maximum harvest yield modulo 10^9 + 7.

Note that the maximization is based on the true value before taking the modulo 10^9 + 7. That is, choose the distribution that maximizes the true harvest yield, and output that harvest yield modulo 10^9 + 7.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{18}
• 1 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

3 5
1 2 3

Sample Output 1

48

Sample Input 2

4 3
2 2 5 8

Sample Output 2

480

Sample Input 3

8 100
1 7 3 20 15 2 9 30

Sample Output 3

505781965

Sample Input 4

20 1000000000000
1000000000 1 500000000 123456789 987654321 42 314159265 271828182 999999937 100 200 300 400 500 600 700 800 900 1000 12345

Sample Output 4

134759236

Sample Input 5

1 1000000000000000000
1000000000

Sample Output 5

42

Problem Statement

Takahashi is in charge of a service counter during business hours represented by the half-open interval [0, T). Time is handled as integers.

During business hours, Takahashi must take exactly one continuous break of length D. If the break starts at time S, then the break period (when the counter is closed) is the half-open interval [S, S+D). S is chosen from integers satisfying 0 \leq S \leq T - D. That is, the break fits completely within business hours. The counter is open during the non-break period [0, S) \cup [S+D, T).

There are N customers who wish to use the counter. Initially, the i-th customer (1 \leq i \leq N) visits the counter only during the time period [L_i, R_i). The condition for the i-th customer's procedure to not be completed is that their stay period [L_i, R_i) is completely contained within the break period [S, S+D), that is, S \leq L_i and R_i \leq S+D hold. In other words, if there exists at least one time within the stay period when the counter is open, the procedure is completed.

Takahashi is given Q operations in order. There are two types of operations:

• Update operation (1 i L R): Change the stay period of the i-th customer to [L, R). This change is reflected in all subsequent operations. Multiple update operations may be performed on the same customer, and the most recent change is always in effect.
• Query operation (2): Based on the current stay periods of all customers, determine the break start time S that minimizes the number of customers whose procedures are not completed. If there are multiple such S, output the smallest one.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq D \leq T
• 1 \leq Q \leq 10^5
• N + 2Q \leq 2 \times 10^5
• 0 \leq L_i < R_i \leq T (for each customer in the initial state)
• For update operations 1 i L R: 1 \leq i \leq N, 0 \leq L < R \leq T
• At least one query operation 2 is included among the Q operations
• All input values are integers

Sample Input 1

10 3 3 5
0 2
4 6
7 10
2
1 2 3 5
2
1 1 7 10
2

Sample Output 1

1 0
1 0
0 0

Sample Input 2

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

Sample Output 2

1 0
1 0
0 0
0 0

Sample Input 3

30 10 7 12
0 4
3 8
6 12
9 15
14 18
17 25
20 27
1 29
11 13
24 30
2
1 4 10 16
2
1 7 0 3
1 2 22 30
2
1 10 14 20
2
1 1 5 6
1 5 23 29
2
2

Sample Output 3

4 0
4 0
1 0
1 0
12 0
12 0

Sample Input 4

1000 30 120 25
0 50
20 180
100 160
150 300
250 260
270 400
390 510
500 620
610 750
740 900
880 1000
5 995
123 456
321 654
600 601
700 701
800 850
50 70
75 125
200 350
360 365
420 480
490 495
520 700
710 930
940 990
30 900
111 222
333 444
555 666
2
1 5 10 130
1 12 0 120
2
1 15 119 120
1 16 120 121
1 17 121 240
2
1 1 880 950
1 30 0 1000
2
1 8 480 500
1 9 500 510
1 10 510 520
2
1 20 100 220
1 21 221 222
1 22 222 342
2
1 3 340 460
1 4 460 580
2
1 25 0 1
1 26 999 1000
2

Sample Output 4

101 0
101 0
122 0
122 0
122 0
223 0
223 0
223 0

Sample Input 5

1 1 1 1
0 1
2

Sample Output 5

0 1