题目描述

聪明兔最近决定监督大笨龙好好学习。

她把大笨龙接下来连续 $N$ 个时段的状态记成一个长度为 $N$ 的序列，位置从 $1$ 到 $N$ 编号。对于第 $i$ 个位置：

• $-1$ 表示大笨龙这段时间在睡觉；
• $1$ 表示大笨龙这段时间在学习。

不过，大笨龙有些时段的状态已经提前确定，不能再修改。除此之外，聪明兔还提出了 $K$ 个要求。每个要求由三个整数 $A_i,B_i,C_i$ 构成，表示在区间 $[A_i,B_i]$ 内，这一段时间的状态值总和必须至少为 $C_i$。

由于睡觉记作 $-1$，学习记作 $1$，因此一个区间内学习得越多，这一段区间的总和通常也会越大。也就是说，聪明兔要求大笨龙在某些连续时间段内，至少要学习到足够的程度。

可能有多种作息安排都满足所有要求，聪明兔希望选出其中字典序最小的一种。这里 $-1 < 1$，因此字典序更小意味着：在尽可能靠前的位置，优先让大笨龙去睡觉；当然，前提是这样安排之后依然满足所有学习要求。

请你帮聪明兔找出这样一个作息安排。

输入格式

输入第一行包含两个整数 $N$ 和 $K$，分别表示作息序列长度和要求数量。

第二行包含 $N$ 个整数 $P_i$（$-1 <= P_i <= 1$）：

• 若 $P_i = 0$，表示这个时段的状态尚未确定；
• 若 $P_i = 1$ 或 $P_i = -1$，表示这个时段已经被预先安排好，不能修改。

接下来 $K$ 行，每行包含三个整数 $A_i,B_i,C_i$（$1 <= A_i <= B_i <= N$，$-N <= C_i <= N$），表示一个要求：区间 $[A_i,B_i]$ 中所有状态值之和至少为 $C_i$。

输出格式

如果存在满足条件的作息安排，则输出一行 $N$ 个整数，表示字典序最小的可行安排，每两个整数之间用一个空格分隔。

如果不存在这样的安排，则输出 Impossible。

样例1输入

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

样例1输出

1 1 -1

样例2输入

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

样例2输出

Impossible

数据规模

对于所有测试数据保证：$1<=n,k<= 10^5$。