Lexical Sign Sequence (Problem H, 2018 ICPC Asia Jakarta Regional Contest, 2018)
Time limit: 1 sec
Memory limit: 256MB
Author: Alfonsus Raditya A., Jonathan I. G.

# Problem Statement

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

Input begins with a line containing two integers: $N$ $K$ $(1 \le N \le 100000;\ 0 \le K \le 100000)$ representing the length of the sequence and the number of constraints, respectively. The second line contains $N$ integers: $P_i$ $(-1 \le P_i \le 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 \le A_i \le B_i \le N;\ -N \le C_i \le N)$ representing the $i^{th}$ constraint.

# Output

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.

# Sample Input #1
```
3 2
0 0 0
1 2 2
2 3 -1
```
# Sample Output #1
```
1 1 -1
```
# 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.

# Sample Input #2
```
3 2
0 -1 0
1 2 2
2 3 -1
```
# Sample Output #2
```
Impossible
```
# 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 novalid sequence in this case.


Sample inputs:
3 2
0 0 0
1 2 2
2 3 -1

3 2
0 -1 0
1 2 2
2 3 -1

Sample outputs:
1 1 -1

Impossible

# Solution Analysis

We can convert each of the constraints $A_i B_i C_i$ into the following: there are at most $D_i = \frac{B_i - A_i + 1 - C_i}{2}$ $-1$s in the range $[A_i, B_i]$. We can imagine $D_i$ as the “hit points” (HP) of the $i^{th}$ constraint. Whenever we put a $-1$ in $[A_i, B_i]$, we decrement the HP of the $i^{th}$ constraint by one.

We can also subtract $D_i$ with the number of $-1$s already prefilled in the range $[A_i, B_i]$, thus we can ignore the prefilled conditions for the rest of the discussion. If one of $D_i$ is less than 0, then it is impossible to fill the sequence.

Since we want to find the lexicographically smallest sequence, we want to fill the sequence greedily from the first position. As long as we can fill a position with $-1$, we will do so. We cannot fill a position with $-1$ if doing so causes one of the constraint to have a negative HP. However, an $\mathcal{O}(NM)$ solution by checking each constraint for each position is too slow for this problem.

We can maintain a data structure to keep track of the constraint with the least HP. At the start of our loop at position $x$, we can insert those constraints $i$ with $A_i = x$ to our data structure. Also, at the end of our loop at position $x$, we can remove those constraints $i$ with $B_i = x$. We check whether it is possible to put a $-1$ in the position $x$ by checking the least value in our data structure. If and only if it is larger than 0, then can put a $-1$ in the position $x$. If we decide to put a $-1$ in the position $x$, we need to subtract all values in our data structure by one. We can implement this by actually inserting $D_i + C$ (instead of $D_i$) to our data structure, where $C$ is the number of $-1$s we have put so far. This is to make sure that all the constraints HP in the data structure are “calibrated” using the same benchmark.

To support our needs, we can either use a balanced binary search tree or a minimum heap with lazy deletion. This algorithm runs in $\mathcal{O}(N \log N)$.

Special judge (C++ scorer):