#P8318. 『JROI-4』淘气的猴子

『JROI-4』淘气的猴子

题目背景

众所周知,jockbutt 是一个可爱的女孩纸。

题目描述

jockbutt 有一个正整数序列,长度为 nn,分别为 a1,a2...ana_1,a_2...a_n,她非常喜欢这个序列,平时都非常爱惜它们。

可是有一天,当 jockbutt 在和你约会的时候,有一只淘气的小猴子改变了这个序列。

猴子操作了 mm 次。

猴子的操作有两种类型:

  • 1 x y\texttt{1 x y} 表示第 xx 个元素加上第 yy 个元素。
  • 2 x y\texttt{2 x y} 表示第 xx 个元素乘上第 yy 个元素。

特别且显然地,当 x=yx=y,新的 xx 就等于原来的 xx 的两倍或平方。

序列最后结果形如 b1,b2...bnb_1,b_2...b_n

等到 jockbutt 回来时,全洛谷的人都在看猴子。$\colorbox{white}{\color{white}{\text{其实 jockbutt 才是他们看的猴子吧}}}$

jockbutt 非常生气,希望你能告诉她这个序列最初的形态,也就是 a1,a2,a3,...,ana_1,a_2,a_3,...,a_n,否则她就会嘤嘤嘤...

输入格式

一共有 m+2m+2 行。

第一行输入两个数 n,mn,m

第二行输入 nn 个数 b1,b2,,bnb_1,b_2,\cdots,b_n,表示经过操作后的序列。

3m+23\sim m+2 行每一行输入 33 个数 k,x,yk,x,y ,分别表示操作类型,以及操作中的 xxyy

输出格式

一行,nn 个整数 a1,a2...ana_1,a_2...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

提示

本题采用捆绑测试。

子任务编号 分值 特殊限制
1 25 1n,m101\leq n,m\leq 10
2 1n1001\leq n\leq 1001m501\leq m \leq 50
3 50
  • 对于 100%100\% 的数据满足 1n1031\leq n\le 10^31m2001\leq m\le 200,对于任意的 i i (1in) ( 1\leq i \leq n ) ,有 1ai,bi2601\leq a_{i},b_{i} \leq 2^{60}