27886번 - 가희와 서울 지하철 1호선 스페셜 저지

문제

서울 지하철 1호선은 n개의 역이 있습니다. 1번 역을 출발하여, n번 역을 종착하는 하행 열차는 1번 역, 2번 역, ... , n번 역 순서대로 역에 도착하게 됩니다. 가희는 해당 노선을 운행하는 열차들을 관찰하다가 몇 가지 특징을 발견하였습니다.

• 열차가 하행 열차인 경우, 시발역부터 종착역까지 가는 동안 거쳐 가는 역들에 쓰인 수들의 최소 공배수를 열차 번호로 가집니다.

예를 들어, 해당 노선에 3개의 역이 있고, 1번 역에는 3, 2번 역에는 1, 3번 역에는 수 1이 있다고 해 보겠습니다. 하행 열차가 1번 역에서 출발하여 3번 역에 종착하는 경우, 거쳐 가는 역은 1번, 2번, 3번 역입니다. 이때, 이 열차는 3, 1, 1의 최소공배수인 3을 열차 번호로 가지게 됩니다. 하행 열차 Q편의 시발역, 종착역, 열차 번호가 주어졌을 때, 1번 역부터 n번 역까지 역에 쓰인 수를 출력해 주세요.

입력

첫 번째 줄에 n과 Q가 공백으로 구분되어 주어집니다.

다음 Q개의 줄에 시발역의 번호, 종착역의 번호, 하행 열차 번호가 공백으로 구분되어 주어집니다.

출력

n개의 역에 쓰인 수들을 출력해 주세요. 이때, 수들은 1이상 2×106이하여야 합니다. 만약 불가능하다면, -1을 출력해 주세요.

제한

• 1 ≤ Q ≤ 2×105
• 1 ≤ n ≤ 2×105
• 하행 열차 번호는 1 또는 소수입니다. 소수란, 1과 자기 자신을 제외한 어떤 양의 정수로도 나누어떨어지지 않는 수입니다.
• 1 ≤ 하행 열차 번호 ≤ 106
• 시발역의 번호 < 종착역의 번호이며, 주어지는 역 번호는 1 이상 n 이하의 정수입니다.

힌트