#include"bits/stdc++.h"

 #define db double

 #define ll long long

 #define vec vector<ll>

 #define Mt  vector<vec>

 #define ci(x) scanf("%d",&x)

 #define cd(x) scanf("%lf",&x)

 #define cl(x) scanf("%lld",&x)

 #define pi(x) printf("%d\n",x)

 #define pd(x) printf("%f\n",x)

 #define pl(x) printf("%lld\n",x)

 using namespace std;

 const int N   = 1e6 + ;

 int a[N],b[N],s[][],n; //s[x][y]表示对于所有a[i]==x时的b[i]%a[i]余数大于等于y的数目

 ll ret;

 bool check(ll x,ll k)

 {

     ll ans=ret*-;

     for(int i=; i<=; i++)

     {

         ans+=x/i*s[i][]; //s[i][0]为a数组中等于i的数的个数

         ans-=s[i][x%i+];  //减掉所有 c1<c2 的情况

     }

     return ans>=k;

 }

 ll cal(ll x)

 {

     ll l=,r=1e13,mid;

     ll res=l;

     while(l<=r)

     {

         mid=(l+r)>>;

         if(check(mid,x)) res=mid,r=mid-;

         else l=mid+;

     }

     return res;

 }

 int main()

 {

     int TA,T,x,y,z;

     scanf("%d",&TA);

     while(TA--)

     {

         scanf("%d%d",&n,&T);

         ret=;

         memset(s,, sizeof(s));

         for(int i=; i<=n; i++) scanf("%d",&a[i]);

         for(int i=; i<=n; i++) scanf("%d",&b[i]),ret+=(b[i]/a[i]),s[a[i]][b[i]%a[i]]++;

         for(int i=; i<=; i++)

             for(int j=i-; j>=; j--)

                 s[i][j]+=s[i][j+];

         while(T--)

         {

             scanf("%d%d",&z,&x);

             if(z==)

             {

                 scanf("%d",&y);

                 for(int i=b[x]%a[x]; i>=; i--) s[a[x]][i]--;

                 for(int i=b[x]%y; i>=; i--)    s[y][i]++;

                 ret-=(b[x]/a[x]);

                 ret+=(b[x]/y);

                 a[x]=y;

             }

             else if(z==)

             {

                 scanf("%d",&y);

                 for(int i=b[x]%a[x]; i>=; i--) s[a[x]][i]--;

                 for(int i=y%a[x]; i>=; i--)    s[a[x]][i]++;

                 ret-=(b[x]/a[x]);

                 ret+=(y/a[x]);

                 b[x]=y;

             }

             else

             {

                 printf("%lld\n",cal(1ll*x));

             }

         }

     }

 }