Дана последовательность $A$ длины $n$. Пусть $f(x,y)=[x\leq y]$, где $[st]=1$, если утверждение $st$ истинно, иначе $[st]=0$. Характеристическая последовательность $A$ — это последовательность $B$ длины $n-1$, где $B_i=f(A_i,A_{i+1})$. Например, характеристическая последовательность для $1,3,3,1,2$ равна $1,1,0,1$.

Имеется $q$ запросов следующего формата.

• $1\ x\ v$ — означает, что нужно изменить $A_x$ на $v$; обратите внимание, что характеристическая последовательность также изменится.
• $2\ l\ r\ v$ — означает, что нужно найти наименьшее $i\in [l,r]$ такое, что если заменить $A_i$ на $v$, характеристическая последовательность не изменится, или вывести $-1$, если такого $i$ нет. Обратите внимание, что этот запрос не изменяет последовательность.

Пожалуйста, выведите ответы на все запросы типа $2$.

Входные данные

Первая строка содержит два целых числа $n,q$ ($3\leq n\leq 5\times 10^5$, $1\leq q\leq 5\times 10^5$) — длину последовательности и количество запросов.

Следующая строка содержит $n$ целых чисел, $i$-е из которых обозначает $A_i$ ($1\leq A_i\leq 10^9$).

Каждая из следующих $q$ строк содержит один запрос в указанном выше формате. Если тип запроса равен $1$, то гарантируется, что $1\leq x\leq n$, $1\leq v\leq 10^9$. Если тип запроса равен $2$, то гарантируется, что $1\leq l\leq r\leq n$, $1\leq v\leq 10^9$.

Выходные данные

Для каждого запроса типа $2$ выведите одну строку, содержащую ответ на запрос.

Примеры

Входные данные 1

3 4
1 2 3
2 1 2 4
2 1 3 3
1 2 3
2 2 3 4

Выходные данные 1

-1
2
3