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 <= N <= 100000$; $0 <= K <= 100000$) representing the length of the sequence and the number of constraints, respectively. The second line contains $N$ integers: $P_i$ ($-1 <= P_i <= 1$). If $P_i = 0$, then the $i^(t h)$ position in the sequence is not prefilled, otherwise the $i^(t h)$ position in the sequence is prefilled by $P_i$. The next $K$ lines, each contains three integers: $A_i$ $B_i$ $C_i$ ($1 <= A_i <= B_i <= N$; $-N <= C_i <= N$) representing the $i^(t h)$ 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.
## Input
Input begins with a line containing two integers: $N$ $K$ ($1 <= N <= 100000$; $0 <= K <= 100000$) representing the length of the sequence and the number of constraints, respectively. The second line contains $N$ integers: $P_i$ ($-1 <= P_i <= 1$). If $P_i = 0$, then the $i^(t h)$ position in the sequence is not prefilled, otherwise the $i^(t h)$ position in the sequence is prefilled by $P_i$. The next $K$ lines, each contains three integers: $A_i$ $B_i$ $C_i$ ($1 <= A_i <= B_i <= N$; $-N <= C_i <= N$) representing the $i^(t h)$ 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.
[samples]
## Note
_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.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n, m \in \mathbb{Z} $ denote the number of stations and people, respectively.
- Let $ X = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n $ be the positions of stations along the line, with $ x_1 \le x_2 \le \dots \le x_n $.
- Let $ P = \{(s_i, d_i) \mid i \in \{1, \dots, m\}\} $ be the set of person trips, where $ s_i, d_i \in \{1, \dots, n\} $, $ s_i \ne d_i $, represent the start and destination station of person $ i $.
**Constraints**
1. $ 1 \le T \le 3700 $
2. $ 2 \le n, m \le 2 \times 10^5 $
3. $ 0 \le x_i \le 2 \times 10^6 $
4. $ \sum_{\text{test cases}} n \le 2 \times 10^6 $, $ \sum_{\text{test cases}} m \le 2 \times 10^6 $
**Objective**
Determine if it is possible to assign card swaps among people such that every person checks out at their destination station with 0 credit, by exchanging metro cards only when two people are at the same station.
This is possible **if and only if** the multiset of start stations equals the multiset of destination stations.
If possible, compute the **minimum total distance traveled** by all people to achieve this, where:
- Each person may travel arbitrarily between stations.
- Card swaps occur at shared stations and are free (no distance cost for swapping).
- Distance traveled is the sum of Euclidean distances moved by each person along the line.
The minimum total distance is the cost of optimally matching each start station to a destination station such that the multiset of starts equals the multiset of ends, and the sum of distances traveled is minimized.
This reduces to:
Let $ S = (s_1, \dots, s_m) $, $ D = (d_1, \dots, d_m) $ be the multisets of start and destination station indices.
Sort both $ S $ and $ D $ in non-decreasing order.
Then, the minimal total distance is:
$$
\sum_{i=1}^{m} |x_{s_i} - x_{d_i}|
$$
where $ s_i, d_i $ are the $ i $-th elements of the sorted multisets.
If the multisets $ S $ and $ D $ are not identical, output $ -1 $.