Alternierende Summe
Sie haben ein Array von
n ganzen Zahlen und q Abfragen. Es gibt zwei Arten von Abfragen: Zum einen können Sie das Array an einem bestimmten Index p aktualisieren, zum anderen können Sie die alternierende Summe eines Teilarrays [l; r] berechnen.Die alternierende Summe eines Teilarrays
[l; r] ist definiert als die Summe der Elemente auf geraden Indizes minus der Summe der Elemente auf ungeraden Indizes innerhalb dieses Teilarrays. Anders ausgedrückt, wenn das Teilarray [l; r] die Elemente hat, dann berechnet sich die alternierende Summe folgendermaßen: .Für jede Abfrage des Typs 2 müssen Sie die alternierende Summe des angegebenen Teilarrays
[l; r] berechnen und ausgeben.Input
Die erste Zeile enthält zwei ganze Zahlen
n und q, die die Größe des Arrays und die Anzahl der Abfragen angeben (1 ≤ n, q ≤ ).
Die zweite Zeile enthält n durch Leerzeichen getrennte ganze Zahlen (), die die Elemente des Arrays darstellen.
Die folgenden q Zeilen beschreiben jeweils eine Abfrage und haben die Form 1 l r oder 2 p x, wobei 1 eine Abfrage bezeichnet, um die alternierende Summe im Teilarray [l; r] zu berechnen, und 2 eine Aktualisierungsabfrage an Index p mit Wert x kennzeichnet (1 ≤ p ≤ n, 1 ≤ x ≤ , 1 ≤ l ≤ r ≤ n).Output
Für jede Abfrage des Typs 2 geben Sie die berechnete alternierende Summe in einer eigenen Zeile aus.
Examples
Input | Output |
8 3
1 2 3 4 5 6 7 8
1 2 6
2 4 9
1 1 8 | 4
-9 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB