#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define oset tree < pair<int, int> , null_type , less<pair<int, int>> , rb_tree_tag , tree_order_statistics_node_update >
using namespace std;
set<int> subarrays;
int findans(int x){ //The second type of query
//For any element k, the first element in the subarray of element k is -
//The largest element j in sa such j<=k
//Find the first element j such that j > k
//j--; (The previous element)
auto it = subarrays.upper_bound(x);
it--;
return (*it);
}
void remove(int x){
subarrays.erase(x);
}
signed main(){
//N -> size of the array// N<=1e6
//A[N] positive integers
//We are dividing the entire array into subarrays
//If i and i+1 are in the same subarray then A(i+1)%A(i) == 0
//S(i) is the index of the subarray in which the ith element lies
//Q queries, Q = 2e5
//Changing A(i) to X
//2 i, we have to output the first element in the same subarray as i
//Required complexity is either O(Q) or O(Q.LogN)
//In this problem, we have to form continuous subarrays
//For any index i, if A(i+1)%A(i) ==0, then we should place i+1 and i in the same subarray
//If we can place A(i), A(i+1) in the same subarray, then they should be in the same subarray
//How do we store the partitions of the subarrays?
//Since the subarrays are all contigious, we only need to store the first element of each subarray
//{2, 6, 5, 10, 20, 3}
//{2, 6} -> index of the first element of each subarray
//{5, 10}
//{3}
//sa
//{1 -> 1/2, 3 -> 3/4/5, 6 -> 6}
//For the second type of query, we need to output the first element of the subarray of index k
//For any element k, the first element in the subarray of element k is -
//The largest element j in sa such j<=k
//We need a data structures that can:
//Store elements in a sorted order - set
//Erase elements in O(1) or O(LogN) - set
//Find the largest element j in sa such j<=k in O(1) or O(LogN) - set
int n, q;
cin>>n>>q;
int a[n+1];
for(int i = 1;i<=n;i++) cin>>a[i];
//We need to create the subarrays
subarrays.insert(1); //1 will always be the start of some subarray
for(int i = 2;i<=n;i++){
//For any index i, if A(i+1)%A(i) ==0, then we should place i+1 and i in the same subarray
//If we can place A(i), A(i+1) in the same subarray, then they should be in the same subarray
if(a[i]%a[i-1] == 0) continue; //we can place i and i-1 in the same subarray
//we skip because we have already stored the start of the (i-1)th subarray
subarrays.insert(i); //When a[i] and a[i-1] could not be in the same subarray, we inserted i into the set
} //We have created the basic partitions before any queries took place
while(q--){
int type, i;
cin>>type>>i;
if(type==1){
cin>>a[i]; //the updated value of a(i)
//There are 4 things that can happen
//a(i) and a(i-1) can now be in the same subarray -> DONE
//A(i) and A(i-1) can no longer be in the same subarray -> DONE
//A(i) and A(i+1) can now be in the same subarray -> DONE
//A(i) and A(i+1) can no longer be in the same subarray
if(i>1) {
if ((findans(i) == i) &&
((a[i] % a[i - 1]) == 0)) { //now a[i] and a[i-1] should be in the same subarray
//We need to reverse the operation on line 68
remove(i);
} else if ((findans(i) < i) &&
((a[i] % a[i - 1]) != 0)) { //this means a[i] and a[i-1] were in the same subarray
//We need to perform the operation on line 68 to separate the elements
subarrays.insert(i);
}
}
if(i<n){
if((findans(i+1)>i && ((a[i+1] % a[i]) == 0))){
remove(i+1);
}
else if((findans(i+1)<=i) && ((a[i+1]%a[i])!=0)){
subarrays.insert(i+1);
}
}
}
else{
cout<<findans(i)<<endl;
}
}
}
//acdabcd