Thật trùng hợp kỳ lạ! Sau khi xác định được bộ sưu tập nghệ thuật đương đại có giá trị nhất, bạn nhận ra rằng dường như nó nằm đâu đó gần Lübeck. Vì chưa biết vị trí chính xác, bạn muốn thu thập thêm thông tin. May thay, vào ngày bạn đến dự BOI năm nay, cộng đồng nghệ thuật địa phương tổ chức \(N\) sự kiện về nghệ thuật đương đại. Đây có vẻ chính là cơ hội bạn đang chờ đợi.

Để lên kế hoạch tham dự, bạn đánh số các sự kiện từ \(1\) đến \(N\). Sự kiện thứ \(i\) bắt đầu lúc \(S_i\) và kết thúc lúc \(E_i\). Bạn muốn bắt đầu chuyến tham dự ở sự kiện \(s\) và kết thúc ở sự kiện \(e\). Chừng nào chưa tham dự sự kiện \(e\), bạn luôn ở lại sự kiện hiện tại đến khi nó kết thúc, rồi lập tức chuyển sang một sự kiện khác đang diễn ra. Rời đi sớm sẽ thật bất lịch sự, nhưng chẳng ai phàn nàn nếu bạn đến muộn: rõ ràng bạn là một nhà phê bình nghệ thuật quan trọng và bận rộn. Như vậy, bạn có thể chuyển từ sự kiện \(i\) sang sự kiện \(j\) khi và chỉ khi \(S_j\le E_i\le E_j\).

Lịch minh họa vào thứ Năm, ngày 28/4: bài nói chuyện của ông Masterart; triển lãm “Bài tập rác đương đại”; hội thảo thiết kế sô-cô-la hiện đại; lễ trao giải quả trứng Phục sinh đương đại đẹp nhất; khai trương phòng trưng bày; chợ nghệ thuật truyền thống Lübeck; và tiệc tối dành cho các nhà sưu tập nghệ thuật.

Rõ ràng, đổi sự kiện quá thường xuyên sẽ khiến bạn trông đáng ngờ. Vì vậy, bạn muốn biết số lần chuyển sự kiện ít nhất cần thiết để bắt đầu ở \(s\) và kết thúc ở \(e\). Bạn cũng chưa biết lúc nào mình sẽ đến Lübeck và lúc nào phải rời đi để đăng ký BOI vào buổi tối, nên cần trả lời câu hỏi này cho \(Q\) cặp sự kiện bắt đầu và kết thúc khác nhau.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(Q\), lần lượt là số sự kiện và số cặp sự kiện cần tìm số lần chuyển ít nhất.

\(N\) dòng tiếp theo mô tả các sự kiện. Dòng thứ \(i\) chứa hai số nguyên \(S_i\) và \(E_i\), là thời điểm bắt đầu và kết thúc của sự kiện \(i\).

\(Q\) dòng tiếp theo mô tả các truy vấn. Dòng thứ \(i\) chứa hai số nguyên \(s_i\) và \(e_i\), yêu cầu tìm số lần chuyển sự kiện ít nhất để bắt đầu ở sự kiện \(s_i\) và kết thúc chuyến tham dự ở sự kiện \(e_i\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(i\) chứa số lần chuyển sự kiện ít nhất cho truy vấn thứ \(i\), hoặc chuỗi impossible nếu không có cách thực hiện.

Ràng buộc

• \(1\le N,Q\le100\,000\).
• \(1\le S_i<E_i\le10^9\) với \(1\le i\le N\).
• \(1\le s_i,e_i\le N\) với \(1\le i\le Q\).
• Giới hạn thời gian: \(1\) giây.
• Giới hạn bộ nhớ: \(512\) MiB.

Phân nhóm

1. \(10\) điểm: từ mỗi sự kiện, có thể chuyển sang nhiều nhất một sự kiện khác.
2. \(10\) điểm: \(N\le1\,000\) và \(Q\le100\).
3. \(15\) điểm: \(N\le5\,000\).
4. \(15\) điểm: \(Q\le100\).
5. \(20\) điểm: không có sự kiện nào nằm hoàn toàn trong một sự kiện khác; tức là không tồn tại hai sự kiện \(i\ne j\) sao cho \(S_i\le S_j<E_j\le E_i\).
6. \(30\) điểm: không có ràng buộc thêm.

Ví dụ

5 2
1 3
2 4
4 7
7 9
3 7
1 4
3 2

2
impossible

8 5
1 2
3 4
1 5
6 7
5 10
10 20
15 20
999999999 1000000000
1 6
1 7
2 4
3 3
5 8

3
4
impossible
0
impossible