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

using namespace std;

typedef long long ll;

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];
vector<int> aib[20];

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);
            }
        }
    }
    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);
        for(int b = 0; b < 20; ++b) {
            int nl = lower_bound(lst[b].begin(), lst[b].end(), l) - lst[b].begin();
            int nr = upper_bound(lst[b].begin(), lst[b].end(), r) - 1 - lst[b].begin();
            cbit[b] += (t == 1 ? 1 : -1) * max(nr - nl + 1, 0);
            sum += (1LL << b) * cbit[b] * (total - cbit[b]);
        }
        ans.push_back(sum);
    }
    return ans;
}
