#include "horses.h"
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
const int mod=1e9+7;
int n;
int bseg[4*maxn];
int y[maxn];
pair<bool,int> pseg[4*maxn];
pair<bool,int> comb(pair<bool,int> a,pair<bool,int> b){
if(ll(a.second)*ll(b.second)>=mod){
return mp(true,ll(a.second)*ll(b.second)%mod);
}
return mp(false,ll(a.second)*ll(b.second));
}
void buildp(int *x,int ind=1,int l=0,int r=n-1){
if(l==r){
pseg[ind]={false,x[l]};
return;
}
int mid=l+(r-l)/2;
buildp(x,2*ind,l,mid);
buildp(x,2*ind+1,mid+1,r);
pseg[ind]=comb(pseg[2*ind],pseg[2*ind+1]);
}
void updatep(int t,int v,int ind=1,int l=0,int r=n-1){
if(t==l){
pseg[ind]={false,v};
return;
}
int mid=l+(r-l)/2;
updatep(t,v,2*ind,l,mid);
updatep(t,v,2*ind+1,mid+1,r);
pseg[ind]=comb(pseg[2*ind],pseg[2*ind+1]);
}
pair<bool,int> queryp(int tl,int tr,int ind=1,int l=0,int r=n-1){
if(tl<=l && r<=tr) return pseg[ind];
int mid=l+(r-l)/2;
pair<bool,int> ret={false,1};
if(tl<=mid) ret=comb(ret,queryp(tl,tr,2*ind,l,mid));
if(tr>mid) ret=comb(ret,queryp(tl,tr,2*ind+1,mid+1,r));
return ret;
}
int comp(int a,int b){
if(a>b) swap(a,b);
pair<bool,int> raz=queryp(a+1,b);
raz=comb(raz,mp(false,y[b]));
if(raz.first) return b;
if(raz.second>y[a]) return b;
else return a;
}
void buildb(int ind=1,int l=0,int r=n-1){
if(l==r){
bseg[ind]=l;
return;
}
int mid=l+(r-l)/2;
buildb(2*ind,l,mid);
buildb(2*ind+1,mid+1,r);
bseg[ind]=comp(bseg[2*ind],bseg[2*ind+1]);
}
void updateb(int t,int ind=1,int l=0,int r=n-1){
if(t==l) return;
int mid=l+(r-l)/2;
updateb(t,2*ind,l,mid);
updateb(t,2*ind+1,mid+1,r);
bseg[ind]=comp(bseg[2*ind],bseg[2*ind+1]);
}
int init(int N, int X[], int Y[]) {
n=N;
for(int i=0;i<n;i++) y[i]=Y[i];
buildp(X);
buildb();
//cout<<bseg[1]<<"\n";
return comb(queryp(0,bseg[1]),mp(false,y[bseg[1]])).second;
}
int updateX(int pos, int val) {
updatep(pos,val);
updateb(pos);
//cout<<bseg[1]<<"\n";
return comb(queryp(0,bseg[1]),mp(false,y[bseg[1]])).second;
}
int updateY(int pos, int val) {
y[pos]=val;
buildb();
//cout<<bseg[1]<<"\n";
return comb(queryp(0,bseg[1]),mp(false,y[bseg[1]])).second;
}
