JOI-kun rất thích sưu tập thẻ trong một trò chơi. Mỗi thẻ có hai số nguyên biểu thị sức mạnh và chi phí. Để có thẻ mới, JOI-kun mang \(N\) thẻ đến nơi đổi thẻ. Các thẻ được đánh số từ \(1\) đến \(N\); thẻ \(i\) có sức mạnh \(S_i\) và chi phí \(V_i\).

Tại đây có hai loại máy. Khi đưa hai thẻ \(A\) và \(B\) vào một máy, JOI-kun nhận được một thẻ \(C\) theo quy tắc sau:

• Máy thứ nhất tạo thẻ có sức mạnh bằng giá trị lớn hơn trong hai sức mạnh của \(A,B\), và chi phí bằng giá trị lớn hơn trong hai chi phí của \(A,B\).
• Máy thứ hai tạo thẻ có sức mạnh bằng giá trị nhỏ hơn trong hai sức mạnh của \(A,B\), và chi phí bằng giá trị nhỏ hơn trong hai chi phí của \(A,B\).

JOI-kun muốn đổi thẻ đúng \(N-1\) lần để cuối cùng chỉ còn một thẻ. Ban đầu, cậu xếp các thẻ thành một hàng theo thứ tự từ thẻ \(1\) đến thẻ \(N\), rồi lặp lại thao tác sau đúng \(N-1\) lần:

Chọn hai thẻ kề nhau, lấy chúng ra khỏi hàng và đổi bằng một trong hai máy. Đặt thẻ mới vào vị trí của hai thẻ vừa lấy ra.

Sức mạnh và chi phí của thẻ cuối cùng phụ thuộc vào các thao tác được chọn. JOI-kun có danh sách \(M\) thẻ muốn nhận được. Thẻ thứ \(j\) trong danh sách được biểu diễn bởi cặp \((T_j,W_j)\), tương ứng với sức mạnh và chi phí.

Cho thông tin về các thẻ ban đầu và danh sách mong muốn, hãy xác định tất cả các thẻ trong danh sách mà JOI-kun có thể nhận được sau đúng \(N-1\) thao tác.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N,M\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(S_i,V_i\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(T_j,W_j\).

Dữ liệu ra

In trên một dòng chỉ số của tất cả các thẻ trong danh sách có thể nhận được sau đúng \(N-1\) thao tác, theo thứ tự tăng dần và cách nhau bởi dấu cách. Nếu không có thẻ nào như vậy, in một dòng trống.

Ràng buộc

• \(2 \le N \le 200000\).
• \(1 \le M \le 200000\).
• \(1 \le S_i \le 10^9\) và \(1 \le V_i \le 10^9\) với mọi \(1 \le i \le N\).
• \(1 \le T_j \le 10^9\) và \(1 \le W_j \le 10^9\) với mọi \(1 \le j \le M\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(11\) điểm: \(N \le 20\), \(M \le 10\).
2. \(38\) điểm: \(N \le 2000\), \(M \le 10\).
3. \(22\) điểm: \(M \le 10\).
4. \(29\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

1 3

2 2
1 1
2 2
1 2
2 1

8 8
5 2
4 4
1 3
7 8
3 1
8 7
6 5
2 6
1 4
7 2
8 8
3 1
5 6
2 7
6 3
2 5

3 4 5 8

Giới hạn

Giới hạn thời gian là \(4\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2023/2024, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.