Quietly, Completely, Forever

Sejong is solving the following problem.

You are given a sequence $A_1,A_2,\cdots,A_N$ of length $N$. Then $Q$ updates are given as follows.

• L R x: For every $L\leq i\leq R$, apply $A_i=\min(A_i,x)$. ($1\leq L\leq R\leq N$; $0\leq x\leq 1\,000\,000$)

Find the sequence after performing the $Q$ updates in order.

Sejong found that some elements stop changing after a certain update. The emotional Sejong calls these elements forgotten elements and decides to keep count of them. Specifically, if an element is not changed by the remaining updates after it processes the $i$-th update, then that element is an $i$-forgotten element. Note that for any two positive integers $i<j$, every $i$-forgotten element is also a $j$-forgotten element.

Write a program that finds the sequence Sejong needs and the number of forgotten elements after each update.

The first line contains an integer $N$, the length of the sequence. ($1\leq N\leq 100\,000$)

The second line contains $N$ integers $A_1,A_2,\cdots,A_N$, separated by spaces. ($0\leq A_i\leq 1\,000\,000$)

The third line contains an integer $Q$, the number of updates. ($1\leq Q\leq 100\,000$)

From the fourth line, $Q$ lines follow, one update per line, in the order they must be processed.

On the first line, print the sequence after all updates are performed, separated by spaces.

On the second line, print $Q$ integers $D_1,D_2,\cdots,D_Q$, separated by spaces. Here, $D_i$ is the number of $i$-forgotten elements.