Problem D
Points of Snow
Lineland is an infinitesimal country primarily known for its 1-dimensional layout. However, it is also true that Lineland provides some truly excellent skiing opportunities for beginners.
You are running a snow depth information service that answers queries about how deep the snow is at various locations in Lineland. As your service is becoming increasingly popular, you realize that the traditional way of answering queries (i.e. by going on a ski trip to make a manual measurement) does not scale.
In order to speed things up, you made a deal with the national wheather forcaster. They have agreed to give you notice whenever snow falls or melts away across different strecthes of the country. What remains is to write a program that can answer incoming queries from the public automatically, provided the information from the wheather forcaster.
Input
The first line contains three integers $N$, $K$ and $Q$, indicating respectively the length of Lineland (in km), the number of wheather reports you receive over the course of the year, and the number of snow depth queries you get. The next $K+Q$ lines describes, in chronological order, either a snowfall or a melting incident for some segment of the country, or a query requesting to know the snow depth at some location.
The $i$’th such line begins with a characther $C_ i \in \{ \texttt{!}, \texttt{?}\} $. If $C_ i = \texttt{!}$, then three integers will follow, $L_ i$, $R_ i$ and $D_ i$, meaning that the snow level rose with $D_ i$ cm in the area between the $L_ i$’th and the $R_ i$’th km mark of Lineland. For snowfalls $D_ i$ is positive, whereas for melting incidents, $D_ i$ is negative.
If $C_ i = \texttt{?}$, then a single integer $X_ i$ will follow on the same line, indicating a query requsting to know the snow depth in the middle of the $X_ i$’th km of Lineland (e.g. if $X_ i = 1$, then you should report the snow depth at distance $0.5$km from the beginning of Lineland). The input will always adhere to the following constraints:
-
$1 \leq N \leq 1\, 000\, 000$
-
$1 \leq K, Q \leq 100\, 000$
-
$0 \leq L_ i < R_ i \leq N$
-
$-100\, 000 \leq D_ i \leq 100\, 000$
-
$1 \leq X_ i \leq N$
The snow level will at no point in time nor space be negative, e.g. for every location $x$, $0 \leq x < N$ and every time $k$, $0\leq k < K$ it holds that $\sum _{i=0}^ k \{ D_ i \mid L_ i \leq x < R_ i\} \geq 0$. At the beginning of the year, there is no snow; however, there might be snow left at the end of the year.
Output
Output $Q$ lines, one for each query, reporting the snow depth (in cm) at the requested location.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 4 2 ! 0 6 3 ! 3 9 5 ? 6 ! 2 7 -2 ! 5 7 1 ? 7 |
8 4 |
