ChrisT is feeling hungry. He has snacks lined up in a row, numbered from ~1~ to ~N~. Each snack has ~C_i~ calories. Because ChrisT doesn't want to get too thicc, he would like to know the number of calories in snack number ~i~. However, his house has a squirrel infestation! The squirrels like to leave nuts or eat part of the snacks from number ~l~ to number ~r~, inclusive. Please help ChrisT!

Input Specification

The first line contains the integer ~N\ (1 \le N \le 10^5)~, the number of snacks.

The next line will contain ~N~ space-separated integers ~C_i\ (1 \le C_i \le 10^8)~, the number of calories in each snack.

The next line contains the integer ~Q\ (1 \le Q \le 10^5)~, the number of queries.

The next ~Q~ lines will contain a query of 2 forms:

1 i, meaning that ChrisT wants to know the number of calories in snack ~i\ (1 \le i \le N)~;

2 l r v, meaning that snacks from number ~l~ to ~r\ (1 \le l \le r \le N)~ had the number of calories increase by ~v\ (0 \le |v| \le 10^8)~.

Output Specification

For every query of form 1 i, print the number of calories in snack number ~i~ on its own line.

Constraints

Subtask 1 [30%]

~(1 \le N \le 10^4),\ (1 \le Q \le 10^4),\ (1 \le C_i, v \le 10^5)~

Subtask 2 [70%]

No additional constraints.

Sample Input

5
1 2 5 3 9
7
1 1
2 3 5 7
1 4
2 1 2 2
1 2
2 1 4 4
1 3

Sample Output

1
10
4
16

Notes

Squirrels can get so full from eating snacks that they use the bag as a washroom, meaning that snacks can have negative calories.