{"raw_statement":[{"iden":"statement","content":"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).\n\nHowever, 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$.\n\nSounds 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$.\n\nFind the sequence Andi wants.\n\nInput 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.\n\nOutput 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.\n\n_Explanation for the sample input/output #1_\n\nBoth sequences $[ 1, 1, -1 ]$ and $[ 1, 1, 1 ]$ satisfy the prefilled conditions and the given $K$ constraints. The former is lexicographically smaller.\n\n_Explanation for the sample input/output #2_\n\nThe second position is already prefilled with $-1$, so it is impossible to fulfill the first constraint. There is no valid sequence in this case.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input3 2\n0 0 0\n1 2 2\n2 3 -1\nOutput1 1 -1\nInput3 2\n0 -1 0\n1 2 2\n2 3 -1\nOutputImpossible\n"},{"iden":"note","content":"_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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n, m \\in \\mathbb{Z} $ denote the number of stations and people, respectively.  \n- 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 $.  \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 $.\n\n**Constraints**  \n1. $ 1 \\le T \\le 3700 $  \n2. $ 2 \\le n, m \\le 2 \\times 10^5 $  \n3. $ 0 \\le x_i \\le 2 \\times 10^6 $  \n4. $ \\sum_{\\text{test cases}} n \\le 2 \\times 10^6 $, $ \\sum_{\\text{test cases}} m \\le 2 \\times 10^6 $  \n\n**Objective**  \nDetermine 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.  \n\nThis is possible **if and only if** the multiset of start stations equals the multiset of destination stations.  \n\nIf possible, compute the **minimum total distance traveled** by all people to achieve this, where:  \n- Each person may travel arbitrarily between stations.  \n- Card swaps occur at shared stations and are free (no distance cost for swapping).  \n- Distance traveled is the sum of Euclidean distances moved by each person along the line.  \n\nThe 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.  \n\nThis reduces to:  \nLet $ S = (s_1, \\dots, s_m) $, $ D = (d_1, \\dots, d_m) $ be the multisets of start and destination station indices.  \nSort both $ S $ and $ D $ in non-decreasing order.  \nThen, the minimal total distance is:  \n$$\n\\sum_{i=1}^{m} |x_{s_i} - x_{d_i}|\n$$  \nwhere $ s_i, d_i $ are the $ i $-th elements of the sorted multisets.  \n\nIf the multisets $ S $ and $ D $ are not identical, output $ -1 $.","simple_statement":"You are given n stations in a line with positions x1, x2, ..., xn.  \nThere are m people, each starting at station si and wanting to end at station di.  \n\nYou can swap metro cards between any two people if they are at the same station.  \nIf you check in and out at the same station, you pay 0 credit.  \n\nGoal: Can all m people end at their destination and pay 0 credit?  \nIf yes, find the minimum total distance all people must travel to make this happen.  \nIf no, output -1.","has_page_source":false}