Cho một cây gồm ~N~ đỉnh, ~N-1~ cạnh. Có ~Q~ truy vấn, mỗi truy vấn cho dưới dạng ~(x, y, a, b, k)~ hỏi rằng có cách nào đi từ ~a~ đến ~b~ qua đúng ~k~ cạnh trên cây nếu cây được nối thêm cạnh ~(x,y)~.

Đường đi có thể qua các đỉnh, các cạnh nhiều lần.

Input

Vào từ file TREEQ.INP:

• Dòng đầu ghi số ~N, Q\ (3 \le N,Q \le 10^5)~ là số đỉnh của cây, số truy vấn.
• ~N-1~ dòng tiếp ghi bộ số ~u, v\ (1 \le u, v \le N)~ mô tả các cạnh của cây, cạnh nối hai đỉnh ~u~, ~v~.
• ~Q~ dòng tiếp theo ghi bộ số thể hiện truy vấn mô tả như trên.

Output

Ghi ra tệp TREEQ.OUT:

• Ghi ~Q~ số là kết quả của từng truy vấn, nếu tồn tại đường đi thỏa mãn thì ghi ~1~, ngược lại thì ghi ~0~.

Sample Input 1

5
1 2
2 3
3 4
4 5
5
1 3 1 2 2
1 4 1 3 2
1 4 1 3 3
4 2 3 3 9
5 2 3 3 9

Sample Output 1

1
1
0
1
0

Giải thích