Chef and medium problem 2

All submissions for this problem are available.
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 lth 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 spaceseparated 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
Author:  furko 
Tester:  stzgd 
Editorial  http://discuss.codechef.com/problems/CHEFD 
Tags  bit, furko, ltime16, medium, sets 
Date Added:  17092014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 