Cho đồ thị cây gồm \(n\) đỉnh đánh số từ 1 tới \(n\), có \(n - 1\) cạnh kết nối các đỉnh của đồ thị. Mỗi cạnh được gán một chữ số nhất định.

Cho trước số nguyên dương mod. Có \(q\) câu hỏi, mỗi câu hỏi có dạng với hai đỉnh \(u, v\) cho trước, các chữ số trên các cạnh của đường đi đơn từ \(u\) tới \(v\) ghép lại thành một số nguyên. Bạn cần tính phần dư của số nguyên đó khi chia cho mod.

Lưu ý: Đường đi đơn là đường đi không đi qua đỉnh nào nhiều hơn 1 lần.

Dữ liệu vào:

• Dòng đầu chứa 2 số nguyên \(n, \text{mod}\) (\(2 \leq n \leq 10^5\); \(1 \leq \text{mod} \leq 10^9 + 7\));
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(u, v, w\) (\(1 \leq u, v \leq n\); \(0 \leq w \leq 9\)) mô tả một cạnh nối hai đỉnh \(u, v\) và trên cạnh này có gán chữ số \(w\);
• Dòng tiếp theo có chứa số nguyên \(q\) (\(1 \leq q \leq 10^5\));
• \(q\) dòng tiếp theo, dòng thứ \(i\) (\(1 \leq i \leq q\)) trong \(q\) dòng này chứa 2 số nguyên \(u_i, v_i\) (\(1 \leq u_i, v_i \leq n\)) mô tả câu hỏi thứ \(i\).

Dữ liệu ra:

• Đưa ra \(q\) dòng, dòng thứ \(i\) (\(1 \leq i \leq q\)) chứa 1 số nguyên là đáp số cho câu hỏi thứ \(i\).

Ràng buộc

• Ràng buộc 1: ứng với 40% số điểm có \(2 \le n,q \le 1000\);
• Ràng buộc 2: ứng với 40% số điểm: với mọi truy vấn u → v thì đỉnh v luôn thuộc đường đi từ u tới đỉnh 1;
• Ràng buộc 3: ứng với 20% số điểm không giới hạn gì thêm.

Input 1

5 1000000000
1 2 6
2 3 5
2 5 0
1 4 9
3
3 4
5 4
4 1

Output 1

569
69
9