#define p(i,n) for(int i=0; i<n; i++)
#define rp(i,n) for(int i=n-1; i>=0; i--)
#define grid_int vector<vector<int>>
#define grid_char vector<vector<char>>
void ADD(int& c,int a, int b, int m) {c = ((a % m) + (b % m)) % m;return;}
void MUL(int& c,int a, int b, int m) {c = ((a % m) * (b % m)) % m;}
void SUB(int& c,int a, int b, int m) {c = ((a % m) - (b % m) + m) % m;}
void MIN(int& a, int b) {a = min(a, b);}
void MAX(int& a, int b) {a = max(a, b);}
int gcdExtended(int a, int b, int *x, int *y);
int modInverse(int b, int m){int x,y;int g = gcdExtended(b, m, &x, &y);if (g != 1)return -1;return (x%m + m) % m;}
int modDivide(int a, int b, int m){a = a % m;int inv = modInverse(b, m);return (inv * a) % m;}
int gcdExtended(int a, int b, int *x, int *y){if (a == 0){*x = 0, *y = 1;return b;}int x1, y1;int gcd = gcdExtended(b%a, a, &x1, &y1);*x = y1 - (b/a) * x1;*y = x1;return gcd;}
#define f first
#define s second
#define ll long long
#define pb push_back//SEGGY FOR max pref sum;
vector<int> xi, yi;
int nnn;
struct item {
double lg;
int idx;
int val;
// VAL IS THE XI
// LG IS LOG OF SELLING AT DAY index
// iDX IS INDEX
};
struct segtree {
vector<item> seggy;
vector<double> lazy;
int n;
segtree(int _n) {
n = _n;
seggy.resize(4 * n);
lazy.resize(4 * n, 0);
}
item merge(item a, item b) {
item x;
if (a.lg > b.lg) {
x.lg = a.lg;
x.idx = a.idx;
} else {
x.lg = b.lg;
x.idx = b.idx;
}
MUL(x.val, a.val, b.val, MOD);
return x;
}
void push(int node, int left, int right) {
if (lazy[node] != 0) {
seggy[node].lg += lazy[node];
if (left != right) {
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
}
lazy[node] = 0;
}
}
void build(int node, int left, int right) {
if (left == right) {
seggy[node].idx = left;
seggy[node].lg = log(yi[left]);
seggy[node].val = xi[left];
} else {
int mid = (left + right) / 2;
build(2 * node, left, mid);
build(2 * node + 1, mid + 1, right);
seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
}
}
// Point update to set new value and log
void update(int node, int left, int right, int idx, int vv) {
push(node, left, right);
if (left == right) {
seggy[node].idx = left;
seggy[node].lg = log(vv);
seggy[node].val = vv;
} else {
int mid = (left + right) / 2;
if (idx > mid) update(2 * node + 1, mid + 1, right, idx, vv);
else update(2 * node, left, mid, idx, vv);
seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
}
}
// Point update to add value to lg
void update_lg(int node, int left, int right, int idx, double vv) {
if (left == right) {
seggy[node].idx = left;
seggy[node].lg += vv;
return;
}
int mid = (left + right) / 2;
if (idx > mid) update_lg(2 * node + 1, mid + 1, right, idx, vv);
else update_lg(2 * node, left, mid, idx, vv);
seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
}
// New range update function for .lg using lazy propagation
void lazyx(int node, int left, int right, int l, int r, double add_val) {
push(node, left, right);
if (r < left || l > right) return;
if (l <= left && right <= r) {
lazy[node] += add_val;
push(node, left, right);
return;
}
int mid = (left + right) / 2;
lazyx(2 * node, left, mid, l, r, add_val);
lazyx(2 * node + 1, mid + 1, right, l, r, add_val);
seggy[node] = merge(seggy[2 * node], seggy[2 * node + 1]);
}
int query(int node, int left, int right, int l, int r) {
push(node, left, right);
if (l > right || r < left) return 1;
if (left >= l && right <= r) return seggy[node].val % MOD;
int mid = (left + right) / 2;
int xx = query(2 * node, left, mid, l, r);
int yy = query(2 * node + 1, mid + 1, right, l, r);
int temp;
MUL(temp, xx, yy, MOD);
return temp;
}
item grab() {
return seggy[1]; // root is usually at index 1
}
};
segtree Tree(2e6+200);
int opt(vector<int>& a, vector<int>& b, int n) {
item x = Tree.grab();
int ppp = Tree.query(1, 0, nnn - 1, 0, x.idx);
int temp;
MUL(temp, ppp, yi[x.idx], MOD);
return temp;
}
// the functions that are asked by the grader
int init(int n, int X[], int Y[]) {
nnn = n;
xi.resize(nnn);
yi.resize(nnn);
for (int i = 0; i < n; i++) {
xi[i] = X[i];
Tree.lazyx(1,0,n-1,i,n-1,log(xi[i]));
}
for (int i = 0; i < n; i++) yi[i] = Y[i];
Tree.build(1,0,n-1);
return opt(xi, yi, n);
}
int updateX(int pos, int val) {
Tree.update_lg(1, 0, nnn - 1, pos, log(val) - log(xi[pos]));
xi[pos] = val;
Tree.update(1, 0, nnn - 1, pos, val);
return opt(xi, yi, nnn);
}
int updateY(int pos, int val) {
Tree.update_lg(1, 0, nnn - 1, pos, log(val) - log(yi[pos]));
yi[pos] = val;
return opt(xi, yi, nnn);
}
