Under construction

Still being built. Things may change

Sequence and Queries 21

Interview

Time limit2sMemory limit512 MB

Summary
Support range-add updates and point queries on an array of up to 100,000 elements with up to 100,000 operations.
Level

Medium4 of 10

Topics
Array, Prefix sum, Implementation
Solved
No attempts yet

Problem

A sequence A1, A2, ..., AN of length N is given. Write a program that performs the following queries.

  • 1 i j k: add k to Ai, Ai+1, ..., Aj.
  • 2 x: print Ax.

Input

The first line gives the size of the sequence N (1 ≤ N ≤ 100,000).

The second line gives A1, A2, ..., AN. (1 ≤ Ai ≤ 1,000,000)

The third line gives the number of queries M (1 ≤ M ≤ 100,000).

M lines follow, one query per line. For a type 1 query, 1 ≤ i ≤ j ≤ N and -1,000,000 ≤ k ≤ 1,000,000; for a type 2 query, 1 ≤ x ≤ N. At least one type 2 query is given.

Output

Print a value for each type 2 query.

Examples1

  1. Example 1

    Input
    5
1 2 3 4 5
4
1 3 4 6
2 3
1 1 3 -2
2 3
    Expected output
    9
7