Problem Description

There is a tree, whose vertices are labeled by 1, 2, …, N. They are connected by N–1 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)$

Output

For each query,output the answer in a line.

5 10 3
1 2 13
2 3 15
2 4 17
2 5 8
1 5
2 4
3 3

6
3
0