Gats and the Two Tempting Cushions

Time limit: 2000 msMemory limit: 256 MB

Gats the kitten is walking on a row of $N$ cushions. The cushions are numbered $1,2,\ldots,N$ from left to right, and cushion $i$ has softness $A_i$ .

When Gats is on cushion $i$ , he looks only to the right. Let $G_i$ be the smallest index $j$ such that $i < j \le N$ and , if such an index exists. Let be the smallest index such that and , if such an index exists.

Gats chooses his next pounce as follows:

If neither $G_i$ nor $S_i$ exists, Gats cannot pounce and stays on cushion $i$ .
If exactly one of $G_i$ and exists, Gats pounces to that cushion.

A pounce is called fluffy if the destination cushion has greater softness than the starting cushion.

You are given $Q$ independent queries. In the $t$ -th query, Gats starts on cushion $X_t$ and tries to make $K_t$ scheduled pounces. If he reaches a cushion from which he cannot pounce, he remains there for all remaining scheduled pounces. For each query, report his final cushion and the number of fluffy pounces he actually made.

Input

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

Output

Print $Q$ lines. On the $t$ -th line ( $1 \le t \le Q$ ), print two integers $P_t$ and , separated by one space. Here is the cushion where Gats is after the query finishes, and is the number of fluffy pounces actually made during that query.

Samples

Sample 1

Input

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

Output

For the query with $X_t = 4$ and $K_t = 3$ , the visited cushions are . Only the pounce lands on a cushion with greater softness, so the printed values are and .

Gats and the Two Tempting Cushions

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2