#include "happy.h"
using namespace std;

void dfs(vector<pair<int, int>> graph[], bool visited[], int N, int x, int y, long long int& XOR, bool& ready)
{
    if(x==y){
        ready=true;
        return;
    }
    visited[x]=true;
    for(int i=0;i<graph[x].size();i++){
        if(!visited[graph[x][i].first]){
            long long int XOR1=XOR;
            XOR=XOR ^ graph[x][i].second;
            dfs(graph, visited, N, graph[x][i].first, y, XOR, ready);
            if(ready){
                return;
            }
            XOR=XOR1;
        }
    }
    return;
}

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<long long int> sum;
    bool open[N]={false};
    vector<pair<int, int>> graph[N];
    vector<int> opens;
    for(int i=0;i<N;i++){
        graph[u[i]].push_back({v[i], h[i]});
        graph[v[i]].push_back({u[i], h[i]});
    }

    for(int i=0;i<Q;i++){
        opens.clear();
        for(int j=l[i];j<=r[i];j++){
            if(t[i]==1){
                open[j]=true;
            }
            else{
                open[j]=false;
            }
        }
        for(int j=0;j<N;j++){
            if(open[j]){
                opens.push_back(j);
            }
        }
        for(int j=0;j<opens.size()-1;j++){
            bool visited[N]={false};
            long long int XOR=opens[j];
            bool ready=false;
            dfs(graph, visited, N, opens[j], opens[j+1], XOR, ready);
            sum.push_back(XOR);
        }
    }
    return sum;
}
