/*input
4 2
1 2 3 3
1 2 1
2 1
*/
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
const int N=1e6 + 100;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl
//Trace prints the name of the variable and the value.
int n, m, arr[N];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//freopen("input.txt","r",stdin);freopen("output0.txt","w",stdout);
cin>>n>>m;
assert(n<=1e6);assert(m<=2e5);
arr[0]=inf;set<int> start;
for(int i=1;i<=n;i++) {cin>>arr[i];assert(arr[i]<=1e6);
if(arr[i]%arr[i-1]!=0) start.insert(i);
}
arr[n+1]=mod;
while(m--)
{
int t;cin>>t;assert(t==1||t==2);
if(t==1)
{int ind, val;cin>>ind>>val;assert(ind<=n);assert(val<=1e6);
arr[ind]=val;
if(arr[ind]%arr[ind-1]!=0) start.insert(ind);
else start.erase(ind);
if(arr[ind+1]%arr[ind]!=0) start.insert(ind+1);
else start.erase(ind+1);}
else{
int ind;cin>>ind;
set<int>::iterator it=start.upper_bound(ind);it--;
cout<<(*it)<<endl;
}
}
}
LyppbnB1dAo0IDIKMSAyIDMgMyAKMSAyIDEKMiAxCiovCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNvbnN0IGludCBtb2Q9MWU5ICsgNzsKI2RlZmluZSBpbnQgbG9uZyBsb25nCmNvbnN0IGludCBpbmY9MWUxODsKY29uc3QgaW50IE49MWU2ICsgMTAwOwojZGVmaW5lIHBpaSBwYWlyPGludCwgaW50PgojZGVmaW5lIGYgZmlyc3QKI2RlZmluZSBzIHNlY29uZCAKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBGT1IoaSwgbikgZm9yKGludCBpPTE7aTw9bjtpKyspCiNkZWZpbmUgVFJBQ0UoeCkgY2VyciA8PCAjeCA8PCAiID0gIiA8PCB4IDw8IGVuZGwgCi8vVHJhY2UgcHJpbnRzIHRoZSBuYW1lIG9mIHRoZSB2YXJpYWJsZSBhbmQgdGhlIHZhbHVlLgppbnQgbiwgbSwgYXJyW05dOwpzaWduZWQgbWFpbigpCnsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpO2Npbi50aWUoTlVMTCk7Y291dC50aWUoTlVMTCk7CgkvL2ZyZW9wZW4oImlucHV0LnR4dCIsInIiLHN0ZGluKTtmcmVvcGVuKCJvdXRwdXQwLnR4dCIsInciLHN0ZG91dCk7CgljaW4+Pm4+Pm07Cglhc3NlcnQobjw9MWU2KTthc3NlcnQobTw9MmU1KTsKCWFyclswXT1pbmY7c2V0PGludD4gc3RhcnQ7Cglmb3IoaW50IGk9MTtpPD1uO2krKykge2Npbj4+YXJyW2ldO2Fzc2VydChhcnJbaV08PTFlNik7CgkJaWYoYXJyW2ldJWFycltpLTFdIT0wKSBzdGFydC5pbnNlcnQoaSk7Cgl9CglhcnJbbisxXT1tb2Q7Cgl3aGlsZShtLS0pCgl7CgkJaW50IHQ7Y2luPj50O2Fzc2VydCh0PT0xfHx0PT0yKTsKCQlpZih0PT0xKQoJCXtpbnQgaW5kLCB2YWw7Y2luPj5pbmQ+PnZhbDthc3NlcnQoaW5kPD1uKTthc3NlcnQodmFsPD0xZTYpOwoJCWFycltpbmRdPXZhbDsKCQlpZihhcnJbaW5kXSVhcnJbaW5kLTFdIT0wKSBzdGFydC5pbnNlcnQoaW5kKTsKCQllbHNlIHN0YXJ0LmVyYXNlKGluZCk7CgkJaWYoYXJyW2luZCsxXSVhcnJbaW5kXSE9MCkgc3RhcnQuaW5zZXJ0KGluZCsxKTsKCQllbHNlIHN0YXJ0LmVyYXNlKGluZCsxKTt9CgkJZWxzZXsKCQkJaW50IGluZDtjaW4+PmluZDsKCQkJc2V0PGludD46Oml0ZXJhdG9yIGl0PXN0YXJ0LnVwcGVyX2JvdW5kKGluZCk7aXQtLTsKCQkJY291dDw8KCppdCk8PGVuZGw7CgkJfQoJfQp9IA==