Poinciana là một vương quốc rất đẹp được đặt tên theo loài hoa Phượng vỹ. Vương quốc này gồm có $n$ thành phố được chia thành $m$ loại. Các thành phố được đánh số từ $1$ đến $n$ với thành phố $1$ là thủ đô và $t_i(t_i\le m)$ là loại của thành phố thứ $i$. Hệ thống đường cao tốc của vương quốc này đảm bảo kết nối giữa thủ đô với các thành phố còn lại bằng $n-1$ tuyến đường một chiều hướng ra khỏi thủ đô. Sau nhiều năm rời khỏi vương quốc du học, công chúa MH của vương quốc đã trở lại và quyết định thực hiện một chuyến thị sát dọc các tuyến đường cao tốc. Hiện tại, có $q$ kế hoạch cho chuyến thị sát này, với kế hoạch thứ $k$ là một lộ trình xuất phát từ một thành phố loại $a_k$ và kết thúc ở thành phố loại $b_k$ và vì một số lý do, sẽ không đi qua thành phố loại $c_k$ nào. Với mỗi kế hoạch, hãy giúp MH biết có bao nhiêu lộ trình phù hợp để tham quan bằng các tuyến cao tốc nhé!

INPUT

• Dòng đầu tiên gồm 3 số nguyên dương $n,m,q$ số thành phố, số loại thành phố và số kế hoạch.
• $n$ dòng tiếp theo, dòng thứ $i$ miêu tả thông tin về thành phố thứ $i$.
• Dòng thứ nhất chứa 1 số $t_1$ là loại thành phố của thủ đô.
• Dòng thứ $i$ trong $n-1$ dòng còn lại gồm hai số $p_i,t_i$ thành phố có đường cao tốc dẫn đến $i$ và loại thành phố của $i$.
• Trong $q$ dòng còn lại, dòng thứ k gồm ba số $a_k,b_k,c_k(a_k,b_k,c_k\le m,a_k\ne b_k\ne c_k)$ mô tả kế hoạch tham quan thứ $k$.

OUTPUT

• Gồm $q$ dòng với dòng thứ $k$ là số lộ trình phù hợp cho kế hoạch tham quan thứ $k$, hai lộ trình từ $u_1$ đến $v_1$ và từ $u_2$ đến $v_2$ được gọi là khác nhau khi $u_1\ne u_2$ hoặc $v_1\ne v_2$

Sample Input

12 3 5
1
1 1
1 2
3 3
4 1
4 2
6 3
6 1
8 1
2 3
10 1
11 3
1 3 2
1 2 3
2 1 3
3 1 2
2 3 1

Sample Output

5
1
2
2
3

Subtask

• Subtask 1: $n\le {10}^3,m\le 100,q=1$ (20p)
• Subtask 2: $n\le {10}^5,m\le {10}^4,q\le 100$ (20p)
• Subtask 3: $n\le {10}^5,m\le {10}^4,q\le {10}^4$ và $b_k=b_{k-1}$ với mọi $k>1$ (20p)
• BONUS:
• Subtask thử thách: $n\le {10}^5,m\le {10}^4,q\le {10}^4$ và số thành phố thuộc mỗi loại thành phố $\le 100$(prize for first AC )
• Subtask: $n\le {10}^5,m\le {10}^4,q\le {10}^4$.