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
