Гриша пришел на контест и увидел там следующую задачу.
Дан массив длины \(n\), изначально состоящий из нулей. Элементы массива пронумерованы от \(1\) до \(n\). К массиву было применено \(q\) операций. \(i\)-я операция задается тремя целыми числами \(l_i\), \(r_i\) и \(x_i\) (\(1 \leq l_i \leq r_i \leq n\)), (\(1 \leq x_i \leq n\)) и означает, что к элементам с номерами \(l_i, l_i + 1, \ldots, r_i\) прибавили число \(x_i\). Требуется найти максимум в массиве после применения всех этих операций.
Но Гриша не из глупых! Он решил эту задачу очень быстро.
Однако что-то в нем переклинило, и он задумался: «интересно, а какие значения может принять максимум в массиве после применения некоторого подмножества данных операций?».
Помогите Грише, найдите все такие целые числа \(y\) от \(1\) до \(n\), что после применения некоторого (возможно, пустого) подмножества данных операций максимум в массиве равен \(y\).
Выходные данные
В первую строку выведите единственное число \(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)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 3 1
2 4 2
3 4 4
|
4
1 2 3 4
|
|
2
|
7 2
1 5 1
3 7 2
|
3
1 2 3
|
|
3
|
10 3
1 1 2
1 1 3
1 1 6
|
6
2 3 5 6 8 9
|