#2495. 数据结构难题

数据结构难题

Description

nn 个数字a1,a2,,ana_1 , a_2 , …, a_n ,每次都可以将[l,r][l , r ]区间的每个数字都更改为数字xx (类型11),或将[l,r][l ,r ]区间每个大于xxaia_i 都更改为最大公约数gcd(ai,x)gcd(a_i , x )(类型22),请输出最后的序列。

Input

11行包含一个整数TT ,表示测试用例的数量。每个测试用例的第11行都包含整数nn 。下一行包含以空格分隔的nn 个整数a1,a2,,ana_1 , a_2 ,…, a_n 。再下一行包含一个整数QQ ,表示操作数量。下面的QQ 行,每行都包含44个整数tlrxtt 、l 、r 、x ,t 表示操作类型,lrl 、r 表示区间左右端点。t2n,Q100000ai,x0t ≤2,n , Q ≤100000,a_i , x ≥0且在int32int32范围内。

Output

对每个测试用例,都单行输出以空格分隔的最终序列,在序列结束后输出一个空格。

Samples

1
10
16807 282475249 1622650073 984943658 1144108930 470211272 101027544 1457850878 1458777923 2007237709 
10
1 3 6 74243042
2 4 8 16531729
1 3 4 1474833169
2 1 8 1131570933
2 7 9 1505795335
2 3 7 101929267
1 4 10 1624379149
2 2 8 2110010672
2 6 7 156091745
1 2 5 937186357
16807 937186357 937186357 937186357 937186357 1 1 1624379149 1624379149 1624379149

来源

HDU4902