Chef and Gcd Queries

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef likes solving problems involving a lot of queries with numbers. One day, he found a new problem which he finds difficult to solve. Therefore, he's asking for your help!
You are given a sequence A_{1}, A_{2}, ..., A_{N} and Q queries. There are two types of queries:
 1 X Y — Set A_{X} = Y.
 2 L R G — Compute the number of indices i such that L ≤ i ≤ R and gcd(G, A_{i}) = 1.
Find the answer to each query of the second type.
Note: gcd(X, Y) denotes the greatest common divisor — the highest positive integer which divides both X and Y.
Input
 The first line of the input contains a single integer N denoting the number of elements in the sequence.
 The second line contains N spaceseparated integers A_{1}, A_{2}, ..., A_{N}.
 The third line contains a single integer Q denoting the number of queries.
 Each of the following Q lines describes one query in the following format:
 1 X Y for a query of the first type
 2 L R G for a query of the second type
Output
For each query of type 2, print a single line containing one integer  the answer to the query.
Constraints
 1 ≤ N, Q ≤ 5 · 10^{4}
 1 ≤ L ≤ R ≤ N
 1 ≤ X ≤ N
 1 ≤ Y, G ≤ 10^{5}
 1 ≤ A_{i} ≤ 10^{5} for each valid i
Subtasks
Subtask #1 (15 points): 1 ≤ N, Q ≤ 1000
Subtask #2 (85 points): original constraints
Example
Input: 4 2 3 4 5 3 2 1 4 2 1 2 6 2 1 4 2 Output: 2 1
Explanation
In the first query, gcd(A_{2}, 2) = 1 and gcd(A_{4}, 2) = 1, so the answer is 2.
In the third query, only gcd(A_{4}, 2) is equal to 1, so the answer is 1.
Author:  vipsharmavip 
Editorial  https://discuss.codechef.com/problems/GCDCNT 
Tags  inclusionexclusion, march18, medium, mobius, vipsharmavip 
Date Added:  31012018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions