Hộ chiếu là giấy tờ được sử dụng trên khắp thế giới khi một người nhập cảnh vào nước ngoài.

Trên một hành tinh có \(N\) quốc gia, đánh số từ \(1\) đến \(N\). Mỗi quốc gia phát hành một loại hộ chiếu. Người có hộ chiếu do quốc gia \(i\) (\(1\le i\le N\)) phát hành được nhập cảnh vào các quốc gia \(L_i,L_i+1,\ldots,R_i\). Luôn được nhập cảnh vào chính quốc gia đã phát hành hộ chiếu, tức là \(L_i\le i\le R_i\).

Bạn có một người bạn rất thích du lịch. Cậu ấy mơ ước đi vòng quanh thế giới, nhưng ban đầu chưa có hộ chiếu nào. Vì vậy, cậu dự định ghé thăm tất cả \(N\) quốc gia bằng cách lặp lại hai hành động sau:

• Nhận hộ chiếu do quốc gia mà cậu đang ở phát hành.
• Di chuyển đến một quốc gia mà cậu được nhập cảnh bằng một trong các hộ chiếu hiện có.

Khi nghe kế hoạch này, bạn muốn biết cậu ấy có thể thực hiện được hay không. Nếu có thể, số hộ chiếu ít nhất mà cậu cần nhận là bao nhiêu? Do không biết cậu đang sống ở đâu, bạn xét \(Q\) khả năng về quốc gia nơi cậu sống: \(X_1,X_2,\ldots,X_Q\).

Cho thông tin về các hộ chiếu và những khả năng về nơi ở. Với mỗi khả năng, hãy xác định cậu ấy có thể ghé thăm tất cả \(N\) quốc gia hay không; nếu có thể, hãy tính số hộ chiếu ít nhất cần nhận.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N
L_1 R_1
L_2 R_2
...
L_N R_N
Q
X_1
X_2
...
X_Q

Dữ liệu ra

Xuất \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) (\(1\le j\le Q\)) tương ứng với trường hợp người bạn sống ở quốc gia \(X_j\). Nếu có thể ghé thăm tất cả \(N\) quốc gia, xuất số hộ chiếu ít nhất cần nhận. Nếu không thể, xuất -1.

Ràng buộc

• \(2\le N\le 200\,000\).
• \(1\le L_i\le i\le R_i\le N\) với \(1\le i\le N\).
• \(1\le Q\le N\).
• \(1\le X_j\le N\) với \(1\le j\le Q\).
• \(X_j<X_{j+1}\) với \(1\le j\le Q-1\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(6\) điểm: \(Q=1\), \(X_1=1\).
2. \(16\) điểm: \(N\le 300\), \(Q=1\).
3. \(24\) điểm: \(N\le 2\,500\), \(Q=1\).
4. \(8\) điểm: \(N\le 2\,500\).
5. \(46\) điểm: Không có ràng buộc bổ sung.

Ví dụ

4
1 3
2 4
2 3
4 4
1
1

2

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

4

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

-1
2
1
2
-1

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

-1
-1
-1
-1

Nguồn

JOI 2022/2023 Spring Training, Contest 1, bài Passport, tác giả 米田寛峻 và 米田優峻.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.