The city council of the capitol city is interested in increasing the size of the buildings along their main street to attract more businesses, but they are worried that if they build too fast, they may run out of money, so they want to build their city in multiple phases.
Assume that the street is n units long and the buildings are one unit wide. In each phase, the council will choose two endpoints (1 ≤ a ≤ b ≤ 100,000) and increase the height of every building in between a and b (inclusively) by y units. For example, here is the sky-line of a city before and after the change: a = 2, b = 10, y = 1 (The numbers below the road are for your sanity).
X X ----> X X X X X XXXX X XXXXXX ____X__XXXXXX_XX__ _XXXXXXXXXXXX_XX__ 123456789012345678 123456789012345678
Keeping track of the heights of the buildings can be rather tricky over time, so we need your help.
Input file starts with a positive integer T on the first line, the number of instructions.
Each of the following T (T ≤ 100,000) lines will be in one of the following two formats:
B a b y : Building instruction - Increase the height of the buildings between a and b by y units. Q a : Query line - Output the height of building a at this point.Input lines are always valid, i.e., 1 ≤ a ≤ b ≤ 100,000. The value of y is a positive integer, at most 1,000. You can assume that the main street is completely flat before the first phase, i.e., height is zero for every building i in [1,100000].
For each query line, output the height of the specified building on a separate line.
9 B 5 5 2 B 8 8 2 B 10 13 1 Q 8 B 8 13 1 Q 8 B 15 16 1 B 2 10 1 Q 8
2 3 4