#include "horses.h"
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
#include <iostream>
#include <math.h>
using namespace std;
long long prime = 1000000007;
long long mod_exp(long long a, long long k){
if (k == 0){
return 1;
}
if (k == 1){
return a;
}
long long a1 = mod_exp(a, k / 2);
if (k % 2 == 1){
return (((a1 * a1) % prime) * a) % prime;
}
return (a1 * a1) % prime;
}
void updateModSegTree(vector<long long> &tree, int p, long long t){
int N = tree.size() / 2;
tree[p + N] = (tree[p + N] * t) % prime;
for (p = (p + N) / 2; p > 0; p = p / 2){
tree[p] = (tree[2 * p] * tree[2 * p + 1]) % prime;
}
}
long long queryModSegTree(vector<long long> &tree, int l, int r){
int N = tree.size() / 2;
long long total = 1;
for (l += N, r += N; l < r; l /= 2, r /= 2){
if (l % 2 == 1){
total = (total * tree[l++]) % prime;
}
if (r % 2 == 1){
total = (total * tree[--r]) % prime;
}
}
return total;
}
void apply(vector<long double> &tree, vector<long double> &delayed, int p, long double t){
tree[p] += t;
if (p < delayed.size()){
delayed[p] += t;
}
}
void build(vector<long double> &tree, vector<long double> &delayed, int p, vector<int> &answer_node){
while (p > 1){
p /= 2;
answer_node[p] = answer_node[2 * p + 1];
if (tree[2 * p] > tree[2 * p + 1]){
answer_node[p] = answer_node[2 * p];
}
tree[p] = max(tree[2 * p], tree[2 * p + 1]) + delayed[p];
}
}
void push(vector<long double> &tree, vector<long double> &delayed, int p){
int N = tree.size() / 2;
int h = sizeof(int) * 8 - __builtin_clz(N);
for (int s = h; s > 0; s--){
int i = p >> s;
if (delayed[i] != 0){
apply(tree, delayed, 2 * i, delayed[i]);
apply(tree, delayed, 2 * i + 1, delayed[i]);
delayed[i] = 0;
}
}
}
void updateMaxSegTree(vector<long double> &tree, vector<long double> &delayed, int l, int r, long double t, vector<int> &answer_node){
int n = tree.size() / 2;
l += n;
r += n;
int L = l;
int R = r;
for (; l < r; l/=2, r/=2){
if (l % 2 == 1){
apply(tree, delayed, l++, t);
}
if (r % 2 == 1){
apply(tree, delayed, --r, t);
}
}
build(tree, delayed, L, answer_node);
build(tree, delayed, R - 1, answer_node);
}
int queryMaxSegTree(vector<long double> &tree, vector<long double> &delayed, int l, int r, vector<int> &answer_node){
int N = tree.size() / 2;
l += N;
r += N;
push(tree, delayed, l);
push(tree, delayed, r - 1);
long double answer = -1;
int answer_n = -1;
for (; l < r; l /= 2, r /= 2){
if (l % 2 == 1){
if (tree[l] > answer){
answer_n = answer_node[l];
}
answer = max(answer, tree[l++]);
}
if (r % 2 == 1){
if (tree[r - 1] > answer){
answer_n = answer_node[r - 1];
}
answer = max(answer, tree[--r]);
}
}
//cout << answer << endl;
return answer_n;
}
vector<long long> mod_seg_tree;
vector<long double> max_seg_tree;
vector<long double> max_seg_tree_delayed;
vector<int> answer_node;
vector<long long> Xi;
vector<long long> Yi;
int init(int N, int X[], int Y[]) {
mod_seg_tree = vector<long long> (2 * N, 1);
max_seg_tree = vector<long double> (2 * N, 0.0);
max_seg_tree_delayed = vector<long double> (N, 0.0);
answer_node = vector<int> (2 * N, 0);
for (int i = 0; i < N; i++){
answer_node[i + N] = i;
Xi.push_back(X[i]);
Yi.push_back(Y[i]);
}
for (int i = 0; i < N; i++){
//cout << i << ' ' << X[i] << endl;
updateModSegTree(mod_seg_tree, i, X[i]);
//cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, N, log(X[i]), answer_node);
updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, i, i + 1, log(Y[i]), answer_node);
}
int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
//cout << best << endl;
long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
//cout << 'a' << endl;
//cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
return (answer * Yi[best]) % prime;
}
int updateX(int pos, int val) {
int N = max_seg_tree.size() / 2;
updateModSegTree(mod_seg_tree, pos, val * mod_exp(Xi[pos], prime - 1));
updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, pos, N, log(val) - log(Xi[pos]), answer_node);
Xi[pos] = (long double) val;
int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
//cout << best << endl;
long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
//cout << 'a' << endl;
//cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
return (answer * Yi[best]) % prime;
}
int updateY(int pos, int val) {
int N = max_seg_tree.size() / 2;
updateMaxSegTree(max_seg_tree, max_seg_tree_delayed, pos, pos + 1, log(val) - log(Yi[pos]), answer_node);
Yi[pos] = (long double) val;
int best = queryMaxSegTree(max_seg_tree, max_seg_tree_delayed, 0, N, answer_node);
//cout << best << endl;
long long answer = queryModSegTree(mod_seg_tree, 0, best + 1);
//cout << 'a' << endl;
//cout << queryModSegTree(mod_seg_tree, 0, 1) << endl;
return (answer * Yi[best]) % prime;
}
