Background

As everyone knows, jockbutt is a cute girl.

Problem Description

jockbutt has a positive integer sequence of length $n$, namely $a_1,a_2,\cdots,a_n$. She likes this sequence very much and usually takes good care of it.

But one day, when jockbutt was on a date with you, a naughty little monkey changed the sequence.

The monkey performed $m$ operations.

There are two types of operations:

• $\texttt{1 x y}$ means adding the $y$-th element to the $x$-th element.
• $\texttt{2 x y}$ means multiplying the $x$-th element by the $y$-th element.

In particular and obviously, when $x=y$, the new value at position $x$ becomes double or squared compared to the original value at position $x$.

The final sequence has the form $b_1,b_2,\cdots,b_n$.

When jockbutt came back, everyone on Luogu was watching the monkey. $\colorbox{white}{\color{white}{\text{Actually, maybe jockbutt is the “monkey” they are watching.}}}$

jockbutt is very angry and hopes you can tell her the initial sequence, that is, $a_1,a_2,\cdots,a_n$, otherwise she will cry...

Input Format

There are $m+2$ lines in total.

The first line contains two integers $n,m$.

The second line contains $n$ integers $b_1,b_2,\cdots,b_n$, representing the sequence after all operations.

Lines $3$ to $m+2$ each contain three integers $k,x,y$, representing the operation type and the $x$ and $y$ used in the operation.

Output Format

One line with $n$ integers $a_1,a_2,\cdots,a_n$, representing the initial sequence.

5 5
12 1 12 4 2
1 3 2
1 4 3
2 3 4
1 5 2
2 1 3

1 1 2 1 1

Hint

This problem uses bundled testdata.

• For $100\%$ of the data, $1\leq n\le 10^3$, $1\leq m\le 200$, and for any $i$ $(1\leq i \leq n)$, $1\leq a_i,b_i \leq 2^{60}$.

Translated by ChatGPT 5