Cho một robot được lập trình di chuyển trên một hàng ngang gồm các ô vuông. Mỗi ô được đặt tên bằng các kí tự theo thứ tự từ ~'𝐴'~ đến ~'𝑍'~ và được lặp lại vô hạn. Ban đầu robot xuất phát ở ô thứ ~1~ có tên là ~'𝐴'~ và nhảy đến các ô tiếp theo quy luật: lần ~1~ nhảy ~1~ ô, lần ~2~ nhảy ~2~ ô, lần ~3~ nhảy ~3~ ô, ~…~, lần ~𝑁~ nhảy ~𝑁~ ô. Vậy sau ~𝑁~ lần nhảy thì robot đang ở ô nào?

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

Gồm một số nguyên dương ~N~ là số lần nhảy của robot ~(N \le 10^9)~.

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

Một kí tự duy nhất là tên của ô sau ~N~ lần robot nhảy.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^3;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 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

1

Output

B

Giải thích: Sau ~1~ lần nhảy, robot ở ô thứ ~2~, có tên là kí tự ~B~.

Input

4

Output

K

Giải thích: Sau ~4~ lần nhảy, robot ở ô thứ ~11~, có tên là kí tự ~K~.

Input

7

Output

C

Giải thích: Sau ~7~ lần nhảy, robot ở ô thứ ~29~, có tên là kí tự ~C~.

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~.