Sau khi tìm được đường đi ngắn nhất tới nhà cô "bạn gái cũ", shiba đã quyết định sẽ cùng cô ấy đi du lịch khắp đất nước để tìm cảm giác mới mẻ cũng như hàn gắn tình cảm. Chuyến du lịch ấy liệu có thành công mĩ mãn, hay sẽ đầy những trắc trở trông gai...

Sau khi hẹn được cô bạn gái đi chơi du lịch dài ngày, shiba quyết định sẽ đi du lịch bằng xe máy và chở cô ấy đi, tất nhiên là sẽ tiện hơn đi taxi vì cậu ấy có thể dừng lại có bất cứ đâu cậu ấy muốn để ngắm cảnh, mà lúc đi xe được cô ấy ôm thì lại còn gì tuyệt vời bằng, đúng không nhỉ :3.

Có thể coi đất nước nơi shiba sống là một đồ thị vô hướng có trọng số. Đất nước nơi shiba đang sống rất rộng lớn và được chia làm \(n\) thành phố. Có tất cả \(m\) đường nối giữa các thành phố với nhau, trong đó giữa hai thành phố có thể có nhiều hơn một đường nối và tồn tại đường đi từ một thành phố tới chính nó. Mỗi đường nối sẽ nối thành phố \(u_i\) và \(v_i\) với nhau và có trọng số bằng \(c_i\).

shiba thắc mắc, nếu như hôm nay mình chọn xe có mức đốt năng lượng là \(g\), thì cậu ấy có thể di chuyển được giữa bao nhiêu cặp thành phố khác nhau với nhau. Biết rằng trọng số của một đường đi là trọng số của cạnh lớn nhất trên đường đi đó. Để di chuyển được trên một đường đi, chiếc xe của shiba cần có mức đốt năng lượng lớn hơn hoặc bằng trọng số của đường đi đó.

Do đang bận soạn đồ, shiba không tính được điều này, thế nên vấn đề này được gửi tới _minhduc và hội bạn của cậu ấy - những Quân Sư uy tín. Do cũng đang mải bận tư vấn tình cảm, _minhduc quyết định sẽ đưa bài tập này lên LQDOJ Contest #6, các bạn hãy thử sức nhé.

Đang kích 4 Quân Sư rồi, sao bạn không thử để có thể kích 5 Quân Sư, tăng độ tự tin cho shiba nhỉ :Đ

Yêu cầu: Với mỗi truy vấn là một lần chọn xe, hãy đưa ra số lượng đường đi thoả mãn.

Input

• Dòng đầu tiên chứa một số nguyên \(\phi\) - số thứ tự của subtask chứa test đó.
• Dòng thứ hai chứa hai số nguyên \(n,m\) (\(1 \le n \le 3 \times 10^5, 1 \le m \le 5 \times 10^5\)).
• \(m\) dòng tiếp theo chứa ba số nguyên \(u_i,v_i,c_i\) (\(1 \le u_i, v_i \le n, 1 \le c_i \le 10^5\)).
• Dòng tiếp theo chứa một số nguyên dương \(q\) - số lượng truy vấn (\(1\le q \le 3 \times 10^5\)).
• Dòng cuối cùng chứa \(q\) số nguyên, lần lượt là các truy vấn (\(1 \le g \le 10^9\)).

Output

• In ra gồm \(q\) dòng, mỗi dòng chứa một số nguyên, là kết quả của truy vấn.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 100, q \le 100, m = n-1\).
• Subtask \(2\) (\(15\%\) số điểm): \(n \le 100, q \le 100\).
• Subtask \(3\) (\(10\%\) số điểm): \(m = n-1\), cạnh thứ \(i\) nối hai thành phố \(i\) và \(i+1\).
• Subtask \(4\) (\(10\%\) số điểm): \(m = n-1\), mỗi thành phố có tối đa \(2\) con đường nối tới nó.
• Subtask \(5\) (\(15\%\) số điểm): \(n \le 10^3\).
• Subtask \(6\) (\(15\%\) số điểm): \(m = n-1\).
• Subtask \(7\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

1
3 2
2 3 1
1 3 2
7
1 4 1 2 1 1 3

1
3
1
3
1
1
3