Cho một cây gồm \(N\) đỉnh và \(N-1\) cạnh. Có \(Q\) truy vấn, mỗi truy vấn cho bởi bộ năm số \((x, y, a, b, k)\). Với mỗi truy vấn, hãy xác định xem có tồn tại đường đi từ \(a\) đến \(b\) qua đúng \(k\) cạnh hay không, nếu cây được nối thêm một cạnh nối giữa hai đỉnh \(x\) và \(y\). Lưu ý rằng đường đi có thể đi qua các đỉnh và các cạnh nhiều lần.

Input

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

Output

• Ghi ra \(Q\) dòng, mỗi dòng trả lời cho một truy vấn tương ứng: ghi \(1\) nếu tồn tại đường đi thỏa mãn, ngược lại ghi \(0\).

Example

5 5
1 2
2 3
3 4
4 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

1
1
0
1
0

Nguồn: CD DHBB 2020