Description

Charlotte can now write many Arabic numerals, so her teacher gave her an advanced assignment.

First, given an array A of N numbers and Q queries.

Each query consists of two numbers L and R. For each query, Charlotte needs to answer how many i satisfy L ≤ A[i] ≤ R in the given array A (where i is integer and 1 ≤ i ≤ N).

Please help Charlotte complete her homework.

Input

The first line contains two numbers N, Q (1 ≤ N ≤ 2 × 10⁵, 1 ≤ Q ≤ 2 × 10⁵).

The second line contains N numbers representing A[1], A[2], ..., A[N] (1 ≤ A[i] ≤ 10⁸).

The next Q lines each contain two numbers L and R (guaranteed that 1 ≤ L ≤ R ≤ 10⁸).

Output

Output Q lines, each representing the answer to the corresponding query.

Please add a newline('\n') at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given a sequence of length N. You can repeatedly choose any two numbers from the sequence and add them together, placing the sum back into the sequence, until only one number remains (thus, you will perform a total of N−1 additions).

Each addition has a cost, which is the sum of the two numbers chosen. For example, the cost of adding 1 and 10 is 11.

Your task is to add the N numbers together in such a way that the total cost is minimized.

Input

Each test case starts with a positive integer N (2 ≤ N ≤ 200000), followed by N positive integers (each less than 100000).

Output

print the minimum total cost of addition on a single line.

Remember to print a ‘\n’ at the end of the output.

HINT

To achieve the minimum total cost, always combine the two smallest available numbers first.

Note: The total cost may exceed 2³¹ - 1

Sample Testcase 1:

Initial: The initial sequence is {1, 2, 3}.

Step 1: We choose the numbers 1 and 2. After adding them, the sequence becomes {3, 3}, and the cost is 1+2=3.

Step 2: We choose the numbers 3 and 3. After adding them, the sequence becomes {6}, and the cost is 3+3=6.

Final: The total cost is 3+6=9.

Sample Testcase 2:

Initial: The initial sequence is {1, 2, 3, 4}.

Step 1: We choose the numbers 1 and 2. After adding them, the sequence becomes {3, 3, 4}, and the cost is 1+2=3.

Step 2: We choose the numbers 3 and 3. After adding them, the sequence becomes {4, 6}, and the cost is 3+3=6.

Step 3: We choose the numbers 4 and 6. After adding them, the sequence becomes {10}, and the cost is 4+6=10.

Final: The total cost is 3+6+10=19.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given n rectangle R_i, i = 1, 2, ..., n in the Euclidean plane. The lower left point and upper right point of R_i is (0, 0) and (u_i, r_i) repectively.

Find the number of pairs (i, j) such that R_i can be contained in R_j after rotating 90^o or 0^o. Formally speaking, find the number of pairs (i, j) that satisfy at least one of the following conditions:

• u_i ≤ u_j and r_i ≤ r_j
• u_i ≤ r_j and r_i ≤ u_j

For example, the following two rectangles satisfy the condition, since the blue rectangle can be contained in the red rectangle by rotating 90^o (see picture on right hand side).

      

Input

The first line contains an integer n. For the next n line, each line contains two integers u_i, r_i, i = 1, 2, ..., n.

Constrain

• 1 ≤ n ≤ 10⁵
• 1 ≤ u_i, r_i ≤ 10⁹, i = 1, 2, ..., n
• No two rectangles are identical after rotating 90^o or 0^o.

Output

Output one integer: the number of pairs satisfying the condition above.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are n gas stations on a highway, the i-th station is located at the x_i km of the highway, and you can get v_i unit of fuel (an unit of fuel can drive 1 km) if you stop and refuel at this station. Also, you can't stop at the i+1, i+2, ..., n-th station if you don't stop at the i-th station.

Now you are at the 0 km of the highway and your car has V unit of fuel. Besides, there are q places you want to visit, the i-th place is located at the p_i km of the highway.  Now, for each place, answer at least how many gas station you need to stop in order to reach the place.

Hint

Let T_i be the total unit of fuel you will have if you stop at 1, 2, ... i-th station. Then T_i = V + v₁ + v₂ + ... + v_i by definition, which can be computed in O(n) time using the following recurrence:

• T₀ = V (We define T₀ as the total unit of fuel if you don't stop at any station)
• T_i = T_i-1 + v_i, i = 1, 2, ..., n

Input

The first line contains two integers: n, q, V. 

For the next n lines, each line contains two integers: x_i, v_i (i = 1, 2, ..., n).

The last line contains q integers: p₁, p₂, ..., p_n.

Constrain

• 1 ≤ n, q ≤ 10⁵
• 1 ≤ x₁ < x₂ < ... < x_n ≤ 10⁹
• 1 ≤ v_i ≤ 10⁹, i = 1, 2, ..., n
• 1 ≤ p_i ≤ 10⁹, i = 1, 2, ..., q

Output

Output n lines, each line contains one integer: the answer of the i-th place. If it is impossible to reach the place, output -1.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss