题目描述

小乔有一个正整数序列，长度为 $n$，分别为 $a_1,a_2,\cdots,a_n$，她非常喜欢这个序列，平时都非常爱惜它们。可是有一天，当小乔出去玩耍的时候，有一只淘气的小猴子改变了这个序列。

猴子操作了 $m$ 次。猴子的操作有两种类型：

• 1 x y 表示第 $x$ 个元素加上第 $y$ 个元素。
• 2 x y 表示第 $x$ 个元素乘上第 $y$ 个元素。

特别且显然地，当 $x=y$，新的 $a_x$ 就等于原来的 $a_x$ 的两倍或平方。序列最后结果形如 $b_1,b_2,\cdots,b_n$。

现在希望你能告诉小乔这个序列最初的形态，也就是 $a_1,a_2,\cdots,a_n$。

输入格式

一共有 $m+2$ 行。第一行输入两个数 $n,m$。

第二行输入 $n$ 个数 $b_1,b_2,\cdots,b_n$，表示经过操作后的序列。

第 $3\sim m+2$ 行每一行输入 $3$ 个数 $k,x,y$，分别表示操作类型，以及操作中的 $x$ 和 $y$。

输出格式

一行，$n$ 个整数 $a_1,a_2,\cdots,a_n$，表示序列最初的样子。

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

数据范围

对于 $100\%$ 的数据满足 $1\le n\le 10^3,1\le m\le 200$，对于任意的 $1\le i\le n$，有 $1\le a_i,b_i \le 2^{60}$ 。