Coffee Shop Game 2

A game is played in a coffee shop.

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

1. Given two positions $x$ and $y$, find the sum of the current array from the $x$-th number through the $y$-th number.
2. 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.

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.

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

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.