There is a tree, whose vertices are labeled by 1, 2, ¡, N. They are connected by N¨C1 edges. Each edge has a weight.For any two vertices u and v, f(u,v) is xor(exclusive-or) sum of weights of all edges on the path from u to v.There are Q queries,for each query,giving you a interval [l,r], you should calculate the number of pairs (u,v) such that f(u,v) > M ($l\leq u < v \leq r$) ¡£
Input
There are multiple test cases.
For each case contains 3 integers N, M and Q on a line.$(1\leq N , M , Q\leq 50000)$
Each of the next N - 1 lines contains three space separated integers a, b and c denoting an edge between a and b, whose weight is c.$(1\leq a, b\leq N,0\leq c\leq 50000)$
Each of the next Q lines contains two integers l and r.$(1\leq l\leq r\leq N)$
