You are given an array of ~n~ integers and must process ~q~ queries of the following types:

1. Increase every value in the range ~[l, r]~ by ~u~.
2. Report the value at position ~k~.

Positions are 1-indexed.

Input

The first line contains the integer ~n~.

The second line contains ~n~ integers ~x_1, \ldots, x_n~: the initial values of the array.

The third line contains the integer ~q~.

Each of the next ~q~ lines describes a query and is one of the following:

• 1 l r u: add ~u~ to every value in the range ~[l, r]~
• 2 k: query the value at position ~k~

Output

For each query of type 2, output a line containing the value at position ~k~.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le q \le 10^5~
• ~1 \le x_i, u \le 10^9~
• ~1 \le k \le n~
• ~1 \le l \le r \le n~

Example 1

Input

5
8 8 6 7 9 
10
1 1 4 3
1 4 5 9
1 1 4 1
2 4
2 3
2 3
2 2
1 1 2 9
1 4 5 1
2 5

Output

20
10
10
12
19

Hints

Hint 1

Try converting this from a range-update / point-query problem into a point-update / range-query problem.