#include<cstdio>

 #include<algorithm>

 #define ls (x<<1)

 #define rs (ls|1)

 #define lson ls,L,mid

 #define rson rs,mid+1,R

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=,inf=1e9,mod=1e9+;

 int n,Q,x,y,a[N],w[N];

 struct Tr{ ll s1,s2; }v[N<<];

 struct P{ ll x,y; };

 void upd(int x){ v[x].s1=v[ls].s1+v[rs].s1; v[x].s2=(v[ls].s2+v[rs].s2)%mod; }

 void build(int x,int L,int R){

     if (L==R){ v[x].s1=w[L]; v[x].s2=1ll*a[L]*w[L]%mod; return; }

     int mid=(L+R)>>;

     build(lson); build(rson); upd(x);

 }

 void mdf(int x,int L,int R,int pos,int k){

     if (L==R){ v[x].s1=k; v[x].s2=1ll*a[pos]*k%mod; return; }

     int mid=(L+R)>>;

     if (pos<=mid) mdf(lson,pos,k); else mdf(rson,pos,k);

     upd(x);

 }

 P que(int x,int L,int R,int l,int r){

     if (L==l && r==R) return (P){v[x].s1,v[x].s2};

     int mid=(L+R)>>;

     if (r<=mid) return que(lson,l,r);

     else if (l>mid) return que(rson,l,r);

         else{

             P s1=que(lson,l,mid),s2=que(rson,mid+,r);

             return (P){s1.x+s2.x,(s1.y+s2.y)%mod};

         }

 }

 P ask(int x,int L,int R,int l,int r,ll k){

     if (L==l && r==R){

         if (v[x].s1<=k) return (P){inf,v[x].s1};

         if (L==R) return (P){l,};

     }

     int mid=(L+R)>>;

     if (r<=mid) return ask(lson,l,r,k);

     else if (l>mid) return ask(rson,l,r,k);

         else{

             ll sm=,res=inf;

             P cur=ask(lson,l,mid,k);

             res=min(res,cur.x); sm+=cur.y;

             if (res<inf) return (P){res,sm};

             cur=ask(rson,mid+,r,k-sm);

             res=min(res,cur.x); sm+=cur.y;

             return (P){res,sm};

         }

 }

 int work(int l,int r){

     int k=ask(,,n,l,r,que(,,n,l,r).x/).x;

     P t1=(k==l) ? (P){,} : que(,,n,l,k-),t2=que(,,n,k,r);

     return ((a[k]*(t1.x%mod)-t1.y+t2.y-a[k]*(t2.x%mod))%mod+mod)%mod;

 }

 int main(){

     freopen("1058f.in","r",stdin);

     freopen("1058f.out","w",stdout);

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

     rep(i,,n) scanf("%d",&a[i]),a[i]=a[i]-i;

     rep(i,,n) scanf("%d",&w[i]);

     build(,,n);

     while (Q--){

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

         if (x<) mdf(,,n,-x,y); else printf("%d\n",work(x,y));

     }

     return ;

 }