#include <iostream>
#include <vector>

using namespace std;

long long int dfs(vector<vector<int>> conn, vector<int> u, vector<int> v, vector<int> h, vector<bool> visited, long long int res, int a, int b) {
    if (visited[a]) return -1;
    visited[a] = true;
    vector<int> children = conn[a];
    for (auto child : children) {
        int idx = (child < 0) ? u[-child] : v[child];
        long long int new_res = res;
        res ^= h[abs(child)];
        if (idx == b) return res;
        if (visited[idx]) {
            res = new_res; 
            continue;
        }
        res = dfs(conn, u, v, h, visited, res, idx, b);
        if (res < 0) res = new_res;
        else return res;
    }
    return -1;
}


vector<long long int> happy(int N, int Q,
    vector<int> u, vector<int> v, vector<int> h,
    vector<int> t, vector<int> l, vector<int> r) {
    vector<bool> status(N);
    vector<vector<int>> conn;
    vector<long long int> res(Q);
    vector<bool> visited(N);
    for (int i = 0; i<N; i++) {
        conn.push_back({});
    }
    for (int i = 0; i<N-1; i++) {
        conn[u[i]].push_back(i);
        conn[v[i]].push_back(-i);
    }
    for (int i = 0; i<Q;i++) {
        switch (t[i])
        {
            case 1:
                for (int j = l[i]; j<=r[i];j++) status[j] = true;
                break;
            case 2:
                for (int j = l[i]; j<=r[i];j++) status[j] = false;
                break;
            default:
                abort();
        }
        long long int sum = 0;
        for (int j = 0; j<N;j++) {
            if (!status[j]) continue;
            for (int a = j+1; a<N;a++) {
                if (!status[a]) continue;
                for (int b = 0; b < N; b++) {
                    visited[b] = false;
                }
                sum += dfs(conn, u, v, h, visited, 0, j, a);
            }
        }
        res[i] = sum;
    }
    return res;
}