Under construction

Still being built. Things may change

Sequence and Queries 22

Time limit1sMemory limit512 MB

Summary
Given a sequence and a stream of updates and range-sum queries, answer each query for the sequence state after its k-th update only, where k can be any earlier prefix of updates.
Level

Hard8 of 10

Topics
Segment tree, Divide and conquer, Prefix sum, Binary search
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 v: change Ai to v.
  • 2 k i j: print the sum of Ai, Ai+1, ..., Aj when the first k type 1 queries have been applied.

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).

Each of the next M lines gives one query. For a type 1 query, 1 ≤ i ≤ N and 1 ≤ v ≤ 1,000,000. For a type 2 query, 1 ≤ i ≤ j ≤ N and 0 ≤ k ≤ (the number of type 1 queries that have appeared up to the point the query is given).

Every number in the input is an integer.

Output

For each type 2 query, print the sum.

Examples1

  1. Example 1

    Input
    5
1 2 3 4 5
7
1 2 5
2 0 1 3
2 1 1 3
1 4 2
2 0 2 5
2 1 2 5
2 2 2 5
    Expected output
    6
9
14
17
15