描述

给定一个长度为 n 的数列和 n 个涉及区间加法和单点查值的操作。

格式

输入

• 第一行包含一个整数 n。

• 第二行包含 n 个整数，其中第 i 个整数表示为 a_i，用空格分隔。

• 接下来的 n 行表示查询。每行包含四个整数 opt、l、r 和 c，用空格分隔。

  如果 opt = 0，表示将位于 [l, r] 区间的所有数字都加上 c。

  如果 opt = 1，表示查询 a_r 的值（忽略 l 和 c）。

输出

对于每次查询，输出一行包含一个整数，表示答案。

样例

输入

4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0

输出

2
5

限制

对于100%的数据，1 ≤ n ≤ 50000，且**-2^31 ≤ others, ans ≤ 2^31-1**。