Recover the Original Sequence

jockbutt had a positive integer sequence \(a_1, a_2, \dots, a_n\) which she cherished. One day, while she was on a date with you, a mischievous monkey played with the sequence by performing \(m\) operations. The operations are of two types:

• Type 1: 1 x y means that the \(x\)th element is increased by the \(y\)th element, i.e. \(a_x = a_x + a_y\). (In particular, if \(x = y\), then \(a_x\) becomes \(2a_x\).)
• Type 2: 2 x y means that the \(x\)th element is multiplied by the \(y\)th element, i.e. \(a_x = a_x \times a_y\). (In particular, if \(x = y\), then \(a_x\) becomes \(a_x^2\).)

After all operations, the sequence becomes \(b_1, b_2, \dots, b_n\). Furious that her sequence has been tampered with, jockbutt now demands that you recover the original sequence \(a_1, a_2, \dots, a_n\).

Note: It is guaranteed that the operations are reversible and the original sequence consists of positive integers. When reversing an operation:

• For a type 1 operation 1 x y: if \(x \neq y\), then the original \(a_x = b_x - b_y\); if \(x = y\), then \(a_x = b_x/2\).
• For a type 2 operation 2 x y: if \(x \neq y\), then the original \(a_x = b_x / b_y\); if \(x = y\), then \(a_x = \sqrt{b_x}\) (the square root is an integer square root).

inputFormat

The first line contains two integers \(n\) and \(m\) denoting the length of the sequence and the number of operations performed by the monkey.

The second line contains \(n\) integers \(b_1, b_2, \dots, b_n\) representing the final sequence after all operations.

Then \(m\) lines follow, each line contains an operation in one of the following formats:

• 1 x y
• 2 x y

All indices are 1-indexed.

outputFormat

Output the original sequence \(a_1, a_2, \dots, a_n\) as \(n\) space-separated integers.

sample

3 3
8 6 4
1 1 2
2 2 3
1 3 3

5 3 2