← 返回题目列表

Codeforces · 482/B

B. 有趣的数组

中文机器翻译题面 查看原题

如果一个包含 n 个非负整数 a[1], a[2], ..., a[n] 的数组满足 m 个约束,我们将其称为有趣的。 m 个约束中的第 i 个由三个整数 li、ri、qi (1 ≤ li ≤ ri ≤ n) 组成,这意味着值 $$a[l_{i}] \& a[l_{i}+1] \& \ldots \& a[r_{i}]$$ 应等于 qi。

你的任务是找到任何有趣的 n 个元素数组,或者声明这样的数组不存在。

表达式 x&y 表示数字 x 和 y 的按位与。在编程语言 C++、Java 和 Python 中,此操作表示为“&”,在 Pascal 中表示为“and”。

输入

第一行包含两个整数 n、m (1 ≤ n ≤ 105, 1 ≤ m ≤ 105) — 数组中的元素数量和限制数量。

接下来的 m 行中的每一行都包含三个整数 li、ri、qi (1 ≤ li ≤ ri ≤ n, 0 ≤ qi < 230),描述第 i 个极限。

输出

如果感兴趣的数组存在,则在第一行打印“YES”(不带引号),并在第二行打印 n 个整数 a[1], a[2], ..., a[n] (0 ≤ a[i] < 230) 描述感兴趣的数组。如果有多个答案,请打印其中任何一个。

如果感兴趣的数组不存在,则在单行中打印“NO”(不带引号)。

示例

输入 #1

3 1
1 3 3

输出 #1

YES
3 3 3

输入 #2

3 2
1 3 3
1 3 2

输出 #2

NO