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.Input Format
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 Format
Print in different lines elements of 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}
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
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
Output
8 1 5 1 3