#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define ROF(i,a,b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define pb push_back
ll MOD = 1000000007;
ll power(ll base, ll n){
if (n == 0) return 1;
if (n == 1) return base;
ll halfn = power(base, n/2);
if (n % 2 == 0) return (halfn * halfn) % MOD;
return (((halfn * halfn) % MOD) * base) % MOD;
}
ll inverse(ll n){
return power(n, MOD-2);
}
vector<ll> x, y;
int n;
// range addition and maximum
struct segtree{
vector<pair<double,int>> mx;
int sz;
void init(int m){
sz = m;
mx.assign(4*m, {0,-1});
ini(1,0,sz-1);
}
void ini(int v, int tl, int tr){
if (tl == tr){
mx[tl].se = tl;
return;
}
int tm = (tl+tr)/2;
ini(2*v, tl, tm);
ini(2*v+1, tm+1, tr);
}
void update(int v, int tl, int tr, int l, int r, double val){
if (tl == l || tr == r){
mx[v].fi += val;
return;
}
if (l > r) return;
int tm = (tl + tr)/2;
update(2*v, tl, tm, l, min(r,tm), val);
update(2*v+1, tm+1, tr, max(l,tm+1), r, val);
if (mx[2*v].fi + 1e-7 > mx[2*v+1].fi){
mx[v] = mx[2*v];
}else{
mx[v] = mx[2*v+1];
}
}
void update(int l, int r, double val){
update(1,0,sz-1,l,r,val);
}
int get(){
return mx[1].se;
}
} st;
vector<ld> a, b;
int init(int N, int X[], int Y[]) {
cout << setprecision(12);
n = N;
FOR(i,0,n){
x.pb(X[i]);
y.pb(Y[i]);
}
a.pb(log2(x[0])); b.pb(log2(y[0]));
FOR(i,1,n){
a.pb(log2(x[i])+a[i-1]);
b.pb(log2(y[i]));
}
ld mx = a[0]+b[0];
int ind = 0;
FOR(i,1,n){
if (a[i]+b[i]+1e-11 > mx){
mx = a[i]+b[i];
ind = i;
}
}
ll ans = y[ind];
FOR(i,0,ind+1){
ans *= x[i];
ans %= MOD;
}
return (int) ans;
st.init(N);
FOR(i,0,N){
st.update(i,n-1,log2(X[i]));
st.update(i,i,log2(Y[i]));
}
cout << st.mx[1].fi << " " << st.mx[1].se << '\n';
return st.get();
}
int updateX(int pos, int val) {
ld add = log2(val) - log2(x[pos]);
FOR(i,pos,n){
a[i] += add;
}
x[pos] = val;
ld mx = a[0]+b[0];
int ind = 0;
FOR(i,1,n){
if (a[i]+b[i]+1e-11 > mx){
mx = a[i]+b[i];
ind = i;
}
}
ll ans = y[ind];
FOR(i,0,ind+1){
ans *= x[i];
ans %= MOD;
}
return (int) ans;
st.update(pos,n-1,log(val)-log(x[pos]));
x[pos] = val;
cout << st.mx[1].fi << " " << st.mx[1].se << '\n';
return st.get();
}
int updateY(int pos, int val) {
y[pos] = val;
b[pos] = log2(val);
ld mx = a[0]+b[0];
int ind = 0;
FOR(i,1,n){
if (a[i]+b[i]+1e-11 > mx){
mx = a[i]+b[i];
ind = i;
}
}
ll ans = y[ind];
FOR(i,0,ind+1){
ans *= x[i];
ans %= MOD;
}
return (int) ans;
st.update(pos,pos,log(val)-log(y[pos]));
y[pos] = val;
cout << st.mx[1].fi << " " << st.mx[1].se << '\n';
return st.get();
}
