Disruption

#include <bits/stdc++.h>

#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

using namespace std;

struct PairHash {inline std::size_t operator()(const std::pair<long long, long long> &v) const { return v.first * 31ll + v.second; }};

// speed
#define Code ios_base::sync_with_stdio(false);
#define By ios::sync_with_stdio(0);
#define Sumfi cout.tie(NULL);

// alias
using ll = long long;
using ld = long double;
using ull = unsigned long long;

// constants
const ld PI = acosl(-1.0);  /* pi */
const ll INF = 1e18;
const ld EPS = 1e-9;
const ll MAX_N = 202020;
const ll mod = 1e9 + 7;

// typedef
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef array<int,3> ai3;
typedef array<ll,3> all3;
typedef array<ll,4> all4;
typedef array<ll,5> all5;
typedef vector<all3> vall3;
typedef vector<all4> vall4;
typedef vector<all5> vall5;
typedef pair<ld, ld> pld;
typedef vector<pld> vpld;
typedef vector<ld> vld;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef deque<ll> dqll;
typedef deque<pll> dqpll;
typedef pair<string, string> pss;
typedef vector<pss> vpss;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef unordered_set<ll> usll;
typedef unordered_set<pll, PairHash> uspll;
typedef unordered_map<ll, ll> umll;
typedef unordered_map<pll, ll, PairHash> umpll;

// macros
#define precision(x) cout<<fixed;cout.precision(x);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,m,n) for(ll i=n;i>=m;i--)
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define uniq(a) sort(all(a)), a.erase(unique(all(a)),end(a))
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define INF(a) memset(a,0x3f3f3f3f3f3f3f3fLL,sizeof(a))
#define NEGINF(a) memset(a,0xcf,sizeof(a))
#define ASCEND(a,b) iota(all(a),b)
#define sz(x) ll((x).size())
#define BIT(a,i) ((a>>i)&1)
#define BITSHIFT(a,i,n) (((a<<i) & ((1ll<<n) - 1)) | (a>>(n-i)))
#define MAXBIT(a) (64ll - __builtin_clzll(a) - 1ll)
#define MINBIT(a) (__builtin_ctzll(a))
#define pyes cout<<"Yes\n";
#define pno cout<<"No\n";
#define endl "\n"
#define pneg1 cout<<"-1\n";
#define ppossible cout<<"possible\n";
#define pimpossible cout<<"impossible\n";
#define TC(x) cout<<"Case #"<<x<<": ";
#define X first
#define Y second

// debug
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename A>
void __print(const A &x);
template <typename A, typename B>
void __print(const pair<A, B> &p);
template <typename... A>
void __print(const tuple<A...> &t);
template <typename T>
void __print(stack<T> s);
template <typename T>
void __print(queue<T> q);
template <typename T, typename... U>
void __print(priority_queue<T, U...> q);
template <typename A>
void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
template <typename A, typename B>
void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.first);
    cerr << ',';
    __print(p.second);
    cerr << ')';
}
template <typename... A>
void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first](const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
template <typename T>
void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
template <typename T>
void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
template <typename T, typename... U>
void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
void _print() { cerr << "]\n"; }
template <typename Head, typename... Tail>
void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T))
        cerr << ", ";
    _print(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "Line:" << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__);
#else
#define debug(...)
#endif

// utility functions
template <typename T>
void print(T &&t)  { cout << t << "\n"; }
template<typename T>
void printv(vector<T>v){ll n=v.size();rep(i,0,n){cout<<v[i];if(i+1!=n)cout<<' ';}cout<<endl;}
template<typename T>
void printvv(vector<vector<T>>v){ll n=v.size();rep(i,0,n)printv(v[i]);}
template<typename T>
void printvln(vector<T>v){ll n=v.size();rep(i,0,n)cout<<v[i]<<endl;}
void fileIO(string in = "input.txt", string out = "output.txt") {freopen(in.c_str(),"r",stdin); freopen(out.c_str(),"w",stdout);}
void hackercupIO(string in) {fileIO("/Users/hayoungsong/Downloads/" + in + ".txt", "/Users/hayoungsong/Downloads/" + in + "_solution.txt");}
void readf(string in) {freopen(("/Users/hayoungsong/Downloads/" + in).c_str(), "rt", stdin);}
template <typename... T>
void in(T &...a) { ((cin >> a), ...); }
template<typename T>
void in(vector<T>& v){rep(i,0,sz(v)) in(v[i]);}
template<typename T>
void in(deque<T>& v){rep(i,0,sz(v)) in(v[i]);}
template<typename T, typename U>
void in(pair<T,U>& A) {in(A.first, A.second);}
template<typename T, typename U>
void in(vector<pair<T,U>>& A) {rep(i,0,sz(A)) in(A[i]); }
template<typename T, std::size_t N>
void in(vector<array<T,N>>& A) {rep(i,0,sz(A)) rep(j,0,sz(A[i])) in(A[i][j]); }
template<typename T>
void in(vector<vector<T>>& A) {rep(i,0,sz(A)) in(A[i]);}

