Great fight#11030
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 gods. After observing them, Kratos assessed the strength of each. God number has the power s_i.
Fighting the gods isn't easy, so after fighting the th god, Kratos' power becomes \lfloor t / s_i \rfloor. When 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 in position through , s_i = \max(s_i - 1, 1).
Kratos comes up with plans as the fight progresses. The plan numbered is that Kratos will take turns fighting the gods numbered l_j, l_j + 1, \ldots, 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 .
The first line contains two integers and (1 \le n, q \le 500000) - the number of gods and the number of requests. The second line contains integers s_1, s_2, \ldots, s_n (1 \le s_i \le 10^9) - the powers of the gods. Each of the following lines contains queries in the following format.
First comes the request type . If type = 1, then the line contains two integers and (1 \le l \le r \le n), meaning that the power of gods with numbers from to has decreased.
If type = 2, then the line contains three integers , , (1 \le l \le r \le n, 1 \le x \le 10^9) - the number of the first god, the number of the last god and the initial power of Kratos in the next plan.
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 .
Example 1
Example 2
In the first query of the first example, Kratos' starting power is . After the first battle, it is \lfloor 61 / 1 \rfloor = 61. Then it is equal to , , , , and respectively.