Gems (GEM)

Time limit2sMemory limit512 MB

Summary

Given range-sum constraints modulo 10 on an array of N values each in [0,100], find the lexicographically smallest valid array or report -1 if the constraints conflict.

Level: Medium7 of 10
Topics: Union-find, Prefix sum, Graph, Greedy
Solved: No attempts yet

Problem

Seonhong keeps a flower bed in the front yard. The bed is a row of $N$ plots numbered 1 to $N$ from the left, and every plot holds between 0 and 100 gems.

One day Seonhong heard a rumor that gems might be buried in the bed and decided to check with a metal detector. Given two numbers $s$ and $e$ , the detector sweeps plot $s$ through plot $e$ and reports the total number of gems buried in that range.

Seonhong swept the bed $M$ times and wrote down every result. Yeongmin walked by, tampered with the notes for fun, and left only the last digit of each result. Seonhong then told Yeongmin to recover the gem count of every plot from those digits alone. Help Yeongmin and find counts that do not contradict the notes.

Input

The first line has the number of plots $N$ and the number of sweeps $M$ , separated by a space. ( $1 \le N \le 10^5$ , $1 \le M \le 10^5$ )

Each of the next $M$ lines has $s_i$ , $e_i$ and $c_i$ separated by spaces. Sweep $i$ covered the range $[s_i, e_i]$ , and the last digit of the total number of gems in that range was $c_i$ . ( $1 \le s_i \le e_i \le N$ , $0 \le c_i \le 9$ )

Output

Print the gem count of plot 1 through plot $N$ on one line, separated by spaces. Every value must be an integer between 0 and 100, and all $M$ sweeps must come out right.

If several arrays satisfy the sweeps, print only the lexicographically smallest one. Array $a$ is lexicographically smaller than array $b$ when $a_i < b_i$ at the first position $i$ where the two arrays differ.

If the notes contradict each other and no array works, print -1 alone.

Examples7

Example 1
Input
```
5 4
1 2 4
2 5 3
3 4 1
1 4 5
```
Expected output
```
0 4 0 1 8
```
Example 2
Input
```
5 3
1 3 4
1 4 3
4 4 8
```
Expected output
```
-1
```
Example 3
Input
```
1 1
1 1 7
```
Expected output
```
7
```
Example 4
Input
```
1 2
1 1 3
1 1 4
```
Expected output
```
-1
```

Example 5

Input

Expected output

0 9 5 0 1 4

Example 6
Input
```
4 1
2 3 5
```
Expected output
```
0 0 5 0
```
Example 7
Input
```
2 2
1 2 0
1 1 9
```
Expected output
```
9 1
```