Nhằm tạo không gian sinh động và tăng tính thẩm mỹ cho tuyến phố vào ban đêm, thành phố A đã lắp đặt một hệ thống đèn trang trí thông minh trên tuyến đường mới. Hệ thống được lập trình để tự động thay đổi trạng thái các đèn theo những chu kỳ khác nhau, tạo nên các hiệu ứng ánh sáng đa dạng và độc đáo.

Tuyến đường có ~N~ đèn được đánh số từ ~1~ đến ~N~. Ban đầu, tất cả các đèn đều tắt.

Hệ thống thực hiện ~N~ lần kích hoạt, được đánh số từ ~1~ đến ~N~.

Ở lần kích hoạt thứ ~i~, hệ thống sẽ đổi trạng thái tất cả các đèn có số hiệu là bội của ~i~. Nghĩa là: đèn đang tắt sẽ được bật và đèn đang bật sẽ bị tắt.

Ví dụ, ở lần kích hoạt thứ ~3~, hệ thống sẽ đổi trạng thái các đèn: ~3, 6, 9, 12, \dots~ không vượt quá ~N~.

Sau khi hoàn thành tất cả ~N~ lần kích hoạt, trạng thái của các đèn được giữ nguyên. Khi đó, trung tâm điều khiển sẽ phân tích hiệu ứng ánh sáng bằng cách đưa ra ~q~ truy vấn. Mỗi truy vấn xác định một đoạn đèn từ vị trí ~L~ đến vị trí ~R~.

Yêu cầu: Với mỗi truy vấn, hãy thực hiện hai yêu cầu:

• a) Đếm số lượng đèn đang bật trong đoạn ~[L, R]~.

• b) Tìm số hiệu lớn nhất của đèn đang bật trong đoạn ~[L, R]~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, q~ ~(1 \le N \le 10^{18}, 1 \le q \le 10^5)~.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L, R~ mô tả một truy vấn ~(1 \le L \le R \le N)~.

Output

Gồm ~q~ dòng: Mỗi dòng chứa hai số nguyên, lần lượt là:

• Số lượng đèn đang bật trong đoạn ~[L, R]~.

• Số hiệu lớn nhất của đèn đang bật trong đoạn ~[L, R]~.

Nếu không có đèn nào đang bật trong đoạn, ghi: 0 0

Scoring

Sample Input 1

10 3
1 10
2 7
5 8

Sample Output 1

3 9
1 4
0 0