给定一个长度为 $n$ 的序列 $a_1,a_2,\dots ,a_n$。

你需要进行两种操作：

1、$1$ $x$ $y$——将第 $x$ 个数变为 $y$；

2、$2$ $y$——将所有小于 $y$ 的数修改为 $y$；

共执行 $q$ 次操作，输出执行完所有操作后的序列。

输入格式

第一行两个数字 $n$ , $q$ $(1 \leq n,q \leq 10^6)$。

接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(0 \leq a \leq 10^9)$。

接下来 $q$ 行，每行表示一个操作: $1$ $x$ $y$ 或 $2$ $y$ $(1 \leq x \leq n, 0 \leq y \leq 10^9)$。

输出格式

一行整数，表示操作完后的序列，用空格分隔。

样例输入

5 5
3 6 14 16 12
2 13
2 16
1 1 1
1 2 14
2 11

样例输出

11 14 16 16 16