One cold and foggy night, you walk down a shady alley.
There should be a lamp every few metres but none of them seem to work, and in this night, not even the moon enlightens your path.
Alone and in the dark, you wonder:
"Even if there was a working lamp somewhere, how much would it lighten my way".
Now, back at home, you want to calculate this.
The alley can be modelled as a line with a length of metres.
The fog has a uniform density and reduces the light of a lamp by a factor of every metre.
The brightness at one point is the sum of the light that reaches this point from every lamp.
You want to calculate this brightness at some points after placing some lamps.
输入格式
The input consists of:
One line with two integers and and one real number (), the length of the alley, the number of queries and the density of the fog. The density of the fog will be given with at most digits behind the decimal point.
lines containing one of three query types:
"" given two integers and ( and ), place a lamp with brightness at position .
"" given integers and ( and ), remove a lamp with brightness at position . It is guaranteed that a lamp with that brightness was placed there earlier.
"" given one integer (), calculate the brightness at position .
输出格式
It can be shown that the brightness can be calculated as a fraction where is not divisible by . For each query of type "", print the brightness as in a single line.
样例
样例输入 1
5 6 0.25
+ 4 2
? 1
? 2
? 3
? 4
? 5
样例输出 1
3
4
3
250000004
187500003
样例输入 2
5 7 0.33
+ 9 1
? 5
+ 4 3
? 2
? 5
- 9 1
? 2
样例输出 2
312342734
470000012
341542736
760000008
数据范围与提示
In the first sample case, the brightness in the alley after placing the lamp will look like this:
