# Prime Divide

medium

You are given an array A of N numbers. You need to perform Q operations. Each operation has one of the two type: 1. 1 l r p: select all numbers between indices l to r which are divisible by p and divide then all by p, here is in set {2, 3 5}. 2. 2 l d: update element at index l to d. Print the final array after performing all operations.

## Constraints

1. 1 <= N <= 10^5 2. 1 <= Q <= 10^5 3. 1 <= l <= r <= N 4. 1 <= A[i], d <= 10^9 5. p belongs to set {2, 3, 5}

## Format

### Input

First line contains single number N denoting size of array Second line contains N space seperated numbers A[1] A[2] A[3] ... A[N] denoting elements of array Third line contains single number Q denoting number of operations Q following lines contains operations of format 1 l r p or 2 l d

### Output

Print in different lines elements of array after performing all operations.

## Example

Sample Input

5
8 9 12 3 5
5
1 1 5 3
2 5 9
1 1 5 3
1 2 5 2
2 3 5

### Sample Output

8
1
5
1
3