Chtholly has given you a sequence. You need to support point updates and queries for the shortest length of a subarray whose bitwise OR sum is greater than or equal to a given number. If no such subarray exists, output $-1$.

Input

The first line contains two integers $n$ and $m$.

The next line contains $n$ integers, representing the sequence $a$.

The next $m$ lines are in the following format:

• $1\ i\ x$: Update $a_i$ to $x$.
• $2\ k$: Query the shortest length of a subarray whose bitwise OR sum is $\geq k$.

Output

For each operation of type $2$, output a single integer representing the answer. If no such subarray exists, output $-1$.

Examples

Input 1

2 3
0 2 
2 3
1 1 1
2 3

Output 1

-1
2

Note

Idea: kczno1

Solution: kczno1 ($O( m\sqrt n\log a )$ solution), liu_cheng_ao ($O( m\log^2 n\log^2 a )$ solution), 142857cs ($O( m\log n\log^2 a )$ solution)

Code: kczno1 ($O( m\sqrt n\log a )$ code), liu_cheng_ao ($O( m\log^2 n\log^2 a )$ code)

Data: kczno1

For $100\%$ of the data, $0\leq a_i,k\leq 2^{30}$, $1\leq n,m\leq 5\times 10^4$.