#include <bits/stdc++.h>
#include "happy.h"
using namespace std;
vector<vector<pair<int, int>>> sus(10000);
int w[10000];
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) {
    int cans;
    bool open[10000];
    vector<int> ans;
    for(int i=0; i<N-1; i++) sus[u[i]].push_back({v[i], h[i]});
    dfs(0, 0, 0);
    for(int i=0; i<Q; i++) {
        if(t[i]==1) for(int j=l[i]; j<=r[i]; j++) open[j]=true;
        else for(int j=l[i]; j<=r[i]; j++) open[j]=false;
        cans=0;
        for(int j=0; j<N; j++) {
                if(open[j]==true) {
                        for(int k=j+1; k<N; k++) {
                                if(open[k]==true) {
                                        cans+=X(w[j], w[k]);
                                }
                        }
                }
        }
        v.push_back(cans);
    }
    return ans;
}
int X(int a, int b) {
    int cans=0, ex;
    for(int i=19; i>=0; i--) {
        int one=0;
        ex=exp2(i);
        if(ex<=a) {
            a-=ex;
            one++;
        }
        if(ex<=b) {
            b-=ex;
            one++;
        }
        if(one==1) cans+=ex;
    }
    return cans;
}
void dfs(int prev, int curr, int currw) {
    if(curr==0) w[curr]=0;
    else w[curr]=X(w[prev], currw);
    for(int i=0; i<sus[curr].size(); i++) dfs(curr, sus[curr][i].first, sus[curr][i].second);
}
