425. Вопросы про максимум

Петя собрал массив $a_1, a_2, \ldots, a_n$ длины $n$, изначально состоящий из нулей, втайне от вас промодифицировал его и стал задавать сложные вопросы про получившийся массив.

Вы знаете, что к массиву было применено подмножество таких операций, как прибавление на отрезке. Формально Петя применил некоторое подмножество из $q$ операций, $i$-я операция задаётся тремя целыми числами $l_i$, $r_i$ и $x_i$ ($1 \leq l_i \leq r_i \leq n$), ($1 \leq x_i \leq n$) и означает, что к элементам $a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i}$ прибавили число $x_i$.

Петя спрашивает, какие существуют целые числа от $1$ до $n$, которые могут соответствовать максимуму в массиве $a_i$. Ответьте ему на этот вопрос.

В первой строке находятся два целых числа $n$ и $q$ ($1 \leq n, q \leq 10^{4}$) — длина массива и количество операций.

В следующих $q$ строках описаны операции, по одной в строке. $i$-я из этих строк содержит три целых числа $l_i$, $r_i$ и $x_i$ ($1 \leq l_i \leq r_i \leq n$, $1 \leq x_i \leq n$), что обозначает операцию добавления числа $x_i$ на отрезке с $l_i$-го по $r_i$-й элемент включительно.

В первую строку выведите единственное число $k$, обозначающее количество возможных целых чисел от $1$ до $n$, которым может быть равен максимум в массиве после применения некоторого (возможно, пустого) подмножества данных операций.

В следующей строке выведите через пробел все $k$ чисел от $1$ до $n$ — возможные значения максимума. Выводите эти числа в возрастающем порядке.

Если в первом тестовом примере оставить только первый запрос, то максимум будет равен $1$. Если оставить только второй запрос, то максимум будет равен $2$. Если оставить первые два запроса, то максимум будет равен $3$. Если оставить только третий запрос, то максимум будет равен $4$. Но если оставить третий запрос и ещё какой-то, максимум будет больше $n$, поэтому его выводить не требуется.

Во втором тестовом примере, оставив только первый запрос, можно получить $1$. Оставив только второй, можно получить $2$. А если оставить все запросы, максимум будет равен $3$.

В третьем тестовом примере можно получить максимумы так:

• Можно получить максимум $2$, оставив запросы: $(1)$.
• Можно получить максимум $3$, оставив запросы: $(2)$.
• Можно получить максимум $5$, оставив запросы: $(1, 2)$.
• Можно получить максимум $6$, оставив запросы: $(3)$.
• Можно получить максимум $8$, оставив запросы: $(1, 3)$.
• Можно получить максимум $9$, оставив запросы: $(2, 3)$.