2081번 - 저울추 스페셜 저지

질량을 모르는 N개의 저울추가 있고, 각각 1부터 N까지 순서대로 번호가 매겨져 있다. 질량을 모르는 저울추는 쓸모가 없으므로, 모든 저울추의 질량을 알아내려고 한다.

정확한 질량을 알아내는 것은 불가능하지만, 저울추의 크기를 가늠하여 대략적인 비교를 해 볼 수 있다. 1번 추가 2번 추보다 크기가 꽤 크다면, 1번 추의 질량은 2번 추의 질량보다 클 것이라고 비교를 할 수 있다. 만약 1번 추가 2번 추보다 크기가 상당히 크다면, 1번 추의 질량은 2번 추의 질량에 5를 더한 것보다도 클 것이라고 비교를 할 수도 있다. 이처럼 추의 질량 비교는 다음의 두 형태로 정리할 수 있다. a와 b는 1 이상 N 이하의 서로 다른 자연수이며, x는 임의의 정수이다. 물론 x는 음수일 수도 있다.

• (a번 추의 질량) ≤ (b번 추의 질량) + x
• (a번 추의 질량) ≥ (b번 추의 질량) + x

이러한 정보가 M개 주어졌을 때, 모든 저울추의 질량을 알아내는 프로그램을 작성하시오.

첫째 줄에 질량을 모르는 저울추의 개수 N과 질량을 비교한 정보의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이어서 M개의 줄에 정보가 a, 0 또는 1, b, x의 순서로 각각 빈칸을 사이에 두고 주어진다. a와 b는 추의 번호로 1 이상 N 이하의 서로 다른 자연수이며, x는 절댓값이 10,000을 넘지 않는 정수이다. 0은 ≤를, 1은 ≥를 의미한다.

N개의 줄에 걸쳐 조건을 만족시키는 추의 질량을 출력한다. i번째 줄에 i번 추의 질량을 출력하도록 하며, 질량은 1,000,000 이하의 자연수여야 한다. 추의 질량을 정할 수 없는 경우에는 첫째 줄에 -1만을 출력하며, 조건을 만족시키는 해가 여러 개일 때는 그 중에 하나만 출력한다.