struct Combination {
    vll fac, inv;
    ll n, MOD;

    ll modpow(ll n, ll x, ll MOD = mod) { if(!x) return 1; ll res = modpow(n,x>>1,MOD); res = (res * res) % MOD; if(x&1) res = (res * n) % MOD; return res; }

    Combination(ll _n, ll MOD = mod): n(_n + 1), MOD(MOD) {
        inv = fac = vll(n,1);
        rep(i,1,n) fac[i] = fac[i-1] * i % MOD;
        inv[n - 1] = modpow(fac[n - 1], MOD - 2, MOD);
        rrep(i,1,n - 2) inv[i] = inv[i + 1] * (i + 1) % MOD;
    }

    ll fact(ll n) {return fac[n];}
    ll nCr(ll n, ll r) {
        if(n < r or n < 0 or r < 0) return 0;
        return fac[n] * inv[r] % MOD * inv[n-r] % MOD;
    }
};

struct Matrix {
    ll r,c,MOD;
    vvll matrix;
    Matrix(ll r, ll c, ll v = 0, ll MOD = mod): r(r), c(c), matrix(vvll(r,vll(c,v))), MOD(MOD) {}
    Matrix(vvll m, ll MOD = mod) : r(sz(m)), c(sz(m[0])), matrix(m), MOD(MOD) {}

    vector<ll>& operator[](ll pos) {return matrix[pos];}
    Matrix operator*(const Matrix& B) const {
        Matrix res(r, B.c, 0,MOD);
        rep(i,0,r) rep(j,0,B.c) rep(k,0,B.r) {
                    res[i][j] = (res[i][j] + matrix[i][k] * B.matrix[k][j] % MOD) % MOD;
                }
        return res;
    }

    Matrix copy() {
        Matrix copy(r,c,0,MOD);
        copy.matrix = matrix;
        return copy;
    }


    Matrix pow(ll n) {
        assert(r == c);
        Matrix res(r,r, 0,MOD);
        Matrix now = copy();
        rep(i,0,r) res[i][i] = 1;
        while(n) {
            if(n & 1) res = res * now;
            now = now * now;
            n /= 2;
        }
        return res;
    }

    ll det() {
        if(r == 1) return matrix[0][0];
        if(r == 2) return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
        ll res = 0;
        rep(p,0,c) {
            Matrix mat(c-1,c-1);
            rep(i,1,r) rep(j,0,c) {
                    if(j == p) continue;
                    mat[i][j - (j >= p)] = matrix[i][j];
                }
            res += matrix[0][p] * (p & 1 ? -1 : 1) * mat.det();
        }
        return res;
    }
};

// geometry data structures
template <typename T>
struct Point {
    T y,x;
    Point(T y, T x) : y(y), x(x) {}
    Point(pair<T,T> p) : y(p.first), x(p.second) {}
    Point() {}
    void input() {cin>>y>>x;}
    friend ostream& operator<<(ostream& os, const Point<T>& p) { os<<p.y<<' '<<p.x<<'\n'; return os;}
    friend istream& operator>>(istream& os, Point<T> &p) { return os>>p.y>>p.x; }
    Point<T> operator+(Point<T>& p) {return Point<T>(y + p.y, x + p.x);}
    Point<T> operator-(Point<T>& p) {return Point<T>(y - p.y, x - p.x);}
    Point<T> operator*(ll n) {return Point<T>(y*n,x*n); }
    Point<T> operator/(ll n) {return Point<T>(y/n,x/n); }
    bool operator==(const Point<T> &a) {return x == a.x && y == a.y;}
    bool operator!=(const Point<T> &a) {return x != a.x or y != a.y;}
    bool operator<(const Point &other) const {if (x == other.x) return y < other.y;return x < other.x;}
    Point<T> rotate(Point<T> center, ld angle) {
        ld si = sin(angle * PI / 180.), co = cos(angle * PI / 180.);
        ld y = this->y - center.y;
        ld x = this->x - center.x;

        return Point<T>(y * co - x * si + center.y, y * si + x * co + center.x);
    }
    ld distance(Point<T> other) {
        T dy = abs(this->y - other.y);
        T dx = abs(this->x - other.x);
        return sqrt(dy * dy + dx * dx);
    }

