Tý cần giải bài toán sau:

AND đường đi

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Hệ thống phân quyền bảo mật của công ty FPTOJ gồm \(N\) phòng ban được nối với nhau bởi \(N-1\) kênh liên lạc nội bộ. Mỗi kênh liên lạc có một mã quyền (là số nguyên dương). Để truyền một tài liệu mật từ phòng ban \(u\) đến \(v\), tài liệu phải hội tụ đủ tất cả các quyền trên đường đi, tức là phép AND (ký hiệu \(\&\)) của các mã quyền. Hãy tính mã quyền tổng hợp cho mỗi đường truyền tài liệu.

Yêu cầu: Cho \(N\) phòng ban và \(N-1\) kênh liên lạc. Trả lời \(Q\) truy vấn, mỗi truy vấn in ra giá trị AND của các cạnh trên đường đi từ \(u\) đến \(v\).

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương \(N\).
• \(N-1\) dòng tiếp theo, mỗi dòng gồm ba số \(u\), \(v\), \(w\).
• Dòng tiếp theo chứa số nguyên dương \(Q\).
• \(Q\) dòng sau, mỗi dòng gồm hai số \(u\), \(v\).

Kết quả:

• In ra \(Q\) dòng, mỗi dòng là kết quả AND của các cạnh trên đường đi.

Ví dụ:

Dữ liệu vào:

3
1 2 7
2 3 3
2
1 3
2 1

Kết quả:

3
7

Giải thích:

• Đường \(1 \to 2 \to 3\): \(7 \,\&\, 3 = 3\) (vì \(111_2 \,\&\, 011_2 = 011_2 = 3\)).
• Đường \(2 \to 1\): \(7\).

Giới hạn: | Subtask | \(N\) | \(Q\) | Điểm | |---------|-----|-----|------| | 1 | ≤ 100 | ≤ 100 | 5 | | 2 | ≤ 500 | ≤ 500 | 5 | | 3 | ≤ 2 000 | ≤ 2 000 | 10 | | 4 | ≤ 10 000 | ≤ 10 000 | 10 | | 5 | ≤ 50 000 | ≤ 50 000 | 15 | | 6 | ≤ 100 000 | ≤ 100 000 | 15 | | 7 | ≤ 100 000 | ≤ 100 000 | 20 | | 8 | ≤ 100 000 | ≤ 100 000 | 20 |