给定一个长度为 n 的序列 a1,a2,…,an。
你需要进行两种操作:
1、1 x y——将第 x 个数变为 y;
2、2 y——将所有小于 y 的数修改为 y;
共执行 q 次操作,输出执行完所有操作后的序列。
输入格式
第一行两个数字 n , q (1≤n,q≤106)。
接下来一行 n 个整数 a1,a2,…,an (0≤a≤109)。
接下来 q 行,每行表示一个操作: 1 x y 或 2 y (1≤x≤n,0≤y≤109)。
输出格式
一行整数,表示操作完后的序列,用空格分隔。
样例输入
5 5
3 6 14 16 12
2 13
2 16
1 1 1
1 2 14
2 11
样例输出
11 14 16 16 16