#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python!
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;
// pairs
#define mp make_pair
#define f first
#define s second
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front
#define rtn return
#define lb lower_bound
#define ub upper_bound
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
// bitwise ops
// also see https://g...content-available-to-author-only...u.org/onlinedocs/gcc/Other-Builtins.html
constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ...
return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
tcT> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; }
tcTU> T fstTrue(T lo, T hi, U f) {
hi ++; assert(lo <= hi); // assuming f is increasing
while (lo < hi) { // find first index such that f is true
T mid = lo+(hi-lo)/2;
f(mid) ? hi = mid : lo = mid+1;
}
return lo;
}
tcTU> T lstTrue(T lo, T hi, U f) {
lo --; assert(lo <= hi); // assuming f is decreasing
while (lo < hi) { // find first index such that f is true
T mid = lo+(hi-lo+1)/2;
f(mid) ? lo = mid : hi = mid-1;
}
return lo;
}
tcT> void remDup(vector<T>& v) { // sort and remove duplicates
sort(all(v)); v.erase(unique(all(v)),end(v)); }
tcTU> void erase(T& t, const U& u) { // don't erase
auto it = t.find(u); assert(it != end(t));
t.erase(it); } // element that doesn't exist from (multi)set
#define tcTUU tcT, class ...U
inline namespace Helpers {
//////////// is_iterable
// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
// this gets used only when we can call begin() and end() on that type
tcT, class = void> struct is_iterable : false_type {};
tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
decltype(end(declval<T>()))
>
> : true_type {};
tcT> constexpr bool is_iterable_v = is_iterable<T>::value;
//////////// is_readable
tcT, class = void> struct is_readable : false_type {};
tcT> struct is_readable<T,
typename std::enable_if_t<
is_same_v<decltype(cin >> declval<T&>()), istream&>
>
> : true_type {};
tcT> constexpr bool is_readable_v = is_readable<T>::value;
//////////// is_printable
// // https://n...content-available-to-author-only...e.es/posts/2020-02-29-is-printable/
tcT, class = void> struct is_printable : false_type {};
tcT> struct is_printable<T,
typename std::enable_if_t<
is_same_v<decltype(cout << declval<T>()), ostream&>
>
> : true_type {};
tcT> constexpr bool is_printable_v = is_printable<T>::value;
}
inline namespace Input {
tcT> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
tcTUU> void re(T& t, U&... u);
tcTU> void re(pair<T,U>& p); // pairs
// re: read
tcT> typename enable_if<is_readable_v<T>,void>::type re(T& x) { cin >> x; } // default
tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } // complex
tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i); // ex. vectors, arrays
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i) {
each(x,i) re(x); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); } // read multiple
// rv: resize and read vectors
void rv(size_t) {}
tcTUU> void rv(size_t N, V<T>& t, U&... u);
template<class...U> void rv(size_t, size_t N2, U&... u);
tcTUU> void rv(size_t N, V<T>& t, U&... u) {
t.rsz(N); re(t);
rv(N,u...); }
template<class...U> void rv(size_t, size_t N2, U&... u) {
rv(N2,u...); }
// dumb shortcuts to read in ints
void decrement() {} // subtract one from each
tcTUU> void decrement(T& t, U&... u) { --t; decrement(u...); }
#define ints(...) int __VA_ARGS__; re(__VA_ARGS__);
#define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);
}
inline namespace ToString {
tcT> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;
// ts: string representation to print
tcT> typename enable_if<is_printable_v<T>,str>::type ts(T v) {
stringstream ss; ss << fixed << setprecision(15) << v;
return ss.str(); } // default
tcT> str bit_vec(T t) { // bit vector to string
str res = "{"; F0R(i,sz(t)) res += ts(t[i]);
res += "}"; return res; }
str ts(V<bool> v) { return bit_vec(v); }
template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); } // bit vector
tcTU> str ts(pair<T,U> p); // pairs
tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v); // vectors, arrays
tcTU> str ts(pair<T,U> p) { return "("+ts(p.f)+", "+ts(p.s)+")"; }
tcT> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep) {
// convert container to string w/ separator sep
bool fst = 1; str res = "";
for (const auto& x: v) {
if (!fst) res += sep;
fst = 0; res += ts(x);
}
return res;
}
tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v) {
return "{"+ts_sep(v,", ")+"}"; }
// for nested DS
template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type
ts_lev(const T& v) { return {ts(v)}; }
template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type
ts_lev(const T& v) {
if (lev == 0 || !sz(v)) return {ts(v)};
vs res;
for (const auto& t: v) {
if (sz(res)) res.bk += ",";
vs tmp = ts_lev<lev-1>(t);
res.ins(end(res),all(tmp));
}
F0R(i,sz(res)) {
str bef = " "; if (i == 0) bef = "{";
res[i] = bef+res[i];
}
res.bk += "}";
return res;
}
}
inline namespace Output {
template<class T> void pr_sep(ostream& os, str, const T& t) { os << ts(t); }
template<class T, class... U> void pr_sep(ostream& os, str sep, const T& t, const U&... u) {
pr_sep(os,sep,t); os << sep; pr_sep(os,sep,u...); }
// print w/ no spaces
template<class ...T> void pr(const T&... t) { pr_sep(cout,"",t...); }
// print w/ spaces, end with newline
void ps() { cout << "\n"; }
template<class ...T> void ps(const T&... t) { pr_sep(cout," ",t...); ps(); }
// debug to cerr
template<class ...T> void dbg_out(const T&... t) {
pr_sep(cerr," | ",t...); cerr << endl; }
void loc_info(int line, str names) {
cerr << "Line(" << line << ") -> [" << names << "]: "; }
template<int lev, class T> void dbgl_out(const T& t) {
cerr << "\n\n" << ts_sep(ts_lev<lev>(t),"\n") << "\n" << endl; }
#ifdef LOCAL
#define dbg(...) loc_info(__LINE__,#__VA_ARGS__), dbg_out(__VA_ARGS__)
#define dbgl(lev,x) loc_info(__LINE__,#x), dbgl_out<lev>(x)
#else // don't actually submit with this
#define dbg(...) 0
#define dbgl(lev,x) 0
#endif
}
inline namespace FileIO {
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void setIO(str s = "") {
cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams
// cin.exceptions(cin.failbit);
// throws exception when do smth illegal
// ex. try to read letter into int
if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for old USACO
}
}
pl& operator+=(pl& a, pl b) { return a = {a.f+b.f,a.s+b.s}; }
pl operator-(pl a, pl b) { return {a.f-b.f,a.s-b.s}; }
/**
* Description: range sum queries and point updates for $D$ dimensions
* Source: https://c...content-available-to-author-only...s.com/blog/entry/64914
* Verification: SPOJ matsum
* Usage: \texttt{BIT<int,10,10>} gives 2D BIT
* Time: O((\log N)^D)
*/
template <class T, int ...Ns> struct BIT {
T val{}; void upd(T v) { val += v; }
T query() { return val; }
};
template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
BIT<T,Ns...> bit[N+1];
template<typename... Args> void upd(int pos, Args... args) { assert(pos > 0);
for (; pos<=N; pos+=pos&-pos) bit[pos].upd(args...); }
template<typename... Args> T sum(int r, Args... args) {
T res{}; for (;r;r-=r&-r) res += bit[r].query(args...);
return res; }
template<typename... Args> T query(int l, int r, Args...
args) { return sum(r,args...)-sum(l-1,args...); }
};
BIT<pl,MX> BB;
/**
* Description: 1D range minimum query. Can also do queries
* for any associative operation in $O(1)$ with D\&C
* Source: KACTL
* Verification:
* https://c...content-available-to-author-only...s.fi/problemset/stats/1647/
* http://w...content-available-to-author-only...g.com/problem/ioi1223
* https://p...content-available-to-author-only...n.com/ChpniVZL
* Memory: O(N\log N)
* Time: O(1)
*/
template<class T> struct RMQ { // floor(log_2(x))
int level(int x) { return 31-__builtin_clz(x); }
vector<T> v; vector<vi> jmp;
int comb(int a, int b) { // index of min
return v[a]==v[b]?min(a,b):(v[a]>v[b]?a:b); }
void init(const vector<T>& _v) {
v = _v; jmp = {vi(sz(v))}; iota(all(jmp[0]),0);
for (int j = 1; 1<<j <= sz(v); ++j) {
jmp.pb(vi(sz(v)-(1<<j)+1));
F0R(i,sz(jmp[j])) jmp[j][i] = comb(jmp[j-1][i],
jmp[j-1][i+(1<<(j-1))]);
}
}
int index(int l, int r) { // get index of min element
assert(l <= r); int d = level(r-l+1);
return comb(jmp[d][l],jmp[d][r-(1<<d)+1]); }
T query(int l, int r) { return v[index(l,r)]; }
};
RMQ<int> R;
struct interval {
int lef, rig, mul;
ll len, contrib;
};
V<interval> intervals;
int N,M;
int start[MX];
vi A,B;
V<tuple<int,int,int>> queries;
vl ans, cum{0,0};
vpi v;
int get_x_0(pi p) {
if (p.s == 1) return intervals[p.f].lef;
return get<0>(queries[p.f]);
}
pi get_x(pi p) { return mp(get_x_0(p),p.s); }
int get_y_0(pi p) {
if (p.s == 1) return intervals[p.f].rig;
return get<1>(queries[p.f]);
}
pi get_y(pi p) { return mp(get_y_0(p),p.s); }
ll get_z_0(pi p) {
if (p.s == 1) return intervals[p.f].len;
return get<2>(queries[p.f]);
}
pair<ll,int> get_z(pi p) { return mp(get_z_0(p),p.s); }
vpl aa;
void divi(int l, int r) {
if (l == r) return;
int m = (l+r)/2;
divi(l,m); divi(m+1,r);
vpi tmp;
FOR(i,l,m+1) {
pi a = v[i];
if (a.s == 0) tmp.pb(a);
}
FOR(j,m+1,r+1) {
pi b = v[j];
if (b.s == 1) tmp.pb(b);
}
sort(all(tmp),[](pi a, pi b) {
return get_y(a) < get_y(b);
});
R0F(i,sz(tmp)) {
pi a = tmp[i];
if (a.s == 1) {
int x = get_x_0(a);
if (x > 0) BB.upd(x,pl{intervals[a.f].contrib,intervals[a.f].mul});
} else {
pl p = BB.query(get_x_0(a),N+2);
aa[a.f].f += p.f;
aa[a.f].s += p.s;
}
}
R0F(i,sz(tmp)) {
pi a = tmp[i];
if (a.s == 1) {
int x = get_x_0(a);
if (x > 0) BB.upd(x,pl{-intervals[a.f].contrib,-intervals[a.f].mul});
}
}
// F0R(i,sz(tmp)) FOR(j,i+1,sz(tmp)) {
// pi a = tmp[i], b = tmp[j];
// if (a.s == 0 && b.s == 1 && get_x(a) < get_x(b)) {
// aa[a.f].f += intervals[b.f].contrib;
// aa[a.f].s += intervals[b.f].mul;
// }
// }
// for (pi a: a_tmp) for (pi b: b_tmp) {
// if (get_x(a) < get_x(b))
// if (get_y(a) < get_y(b)) {
// aa[a.f].f += intervals[b.f].contrib;
// aa[a.f].s += intervals[b.f].mul;
// }
// }
}
void deal1() {
BB = BIT<pl,MX>();
aa.rsz(M);
each(p,intervals) {
p.contrib = p.mul*p.len;
p.rig *= -1;
-- p.len;
}
each(t,queries) get<1>(t) *= -1;
F0R(i,M) if (ans[i] != -1) {
int S,T,U; tie(S,T,U) = queries[i];
// each(p,intervals) if (S <= p.lef && T <= p.rig && U <= p.len) {
// aa[i].f += p.contrib;
// aa[i].s += p.mul;
// }
}
vpi ii,qq;
F0R(i,sz(intervals)) {
v.pb({i,1});
ii.pb({i,1});
}
F0R(i,sz(queries)) {
v.pb({i,0});
qq.pb({i,0});
}
// for (pi a: qq) for (pi b: ii)
// if (get_x(a) < get_x(b))
// if (get_y(a) < get_y(b))
// if (get_z(a) < get_z(b)) {
// aa[a.f].f += intervals[b.f].contrib;
// aa[a.f].s += intervals[b.f].mul;
// }
// F0R(i,sz(queries)) F0R(j,sz(intervals))
sort(all(v),[&](pi a, pi b) {
return get_z(a) < get_z(b);
});
divi(0,sz(v)-1);
F0R(i,M) if (ans[i] != -1) {
int S,T,U; tie(S,T,U) = queries[i];
ans[i] += aa[i].f-aa[i].s*U;
}
}
void deal2() {
V<AR<ll,5>> contrib;
// dbg("START",ans[0]);
F0R(i,M) if (ans[i] != -1) {
int S,T,U; tie(S,T,U) = queries[i];
int maxLef = lstTrue(0,N+2,[&](int x) {
return cum[x] <= cum[T]-U;
});
int lo = S, hi = min(T-1,maxLef);
if (lo <= hi) {
contrib.pb({hi, T,cum[T]-U,i,1});
contrib.pb({lo-1,T,cum[T]-U,i,-1});
// each(p,intervals) if (p.lef <= hi) {
// if (p.rig > T) ans[i] += p.mul*(-cum[p.lef]+cum[T]-U);
// }
// each(p,intervals) if (p.lef <= lo-1) {
// if (p.rig > T) ans[i] -= p.mul*(-cum[p.lef]+cum[T]-U);
// }
}
}
sor(contrib);
BB = BIT<pl,MX>();
int ind = 0;
each(t,contrib) {
for(;ind < sz(intervals) && intervals[ind].lef <= t[0];++ind) {
const auto& p = intervals[ind];
BB.upd(p.rig,pl{-p.mul*cum[p.lef],p.mul});
}
pl p = BB.query((int)t[1]+1,N+2);
// dbg("AH",p.f+p.s*t[2],t[3],t[4]);
assert(t[3] < sz(ans));
ans[t[3]] += t[4]*(p.f+p.s*t[2]);
}
// dbg("END",ans[0]);
}
int main() {
setIO(); re(N,M);
A.rsz(N+1), B.rsz(N+1);
FOR(i,1,N+1) re(A[i]);
FOR(i,1,N+1) re(B[i]);
R.init(A);
FOR(i,1,N+1) cum.pb(cum.bk+A[i]);
cum.pb(cum.bk);
assert(sz(cum)-1 == N+2);
set<int> cur{0,N+2};
vi inds; FOR(i,1,N+2) inds.pb(i);
// F0R(i,N+2) {
// rig[i] = i+1;
// lef[i+1] = i;
// }
sort(all(inds),[&](int x, int y) {
return B[x] < B[y]; });
for (int x: inds) {
cur.ins(x);
auto it = cur.find(x);
int l = *prev(it), r = *next(it);
intervals.pb({l,r,B[x]-start[l],cum[r]-cum[l]});
start[l] = start[x] = B[x];
}
// cout << cum[3]-cum[2] << "\n";
// for (auto a: intervals) cout << "HA " << a.lef << " " << a.rig << " " << a.mul << " " << a.len << "\n";
queries.rsz(M);
ans.rsz(M);
F0R(i,M) {
ints(S,T,U);
queries[i] = {S,T,U};
if (R.query(S,T-1) > U) {
ans[i] = -1;
}
}
sort(all(intervals),[](const interval& a, const interval& b) {
return a.lef < b.lef;
});
deal2();
vi qinds(M); iota(all(qinds),0);
sort(all(qinds),[&](int x, int y) {
return get<0>(queries[x]) < get<0>(queries[y]);
});
int pos = 0;
BB = BIT<pl,MX>();
for (int i: qinds) if (ans[i] != -1) {
int S,T,U; tie(S,T,U) = queries[i];
// each(p,intervals) if (p.lef < S) {
// if (p.rig <= S) {
// } else if (p.rig <= T) {
// ans[i] += p.mul*(cum[p.rig]-cum[S]);
// } else {
// ans[i] += p.mul*(cum[T]-cum[S]);
// }
// }
for(;pos < sz(intervals) && intervals[pos].lef < S;++pos) {
const auto& p = intervals[pos];
BB.upd(intervals[pos].rig,pl{p.mul*cum[p.rig],p.mul});
}
pl qq = BB.query(S,T);
ans[i] += qq.f-qq.s*cum[S];
qq = BB.query(T+1,N+2);
ans[i] += qq.s*(cum[T]-cum[S]);
}
deal1();
each(t,ans) ps(t);
// you should actually read the stuff at the bottom
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKdXNpbmcgbGwgPSBsb25nIGxvbmc7CnVzaW5nIGRiID0gbG9uZyBkb3VibGU7IC8vIG9yIGRvdWJsZSwgaWYgVEwgaXMgdGlnaHQKdXNpbmcgc3RyID0gc3RyaW5nOyAvLyB5YXkgcHl0aG9uIQoKdXNpbmcgcGkgPSBwYWlyPGludCxpbnQ+Owp1c2luZyBwbCA9IHBhaXI8bGwsbGw+Owp1c2luZyBwZCA9IHBhaXI8ZGIsZGI+OwoKdXNpbmcgdmkgPSB2ZWN0b3I8aW50PjsKdXNpbmcgdmIgPSB2ZWN0b3I8Ym9vbD47CnVzaW5nIHZsID0gdmVjdG9yPGxsPjsKdXNpbmcgdmQgPSB2ZWN0b3I8ZGI+OyAKdXNpbmcgdnMgPSB2ZWN0b3I8c3RyPjsKdXNpbmcgdnBpID0gdmVjdG9yPHBpPjsKdXNpbmcgdnBsID0gdmVjdG9yPHBsPjsgCnVzaW5nIHZwZCA9IHZlY3RvcjxwZD47CgojZGVmaW5lIHRjVCB0ZW1wbGF0ZTxjbGFzcyBUCiNkZWZpbmUgdGNUVSB0Y1QsIGNsYXNzIFUKLy8gXiBsb2wgdGhpcyBtYWtlcyBldmVyeXRoaW5nIGxvb2sgd2VpcmQgYnV0IEknbGwgdHJ5IGl0CnRjVD4gdXNpbmcgViA9IHZlY3RvcjxUPjsgCnRjVCwgc2l6ZV90IFNaPiB1c2luZyBBUiA9IGFycmF5PFQsU1o+OyAKdGNUPiB1c2luZyBQUiA9IHBhaXI8VCxUPjsKCi8vIHBhaXJzCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgZiBmaXJzdAojZGVmaW5lIHMgc2Vjb25kCgovLyB2ZWN0b3JzCi8vIG9vcHMgc2l6ZSh4KSwgcmJlZ2luKHgpLCByZW5kKHgpIG5lZWQgQysrMTcKI2RlZmluZSBzeih4KSBpbnQoKHgpLnNpemUoKSkKI2RlZmluZSBiZyh4KSBiZWdpbih4KQojZGVmaW5lIGFsbCh4KSBiZyh4KSwgZW5kKHgpCiNkZWZpbmUgcmFsbCh4KSB4LnJiZWdpbigpLCB4LnJlbmQoKSAKI2RlZmluZSBzb3IoeCkgc29ydChhbGwoeCkpIAojZGVmaW5lIHJzeiByZXNpemUKI2RlZmluZSBpbnMgaW5zZXJ0IAojZGVmaW5lIGZ0IGZyb250KCkKI2RlZmluZSBiayBiYWNrKCkKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBlYiBlbXBsYWNlX2JhY2sgCiNkZWZpbmUgcGYgcHVzaF9mcm9udAojZGVmaW5lIHJ0biByZXR1cm4KCiNkZWZpbmUgbGIgbG93ZXJfYm91bmQKI2RlZmluZSB1YiB1cHBlcl9ib3VuZCAKdGNUPiBpbnQgbHdiKFY8VD4mIGEsIGNvbnN0IFQmIGIpIHsgcmV0dXJuIGludChsYihhbGwoYSksYiktYmcoYSkpOyB9CgovLyBsb29wcwojZGVmaW5lIEZPUihpLGEsYikgZm9yIChpbnQgaSA9IChhKTsgaSA8IChiKTsgKytpKQojZGVmaW5lIEYwUihpLGEpIEZPUihpLDAsYSkKI2RlZmluZSBST0YoaSxhLGIpIGZvciAoaW50IGkgPSAoYiktMTsgaSA+PSAoYSk7IC0taSkKI2RlZmluZSBSMEYoaSxhKSBST0YoaSwwLGEpCiNkZWZpbmUgcmVwKGEpIEYwUihfLGEpCiNkZWZpbmUgZWFjaChhLHgpIGZvciAoYXV0byYgYTogeCkKCmNvbnN0IGludCBNT0QgPSAxZTkrNzsgLy8gOTk4MjQ0MzUzOwpjb25zdCBpbnQgTVggPSAyZTUrNTsKY29uc3QgbGwgSU5GID0gMWUxODsgLy8gbm90IHRvbyBjbG9zZSB0byBMTE9OR19NQVgKY29uc3QgZGIgUEkgPSBhY29zKChkYiktMSk7CmNvbnN0IGludCBkeFs0XSA9IHsxLDAsLTEsMH0sIGR5WzRdID0gezAsMSwwLC0xfTsgLy8gZm9yIGV2ZXJ5IGdyaWQgcHJvYmxlbSEhCm10MTk5Mzcgcm5nKCh1aW50MzJfdCljaHJvbm86OnN0ZWFkeV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCkpOyAKdGVtcGxhdGU8Y2xhc3MgVD4gdXNpbmcgcHFnID0gcHJpb3JpdHlfcXVldWU8VCx2ZWN0b3I8VD4sZ3JlYXRlcjxUPj47CgovLyBiaXR3aXNlIG9wcwovLyBhbHNvIHNlZSBodHRwczovL2cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLnUub3JnL29ubGluZWRvY3MvZ2NjL090aGVyLUJ1aWx0aW5zLmh0bWwKY29uc3RleHByIGludCBwY3QoaW50IHgpIHsgcmV0dXJuIF9fYnVpbHRpbl9wb3Bjb3VudCh4KTsgfSAvLyAjIG9mIGJpdHMgc2V0CmNvbnN0ZXhwciBpbnQgYml0cyhpbnQgeCkgeyAvLyBhc3NlcnQoeCA+PSAwKTsgLy8gbWFrZSBDKysxMSBjb21wYXRpYmxlIHVudGlsIFVTQUNPIHVwZGF0ZXMgLi4uCglyZXR1cm4geCA9PSAwID8gMCA6IDMxLV9fYnVpbHRpbl9jbHooeCk7IH0gLy8gZmxvb3IobG9nMih4KSkgCmNvbnN0ZXhwciBpbnQgcDIoaW50IHgpIHsgcmV0dXJuIDE8PHg7IH0KY29uc3RleHByIGludCBtc2syKGludCB4KSB7IHJldHVybiBwMih4KS0xOyB9CgpsbCBjZGl2KGxsIGEsIGxsIGIpIHsgcmV0dXJuIGEvYisoKGFeYik+MCYmYSViKTsgfSAvLyBkaXZpZGUgYSBieSBiIHJvdW5kZWQgdXAKbGwgZmRpdihsbCBhLCBsbCBiKSB7IHJldHVybiBhL2ItKChhXmIpPDAmJmElYik7IH0gLy8gZGl2aWRlIGEgYnkgYiByb3VuZGVkIGRvd24KCnRjVD4gYm9vbCBja21pbihUJiBhLCBjb25zdCBUJiBiKSB7CglyZXR1cm4gYiA8IGEgPyBhID0gYiwgMSA6IDA7IH0gLy8gc2V0IGEgPSBtaW4oYSxiKQp0Y1Q+IGJvb2wgY2ttYXgoVCYgYSwgY29uc3QgVCYgYikgewoJcmV0dXJuIGEgPCBiID8gYSA9IGIsIDEgOiAwOyB9Cgp0Y1RVPiBUIGZzdFRydWUoVCBsbywgVCBoaSwgVSBmKSB7CgloaSArKzsgYXNzZXJ0KGxvIDw9IGhpKTsgLy8gYXNzdW1pbmcgZiBpcyBpbmNyZWFzaW5nCgl3aGlsZSAobG8gPCBoaSkgeyAvLyBmaW5kIGZpcnN0IGluZGV4IHN1Y2ggdGhhdCBmIGlzIHRydWUgCgkJVCBtaWQgPSBsbysoaGktbG8pLzI7CgkJZihtaWQpID8gaGkgPSBtaWQgOiBsbyA9IG1pZCsxOyAKCX0gCglyZXR1cm4gbG87Cn0KdGNUVT4gVCBsc3RUcnVlKFQgbG8sIFQgaGksIFUgZikgewoJbG8gLS07IGFzc2VydChsbyA8PSBoaSk7IC8vIGFzc3VtaW5nIGYgaXMgZGVjcmVhc2luZwoJd2hpbGUgKGxvIDwgaGkpIHsgLy8gZmluZCBmaXJzdCBpbmRleCBzdWNoIHRoYXQgZiBpcyB0cnVlIAoJCVQgbWlkID0gbG8rKGhpLWxvKzEpLzI7CgkJZihtaWQpID8gbG8gPSBtaWQgOiBoaSA9IG1pZC0xOwoJfSAKCXJldHVybiBsbzsKfQp0Y1Q+IHZvaWQgcmVtRHVwKHZlY3RvcjxUPiYgdikgeyAvLyBzb3J0IGFuZCByZW1vdmUgZHVwbGljYXRlcwoJc29ydChhbGwodikpOyB2LmVyYXNlKHVuaXF1ZShhbGwodikpLGVuZCh2KSk7IH0KdGNUVT4gdm9pZCBlcmFzZShUJiB0LCBjb25zdCBVJiB1KSB7IC8vIGRvbid0IGVyYXNlCglhdXRvIGl0ID0gdC5maW5kKHUpOyBhc3NlcnQoaXQgIT0gZW5kKHQpKTsKCXQuZXJhc2UoaXQpOyB9IC8vIGVsZW1lbnQgdGhhdCBkb2Vzbid0IGV4aXN0IGZyb20gKG11bHRpKXNldAoKI2RlZmluZSB0Y1RVVSB0Y1QsIGNsYXNzIC4uLlUKCmlubGluZSBuYW1lc3BhY2UgSGVscGVycyB7CgkvLy8vLy8vLy8vLy8gaXNfaXRlcmFibGUKCS8vIGh0dHBzOi8vc3RhY2tvdmVyZmxvdy5jb20vcXVlc3Rpb25zLzEzODMwMTU4L2NoZWNrLWlmLWEtdmFyaWFibGUtdHlwZS1pcy1pdGVyYWJsZQoJLy8gdGhpcyBnZXRzIHVzZWQgb25seSB3aGVuIHdlIGNhbiBjYWxsIGJlZ2luKCkgYW5kIGVuZCgpIG9uIHRoYXQgdHlwZQoJdGNULCBjbGFzcyA9IHZvaWQ+IHN0cnVjdCBpc19pdGVyYWJsZSA6IGZhbHNlX3R5cGUge307Cgl0Y1Q+IHN0cnVjdCBpc19pdGVyYWJsZTxULCB2b2lkX3Q8ZGVjbHR5cGUoYmVnaW4oZGVjbHZhbDxUPigpKSksCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGVjbHR5cGUoZW5kKGRlY2x2YWw8VD4oKSkpCgkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICA+CgkgICAgICAgICAgICAgICAgICAgICAgID4gOiB0cnVlX3R5cGUge307Cgl0Y1Q+IGNvbnN0ZXhwciBib29sIGlzX2l0ZXJhYmxlX3YgPSBpc19pdGVyYWJsZTxUPjo6dmFsdWU7CgoJLy8vLy8vLy8vLy8vIGlzX3JlYWRhYmxlCgl0Y1QsIGNsYXNzID0gdm9pZD4gc3RydWN0IGlzX3JlYWRhYmxlIDogZmFsc2VfdHlwZSB7fTsKCXRjVD4gc3RydWN0IGlzX3JlYWRhYmxlPFQsCgkgICAgICAgIHR5cGVuYW1lIHN0ZDo6ZW5hYmxlX2lmX3Q8CgkgICAgICAgICAgICBpc19zYW1lX3Y8ZGVjbHR5cGUoY2luID4+IGRlY2x2YWw8VCY+KCkpLCBpc3RyZWFtJj4KCSAgICAgICAgPgoJICAgID4gOiB0cnVlX3R5cGUge307Cgl0Y1Q+IGNvbnN0ZXhwciBib29sIGlzX3JlYWRhYmxlX3YgPSBpc19yZWFkYWJsZTxUPjo6dmFsdWU7CgoJLy8vLy8vLy8vLy8vIGlzX3ByaW50YWJsZQoJLy8gLy8gaHR0cHM6Ly9uLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLmVzL3Bvc3RzLzIwMjAtMDItMjktaXMtcHJpbnRhYmxlLwoJdGNULCBjbGFzcyA9IHZvaWQ+IHN0cnVjdCBpc19wcmludGFibGUgOiBmYWxzZV90eXBlIHt9OwoJdGNUPiBzdHJ1Y3QgaXNfcHJpbnRhYmxlPFQsCgkgICAgICAgIHR5cGVuYW1lIHN0ZDo6ZW5hYmxlX2lmX3Q8CgkgICAgICAgICAgICBpc19zYW1lX3Y8ZGVjbHR5cGUoY291dCA8PCBkZWNsdmFsPFQ+KCkpLCBvc3RyZWFtJj4KCSAgICAgICAgPgoJICAgID4gOiB0cnVlX3R5cGUge307Cgl0Y1Q+IGNvbnN0ZXhwciBib29sIGlzX3ByaW50YWJsZV92ID0gaXNfcHJpbnRhYmxlPFQ+Ojp2YWx1ZTsKfQoKaW5saW5lIG5hbWVzcGFjZSBJbnB1dCB7Cgl0Y1Q+IGNvbnN0ZXhwciBib29sIG5lZWRzX2lucHV0X3YgPSAhaXNfcmVhZGFibGVfdjxUPiAmJiBpc19pdGVyYWJsZV92PFQ+OwoJdGNUVVU+IHZvaWQgcmUoVCYgdCwgVSYuLi4gdSk7Cgl0Y1RVPiB2b2lkIHJlKHBhaXI8VCxVPiYgcCk7IC8vIHBhaXJzCgoJLy8gcmU6IHJlYWQKCXRjVD4gdHlwZW5hbWUgZW5hYmxlX2lmPGlzX3JlYWRhYmxlX3Y8VD4sdm9pZD46OnR5cGUgcmUoVCYgeCkgeyBjaW4gPj4geDsgfSAvLyBkZWZhdWx0Cgl0Y1Q+IHZvaWQgcmUoY29tcGxleDxUPiYgYykgeyBUIGEsYjsgcmUoYSxiKTsgYyA9IHthLGJ9OyB9IC8vIGNvbXBsZXgKCXRjVD4gdHlwZW5hbWUgZW5hYmxlX2lmPG5lZWRzX2lucHV0X3Y8VD4sdm9pZD46OnR5cGUgcmUoVCYgaSk7IC8vIGV4LiB2ZWN0b3JzLCBhcnJheXMKCXRjVFU+IHZvaWQgcmUocGFpcjxULFU+JiBwKSB7IHJlKHAuZixwLnMpOyB9Cgl0Y1Q+IHR5cGVuYW1lIGVuYWJsZV9pZjxuZWVkc19pbnB1dF92PFQ+LHZvaWQ+Ojp0eXBlIHJlKFQmIGkpIHsKCQllYWNoKHgsaSkgcmUoeCk7IH0KCXRjVFVVPiB2b2lkIHJlKFQmIHQsIFUmLi4uIHUpIHsgcmUodCk7IHJlKHUuLi4pOyB9IC8vIHJlYWQgbXVsdGlwbGUKCgkvLyBydjogcmVzaXplIGFuZCByZWFkIHZlY3RvcnMKCXZvaWQgcnYoc2l6ZV90KSB7fQoJdGNUVVU+IHZvaWQgcnYoc2l6ZV90IE4sIFY8VD4mIHQsIFUmLi4uIHUpOwoJdGVtcGxhdGU8Y2xhc3MuLi5VPiB2b2lkIHJ2KHNpemVfdCwgc2l6ZV90IE4yLCBVJi4uLiB1KTsKCXRjVFVVPiB2b2lkIHJ2KHNpemVfdCBOLCBWPFQ+JiB0LCBVJi4uLiB1KSB7CgkJdC5yc3ooTik7IHJlKHQpOwoJCXJ2KE4sdS4uLik7IH0KCXRlbXBsYXRlPGNsYXNzLi4uVT4gdm9pZCBydihzaXplX3QsIHNpemVfdCBOMiwgVSYuLi4gdSkgewoJCXJ2KE4yLHUuLi4pOyB9CgoJLy8gZHVtYiBzaG9ydGN1dHMgdG8gcmVhZCBpbiBpbnRzCgl2b2lkIGRlY3JlbWVudCgpIHt9IC8vIHN1YnRyYWN0IG9uZSBmcm9tIGVhY2gKCXRjVFVVPiB2b2lkIGRlY3JlbWVudChUJiB0LCBVJi4uLiB1KSB7IC0tdDsgZGVjcmVtZW50KHUuLi4pOyB9CgkjZGVmaW5lIGludHMoLi4uKSBpbnQgX19WQV9BUkdTX187IHJlKF9fVkFfQVJHU19fKTsKCSNkZWZpbmUgaW50MSguLi4pIGludHMoX19WQV9BUkdTX18pOyBkZWNyZW1lbnQoX19WQV9BUkdTX18pOwp9CgppbmxpbmUgbmFtZXNwYWNlIFRvU3RyaW5nIHsKCXRjVD4gY29uc3RleHByIGJvb2wgbmVlZHNfb3V0cHV0X3YgPSAhaXNfcHJpbnRhYmxlX3Y8VD4gJiYgaXNfaXRlcmFibGVfdjxUPjsKCgkvLyB0czogc3RyaW5nIHJlcHJlc2VudGF0aW9uIHRvIHByaW50Cgl0Y1Q+IHR5cGVuYW1lIGVuYWJsZV9pZjxpc19wcmludGFibGVfdjxUPixzdHI+Ojp0eXBlIHRzKFQgdikgewoJCXN0cmluZ3N0cmVhbSBzczsgc3MgPDwgZml4ZWQgPDwgc2V0cHJlY2lzaW9uKDE1KSA8PCB2OwoJCXJldHVybiBzcy5zdHIoKTsgfSAvLyBkZWZhdWx0Cgl0Y1Q+IHN0ciBiaXRfdmVjKFQgdCkgeyAvLyBiaXQgdmVjdG9yIHRvIHN0cmluZwoJCXN0ciByZXMgPSAieyI7IEYwUihpLHN6KHQpKSByZXMgKz0gdHModFtpXSk7CgkJcmVzICs9ICJ9IjsgcmV0dXJuIHJlczsgfQoJc3RyIHRzKFY8Ym9vbD4gdikgeyByZXR1cm4gYml0X3ZlYyh2KTsgfQoJdGVtcGxhdGU8c2l6ZV90IFNaPiBzdHIgdHMoYml0c2V0PFNaPiBiKSB7IHJldHVybiBiaXRfdmVjKGIpOyB9IC8vIGJpdCB2ZWN0b3IKCXRjVFU+IHN0ciB0cyhwYWlyPFQsVT4gcCk7IC8vIHBhaXJzCgl0Y1Q+IHR5cGVuYW1lIGVuYWJsZV9pZjxuZWVkc19vdXRwdXRfdjxUPixzdHI+Ojp0eXBlIHRzKFQgdik7IC8vIHZlY3RvcnMsIGFycmF5cwoJdGNUVT4gc3RyIHRzKHBhaXI8VCxVPiBwKSB7IHJldHVybiAiKCIrdHMocC5mKSsiLCAiK3RzKHAucykrIikiOyB9Cgl0Y1Q+IHR5cGVuYW1lIGVuYWJsZV9pZjxpc19pdGVyYWJsZV92PFQ+LHN0cj46OnR5cGUgdHNfc2VwKFQgdiwgc3RyIHNlcCkgewoJCS8vIGNvbnZlcnQgY29udGFpbmVyIHRvIHN0cmluZyB3LyBzZXBhcmF0b3Igc2VwCgkJYm9vbCBmc3QgPSAxOyBzdHIgcmVzID0gIiI7CgkJZm9yIChjb25zdCBhdXRvJiB4OiB2KSB7CgkJCWlmICghZnN0KSByZXMgKz0gc2VwOwoJCQlmc3QgPSAwOyByZXMgKz0gdHMoeCk7CgkJfQoJCXJldHVybiByZXM7Cgl9Cgl0Y1Q+IHR5cGVuYW1lIGVuYWJsZV9pZjxuZWVkc19vdXRwdXRfdjxUPixzdHI+Ojp0eXBlIHRzKFQgdikgewoJCXJldHVybiAieyIrdHNfc2VwKHYsIiwgIikrIn0iOyB9CgoJLy8gZm9yIG5lc3RlZCBEUwoJdGVtcGxhdGU8aW50LCBjbGFzcyBUPiB0eXBlbmFtZSBlbmFibGVfaWY8IW5lZWRzX291dHB1dF92PFQ+LHZzPjo6dHlwZSAKCSAgdHNfbGV2KGNvbnN0IFQmIHYpIHsgcmV0dXJuIHt0cyh2KX07IH0KCXRlbXBsYXRlPGludCBsZXYsIGNsYXNzIFQ+IHR5cGVuYW1lIGVuYWJsZV9pZjxuZWVkc19vdXRwdXRfdjxUPix2cz46OnR5cGUgCgkgIHRzX2xldihjb25zdCBUJiB2KSB7CgkJaWYgKGxldiA9PSAwIHx8ICFzeih2KSkgcmV0dXJuIHt0cyh2KX07CgkJdnMgcmVzOwoJCWZvciAoY29uc3QgYXV0byYgdDogdikgewoJCQlpZiAoc3oocmVzKSkgcmVzLmJrICs9ICIsIjsKCQkJdnMgdG1wID0gdHNfbGV2PGxldi0xPih0KTsKCQkJcmVzLmlucyhlbmQocmVzKSxhbGwodG1wKSk7CgkJfQoJCUYwUihpLHN6KHJlcykpIHsKCQkJc3RyIGJlZiA9ICIgIjsgaWYgKGkgPT0gMCkgYmVmID0gInsiOwoJCQlyZXNbaV0gPSBiZWYrcmVzW2ldOwoJCX0KCQlyZXMuYmsgKz0gIn0iOwoJCXJldHVybiByZXM7Cgl9Cn0KCmlubGluZSBuYW1lc3BhY2UgT3V0cHV0IHsKCXRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgcHJfc2VwKG9zdHJlYW0mIG9zLCBzdHIsIGNvbnN0IFQmIHQpIHsgb3MgPDwgdHModCk7IH0KCXRlbXBsYXRlPGNsYXNzIFQsIGNsYXNzLi4uIFU+IHZvaWQgcHJfc2VwKG9zdHJlYW0mIG9zLCBzdHIgc2VwLCBjb25zdCBUJiB0LCBjb25zdCBVJi4uLiB1KSB7CgkJcHJfc2VwKG9zLHNlcCx0KTsgb3MgPDwgc2VwOyBwcl9zZXAob3Msc2VwLHUuLi4pOyB9CgkvLyBwcmludCB3LyBubyBzcGFjZXMKCXRlbXBsYXRlPGNsYXNzIC4uLlQ+IHZvaWQgcHIoY29uc3QgVCYuLi4gdCkgeyBwcl9zZXAoY291dCwiIix0Li4uKTsgfSAKCS8vIHByaW50IHcvIHNwYWNlcywgZW5kIHdpdGggbmV3bGluZQoJdm9pZCBwcygpIHsgY291dCA8PCAiXG4iOyB9Cgl0ZW1wbGF0ZTxjbGFzcyAuLi5UPiB2b2lkIHBzKGNvbnN0IFQmLi4uIHQpIHsgcHJfc2VwKGNvdXQsIiAiLHQuLi4pOyBwcygpOyB9IAoJLy8gZGVidWcgdG8gY2VycgoJdGVtcGxhdGU8Y2xhc3MgLi4uVD4gdm9pZCBkYmdfb3V0KGNvbnN0IFQmLi4uIHQpIHsKCQlwcl9zZXAoY2VyciwiIHwgIix0Li4uKTsgY2VyciA8PCBlbmRsOyB9Cgl2b2lkIGxvY19pbmZvKGludCBsaW5lLCBzdHIgbmFtZXMpIHsKCQljZXJyIDw8ICJMaW5lKCIgPDwgbGluZSA8PCAiKSAtPiBbIiA8PCBuYW1lcyA8PCAiXTogIjsgfQoJdGVtcGxhdGU8aW50IGxldiwgY2xhc3MgVD4gdm9pZCBkYmdsX291dChjb25zdCBUJiB0KSB7CgkJY2VyciA8PCAiXG5cbiIgPDwgdHNfc2VwKHRzX2xldjxsZXY+KHQpLCJcbiIpIDw8ICJcbiIgPDwgZW5kbDsgfQoJI2lmZGVmIExPQ0FMCgkJI2RlZmluZSBkYmcoLi4uKSBsb2NfaW5mbyhfX0xJTkVfXywjX19WQV9BUkdTX18pLCBkYmdfb3V0KF9fVkFfQVJHU19fKQoJCSNkZWZpbmUgZGJnbChsZXYseCkgbG9jX2luZm8oX19MSU5FX18sI3gpLCBkYmdsX291dDxsZXY+KHgpCgkjZWxzZSAvLyBkb24ndCBhY3R1YWxseSBzdWJtaXQgd2l0aCB0aGlzCgkJI2RlZmluZSBkYmcoLi4uKSAwCgkJI2RlZmluZSBkYmdsKGxldix4KSAwCgkjZW5kaWYKfQoKaW5saW5lIG5hbWVzcGFjZSBGaWxlSU8gewoJdm9pZCBzZXRJbihzdHIgcykgIHsgZnJlb3BlbihzLmNfc3RyKCksInIiLHN0ZGluKTsgfQoJdm9pZCBzZXRPdXQoc3RyIHMpIHsgZnJlb3BlbihzLmNfc3RyKCksInciLHN0ZG91dCk7IH0KCXZvaWQgc2V0SU8oc3RyIHMgPSAiIikgewoJCWNpbi50aWUoMCktPnN5bmNfd2l0aF9zdGRpbygwKTsgLy8gdW5zeW5jIEMgLyBDKysgSS9PIHN0cmVhbXMKCQkvLyBjaW4uZXhjZXB0aW9ucyhjaW4uZmFpbGJpdCk7CgkJLy8gdGhyb3dzIGV4Y2VwdGlvbiB3aGVuIGRvIHNtdGggaWxsZWdhbAoJCS8vIGV4LiB0cnkgdG8gcmVhZCBsZXR0ZXIgaW50byBpbnQKCQlpZiAoc3oocykpIHNldEluKHMrIi5pbiIpLCBzZXRPdXQocysiLm91dCIpOyAvLyBmb3Igb2xkIFVTQUNPCgl9Cn0KCnBsJiBvcGVyYXRvcis9KHBsJiBhLCBwbCBiKSB7IHJldHVybiBhID0ge2EuZitiLmYsYS5zK2Iuc307IH0KcGwgb3BlcmF0b3ItKHBsIGEsIHBsIGIpIHsgcmV0dXJuIHthLmYtYi5mLGEucy1iLnN9OyB9CgovKioKICogRGVzY3JpcHRpb246IHJhbmdlIHN1bSBxdWVyaWVzIGFuZCBwb2ludCB1cGRhdGVzIGZvciAkRCQgZGltZW5zaW9ucwogKiBTb3VyY2U6IGh0dHBzOi8vYy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ucy5jb20vYmxvZy9lbnRyeS82NDkxNAogKiBWZXJpZmljYXRpb246IFNQT0ogbWF0c3VtCiAqIFVzYWdlOiBcdGV4dHR0e0JJVDxpbnQsMTAsMTA+fSBnaXZlcyAyRCBCSVQKICogVGltZTogTygoXGxvZyBOKV5EKQogKi8KCnRlbXBsYXRlIDxjbGFzcyBULCBpbnQgLi4uTnM+IHN0cnVjdCBCSVQgewoJVCB2YWx7fTsgdm9pZCB1cGQoVCB2KSB7IHZhbCArPSB2OyB9CglUIHF1ZXJ5KCkgeyByZXR1cm4gdmFsOyB9Cn07CnRlbXBsYXRlIDxjbGFzcyBULCBpbnQgTiwgaW50Li4uIE5zPiBzdHJ1Y3QgQklUPFQsIE4sIE5zLi4uPiB7CglCSVQ8VCxOcy4uLj4gYml0W04rMV07Cgl0ZW1wbGF0ZTx0eXBlbmFtZS4uLiBBcmdzPiB2b2lkIHVwZChpbnQgcG9zLCBBcmdzLi4uIGFyZ3MpIHsgYXNzZXJ0KHBvcyA+IDApOwoJCWZvciAoOyBwb3M8PU47IHBvcys9cG9zJi1wb3MpIGJpdFtwb3NdLnVwZChhcmdzLi4uKTsgfQoJdGVtcGxhdGU8dHlwZW5hbWUuLi4gQXJncz4gVCBzdW0oaW50IHIsIEFyZ3MuLi4gYXJncykgewoJCVQgcmVze307IGZvciAoO3I7ci09ciYtcikgcmVzICs9IGJpdFtyXS5xdWVyeShhcmdzLi4uKTsgCgkJcmV0dXJuIHJlczsgfQoJdGVtcGxhdGU8dHlwZW5hbWUuLi4gQXJncz4gVCBxdWVyeShpbnQgbCwgaW50IHIsIEFyZ3MuLi4gCgkJYXJncykgeyByZXR1cm4gc3VtKHIsYXJncy4uLiktc3VtKGwtMSxhcmdzLi4uKTsgfQp9OyAKCkJJVDxwbCxNWD4gQkI7CgovKioKICogRGVzY3JpcHRpb246IDFEIHJhbmdlIG1pbmltdW0gcXVlcnkuIENhbiBhbHNvIGRvIHF1ZXJpZXMgCiAJKiBmb3IgYW55IGFzc29jaWF0aXZlIG9wZXJhdGlvbiBpbiAkTygxKSQgd2l0aCBEXCZDCiAqIFNvdXJjZTogS0FDVEwKICogVmVyaWZpY2F0aW9uOiAKCSogaHR0cHM6Ly9jLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5zLmZpL3Byb2JsZW1zZXQvc3RhdHMvMTY0Ny8KCSogaHR0cDovL3cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmcuY29tL3Byb2JsZW0vaW9pMTIyMwoJKiBodHRwczovL3AuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLm4uY29tL0NocG5pVlpMCiAqIE1lbW9yeTogTyhOXGxvZyBOKQogKiBUaW1lOiBPKDEpCiAqLwoKdGVtcGxhdGU8Y2xhc3MgVD4gc3RydWN0IFJNUSB7IC8vIGZsb29yKGxvZ18yKHgpKQoJaW50IGxldmVsKGludCB4KSB7IHJldHVybiAzMS1fX2J1aWx0aW5fY2x6KHgpOyB9IAoJdmVjdG9yPFQ+IHY7IHZlY3Rvcjx2aT4gam1wOwoJaW50IGNvbWIoaW50IGEsIGludCBiKSB7IC8vIGluZGV4IG9mIG1pbgoJCXJldHVybiB2W2FdPT12W2JdP21pbihhLGIpOih2W2FdPnZbYl0/YTpiKTsgfSAKCXZvaWQgaW5pdChjb25zdCB2ZWN0b3I8VD4mIF92KSB7CgkJdiA9IF92OyBqbXAgPSB7dmkoc3oodikpfTsgaW90YShhbGwoam1wWzBdKSwwKTsKCQlmb3IgKGludCBqID0gMTsgMTw8aiA8PSBzeih2KTsgKytqKSB7CgkJCWptcC5wYih2aShzeih2KS0oMTw8aikrMSkpOwoJCQlGMFIoaSxzeihqbXBbal0pKSBqbXBbal1baV0gPSBjb21iKGptcFtqLTFdW2ldLAoJCQkJCQkJCQlqbXBbai0xXVtpKygxPDwoai0xKSldKTsKCQl9Cgl9CglpbnQgaW5kZXgoaW50IGwsIGludCByKSB7IC8vIGdldCBpbmRleCBvZiBtaW4gZWxlbWVudAoJCWFzc2VydChsIDw9IHIpOyBpbnQgZCA9IGxldmVsKHItbCsxKTsKCQlyZXR1cm4gY29tYihqbXBbZF1bbF0sam1wW2RdW3ItKDE8PGQpKzFdKTsgfQoJVCBxdWVyeShpbnQgbCwgaW50IHIpIHsgcmV0dXJuIHZbaW5kZXgobCxyKV07IH0KfTsKClJNUTxpbnQ+IFI7CnN0cnVjdCBpbnRlcnZhbCB7CglpbnQgbGVmLCByaWcsIG11bDsKCWxsIGxlbiwgY29udHJpYjsKfTsKClY8aW50ZXJ2YWw+IGludGVydmFsczsKCmludCBOLE07CmludCBzdGFydFtNWF07CnZpIEEsQjsKVjx0dXBsZTxpbnQsaW50LGludD4+IHF1ZXJpZXM7CnZsIGFucywgY3VtezAsMH07Cgp2cGkgdjsKCmludCBnZXRfeF8wKHBpIHApIHsKCWlmIChwLnMgPT0gMSkgcmV0dXJuIGludGVydmFsc1twLmZdLmxlZjsKCXJldHVybiBnZXQ8MD4ocXVlcmllc1twLmZdKTsKfQoKcGkgZ2V0X3gocGkgcCkgeyByZXR1cm4gbXAoZ2V0X3hfMChwKSxwLnMpOyB9CgoKaW50IGdldF95XzAocGkgcCkgewoJaWYgKHAucyA9PSAxKSByZXR1cm4gaW50ZXJ2YWxzW3AuZl0ucmlnOwoJcmV0dXJuIGdldDwxPihxdWVyaWVzW3AuZl0pOwp9CgpwaSBnZXRfeShwaSBwKSB7IHJldHVybiBtcChnZXRfeV8wKHApLHAucyk7IH0KCgpsbCBnZXRfel8wKHBpIHApIHsKCWlmIChwLnMgPT0gMSkgcmV0dXJuIGludGVydmFsc1twLmZdLmxlbjsKCXJldHVybiBnZXQ8Mj4ocXVlcmllc1twLmZdKTsKfQoKcGFpcjxsbCxpbnQ+IGdldF96KHBpIHApIHsgcmV0dXJuIG1wKGdldF96XzAocCkscC5zKTsgfQoKdnBsIGFhOwoKdm9pZCBkaXZpKGludCBsLCBpbnQgcikgewoJaWYgKGwgPT0gcikgcmV0dXJuOwoJaW50IG0gPSAobCtyKS8yOwoJZGl2aShsLG0pOyBkaXZpKG0rMSxyKTsKCXZwaSB0bXA7CglGT1IoaSxsLG0rMSkgewoJCXBpIGEgPSB2W2ldOwoJCWlmIChhLnMgPT0gMCkgdG1wLnBiKGEpOwoJfQoJRk9SKGosbSsxLHIrMSkgewoJCXBpIGIgPSB2W2pdOwoJCWlmIChiLnMgPT0gMSkgdG1wLnBiKGIpOwoJfQoJc29ydChhbGwodG1wKSxbXShwaSBhLCBwaSBiKSB7CgkJcmV0dXJuIGdldF95KGEpIDwgZ2V0X3koYik7Cgl9KTsKCVIwRihpLHN6KHRtcCkpIHsKCQlwaSBhID0gdG1wW2ldOwoJCWlmIChhLnMgPT0gMSkgewoJCQlpbnQgeCA9IGdldF94XzAoYSk7CgkJCWlmICh4ID4gMCkgQkIudXBkKHgscGx7aW50ZXJ2YWxzW2EuZl0uY29udHJpYixpbnRlcnZhbHNbYS5mXS5tdWx9KTsKCQl9IGVsc2UgewoJCQlwbCBwID0gQkIucXVlcnkoZ2V0X3hfMChhKSxOKzIpOwoJCQlhYVthLmZdLmYgKz0gcC5mOwoJCQlhYVthLmZdLnMgKz0gcC5zOwoJCX0KCX0KCVIwRihpLHN6KHRtcCkpIHsKCQlwaSBhID0gdG1wW2ldOwoJCWlmIChhLnMgPT0gMSkgewoJCQlpbnQgeCA9IGdldF94XzAoYSk7CgkJCWlmICh4ID4gMCkgQkIudXBkKHgscGx7LWludGVydmFsc1thLmZdLmNvbnRyaWIsLWludGVydmFsc1thLmZdLm11bH0pOwoJCX0KCX0KIC8vIAlGMFIoaSxzeih0bXApKSBGT1IoaixpKzEsc3oodG1wKSkgewoJLy8gCXBpIGEgPSB0bXBbaV0sIGIgPSB0bXBbal07CgkvLyAJaWYgKGEucyA9PSAwICYmIGIucyA9PSAxICYmIGdldF94KGEpIDwgZ2V0X3goYikpIHsKCS8vIAkJYWFbYS5mXS5mICs9IGludGVydmFsc1tiLmZdLmNvbnRyaWI7CgkvLyAJCWFhW2EuZl0ucyArPSBpbnRlcnZhbHNbYi5mXS5tdWw7CgkvLyAJfQoJLy8gfQoJLy8gZm9yIChwaSBhOiBhX3RtcCkgZm9yIChwaSBiOiBiX3RtcCkgewoJLy8gCWlmIChnZXRfeChhKSA8IGdldF94KGIpKQoJLy8gCWlmIChnZXRfeShhKSA8IGdldF95KGIpKSB7CgkvLyAJCWFhW2EuZl0uZiArPSBpbnRlcnZhbHNbYi5mXS5jb250cmliOwoJLy8gCQlhYVthLmZdLnMgKz0gaW50ZXJ2YWxzW2IuZl0ubXVsOwoJLy8gCX0KCS8vIH0KfQoKdm9pZCBkZWFsMSgpIHsKCUJCID0gQklUPHBsLE1YPigpOwoJYWEucnN6KE0pOwoJZWFjaChwLGludGVydmFscykgewoJCXAuY29udHJpYiA9IHAubXVsKnAubGVuOwoJCXAucmlnICo9IC0xOwoJCS0tIHAubGVuOwoJfQoJZWFjaCh0LHF1ZXJpZXMpIGdldDwxPih0KSAqPSAtMTsKCUYwUihpLE0pIGlmIChhbnNbaV0gIT0gLTEpIHsKCQlpbnQgUyxULFU7IHRpZShTLFQsVSkgPSBxdWVyaWVzW2ldOwoJCS8vIGVhY2gocCxpbnRlcnZhbHMpIGlmIChTIDw9IHAubGVmICYmIFQgPD0gcC5yaWcgJiYgVSA8PSBwLmxlbikgewoJCS8vIAlhYVtpXS5mICs9IHAuY29udHJpYjsKCQkvLyAJYWFbaV0ucyArPSBwLm11bDsKCQkvLyB9Cgl9Cgl2cGkgaWkscXE7CglGMFIoaSxzeihpbnRlcnZhbHMpKSB7CgkJdi5wYih7aSwxfSk7CgkJaWkucGIoe2ksMX0pOwoJfQoJRjBSKGksc3oocXVlcmllcykpIHsKCQl2LnBiKHtpLDB9KTsKCQlxcS5wYih7aSwwfSk7Cgl9CgkvLyBmb3IgKHBpIGE6IHFxKSBmb3IgKHBpIGI6IGlpKQoJLy8gCWlmIChnZXRfeChhKSA8IGdldF94KGIpKQoJLy8gCWlmIChnZXRfeShhKSA8IGdldF95KGIpKQoJLy8gCWlmIChnZXRfeihhKSA8IGdldF96KGIpKSB7CgkvLyAJCWFhW2EuZl0uZiArPSBpbnRlcnZhbHNbYi5mXS5jb250cmliOwoJLy8gCQlhYVthLmZdLnMgKz0gaW50ZXJ2YWxzW2IuZl0ubXVsOwoJLy8gCX0KCS8vIEYwUihpLHN6KHF1ZXJpZXMpKSBGMFIoaixzeihpbnRlcnZhbHMpKQoJc29ydChhbGwodiksWyZdKHBpIGEsIHBpIGIpIHsKCQlyZXR1cm4gZ2V0X3ooYSkgPCBnZXRfeihiKTsKCX0pOwoJZGl2aSgwLHN6KHYpLTEpOwoKCglGMFIoaSxNKSBpZiAoYW5zW2ldICE9IC0xKSB7CgkJaW50IFMsVCxVOyB0aWUoUyxULFUpID0gcXVlcmllc1tpXTsKCQlhbnNbaV0gKz0gYWFbaV0uZi1hYVtpXS5zKlU7Cgl9Cn0KCnZvaWQgZGVhbDIoKSB7CglWPEFSPGxsLDU+PiBjb250cmliOwoJLy8gZGJnKCJTVEFSVCIsYW5zWzBdKTsKCUYwUihpLE0pIGlmIChhbnNbaV0gIT0gLTEpIHsKCQlpbnQgUyxULFU7IHRpZShTLFQsVSkgPSBxdWVyaWVzW2ldOwoJCWludCBtYXhMZWYgPSBsc3RUcnVlKDAsTisyLFsmXShpbnQgeCkgewoJCQlyZXR1cm4gY3VtW3hdIDw9IGN1bVtUXS1VOwoJCX0pOwoJCWludCBsbyA9IFMsIGhpID0gbWluKFQtMSxtYXhMZWYpOwoJCWlmIChsbyA8PSBoaSkgewoJCQljb250cmliLnBiKHtoaSwgIFQsY3VtW1RdLVUsaSwxfSk7CgkJCWNvbnRyaWIucGIoe2xvLTEsVCxjdW1bVF0tVSxpLC0xfSk7CgkJCS8vIGVhY2gocCxpbnRlcnZhbHMpIGlmIChwLmxlZiA8PSBoaSkgewoJCQkvLyAJaWYgKHAucmlnID4gVCkgYW5zW2ldICs9IHAubXVsKigtY3VtW3AubGVmXStjdW1bVF0tVSk7CgkJCS8vIH0KCQkJLy8gZWFjaChwLGludGVydmFscykgaWYgKHAubGVmIDw9IGxvLTEpIHsKCQkJLy8gCWlmIChwLnJpZyA+IFQpIGFuc1tpXSAtPSBwLm11bCooLWN1bVtwLmxlZl0rY3VtW1RdLVUpOwoJCQkvLyB9CgkJfQoJfQoJc29yKGNvbnRyaWIpOwoJQkIgPSBCSVQ8cGwsTVg+KCk7CglpbnQgaW5kID0gMDsKCWVhY2godCxjb250cmliKSB7CgkJZm9yKDtpbmQgPCBzeihpbnRlcnZhbHMpICYmIGludGVydmFsc1tpbmRdLmxlZiA8PSB0WzBdOysraW5kKSB7CgkJCWNvbnN0IGF1dG8mIHAgPSBpbnRlcnZhbHNbaW5kXTsKCQkJQkIudXBkKHAucmlnLHBsey1wLm11bCpjdW1bcC5sZWZdLHAubXVsfSk7CgkJfQoJCXBsIHAgPSBCQi5xdWVyeSgoaW50KXRbMV0rMSxOKzIpOwoJCS8vIGRiZygiQUgiLHAuZitwLnMqdFsyXSx0WzNdLHRbNF0pOwoJCWFzc2VydCh0WzNdIDwgc3ooYW5zKSk7CgkJYW5zW3RbM11dICs9IHRbNF0qKHAuZitwLnMqdFsyXSk7Cgl9CgkvLyBkYmcoIkVORCIsYW5zWzBdKTsKfQoKaW50IG1haW4oKSB7CglzZXRJTygpOyByZShOLE0pOwoJQS5yc3ooTisxKSwgQi5yc3ooTisxKTsKCUZPUihpLDEsTisxKSByZShBW2ldKTsKCUZPUihpLDEsTisxKSByZShCW2ldKTsKCVIuaW5pdChBKTsKCUZPUihpLDEsTisxKSBjdW0ucGIoY3VtLmJrK0FbaV0pOwoJY3VtLnBiKGN1bS5iayk7Cglhc3NlcnQoc3ooY3VtKS0xID09IE4rMik7CglzZXQ8aW50PiBjdXJ7MCxOKzJ9OwoJdmkgaW5kczsgRk9SKGksMSxOKzIpIGluZHMucGIoaSk7CgkvLyBGMFIoaSxOKzIpIHsKCS8vIAlyaWdbaV0gPSBpKzE7CgkvLyAJbGVmW2krMV0gPSBpOwoJLy8gfQoJc29ydChhbGwoaW5kcyksWyZdKGludCB4LCBpbnQgeSkgewoJCXJldHVybiBCW3hdIDwgQlt5XTsgfSk7Cglmb3IgKGludCB4OiBpbmRzKSB7CgkJY3VyLmlucyh4KTsKCQlhdXRvIGl0ID0gY3VyLmZpbmQoeCk7CgkJaW50IGwgPSAqcHJldihpdCksIHIgPSAqbmV4dChpdCk7CgkJaW50ZXJ2YWxzLnBiKHtsLHIsQlt4XS1zdGFydFtsXSxjdW1bcl0tY3VtW2xdfSk7CgkJc3RhcnRbbF0gPSBzdGFydFt4XSA9IEJbeF07Cgl9CgkvLyBjb3V0IDw8IGN1bVszXS1jdW1bMl0gPDwgIlxuIjsKCS8vIGZvciAoYXV0byBhOiBpbnRlcnZhbHMpIGNvdXQgPDwgIkhBICIgPDwgYS5sZWYgPDwgIiAiIDw8IGEucmlnIDw8ICIgIiA8PCBhLm11bCA8PCAiICIgPDwgYS5sZW4gPDwgIlxuIjsKCXF1ZXJpZXMucnN6KE0pOyAKCWFucy5yc3ooTSk7CglGMFIoaSxNKSB7CgkJaW50cyhTLFQsVSk7CgkJcXVlcmllc1tpXSA9IHtTLFQsVX07CgkJaWYgKFIucXVlcnkoUyxULTEpID4gVSkgewoJCQlhbnNbaV0gPSAtMTsKCQl9Cgl9Cglzb3J0KGFsbChpbnRlcnZhbHMpLFtdKGNvbnN0IGludGVydmFsJiBhLCBjb25zdCBpbnRlcnZhbCYgYikgewoJCXJldHVybiBhLmxlZiA8IGIubGVmOwoJfSk7CglkZWFsMigpOwoJdmkgcWluZHMoTSk7IGlvdGEoYWxsKHFpbmRzKSwwKTsKCXNvcnQoYWxsKHFpbmRzKSxbJl0oaW50IHgsIGludCB5KSB7CgkJcmV0dXJuIGdldDwwPihxdWVyaWVzW3hdKSA8IGdldDwwPihxdWVyaWVzW3ldKTsKCX0pOwoJaW50IHBvcyA9IDA7CglCQiA9IEJJVDxwbCxNWD4oKTsKCWZvciAoaW50IGk6IHFpbmRzKSBpZiAoYW5zW2ldICE9IC0xKSB7CgkJaW50IFMsVCxVOyB0aWUoUyxULFUpID0gcXVlcmllc1tpXTsKCQkvLyBlYWNoKHAsaW50ZXJ2YWxzKSBpZiAocC5sZWYgPCBTKSB7CgkJLy8gCWlmIChwLnJpZyA8PSBTKSB7CgoJCS8vIAl9IGVsc2UgaWYgKHAucmlnIDw9IFQpIHsKCQkvLyAJCWFuc1tpXSArPSBwLm11bCooY3VtW3AucmlnXS1jdW1bU10pOwoJCS8vIAl9IGVsc2UgewoJCS8vIAkJYW5zW2ldICs9IHAubXVsKihjdW1bVF0tY3VtW1NdKTsKCQkvLyAJfQoKCQkvLyB9CgkJZm9yKDtwb3MgPCBzeihpbnRlcnZhbHMpICYmIGludGVydmFsc1twb3NdLmxlZiA8IFM7Kytwb3MpIHsKCQkJY29uc3QgYXV0byYgcCA9IGludGVydmFsc1twb3NdOwoJCQlCQi51cGQoaW50ZXJ2YWxzW3Bvc10ucmlnLHBse3AubXVsKmN1bVtwLnJpZ10scC5tdWx9KTsKCQl9CgkJcGwgcXEgPSBCQi5xdWVyeShTLFQpOwoJCWFuc1tpXSArPSBxcS5mLXFxLnMqY3VtW1NdOwoJCXFxID0gQkIucXVlcnkoVCsxLE4rMik7CgkJYW5zW2ldICs9IHFxLnMqKGN1bVtUXS1jdW1bU10pOwoJfQoJZGVhbDEoKTsKCWVhY2godCxhbnMpIHBzKHQpOwoJLy8geW91IHNob3VsZCBhY3R1YWxseSByZWFkIHRoZSBzdHVmZiBhdCB0aGUgYm90dG9tCn0KCi8qIHN0dWZmIHlvdSBzaG91bGQgbG9vayBmb3IKCSogaW50IG92ZXJmbG93LCBhcnJheSBib3VuZHMKCSogc3BlY2lhbCBjYXNlcyAobj0xPykKCSogZG8gc210aCBpbnN0ZWFkIG9mIG5vdGhpbmcgYW5kIHN0YXkgb3JnYW5pemVkCgkqIFdSSVRFIFNUVUZGIERPV04KCSogRE9OJ1QgR0VUIFNUVUNLIE9OIE9ORSBBUFBST0FDSAoqLwo=