#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define DEBUG(...) 6
#endif
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
template<int MOD>
struct ModInt {
long long v;
ModInt(long long _v = 0) {v = (-MOD < _v && _v < MOD) ? _v : _v % MOD; if (v < 0) v += MOD;}
ModInt& operator += (const ModInt &other) {v += other.v; if (v >= MOD) v -= MOD; return *this;}
ModInt& operator -= (const ModInt &other) {v -= other.v; if (v < 0) v += MOD; return *this;}
ModInt& operator *= (const ModInt &other) {v = v * other.v % MOD; return *this;}
ModInt& operator /= (const ModInt &other) {return *this *= inverse(other);}
bool operator == (const ModInt &other) const {return v == other.v;}
bool operator != (const ModInt &other) const {return v != other.v;}
friend ModInt operator + (ModInt a, const ModInt &b) {return a += b;}
friend ModInt operator - (ModInt a, const ModInt &b) {return a -= b;}
friend ModInt operator * (ModInt a, const ModInt &b) {return a *= b;}
friend ModInt operator / (ModInt a, const ModInt &b) {return a /= b;}
friend ModInt operator - (const ModInt &a) {return 0 - a;}
friend ModInt power(ModInt a, long long b) {ModInt ret(1); while (b > 0) {if (b & 1) ret *= a; a *= a; b >>= 1;} return ret;}
friend ModInt inverse(ModInt a) {return power(a, MOD - 2);}
friend istream& operator >> (istream &is, ModInt &m) {is >> m.v; m.v = (-MOD < m.v && m.v < MOD) ? m.v : m.v % MOD; if (m.v < 0) m.v += MOD; return is;}
friend ostream& operator << (ostream &os, const ModInt &m) {return os << m.v;}
};
using M = ModInt<1000000007>;
struct SegmentTree {
struct Node {
int ti, lazyTi, l, r;
bool flag;
M sum, sumsq, ans, lazy, cumsum, cumsumsq;
void leaf(int val) {
ti = lazyTi = 0;
flag = false;
sum = val;
sumsq = M(val) * val;
ans = lazy = cumsum = cumsumsq = 0;
}
void pull(const Node &a, const Node &b) {
sum = a.sum + b.sum;
sumsq = a.sumsq + b.sumsq;
ti = max(a.ti, b.ti);
ans = a.ans + b.ans + (ti - a.ti) * a.sumsq + (ti - b.ti) * b.sumsq;
}
void push(const Node &other) {
if (flag) {
cumsumsq += lazy * lazy * (other.lazyTi - lazyTi) + 2 * lazy * other.cumsum + other.cumsumsq;
cumsum += lazy * (other.lazyTi - lazyTi) + other.cumsum;
} else {
cumsumsq = other.cumsumsq;
cumsum = other.cumsum;
}
lazy += other.lazy;
lazyTi = other.lazyTi;
flag = true;
}
void apply() {
// a^2 part
ans += sumsq * (lazyTi - ti);
// 2a * sum part
ans += 2 * sum * cumsum;
// sum^2 part
ans += (r - l + 1) * cumsumsq;
// update rest of stuff
sumsq += 2 * sum * lazy + (r - l + 1) * lazy * lazy;
sum += (r - l + 1) * lazy;
ti = lazyTi;
flag = false;
lazy = cumsum = cumsumsq = 0;
}
};
int n;
vector<int> a;
vector<Node> st;
SegmentTree(int _n) : n(_n), a(n), st(4*n) {
build(1, 0, n-1);
}
SegmentTree(const vector<int> &_a) : n((int) _a.size()), a(_a), st(4*n) {
build(1, 0, n-1);
}
void build(int p, int l, int r) {
st[p].l = l;
st[p].r = r;
if (l == r) {
st[p].leaf(a[l]);
return;
}
int m = (l + r) / 2;
build(2*p, l, m);
build(2*p+1, m+1, r);
st[p].pull(st[2*p], st[2*p+1]);
}
void push(int p) {
if (st[p].flag) {
if (st[p].l != st[p].r) {
st[2*p].push(st[p]);
st[2*p+1].push(st[p]);
}
st[p].apply();
}
}
Node query(int p, int i, int j) {
push(p);
if (st[p].l == i && st[p].r == j)
return st[p];
int m = (st[p].l + st[p].r) / 2;
if (j <= m)
return query(2*p, i, j);
else if (i > m)
return query(2*p+1, i, j);
Node ret, ls = query(2*p, i, m), rs = query(2*p+1, m+1, j);
ret.pull(ls, rs);
return ret;
}
M query(int i, int j, long long ti) {
Node ret = query(1, i, j);
return ret.ans + (ti - ret.ti) * ret.sumsq;
}
void update(int p, int i, int j, int val, int ti) {
if (st[p].l == i && st[p].r == j) {
Node cur;
cur.flag = true;
cur.lazyTi = ti;
cur.lazy = val;
cur.cumsum = cur.cumsumsq = 0;
st[p].push(cur);
push(p);
return;
}
push(p);
int m = (st[p].l + st[p].r) / 2;
if (j <= m) {
update(2*p, i, j, val, ti);
push(2*p+1);
} else if (i > m) {
push(2*p);
update(2*p+1, i, j, val, ti);
} else {
update(2*p, i, m, val, ti);
update(2*p+1, m+1, j, val, ti);
}
st[p].pull(st[2*p], st[2*p+1]);
}
void update(int i, int j, int val, int ti) {
update(1, i, j, val, ti);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, q;
cin >> n >> m >> q;
vector<int> a(n);
for (int i=0; i<n; i++)
cin >> a[i];
vector<array<int, 3>> modif;
for (int i=0; i<m; i++) {
int l, r, x;
cin >> l >> r >> x;
l--, r--;
modif.push_back({l, r, x});
}
vector<vector<array<int, 4>>> queries(m + 1);
for (int i=0; i<q; i++) {
int l, r, x, y;
cin >> l >> r >> x >> y;
l--, r--;
if (x > 0)
queries[x-1].push_back({l, r, i, -1});
queries[y].push_back({l, r, i, 1});
}
SegmentTree st(a);
vector<M> ret(q);
for (int i=0; i<m; i++) {
for (auto [l, r, j, c] : queries[i])
ret[j] += c * st.query(l, r, (long long) i + 1);
st.update(modif[i][0], modif[i][1], modif[i][2], i + 1);
}
for (auto [l, r, j, c] : queries[m])
ret[j] += c * st.query(l, r, (long long) m + 1);
for (int i=0; i<q; i++)
cout << ret[i] << "\n";
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojaWZkZWYgTE9DQUwKI2RlZmluZSBERUJVRyguLi4pIGRlYnVnKCNfX1ZBX0FSR1NfXywgX19WQV9BUkdTX18pCiNlbHNlCiNkZWZpbmUgREVCVUcoLi4uKSA2CiNlbmRpZgoKdGVtcGxhdGU8dHlwZW5hbWUgVCwgdHlwZW5hbWUgUz4gb3N0cmVhbSYgb3BlcmF0b3IgPDwgKG9zdHJlYW0gJm9zLCBjb25zdCBwYWlyPFQsIFM+ICZwKSB7cmV0dXJuIG9zIDw8ICIoIiA8PCBwLmZpcnN0IDw8ICIsICIgPDwgcC5zZWNvbmQgPDwgIikiO30KdGVtcGxhdGU8dHlwZW5hbWUgQywgdHlwZW5hbWUgVCA9IGRlY2F5PGRlY2x0eXBlKCpiZWdpbihkZWNsdmFsPEM+KCkpKT4sIHR5cGVuYW1lIGVuYWJsZV9pZjwhaXNfc2FtZTxDLCBzdHJpbmc+Ojp2YWx1ZT46OnR5cGUqID0gbnVsbHB0cj4Kb3N0cmVhbSYgb3BlcmF0b3IgPDwgKG9zdHJlYW0gJm9zLCBjb25zdCBDICZjKSB7Ym9vbCBmID0gdHJ1ZTsgb3MgPDwgIlsiOyBmb3IgKGNvbnN0IGF1dG8gJnggOiBjKSB7aWYgKCFmKSBvcyA8PCAiLCAiOyBmID0gZmFsc2U7IG9zIDw8IHg7fSByZXR1cm4gb3MgPDwgIl0iO30KdGVtcGxhdGU8dHlwZW5hbWUgVD4gdm9pZCBkZWJ1ZyhzdHJpbmcgcywgVCB4KSB7Y2VyciA8PCAiXDAzM1sxOzM1bSIgPDwgcyA8PCAiXDAzM1swOzMybSA9IFwwMzNbMzNtIiA8PCB4IDw8ICJcMDMzWzBtXG4iO30KdGVtcGxhdGU8dHlwZW5hbWUgVCwgdHlwZW5hbWUuLi4gQXJncz4gdm9pZCBkZWJ1ZyhzdHJpbmcgcywgVCB4LCBBcmdzLi4uIGFyZ3MpIHtmb3IgKGludCBpPTAsIGI9MDsgaTwoaW50KXMuc2l6ZSgpOyBpKyspIGlmIChzW2ldID09ICcoJyB8fCBzW2ldID09ICd7JykgYisrOyBlbHNlCmlmIChzW2ldID09ICcpJyB8fCBzW2ldID09ICd9JykgYi0tOyBlbHNlIGlmIChzW2ldID09ICcsJyAmJiBiID09IDApIHtjZXJyIDw8ICJcMDMzWzE7MzVtIiA8PCBzLnN1YnN0cigwLCBpKSA8PCAiXDAzM1swOzMybSA9IFwwMzNbMzNtIiA8PCB4IDw8ICJcMDMzWzMxbSB8ICI7IGRlYnVnKHMuc3Vic3RyKHMuZmluZF9maXJzdF9ub3Rfb2YoJyAnLCBpICsgMSkpLCBhcmdzLi4uKTsgYnJlYWs7fX0KCnRlbXBsYXRlPGludCBNT0Q+CnN0cnVjdCBNb2RJbnQgewogICAgbG9uZyBsb25nIHY7CiAgICBNb2RJbnQobG9uZyBsb25nIF92ID0gMCkge3YgPSAoLU1PRCA8IF92ICYmIF92IDwgTU9EKSA/IF92IDogX3YgJSBNT0Q7IGlmICh2IDwgMCkgdiArPSBNT0Q7fQogICAgTW9kSW50JiBvcGVyYXRvciArPSAoY29uc3QgTW9kSW50ICZvdGhlcikge3YgKz0gb3RoZXIudjsgaWYgKHYgPj0gTU9EKSB2IC09IE1PRDsgcmV0dXJuICp0aGlzO30KICAgIE1vZEludCYgb3BlcmF0b3IgLT0gKGNvbnN0IE1vZEludCAmb3RoZXIpIHt2IC09IG90aGVyLnY7IGlmICh2IDwgMCkgdiArPSBNT0Q7IHJldHVybiAqdGhpczt9CiAgICBNb2RJbnQmIG9wZXJhdG9yICo9IChjb25zdCBNb2RJbnQgJm90aGVyKSB7diA9IHYgKiBvdGhlci52ICUgTU9EOyByZXR1cm4gKnRoaXM7fQogICAgTW9kSW50JiBvcGVyYXRvciAvPSAoY29uc3QgTW9kSW50ICZvdGhlcikge3JldHVybiAqdGhpcyAqPSBpbnZlcnNlKG90aGVyKTt9CiAgICBib29sIG9wZXJhdG9yID09IChjb25zdCBNb2RJbnQgJm90aGVyKSBjb25zdCB7cmV0dXJuIHYgPT0gb3RoZXIudjt9CiAgICBib29sIG9wZXJhdG9yICE9IChjb25zdCBNb2RJbnQgJm90aGVyKSBjb25zdCB7cmV0dXJuIHYgIT0gb3RoZXIudjt9CiAgICBmcmllbmQgTW9kSW50IG9wZXJhdG9yICsgKE1vZEludCBhLCBjb25zdCBNb2RJbnQgJmIpIHtyZXR1cm4gYSArPSBiO30KICAgIGZyaWVuZCBNb2RJbnQgb3BlcmF0b3IgLSAoTW9kSW50IGEsIGNvbnN0IE1vZEludCAmYikge3JldHVybiBhIC09IGI7fQogICAgZnJpZW5kIE1vZEludCBvcGVyYXRvciAqIChNb2RJbnQgYSwgY29uc3QgTW9kSW50ICZiKSB7cmV0dXJuIGEgKj0gYjt9CiAgICBmcmllbmQgTW9kSW50IG9wZXJhdG9yIC8gKE1vZEludCBhLCBjb25zdCBNb2RJbnQgJmIpIHtyZXR1cm4gYSAvPSBiO30KICAgIGZyaWVuZCBNb2RJbnQgb3BlcmF0b3IgLSAoY29uc3QgTW9kSW50ICZhKSB7cmV0dXJuIDAgLSBhO30KICAgIGZyaWVuZCBNb2RJbnQgcG93ZXIoTW9kSW50IGEsIGxvbmcgbG9uZyBiKSB7TW9kSW50IHJldCgxKTsgd2hpbGUgKGIgPiAwKSB7aWYgKGIgJiAxKSByZXQgKj0gYTsgYSAqPSBhOyBiID4+PSAxO30gcmV0dXJuIHJldDt9CiAgICBmcmllbmQgTW9kSW50IGludmVyc2UoTW9kSW50IGEpIHtyZXR1cm4gcG93ZXIoYSwgTU9EIC0gMik7fQogICAgZnJpZW5kIGlzdHJlYW0mIG9wZXJhdG9yID4+IChpc3RyZWFtICZpcywgTW9kSW50ICZtKSB7aXMgPj4gbS52OyBtLnYgPSAoLU1PRCA8IG0udiAmJiBtLnYgPCBNT0QpID8gbS52IDogbS52ICUgTU9EOyBpZiAobS52IDwgMCkgbS52ICs9IE1PRDsgcmV0dXJuIGlzO30KICAgIGZyaWVuZCBvc3RyZWFtJiBvcGVyYXRvciA8PCAob3N0cmVhbSAmb3MsIGNvbnN0IE1vZEludCAmbSkge3JldHVybiBvcyA8PCBtLnY7fQp9Owp1c2luZyBNID0gTW9kSW50PDEwMDAwMDAwMDc+OwoKc3RydWN0IFNlZ21lbnRUcmVlIHsKICAgIHN0cnVjdCBOb2RlIHsKICAgICAgICBpbnQgdGksIGxhenlUaSwgbCwgcjsKICAgICAgICBib29sIGZsYWc7CiAgICAgICAgTSBzdW0sIHN1bXNxLCBhbnMsIGxhenksIGN1bXN1bSwgY3Vtc3Vtc3E7CgogICAgICAgIHZvaWQgbGVhZihpbnQgdmFsKSB7CiAgICAgICAgICAgIHRpID0gbGF6eVRpID0gMDsKICAgICAgICAgICAgZmxhZyA9IGZhbHNlOwogICAgICAgICAgICBzdW0gPSB2YWw7CiAgICAgICAgICAgIHN1bXNxID0gTSh2YWwpICogdmFsOwogICAgICAgICAgICBhbnMgPSBsYXp5ID0gY3Vtc3VtID0gY3Vtc3Vtc3EgPSAwOwogICAgICAgIH0KCiAgICAgICAgdm9pZCBwdWxsKGNvbnN0IE5vZGUgJmEsIGNvbnN0IE5vZGUgJmIpIHsKICAgICAgICAgICAgc3VtID0gYS5zdW0gKyBiLnN1bTsKICAgICAgICAgICAgc3Vtc3EgPSBhLnN1bXNxICsgYi5zdW1zcTsKICAgICAgICAgICAgdGkgPSBtYXgoYS50aSwgYi50aSk7CiAgICAgICAgICAgIGFucyA9IGEuYW5zICsgYi5hbnMgKyAodGkgLSBhLnRpKSAqIGEuc3Vtc3EgKyAodGkgLSBiLnRpKSAqIGIuc3Vtc3E7CiAgICAgICAgfQoKICAgICAgICB2b2lkIHB1c2goY29uc3QgTm9kZSAmb3RoZXIpIHsKICAgICAgICAgICAgaWYgKGZsYWcpIHsKICAgICAgICAgICAgICAgIGN1bXN1bXNxICs9IGxhenkgKiBsYXp5ICogKG90aGVyLmxhenlUaSAtIGxhenlUaSkgKyAyICogbGF6eSAqIG90aGVyLmN1bXN1bSArIG90aGVyLmN1bXN1bXNxOwogICAgICAgICAgICAgICAgY3Vtc3VtICs9IGxhenkgKiAob3RoZXIubGF6eVRpIC0gbGF6eVRpKSArIG90aGVyLmN1bXN1bTsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGN1bXN1bXNxID0gb3RoZXIuY3Vtc3Vtc3E7CiAgICAgICAgICAgICAgICBjdW1zdW0gPSBvdGhlci5jdW1zdW07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgbGF6eSArPSBvdGhlci5sYXp5OwogICAgICAgICAgICBsYXp5VGkgPSBvdGhlci5sYXp5VGk7CiAgICAgICAgICAgIGZsYWcgPSB0cnVlOwogICAgICAgIH0KCiAgICAgICAgdm9pZCBhcHBseSgpIHsKICAgICAgICAgICAgLy8gYV4yIHBhcnQKICAgICAgICAgICAgYW5zICs9IHN1bXNxICogKGxhenlUaSAtIHRpKTsKICAgICAgICAgICAgLy8gMmEgKiBzdW0gcGFydAogICAgICAgICAgICBhbnMgKz0gMiAqIHN1bSAqIGN1bXN1bTsKICAgICAgICAgICAgLy8gc3VtXjIgcGFydAogICAgICAgICAgICBhbnMgKz0gKHIgLSBsICsgMSkgKiBjdW1zdW1zcTsKICAgICAgICAgICAgLy8gdXBkYXRlIHJlc3Qgb2Ygc3R1ZmYKICAgICAgICAgICAgc3Vtc3EgKz0gMiAqIHN1bSAqIGxhenkgKyAociAtIGwgKyAxKSAqIGxhenkgKiBsYXp5OwogICAgICAgICAgICBzdW0gKz0gKHIgLSBsICsgMSkgKiBsYXp5OwogICAgICAgICAgICB0aSA9IGxhenlUaTsKICAgICAgICAgICAgZmxhZyA9IGZhbHNlOwogICAgICAgICAgICBsYXp5ID0gY3Vtc3VtID0gY3Vtc3Vtc3EgPSAwOwogICAgICAgIH0KICAgIH07CgogICAgaW50IG47CiAgICB2ZWN0b3I8aW50PiBhOwogICAgdmVjdG9yPE5vZGU+IHN0OwoKICAgIFNlZ21lbnRUcmVlKGludCBfbikgOiBuKF9uKSwgYShuKSwgc3QoNCpuKSB7CiAgICAgICAgYnVpbGQoMSwgMCwgbi0xKTsKICAgIH0KCiAgICBTZWdtZW50VHJlZShjb25zdCB2ZWN0b3I8aW50PiAmX2EpIDogbigoaW50KSBfYS5zaXplKCkpLCBhKF9hKSwgc3QoNCpuKSB7CiAgICAgICAgYnVpbGQoMSwgMCwgbi0xKTsKICAgIH0KCiAgICB2b2lkIGJ1aWxkKGludCBwLCBpbnQgbCwgaW50IHIpIHsKICAgICAgICBzdFtwXS5sID0gbDsKICAgICAgICBzdFtwXS5yID0gcjsKICAgICAgICBpZiAobCA9PSByKSB7CiAgICAgICAgICAgIHN0W3BdLmxlYWYoYVtsXSk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgaW50IG0gPSAobCArIHIpIC8gMjsKICAgICAgICBidWlsZCgyKnAsIGwsIG0pOwogICAgICAgIGJ1aWxkKDIqcCsxLCBtKzEsIHIpOwogICAgICAgIHN0W3BdLnB1bGwoc3RbMipwXSwgc3RbMipwKzFdKTsKICAgIH0KCiAgICB2b2lkIHB1c2goaW50IHApIHsKICAgICAgICBpZiAoc3RbcF0uZmxhZykgewogICAgICAgICAgICBpZiAoc3RbcF0ubCAhPSBzdFtwXS5yKSB7CiAgICAgICAgICAgICAgICBzdFsyKnBdLnB1c2goc3RbcF0pOwogICAgICAgICAgICAgICAgc3RbMipwKzFdLnB1c2goc3RbcF0pOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHN0W3BdLmFwcGx5KCk7CiAgICAgICAgfQogICAgfQoKICAgIE5vZGUgcXVlcnkoaW50IHAsIGludCBpLCBpbnQgaikgewogICAgICAgIHB1c2gocCk7CiAgICAgICAgaWYgKHN0W3BdLmwgPT0gaSAmJiBzdFtwXS5yID09IGopCiAgICAgICAgICAgIHJldHVybiBzdFtwXTsKICAgICAgICBpbnQgbSA9IChzdFtwXS5sICsgc3RbcF0ucikgLyAyOwogICAgICAgIGlmIChqIDw9IG0pCiAgICAgICAgICAgIHJldHVybiBxdWVyeSgyKnAsIGksIGopOwogICAgICAgIGVsc2UgaWYgKGkgPiBtKQogICAgICAgICAgICByZXR1cm4gcXVlcnkoMipwKzEsIGksIGopOwogICAgICAgIE5vZGUgcmV0LCBscyA9IHF1ZXJ5KDIqcCwgaSwgbSksIHJzID0gcXVlcnkoMipwKzEsIG0rMSwgaik7CiAgICAgICAgcmV0LnB1bGwobHMsIHJzKTsKICAgICAgICByZXR1cm4gcmV0OwogICAgfQoKICAgIE0gcXVlcnkoaW50IGksIGludCBqLCBsb25nIGxvbmcgdGkpIHsKICAgICAgICBOb2RlIHJldCA9IHF1ZXJ5KDEsIGksIGopOwogICAgICAgIHJldHVybiByZXQuYW5zICsgKHRpIC0gcmV0LnRpKSAqIHJldC5zdW1zcTsKICAgIH0KCiAgICB2b2lkIHVwZGF0ZShpbnQgcCwgaW50IGksIGludCBqLCBpbnQgdmFsLCBpbnQgdGkpIHsKICAgICAgICBpZiAoc3RbcF0ubCA9PSBpICYmIHN0W3BdLnIgPT0gaikgewogICAgICAgICAgICBOb2RlIGN1cjsKICAgICAgICAgICAgY3VyLmZsYWcgPSB0cnVlOwogICAgICAgICAgICBjdXIubGF6eVRpID0gdGk7CiAgICAgICAgICAgIGN1ci5sYXp5ID0gdmFsOwogICAgICAgICAgICBjdXIuY3Vtc3VtID0gY3VyLmN1bXN1bXNxID0gMDsKICAgICAgICAgICAgc3RbcF0ucHVzaChjdXIpOwogICAgICAgICAgICBwdXNoKHApOwogICAgICAgICAgICByZXR1cm47CiAgICAgICAgfQogICAgICAgIHB1c2gocCk7CiAgICAgICAgaW50IG0gPSAoc3RbcF0ubCArIHN0W3BdLnIpIC8gMjsKICAgICAgICBpZiAoaiA8PSBtKSB7CiAgICAgICAgICAgIHVwZGF0ZSgyKnAsIGksIGosIHZhbCwgdGkpOwogICAgICAgICAgICBwdXNoKDIqcCsxKTsKICAgICAgICB9IGVsc2UgaWYgKGkgPiBtKSB7CiAgICAgICAgICAgIHB1c2goMipwKTsKICAgICAgICAgICAgdXBkYXRlKDIqcCsxLCBpLCBqLCB2YWwsIHRpKTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICB1cGRhdGUoMipwLCBpLCBtLCB2YWwsIHRpKTsKICAgICAgICAgICAgdXBkYXRlKDIqcCsxLCBtKzEsIGosIHZhbCwgdGkpOwogICAgICAgIH0KICAgICAgICBzdFtwXS5wdWxsKHN0WzIqcF0sIHN0WzIqcCsxXSk7CiAgICB9CgogICAgdm9pZCB1cGRhdGUoaW50IGksIGludCBqLCBpbnQgdmFsLCBpbnQgdGkpIHsKICAgICAgICB1cGRhdGUoMSwgaSwgaiwgdmFsLCB0aSk7CiAgICB9Cn07CgppbnQgbWFpbigpIHsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShOVUxMKTsKCiAgICBpbnQgbiwgbSwgcTsKICAgIGNpbiA+PiBuID4+IG0gPj4gcTsKICAgIHZlY3RvcjxpbnQ+IGEobik7CiAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKQogICAgICAgIGNpbiA+PiBhW2ldOwoKICAgIHZlY3RvcjxhcnJheTxpbnQsIDM+PiBtb2RpZjsKICAgIGZvciAoaW50IGk9MDsgaTxtOyBpKyspIHsKICAgICAgICBpbnQgbCwgciwgeDsKICAgICAgICBjaW4gPj4gbCA+PiByID4+IHg7CiAgICAgICAgbC0tLCByLS07CiAgICAgICAgbW9kaWYucHVzaF9iYWNrKHtsLCByLCB4fSk7CiAgICB9CgogICAgdmVjdG9yPHZlY3RvcjxhcnJheTxpbnQsIDQ+Pj4gcXVlcmllcyhtICsgMSk7CiAgICBmb3IgKGludCBpPTA7IGk8cTsgaSsrKSB7CiAgICAgICAgaW50IGwsIHIsIHgsIHk7CiAgICAgICAgY2luID4+IGwgPj4gciA+PiB4ID4+IHk7CiAgICAgICAgbC0tLCByLS07CiAgICAgICAgaWYgKHggPiAwKQogICAgICAgICAgICBxdWVyaWVzW3gtMV0ucHVzaF9iYWNrKHtsLCByLCBpLCAtMX0pOwogICAgICAgIHF1ZXJpZXNbeV0ucHVzaF9iYWNrKHtsLCByLCBpLCAxfSk7CiAgICB9CgogICAgU2VnbWVudFRyZWUgc3QoYSk7CiAgICB2ZWN0b3I8TT4gcmV0KHEpOwogICAgZm9yIChpbnQgaT0wOyBpPG07IGkrKykgewogICAgICAgIGZvciAoYXV0byBbbCwgciwgaiwgY10gOiBxdWVyaWVzW2ldKQogICAgICAgICAgICByZXRbal0gKz0gYyAqIHN0LnF1ZXJ5KGwsIHIsIChsb25nIGxvbmcpIGkgKyAxKTsKICAgICAgICBzdC51cGRhdGUobW9kaWZbaV1bMF0sIG1vZGlmW2ldWzFdLCBtb2RpZltpXVsyXSwgaSArIDEpOwogICAgfQogICAgZm9yIChhdXRvIFtsLCByLCBqLCBjXSA6IHF1ZXJpZXNbbV0pCiAgICAgICAgcmV0W2pdICs9IGMgKiBzdC5xdWVyeShsLCByLCAobG9uZyBsb25nKSBtICsgMSk7CgogICAgZm9yIChpbnQgaT0wOyBpPHE7IGkrKykKICAgICAgICBjb3V0IDw8IHJldFtpXSA8PCAiXG4iOwoKICAgIHJldHVybiAwOwp9Cg==