#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define X first
#define Y second
const int N = 500000 + 5;
const int mod = 1000000007;
const int limit = 1000000000;
int n, request, type, x, y, u, v, k;
int a[N], b[N], Xarr[N], Yarr[N], t[4 * N], lazy[4 * N], tTwo[4 * N];
set<int> se;
set<int>::iterator it;
int mul(int x,int y)
{
return 1LL*x*y%mod;
}
int luythua(int x,int n)
{
int c=1;
while (n)
{
if (n&1) c=mul(c,x);
x=mul(x,x);
n/=2;
}
return c;
}
void down(int id)
{
if (lazy[id]!=1)
{
lazy[id*2]=mul(lazy[id*2],lazy[id]);
lazy[id*2+1]=mul(lazy[id*2+1],lazy[id]);
tTwo[id*2]=mul(tTwo[id*2],lazy[id]);
tTwo[id*2+1]=mul(tTwo[id*2+1],lazy[id]);
lazy[id]=1;
}
}
void update_range(int id,int l,int r)
{
if (u>r or v<l) return;
if (u<=l and v>=r)
{
tTwo[id]=mul(tTwo[id],k);
lazy[id]=mul(lazy[id],k);
return;
}
down(id);
int m=(l+r)/2;
update_range(id*2,l,m);
update_range(id*2+1,m+1,r);
}
void update_point(int id,int l,int r)
{
if (l==r)
{
t[id]=k;
return;
}
int m=(l+r)/2;
if (u<=m) update_point(id*2,l,m);
else update_point(id*2+1,m+1,r);
t[id]=max(t[id*2],t[id*2+1]);
}
int get_range(int id,int l,int r)
{
if (u>r or v<l) return 0;
if (u<=l and v>=r) return t[id];
int m=(l+r)/2;
return max(get_range(id*2,l,m),get_range(id*2+1,m+1,r));
}
ll get_point(int id,int l,int r)
{
if (l==r)
return tTwo[id];
down(id);
int m=(l+r)/2;
if (u<=m) return get_point(id*2,l,m);
else return get_point(id*2+1,m+1,r);
}
// build using pref_mod to avoid side effects of modifying cur inside recursion
function<void(int,int,int, const vector<int>&)> build; // forward
int init(int nn, int aarr[], int barr[]) {
::n = nn;
for (int i = 0; i < n; ++i) {
Xarr[i] = aarr[i];
Yarr[i] = barr[i];
}
// prepare prefix modulo array (prefix_mod[i] = X[0]*...*X[i-1] mod)
vector<int> prefix_mod(n + 1);
prefix_mod[0] = 1;
for (int i = 1; i <= n; ++i) prefix_mod[i] = mul(prefix_mod[i - 1], Xarr[i - 1]);
long long cur=1;
// build function (uses prefix_mod)
build = [&](int id, int l, int r, const vector<int> &pref_mod) {
lazy[id] = 1;
tTwo[id] = 1;
if (l == r) {
if (l == 0) t[id] = 1;
else t[id] = Yarr[l - 1],cur=mul(cur,Xarr[l-1]);
tTwo[id] = cur; // prefix mod for leaf l
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m, pref_mod);
build(id << 1 | 1, m + 1, r, pref_mod);
t[id] = max(t[id << 1], t[id << 1 | 1]);
};
// build tree
build(1, 0, n, prefix_mod);
// fill set se
se.insert(0);
for (int i = 0; i < n; ++i) if (Xarr[i] != 1) se.insert(i + 1);
// find best: iterate as you requested: multiply cur by X[old-1] then --it then check pos=*it
it = prev(se.end());
int best = *it;
// ma: pair(maxY, den) where den is cur-ref per your semantics; init with last element
u = *it; v = n;
pii ma = make_pair(get_range(1, 0, n), 1);
cur = 1;
while (it!=se.begin())
{
if (*it) cur*=Xarr[(*it)-1];
if (cur>=limit) break;
it--;
u=*it;
v=n;
int temp=get_range(1,0,n);
if (ma.X*cur<temp*ma.Y)
{
best=*it;
cur=1;
ma=make_pair(temp,cur);
}
}
u = best;
int prefMod = get_point(1, 0, n);
u = best; v = n;
int ans = mul(prefMod, get_range(1, 0, n));
return ans;
}
int updateX(int pos0, int val) {
int pos = pos0 + 1;
if (Xarr[pos - 1] != val) {
if (Xarr[pos - 1] == 1) se.insert(pos);
k = mul(luythua(Xarr[pos - 1], mod - 2), val); // multiplier modulo
u = pos; v = n;
update_range(1, 0, n);
Xarr[pos - 1] = val;
if (val == 1) se.erase(pos);
}
// find best again with same iteration logic
it = prev(se.end());
int best = *it;
u = *it; v = n;
pii ma = make_pair(get_range(1, 0, n), 1);
long long cur = 1;
while (it!=se.begin())
{
if (*it) cur*=Xarr[(*it)-1];
if (cur>=limit) break;
it--;
u=*it;
v=n;
int temp=get_range(1,0,n);
if (ma.X*cur<temp*ma.Y)
{
best=*it;
cur=1;
ma=make_pair(temp,cur);
}
}
u = best;
int prefMod = get_point(1, 0, n);
u = best; v = n;
return mul(prefMod, get_range(1, 0, n));
}
int updateY(int pos0, int val) {
int pos = pos0 + 1;
if (Yarr[pos - 1] != val) {
u = pos; k = val;
update_point(1, 0, n); // set t at leaf pos to val
Yarr[pos - 1] = val;
}
// find best again
it = prev(se.end());
int best = *it;
u = *it; v = n;
pii ma = make_pair(get_range(1, 0, n), 1);
long long cur = 1;
while (it!=se.begin())
{
if (*it) cur*=Xarr[(*it)-1];
if (cur>=limit) break;
it--;
u=*it;
v=n;
int temp=get_range(1,0,n);
if (ma.X*cur<temp*ma.Y)
{
best=*it;
cur=1;
ma=make_pair(temp,cur);
}
}
u = best;
int prefMod = get_point(1, 0, n);
u = best; v = n;
return mul(prefMod, get_range(1, 0, n));
}