    T norm() { return x * x + y * y; }
};

template<typename T>
struct Line {
    Point<T> A, B;
    Line(Point<T> A, Point<T> B) : A(A), B(B) {}
    Line() {}

    void input() {
        A = Point<T>();
        B = Point<T>();
        A.input();
        B.input();
    }

    T ccw(Point<T> &a, Point<T> &b, Point<T> &c) {
        T res = a.x * b.y + b.x * c.y + c.x * a.y;
        res -= (a.x * c.y + b.x * a.y + c.x * b.y);
        return res;
    }

    bool on(Point<T> x) {
        return ccw(A,x,B) == 0;
    }

    bool onSegment(Point<T> x) {
        if(!on(x)) return false;
        if(min(A.x, B.x) > x.x or max(A.x, B.x) < x.x) return false;
        if(min(A.y, B.y) > x.y or max(A.y, B.y) < x.y) return false;
        return true;
    }

    bool isIntersect(Line<T> o) {
        T p1p2 = ccw(A,B,o.A) * ccw(A,B,o.B);
        T p3p4 = ccw(o.A,o.B,A) * ccw(o.A,o.B,B);
        if (p1p2 == 0 && p3p4 == 0) {
            pair<T,T> p1(A.y, A.x), p2(B.y,B.x), p3(o.A.y, o.A.x), p4(o.B.y, o.B.x);
            if (p1 > p2) swap(p2, p1);
            if (p3 > p4) swap(p3, p4);
            return p3 <= p2 && p1 <= p4;
        }
        return p1p2 <= 0 && p3p4 <= 0;
    }

    pair<bool,Point<ld>> intersection(Line<T> o) {
        if(!this->intersection(o)) return {false, {}};
        ld det = 1. * (o.B.y-o.A.y)*(B.x-A.x) - 1.*(o.B.x-o.A.x)*(B.y-A.y);
        ld t = ((o.B.x-o.A.x)*(A.y-o.A.y) - (o.B.y-o.A.y)*(A.x-o.A.x)) / det;
        return {true, {A.y + 1. * t * (B.y - A.y), B.x + 1. * t * (B.x - A.x)}};
    }

    //@formula for : y = ax + pre
    //@return {a,pre};
    pair<ld, ld> formula() {
        T y1 = A.y, y2 = B.y;
        T x1 = A.x, x2 = B.x;
        if(y1 == y2) return {0, (ld)y1};
        if(x1 == x2) return {INF, (ld)x1};
        ld a = 1. * (y2 - y1) / (x2 - x1);
        ld b = -x1 * a + y1;
        return {a, b};
    }
};

template<typename T>
struct Circle {
    Point<T> center;
    T radius;
    Circle(T y, T x, T radius) : center(Point<T>(y,x)), radius(radius) {}
    Circle(Point<T> center, T radius) : center(center), radius(radius) {}
    Circle() {}

    void input() {
        center = Point<T>();
        center.input();
        cin>>radius;
    }

    bool circumference(Point<T> p) {
        return (center.x - p.x) * (center.x - p.x) + (center.y - p.y) * (center.y - p.y) == radius * radius;
    }

    bool intersect(Circle<T> c) {
        T d = (center.x - c.center.x) * (center.x - c.center.x) + (center.y - c.center.y) * (center.y - c.center.y);
        return (radius - c.radius) * (radius - c.radius) <= d and d <= (radius + c.radius) * (radius + c.radius);
    }

    bool include(Circle<T> c) {
        T d = (center.x - c.center.x) * (center.x - c.center.x) + (center.y - c.center.y) * (center.y - c.center.y);
        return d <= radius * radius;
    }

    bool include(Point<T> p) {
        T d = (center.x - p.x) * (center.x - p.x) + (center.y - p.y) * (center.y - p.y);
        return d <= radius * radius;
    }
};

