烟花

题号：NC313370
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

除夕之夜，万家灯火通明，小红正忙着筹备一场盛大的烟花表演。她在长街上布置了 $n$ 个发射点，从 $1$ 到 $n$ 编号，每个发射点都准备了一枚具有特定「色彩强度值」的烟花。这种色彩强度值是一个非负整数。

然而，由于忙着和家人团聚吃年夜饭，小红不小心弄丢了每枚烟花具体的强度清单。幸好，在之前的试放记录中，她找到了 $m$ 条观测数据。每条数据记录了从第 $l_i$ 个到第 $r_i$ 个发射点的烟花同时升空时，它们的光芒交织合并后的总强度为 $v_i$ 。根据烟花的特性，强度的合并规则遵循 按位或（Bitwise OR） 运算。

现在，小红请你根据这 $m$ 条记录，还原出 $n$ 枚烟花各自的色彩强度值 $a_1, a_2, \dots, a_n$ 。如果存在多种可能的还原方案，输出其中任意一种即可；如果这些记录之间存在矛盾，导致无法找到符合要求的强度序列，请输出 -1。

输入描述:

第一行包含两个正整数  和 （），分别表示烟花的数量和观测记录的数量。
接下来的  行，每行包含三个整数  和 （，），表示在区间  内的所有烟花色彩强度按位或的结果为 。

输出描述:

如果存在符合要求的还原方案，在一行中输出  个非负整数，表示每枚烟花的色彩强度值。每个数值应小于 。
如果不存在合法的方案，输出 -1。

示例1

输入

复制

5 2
1 3 3
3 5 6

输出

复制

3 3 2 6 6

说明


	在样例中，小红给出了两条观测记录：

	1. 第一条记录显示区间  的按位或结果为 。在输出的方案中，前三个数是 ，计算 ，符合要求。

	2. 第二条记录显示区间  的按位或结果为 。在输出的方案中，后三个数是 ，计算 ，符合要求。

	注意，第  枚烟花的强度值为 ，它同时满足了上述两条记录的约束。