사전순으로 가장 작은 부호 수열

Andi는 수와 수열, 그중에서도 부호 수열을 좋아한다. 부호 수열은 -1과 1로 이루어진 수열이다. Andi는 호기심이 많아서 길이가 N인 부호 수열을 만들려고 한다. 위치는 1부터 N까지 번호가 매겨진다.

Andi는 도전도 좋아한다. 그래서 수열의 일부 위치를 -1 또는 1로 미리 채워 두었다. 이 위치의 값은 바꿀 수 없다. 또한 Andi는 수열이 K개의 제약을 만족하기를 원한다. 각 제약은 세 수 Ai, Bi, Ci로 주어진다. 이는 위치가 구간 [Ai, Bi]에 속하는 수들의 합이 Ci 이상이어야 한다는 뜻이다.

복잡하게 들리는가? 아직 끝나지 않았다. 위 조건을 모두 만족하는 수열이 여러 개 있을 수 있으므로 Andi는 사전순으로 가장 작은 수열을 원한다. 수열 X가 수열 Y보다 사전순으로 작다는 것은, Xi < Yi이고 모든 j < i에 대해 Xj = Yj인 위치 i가 존재한다는 뜻이다.

Andi가 원하는 수열을 구하라.

첫 줄에는 두 정수 N K (1 ≤ N ≤ 100000; 0 ≤ K ≤ 100000)가 주어진다. 이는 각각 수열의 길이와 제약의 개수이다. 둘째 줄에는 N개의 정수 Pi (-1 ≤ Pi ≤ 1)가 주어진다. Pi = 0이면 수열의 i번째 위치는 미리 채워지지 않았고, 그렇지 않으면 수열의 i번째 위치는 Pi로 미리 채워져 있다. 다음 K개의 줄에는 각각 세 정수 Ai Bi Ci (1 ≤ Ai ≤ Bi ≤ N; -N ≤ Ci ≤ N)가 주어지며, i번째 제약을 나타낸다.

Andi가 원하는 수열이 존재하면 그 수열의 N개 정수를 한 줄에 공백 하나로 구분하여 출력하고, 존재하지 않으면 “Impossible”을 출력한다. 따옴표는 출력하지 않는다.