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。
在第二个示例中,两个操作明显矛盾,因此不存在这样好的顺序。