Người dân đang cảm thấy không hài lòng về hệ thống đèn tín hiệu giao thông ở thành phố Omega. Họ than phiền rằng thời gian chờ đèn đỏ khi đi lại giữa các địa điểm trong thành phố là quá dài. Trước khi quyết định thay đổi hệ thống đèn giao thông, thị trưởng thành phố là ngài PVH muốn kiểm chứng lại phản ánh này của người dân.

Thành phố Omega có ~N~ địa điểm, được nối với nhau bởi ~N - 1~ con đường hai chiều. Mỗi con đường nối giữa hai địa điểm khác nhau. Hệ thống các con đường đảm bảo với mọi cặp địa điểm ~(u, v)~ thỏa mãn ~1 \le u, v \le N~ và ~u \neq v~, luôn có một và chỉ một đường đi từ địa điểm ~u~ đến địa điểm ~v~ thông qua một hoặc nhiều con đường. Trên mỗi con đường có một cột đèn giao thông. Chu kỳ đèn của mọi cột đèn là ~K~ giây. Cột đèn giao thông trên con đường thứ ~i~ trong số ~N-1~ con đường sẽ bật đèn xanh trong ~g_i~ giây, bắt đầu từ thời điểm 0, sau đó chuyển sang bật đèn đỏ trong ~K - g_i~ giây, rồi lại chuyển sang bật đèn xanh trong ~g_i~ giây, sau đó chuyển sang bật đèn đỏ trong ~K - g_i~ giây,... cứ thế tiếp tục quá trình này mãi mãi. Khi đèn đang đỏ trên con đường nối hai địa điểm ~u~ và ~v~, các phương tiện không được phép xuất phát từ ~u~ để sang ~v~ hoặc xuất phát từ ~v~ để sang ~u~, mà phải chờ cho đến khi đèn xanh bật lên mới được di chuyển (các phương tiện đang ở giữa con đường nối ~u~ và ~v~ thì vẫn được tiếp tục di chuyển). Còn khi đèn đang xanh thì các phương tiện có thể thoải mái di chuyển trên con đường nối ~u~ và ~v~. Con đường thứ ~i~ trong số ~N-1~ con đường có độ dài ~c_i~, là số giây cần để một phương tiện đi hết con đường đó (ta giả sử mọi phương tiện ở thành phố Omega di chuyển với cùng tốc độ).

Cho biết hệ thống đường xá và đèn giao thông ở thành phố Omega, đồng thời cho ~Q~ truy vấn, truy vấn thứ ~i~ gồm hai địa điểm ~x_i~ và ~y_i~. Với mỗi truy vấn, hãy giúp ngài PVH tính số giây cần để đi từ ~x_i~ đến ~y_i~, giả sử rằng người lái xe bắt đầu hành trình ở thời điểm 0.

Input

• Dòng đầu chứa ba số nguyên ~N, Q, K~ (~1 \le N, Q \le 50000, 2 \le K \le 6~).
• Dòng thứ ~i~ trong số ~N-1~ dòng tiếp theo gồm ba số nguyên ~p_i, g_i, c_i~ (~1 \le p_i \le i, 1 \le g_i \le K, 1 \le c_i \le 10000~), biểu thị có một con đường nối giữa địa điểm ~p_i~ và địa điểm ~(i + 1)~, với số giây đèn xanh trong chu kỳ là ~g_i~ và độ dài con đường là ~c_i~.
• ~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x_i~ và ~y_i~ (~1 \le x_i, y_i \le N~).

Output

Với mỗi truy vấn in ra một số nguyên trên một dòng là số giây cần để đi từ ~x_i~ đến ~y_i~, giả sử rằng người lái xe bắt đầu hành trình ở thời điểm 0.