14933번 - 보석 (GEM) 스페셜 저지

선홍이는 집 앞마당에 일렬로 배치된 N(≤100,000)개의 칸으로 구성된 화단을 가꾸면서 왼쪽부터 차례로 1, 2, 3, … N의 번호를 붙여주었다. 어느 날 선홍이는 자신의 화단에 보석이 묻혀 있을 지도 모른다는 찌라시를 접하고는 금속 탐지기를 통해 보석을 파악하기로 마음 먹게 된다. 선홍이의 금속 탐지기는 s와 e라는 두 숫자를 지정해주면 s번 화단부터 e번 화단까지 돌며 그 구간 안에 있는 보석의 총 개수를 알려준다. (1≤s≤e≤N) 선홍이는 금속 탐지기를 통해 자신의 화단을 M(≤100,000)번 테스트해보고 그 결과를 적어놓았다. 때마침 지나가던 영민이는 평소 선홍이에게 괴롭힘 당한 것에 대한 분풀이를 하기 위해 보석 개수를 조작해 일의 자릿수만을 남겨 놓았다. 이 사실을 알고 화가 난 선홍이는 영민이를 불러 이 자료만을 가지고 각 칸에 있는 보석 개수를 유추해오라는 지시를 내렸다. 불쌍한 영민이를 도와주자 ㅠㅠ

첫째 줄에 화단의 개수 N과 테스트한 횟수 M이 주어진다.

둘째 줄부터 M개의 줄에는 공백을 사이에 두고 s_i, e_i, c_i가 주어진다. 이는 i번째 테스트에서 선홍이가 [s_i, e_i] 구간을 탐사했으며 그 구간의 보석 개수의 일의 자리 숫자가 c_i임을 의미한다. (1≤s_i≤e_i≤N, 0≤c_i≤9)

테스트 결과에 부합하게끔 각 칸의 보석 개수를 출력한다. 답이 여러 개라면 아무거나 출력해도 좋으며, 입력 자체에 모순이 있는 경우 -1을 출력한다. 각 칸에 묻혀 있는 보석의 수는 0이상 100이하의 정수여야 한다.

1번 예제에서는 4 0 0 1 2, 96 98 94 97 94 등도 답이 될 수 있다. 2번 예제를 만족하는 해는 없음을 쉽게 알 수 있으므로 -1을 출력한다.