{"problem":{"name":"H. Lexical Sign Sequence","description":{"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 leng","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10200H"},"statements":[{"statement_type":"Markdown","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## Input\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\n## Output\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[samples]\n\n## Note\n\n_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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10200H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}