#include "happy.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Data {
    int cnt[21], lazy;
};

const int NMAX = 300000;
int n, q;
vector<pair<int, int>> adj[NMAX + 5];
int val[NMAX + 5];
int cbit[20];
vector<int> lst[20];
int ps[NMAX + 5][21];
vector<int> aib[20];
Data aint[4 * NMAX + 5];

void combine(Data &r, const Data &a, const Data &b) {
    for(int i=0; i<21; ++i) {
        r.cnt[i] = a.cnt[i] + b.cnt[i];
    }
}

void apply(Data &r, int lazy, int st, int dr) {
    r.lazy = lazy;
    if(lazy == -1) {
        memset(r.cnt, 0, 21 * sizeof(int));
    } else {
        for(int i=0; i<21; ++i) {
            r.cnt[i] = ps[dr][i] - ps[st-1][i];
        }
    }
}

void propag(int pos, int st, int dr) {
    if(aint[pos].lazy != 0) {
        int mij = (st + dr >> 1);
        apply(aint[pos << 1], aint[pos].lazy, st, mij);
        apply(aint[pos << 1 | 1], aint[pos].lazy, mij + 1, dr);
        aint[pos].lazy = 0;
    }
}

void updateAINT(int st, int dr, int pos, int l, int r, int x) {
    if(l <= st && dr <= r) {
        apply(aint[pos], x, st, dr);
    } else {
        propag(pos, st, dr);
        int mij = (st + dr >> 1);
        if(l <= mij) {
            updateAINT(st, mij, pos << 1, l, r, x);
        }
        if(r > mij) {
            updateAINT(mij + 1, dr, pos << 1 | 1, l, r, x);
        }
        combine(aint[pos], aint[pos << 1], aint[pos << 1 | 1]);
    }
}

void updateAIB(int p, int x, vector<int> &aib) {
    ++p;
    for(; p <= n; p += (p & -p)) {
        aib[p - 1] += x;
    }
}

int queryAIB(int p, const vector<int> &aib) {
    ++p;
    int r = 0;
    for(; p; p ^= (p & -p)) {
        r += aib[p - 1];
    }
    return r;
}

void dfs(int u, int par, int x) {
    val[u] = x;
    for(auto [v, cost] : adj[u]) {
        if(v != par) {
            dfs(v, u, x ^ cost);
        }
    }
}

vector<ll> happy(int N, int Q, vector<int> u, vector<int> v, vector<int> h, vector<int> T, vector<int> L, vector<int> R) {
    n = N; q = Q;
    for(int i=0; i<n-1; ++i) {
        adj[u[i]].emplace_back(v[i], h[i]);
        adj[v[i]].emplace_back(u[i], h[i]);
    }
    dfs(0, -1, 0);
    for(int b = 0; b < 20; ++b) {
        lst[b].push_back(-1);
        for(int i=0; i<n; ++i) {
            if(val[i] & (1 << b)) {
                lst[b].push_back(i);
            }
            ps[i+1][b] = ps[i][b] + ((val[i] >> b) & 1);
        }
    }
    for(int i=1; i<=n; ++i) {
        ps[i][20] = ps[i-1][20] + 1;
    }
    vector<ll> ans;
    int total = 0;
    for(int i=0; i<q; ++i) {
        int l = L[i], r = R[i], t = T[i];
        ll sum = 0;
//        total += (t == 1 ? 1 : -1) * max(r - l + 1, 0);
        updateAINT(1, n, 1, l + 1, r + 1, (t == 1 ? 1 : -1));
        total = aint[1].cnt[20];
        for(int i=0; i<20; ++i) {
            cbit[i] = aint[1].cnt[i];
//            cout << i << ' ' << cbit[i] << endl;
        }
        for(int b = 0; b < 20; ++b) {
            sum += (1LL << b) * cbit[b] * (total - cbit[b]);
        }
        ans.push_back(sum);
    }
    return ans;
}