ll __gcd(ll x, ll y) { return !y ? x : __gcd(y, x % y); }
all3 __exgcd(ll x, ll y) { if(!y) return {x,1,0}; auto [g,x1,y1] = __exgcd(y, x % y); return {g, y1, x1 - (x/y) * y1}; }
ll __lcm(ll x, ll y) { return x / __gcd(x,y) * y; }
ll modpow(ll n, ll x, ll MOD = mod) {if(x<0){return modpow(modpow(n,-x,MOD),MOD-2,MOD);}n%=MOD;ll res=1;while(x){if(x&1){res=res*n%MOD;}n=n*n%MOD;x>>=1;}return res;}
ll __xor(ll n) {return n%4==0?n:n%4==1?1:n%4==2?n+1:0;}
ll __rangexor(ll l, ll r) {return __xor(r)^__xor(l-1);};




template<typename W>
struct LazySegTree {
    int n;
    vector<W> st_sum, st_min, st_max;
    vector<W> lazy_add, lazy_mul, lazy_set;
    LazySegTree(): n(0) {}
    LazySegTree(int _n): n(_n) {
        st_sum.assign(4*n, 0);
        st_min.assign(4*n, numeric_limits<W>::max());
        st_max.assign(4*n, numeric_limits<W>::lowest());
        lazy_add.assign(4*n, 0);
        lazy_mul.assign(4*n, 1);
        lazy_set.assign(4*n, numeric_limits<W>::lowest());
    }
    void init(const vector<W>& A) {
        n = A.size();
        st_sum.assign(4*n, 0);
        st_min.assign(4*n, numeric_limits<W>::max());
        st_max.assign(4*n, numeric_limits<W>::lowest());
        lazy_add.assign(4*n, 0);
        lazy_mul.assign(4*n, 1);
        lazy_set.assign(4*n, numeric_limits<W>::lowest());
        build(1,0,n-1,A);
    }
private:
    void build(int p,int l,int r,const vector<W>& A){
        if(l==r){
            W v=A[l];
            st_sum[p]=v;
            st_min[p]=v;
            st_max[p]=v;
        } else {
            int m=(l+r)/2;
            build(p<<1,l,m,A);
            build(p<<1|1,m+1,r,A);
            pull(p);
        }
    }
    void pull(int p){
        st_sum[p]=st_sum[p<<1]+st_sum[p<<1|1];
        st_min[p]=min(st_min[p<<1],st_min[p<<1|1]);
        st_max[p]=max(st_max[p<<1],st_max[p<<1|1]);
    }
    void apply_set_op(int p,int l,int r,W v){
        st_sum[p]=v*(r-l+1);
        st_min[p]=v;
        st_max[p]=v;
        lazy_set[p]=v;
        lazy_mul[p]=1;
        lazy_add[p]=0;
    }
    void apply_mul_op(int p,int l,int r,W v){
        st_sum[p]*=v;
        st_min[p]*=v;
        st_max[p]*=v;
        if(lazy_set[p]!=numeric_limits<W>::lowest()){
            lazy_set[p]*=v;
        }
        lazy_mul[p]*=v;
        lazy_add[p]*=v;
    }
    void apply_add_op(int p,int l,int r,W v){
        st_sum[p]+=v*(r-l+1);
        st_min[p]+=v;
        st_max[p]+=v;
        if(lazy_set[p]!=numeric_limits<W>::lowest()){
            lazy_set[p]+=v;
        }
        lazy_add[p]+=v;
    }
    void push(int p,int l,int r){
        if(lazy_set[p]!=numeric_limits<W>::lowest()){
            int m=(l+r)/2;
            apply_set_op(p<<1,l,m,lazy_set[p]);
            apply_set_op(p<<1|1,m+1,r,lazy_set[p]);
            lazy_set[p]=numeric_limits<W>::lowest();
        }
        if(lazy_mul[p]!=1){
            int m=(l+r)/2;
            apply_mul_op(p<<1,l,m,lazy_mul[p]);
            apply_mul_op(p<<1|1,m+1,r,lazy_mul[p]);
            lazy_mul[p]=1;
        }
        if(lazy_add[p]!=0){
            int m=(l+r)/2;
            apply_add_op(p<<1,l,m,lazy_add[p]);
            apply_add_op(p<<1|1,m+1,r,lazy_add[p]);
            lazy_add[p]=0;
        }
    }
public:
    void update_set(int i,int j,W v){ update_set(1,0,n-1,i,j,v); }
    void update_mul(int i,int j,W v){ update_mul(1,0,n-1,i,j,v); }
    void update_add(int i,int j,W v){ update_add(1,0,n-1,i,j,v); }
    W querySum(int i,int j){ return query(1,0,n-1,i,j); }
    W queryMin(int i,int j){ return queryMin(1,0,n-1,i,j); }
    W queryMax(int i,int j){ return queryMax(1,0,n-1,i,j); }
private:
    void update_set(int p,int l,int r,int i,int j,W v){
        if(r<i||l>j) return;
        if(i<=l&&r<=j){ apply_set_op(p,l,r,v); return; }
        push(p,l,r);
        int m=(l+r)/2;
        update_set(p<<1,l,m,i,j,v);
        update_set(p<<1|1,m+1,r,i,j,v);
        pull(p);
    }
    void update_mul(int p,int l,int r,int i,int j,W v){
        if(r<i||l>j) return;
        if(i<=l&&r<=j){ apply_mul_op(p,l,r,v); return; }
        push(p,l,r);
        int m=(l+r)/2;
        update_mul(p<<1,l,m,i,j,v);
        update_mul(p<<1|1,m+1,r,i,j,v);
        pull(p);
    }
    void update_add(int p,int l,int r,int i,int j,W v){
        if(r<i||l>j) return;
        if(i<=l&&r<=j){ apply_add_op(p,l,r,v); return; }
        push(p,l,r);
        int m=(l+r)/2;
        update_add(p<<1,l,m,i,j,v);
        update_add(p<<1|1,m+1,r,i,j,v);
        pull(p);
    }
    W query(int p,int l,int r,int i,int j){
        if(r<i||l>j) return 0;
        if(i<=l&&r<=j) return st_sum[p];
        push(p,l,r);
        int m=(l+r)/2;
        return query(p<<1,l,m,i,j)+query(p<<1|1,m+1,r,i,j);
    }
    W queryMin(int p,int l,int r,int i,int j){
        if(r<i||l>j) return numeric_limits<W>::max();
        if(i<=l&&r<=j) return st_min[p];
        push(p,l,r);
        int m=(l+r)/2;
        return min(queryMin(p<<1,l,m,i,j),queryMin(p<<1|1,m+1,r,i,j));
    }
    W queryMax(int p,int l,int r,int i,int j){
        if(r<i||l>j) return numeric_limits<W>::lowest();
        if(i<=l&&r<=j) return st_max[p];
        push(p,l,r);
        int m=(l+r)/2;
        return max(queryMax(p<<1,l,m,i,j),queryMax(p<<1|1,m+1,r,i,j));
    }
};

