나무들이 불타는 것을 봤을 때 해야 하는 말은?

나무들이 불타고 있는 것을 봤을 때 해야 하는 말은? 나무들이 불타는 것을 봤다면 119에 바로 신고를 해야죠. 무엇을 기대하셨나요. 반성하십시오. 잠깐, 설마 트리스타나 혹은 나무아미타불 같이 경솔한 생각을 하신 건 아니시겠죠?

2024년 여름 진행된 <제5회 고려대학교 MatKor Cup: 2024 Summer/Fall>에서 동우는 너무 많은 문제를 출제해 세팅에 어려움을 겪었다. 안 그래도 지난 4회 대회 에디토리얼도 밀려 있는데 세팅까지 쌓이게 된 동우가 안쓰러웠던 진한이는 옆에서 보다가 한 문제 세팅을 도와주기로 했다. 동우는 진한이가 트리 문제를 많이 풀어 보고 만들었으니 트리 문제를 잘 세팅하리라 생각했다. 그래서 나뭇가지가 다 사라지면? 문제의 지문을 작성하고 풀이와 함께 진한이에게 주었다.

진한이는 이 문제, 특히 제목에 충격을 받은 나머지 흑화해서, 정점에 가중치가 있는 또 다른 트리 문제를 종우에게 요청했다. 종우는 오랜 고민 끝에 이번 대회에 출제할 문제를 하나 만들었다.

종우는 진한이에게 $N$개의 정점과 각 정점별로 가중치가 있는 트리를 주었다. 이 트리는 진한이가 처음 받았을 때 $i$번 정점에 가중치 $i$가 있던 트리다. 진한이는 이제 종우의 요청에 따라 다음과 같은 쿼리를 처리해야 한다.

• $a$ $b$ $k$: 정점 $a$부터 정점 $b$까지의 경로 순서대로 가중치를 $a_0,a_1,\cdots ,a_{m-1}$라 하자. 각 가중치를 $a_{(0-k)\mod m},a_{(1-k)\mod m},\cdots ,a_{(m-1-k)\mod m}$로 고친다. 그다음 경로 위의 모든 가중치의 비트 XOR을 출력한다. 경로는 시작 정점과 끝 정점을 포함한다.

위와 같은 쿼리 $Q$개를 처리해 보자.

첫 번째 줄에 정점의 개수 $N(1\le N\le 10^6)$, 쿼리의 수 $Q(1\le Q\le 10^4)$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 간선을 이루는 서로 다른 두 정점 $u$, $v(1\le u,v\le N)$가 주어진다.

$N+1$번째 줄부터 $Q$개의 줄에 걸쳐 쿼리 $a$ $b$ $k(1\le a,b\le N$; $0\le k\le 10^6)$가 주어진다.

첫 번째 줄부터 $Q$개의 줄에 걸쳐 각 쿼리의 결과를 한 줄에 하나씩 출력한다.