#include <bits/stdc++.h>
using namespace std;
#define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#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 rep(i, c) for(auto &(i) : (c))
#define x first
#define y second
#define pb push_back
#define PB pop_back()
#define iOS ios_base::sync_with_stdio(false)
#define sqr(a) (((a) * (a)))
#define all(a) a.begin() , a.end()
#define error(x) cerr << #x << " = " << (x) <<endl
#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define umap unordered_map
//#define max(x,y) ((x) > (y) ? (x) : (y))
#define double long double
typedef long long ll;
typedef pair<int,int>pii;
typedef vector<int> vi;
typedef pair<long long,long long> PLL;
const int maxn = 1e5 + 100;
const int maxl = 20;
int sz[maxn], f[maxn], par[maxn][maxl], h[maxn];
vi adj[maxn], adw[maxn];
int chn[maxn];
int w[maxn];
struct node{
ll p,s,tot,cnt;
node(){
cnt = p = s = tot = 0LL;
}
node(int x){
tot = 0LL;
p = s = cnt = x;
}
inline bool ish(){
return (cnt == p && p && s);
}
inline node operator * (node a){
node ans;
ans.cnt = a.cnt + cnt;
bool h = ish(), H = a.ish();
ans.tot = a.tot + tot;
if(!h && !H){
ans.tot += f[s + a.p];
ans.p = p;
ans.s = a.s;
}
else if(!h && H){
ans.p = p;
ans.s = s + a.s;
}
else if(h && !H){
ans.p = p + a.p;
ans.s = a.s;
}
else{
ans.p = ans.s = p + a.p;
}
return ans;
}
inline ll score(){
ll ans = tot + f[p];
if(!ish())
ans += f[s];
return ans;
}
inline node reverse(){
node ans;
ans.p = s;
ans.s = p;
ans.tot = tot;
ans.cnt = cnt;
return ans;
}
};
struct seg{
vector<node> s;
int sz;
seg(){
sz = 0;}
seg(int n){
while(s.size() < 4 * n)
s.pb(node());
sz = n;
}
inline void add(int p,int id,int l,int r){
if(r - l < 2){
s[id] = node(1);
return ;
}
int mid = (l+r)/2;
if(p < mid)
add(p, L(id), l, mid);
else
add(p, R(id), mid, r);
s[id] = s[L(id)] * s[R(id)];
}
inline node get(int x,int y,int id,int l,int r){
if(x <= l && r <= y)
return s[id];
int mid = (l+r)/2;
if(y <= mid)
return get(x, y, L(id), l, mid);
else if(mid <= x)
return get(x, y, R(id), mid, r);
return get(x, y, L(id), l, mid) * get(x, y, R(id), mid, r);
}
inline void ADD(int p){
add(p, 1, 0, sz);
}
inline node score(int x,int y){
return get(x, y, 1, 0, sz);
}
};
struct query{
int ind, mnh, mxh, l;
query(){
}
query(int a,int b,int c,int d){
ind = a;
mnh = b;
mxh = c;
l = d;
}
};
inline bool qcmp (const query &a, const query & q){
return a.l < q.l;
}
inline bool cmp(const pii &p, const pii &q){
if(p.y - q.y)
return p.y > q.y;
return p.x < q.x;
}
struct chain{
int X,x,y;
seg s;
umap <int, node> MP;
chain(){}
chain(int a,int b): X(a), y(b){}
chain(int a,int b,int c): X(a), x(b), y(c){}
vector<pii> vpn;
vector<query> QQ;
inline void proc(int i){
int v = y;
while(v != X){
if(par[v][0] == X)
x = v;
vpn.pb({h[v], w[v]});
chn[v] = i;
v = par[v][0];
}
sort(all(vpn));
}
inline void solve(){
sort(all(QQ), qcmp);
s = seg(vpn.size());
vector<pii> vs = vpn;
sort(all(vs), cmp);
reverse(all(QQ));
int po = 0;
rep(q, QQ){
while(po < vs.size() && vs[po].y >= q.l){
int i = lower_bound(all(vpn), pii(vs[po].x, -1)) - vpn.begin();
s.ADD(i);
po ++;
}
int l = lower_bound(all(vpn), pii(q.mnh, -1)) - vpn.begin();
int r = upper_bound(all(vpn), pii(q.mxh, 1e9)) - vpn.begin();
MP[q.ind] = s.score(l, r);
}
}
};
vector<chain> HLD;
inline int dfs(int v = 0,int p = -1){
if(p + 1)
h[v] = h[p] + 1;
par[v][0] = p;
For(i,1,maxl) if(par[v][i-1] + 1)
par[v][i] = par[par[v][i-1]][i-1];
sz[v] = 1;
For(i,0,adj[v].size()){
int u = adj[v][i];
if(u - p){
w[u] = adw[v][i];
sz[v] += dfs(u, v);
}
}
return sz[v];
}
inline void prepHLD(int v = 0,bool h = 0,int f = -1){
if(f == -1){
if(par[v][0] != -1)
f = par[v][0];
else
f = v;
}
bool hh = 0, ch = 0, is = 0;
rep(u, adj[v]){
if(u - par[v][0] && sz[u] * 2 >= sz[v])
hh = 1;
if(u - par[v][0])
ch = 1;
}
if(par[v][0] != -1){
if(h && !hh && !ch)
HLD.pb(chain(f,v));
if(!h && !ch)
HLD.pb(chain(par[v][0],v));
}
rep(u, adj[v])
if(u - par[v][0]){
if(sz[u] * 2 < sz[v]){
if(!is && !hh)
prepHLD(u,1,f);
else
prepHLD(u);
}
else
prepHLD(u,1,f);
is = 1;
}
}
inline int lca(int v,int u){
if(h[u] > h[v])
swap(v, u);
rof(i, maxl - 1, -1)
if(par[v][i] + 1 && h[par[v][i]] >= h[u])
v = par[v][i];
if(v == u) return v;
rof(i, maxl - 1, -1)
if(par[v][i] - par[u][i])
v = par[v][i], u = par[u][i];
return par[v][0];
}
inline vi dec(int v,int H){
vi ans;
while(v + 1 && h[v] > H){
ans.pb(chn[v]);
v = HLD[chn[v]].X;
}
return ans;
}
inline vi decompose(int v,int u){
int x = lca(v, u);
int H = h[x];
vi ans = dec(v, H);
vi V = dec(u, H);
reverse(all(V));
rep(w, V)
ans.pb(w);
return ans;
}
stringstream ss;
inline void prepQ(int i,int v,int w,int l){
while(v + 1 && h[v] > h[w]){
int j = chn[v];
int mnh = h[w] + 1;
int mxh = h[v];
HLD[j].QQ.pb(query(i, mnh, mxh, l));
v = HLD[chn[v]].X;
}
}
inline void prepq(int i,int v,int u,int l){
ss << v << ' ' << u << ' ' << l << '\n';
int w = lca(v, u);
prepQ(i, v, w, l);
prepQ(i, u, w, l);
}
int IND;
inline ll ANS(){
int v,u,l;
ss >> v >> u >> l;
int w = lca(v, u);
vi V = decompose(v, w);
vi U = decompose(w, u);
node N(0);
rep(c, V)
N = N * HLD[c].MP[IND].reverse();//, error(HLD[c].MP[IND].reverse().cnt);
rep(c, U){
N = N * HLD[c].MP[IND];
/* error(HLD[c].MP[IND].cnt);
error(HLD[c].MP[IND].p);
error(HLD[c].MP[IND].s);
error(HLD[c].y);*/
}
IND ++;
//Error(N.s, N.p);
//error(N.cnt);
return N.score();
}
int n,q;
int main(){
memset(par, -1, sizeof(par));
iOS;
cin >> n >> q;
For(i,1,n)
cin >> f[i];
int v,u,w;
For(i,1,n){
cin >> v >> u >> w;
-- v, -- u;
adj[v].pb(u);
adj[u].pb(v);
adw[v].pb(w);
adw[u].pb(w);
}
dfs();
prepHLD();
For(i,0,HLD.size())
HLD[i].proc(i);
//error(HLD.size());
For(i,0,q){
cin >> v >> u >> w;
-- v, -- u;
prepq(i, v, u, w);
}
For(i,0,HLD.size())
HLD[i].solve();
For(i,0,q)
cout << ANS() << '\n';
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgRm9yZWFjaChpLCBjKSBmb3IoX190eXBlb2YoKGMpLmJlZ2luKCkpIGkgPSAoYykuYmVnaW4oKTsgaSAhPSAoYykuZW5kKCk7ICsraSkKI2RlZmluZSBGb3IoaSxhLGIpIGZvcihpbnQgKGkpPShhKTsoaSkgPCAoYik7ICsrKGkpKQojZGVmaW5lIHJvZihpLGEsYikgZm9yKGludCAoaSk9KGEpOyhpKSA+IChiKTsgLS0oaSkpCiNkZWZpbmUgcmVwKGksIGMpICBmb3IoYXV0byAmKGkpIDogKGMpKQojZGVmaW5lIHggICAgIGZpcnN0CiNkZWZpbmUgeSAgICAgc2Vjb25kCiNkZWZpbmUgcGIgIHB1c2hfYmFjawojZGVmaW5lIFBCICBwb3BfYmFjaygpCiNkZWZpbmUgaU9TICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKQojZGVmaW5lIHNxcihhKSAgKCgoYSkgKiAoYSkpKQojZGVmaW5lIGFsbChhKSAgYS5iZWdpbigpICwgYS5lbmQoKQojZGVmaW5lIGVycm9yKHgpIGNlcnIgPDwgI3ggPDwgIiA9ICIgPDwgKHgpIDw8ZW5kbAojZGVmaW5lIEVycm9yKGEsYikgY2Vycjw8IiggIjw8I2E8PCIgLCAiPDwjYjw8IiApID0gKCAiPDwoYSk8PCIgLCAiPDwoYik8PCIgKVxuIjsKI2RlZmluZSBlcnJvcChhKSBjZXJyPDwjYTw8IiA9ICggIjw8KChhKS54KTw8IiAsICI8PCgoYSkueSk8PCIgKVxuIjsKI2RlZmluZSBjb3VkKGEsYikgY291dDw8Zml4ZWQgPDwgc2V0cHJlY2lzaW9uKChiKSkgPDwgKGEpCiNkZWZpbmUgTCh4KSAgKCh4KTw8MSkKI2RlZmluZSBSKHgpICAoKCh4KTw8MSkrMSkKI2RlZmluZSB1bWFwICB1bm9yZGVyZWRfbWFwCi8vI2RlZmluZSBtYXgoeCx5KSAgKCh4KSA+ICh5KSA/ICh4KSA6ICh5KSkKI2RlZmluZSBkb3VibGUgbG9uZyBkb3VibGUKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgcGFpcjxpbnQsaW50PnBpaTsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiBwYWlyPGxvbmcgbG9uZyxsb25nIGxvbmc+IFBMTDsKY29uc3QgaW50IG1heG4gPSAxZTUgKyAxMDA7CmNvbnN0IGludCBtYXhsID0gMjA7CmludCBzelttYXhuXSwgZlttYXhuXSwgcGFyW21heG5dW21heGxdLCBoW21heG5dOwp2aSBhZGpbbWF4bl0sIGFkd1ttYXhuXTsKaW50IGNoblttYXhuXTsKaW50IHdbbWF4bl07CnN0cnVjdCBub2RlewoJbGwgcCxzLHRvdCxjbnQ7Cglub2RlKCl7CgkJY250ID0gcCA9IHMgPSB0b3QgPSAwTEw7Cgl9Cglub2RlKGludCB4KXsKCQl0b3QgPSAwTEw7CgkJcCA9IHMgPSBjbnQgPSB4OwoJfQoJaW5saW5lIGJvb2wgaXNoKCl7CgkJcmV0dXJuIChjbnQgPT0gcCAmJiBwICYmIHMpOwoJfQoJaW5saW5lIG5vZGUgb3BlcmF0b3IgKiAobm9kZSBhKXsKCQlub2RlIGFuczsKCQlhbnMuY250ID0gYS5jbnQgKyBjbnQ7CgkJYm9vbCBoID0gaXNoKCksIEggPSBhLmlzaCgpOwoJCWFucy50b3QgPSBhLnRvdCArIHRvdDsKCQlpZighaCAmJiAhSCl7CgkJCWFucy50b3QgKz0gZltzICsgYS5wXTsKCQkJYW5zLnAgPSBwOwoJCQlhbnMucyA9IGEuczsKCQl9CgkJZWxzZSBpZighaCAmJiBIKXsKCQkJYW5zLnAgPSBwOwoJCQlhbnMucyA9IHMgKyBhLnM7CgkJfQoJCWVsc2UgaWYoaCAmJiAhSCl7CgkJCWFucy5wID0gcCArIGEucDsKCQkJYW5zLnMgPSBhLnM7CgkJfQoJCWVsc2V7CgkJCWFucy5wID0gYW5zLnMgPSBwICsgYS5wOwoJCX0KCQlyZXR1cm4gYW5zOwoJfQoJaW5saW5lIGxsIHNjb3JlKCl7CgkJbGwgYW5zID0gdG90ICsgZltwXTsKCQlpZighaXNoKCkpCgkJCWFucyArPSBmW3NdOwoJCXJldHVybiBhbnM7Cgl9CglpbmxpbmUgbm9kZSByZXZlcnNlKCl7CgkJbm9kZSBhbnM7CgkJYW5zLnAgPSBzOwoJCWFucy5zID0gcDsKCQlhbnMudG90ID0gdG90OwoJCWFucy5jbnQgPSBjbnQ7CgkJcmV0dXJuIGFuczsKCX0KfTsKc3RydWN0IHNlZ3sKCXZlY3Rvcjxub2RlPiBzOwoJaW50IHN6OwoJc2VnKCl7CglzeiA9IDA7fQoJc2VnKGludCBuKXsKCQl3aGlsZShzLnNpemUoKSA8IDQgKiBuKQoJCQlzLnBiKG5vZGUoKSk7CgkJc3ogPSBuOwoJfQoJaW5saW5lIHZvaWQgYWRkKGludCBwLGludCBpZCxpbnQgbCxpbnQgcil7CgkJaWYociAtIGwgPCAyKXsKCQkJc1tpZF0gPSBub2RlKDEpOwoJCQlyZXR1cm4gOwoJCX0KCQlpbnQgbWlkID0gKGwrcikvMjsKCQlpZihwIDwgbWlkKQoJCQlhZGQocCwgTChpZCksIGwsIG1pZCk7CgkJZWxzZQoJCQlhZGQocCwgUihpZCksIG1pZCwgcik7CgkJc1tpZF0gPSBzW0woaWQpXSAqIHNbUihpZCldOwoJfQoJaW5saW5lIG5vZGUgZ2V0KGludCB4LGludCB5LGludCBpZCxpbnQgbCxpbnQgcil7CgkJaWYoeCA8PSBsICYmIHIgPD0geSkKCQkJcmV0dXJuIHNbaWRdOwoJCWludCBtaWQgPSAobCtyKS8yOwoJCWlmKHkgPD0gbWlkKQoJCQlyZXR1cm4gZ2V0KHgsIHksIEwoaWQpLCBsLCBtaWQpOwoJCWVsc2UgaWYobWlkIDw9IHgpCgkJCXJldHVybiBnZXQoeCwgeSwgUihpZCksIG1pZCwgcik7CgkJcmV0dXJuIGdldCh4LCB5LCBMKGlkKSwgbCwgbWlkKSAqIGdldCh4LCB5LCBSKGlkKSwgbWlkLCByKTsKCX0KCWlubGluZSB2b2lkIEFERChpbnQgcCl7CgkJYWRkKHAsIDEsIDAsIHN6KTsKCX0KCWlubGluZSBub2RlIHNjb3JlKGludCB4LGludCB5KXsKCQlyZXR1cm4gZ2V0KHgsIHksIDEsIDAsIHN6KTsKCX0KCn07CnN0cnVjdCBxdWVyeXsKCWludCBpbmQsIG1uaCwgbXhoLCBsOwoJcXVlcnkoKXsKCX0KCXF1ZXJ5KGludCBhLGludCBiLGludCBjLGludCBkKXsKCQlpbmQgPSBhOwoJIAltbmggPSBiOwoJCW14aCA9IGM7CgkJbCA9IGQ7Cgl9Cn07CmlubGluZSBib29sIHFjbXAgKGNvbnN0IHF1ZXJ5ICZhLCBjb25zdCBxdWVyeSAmIHEpewoJCXJldHVybiBhLmwgPCBxLmw7Cgl9CmlubGluZSBib29sIGNtcChjb25zdCBwaWkgJnAsIGNvbnN0IHBpaSAmcSl7CglpZihwLnkgLSBxLnkpCgkJcmV0dXJuIHAueSA+IHEueTsKCXJldHVybiBwLnggPCBxLng7Cn0Kc3RydWN0IGNoYWluewoJaW50IFgseCx5OwoJc2VnIHM7Cgl1bWFwIDxpbnQsIG5vZGU+IE1QOwoJY2hhaW4oKXt9CgljaGFpbihpbnQgYSxpbnQgYik6IFgoYSksIHkoYil7fQoJY2hhaW4oaW50IGEsaW50IGIsaW50IGMpOiBYKGEpLCB4KGIpLCB5KGMpe30KCXZlY3RvcjxwaWk+IHZwbjsKCXZlY3RvcjxxdWVyeT4gUVE7CglpbmxpbmUgdm9pZCBwcm9jKGludCBpKXsKCQlpbnQgdiA9IHk7CgkJd2hpbGUodiAhPSBYKXsKCQkJaWYocGFyW3ZdWzBdID09IFgpCgkJCQl4ID0gdjsKCQkJdnBuLnBiKHtoW3ZdLCB3W3ZdfSk7CgkJCWNoblt2XSA9IGk7CgkJCXYgPSBwYXJbdl1bMF07CgkJfQoJCXNvcnQoYWxsKHZwbikpOwoJfQoJaW5saW5lIHZvaWQgc29sdmUoKXsKCQlzb3J0KGFsbChRUSksIHFjbXApOwoJCXMgPSBzZWcodnBuLnNpemUoKSk7CgkJdmVjdG9yPHBpaT4gdnMgPSB2cG47CgkJc29ydChhbGwodnMpLCBjbXApOwoJCXJldmVyc2UoYWxsKFFRKSk7CgkJaW50IHBvID0gMDsKCQlyZXAocSwgUVEpewoJCQl3aGlsZShwbyA8IHZzLnNpemUoKSAmJiB2c1twb10ueSA+PSBxLmwpewoJCQkJaW50IGkgPSBsb3dlcl9ib3VuZChhbGwodnBuKSwgcGlpKHZzW3BvXS54LCAtMSkpIC0gIHZwbi5iZWdpbigpOwoJCQkJcy5BREQoaSk7CgkJCQlwbyArKzsKCQkJfQoJCQlpbnQgbCA9IGxvd2VyX2JvdW5kKGFsbCh2cG4pLCBwaWkocS5tbmgsIC0xKSkgLSAgdnBuLmJlZ2luKCk7CgkJCWludCByID0gdXBwZXJfYm91bmQoYWxsKHZwbiksIHBpaShxLm14aCwgMWU5KSkgLSAgdnBuLmJlZ2luKCk7CgkJCU1QW3EuaW5kXSA9IHMuc2NvcmUobCwgcik7CgkJfQoJfQp9Owp2ZWN0b3I8Y2hhaW4+IEhMRDsKaW5saW5lIGludCBkZnMoaW50IHYgPSAwLGludCBwID0gLTEpewoJaWYocCArIDEpCgkJaFt2XSA9IGhbcF0gKyAxOwoJcGFyW3ZdWzBdID0gcDsKCUZvcihpLDEsbWF4bCkJaWYocGFyW3ZdW2ktMV0gKyAxKQoJCXBhclt2XVtpXSA9IHBhcltwYXJbdl1baS0xXV1baS0xXTsKCXN6W3ZdID0gMTsKCUZvcihpLDAsYWRqW3ZdLnNpemUoKSl7CgkJaW50IHUgPSBhZGpbdl1baV07CgkJaWYodSAtIHApewoJCQl3W3VdID0gYWR3W3ZdW2ldOwoJCQlzelt2XSArPSBkZnModSwgdik7CgkJfQoJfQoJcmV0dXJuIHN6W3ZdOwp9CmlubGluZSB2b2lkIHByZXBITEQoaW50IHYgPSAwLGJvb2wgaCA9IDAsaW50IGYgPSAtMSl7CglpZihmID09IC0xKXsKCQlpZihwYXJbdl1bMF0gIT0gLTEpCgkJCWYgPSBwYXJbdl1bMF07CgkJZWxzZQoJCQlmID0gdjsKCX0KCWJvb2wgaGggPSAwLCBjaCA9IDAsIGlzID0gMDsKCQlyZXAodSwgYWRqW3ZdKXsKCQkJaWYodSAtIHBhclt2XVswXSAmJiBzelt1XSAqIDIgPj0gc3pbdl0pCgkJCQloaCA9IDE7CgkJCWlmKHUgLSBwYXJbdl1bMF0pCgkJCQljaCA9IDE7CgkJfQoJaWYocGFyW3ZdWzBdICE9IC0xKXsKCQlpZihoICYmICFoaCAmJiAhY2gpCgkJCUhMRC5wYihjaGFpbihmLHYpKTsKCQlpZighaCAmJiAhY2gpCgkJCUhMRC5wYihjaGFpbihwYXJbdl1bMF0sdikpOwoJfQoJcmVwKHUsIGFkalt2XSkKCQlpZih1IC0gcGFyW3ZdWzBdKXsKCQkJaWYoc3pbdV0gKiAyIDwgc3pbdl0pewoJCQkJaWYoIWlzICYmICFoaCkKCQkJCQlwcmVwSExEKHUsMSxmKTsKCQkJCWVsc2UKCQkJCQlwcmVwSExEKHUpOwoJCQl9CgkJCWVsc2UKCQkJCXByZXBITEQodSwxLGYpOwoJCQlpcyA9IDE7CgkJfQp9CmlubGluZSBpbnQgbGNhKGludCB2LGludCB1KXsKCWlmKGhbdV0gPiBoW3ZdKQoJCXN3YXAodiwgdSk7Cglyb2YoaSwgbWF4bCAtIDEsIC0xKQoJCWlmKHBhclt2XVtpXSArIDEgJiYgaFtwYXJbdl1baV1dID49IGhbdV0pCgkJCXYgPSBwYXJbdl1baV07CglpZih2ID09IHUpCXJldHVybiB2OwoJcm9mKGksIG1heGwgLSAxLCAtMSkKCQlpZihwYXJbdl1baV0gLSBwYXJbdV1baV0pCgkJCXYgPSBwYXJbdl1baV0sIHUgPSBwYXJbdV1baV07CglyZXR1cm4gcGFyW3ZdWzBdOwp9CmlubGluZSB2aSBkZWMoaW50IHYsaW50IEgpewoJdmkgYW5zOwoJd2hpbGUodiArIDEgJiYgaFt2XSA+IEgpewoJCWFucy5wYihjaG5bdl0pOwoJCXYgPSBITERbY2huW3ZdXS5YOwoJfQoJcmV0dXJuIGFuczsKfQppbmxpbmUgdmkgZGVjb21wb3NlKGludCB2LGludCB1KXsKCWludCB4ID0gbGNhKHYsIHUpOwoJaW50IEggPSBoW3hdOwoJdmkgYW5zID0gZGVjKHYsIEgpOwoJdmkgViA9IGRlYyh1LCBIKTsKCXJldmVyc2UoYWxsKFYpKTsKCXJlcCh3LCBWKQoJCWFucy5wYih3KTsKCXJldHVybiBhbnM7Cn0Kc3RyaW5nc3RyZWFtIHNzOwppbmxpbmUgdm9pZCBwcmVwUShpbnQgaSxpbnQgdixpbnQgdyxpbnQgbCl7Cgl3aGlsZSh2ICsgMSAmJiBoW3ZdID4gaFt3XSl7CgkJaW50IGogPSBjaG5bdl07CgkJaW50IG1uaCA9IGhbd10gKyAxOwoJCWludCBteGggPSBoW3ZdOwoJCUhMRFtqXS5RUS5wYihxdWVyeShpLCBtbmgsIG14aCwgbCkpOwoJCXYgPSBITERbY2huW3ZdXS5YOwoJfQp9CmlubGluZSB2b2lkIHByZXBxKGludCBpLGludCB2LGludCB1LGludCBsKXsKCXNzIDw8IHYgPDwgJyAnIDw8IHUgPDwgJyAnIDw8IGwgPDwgJ1xuJzsKCWludCB3ID0gbGNhKHYsIHUpOwoJcHJlcFEoaSwgdiwgdywgbCk7CglwcmVwUShpLCB1LCB3LCBsKTsKfQppbnQgSU5EOwppbmxpbmUgbGwgQU5TKCl7CglpbnQgdix1LGw7CglzcyA+PiB2ID4+IHUgPj4gbDsKCWludCB3ID0gbGNhKHYsIHUpOwoJdmkgViA9IGRlY29tcG9zZSh2LCB3KTsKCXZpIFUgPSBkZWNvbXBvc2UodywgdSk7Cglub2RlIE4oMCk7CglyZXAoYywgVikKCQlOID0gTiAqIEhMRFtjXS5NUFtJTkRdLnJldmVyc2UoKTsvLywgZXJyb3IoSExEW2NdLk1QW0lORF0ucmV2ZXJzZSgpLmNudCk7CglyZXAoYywgVSl7CgkJTiA9IE4gKiBITERbY10uTVBbSU5EXTsKCS8qCWVycm9yKEhMRFtjXS5NUFtJTkRdLmNudCk7CgkJZXJyb3IoSExEW2NdLk1QW0lORF0ucCk7CgkJZXJyb3IoSExEW2NdLk1QW0lORF0ucyk7CgkJZXJyb3IoSExEW2NdLnkpOyovCgoJfQoJSU5EICsrOwoJLy9FcnJvcihOLnMsIE4ucCk7CgkvL2Vycm9yKE4uY250KTsKCXJldHVybiBOLnNjb3JlKCk7Cn0KaW50IG4scTsKaW50IG1haW4oKXsKCW1lbXNldChwYXIsIC0xLCBzaXplb2YocGFyKSk7CglpT1M7CgljaW4gPj4gbiA+PiBxOwoJRm9yKGksMSxuKQoJCWNpbiA+PiBmW2ldOwoJaW50IHYsdSx3OwoJRm9yKGksMSxuKXsKCQljaW4gPj4gdiA+PiB1ID4+IHc7CgkJLS0gdiwgLS0gdTsKCQlhZGpbdl0ucGIodSk7CgkJYWRqW3VdLnBiKHYpOwoJCWFkd1t2XS5wYih3KTsKCQlhZHdbdV0ucGIodyk7Cgl9CglkZnMoKTsKCXByZXBITEQoKTsKCUZvcihpLDAsSExELnNpemUoKSkKCQlITERbaV0ucHJvYyhpKTsKCS8vZXJyb3IoSExELnNpemUoKSk7CglGb3IoaSwwLHEpewoJCWNpbiA+PiB2ID4+IHUgPj4gdzsKCQktLSB2LCAtLSB1OwoJCXByZXBxKGksIHYsIHUsIHcpOwoJfQoJRm9yKGksMCxITEQuc2l6ZSgpKQoJCUhMRFtpXS5zb2x2ZSgpOwoJRm9yKGksMCxxKQoJCWNvdXQgPDwgQU5TKCkgPDwgJ1xuJzsKCn0K