В первой строке заданы два числа $n$ и $q$~--- количество чисел в массиве и количество запросов ($1 \le n, q \le 2 \cdot 10^5$).

Во второй строке заданы $n$ чисел $x_1, x_2, \dots, x_n$~--- элементы массива ($1 \le x_i \le 10^6$).

Каждая из следующих $q$ строк содержит запрос в формате $l$, $r$, $S$ ($1 \leq l \leq r \leq n$; $1 \leq S \leq 10^9$).
