Giai đoạn tiếp theo trong nghiên cứu, hệ thống AI cần được tiếp tục được đào tạo cho phép xử lý và phân tích thông tin trong mạng lưới dữ liệu khổng lồ. Để đảm bảo hiệu quả cao nhất trong việc truyền thông tin giữa các trạm dữ liệu, hệ thống cần tìm ra những con đường tối ưu, có băng thông và bước truyền phù hợp.

Mạng lưới này có ~N~ nút, kết nối với nhau theo cấu trúc cây, nơi mỗi nút đại diện là một trạm dữ liệu và mỗi cạnh biểu thị một kênh truyền thông. Mỗi trạm dữ liệu có một giới hạn băng thông nhất định (được biểu diễn bằng trọng số). Do nhu cầu phân tích dữ liệu, hệ thống AI phải thực hiện ~Q~ truy vấn để tìm ra số lượng đường đi tối ưu giữa hai trạm, thỏa mãn các tiêu chí sau:

• Đường đi bắt đầu từ trạm ~S~ và kết thúc tại trạm ~T~.
• Độ dài đường đi chính xác bằng ~L~ kênh truyền.
• Tổng băng thông tiêu thụ trên đường đi không vượt quá ~W~.

Nhiệm vụ của bạn là thiết kế một thuật toán AI hiệu quả để giúp hệ thống nhanh chóng tìm ra số lượng đường đi đặc biệt thỏa mãn tất cả các điều kiện.

Input

• Dòng 1: Hai số nguyên ~N~ và ~Q~ (~1 \le N, Q \le 10^5~) – số trạm dữ liệu và số truy vấn.
• Dòng 2: ~N~ số nguyên (~1 \le W_i \le 10^6~) – băng thông của từng trạm dữ liệu.
• ~N-1~ dòng tiếp theo: Mỗi dòng chứa hai số nguyên ~U, V~ (~1 \le U, V \le N, U \ne V~), biểu thị một kênh truyền dữ liệu giữa hai trạm.
• ~Q~ dòng tiếp theo: Mỗi dòng chứa bốn số nguyên ~S, T, L, W~ (~1 \le S, T \le N, 0 \le L \le N-1, 1 \le W \le 10^6~), yêu cầu AI tìm số lượng đường đi đặc biệt giữa ~S~ và ~T~.

Output

• Ghi kết quả ra ~Q~ dòng, mỗi dòng chứa một số nguyên là số lượng đường đi đặc biệt từ ~S~ đến ~T~ thỏa mãn các điều kiện của truy vấn thứ ~i~ (đánh số từ 1 đến ~Q~).