Coffee Shop Game 2

Interview

Time limit2sMemory limit256 MB

Summary

Given an array, answer Q online queries each asking a range sum (with swapped bounds allowed) followed by a point update.

Level: Medium4 of 10
Topics: Segment tree, Prefix sum, Array
Solved: No attempts yet

Problem

A game is played in a coffee shop.

Initially, there are $N$ integers arranged in a row. Each turn has two steps.

Given two positions $x$ and $y$ , find the sum of the current array from the $x$ -th number through the $y$ -th number.
Given a position $a$ and a value $b$ , replace the $a$ -th number with $b$ .

Write a program that prints the required range sum for every turn.

Input

The first line contains the number of integers $N$ and the number of turns $Q$ . $(1 \le N, Q \le 100,000)$

The second line contains the initial $N$ integers in the array.

Each of the next $Q$ lines contains four integers $x$ , $y$ , $a$ , and $b$ , describing one turn. First find the sum from the $x$ -th number through the $y$ -th number in the current array, then replace the $a$ -th number with $b$ .

Every integer in the input is between $-2^{31}$ and $2^{31}-1$ , inclusive.

Output

For each turn, output the computed range sum on its own line.

Hint

Normally, $x \sim y$ means from the $x$ -th number through the $y$ -th number. In this problem, if $x > y$ , compute the sum from the $y$ -th number through the $x$ -th number instead.

Examples1

Example 1
Input
```
5 2
1 2 3 4 5
2 3 3 1
3 5 4 1
```
Expected output
```
5
10
```