Trong một buổi học về quản lý đô thị, lớp bạn An được thầy cho một bản quy hoạch giả tưởng về đường cao tốc của một quốc gia có \(n\) tỉnh thành được đánh số từ \(1\) tới \(n\) và \(n-1\) đường cao tốc, trong đó đường cao tốc thứ \(i\) kết nối hai chiều giữa hai tỉnh \(u_i\) và \(v_i\). Giữa hai tỉnh bất kỳ luôn được kết nối liên thông với nhau thông qua các đường cao tốc này. Các đường cao tốc này là tuyến huyết mạch quan trọng của cả đất nước, nên được xây vô cùng kiên cố và hoàn toàn không thể bị phá hủy bởi thiên tai.

Đất nước giả tưởng này cũng thường xuyên gặp động đất, vì vậy họ đã tạo ra một phương pháp đo lượng độ rung chấn, với thang đo có giá trị từ \(1\) tới \(10^9\). Ngoài ra, giả sử rằng khi có động đất, độ rung chấn ở mọi điểm trên mặt đất của toàn lãnh thổ là như nhau.

Để thuận tiện cho việc giao thông và giao thương giữa các tỉnh với nhau, giúp tăng sức bật cho nền kinh tế, Chính phủ giả tưởng quyết định xây thêm \(m\) đường cao tốc hai chiều nữa, trong đó đường thứ \(j\) kết nối tỉnh \(u_j\) với tỉnh \(v_j\). Các tuyến đường phụ này có sức chịu tải kém hơn, nên khả năng chịu đựng rung chấn cũng kém hơn: con đường thứ \(j\) sẽ chịu được độ rung chấn tối đa là \(w_j\).

Khi quản trị rủi ro, chúng ta luôn phải tính tới nhiều phương án dự phòng khác nhau. Ví dụ, việc xây những tuyến đường huyết mạch cực kỳ kiên cố khiến cho động đất dù phá hủy đi \(k\) trong số \(m\) tuyến đường cao tốc phụ, thì \(n-1\) tuyến đường huyết mạch vẫn có khả năng kết nối giao thông của toàn quốc, và \(m-k\) tuyến đường còn lại sẽ chịu tải một phần cho những tuyến đường gốc này. Thêm nữa, \((n-1)+(m-k)\) con đường còn lại tuy là không bị chặn, nhưng mà động đất khiến những con đường dễ bị nứt vỡ cục bộ, nên cần phải lần lượt bảo trì. Mà mỗi khi bảo trì thì xe không được lưu thông trên đường cao tốc. Vì vậy, nếu có một con đường trong giai đoạn bảo trì, thì \((n-1)+(m-k)-1\) con đường còn lại vẫn phải đảm bảo kết nối giao thông giữa hai tỉnh thành bất kỳ với nhau.

Sau khi trình bày xong vấn đề nêu trên, thầy giáo đưa ra yêu cầu cho các bạn sinh viên là hãy tính độ chống chịu của giao thông đất nước này. Độ chống chịu là giá trị \(w\) lớn nhất, sao cho khi động đất \(w\) độ xảy ra trên toàn quốc, thì cho dù một số đường cao tốc bị sập, những đường cao tốc còn lại vẫn phải đảm bảo kết nối được hai tỉnh thành bất kỳ với nhau, kể cả trong trường hợp có thêm tối đa một con đường cần phải bảo trì.

Để tạo ra nhiều bài tập cho các bạn về nhà luyện tập, thầy quyết định cho các bạn thêm \(q\) phiên bản quy hoạch nữa. Gọi phiên bản gốc (phiên bản thứ \(0\)) là phiên bản gồm \((n-1)+m\) đường cao tốc ban đầu; phiên bản thứ \(y\) được tạo bằng cách thêm vào phiên bản thứ \(y-1\) một tuyến đường cao tốc phụ nữa nối giữa tỉnh \(u'_y\) và tỉnh \(v'_y\), với khả năng chống chịu động đất tối đa \(w'_y\) độ. Hãy tính độ chống chịu của quốc gia này ở mỗi phiên bản quy hoạch trong số \(q+1\) phiên bản.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 15 \cdot 10^4)\) là số tỉnh thành trong nước.
• Dòng thứ \(i\) trong số \(n-1\) dòng tiếp theo chứa hai số nguyên \(u_i\) và \(v_i\) \((1 \leq u_i, v_i \leq n, u_i \neq v_i)\) thể hiện một đường cao tốc huyết mạch nối giữa hai thành phố \(u_i\) và \(v_i\). Dữ liệu đảm bảo tồn tại một đường đi giữa hai thành phố bất kỳ mà chỉ dùng những cây cầu này.
• Dòng tiếp theo chứa một số nguyên \(m\) \((0 \leq m \leq 2 \cdot 10^5)\) là đường cao tốc đã được xây thêm.
• Dòng thứ \(j\) trong số \(m\) dòng tiếp theo chứa hai số nguyên \(u_j\), \(v_j\) và \(w_j\) \((1 \leq u_j, v_j \leq n, u_j \neq v_j, 1 \leq w_j \leq 10^9)\) thể hiện một tuyến đường cao tốc phụ đã được xây thêm giữa hai thành phố \(u_j\) và \(v_j\) với khả năng chịu rung chấn tối đa \(w_j\) độ.
• Dòng tiếp theo chứa một số nguyên \(q\) \((0 \leq q \leq 3 \cdot 10^5)\) là số phiên bản quy hoạch mà giảng viên giao cho.
• Dòng thứ \(y\) trong số \(q\) dòng tiếp theo chứa ba số nguyên \(u'_y\), \(v'_y\) và \(w'_y\) \((1 \leq u'_y, v'_y \leq n, u'_y \neq v'_y, 1 \leq w'_y \leq 10^9)\) thể hiện một tuyến đường phụ sẽ được xây thêm giữa hai thành phố \(u'_y\) và \(v'_y\) với khả năng chịu rung chấn tối đa \(w'_y\) độ.

Output

• In ra \(q+1\) dòng, dòng thứ \(i\) \((1 \leq i \leq q+1)\) chứa một số nguyên là độ chống chịu của quốc gia đó tại phiên bản quy hoạch thứ \(i-1\). Nếu với mọi trận động đất với sức mạnh khác nhau, ta luôn tìm được một cây cầu mà khi bảo trì thì các tỉnh thành còn lại không liên thông với nhau, thì phiên bản quy hoạch đấy không có sức chống chịu rủi ro, khi đó ta in ra \(-1\).

Scoring

• Subtask 1 (15% số điểm): \(n \leq 500\), \(m = 1\), \(q = 0\) và mỗi tỉnh kề với không quá 2 đường cao tốc trong số \(n-1\) đường cao tốc thuộc bản quy hoạch giả tưởng.
• Subtask 2 (14% số điểm): \(n, m \leq 500\), \(q = 0\).
• Subtask 3 (8% số điểm): \(n, m, q \leq 500\).
• Subtask 4 (9% số điểm): \(n \leq 3000\), \(m \leq 5000\), \(q = 0\).
• Subtask 5 (12% số điểm): \(n \leq 8000\), \(m \leq 7000\), \(q \leq 9000\).
• Subtask 6 (15% số điểm): \(q = 0\).
• Subtask 7 (17% số điểm): Mỗi tỉnh kề với không quá 2 đường cao tốc trong số \(n-1\) đường cao tốc thuộc bản quy hoạch giả tưởng.
• Subtask 8 (10% số điểm): Không có ràng buộc gì thêm.

Example

4
1 2
1 3 
1 4
2
2 3 4
3 4 5
0

4

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

-1
3