Read problem statements in [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$. Chef wants you to handle $Q$ queries. There are two types of queries:
1 L R X: for each $i$ ($L ≤ i ≤ R$), add $(X + i - L)^2$ to $A_{i}$
2 Y: find the current value of $A_{Y}$

------  Input ------
The first line of the input contains two space-separated integers $N$ and $Q$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.
$Q$ lines follow. Each of these lines describes a query in the format described above.

------  Output ------
For each query of the second type, print a single line containing one integer $A_{Y}$.

------  Constraints ------
$1 ≤ N, Q ≤ 10^{5}$
$0 ≤ |A_{i}| ≤ 10^{6}$ for each valid $i$
$1 ≤ L ≤ R ≤ N$
$0 ≤ |X| ≤ 10^{6}$
$1 ≤ Y ≤ N$

----- Sample Input 1 ------ 
5 4
1 10 3 6 5
1 1 3 5
2 3
1 4 5 7
2 5
----- Sample Output 1 ------ 
52
69
----- explanation 1 ------ 
- the sequence after the first query is $[1 + 5^{2}, 10 + (5 + 2 - 1)^2, 3 + (5 + 3 - 1)^2, 6, 5] = [26,  46, 52, 6, 5]$
- the second query asks for $A_{3}$, which is $52$
- the sequence after the third query is $[26,  46, 52, 6 + 7^{2}, 5 + (7+1)^2] = [26,  46, 52, 55, 69]$
- the fourth query asks for $A_{5}$, which is $69$

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
class Ftree:

	def __init__(self, N):
		self.st = [0] * (N + 1)
		self.n = N

	def Update(self, l, r, diff):
		while l <= self.n:
			self.st[l] += diff
			l += l & -l
		r += 1
		while r <= self.n:
			self.st[r] -= diff
			r += r & -r

	def Query(self, i):
		sum = 0
		while i > 0:
			sum += self.st[i]
			i -= i & -i
		return sum

def main():
	(n, q) = input().split()
	N = int(n)
	Q = int(q)
	A = [int(e) for e in input().split()]
	A.insert(0, 0)
	b1 = Ftree(N)
	b2 = Ftree(N)
	b3 = Ftree(N)
	while Q != 0:
		q = list(map(int, input().split()))
		if q[0] == 1:
			L = q[1]
			R = q[2]
			X = q[3]
			y = X - L
			b1.Update(L, R, y ** 2)
			b2.Update(L, R, 2 * y)
			b3.Update(L, R, 1)
		else:
			i = q[1]
			print(A[i] + b1.Query(i) + b2.Query(i) * i + b3.Query(i) * i * i)
		Q -= 1
main()


class Fenwick:

	def __init__(self, n):
		self.bits = [0] * (n + 1)

	def add(self, i, v):
		i += 1
		while i <= n:
			self.bits[i] += v
			i += i & -i

	def rnge(self, l, r, x):
		self.add(l, x)
		self.add(r + 1, -x)

	def get(self, i):
		i += 1
		ans = 0
		while i > 0:
			ans += self.bits[i]
			i -= i & -i
		return ans
(N, Q) = input().split()
n = int(N)
q = int(Q)
f1 = Fenwick(n)
f2 = Fenwick(n)
f3 = Fenwick(n)
arr = [int(i) for i in input().split()]
for i in range(q):
	t = [int(i) for i in input().split()]
	if t[0] == 1:
		l = t[1] - 1
		r = t[2] - 1
		x = t[3]
		f1.rnge(l, r, 1)
		f2.rnge(l, r, (x - l - 1) * (x - l - 1))
		f3.rnge(l, r, 2 * (x - l - 1))
	else:
		j = t[1]
		k = arr[j - 1] + j * j * f1.get(j - 1) + f2.get(j - 1) + j * f3.get(j - 1)
		print(k)


def update_BIT(BIT, n, i, val, j):
	while i <= n:
		BIT[i][j] += val
		i += i & -i

def get_sum(BIT, i, j):
	ret = 0
	while i > 0:
		ret += BIT[i][j]
		i -= i & -i
	return ret
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
bit = []
for i in range(n + 1):
	bit.append([0, 0, 0])
for _ in range(q):
	b = list(map(int, input().split()))
	if b[0] == 1:
		l = b[1]
		r = b[2]
		x = b[3]
		update_BIT(bit, n, l, 1, 0)
		update_BIT(bit, n, r + 1, -1, 0)
		update_BIT(bit, n, l, pow(x - l, 2), 1)
		update_BIT(bit, n, r + 1, -pow(x - l, 2), 1)
		update_BIT(bit, n, l, 2 * (x - l), 2)
		update_BIT(bit, n, r + 1, -2 * (x - l), 2)
	else:
		x = b[1]
		ans = a[x - 1] + get_sum(bit, x, 0) * pow(x, 2) + get_sum(bit, x, 1) + get_sum(bit, x, 2) * x
		print(ans)


def update_range(BIT, i, n, val):
	i += 1
	while i <= n:
		BIT[i] += val
		i += i & -i

def get(BIT, i):
	i += 1
	s = 0
	while i > 0:
		s = s + BIT[i]
		i = i - (i & -i)
	return s

def update(BIT, l, r, n, val):
	update_range(BIT, l, n, val)
	update_range(BIT, r + 1, n, -val)
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
BIT1 = [0] * (n + 1)
BIT2 = [0] * (n + 1)
BIT3 = [0] * (n + 1)
for i in range(q):
	k = list(map(int, input().split()))
	if k[0] == 1:
		(l, r, x) = (k[1] - 1, k[2] - 1, k[3])
		update(BIT1, l, r, n, (x - l) * (x - l))
		update(BIT2, l, r, n, 2 * (x - l))
		update(BIT3, l, r, n, 1)
	else:
		y = k[1] - 1
		ans = arr[y] + get(BIT1, y) + y * get(BIT2, y) + y * y * get(BIT3, y)
		print(ans)


N = 131072

class SegmentTree:

	def __init__(self):
		self.array = [0 for i in range(2 * N)]

	def add_range(self, left, right, x, i=1, l=1, r=N):
		if l >= left and r <= right:
			self.array[i] += x
			return
		m = (l + r) // 2
		if m >= left:
			self.add_range(left, right, x, i * 2, l, m)
		if m + 1 <= right:
			self.add_range(left, right, x, i * 2 + 1, m + 1, r)

	def get_value(self, index):
		value = 0
		i = N + index - 1
		while i > 0:
			value += self.array[i]
			i //= 2
		return value
segment_trees = [SegmentTree() for i in range(3)]
(n, n_query) = (int(x) for x in input().split())
offset = [None] + [int(x) for x in input().split()]
for query in range(n_query):
	operation = [int(x) for x in input().split()]
	if operation[0] == 1:
		(left, right, x) = operation[1:]
		y = x - left
		segment_trees[0].add_range(left, right, y ** 2)
		segment_trees[1].add_range(left, right, 2 * y)
		segment_trees[2].add_range(left, right, 1)
	if operation[0] == 2:
		index = operation[1]
		answer = offset[index] + sum((segment_trees[i].get_value(index) * index ** i for i in range(3)))
		print(answer)


class FenwickTree:

	def __init__(self, arg):
		self.arg = arg + 1
		self.arr = [0] * (arg + 1)

	def update(self, i, delta):
		i += 1
		while i < self.arg:
			self.arr[i] += delta
			i += i & -i

	def range_update(self, L, R, value):
		self.update(L, value)
		self.update(R + 1, -value)

	def get(self, i):
		ans = 0
		i += 1
		while i > 0:
			ans += self.arr[i]
			i -= i & -i
		return ans

	def pp(self):
		print(self.arr)
(n, q) = map(int, input().split())
f1 = FenwickTree(n)
f2 = FenwickTree(n)
f3 = FenwickTree(n)
A = list(map(int, input().split()))
for _ in range(q):
	operation = list(map(int, input().split()))
	if operation[0] == 1:
		l = operation[1] - 1
		r = operation[2] - 1
		x = operation[3]
		y = x - l - 1
		f1.range_update(l, r, 1)
		f2.range_update(l, r, y * y)
		f3.range_update(l, r, 2 * y)
	else:
		i = operation[1]
		ans = A[i - 1] + i * i * f1.get(i - 1) + f2.get(i - 1) + i * f3.get(i - 1)
		print(ans)


def updateBIT(BIT, i, n, val):
	i += 1
	while i <= n:
		BIT[i] += val
		i += i & -i

def get(BIT, i):
	i += 1
	s = 0
	while i > 0:
		s += BIT[i]
		i -= i & -i
	return s

def update(BIT, l, r, n, val):
	updateBIT(BIT, l, n, val)
	updateBIT(BIT, r + 1, n, -val)
(n, q) = map(int, input().split())
seq = list(map(int, input().split()))
BIT1 = [0] * (n + 1)
BIT2 = [0] * (n + 1)
BIT3 = [0] * (n + 1)
for i in range(q):
	qr = list(map(int, input().split()))
	if qr[0] == 1:
		y = qr[3] - qr[1]
		update(BIT1, qr[1] - 1, qr[2] - 1, n, y * y)
		update(BIT2, qr[1] - 1, qr[2] - 1, n, 2 * y)
		update(BIT3, qr[1] - 1, qr[2] - 1, n, 1)
	else:
		sum = seq[qr[1] - 1] + get(BIT1, qr[1] - 1) + get(BIT2, qr[1] - 1) * qr[1] + get(BIT3, qr[1] - 1) * qr[1] ** 2
		print(sum)


def range_update(bit, l, r, val):
	while l <= n:
		bit[l] += val
		l += l & -l
	r += 1
	while r <= n:
		bit[r] -= val
		r += r & -r

def getsum(bit, idx):
	s = 0
	while idx > 0:
		s += bit[idx]
		idx -= idx & -idx
	return s
(n, q) = map(int, input().split())
bit1 = [0] * (n + 1)
bit2 = [0] * (n + 1)
bit3 = [0] * (n + 1)
a = list(map(int, input().split()))
for _ in range(q):
	qr = list(map(int, input().split()))
	if qr[0] == 1:
		(l, r, x) = qr[1:]
		range_update(bit1, l, r, 1)
		range_update(bit2, l, r, (x - l) ** 2)
		range_update(bit3, l, r, 2 * (x - l))
	else:
		i = qr[1]
		print(a[i - 1] + i * i * getsum(bit1, i) + getsum(bit2, i) + i * getsum(bit3, i))