Bạn đang chuẩn bị mở một cửa hàng bán búp bê Matryoshka. Vì vậy, bạn đã đặt mua \(N\) con búp bê Matryoshka từ một nhà máy. Các con búp bê được đánh số từ \(1\) đến \(N\). Búp bê thứ \(i\) (\(1 \le i \le N\)) có thể được xem là một hình trụ tròn đứng rỗng bên trong, với đường kính đáy \(R_i\) cm và chiều cao \(H_i\) cm.

Các con búp bê Matryoshka có thể được lồng vào nhau để cất giữ. Mỗi con búp bê chỉ có thể chứa trực tiếp một con búp bê khác có cả đường kính đáy và chiều cao nhỏ hơn nó. Con búp bê được chứa bên trong cũng có thể chứa một con búp bê khác.

Một ngày nọ, nhà máy mà bạn đặt mua búp bê liên lạc với bạn. Do không thể chuẩn bị đồng thời tất cả \(N\) con búp bê đã đặt, nhà máy sẽ giao trước tất cả những con búp bê có đường kính đáy ít nhất \(A\) cm và chiều cao không quá \(B\) cm.

Các giá trị \(A, B\) có thể bị thay đổi đột ngột. Vì vậy, với mỗi trong \(Q\) cặp \((A_j, B_j)\) (\(1 \le j \le Q\)), bạn muốn tính trước số lượng nhỏ nhất các con búp bê không nằm trong bất kỳ con búp bê nào khác, khi lồng những con búp bê được giao trước vào nhau để cất giữ.

Yêu cầu

Cho đường kính đáy và chiều cao của từng con búp bê, cùng \(Q\) cặp \((A_j, B_j)\) (\(1 \le j \le Q\)). Hãy viết chương trình, với mỗi cặp, tìm số lượng nhỏ nhất các con búp bê không nằm trong bất kỳ con búp bê nào khác, khi lồng những con búp bê được giao trước vào nhau để cất giữ.

Dữ liệu vào

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

• Dòng đầu tiên chứa hai số nguyên \(N, Q\), cách nhau bởi dấu cách. Đây lần lượt là số con búp bê đã đặt mua và số cặp giá trị \(A, B\) được cho.
• Dòng thứ \(i\) (\(1 \le i \le N\)) trong \(N\) dòng tiếp theo chứa hai số nguyên \(R_i, H_i\), cách nhau bởi dấu cách. Búp bê thứ \(i\) có đường kính đáy \(R_i\) cm và chiều cao \(H_i\) cm.
• Dòng thứ \(j\) (\(1 \le j \le Q\)) trong \(Q\) dòng tiếp theo chứa hai số nguyên \(A_j, B_j\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa số lượng nhỏ nhất các con búp bê không nằm trong bất kỳ con búp bê nào khác, khi lồng những con búp bê được giao trước ứng với cặp \((A_j, B_j)\) vào nhau để cất giữ.

Ràng buộc

Tất cả dữ liệu vào thỏa mãn các điều kiện sau:

• \(1 \le N \le 200\,000\).
• \(1 \le Q \le 200\,000\).
• \(1 \le R_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).
• \(1 \le H_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).
• \(1 \le A_j \le 1\,000\,000\,000\) (\(1 \le j \le Q\)).
• \(1 \le B_j \le 1\,000\,000\,000\) (\(1 \le j \le Q\)).

Phân nhóm

1. 11 điểm: \(N \le 10\); \(Q = 1\).
2. 15 điểm: \(N \le 100\); \(Q = 1\).
3. 25 điểm: \(N \le 2\,000\); \(Q \le 2\,000\).
4. 49 điểm: Không có ràng buộc bổ sung.

Ví dụ

7 3
9 5
3 7
10 6
5 10
2 6
10 10
4 1
10 5
3 5
3 9

0
1
2

10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14

3
1
3
5
0
2
1
3