← 返回题目列表

Codeforces · 796/F

F. 序列恢复

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

Zane 曾经有一个很好的序列 a,由 n 个整数 a1, a2, ..., an 组成 - 但他已经丢失了它。

当且仅当一个序列的所有整数均为非负且值不超过 109 时,该序列才被称为良好序列。

然而,Zane 记得曾通过对他的序列应用 m 个操作来玩弄它。

有两种类型的操作:

1. 给定 l 和 r,找到索引为 i 且 l ≤ i ≤ r 的整数的最大值。

2. 给定 k 和 d,将 d 指定为索引 k 的整数值。

演奏结束后,他将序列恢复到进行任何操作之前的状态。也就是说,序列a不再受到所应用的类型2操作的影响。然后,他在从现在到那时之间的某个时间丢失了他的序列。

幸运的是,Zane 记得所有操作以及他将它们应用到序列中的顺序,以及所有 1 类操作的不同结果。而且,在所有以相同顺序应用相同操作时会产生相同结果的好序列中,他知道他的序列a最可爱。

我们将序列的可爱度定义为该序列中所有整数的按位或结果。例如,Zane的序列a的可爱度是a1 OR a2 OR ... OR an。

Zane 明白,根据他的信息,可能无法准确恢复丢失的序列,因此他很乐意获得由 n 个整数 b1, b2, ..., bn 组成的任何好的序列 b:

1. 当以相同的顺序应用相同的操作时,会给出相同的结果,并且

2. 与赞恩的原始序列 a 一样可爱。

如果存在这样的序列,找到它。否则的话,就说明赞恩一定是记错了什么,这是有可能的。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 3·105) - 分别是 Zane 原始序列中的整数个数和已应用于该序列的操作数。

以下 m 行中的第 i 行以一个整数 ti ($$t_{i} \in \{1,2\}$$) 开头 - 第 i 个操作的类型。

如果运算为类型 1 (ti = 1),则后面跟着三个整数 li、ri 和 xi (1 ≤ li ≤ ri ≤ n, 0 ≤ xi ≤ 109) - 分别是要考虑的最左边的索引、要考虑的最右边的索引以及索引在 li 和 ri 之间(含)的所有整数的最大值。

如果运算为类型 2 (ti = 2),则后面有两个整数 ki 和 di (1 ≤ ki ≤ n, 0 ≤ di ≤ 109) — 意味着索引为 ki 的整数在该运算后应变为 di。

对于所有 (i, j) 对,保证 xi ≠ xj,其中 1 ≤ i < j ≤ m 且 ti = tj = 1。

操作按照应用的顺序给出。也就是说,首先应用第一个给出的操作,然后应用第二个给出的操作,依此类推。

输出

如果不存在有效的好序列,则在第一行打印“NO”(不带引号)。

否则,在第一行打印“YES”(不带引号),并在第二行打印 n 个空格分隔的整数 b1, b2, ..., bn (0 ≤ bi ≤ 109)。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

5 4
1 1 5 19
1 2 5 1
2 5 100
1 1 5 100

输出 #1

YES
19 0 0 0 1

输入 #2

5 2
1 1 5 0
1 1 5 100

输出 #2

NO

注意

在第一个示例中,很容易验证这个好的序列是否有效。特别是,它的可爱度是19 OR 0 OR 0 OR 0 OR 1 = 19。

在第二个示例中,两个操作明显矛盾,因此不存在这样好的顺序。