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,\ mod\ \left( 2 \leq n \leq 100000;1 \leq mod \leq 10^{9} + 7 \right)\);

• \(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 100000)\);

• \(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}\ \left( 1 \leq u_{i},\ v_{i} \leq n \right)\) mô tả câu hỏi thứ \(i\).

Kết quả:

+ Đư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\).

Ví dụ:

Ràng buộc:

• Ràng buộc 1: ứng với 40% số điểm có \(2 \leq n,q \leq 1000;\)

• Ràng buộc 2: ứng với 40% số điểm: với mọi truy vấn \(u \rightarrow 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.