Process Execution

Each process has a power consumption power, and each processor can serve the processes in the closed interval [minPower,maxPower]. For each processor independently, output the number of processes in its range and the total power of those processes; this is not a one-time assignment of processes to different processors. Duplicate power values belong to different processes and are counted separately.

输入格式

The first line contains n m, the second line contains n power values, followed by m lines of minPower maxPower. The original bounds are 1≤n≤12×10^5=1200000, 1≤m≤200000, 1≤power,minPower≤maxPower≤10^8 (power on its own is in 1..10^8). 1,200,000 is not misread as 120,000.

输出格式

Output m lines in the input order of the processors, each containing the count and the total power.

样例 1

输入：

4 3
7 6 8 10
6 10
3 7
4 9

输出：

4 31
2 13
3 21

样例 2

输入：

3 2
11 11 11
8 11
13 100

输出：

3 33
0 0

样例 3

输入：

3 2
1 2 3
2 2
1 3

输出：

1 2
3 6

样例说明

The outputs are 4 31 / 2 13 / 3 21; 3 33 / 0 0; and 1 2 / 3 6. The text of the second original example wrongly says 2 processes; given its three-element array, it should be 3.