Trên một vùng biển có ~N~ hòn đảo, được đánh số từ 1 đến ~N~. Các hòn đảo được nối với nhau bởi ~N - 1~ con đường trên biển (gọi là đường thủy), tạo thành một mạng lưới mà từ bất kỳ hòn đảo nào cũng có thể đi đến hòn đảo khác. Mỗi đường thủy nối giữa hai hòn đảo ~u~ và ~v~ có hai chi phí: chi phí ~c~ khi đi từ ~u~ đến ~v~, và chi phí ~d~ khi đi từ ~v~ đến ~u~. Chi phí bảo trì của một con đường là ~c + d~.

Mỗi hòn đảo ~i~ có một giá trị ~a[i]~, biểu thị số lượng kho báu trên hòn đảo đó. Các thủy thủ muốn thực hiện hai nhiệm vụ trong ~Q~ ngày:

1. Nhiệm vụ 1: Với mỗi cặp hòn đảo ~u~ và ~v~, tính tổng chi phí bảo trì của tất cả các con đường không nằm trên đường đi ngắn nhất từ hòn đảo ~u~ đến hòn đảo ~v~.
2. Nhiệm vụ 2: Khi đi từ ~u~ đến ~v~, các thủy thủ có thể dừng lại tại một số hòn đảo trên đường đi để thu thập kho báu. Tuy nhiên, tổng chi phí bảo trì của các con đường trên đường đi từ ~u~ đến ~v~ (tính bằng ~c + d~) không được vượt quá một ngưỡng ~K~. Hãy tính tổng giá trị kho báu lớn nhất có thể thu thập được, biết rằng họ có thể chọn thu hoặc không thu kho báu tại mỗi hòn đảo trên đường đi.

Yêu cầu: Với mỗi ngày, hãy trả lời cả hai nhiệm vụ trên cho cặp hòn đảo ~(u, v)~.

Input

• Dòng 1: Chứa hai số nguyên ~N~ và ~K~ (~1 \le N \le 2 \times 10^5~, ~1 \le K \le 10^9~), lần lượt là số hòn đảo và ngưỡng chi phí bảo trì.
• Dòng 2: Chứa ~N~ số nguyên ~a[1], a[2], \dots, a[N]~ (~0 \le a[i] \le 10^4~), là giá trị kho báu trên mỗi hòn đảo.
• ~N - 1~ dòng tiếp theo: Mỗi dòng chứa 4 số nguyên ~u, v, c, d~ (~1 \le u, v \le N~, ~1 \le c, d \le 10^4~), mô tả một con đường thủy giữa hòn đảo ~u~ và hòn đảo ~v~.
• Dòng tiếp theo: Chứa số nguyên ~Q~ (~1 \le Q \le 2 \times 10^5~), là số ngày cần thực hiện nhiệm vụ.
• ~Q~ dòng tiếp theo: Mỗi dòng chứa 2 số nguyên ~u, v~ (~1 \le u, v \le N~), là cặp hòn đảo mà các thủy thủ chọn trong ngày đó.

Output

• Ghi ra ~Q~ dòng, mỗi dòng chứa 2 số nguyên cách nhau bởi một khoảng trắng:
  • Số thứ nhất: Tổng chi phí bảo trì của các con đường không nằm trên đường đi ngắn nhất từ hòn đảo ~u~ đến hòn đảo ~v~.
  • Số thứ hai: Tổng giá trị kho báu lớn nhất có thể thu thập được trên đường đi từ ~u~ đến ~v~, với ràng buộc tổng chi phí bảo trì trên đường đi không vượt quá ~K~.

Sample Input 1

5 50
10 20 30 40 50
1 2 10 10
2 5 25 3
3 5 15 3
4 2 15 12
2
2 5
1 5

Sample Output 1

65 70
45 60