题目描述

安迪喜欢数字和序列，尤其是符号序列。符号序列是由 $-1$ 和 $1$ 组成的序列。安迪是个好奇的人，因此他想构建一个长度为 $N$ 的符号序列（位置从 $1$ 到 $N$ 编号）。

然而，安迪也喜欢一些挑战。因此，他预先填充了序列中的某些位置为 $-1$ 或 $1$（这些位置的数值不可更改）。安迪还希望该序列满足 $K$ 个约束条件。每个约束条件包含三个数：$A_i$、$B_i$ 和 $C_i$。这意味着在区间 $[A_i, B_i]$（包含端点）内所有位置上的数字之和必须至少为 $C_i$。

听起来很困惑，对吧？还没完。由于可能存在多个序列满足上述所有条件，安迪希望序列的字典序最小。序列 $X$ 的字典序小于序列 $Y$，当且仅当存在某个位置 $i$，使得 $X_i < Y_i$，并且对于所有 $j < i$，有 $X_j = Y_j$。

请找出安迪想要的序列。

输入格式

输入的第一行包含两个整数：$N$ 和 $K$（$1 \leq N \leq 100000$；$0 \leq K \leq 100000$），分别表示序列的长度和约束条件的数量。第二行包含 $N$ 个整数：$P_i$（$-1 \leq P_i \leq 1$）。如果 $P_i = 0$，则表示序列中第 $i$ 个位置未被预先填充；否则，序列中第 $i$ 个位置被预先填充为 $P_i$。接下来的 $K$ 行，每行包含三个整数：$A_i$、$B_i$ 和 $C_i$（$1 \leq A_i \leq B_i \leq N$；$-N \leq C_i \leq N$），表示第 $i$ 个约束条件。

输出格式

如果存在这样的序列，则输出一行包含 $N$ 个整数（每个整数之间用一个空格分隔），表示安迪想要的序列；否则输出 Impossible（不含引号）。

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

1 1 -1

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

Impossible

提示

样例输入 #1 的解释

序列 $[1, 1, -1]$ 和 $[1, 1, 1]$ 都满足预先填充条件和给定的 $K$ 个约束条件。前者字典序更小。

样例输入 #2 的解释

第二个位置已被预先填充为 $-1$，因此无法满足第一个约束条件。这种情况下不存在有效序列。

翻译由 DeepSeek V3.2 完成