Ngày hôm nay có ~n~ gian hàng bán đồ ăn tại lễ hội ở đền Hakurei. Yuyuko ham ăn muốn đi ăn ~q~ lượt, mỗi lượt từ gian hàng ~l~ đến gian hàng ~r~. Với mỗi gian hàng, hãy in ra số lần cô ghé thăm.

Input

• Dòng đầu gồm 2 số ~n, q~.
• ~q~ dòng tiếp theo mỗi dòng thứ ~i~ gồm 2 số ~l_i, r_i~ ~(1 \le l_i \le r_i \le 10^5)~ là lượt đi ăn thứ ~i~.

Output

• In ra ~n~ số ứng với ~n~ cửa hàng là số lần Yuyuko vào gian hàng.

Sample Test

Input:

4 3
1 3
2 4
1 2

Output:

2 3 2 1

Trên trục số ~Ox~, cho ~𝑁~ đoạn thẳng, mỗi đoạn thẳng được xác định bởi hai điểm đầu và cuối là hai số nguyên. Một điểm ~𝑀~ được gọi là nằm trong đoạn thẳng ~𝐴𝐵~ nếu ~𝐴 ≤ 𝑀 ≤ 𝐵~.

Yêu cầu: Đếm xem có bao nhiêu điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Dữ liệu nhập vào từ file văn bản DC.INP:

• Dòng đầu tiên gồm hai số nguyên ~𝑁~ và ~𝐾~ ~(1 ≤ 𝐾 ≤ 𝑁 ≤ 10^5);~
• ~𝑁~ dòng sau, mỗi dòng gồm hai số nguyên ~𝑎, 𝑏~ mô tả hai điểm đầu và cuối của đoạn thẳng ~(1 ≤ 𝑎 ≤ 𝑏 ≤ 10^{18})~.

Kết quả ghi ra file văn bản DC.OUT:

Một số nguyên duy nhất là số lượng điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Ràng buộc

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bài thoả mãn: ~𝑎, 𝑏 ≤ 10^3;~
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~𝐾 = 𝑁;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3 2
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong đúng ~2~ đoạn thẳng là: ~2, 6, 7~.

• Điểm có toạ độ ~2~ nằm trong ~2~ đoạn thẳng: đầu tiên và thứ hai.
• Điểm có toạ độ ~6, 7~ nằm trong ~2~ đoạn thẳng: thứ hai và thứ ba.

Input

3 1
1 5
2 8
3 7

Output

2   

Giải thích: Toạ độ của ~2~ điểm nằm trong đúng ~1~ đoạn thẳng là: ~1, 8~.

• Điểm có toạ độ ~1~ chỉ nằm trong đoạn thẳng đầu tiên.
• Điểm có toạ độ ~8~ chỉ nằm trong đoạn thẳng thứ ba.

Input

3 3
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong cả ~3~ đoạn thẳng là: ~3,4,5~.

Hôm nay lại có ~n~ gian hàng bán đồ ăn tại lễ hội ở đền Hakurei. Yuyuko tham ăn có ~q~ lựa chọn dạng ~l_i, r_i~, đi ăn tất cả cửa hàng ở vị trí ~l_i~ đến vị trí ~r_i~.

Nhưng hôm nay do quá đói, cô đã đi ăn ~m~ lần, sử dụng tất cả các lựa chọn từ ~x_i~ đến ~y_i~. Với mỗi gian hàng, hãy in ra số lần cô ghé thăm.

Input:

• Dòng đầu gồm 3 số tự nhiên ~n, q, m~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số ~1 \le l_i, r_i \le n~ là lựa chọn thứ ~i~.
• ~m~ dòng tiếp theo mỗi dòng gồm 2 số ~1 \le x_i, y_i \le q~ là lượt đi ăn thứ ~j~.

Output:

• ~n~ số nguyên không âm là số lần cô ghé thăm các gian hàng.

Sample Test:

• Input:

3 3 3
1 2
2 3
1 3
2 3
1 2
1 3

• Output

4 7 5

Giới hạn:

• 40% số điểm: ~n, q, m \le 100~.
• 30% số điểm: ~n, q, m \le 5000~.
• 30% số điểm: ~n, q, m \le 10^5~

Số chính phương đặc biệt là số chính phương được tạo bởi một số nguyên tố. Ví dụ ~4 = 2 \times 2; \ 9 = 3 \times 3; \ 36 = 6 \times 6~ nên ~4~ và ~9~ là số chính phương đặc biệt còn ~36~ thì không phải là số chính phương đặc biệt.

Yêu cầu: Cho ~2~ số nguyên dương ~a, b~. Hãy đếm xem trong đoạn ~[a..b]~ có bao nhiêu số chính phương đặc biệt?

Dữ liệu vào từ tệp văn bản CP.INP:

Gồm hai số nguyên dương ~a, b \ (2 \le a \le b \le 10^{12})~.

Kết quả ghi ra tệp văn bản CP.OUT:

Gồm một dòng chứa một số duy nhất là kết quả của bài toán.

Ràng buộc

• Có ~80\%~ số test ứng với ~80\%~ số điểm của bài thoả mãn ~2 \le a \le b \le 10^6;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

2 10

Output

2