Description

有$n$ 个数字$a_1 , a_2 , …, a_n ，$每次都可以将$[l , r ]$区间的每个数字都更改为数字$x$ （类型$1$），或将$[l ,r ]$区间每个大于$x$ 的$a_i$ 都更改为最大公约数$gcd(a_i , x )$（类型$2$），请输出最后的序列。

Input

第$1$行包含一个整数$T$ ，表示测试用例的数量。每个测试用例的第$1$行都包含整数$n$ 。下一行包含以空格分隔的$n$ 个整数$a_1 , a_2 ,…, a_n 。$再下一行包含一个整数$Q$ ，表示操作数量。下面的$Q$ 行，每行都包含$4$个整数$t 、l 、r 、x ，t$表示操作类型，$l 、r$ 表示区间左右端点。$T ≤2，n , Q ≤100000，a_i , x ≥0$且在$int32$范围内。

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