template<typename W>
struct HLD {
    int n;
    vector<vector<pair<int,W>>> adj;
    vector<int> parent, depth, heavy, head, pos, size, invPos;
    vector<W> distRoot, parentEdge;
    int curPos;
    LazySegTree<W> seg;

    HLD(int _n)
            : n(_n), adj(n), parent(n), depth(n), heavy(n,-1),
              head(n), pos(n), size(n), distRoot(n), parentEdge(n), curPos(0), invPos(n) {}
    void addEdge(int u, int v, W w) {
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    int dfs1(int u, int p, W w) {
        parent[u] = p;
        parentEdge[u] = w;
        size[u] = 1;
        int maxSub = 0;
        for (auto &pr : adj[u]) {
            int v = pr.first;
            W wt = pr.second;
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            distRoot[v] = distRoot[u] + wt;
            int subsz = dfs1(v, u, wt);
            if (subsz > maxSub) {
                maxSub = subsz;
                heavy[u] = v;
            }
            size[u] += subsz;
        }
        return size[u];
    }
    void dfs2(int u, int h) {
        head[u] = h;
        invPos[curPos] = u;
        pos[u] = curPos++;
        if (heavy[u] != -1) dfs2(heavy[u], h);
        for (auto &pr : adj[u]) {
            int v = pr.first;
            if (v == parent[u] || v == heavy[u]) continue;
            dfs2(v, v);
        }
    }
    void build(int root = 0) {
        depth[root] = 0;
        distRoot[root] = 0;
        dfs1(root, -1, 0);
        dfs2(root, root);
        vector<W> base(n,INF);
        seg = LazySegTree<W>(n);
        seg.init(base);
    }
    int climb(int u, int k) const {
        while (u >= 0 && k > 0) {
            int h = head[u];
            int d = depth[u] - depth[h];
            if (k <= d) {
                return invPos[pos[u] - k];
            }
            k -= (d + 1);
            u = parent[h];
        }
        return u;
    }

    int lca(int a, int b) {
        while (head[a] != head[b]) {
            if (depth[head[a]] > depth[head[b]]) a = parent[head[a]];
            else b = parent[head[b]];
        }
        return depth[a] < depth[b] ? a : b;
    }
    template<class F>
    void processPath(int u, int v, F visitor) {
        while (head[u] != head[v]) {
            if (depth[head[u]] > depth[head[v]]) swap(u, v);
            int h = head[v];
            visitor(pos[h], pos[v]);
            v = parent[h];
        }
        if (depth[u] > depth[v]) swap(u, v);
        visitor(pos[u], pos[v]);
    }
    void updatePathSum(int u, int v, W val) {
        processPath(u, v, [&](int l, int r) { seg.update_add(l, r, val); });
    }
    void updatePathMul(int u, int v, W val) {
        processPath(u, v, [&](int l, int r) { seg.update_mul(l, r, val); });
    }
    void updatePathSet(int u, int v, W val) {
        processPath(u, v, [&](int l, int r) { seg.update_set(l, r, val); });
    }
    void updateSubtreeSum(int x, W val) {
        seg.update_add(pos[x], pos[x] + size[x] - 1, val);
    }
    void updateSubtreeMul(int x, W val) {
        seg.update_mul(pos[x], pos[x] + size[x] - 1, val);
    }
    void updateSubtreeSet(int x, W val) {
        seg.update_set(pos[x], pos[x] + size[x] - 1, val);
    }

    W queryPathSum(int u, int v) {
        W res = 0;
        processPath(u, v, [&](int l, int r) { res += seg.querySum(l, r); });
        return res;
    }
    W queryPathMin(int u, int v) {
        W res = numeric_limits<W>::max();
        processPath(u, v, [&](int l, int r) { res = min(res, seg.queryMin(l, r)); });
        return res;
    }
    W queryPathMax(int u, int v) {
        W res = numeric_limits<W>::lowest();
        processPath(u, v, [&](int l, int r) { res = max(res, seg.queryMax(l, r)); });
        return res;
    }
    W querySubtreeSum(int x) {
        return seg.querySum(pos[x], pos[x] + size[x] - 1);
    }
    W querySubtreeMin(int x) {
        return seg.queryMin(pos[x], pos[x] + size[x] - 1);
    }
    W querySubtreeMax(int x) {
        return seg.queryMax(pos[x], pos[x] + size[x] - 1);
    }

    int median(int a, int b, int c) {
        int ab = lca(a, b), ac = lca(a, c), bc = lca(b, c);
        if (depth[ab] < depth[ac]) swap(ab, ac);
        if (depth[ab] < depth[bc]) swap(ab, bc);
        return ab;
    }
};

vll solve(vpll& E, vall3& Q) {
    ll n = sz(E) + 1;
    HLD<ll> hld(n);
    rep(i,0,sz(E)) {
        auto [u,v] = E[i];
        hld.addEdge(u-1,v-1,0);
    }
    hld.build();
    sort(all(Q), [&](auto& a, auto& b) {
        return a[2] > b[2];
    });
    rep(i,0,sz(Q)) {
        auto [u,v,w] = Q[i];
        u -= 1, v -= 1;
        ll lca = hld.lca(u,v);
        if(hld.depth[u] > hld.depth[v]) swap(u,v);
        hld.updatePathSet(hld.climb(v, hld.depth[v] - hld.depth[lca] - 1), v, w);
        if(lca != u) {
            hld.updatePathSet(hld.climb(u, hld.depth[u] - hld.depth[lca] - 1), u, w);
        }
    }
    vll res;
    rep(i,0,sz(E)) {
        auto [u,v] = E[i];
        u -= 1, v -= 1;
        ll sub = hld.depth[u] > hld.depth[v] ? u : v;
        hld.processPath(sub,sub,[&](ll l, ll r) {
            ll x = hld.seg.queryMin(l,r);
            res.push_back(x == INF ? -1 : x);
        });
    }
    return res;
}

int main() {
    Code By Sumfi
    precision(10)
    ll tc = 1;
    //in(tc);
    rep(i,1,tc+1) {
        ll n,q;
        in(n,q);
        vpll E(n-1);
        vall3 Q(q);
        in(E);
        in(Q);
        printvln(solve(E,Q));
    }
    return 0;
}