Đất nước JOI nằm trên một mặt phẳng và có \(N\) ngôi làng, đánh số từ \(1\) đến \(N\). Làng \(i\) được biểu diễn bởi điểm \((i,0)\). Để đề phòng sự cố, đất nước dự định xây dựng hai hệ thống đường truyền thông tin, gọi là hệ thống \(1\) và hệ thống \(2\).

Hệ thống \(k\) có \(M_k\) bộ tập trung, đánh số từ \(1\) đến \(M_k\), và \(N+M_k-1\) đường truyền. Bộ tập trung thứ \(j\) của hệ thống \(k\) nằm tại \((X_{kj},Y_{kj})\). Mỗi đường truyền của hệ thống \(k\) nối một làng với một bộ tập trung của hệ thống đó, hoặc nối hai bộ tập trung của hệ thống đó. Đường truyền là đoạn thẳng nối hai đầu mút. Hai đường truyền bất kỳ chỉ có thể có điểm chung tại đầu mút chung của chúng.

Các bộ tập trung của hệ thống \(1\) có tung độ dương, còn các bộ tập trung của hệ thống \(2\) có tung độ âm. Hai địa điểm liên lạc được với nhau nếu có thể đi từ địa điểm này đến địa điểm kia bằng cách đi dọc các đường truyền liên tiếp. Khi chỉ xét riêng từng hệ thống, mọi làng và mọi bộ tập trung của hệ thống đó đều liên lạc được với nhau.

Người ta muốn đánh giá khả năng duy trì liên lạc khi bị tấn công. Một cuộc tấn công được mô tả bởi hai số \(A,B\) với \(A\ge0\) và \(B\le0\): tất cả bộ tập trung có tung độ lớn hơn \(A\) hoặc nhỏ hơn \(B\) bị phá hủy. Không thể truyền thông tin qua một bộ tập trung đã bị phá hủy.

Yêu cầu

Cho thông tin các làng, hai hệ thống và \(Q\) truy vấn. Truy vấn thứ \(q\) cho số nguyên \(A_q\). Hãy tìm số nguyên \(B_q\le0\) lớn nhất sao cho, sau khi phá hủy mọi bộ tập trung có tung độ lớn hơn \(A_q\) và mọi bộ tập trung có tung độ nhỏ hơn \(B_q\), tất cả các làng vẫn liên lạc được với nhau bằng các đường truyền còn sử dụng được của hai hệ thống.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa bốn số nguyên \(N,M_1,M_2,Q\).
• Tiếp theo là thông tin hệ thống \(1\): trước hết là \(M_1\) dòng tọa độ, rồi \(N+M_1-1\) dòng mô tả đường truyền.
• Tiếp theo là thông tin hệ thống \(2\): trước hết là \(M_2\) dòng tọa độ, rồi \(N+M_2-1\) dòng mô tả đường truyền.
• Cuối cùng là \(Q\) dòng, dòng thứ \(q\) chứa số nguyên \(A_q\).

Đối với hệ thống \(k\), dòng tọa độ thứ \(j\) chứa hai số nguyên \(X_{kj},Y_{kj}\). Dòng mô tả đường truyền thứ \(i\) chứa ba số nguyên \(T_{ki},C_{ki},D_{ki}\), trong đó:

• Nếu \(T_{ki}=1\), đường truyền nối làng \(C_{ki}\) với bộ tập trung \(D_{ki}\) của hệ thống \(k\); \(1\le C_{ki}\le N\) và \(1\le D_{ki}\le M_k\).
• Nếu \(T_{ki}=2\), đường truyền nối hai bộ tập trung \(C_{ki}\) và \(D_{ki}\) của hệ thống \(k\); \(1\le C_{ki},D_{ki}\le M_k\) và \(C_{ki}\ne D_{ki}\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(q\) chứa số nguyên \(B_q\), là đáp án của truy vấn thứ \(q\).

Nếu đáp án bằng \(0\), phải in 0, không được in -0.

Ràng buộc

• Giới hạn thời gian: 2 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(1\le N,M_1,M_2\le100000\).
• \(-10^9\le X_{1j},X_{2j}\le10^9\) với các chỉ số tương ứng hợp lệ.
• \(1\le Y_{1j}\le10^9\) với \(1\le j\le M_1\).
• \(-10^9\le Y_{2j}\le-1\) với \(1\le j\le M_2\).
• Trong cùng một hệ thống, không có hai bộ tập trung trùng tọa độ: nếu \(i\ne j\) thì \(X_{ki}\ne X_{kj}\) hoặc \(Y_{ki}\ne Y_{kj}\).
• \(1\le Q\le100000\) và \(0\le A_q\le10^9\).
• \(T_{ki}\in\{1,2\}\).
• Hai đường truyền bất kỳ chỉ có thể có điểm chung tại đầu mút chung.
• Khi chỉ xét riêng từng hệ thống, mọi làng và mọi bộ tập trung của hệ thống đó đều liên lạc được với nhau.

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (20 điểm): \(N,M_1,M_2,Q\le1000\).
• Nhóm 2 (80 điểm): Không có ràng buộc bổ sung.

4 3 3 1
1 1
3 2
2 3
1 1 1
1 2 1
1 3 2
1 4 2
2 1 3
2 2 3
3 -1
2 -2
1 -3
1 1 3
1 2 2
1 3 1
1 4 1
2 1 2
2 2 3
2

-2

Với \(A_1=2\), bộ tập trung số \(3\) của hệ thống \(1\) bị phá hủy. Chọn \(B_1=-2\) sẽ phá hủy thêm bộ tập trung số \(3\) của hệ thống \(2\), nhưng các làng vẫn liên lạc được với nhau. Nếu tăng \(B_1\) lên \(-1\), bộ tập trung số \(2\) của hệ thống \(2\) cũng bị phá hủy và không còn liên lạc được giữa nhóm làng \(1,2\) với nhóm làng \(3,4\).

6 4 5 4
2 1
4 1
3 3
5 2
1 1 1
1 2 1
1 3 2
1 4 2
2 2 4
1 5 4
1 6 4
2 1 3
2 4 3
3 -3
5 -1
2 -2
2 -1
4 -2
1 2 4
1 3 4
1 1 4
2 1 3
1 5 2
1 6 2
1 4 5
2 2 5
1 3 1
2 5 1
3
1
2
0

0
-2
-1
-3

Bốn truy vấn với \(A_q\) lần lượt là \(3,1,2,0\) có các giá trị \(B_q\) lớn nhất tương ứng là \(0,-2,-1,-3\).