I just saw a problem and I tried to solve it many times but got time limit exceeded. I need your help to this problem. there are two number in first line of input N,Q the number of the number in the array A, the number of queries respectively . and in the second line of input there are no number elements of A array and next q lines include queries. there are two types of queries - 1,x,y in this kind of query we need to update element in x position to y - 2,l,r in this query we need to print one number that the numbers of the gcd sequences in the array that is greater than 1

constraints : - 1≤N,Q≤10**5 - 1≤X≤N - 1≤A - 1<=A[i],V[i]<=10**9 time complexity: 4000ms space complexity: 256mb

I tried to solve it using segment tree