Bob has n heap(s) of gravel (initially there are exactly c piece(s) in each). He wants to do m operation(s) with that heaps, each maybe:

- adding pieces of gravel onto the heaps from u to v, exactly k pieces for each,
- or querying "how many pieces of gravel are there in the heap p now?".

-----Request-----
Help Bob do operations of the second type.

-----Input-----

- The first line contains the integers n,m,c, respectively.
- m following lines, each forms:

- S u v k to describe an operation of the first type.
- Q p to describe an operation of the second type.
(Each integer on a same line, or between the characters S, Q and the integers is separated by at least one space character)

-----Output-----
For each operation of the second type, output (on a single line) an integer answering to the respective query (follows the respective Input order).

-----Example-----Input:
7 5 0
Q 7
S 1 7 1
Q 3
S 1 3 1
Q 3
Output:
0
1
2

-----Limitations-----
- 0<n≤106
- 0<m≤250 000
- 0<u≤v≤n
- 0≤c,k≤109
- 0<p≤n

Difficulty: MEDIUM_HARD
Tags: Range queries

Data structures

Implementation

Segment trees revisited
Skill types: Data structures

Range queries

Starter code:

Solutions:
(N, M, C) = list(map(int, input().split()))
tree = [0] * (N + 1)

def add(u, k):
	while u < len(tree):
		tree[u] += k
		u += u & -u

def query(k):
	ans = 0
	while k:
		ans += tree[k]
		k -= k & -k
	return ans

def solve():
	for _ in range(M):
		op = input().split()
		if op[0] == 'Q':
			print(query(int(op[1])) + C)
		else:
			(u, v, k) = (int(op[1]), int(op[2]), int(op[3]))
			add(u, k)
			add(v + 1, -k)

def __starting_point():
	solve()
__starting_point()


(n, m, val) = list(map(int, input().split()))
fenwick = [0] * (n + 1)

def add(idx, val):
	while idx <= n:
		fenwick[idx] += val
		idx += idx & -idx

def interval_add(xxx_todo_changeme):
	(right, left, val) = xxx_todo_changeme
	add(right, val)
	add(left + 1, -val)

def val_at(idx):
	ret = 0
	while idx:
		ret += fenwick[idx]
		idx -= idx & -idx
	return ret + val
for _ in range(m):
	q = input().split()
	if q[0] == 'Q':
		print(val_at(int(q[1])))
	else:
		interval_add(list(map(int, q[1:])))


import sys
(n, m, c) = map(int, sys.stdin.readline().split())
bit = [0] * (n + 1)

def add(index, val):
	index += 1
	while index <= n:
		bit[index] += val
		index += index & -index

def get(index):
	r = 0
	index += 1
	while index:
		r += bit[index]
		index -= index & -index
	return r
while m:
	m -= 1
	op = sys.stdin.readline().split()
	if len(op) == 4:
		(_, u, v, k) = op
		u = int(u)
		v = int(v)
		k = int(k)
		u -= 1
		v -= 1
		add(u, k)
		add(v + 1, -k)
	else:
		(_, p) = op
		p = int(p)
		print(get(p - 1) + c)


def update(fenwick, n, ind, val):
	while ind <= n:
		fenwick[ind] += val
		ind += ind & -ind

def get(arr, ind):
	su = 0
	while ind > 0:
		su += arr[ind]
		ind -= ind & -ind
	return su
(n, m, c) = list(map(int, input().strip().split(' ')))
fenwick = [0] * (n + 1)
for z in range(m):
	s = list(map(str, input().strip().split(' ')))
	if s[0] == 'S':
		update(fenwick, n, int(s[1]), int(s[3]))
		update(fenwick, n, int(s[2]) + 1, -int(s[3]))
	else:
		print(get(fenwick, int(s[1])) + c)


def bitadd(tree, index, value):
	index += 1
	while index < len(tree):
		tree[index] += value
		index += index & -index

def bitsum(tree, index):
	index += 1
	result = 0
	while index:
		result += tree[index]
		index -= index & -index
	return result
(n, m, c) = list(map(int, input().split()))
tree = [0 for _ in range(n + 1)]
for _ in range(m):
	q = input().split()
	if q[0] == 'Q':
		print(bitsum(tree, int(q[1]) - 1) + c)
	else:
		u = int(q[1])
		v = int(q[2])
		k = int(q[3])
		bitadd(tree, u - 1, k)
		bitadd(tree, v, -k)


(n, m, c) = list(map(int, input().split()))
bit = [0] * (n + 1)

def add(index, val):
	index += 1
	while index <= n:
		bit[index] += val
		index += index & -index

def get(index):
	r = 0
	index += 1
	while index:
		r += bit[index]
		index -= index & -index
	return r
while m:
	m -= 1
	op = input().split()
	if len(op) == 4:
		(_, u, v, k) = op
		u = int(u)
		v = int(v)
		k = int(k)
		u -= 1
		v -= 1
		add(u, k)
		add(v + 1, -k)
	else:
		(_, p) = op
		p = int(p)
		print(get(p - 1) + c)