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 \leq 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 \leq m,a_k \neq b_k \neq 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 \neq u_2~ hoặc ~v_1 \neq 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 \leq 10^3,m \leq 100, q = 1~ (20p)
• Subtask 2: ~n \leq 10^5,m \leq 10^4, q \leq 100~ (20p)
• Subtask 3: ~n \leq 10^5, m \leq 10^4, q\leq 10^4~ và ~b_k = b_{k-1}~ với mọi ~k>1~ (20p)
• BONUS:
• Subtask thử thách: ~n \leq 10^5,m \leq 10^4, q\leq 10^4~ và số thành phố thuộc mỗi loại thành phố ~\leq 100~(prize for first AC )
• Subtask: ~n \leq 10^5,m \leq 10^4, q\leq 10^4~.