Trang trại nuôi trồng thủy sản ở đại dương bao gồm \(n\) trạm đánh số từ \(1\) đến \(n\). Trạm 1 là mô đun chế biến và điều hành chung. Đây là trạm duy nhất nổi trên mặt nước. Các trạm còn lại đều ở dưới mặt nước. Trừ trạm \(1\), mỗi trạm trong số các trạm còn lại được neo với một trạm trên nó, gần mặt nước hơn. Độ dài các dây neo nối 2 trạm là như nhau, vì vậy các trạm neo với trạm 1 đều ở độ sâu d so với mặt nước, các trạm neo với trạm ở độ sâu \(d\) sẽ nằm ở độ sâu \(2d,\ldots\) Từ nhật ký bảo dưỡng dây neo người ta biết được các cặp trạm có dây neo nối với nhau.

Phần lớn các công việc do rô bốt đảm nhiệm, nhưng cũng có những việc phải thợ lặn trực tiếp thực hiện. Để đi từ trạm này sang trạm khác người thợ lặn phải bám theo các dây neo để khỏi mất phương hướng. Thời gian đi từ một trạm tới trạm kế tiếp là 1 đơn vị, không phụ thuộc vào việc nổi lên hay lặn xuống. Cứ đi lên hoặc đi xuống \(p\) khoảng cách giữa các trạm người thợ lặn cần ghé vào trạm nghỉ một khoảng thời gian \(t\) để thích nghi với việc thay đổi độ sâu. Ngoài ra, khi đang đi lên mà phải chuyển sang lặn xuống cũng phải nghỉ một khoảng thời gian \(t\).

Có \(m\) nhóm thợ. Nhóm thợ thứ \(i\) sau khi hoàn thành xong công việc duy tu bảo dưỡng bên ngoài trạm \(a_i\) nhận được yêu cầu chuyển sang làm các công việc tương tự ở trạm \(b_i\).

Yêu cầu: Cho số nguyên \(n, p, t, a_i, b_i (i=1\div m)\) và \(n-1\) cặp giá trị khác nhau từng đôi một \(u_i, v_i\) cặp dây nối trực tiếp 2 trạm \(u_i\) và \(v_i\) (\(1 \leq u_i, v_i, a, b \leq n, a\neq b, u_i \neq v_i, i = 1 \div n-1\)). Hãy xác định thời gian ít nhất chuyển từ \(a_i\) tới \(b_i\) (\(i = 1 \div m\)).

Input

• Dòng đầu tiên chứa \(5\) số nguyên \(n, p, t(2 \leq n \leq 10^5, 1 \leq p \leq n, 1 \leq t \leq 10^6)\).
• Dòng thứ \(i\) trong \(n-1\) dòng sau chứa 2 số nguyên \(u_i\) và \(v_i\).
• Dòng tiếp theo ghi số nguyên dương \(m\) (\(1 \leq m \leq 10^5\)).
• \(m\) dòng cuối cùng, dòng thứ \(i\) chứa hai số nguyên \(a_i, b_i\).

Output

• \(m\) số nguyên - thời gian ít nhất chuyển từ \(a_i\) tới \(b_i\) \((i = 1 \div m)\).

14 2 1
11 8
8 13
7 8
7 4
4 1
2 1
1 6
2 3
2 5
12 10
14 10
6 9
3 10
1
8 10

9