The Great Battle

Recovering from the last fight, Kratos sets out on another journey. He decides to climb Mount Olympus together with the Titans and fight the greatest battle yet.

At the summit he sees $n$ gods. After watching them, Kratos sizes up the strength of each one. God number $i$ has strength $s_i$.

Fighting gods is hard, so after a battle with god $i$, Kratos's power $T$ becomes $\lfloor \frac{T}{s_i} \rfloor$. When $T$ drops to zero, Kratos dies.

Over time, some gods standing next to each other grow tired, and their strength drops by one. In other words, a query $(l, r)$ means that for every god $i$ at position $l$ through $r$, $s_i = \max(s_i - 1, 1)$.

During the fight, Kratos makes plans. Plan number $j$ means Kratos fights gods $l_j, l_j + 1, \dots, r_j$ in order, starting with power $x_j$. For each plan he wants to know whether he survives it. If he dies, he wants to know which god lands the last blow.

For each plan, print the number of the god who kills Kratos. If Kratos survives, print <<-1>>.

The first line contains two integers $n$ and $q$, the number of gods and the number of queries ($1 \leq n, q \leq 500\,000$). The second line contains $n$ integers $s_1, s_2, \dots, s_n$, the strengths of the gods ($1 \leq s_i \leq 10^9$). Each of the next $q$ lines is a query, and its first number is the type $type$.

If $type = 1$, two integers $l$ and $r$ follow ($1 \leq l \leq r \leq n$). The strength of the gods from $l$ to $r$ decreases by one.

If $type = 2$, three integers $l$, $r$, and $x$ follow: the number of the first god, the number of the last god, and Kratos's starting power for this plan ($1 \leq l \leq r \leq n$, $1 \leq x \leq 10^9$).

For each query of type 2, print the number of the god who kills Kratos. If Kratos is still alive after the plan, print <<-1>>.

In the first query of the first sample, Kratos starts with power 61. After the first fight, it is $\lfloor \frac{61}{1} \rfloor = 61$. Then the power becomes 30, 10, 5, 1, 1, and 1 in turn.