E. Snowy Hill
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In preparation for this year's Iditarod, you plan to practice racing on a new hill.

The hill can be considered an array of size $$$N$$$ where each index corresponds to a position on the hill. The value of each element represents the height of snow at that position on the hill. Index $$$0$$$ represents the start of the hill and index $$$N-1$$$ represents the end of the hill. Since the hill slopes upwards, the height of snow is monotonically increasing from the start to the end of the hill.

To ensure it is safe to traverse, you want to analyze the hill before you begin. You want to answer $$$Q$$$ queries where each query contains an integer $$$K$$$. For each query, find the smallest interval $$$[a,b]$$$ on the hill where the sum of the snow heights is exactly $$$K$$$ units.

If multiple of these intervals exist, output the interval closest to the start of the hill. It is guaranteed that such an interval exists somewhere on the hill.

Input

The first line of input contains two numbers $$$N$$$ and $$$Q$$$. $$$(1 \leq N \leq 100,000)$$$ $$$(1 \leq Q \leq 100)$$$

The next line of input contains $$$N$$$ numbers representing the hill array. $$$(1 \leq a_i \leq N)$$$

The next Q lines each contain an integer $$$K$$$. $$$(1 \leq K \leq N^2)$$$

Output

For each query, please output integers $$$a \space b$$$ (0-indexed) representing the start and end index of the desired interval $$$[a, b]$$$ respectively.

Examples
Input
6 3
2 2 3 4 5 6
4
7
16
Output
3 3
2 3
0 4
Input
10 5
1 1 1 2 2 4 6 7 9 9
1
16
2
10
7
Output
0 0
7 8
3 3
5 6
7 7