커피숍 게임 2

커피숍에서 다음과 같은 게임을 한다.

처음에 $N$개의 정수가 일렬로 놓여 있다. 한 턴은 두 단계로 이루어진다.

1. 두 위치 $x$, $y$가 주어지면, 현재 배열에서 $x$번째 수부터 $y$번째 수까지의 합을 구한다.
2. 위치 $a$와 값 $b$가 주어지면, $a$번째 수를 $b$로 바꾼다.

각 턴마다 구해야 하는 구간 합을 모두 출력하는 프로그램을 작성하라.

첫째 줄에 수의 개수 $N$과 턴의 개수 $Q$가 주어진다. $(1 \le N, Q \le 100,000)$

둘째 줄에는 처음 배열에 들어 있는 정수 $N$개가 주어진다.

셋째 줄부터 $Q$개의 줄에는 한 턴을 나타내는 네 정수 $x$, $y$, $a$, $b$가 주어진다. 이는 현재 배열에서 $x$번째 수부터 $y$번째 수까지의 합을 구한 뒤, $a$번째 수를 $b$로 바꾸라는 뜻이다.

입력되는 모든 정수는 $-2^{31}$ 이상 $2^{31}-1$ 이하이다.

각 턴에서 구한 구간 합을 한 줄에 하나씩 출력한다.

보통 $x \sim y$는 $x$번째 수부터 $y$번째 수까지를 뜻한다. 이 문제에서는 $x > y$인 경우에도 같은 규칙을 적용해, $y$번째 수부터 $x$번째 수까지의 합을 구한다.