Khu phố của Dracula và Vampire chuẩn bị mở một bữa tiệc Halloween trái mùa. Khu phố có góc nhìn dưới dạng một đơn đồ thị vô hướng, liên thông gồm ~N~ đỉnh (mỗi đỉnh tương ứng với ngôi nhà) và ~M~ cạnh (mỗi cạnh tương ứng với đường đi trực tiếp giữa hai ngôi nhà). Các đỉnh được đánh số từ ~1~ đến ~N~, các cạnh được đánh số từ ~1~ đến ~M~. Cạnh thứ ~i~ có độ dài là ~i~ nối hai đỉnh ~A_i~ và ~B_i~.

Đến ngày tổ chức tiệc, Dracula và Vampire sẽ ghé thăm và tặng quà ở các ngôi nhà xung quanh:

• Ban đầu, Dracula xuất phát ở ngôi nhà thứ ~X~ và Vampire xuất phát ở ngôi nhà thứ ~Y~.
• Cả hai tiến hành ghé thăm khu phố cho đến khi thăm được tổng cộng ít nhất ~Z~ ngôi nhà (bao gồm cả ngôi nhà xuất phát), mỗi ngôi nhà có thể ghé thăm nhiều lần và chỉ được tính tối đa ~1~ lần.
• Chi phí thăm khu phố được xác định bằng giá trị độ dài đường đi lớn nhất trong số các đường đi đã đi qua.

Bạn hãy giúp Dracula và Vampire tối thiểu hóa chi phí thăm khu phố, trả lời trong ~Q~ truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~3 \le N \le 10^5~, ~N-1 \le M \le 10^5~).
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~A_i~ và ~B_i~ (~1 \le A_i,B_i \le N~).
• Dòng tiếp theo chứa số nguyên ~Q~ (~1 \le Q \le 10^5~).
• ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~X_i, Y_i~ và ~Z_i~ (~1 \le X_i<Y_i \le N~, ~3 \le Z_i \le N~).
• Dữ liệu đảm bảo đồ thị được cho là đơn đồ thị liên thông.

Output

• In ra ~Q~ dòng, dòng thứ ~i~ in ra số nguyên là chi phí tối thiểu để thăm khu phố tương ứng với truy vấn thứ ~i~.

Examples

Input

5 6
2 3
4 5
1 2
1 3
1 4
1 5
6
2 4 3
2 4 4
2 4 5
1 3 3
1 3 4
1 3 5

Output

1
2
3
1
5
5

Scoring

• Subtask ~1~ với ~11\%~ số điểm: ~N,M,Q \le 10~
• Subtask ~2~ với ~30\%~ số điểm: ~N,M,Q \le 1000~
• Subtask ~3~ với ~59\%~ số điểm: ~N,M,Q \le 10^5~

Notes

Ở ví dụ, khu phố được mô tả trong hình sau:

• Truy vấn thứ nhất, Dracula xuất phát từ ngôi nhà số ~2~, đến thăm ngôi nhà số ~3~, Vampire xuất phát từ ngôi nhà số ~4~, không cần đi thăm các ngôi nhà khác. Các ngôi nhà đã thăm của cả hai là ~\{2, 3, 4\}~.
• Truy vấn thứ hai, Dracula xuất phát từ ngôi nhà số ~2~, đến thăm ngôi nhà số ~3~, Vampire xuất phát từ ngôi nhà số ~4~, đến thăm ngôi nhà số ~5~. Các ngôi nhà đã thăm của cả hai là ~\{2, 3, 4, 5\}~.
• Truy vấn thứ ba, Dracula xuất phát từ ngôi nhà số ~2~, đến thăm ngôi nhà số ~3~, quay về ngôi nhà số ~2~, sau đó thăm ngôi nhà số ~1~, Vampire xuất phát từ ngôi nhà số ~4~, đến thăm ngôi nhà số ~5~. Các ngôi nhà đã thăm của cả hai là ~\{2, 3, 1, 4, 5\}~.
• Truy vấn thứ tư, Dracula xuất phát từ ngôi nhà số ~1~, không cần đi thăm các ngôi nhà khác, Vampire xuất phát từ ngôi nhà số ~3~, đến thăm ngôi nhà số ~2~. Các ngôi nhà đã thăm của cả hai là ~\{1, 3, 2\}~.
• Truy vấn thứ năm, Dracula xuất phát từ ngôi nhà số ~1~, đến thăm ngôi nhà số ~4~, sau đó thăm ngôi nhà số ~5~, Vampire xuất phát từ ngôi nhà số ~3~, đến thăm ngôi nhà số ~2~. Các ngôi nhà đã thăm của cả hai là ~\{1, 4, 5, 3, 2\}~.
• Truy vấn thứ sáu được thực hiện tương tự như truy vấn thứ năm.