Question
Magic Array Updates
You are asked to work with a phantom array arr of size 10^9, initially filled with zeros.
You need to process two types of operations:
-
Update Queries (
q1queries): Each query has the forml r x, meaning:-
Add
xto every element in the subarrayarr[l], arr[l+1], …, arr[r].
-
-
Point Queries (
q2queries): Each query gives an indexi, and you must return the final value ofarr[i]after applying all updates.
Input
The first line contains two integers q1, q2 — the number of update queries and the number of point queries.
The next q1 lines each contain three integers l r x — meaning add x to all indices from l to r.
The next q2 lines each contain a single integer i — meaning query the final value of arr[i].
The next q1 lines each contain three integers l r x — meaning add x to all indices from l to r.
The next q2 lines each contain a single integer i — meaning query the final value of arr[i].
Output
Print q2 integers, where the k-th integer is the result of the k-th query.
Example
Input
3 3
1 3 2
2 5 1
4 4 5
1
4
5
Output
2
6
1
Explanation
After the updates:
- Add 2 to indices [1, 3]
- Add 1 to indices [2, 5]
- Add 5 to index [4]
Final values for the queries are:
arr[1] = 2
arr[4] = 6
arr[5] = 1
3 3
1 3 2
2 5 1
4 4 5
1
4
5
Output
2
6
1
Explanation
After the updates:
- Add 2 to indices [1, 3]
- Add 1 to indices [2, 5]
- Add 5 to index [4]
Final values for the queries are:
arr[1] = 2
arr[4] = 6
arr[5] = 1