M. Hiya Ti7 Wena Ntala3ha
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You have a number $$$x$$$, initially equal to $$$S$$$.

There are $$$N$$$ types of operations available. Each operation $$$i$$$ is described by:

- a range $$$[l_i, r_i]$$$

- an integer $$$d_i$$$

An operation $$$i$$$ can be applied only if the current value of $$$x$$$ satisfies $$$l_i \le x \le r_i$$$.

When applied, the operation reduces $$$x$$$ by exactly $$$d_i$$$: $$$x := x - d_i$$$.

You may apply any operation any number of times, as long as its condition is satisfied at the moment of application. Each application counts as one step.

Your goal is to reduce $$$x$$$ to exactly $$$0$$$ using the minimum number of steps.

If there are multiple sequences of operations that achieve this using the minimum number of steps, output the lexicographically smallest sequence of applied $$$d_i$$$ values.

If there is no solution your answer should be $$$-1$$$.

Input

An integer $$$S$$$ ($$$1 \le S \le 10^6$$$), the initial value of $$$x$$$.

An integer $$$N$$$ ($$$1 \le N \le 10^6$$$), the number of operations.

The next $$$N$$$ lines each contain three integers: $$$l_i, r_i$$$ and $$$d_i$$$ where $$$(1 \le l_i \le r_i \le S)$$$ and $$$(1 \le d_i \le l_i)$$$

- Operation ranges may overlap.

- The sum of all ($$$r_i-l_i+1$$$) does not exceed $$$2 \times 10^7$$$.

Output

Print an integer $$$m$$$: the minimum number of steps required. Then print $$$m$$$ integers — the values $$$d_i$$$ used, in the order they are applied.

If there is no solution, print $$$-1$$$.

Examples
Input
10 2
1 10 1
5 10 5
Output
2
5 5
Input
15 3
1 15 1
3 12 3
7 15 7
Output
3
1 7 7
Note

Lexicographical Order:

Given two integer sequences $$$A$$$ and $$$B$$$ of equal length, $$$A$$$ is lexicographically smaller than $$$B$$$ if at the first position where they differ, $$$A$$$ has a smaller value than $$$B$$$. Example: $$$[1, 24, 3]$$$ is lexicographically smaller than $$$[1, 112, 3]$$$ because at the first position where they differ (the second position), $$$24 \le 112$$$.