#include <bits/stdc++.h>
using namespace std;
typedef int num_t;
const num_t oo = (num_t) 1e9;
struct func_t {
num_t a, b;
func_t(num_t a = 0, num_t b = oo) : a(a), b(b) {}
num_t query(num_t x) {return a * x + b;}
};
struct node_t {
node_t *l, *r;
func_t f;
node_t(node_t* l = 0, node_t* r = 0, func_t f = func_t()) : l(l), r(r), f(f) {}
num_t query(num_t x) {return f.query(x);}
};
node_t* upd(node_t* p, int l, int r, int L, int R, func_t f) {
if (l > R || r < L) return p;
int M = L + (R - L >> 1);
node_t* res = p ? new node_t(p->l, p->r, p->f) : new node_t();
if (l <= L && r >= R) {
int fl = f.query(L) >= (p ? p->query(L) : oo);
int fr = f.query(R) >= (p ? p->query(R) : oo);
if (fl && fr) return res;
if (!fl && !fr) {
res->f = f;
return res;
}
int fm1 = f.query(M) >= (p ? p->query(M) : oo);
if (fl && fm1) {
res->r = upd(res->r, l, r, M + 1, R, f);
return res;
}
if (!fl && !fm1) {
res->r = upd(res->r, l, r, M + 1, R, res->f);
res->f = f;
return res;
}
int fm2 = f.query(M + 1) >= (p ? p->query(M + 1) : oo);
if (fm2 && fr) {
res->l = upd(res->l, l, r, L, M, f);
return res;
}
if (!fm2 && !fr) {
res->l = upd(res->l, l, r, L, M, res->f);
res->f = f;
return res;
}
assert(0);
}
res->l = upd(res->l, l, r, L, M, f);
res->r = upd(res->r, l, r, M + 1, R, f);
return res;
}
node_t* upd(node_t* p, int l, int r, int L, int R, num_t a, num_t b) {
return upd(p, l, r, L, R, func_t(a, b));
}
num_t query(node_t* p, int i, int L, int R) {
if (!p) return oo;
if (i < L || i > R) return oo;
num_t res = p->query(i);
if (L < R) {
res = min(res, query(p->l, i, L, L + R >> 1));
res = min(res, query(p->r, i, (L + R >> 1) + 1, R));
}
return res;
}
int main() {
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGludCBudW1fdDsKY29uc3QgbnVtX3Qgb28gPSAobnVtX3QpIDFlOTsKc3RydWN0IGZ1bmNfdCB7CiAgICBudW1fdCBhLCBiOwogICAgZnVuY190KG51bV90IGEgPSAwLCBudW1fdCBiID0gb28pIDogYShhKSwgYihiKSB7fQogICAgbnVtX3QgcXVlcnkobnVtX3QgeCkge3JldHVybiBhICogeCArIGI7fQp9OwpzdHJ1Y3Qgbm9kZV90IHsKICAgIG5vZGVfdCAqbCwgKnI7CiAgICBmdW5jX3QgZjsKICAgIG5vZGVfdChub2RlX3QqIGwgPSAwLCBub2RlX3QqIHIgPSAwLCBmdW5jX3QgZiA9IGZ1bmNfdCgpKSA6IGwobCksIHIociksIGYoZikge30KICAgIG51bV90IHF1ZXJ5KG51bV90IHgpIHtyZXR1cm4gZi5xdWVyeSh4KTt9Cn07Cm5vZGVfdCogdXBkKG5vZGVfdCogcCwgaW50IGwsIGludCByLCBpbnQgTCwgaW50IFIsIGZ1bmNfdCBmKSB7CiAgICBpZiAobCA+IFIgfHwgciA8IEwpIHJldHVybiBwOwogICAgaW50IE0gPSBMICsgKFIgLSBMID4+IDEpOwogICAgbm9kZV90KiByZXMgPSBwID8gbmV3IG5vZGVfdChwLT5sLCBwLT5yLCBwLT5mKSA6IG5ldyBub2RlX3QoKTsKICAgIGlmIChsIDw9IEwgJiYgciA+PSBSKSB7CiAgICAgICAgaW50IGZsID0gZi5xdWVyeShMKSA+PSAocCA/IHAtPnF1ZXJ5KEwpIDogb28pOwogICAgICAgIGludCBmciA9IGYucXVlcnkoUikgPj0gKHAgPyBwLT5xdWVyeShSKSA6IG9vKTsKICAgICAgICBpZiAoZmwgJiYgZnIpIHJldHVybiByZXM7CiAgICAgICAgaWYgKCFmbCAmJiAhZnIpIHsKICAgICAgICAgICAgcmVzLT5mID0gZjsKICAgICAgICAgICAgcmV0dXJuIHJlczsKICAgICAgICB9CiAgICAgICAgaW50IGZtMSA9IGYucXVlcnkoTSkgPj0gKHAgPyBwLT5xdWVyeShNKSA6IG9vKTsKICAgICAgICBpZiAoZmwgJiYgZm0xKSB7CiAgICAgICAgICAgIHJlcy0+ciA9IHVwZChyZXMtPnIsIGwsIHIsIE0gKyAxLCBSLCBmKTsKICAgICAgICAgICAgcmV0dXJuIHJlczsKICAgICAgICB9CiAgICAgICAgaWYgKCFmbCAmJiAhZm0xKSB7CiAgICAgICAgICAgIHJlcy0+ciA9IHVwZChyZXMtPnIsIGwsIHIsIE0gKyAxLCBSLCByZXMtPmYpOwogICAgICAgICAgICByZXMtPmYgPSBmOwogICAgICAgICAgICByZXR1cm4gcmVzOwogICAgICAgIH0KICAgICAgICBpbnQgZm0yID0gZi5xdWVyeShNICsgMSkgPj0gKHAgPyBwLT5xdWVyeShNICsgMSkgOiBvbyk7CiAgICAgICAgaWYgKGZtMiAmJiBmcikgewogICAgICAgICAgICByZXMtPmwgPSB1cGQocmVzLT5sLCBsLCByLCBMLCBNLCBmKTsKICAgICAgICAgICAgcmV0dXJuIHJlczsKICAgICAgICB9CiAgICAgICAgaWYgKCFmbTIgJiYgIWZyKSB7CiAgICAgICAgICAgIHJlcy0+bCA9IHVwZChyZXMtPmwsIGwsIHIsIEwsIE0sIHJlcy0+Zik7CiAgICAgICAgICAgIHJlcy0+ZiA9IGY7CiAgICAgICAgICAgIHJldHVybiByZXM7CiAgICAgICAgfQogICAgICAgIGFzc2VydCgwKTsKICAgIH0KICAgIHJlcy0+bCA9IHVwZChyZXMtPmwsIGwsIHIsIEwsIE0sIGYpOwogICAgcmVzLT5yID0gdXBkKHJlcy0+ciwgbCwgciwgTSArIDEsIFIsIGYpOwogICAgcmV0dXJuIHJlczsKfQpub2RlX3QqIHVwZChub2RlX3QqIHAsIGludCBsLCBpbnQgciwgaW50IEwsIGludCBSLCBudW1fdCBhLCBudW1fdCBiKSB7CiAgICByZXR1cm4gdXBkKHAsIGwsIHIsIEwsIFIsIGZ1bmNfdChhLCBiKSk7Cn0KbnVtX3QgcXVlcnkobm9kZV90KiBwLCBpbnQgaSwgaW50IEwsIGludCBSKSB7CiAgICBpZiAoIXApIHJldHVybiBvbzsKICAgIGlmIChpIDwgTCB8fCBpID4gUikgcmV0dXJuIG9vOwogICAgbnVtX3QgcmVzID0gcC0+cXVlcnkoaSk7CiAgICBpZiAoTCA8IFIpIHsKICAgICAgICByZXMgPSBtaW4ocmVzLCBxdWVyeShwLT5sLCBpLCBMLCBMICsgUiA+PiAxKSk7CiAgICAgICAgcmVzID0gbWluKHJlcywgcXVlcnkocC0+ciwgaSwgKEwgKyBSID4+IDEpICsgMSwgUikpOwogICAgfQogICAgcmV0dXJuIHJlczsKfQoKaW50IG1haW4oKSB7CiAgICByZXR1cm4gMDsKfQ==