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

然而，Andi 也喜欢挑战。因此，他预先填充了序列中的某些位置，填入 $-1$ 或 $1$（这些位置的数字不能更改）。Andi 还希望序列满足 $K$ 个约束条件。对于每个约束，有三个数字：$A_i$、$B_i$ 和 $C_i$。这意味着位置在 $[A_i, B_i]$（包含边界）范围内的数字之和必须至少为 $C_i$。

听起来很复杂，对吧？还没完。由于可能存在许多满足上述所有条件的序列，Andi 希望得到字典序最小的序列。如果存在一个位置 $i$，使得 $X_i < Y_i$ 且对于所有 $j < i$ 都有 $X_j = Y_j$，则称序列 $X$ 的字典序小于序列 $Y$。

请找出 Andi 想要的序列。

输入格式

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

输出格式

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

样例

样例输入 1

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

样例输出 1

1 1 -1

说明 1

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

样例输入 2

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

样例输出 2

Impossible

说明 2

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