Trên đại lộ THT độ dài ~N~ mét, người ta cần trồng cây để làm đẹp cảnh quan. Tuy nhiên, khoảng cách giữa hai cây bắt buộc là ~K~ mét.

Yêu cầu: Bắt đầu trồng cây từ điểm bắt đầu của đại lộ, em hãy tính số lượng cây được trồng ở một bên đường của đại lộ THT.

Dữ liệu nhập vào từ bàn phím

• Gồm hai số tự nhiên ~N~ và ~K~ ~(1 ≤ K, N ≤ 1000)~. Mỗi số trên một dòng.

Kết quả

• Một số duy nhất là kết quả bài toán.

Sample Input 1

10
2

Sample Output 1

6

Note

• Ta có thể trồng được ~6~ cây tính cả ~2~ cây được trồng tại hai đầu của đại lộ.

Sample Input 2

7
3

Sample Output 2

3

Note

• Ta chỉ trồng được ~3~ cây.

Ban tổ chức (BTC) THT có ~N~ quả bóng xếp thành một hàng từ trái sang phải đánh số từ ~1~ đến ~N~ để cho các bạn học sinh chơi trò chơi.

• Đầu tiên, BTC tô màu đỏ lên những quả bóng có số thứ tự chia hết cho ~a~;
• Sau đó, BTC tô màu xanh lên những quả bóng có số thứ tự chia hết cho ~b~;
• Cuối cùng, BTC tô các quả bóng còn lại bằng màu vàng.

Yêu cầu: Em hãy tính số lượng quả bóng được tô màu vàng?

Dữ liệu nhập vào

• Gồm ba số tự nhiên ~N~, ~a~, ~b~ ~(1 \le a, b ≤ N)~. Mỗi số trên một dòng.

Kết quả

• Một số tự nhiên duy nhất là kết quả của bài toán.

Chấm điểm

• Có 50% số test ứng với 50% số điểm: ~N ≤ 100~;
• 50% số test còn lại ứng với 50% số điểm: ~100 < N ≤ 10^8~; ~b = a + 1~.

Sample Input

10
2
5

Sample Output

4

Note

• Đầu tiên, tô màu đỏ lên các quả bóng có số thứ tự ~2~, ~4~, ~6~, ~8~, ~10~; sau đó, tô màu xanh lên các quả bóng có số thứ tự ~5~ và ~10~; Cuối cùng còn lại ~4~ quả bóng có số thứ tự ~1~, ~3~, ~7~, ~9~ được tô màu vàng.

Ban tổ chức (BTC) THT có một bàn cờ kích thước ~N × N~ ô vuông. Như vậy, bàn cờ có ~2 × N-1~ đường chéo từ trái - trên sang phải - dưới. Trong đó, đường chéo chính là đường chéo nối ô ~(1, 1)~ ở góc trái trên xuống ô ~(N, N)~ ở góc phải dưới.

BTC muốn tô bàn cờ bằng ~K~ màu khác nhau với quy tắc như sau:

• Đường chéo chính luôn được tô màu ~1~
• Các đường chéo tính từ đường chéo chính lên phía trên sẽ tô các màu từ ~1~ đến ~K~ rồi lại lặp lại chu kì ~1~ đến ~K~;
• Các đường chéo tính từ đường chéo chính xuống dưới sẽ tô các màu lần lượt từ ~1~ đến ~K~ rồi lặp lại chu kì ~1~ đến ~K~.

Yêu cầu: Em hãy tính giúp ban tổ chức số ô vuông được tô màu ~1~.

Dữ liệu

• Gồm hai số tự nhiên ~N~ và ~K~ ~(N ≤ 10^6; K ≤ 10^3)~, mỗi số trên một dòng.

Kết quả

• Gồm một số tự nhiên duy nhất là kết quả của bài toán.

Sample Input 1

4
2

Sample Output 1

8

Note

• Bàn cờ sẽ có màu như sau:

Sample Input 2

8
3

Sample Output 2

22

Note

• Bàn cờ sẽ có màu như sau:

Cho dãy số có quy luật sau:

~1~ , ~2~ , ~3~ , ~6~ , ~5~ , ~4~ , ~7~ , ~8~ , ~9~ , ~12~ , ~11~ , ~10~ , ~13~ , ~14~ , ~15~ , ~18~ , ~17~ , ~16~ , ~...~

Yêu cầu: Cho hai số nguyên dương ~L~, ~R~. Hãy tính tổng các số từ vị trí ~L~ đến vị trí ~R~ của dãy số trên.

Dữ liệu

• Gồm hai số tự nhiên ~L~ và ~R~ ~(1 ≤ L ≤ R ≤ 10^8)~, mỗi số trên một dòng.

Kết quả

• Gồm một số tự nhiên là kết quả của bài toán.

Chấm điểm:

• Có 50% số test ứng với 50% số điểm với ~R ≤ 10^5~;
• 50% số test còn lại ứng với 50% số điểm không có ràng buộc gì thêm.

Sample Input

3
8

Sample Output

33

Note

• Tổng các số từ vị trí ~3~ đến vị trí ~8~ là ~3+6+5+4+7+8= 33~

Mật mã để mở kho báu được giấu trong một xâu kí tự. Xâu kí tự này gồm ~4~ loại kí tự các kí tự a, b, c, d và kí tự 0. Điều đặc biệt là xâu kí tự này có thể nối hai đầu lại với nhau thành ~1~ vòng tròn và có thể thay mỗi kí tự 0 bằng một kí tự bất kì trong các kí tự từ a đến d. Mật mã của xâu chính là độ dài lớn nhất của xâu con liên tiếp chỉ chứa một loại kí tự duy nhất.

Yêu cầu: Em hãy lập trình đưa ra mật mã để mở kho báu.

Dữ liệu vào

• Gồm một xâu duy nhất chứa các kí tự chữ cái từ a đến d và kí tự 0. Độ dài của xâu không vượt quá ~100~.

Chấm điểm

• Có 30% số test ứng với 30% số điểm:
  • Trong xâu chỉ bao gồm hai loại kí tự là a và b;
  • Xâu chia làm hai phần, một phần toàn kí tự a liên tiếp và một phần toàn kí tự b liên tiếp.
• Có 30% số test ứng với 30% số điểm: trong xâu chỉ bao gồm hai loại kí tự là a và b;
• Có 20% số test ứng với 20% số điểm: mật mã được giấu trong xâu ban đầu theo đúng thứ tự đó mà không cần ghép hai đầu lại với nhau;
• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Kết quả

• Một số nguyên dương duy nhất là kết quả của bài toán.

Sample Input 1

0ddc0ba

Sample Output 1

3

Note

• Có thể thay kí tự 0 ở vị trí đầu tiên thành d. Tạo ra xâu dddc0ba, chứa xâu ddd là xâu con dài nhất chỉ chứa một loại kí tự.

Sample Input 2

0dc0b

Sample Output 2

3

Note

• Có thể thay cả hai kí tự 0 trong xâu thành kí tự b được xâu bdcbb. Ghép đầu và cuối xâu lại thì được xâu con bbb có độ dài 3 là lớn nhất.