보석 (GEM)

선홍이는 집 앞마당에 일렬로 놓인 $N$개의 칸으로 된 화단을 가꾸고, 왼쪽부터 차례로 1번부터 $N$번까지 번호를 붙였다. 칸마다 보석이 0개 이상 100개 이하로 묻혀 있다.

어느 날 선홍이는 화단에 보석이 묻혀 있을지도 모른다는 소문을 듣고 금속 탐지기로 확인하기로 했다. 이 탐지기는 두 수 $s$와 $e$를 지정하면 $s$번 칸부터 $e$번 칸까지 훑어서 그 구간에 묻힌 보석의 총 개수를 알려준다.

선홍이는 탐지기로 화단을 $M$번 조사하고 결과를 모두 적어 두었다. 그런데 지나가던 영민이가 장난으로 기록을 고쳐 각 결과의 일의 자리 숫자만 남겨 놓았다. 선홍이는 영민이에게 이 기록만으로 각 칸의 보석 개수를 알아내라고 시켰다. 영민이를 대신해 기록과 어긋나지 않는 보석 개수를 구하자.

첫째 줄에 화단 칸의 개수 $N$과 탐지 횟수 $M$이 공백을 사이에 두고 주어진다. ($1 \le N \le 10^5$, $1 \le M \le 10^5$)

둘째 줄부터 $M$개의 줄에 각각 $s_i$, $e_i$, $c_i$가 공백을 사이에 두고 주어진다. $i$번째 탐지에서 $[s_i, e_i]$ 구간을 훑었고, 그 구간에 묻힌 보석 개수의 일의 자리 숫자가 $c_i$였다는 뜻이다. ($1 \le s_i \le e_i \le N$, $0 \le c_i \le 9$)

1번 칸부터 $N$번 칸까지 각 칸의 보석 개수를 공백으로 구분해 한 줄에 출력한다. 각 값은 0 이상 100 이하의 정수여야 하고, $M$번의 탐지 결과와 모두 맞아야 한다.

조건을 만족하는 배열이 여러 개면 사전순으로 가장 앞서는 배열 하나만 출력한다. 배열 $a$가 배열 $b$보다 사전순으로 앞선다는 것은 두 배열이 처음으로 달라지는 위치 $i$에서 $a_i < b_i$라는 뜻이다.

기록에 모순이 있어 조건을 만족하는 배열이 하나도 없으면 -1만 출력한다.