P15958 [ICPC 2018 Jakarta R] Lexical Sign Sequence

Andi likes numbers and sequences, especially, sign sequences. A sign sequence is a sequence which consists of $-1$ and $1$. Andi is a curious person, thus, he wants to build a sign sequence which length is $N$ (the positions are numbered from $1$ to $N$, inclusive). However, Andi also likes some challenges. Therefore, he prefilled some positions in the sequence with $-1$ or $1$ (the number in these positions cannot be changed). Andi also wants the sequence to fulfill $K$ constraints. For each constraint, there are 3 numbers: $A_i$, $B_i$, and $C_i$. This means that the sum of numbers which position is in the range $[A_i, B_i]$ (inclusive) must be at least $C_i$. Sounds confusing, right? It is not done yet. Since there can be many sequences that fulfill all the criteria above, Andi wants the sequence to be lexicographically smallest. Sequence $X$ is lexicographically smaller than sequence $Y$ if and only if there exists a position $i$ where $X_i < Y_i$ and $X_j = Y_j$ for all $j < i$. Find the sequence Andi wants.

Input begins with a line containing two integers: $N$ $K$ ($1 \leq N \leq 100000$; $0 \leq K \leq 100000$) representing the length of the sequence and the number of constraints, respectively. The second line contains $N$ integers: $P_i$ ($-1 \leq P_i \leq 1$). If $P_i = 0$, then the $i^{th}$ position in the sequence is not prefilled, otherwise the $i^{th}$ position in the sequence is prefilled by $P_i$. The next $K$ lines, each contains three integers: $A_i$ $B_i$ $C_i$ ($1 \leq A_i \leq B_i \leq N$; $-N \leq C_i \leq N$) representing the $i^{th}$ constraint.

Output contains $N$ integers (each separated by a single space) in a line representing the sequence that Andi wants if there exists such sequence, or “Impossible” (without quotes) otherwise.

**Explanation for the sample input/output #1** Both sequences $[1, 1, -1]$ and $[1, 1, 1]$ satisfy the prefilled conditions and the given $K$ constraints. The former is lexicographically smaller. **Explanation for the sample input/output #2** The second position is already prefilled with $-1$, so it is impossible to fulfill the first constraint. There is no valid sequence in this case.