위대한 전투

기력을 회복한 크라토스가 다시 여정에 나선다. 그는 티탄들과 함께 올림푸스 산에 오르고, 지금까지 가장 큰 싸움을 벌이려 한다.

산꼭대기에서 그는 신 $n$명을 본다. 신들을 지켜본 뒤 크라토스는 각 신의 힘을 가늠한다. $i$번 신의 힘은 $s_i$이다.

신과의 싸움은 쉽지 않다. 그래서 $i$번 신과 싸운 뒤 크라토스의 힘 $T$는 $\lfloor \frac{T}{s_i} \rfloor$가 된다. $T$가 0까지 줄어들면 크라토스는 죽는다.

시간이 지나면서 가까이 서 있는 일부 신들이 지쳐 힘이 1 줄어든다. 즉 쿼리 $(l, r)$는 위치 $l$부터 $r$까지 모든 신 $i$에 대해 $s_i = \max(s_i - 1, 1)$을 뜻한다.

싸움 도중 크라토스는 계획을 세운다. $j$번 계획은 초기 힘 $x_j$로 $l_j$번 신부터 $r_j$번 신까지 차례로 싸우는 것이다. 각 계획마다 그가 살아남을 수 있는지 알고 싶다. 죽는다면 마지막 일격을 가하는 신의 번호를 알고 싶다.

각 계획에 대해 크라토스를 죽이는 신의 번호를 출력한다. 크라토스가 살아남으면 <<-1>>을 출력한다.

첫 줄에 신의 수 $n$과 쿼리의 수 $q$가 주어진다 ($1 \leq n, q \leq 500\,000$). 둘째 줄에는 신들의 힘 $s_1, s_2, \dots, s_n$이 주어진다 ($1 \leq s_i \leq 10^9$). 이어지는 $q$개의 줄은 쿼리이며, 각 쿼리의 첫 값은 종류 $type$이다.

$type = 1$이면 정수 $l$과 $r$이 이어서 주어진다 ($1 \leq l \leq r \leq n$). 위치 $l$부터 $r$까지 신들의 힘이 1 줄어든다.

$type = 2$이면 정수 $l$, $r$, $x$가 이어서 주어진다. 각각 첫 신의 번호, 마지막 신의 번호, 그 계획에서 크라토스의 초기 힘이다 ($1 \leq l \leq r \leq n$, $1 \leq x \leq 10^9$).

$type = 2$인 각 쿼리마다 크라토스를 죽이는 신의 번호를 출력한다. 계획을 마친 뒤 크라토스가 살아 있으면 <<-1>>을 출력한다.

첫 번째 예제의 첫 번째 쿼리에서 크라토스의 초기 힘은 61이다. 첫 번째 싸움 후 힘은 $\lfloor \frac{61}{1} \rfloor = 61$이다. 이어서 힘은 차례로 30, 10, 5, 1, 1, 1이 된다.