You are given an array of size $N$ in which the value of the elements are either $0$ or $1$. All the elements of array are numbered from position $0$ to $N-1$.You are given some queries which can be of following $2$ types.

$0 \; index$ : In this type of query you have to find the nearest left and nearest right element from position $index$ in the array whose value is $1$.
$1 \; index$ : In this type of query you need to change the value at positon $index$ to $1$ if its previous value is 0 or else leave it unchanged.

Important Note : If there is no position with value 1 on the left side of any index in query then print -1 instead of left index and similarly if there is no value 1 in right side of the value index in that query then print -1 in place of the answer for right element.

Input
First line contains $2$ integers $N$ and $Q$ denoting the number of elements in array and number of queries.
Next line contains $N$ elements denoting the array.
Next $Q$ lines contains $2$ integer each denoting the any type of Query.

Output
For each query print left and right nearest element seprated by space.

Constraints
$1 \le N \le 100000$
$1\le index \le N$

Sample Inputs

-1 -1
2 4

-1 2
2 5