Read problems statements in Mandarin Chinese and Russian.

Chef has an array containing N integers. You have to make M queries. Each query has one of the two types:

1 l r p - Select all the numbers having indices between l and r (inclusive) that are divisible by p and divide them by p,
where p is in set {2, 3, 5}.
2 l d - Modify the l-th number in the array to d.

Please help Chef in finding out the array after all the M queries.

------ Input ------

The first line of the input contains a single integer N denoting the number of integers in given array.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the given array.
Next line contains a single integer M denoting the number of queries.
Each of the following M lines describes a single query in the format given in the statement.

------ Output ------

Output a single line containing N integers denoting the array after all the M queries.

------ Constraints ------

$1 ≤ M ≤ 10^{5}$
$1 ≤ l ≤ r ≤ N$
$1 ≤ A_{i} ≤ 10^{9}$
$In each query of first type, p is in set {2, 3, 5} $
$Subtask 1 (20 points): 1 ≤ N ≤ 100$
$Subtask 2 (35 points): 1 ≤ N ≤ 10^{5}, there is no query of second type$
$Subtask 3 (45 points): 1 ≤ N ≤ 10^{5}$

------ Example ------

Input:
3
1 2 3
5
1 2 2 2
1 2 2 2
2 2 3
1 2 3 3
2 1 5

Output:
5 1 1

见题面

见题面