#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define files(name) name!=""?freopen(name".in","r",stdin),freopen(name".out","w",stdout):0
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define elif else if
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
using namespace std;
#define int long long
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
const int arr=2e5+10;
const int ar=2e3+10;
const ld pi=acos(-1);
const ld eps=1e-10;
const ll md=1e9+7;
///---program start---///
struct line
{
ld k,b;
set<line>::iterator it;
set<line>* where;
line() {}
line(ld k,ld b)
{
this->k=k;
this->b=b;
}
ld eval(ld x)
{
return k*x+b;
}
};
const bool operator<(const line& lhs,const line& rhs)
{
if (rhs.k==5e18){
auto it=lhs.it;
return next(it)!=lhs.where->end()&&next(it)->k*rhs.b+next(it)->b<=it->k*rhs.b+it->b;
}
return lhs.k>rhs.k||(lhs.k==rhs.k&&lhs.b<rhs.b);
}
ld intersect(line l1,line l2)
{
/// l1.k*x+l1.b==l2.k*x+l2.b
/// x*(l1.k-l2.k)==l2.b-l1.b
/// x==(l2.b-l1.b)/(l1.k-l2.k)
return (l2.b-l1.b)/(l1.k-l2.k);
}
bool to_erase(line l1,line l2,line l3)
{
ld x=intersect(l1,l2);
return l2.eval(x)>=l3.eval(x);
}
struct convex_hull_trick
{
set<line> lines;
convex_hull_trick()
{
lines.clear();
}
void clear()
{
lines.clear();
}
void add_line(line l)
{
auto it=lines.insert(l).fir;
line* what=(line*)&*it;
what->it=it;
what->where=(set<line>*)&lines;
while (it!=lines.begin()&&prev(it)->k==it->k){
lines.erase(it);
return;
}
while (next(it)!=lines.end()&&next(it)->k==it->k){
lines.erase(next(it));
}
if (it!=lines.begin()&&next(it)!=lines.end()&&to_erase(*prev(it),*it,*next(it))){
lines.erase(it);
return;
}
while (it!=lines.begin()&&prev(it)!=lines.begin()&&to_erase(*prev(prev(it)),*prev(it),*it)){
lines.erase(prev(it));
}
while (next(it)!=lines.end()&&next(next(it))!=lines.end()&&to_erase(*it,*next(it),*next(next(it)))){
lines.erase(next(it));
}
}
ld get(ld x)
{
if (lines.empty()){
return 5e18;
}
line special(5e18,x);
auto it=*lines.lower_bound(special);
return it.eval(x);
}
};
struct segment_tree
{
int n;
vector<convex_hull_trick> t;
segment_tree() {}
segment_tree(int n)
{
n++;
this->n=n;
t.resize(4*n);
}
void upd(int v,int l,int r,int tl,int tr,line val)
{
if (l>tr||r<tl){
return;
}
if (l>=tl&&r<=tr){
t[v].add_line(val);
return;
}
int m=(l+r)/2;
upd(v*2,l,m,tl,tr,val);
upd(v*2+1,m+1,r,tl,tr,val);
}
void upd(int tl,int tr,line val)
{
upd(1,1,n,tl,tr,val);
}
ld get(int v,int l,int r,int pos,ld x)
{
if (l==r){
return t[v].get(x);
}
ld res=t[v].get(x);
int m=(l+r)/2;
if (pos<=m){
res=min(res,get(v*2,l,m,pos,x));
}
else{
res=min(res,get(v*2+1,m+1,r,pos,x));
}
return res;
}
ld get(int pos,ld x)
{
return get(1,1,n,pos,x);
}
};
#define arr (int)(5e5+10)
vector<pii> reb[arr];
const int M=20;
int p[arr][M];
ld d[arr];
int deep[arr];
int cnt[arr];
int go_hld[arr];
void dfs(int now,int pred=-1)
{
p[now][0]=pred;
for (int i=1;i<M;i++){
p[now][i]=p[p[now][i-1]][i-1];
}
cnt[now]=1;
go_hld[now]=-1;
for (auto wh:reb[now]){
if (wh.fir!=pred){
deep[wh.fir]=deep[now]+1;
d[wh.fir]=d[now]+wh.sec;
dfs(wh.fir,now);
cnt[now]+=cnt[wh.fir];
if (go_hld[now]==-1||cnt[wh.fir]>cnt[go_hld[now]]){
go_hld[now]=wh.fir;
}
}
}
}
int lca(int u,int v)
{
if (deep[u]>deep[v]){
swap(u,v);
}
for (int i=M-1;i>=0;i--){
if (deep[p[v][i]]>=deep[u]){
v=p[v][i];
}
}
if (u==v){
return u;
}
for (int i=M-1;i>=0;i--){
if (p[u][i]!=p[v][i]){
u=p[u][i];
v=p[v][i];
}
}
return p[u][0];
}
int len_of_way[arr];
int top_of_way[arr];
int back_of_way[arr];
int number_of_way[arr];
segment_tree S;
vector<line> to_push_on_prefix[arr];
int pos_in_segment_tree[arr];
int who_with_pos[arr];
int current_number_of_way;
int current_pos_in_segment_tree;
void hld(int now,int pred)
{
pos_in_segment_tree[now]=++current_pos_in_segment_tree;
who_with_pos[pos_in_segment_tree[now]]=now;
number_of_way[now]=current_number_of_way;
if (!top_of_way[current_number_of_way]){
top_of_way[current_number_of_way]=now;
}
len_of_way[number_of_way[now]]++;
back_of_way[current_number_of_way]=now;
if (go_hld[now]!=-1){
hld(go_hld[now],now);
}
for (auto wh:reb[now]){
if (wh.fir!=pred&&wh.fir!=go_hld[now]){
current_number_of_way++;
hld(wh.fir,now);
}
}
}
void add_line_to_mini_way(int u,int v,line l) /// v is pred u
{
if (top_of_way[number_of_way[u]]==v){
to_push_on_prefix[pos_in_segment_tree[u]].pb(l);
}
else{
int tl=pos_in_segment_tree[v];
int tr=pos_in_segment_tree[u];
S.upd(tl,tr,l);
}
}
void add_line_to_way(int u,int v,line l) /// v is pred u
{
while (number_of_way[u]!=number_of_way[v]){
int to=top_of_way[number_of_way[u]];
add_line_to_mini_way(u,to,l);
u=p[to][0];
}
add_line_to_mini_way(u,v,l);
}
void add_way(int u,int v,ld t,ld s)
{
int LCA=lca(u,v);
line line1=*new line(-ld(1)/ld(s),ld(d[u])/s+t);
add_line_to_way(u,LCA,line1);
line line2=*new line(+ld(1)/ld(s),ld(d[u]-2*d[LCA])/s+t);
add_line_to_way(v,LCA,line2);
}
int n;
ld ans[arr];
void build_all_ans()
{
for (int i=1;i<=n;i++){
ans[i]=S.get(pos_in_segment_tree[i],d[i]);
}
convex_hull_trick CHT;
for (int i=0;i<=current_number_of_way;i++){
CHT.clear();
int cur=back_of_way[i];
for (int j=0;j<len_of_way[i];j++){
for (auto k:to_push_on_prefix[pos_in_segment_tree[cur]]){
CHT.add_line(k);
}
ans[cur]=min(ans[cur],CHT.get(d[cur]));
cur=p[cur][0];
}
}
}
void solve()
{
cin>>n;
for (int i=0;i<=n;i++){
reb[i].clear();
ans[i]=0;
len_of_way[i]=0;
top_of_way[i]=0;
back_of_way[i]=0;
number_of_way[i]=0;
to_push_on_prefix[i].clear();
pos_in_segment_tree[i]=0;
who_with_pos[i]=0;
d[i]=0;
deep[i]=0;
cnt[i]=0;
go_hld[i]=-1;
}
current_number_of_way=0;
current_pos_in_segment_tree=0;
for (int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
reb[u].pb({v,w});
reb[v].pb({u,w});
}
dfs(1,1);
hld(1,1);
S=*new segment_tree(n);
int m;
cin>>m;
while (m--){
int u,v,t,s;
cin>>u>>v>>t>>s;
add_way(u,v,t,s);
}
build_all_ans();
for (int i=1;i<=n;i++){
if (ans[i]==5e18){
cout<<-1<<"\n";
}
else{
cout<<fixed<<setprecision(7)<<ans[i]<<"\n";
}
}
}
main()
{
#ifdef I_love_Maria_Ivanova
files("barik");
freopen("debug.txt","w",stderr);
#endif
fast;
int test;
cin>>test;
while (test--){
solve();
}
}
I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk8zIikKI3ByYWdtYSBHQ0MgdGFyZ2V0KCJzc2Usc3NlMixzc2UzLHNzc2UzLHNzZTQscG9wY250LGFibSxtbXgsYXZ4LHR1bmU9bmF0aXZlIikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUoInVucm9sbC1sb29wcyIpCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgoKI2RlZmluZSBmYXN0IGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwojZGVmaW5lIGZpbGVzKG5hbWUpIG5hbWUhPSIiP2ZyZW9wZW4obmFtZSIuaW4iLCJyIixzdGRpbiksZnJlb3BlbihuYW1lIi5vdXQiLCJ3IixzdGRvdXQpOjAKI2RlZmluZSBhbGwoYSkgYS5iZWdpbigpLGEuZW5kKCkKI2RlZmluZSBsZW4oYSkgKGludCkoYS5zaXplKCkpCiNkZWZpbmUgZWxpZiBlbHNlIGlmCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgZmlyIGZpcnN0CiNkZWZpbmUgc2VjIHNlY29uZAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBpbnQgbG9uZyBsb25nCgp0eXBlZGVmIHVuc2lnbmVkIGxvbmcgbG9uZyB1bGw7CnR5cGVkZWYgcGFpcjxpbnQsaW50PiBwaWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwoKY29uc3QgaW50IGFycj0yZTUrMTA7CmNvbnN0IGludCBhcj0yZTMrMTA7CmNvbnN0IGxkIHBpPWFjb3MoLTEpOwpjb25zdCBsZCBlcHM9MWUtMTA7CmNvbnN0IGxsIG1kPTFlOSs3OwoKLy8vLS0tcHJvZ3JhbSBzdGFydC0tLS8vLwoKc3RydWN0IGxpbmUKewogICAgbGQgayxiOwogICAgc2V0PGxpbmU+OjppdGVyYXRvciBpdDsKICAgIHNldDxsaW5lPiogd2hlcmU7CgogICAgbGluZSgpIHt9CiAgICBsaW5lKGxkIGssbGQgYikKICAgIHsKICAgICAgICB0aGlzLT5rPWs7CiAgICAgICAgdGhpcy0+Yj1iOwogICAgfQoKICAgIGxkIGV2YWwobGQgeCkKICAgIHsKICAgICAgICByZXR1cm4gayp4K2I7CiAgICB9Cn07Cgpjb25zdCBib29sIG9wZXJhdG9yPChjb25zdCBsaW5lJiBsaHMsY29uc3QgbGluZSYgcmhzKQp7CiAgICBpZiAocmhzLms9PTVlMTgpewogICAgICAgIGF1dG8gaXQ9bGhzLml0OwogICAgICAgIHJldHVybiBuZXh0KGl0KSE9bGhzLndoZXJlLT5lbmQoKSYmbmV4dChpdCktPmsqcmhzLmIrbmV4dChpdCktPmI8PWl0LT5rKnJocy5iK2l0LT5iOwogICAgfQogICAgcmV0dXJuIGxocy5rPnJocy5rfHwobGhzLms9PXJocy5rJiZsaHMuYjxyaHMuYik7Cn0KCmxkIGludGVyc2VjdChsaW5lIGwxLGxpbmUgbDIpCnsKICAgIC8vLyBsMS5rKngrbDEuYj09bDIuayp4K2wyLmIKICAgIC8vLyB4KihsMS5rLWwyLmspPT1sMi5iLWwxLmIKICAgIC8vLyB4PT0obDIuYi1sMS5iKS8obDEuay1sMi5rKQogICAgcmV0dXJuIChsMi5iLWwxLmIpLyhsMS5rLWwyLmspOwp9Cgpib29sIHRvX2VyYXNlKGxpbmUgbDEsbGluZSBsMixsaW5lIGwzKQp7CiAgICBsZCB4PWludGVyc2VjdChsMSxsMik7CiAgICByZXR1cm4gbDIuZXZhbCh4KT49bDMuZXZhbCh4KTsKfQoKc3RydWN0IGNvbnZleF9odWxsX3RyaWNrCnsKICAgIHNldDxsaW5lPiBsaW5lczsKCiAgICBjb252ZXhfaHVsbF90cmljaygpCiAgICB7CiAgICAgICAgbGluZXMuY2xlYXIoKTsKICAgIH0KCiAgICB2b2lkIGNsZWFyKCkKICAgIHsKICAgICAgICBsaW5lcy5jbGVhcigpOwogICAgfQogICAgdm9pZCBhZGRfbGluZShsaW5lIGwpCiAgICB7CiAgICAgICAgYXV0byBpdD1saW5lcy5pbnNlcnQobCkuZmlyOwoKICAgICAgICBsaW5lKiB3aGF0PShsaW5lKikmKml0OwogICAgICAgIHdoYXQtPml0PWl0OwogICAgICAgIHdoYXQtPndoZXJlPShzZXQ8bGluZT4qKSZsaW5lczsKCiAgICAgICAgd2hpbGUgKGl0IT1saW5lcy5iZWdpbigpJiZwcmV2KGl0KS0+az09aXQtPmspewogICAgICAgICAgICBsaW5lcy5lcmFzZShpdCk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CgogICAgICAgIHdoaWxlIChuZXh0KGl0KSE9bGluZXMuZW5kKCkmJm5leHQoaXQpLT5rPT1pdC0+ayl7CiAgICAgICAgICAgIGxpbmVzLmVyYXNlKG5leHQoaXQpKTsKICAgICAgICB9CgogICAgICAgIGlmIChpdCE9bGluZXMuYmVnaW4oKSYmbmV4dChpdCkhPWxpbmVzLmVuZCgpJiZ0b19lcmFzZSgqcHJldihpdCksKml0LCpuZXh0KGl0KSkpewogICAgICAgICAgICBsaW5lcy5lcmFzZShpdCk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CgogICAgICAgIHdoaWxlIChpdCE9bGluZXMuYmVnaW4oKSYmcHJldihpdCkhPWxpbmVzLmJlZ2luKCkmJnRvX2VyYXNlKCpwcmV2KHByZXYoaXQpKSwqcHJldihpdCksKml0KSl7CiAgICAgICAgICAgIGxpbmVzLmVyYXNlKHByZXYoaXQpKTsKICAgICAgICB9CgogICAgICAgIHdoaWxlIChuZXh0KGl0KSE9bGluZXMuZW5kKCkmJm5leHQobmV4dChpdCkpIT1saW5lcy5lbmQoKSYmdG9fZXJhc2UoKml0LCpuZXh0KGl0KSwqbmV4dChuZXh0KGl0KSkpKXsKICAgICAgICAgICAgbGluZXMuZXJhc2UobmV4dChpdCkpOwogICAgICAgIH0KICAgIH0KCiAgICBsZCBnZXQobGQgeCkKICAgIHsKICAgICAgICBpZiAobGluZXMuZW1wdHkoKSl7CiAgICAgICAgICAgIHJldHVybiA1ZTE4OwogICAgICAgIH0KICAgICAgICBsaW5lIHNwZWNpYWwoNWUxOCx4KTsKICAgICAgICBhdXRvIGl0PSpsaW5lcy5sb3dlcl9ib3VuZChzcGVjaWFsKTsKICAgICAgICByZXR1cm4gaXQuZXZhbCh4KTsKICAgIH0KfTsKCnN0cnVjdCBzZWdtZW50X3RyZWUKewogICAgaW50IG47CiAgICB2ZWN0b3I8Y29udmV4X2h1bGxfdHJpY2s+IHQ7CgogICAgc2VnbWVudF90cmVlKCkge30KICAgIHNlZ21lbnRfdHJlZShpbnQgbikKICAgIHsKICAgICAgICBuKys7CiAgICAgICAgdGhpcy0+bj1uOwogICAgICAgIHQucmVzaXplKDQqbik7CiAgICB9CgogICAgdm9pZCB1cGQoaW50IHYsaW50IGwsaW50IHIsaW50IHRsLGludCB0cixsaW5lIHZhbCkKICAgIHsKICAgICAgICBpZiAobD50cnx8cjx0bCl7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgaWYgKGw+PXRsJiZyPD10cil7CiAgICAgICAgICAgIHRbdl0uYWRkX2xpbmUodmFsKTsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgICAgICBpbnQgbT0obCtyKS8yOwogICAgICAgIHVwZCh2KjIsbCxtLHRsLHRyLHZhbCk7CiAgICAgICAgdXBkKHYqMisxLG0rMSxyLHRsLHRyLHZhbCk7CiAgICB9CiAgICB2b2lkIHVwZChpbnQgdGwsaW50IHRyLGxpbmUgdmFsKQogICAgewogICAgICAgIHVwZCgxLDEsbix0bCx0cix2YWwpOwogICAgfQogICAgbGQgZ2V0KGludCB2LGludCBsLGludCByLGludCBwb3MsbGQgeCkKICAgIHsKICAgICAgICBpZiAobD09cil7CiAgICAgICAgICAgIHJldHVybiB0W3ZdLmdldCh4KTsKICAgICAgICB9CiAgICAgICAgbGQgcmVzPXRbdl0uZ2V0KHgpOwogICAgICAgIGludCBtPShsK3IpLzI7CiAgICAgICAgaWYgKHBvczw9bSl7CiAgICAgICAgICAgIHJlcz1taW4ocmVzLGdldCh2KjIsbCxtLHBvcyx4KSk7CiAgICAgICAgfQogICAgICAgIGVsc2V7CiAgICAgICAgICAgIHJlcz1taW4ocmVzLGdldCh2KjIrMSxtKzEscixwb3MseCkpOwogICAgICAgIH0KICAgICAgICByZXR1cm4gcmVzOwogICAgfQogICAgbGQgZ2V0KGludCBwb3MsbGQgeCkKICAgIHsKICAgICAgICByZXR1cm4gZ2V0KDEsMSxuLHBvcyx4KTsKICAgIH0KfTsKCiNkZWZpbmUgYXJyIChpbnQpKDVlNSsxMCkKCnZlY3RvcjxwaWk+IHJlYlthcnJdOwpjb25zdCBpbnQgTT0yMDsKaW50IHBbYXJyXVtNXTsKbGQgZFthcnJdOwppbnQgZGVlcFthcnJdOwppbnQgY250W2Fycl07CmludCBnb19obGRbYXJyXTsKCnZvaWQgZGZzKGludCBub3csaW50IHByZWQ9LTEpCnsKICAgIHBbbm93XVswXT1wcmVkOwogICAgZm9yIChpbnQgaT0xO2k8TTtpKyspewogICAgICAgIHBbbm93XVtpXT1wW3Bbbm93XVtpLTFdXVtpLTFdOwogICAgfQogICAgY250W25vd109MTsKICAgIGdvX2hsZFtub3ddPS0xOwogICAgZm9yIChhdXRvIHdoOnJlYltub3ddKXsKICAgICAgICBpZiAod2guZmlyIT1wcmVkKXsKICAgICAgICAgICAgZGVlcFt3aC5maXJdPWRlZXBbbm93XSsxOwogICAgICAgICAgICBkW3doLmZpcl09ZFtub3ddK3doLnNlYzsKICAgICAgICAgICAgZGZzKHdoLmZpcixub3cpOwogICAgICAgICAgICBjbnRbbm93XSs9Y250W3doLmZpcl07CiAgICAgICAgICAgIGlmIChnb19obGRbbm93XT09LTF8fGNudFt3aC5maXJdPmNudFtnb19obGRbbm93XV0pewogICAgICAgICAgICAgICAgZ29faGxkW25vd109d2guZmlyOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CgppbnQgbGNhKGludCB1LGludCB2KQp7CiAgICBpZiAoZGVlcFt1XT5kZWVwW3ZdKXsKICAgICAgICBzd2FwKHUsdik7CiAgICB9CiAgICBmb3IgKGludCBpPU0tMTtpPj0wO2ktLSl7CiAgICAgICAgaWYgKGRlZXBbcFt2XVtpXV0+PWRlZXBbdV0pewogICAgICAgICAgICB2PXBbdl1baV07CiAgICAgICAgfQogICAgfQogICAgaWYgKHU9PXYpewogICAgICAgIHJldHVybiB1OwogICAgfQogICAgZm9yIChpbnQgaT1NLTE7aT49MDtpLS0pewogICAgICAgIGlmIChwW3VdW2ldIT1wW3ZdW2ldKXsKICAgICAgICAgICAgdT1wW3VdW2ldOwogICAgICAgICAgICB2PXBbdl1baV07CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIHBbdV1bMF07Cn0KCmludCBsZW5fb2Zfd2F5W2Fycl07CmludCB0b3Bfb2Zfd2F5W2Fycl07CmludCBiYWNrX29mX3dheVthcnJdOwppbnQgbnVtYmVyX29mX3dheVthcnJdOwpzZWdtZW50X3RyZWUgUzsKdmVjdG9yPGxpbmU+IHRvX3B1c2hfb25fcHJlZml4W2Fycl07CgppbnQgcG9zX2luX3NlZ21lbnRfdHJlZVthcnJdOwppbnQgd2hvX3dpdGhfcG9zW2Fycl07CgppbnQgY3VycmVudF9udW1iZXJfb2Zfd2F5OwppbnQgY3VycmVudF9wb3NfaW5fc2VnbWVudF90cmVlOwoKdm9pZCBobGQoaW50IG5vdyxpbnQgcHJlZCkKewogICAgcG9zX2luX3NlZ21lbnRfdHJlZVtub3ddPSsrY3VycmVudF9wb3NfaW5fc2VnbWVudF90cmVlOwogICAgd2hvX3dpdGhfcG9zW3Bvc19pbl9zZWdtZW50X3RyZWVbbm93XV09bm93OwogICAgbnVtYmVyX29mX3dheVtub3ddPWN1cnJlbnRfbnVtYmVyX29mX3dheTsKICAgIGlmICghdG9wX29mX3dheVtjdXJyZW50X251bWJlcl9vZl93YXldKXsKICAgICAgICB0b3Bfb2Zfd2F5W2N1cnJlbnRfbnVtYmVyX29mX3dheV09bm93OwogICAgfQogICAgbGVuX29mX3dheVtudW1iZXJfb2Zfd2F5W25vd11dKys7CiAgICBiYWNrX29mX3dheVtjdXJyZW50X251bWJlcl9vZl93YXldPW5vdzsKCiAgICBpZiAoZ29faGxkW25vd10hPS0xKXsKICAgICAgICBobGQoZ29faGxkW25vd10sbm93KTsKICAgIH0KICAgIGZvciAoYXV0byB3aDpyZWJbbm93XSl7CiAgICAgICAgaWYgKHdoLmZpciE9cHJlZCYmd2guZmlyIT1nb19obGRbbm93XSl7CiAgICAgICAgICAgIGN1cnJlbnRfbnVtYmVyX29mX3dheSsrOwogICAgICAgICAgICBobGQod2guZmlyLG5vdyk7CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIGFkZF9saW5lX3RvX21pbmlfd2F5KGludCB1LGludCB2LGxpbmUgbCkgLy8vIHYgaXMgcHJlZCB1CnsKICAgIGlmICh0b3Bfb2Zfd2F5W251bWJlcl9vZl93YXlbdV1dPT12KXsKICAgICAgICB0b19wdXNoX29uX3ByZWZpeFtwb3NfaW5fc2VnbWVudF90cmVlW3VdXS5wYihsKTsKICAgIH0KICAgIGVsc2V7CiAgICAgICAgaW50IHRsPXBvc19pbl9zZWdtZW50X3RyZWVbdl07CiAgICAgICAgaW50IHRyPXBvc19pbl9zZWdtZW50X3RyZWVbdV07CiAgICAgICAgUy51cGQodGwsdHIsbCk7CiAgICB9Cn0KCnZvaWQgYWRkX2xpbmVfdG9fd2F5KGludCB1LGludCB2LGxpbmUgbCkgLy8vIHYgaXMgcHJlZCB1CnsKICAgIHdoaWxlIChudW1iZXJfb2Zfd2F5W3VdIT1udW1iZXJfb2Zfd2F5W3ZdKXsKICAgICAgICBpbnQgdG89dG9wX29mX3dheVtudW1iZXJfb2Zfd2F5W3VdXTsKICAgICAgICBhZGRfbGluZV90b19taW5pX3dheSh1LHRvLGwpOwogICAgICAgIHU9cFt0b11bMF07CiAgICB9CiAgICBhZGRfbGluZV90b19taW5pX3dheSh1LHYsbCk7Cn0KCnZvaWQgYWRkX3dheShpbnQgdSxpbnQgdixsZCB0LGxkIHMpCnsKICAgIGludCBMQ0E9bGNhKHUsdik7CiAgICBsaW5lIGxpbmUxPSpuZXcgbGluZSgtbGQoMSkvbGQocyksbGQoZFt1XSkvcyt0KTsKICAgIGFkZF9saW5lX3RvX3dheSh1LExDQSxsaW5lMSk7CiAgICBsaW5lIGxpbmUyPSpuZXcgbGluZSgrbGQoMSkvbGQocyksbGQoZFt1XS0yKmRbTENBXSkvcyt0KTsKICAgIGFkZF9saW5lX3RvX3dheSh2LExDQSxsaW5lMik7Cn0KCmludCBuOwpsZCBhbnNbYXJyXTsKCnZvaWQgYnVpbGRfYWxsX2FucygpCnsKICAgIGZvciAoaW50IGk9MTtpPD1uO2krKyl7CiAgICAgICAgYW5zW2ldPVMuZ2V0KHBvc19pbl9zZWdtZW50X3RyZWVbaV0sZFtpXSk7CiAgICB9CiAgICBjb252ZXhfaHVsbF90cmljayBDSFQ7CiAgICBmb3IgKGludCBpPTA7aTw9Y3VycmVudF9udW1iZXJfb2Zfd2F5O2krKyl7CiAgICAgICAgQ0hULmNsZWFyKCk7CiAgICAgICAgaW50IGN1cj1iYWNrX29mX3dheVtpXTsKICAgICAgICBmb3IgKGludCBqPTA7ajxsZW5fb2Zfd2F5W2ldO2orKyl7CiAgICAgICAgICAgIGZvciAoYXV0byBrOnRvX3B1c2hfb25fcHJlZml4W3Bvc19pbl9zZWdtZW50X3RyZWVbY3VyXV0pewogICAgICAgICAgICAgICAgQ0hULmFkZF9saW5lKGspOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGFuc1tjdXJdPW1pbihhbnNbY3VyXSxDSFQuZ2V0KGRbY3VyXSkpOwogICAgICAgICAgICBjdXI9cFtjdXJdWzBdOwogICAgICAgIH0KICAgIH0KfQoKdm9pZCBzb2x2ZSgpCnsKICAgIGNpbj4+bjsKCiAgICBmb3IgKGludCBpPTA7aTw9bjtpKyspewogICAgICAgIHJlYltpXS5jbGVhcigpOwogICAgICAgIGFuc1tpXT0wOwogICAgICAgIGxlbl9vZl93YXlbaV09MDsKICAgICAgICB0b3Bfb2Zfd2F5W2ldPTA7CiAgICAgICAgYmFja19vZl93YXlbaV09MDsKICAgICAgICBudW1iZXJfb2Zfd2F5W2ldPTA7CiAgICAgICAgdG9fcHVzaF9vbl9wcmVmaXhbaV0uY2xlYXIoKTsKICAgICAgICBwb3NfaW5fc2VnbWVudF90cmVlW2ldPTA7CiAgICAgICAgd2hvX3dpdGhfcG9zW2ldPTA7CiAgICAgICAgZFtpXT0wOwogICAgICAgIGRlZXBbaV09MDsKICAgICAgICBjbnRbaV09MDsKICAgICAgICBnb19obGRbaV09LTE7CiAgICB9CiAgICBjdXJyZW50X251bWJlcl9vZl93YXk9MDsKICAgIGN1cnJlbnRfcG9zX2luX3NlZ21lbnRfdHJlZT0wOwoKICAgIGZvciAoaW50IGk9MTtpPG47aSsrKXsKICAgICAgICBpbnQgdSx2LHc7CiAgICAgICAgY2luPj51Pj52Pj53OwogICAgICAgIHJlYlt1XS5wYih7dix3fSk7CiAgICAgICAgcmViW3ZdLnBiKHt1LHd9KTsKICAgIH0KICAgIGRmcygxLDEpOwogICAgaGxkKDEsMSk7CiAgICBTPSpuZXcgc2VnbWVudF90cmVlKG4pOwogICAgaW50IG07CiAgICBjaW4+Pm07CiAgICB3aGlsZSAobS0tKXsKICAgICAgICBpbnQgdSx2LHQsczsKICAgICAgICBjaW4+PnU+PnY+PnQ+PnM7CiAgICAgICAgYWRkX3dheSh1LHYsdCxzKTsKICAgIH0KICAgIGJ1aWxkX2FsbF9hbnMoKTsKICAgIGZvciAoaW50IGk9MTtpPD1uO2krKyl7CiAgICAgICAgaWYgKGFuc1tpXT09NWUxOCl7CiAgICAgICAgICAgIGNvdXQ8PC0xPDwiXG4iOwogICAgICAgIH0KICAgICAgICBlbHNlewogICAgICAgICAgICBjb3V0PDxmaXhlZDw8c2V0cHJlY2lzaW9uKDcpPDxhbnNbaV08PCJcbiI7CiAgICAgICAgfQogICAgfQp9CgptYWluKCkKewogICAgI2lmZGVmIElfbG92ZV9NYXJpYV9JdmFub3ZhCiAgICAgICAgZmlsZXMoImJhcmlrIik7CiAgICAgICAgZnJlb3BlbigiZGVidWcudHh0IiwidyIsc3RkZXJyKTsKICAgICNlbmRpZgoKICAgIGZhc3Q7CgogICAgaW50IHRlc3Q7CiAgICBjaW4+PnRlc3Q7CiAgICB3aGlsZSAodGVzdC0tKXsKICAgICAgICBzb2x2ZSgpOwogICAgfQp9