Great fight

Having recovered from the last battle, Kratos again goes on a campaign. He decided to climb Mount Olympus with the Titans and arrange the most epic battle.

Climbing the mountain, he saw n gods. After observing them, Kratos assessed the strength of each. God number i has the power s[i].

Fighting the gods isn't easy, so after fighting the ith god, Kratos' power t becomes ⌊t / s[i]⌋. When t drops to zero, Kratos dies.

Over time, some nearby gods get tired, and their strength decreases by one. In other words, Kratos receives a request (l, r), which means that for each god i in position l through r, s[i] = max(s[i] − 1, 1).

Kratos comes up with plans as the fight progresses. The plan numbered j is that Kratos will take turns fighting the gods numbered l[j] , l[j + 1], ..., r[j]. The initial strength of Kratos will be equal to x[j]. For each plan, he wants to know if he can survive after it is executed. If Kratos dies, he wants to know which god will deal him the final blow.

Help Kratos and for each plan print the number of the god who will kill Kratos. If Kratos remains alive, then print -1.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 500000) - the number of gods and the number of requests. The second line contains n integers s[1], s[2], ..., s[n] (1 ≤ s[i] ≤ 10^9) - the powers of the gods. Each of the following q lines contains queries in the following format.

First comes the request type type. If type = 1, then the next line contains two integers l and r (1 ≤ l ≤ r ≤ n), meaning that the power of gods with numbers from l to r has decreased.

If type = 2, then the next line contains three integers l, r, x (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^9) - the number of the first god, the number of the last god and the initial power of Kratos in the next plan.

Output

After each request of the second type, print the number of the god who will kill Kratos. If after the execution of the plan Kratos remains alive, then print -1.

Examples

Note

In the first query of the first example, Kratos' starting power is 61. After the first battle, it is ⌊61 / 1⌋ = 61. Then it is equal to 30, 10, 5, 1, 1 and 1 respectively.