B. Segment Trees ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sanjay gives you a sequence of $$$n$$$ integers is given $$$a_1$$$, $$$a_2$$$, .. $$$a_n$$$. You need to process $$$q$$$ queries of two types.

The sequence supports the following two types of operations:

  • $$$1$$$ $$$x$$$ $$$p$$$ — Set $$$a_x$$$ to $$$p$$$.
  • $$$2$$$ $$$v$$$ — Set $$$a_i$$$=$$$max$$$($$$a_i$$$,$$$v$$$) for all $$$i$$$ $$$\in$$$ ($$$1$$$,$$$n$$$). Where $$$max$$$($$$a$$$,$$$b$$$) denotes maximum of $$$a$$$ and $$$b$$$
Your task is to determine the final values of the array after processing all queries.
Input
  • The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
  • For each test case:
    • The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the size of the array.
    • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — the elements of the array.
    • The third line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of queries.
    • Then $$$q$$$ lines follow. The $$$i$$$-th line contains the $$$i$$$-th query is given either as
      • $$$1$$$ $$$x$$$ $$$p$$$ $$$(1 \leq x \leq n, 1 \leq p \leq 10^9)$$$
      • $$$2$$$ $$$v$$$ $$$(1 \leq v \leq 10^9)$$$
  • The sum of $$$n$$$ and $$$q$$$ across all test cases does not exceed $$$10^5$$$.
Output
  • For each test case, print $$$n$$$ space-separated integers — the final values of the array after processing all queries.
Example
Input
1
8
1 2 3 4 5 6 7 8
8
2 10
1 1 6
1 2 6
2 10
1 1 5
1 2 6
1 3 7
1 4 1
Output
5 6 7 1 10 10 10 10
Note

$$$[1 ,2 ,3 ,4 ,5 ,6 ,7 ,8]$$$ $$$\xrightarrow[]{1}$$$ $$$[10 ,10 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{2}$$$ $$$[6 ,10 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{3}$$$ $$$[6 ,6 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{4}$$$ $$$[10 ,10 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{5}$$$ $$$[5 ,10 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{6}$$$ $$$[5 ,6 ,10 ,10 ,10 ,10 ,10 ,10]$$$ $$$\xrightarrow[]{7}$$$ $$$[5 ,6 ,7 ,10 ,10 ,10 ,10 ,10]$$$ ,$$$\xrightarrow[]{8}$$$ $$$[5 ,6 ,7 ,1 ,10 ,10 ,10 ,10]$$$