Служба електропостачання проводить моніторинг рівня снігу, що лежить на ЛЕП. Уся ЛЕП розбивається на ділянки опорами. Сніг має властивості падати на якийсь інтервал ЛЕП, якщо там уже лежав якийсь сніг, то висота снігового покриву на цій ділянці підсумовується. Також сніг має тенденцію танути на ділянці траси в результаті відлиги, при цьому відомо, що не буває кучугур відʼємної висоти.

Енергетикам вкрай важливо вміти визначати сумарну висоту снігового покриву на деяких послідовних ділянках, щоб знати можливість обриву проводів.

Формат вхідних даних

У першому рядку містяться два числа: \(N\) – (\(1 ≤ N ≤ 10 000\)) та \(M\) – кількість команд (\(1 ≤ M ≤ 50 000\)). Кожна команда має вигляд "1 L R S", що означає, що на ділянку з \(L\)-ої опори по \(R\)-у опору випало \(S\) сантиметрів снігу (\(S\) може бути і відʼємним, тоді це означає, що така кількість снігу розтанула), або "2 L R" - запит сумарної висоти снігу на ділянці з \(L\)-ої опори по \(R\)-у. Опори нумеруються від 0 до \(N\). Гарантується, що для запитів виду “1 L R S” при \(S < 0\) на кожній ділянці між опорами \(L\) та \(R\) рівень снігу становить не менший за \(S\).

Формат вихідних даних

На кожну команду 2 (запит) ви повинні виводити число \(K\) - cумарну висоту снігового покриву, що лежить на проводах з \(L\)-ої опори по \(R\)-у. Кожне число має виводитись на новому рядку. Відомо, що у процесі роботи сумарна кількість снігу на будь-якому інтервалі не перевищує ~2^{31}.

Приклад вхідних даних

10 5
1 0 9 10
1 1 5 -3
2 4 8
1 0 6 25
2 0 2

Приклад вихідних даних

37
67