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

OR đườ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

Trong một hệ thống định tuyến tín hiệu số, \(N\) bộ định tuyến được kết nối với nhau bởi \(N-1\) đường truyền. Mỗi đường truyền có một mặt nạ tín hiệu (là số nguyên dương). Khi một gói tin đi từ bộ định tuyến \(u\) đến \(v\), nó sẽ mang mặt nạ tổng hợp bằng phép OR (ký hiệu \(|\)) của tất cả các mặt nạ trên đường đi. Hãy tính mặt nạ tổng hợp cho mỗi đường truyền tin.

Yêu cầu: Cho \(N\) bộ định tuyến và \(N-1\) đường truyền. Trả lời \(Q\) truy vấn, mỗi truy vấn in ra giá trị OR 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ả OR của các cạnh trên đường đi.

Ví dụ:

Dữ liệu vào:

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

Kết quả:

7
3

Giải thích:

• Đường \(1 \to 2 \to 3\): \(3 \,|\, 5 = 7\).
• Đường \(2 \to 1\): \(3\).

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 |