Under construction

Still being built. Things may change

Tree and K

Time limit3sMemory limit1024 MB

Summary
Given a weighted tree, answer each query with the XOR of all vertex numbers whose distance from vertex x is exactly d.
Level

Medium7 of 10

Topics
Tree, Divide and conquer, Hash map
Solved
No attempts yet

Problem

A tree with NN vertices is given. A tree is a connected graph with no undirected cycles. The vertices are numbered from 11 to NN, and each edge has a weight. Write a program that processes the following query.

  • xx dd: Output the XOR of all vertex numbers whose distance from vertex xx is exactly dd.

Input

The first line contains NN and MM, separated by a space. (1≤N,M≤200 000)(1 \leq N, M \leq 200\,000)

From the second line, the next N−1N-1 lines each contain two distinct vertex numbers uiu_i, viv_i connected by the ii-th edge and its weight wiw_i, separated by spaces. (1≤ui,vi≤N;(1 \leq u_i, v_i \leq N; ui≠vi;u_i \neq v_i; 1≤wi≤1 000 000 000)1 \leq w_i \leq 1\,000\,000\,000)

The input graph is guaranteed to be a tree.

The next MM lines each contain a query vertex number xix_i and a distance did_i, separated by a space, one query per line. (1≤xi≤N;(1 \leq x_i \leq N; 0≤di≤1015)0 \leq d_i \leq 10^{15})

Output

For each query, print the result on its own line, in the order the queries are given.

Examples2

  1. Example 1

    Input
    6 4
6 2 2
1 4 2
2 3 1
2 4 4
4 5 2
2 6
3 5
4 2
4 4
    Expected output
    4
4
4
2

  2. Example 2

    Input
    19 4
8 7 1
9 7 1
7 6 1
11 10 1
12 10 1
10 6 1
6 1 1
2 1 1
1 3 1
3 4 1
3 5 1
1 13 1
13 14 1
14 15 1
13 16 1
16 17 1
16 18 1
16 19 1
6 4
1 3
10 3
14 3
    Expected output
    31
25
13
23