Bolder Yarn Knots

Time limit: 2000 msMemory limit: 256 MB

Gats found a row of yarn knots. The knots are numbered $1$ through $N$ from left to right, and knot $i$ has height $H_i$ .

Gats starts on some knot and repeatedly jumps according to the following rules.

For his current knot $i$ :

On the left, consider the closest knot $j$ such that $j < i$ and $H_j > H_i$ .

Every jump goes to a knot with strictly larger height, so Gats eventually stops.

You are given $Q$ starting knots. For each starting knot, determine where Gats stops and the total distance he travels.

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N,Q \le 2 \times 10^5$ ), the number of knots and the number of starting questions.

Output

For each query, print two integers $F_t$ and $D_t$ on one line. Here, $F_t$ is the index of the knot where Gats stops when starting from , and is the total distance he travels, equal to the sum of over all jumps from knot to knot .

Samples

Sample 1

Input

7 4
3 1 4 2 5 2 6
1
2
4
7

Output

For $S_1 = 1$ , the walk is $1 \to 3 \to 5 \to 7$ , so and . For , the walk is . For , Gats is already at a stopping knot.

Bolder Yarn Knots

Input

Output

Samples

Sample 1

Submit

Submissions