# Hackerland General Store
## Problem Statement
A general store in Hackerland sells $n$ items. Initially, the price of the $i$-th item is $a_i$. The store frequently adjusts its prices using a series of $q$ queries to account for market changes and inflation. Each query is one of two types:
1. **Type 1 Query**: `1 x v`
This query means that the price of the $x$-th item should be changed to $v$. That is, $a_x \leftarrow v$.
2. **Type 2 Query**: `2 v v`
This query means that for all items, if their current price is strictly less than $v$, their price should be updated to $v$. That is, for all $i$ from $1$ to $n$, if $a_i < v$, then $a_i \leftarrow v$.
You are given the initial prices of $n$ items and a sequence of $q$ queries. Your task is to apply all queries in the given order and output the final prices of all items.
## Input Format
The first line contains a single integer $n$ ($1 \le n \le 2 \times 10^5$), representing the number of items.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), representing the initial prices of the items.
The third line contains a single integer $q$ ($1 \le q \le 2 \times 10^5$), representing the number of queries.
Each of the next $q$ lines describes a query. Each query is given in one of the following formats:
* `1 x v`: for a Type 1 query, where $x$ is a 1-based index ($1 \le x \le n$) and $v$ is the new price ($0 \le v \le 10^9$).
* `2 v v`: for a Type 2 query, where $v$ is the threshold price ($0 \le v \le 10^9$). Note that the second and third integers are identical.
## Output Format
Output a single line containing $n$ integers, the final prices of items $a_1, a_2, \ldots, a_n$, separated by spaces.
## Sample Test Cases
### Sample Input 1
```
3
7 5 4
3
2 6 6
1 2 9
2 8 8
```
### Sample Output 1
```
8 9 8
```
## Constraints
* $1 \le n \le 2 \times 10^5$
* $1 \le q \le 2 \times 10^5$
* $0 \le a_i \le 10^9$
* $0 \le v \le 10^9$
* $1 \le x \le n$ (for Type 1 queries)
* Time limit: 1 second
* Memory limit: 256 MB
## Explanation
Let's trace the operations for Sample Input 1:
Initial prices: $[7, 5, 4]$
1. **Query `2 6 6`**: This is a Type 2 query with threshold $v = 6$. All prices less than $6$ are changed to $6$.
* $7$ is not less than $6$.
* $5$ is less than $6$, so $5 \to 6$.
* $4$ is less than $6$, so $4 \to 6$.
Current prices: $[7, 6, 6]$
2. **Query `1 2 9`**: This is a Type 1 query. The price of the 2nd item (index $x=2$) is changed to $9$.
* The 2nd item's price becomes $9$.
Current prices: $[7, 9, 6]$
3. **Query `2 8 8`**: This is a Type 2 query with threshold $v = 8$. All prices less than $8$ are changed to $8$.
* $7$ is less than $8$, so $7 \to 8$.
* $9$ is not less than $8$.
* $6$ is less than $8$, so $6 \to 8$.
Current prices: $[8, 9, 8]$
After all queries, the final prices are $[8, 9, 8]$.
Loading problem statement...