10292: CF EDU - Segment Tree P2 - Step 3 - C. Addition and First element at least X
[Creator : ]
Description
There is an array of $n$ elements, initially filled with zeros. You need to write a data structure that processes two types of queries:
- add $v$ to all elements on the segment from $l$ to $r−1$,
- find the minimum index $j$ such that $j≥l$ and $a[j]≥x$.
Input
The first line contains two numbers $n,m\ (1≤n,m≤100,000)$, the size of the array and the number of operations.
The following lines contain the desc
- 1 l r v: add $v$ to all elements on the segment from $l$ to $r−1\ (0≤i<n,\ 0≤v≤10^4)$.
- 2 x l: find the minimum index $j$ such that $j≥l$ and $a[j]≥x\ (0≤x≤10^9,\ 0≤l<n)$. If there is no such element, print −1.
Output
For each operation of the second type, print the answer for the query.
Sample 1 Input
5 7
1 2 5 3
1 1 3 4
2 3 0
2 5 0
1 4 5 5
2 5 3
2 8 1
Sample 1 Output
1
2
4
4