Sequence Operations

Problem Description

You are given a sequence $a_1, a_2, \dots, a_n$ of length $n$.

You need to perform two kinds of operations:

1. 1 x y — change the $x$-th element to $y$;
2. 2 y — change every element that is less than $y$ to $y$.

After performing $q$ operations in total, output the resulting sequence.

Input Format

The first line contains two integers $n, q$ ($1 \le n, q \le 10^6$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$).

The next $q$ lines each describe one operation: 1 x y or 2 y ($1 \le x \le n$, $0 \le y \le 10^9$).

Output Format

Output one line containing the resulting sequence, with the integers separated by spaces.

Sample Input

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

Sample Output

11 14 16 16 16