Trên một con đường thẳng các vị trí được đánh số từ 1 tới ~n~, khoảng cách giữa hai vị trí liên tiếp là một đơn vị độ dài, có một con thỏ đang ở vị trí ~x_1~ và một củ cà rốt đang ở vị trí ~x_2~. Cà rốt luôn là món ăn yêu thích của thỏ nên nó muốn nhảy thật nhanh đến đó để lấp đầy chiếc bụng đói của mình. Tuy vậy, mỗi bước nhảy thỏ chỉ nhảy được tối đa $a$ đơn vị độ dài.

Yêu cầu: Thỏ cần nhảy ít nhất bao nhiêu bước để tới vị trí của cà rốt?

Dữ liệu: Từ tệp văn bản CAU1.INP chứa 3 số nguyên ~x_1~, ~x_2~ và ~a~ (~1 \le x_1 \le x_2 \le 10^{12}, 1 \le a \le 10^3~) trên một dòng.

Kết quả: Ghi ra tệp văn bản CAU1.OUT một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ 1:

CAU1.INP

1 6 3

CAU1.OUT

2

CAU2.INP

2 20 3

CAU2.OUT

6

Ràng buộc:

• Có 80% số test tương ứng 80% số điểm có ~x_2 \le 10^6~;
• Có 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm.

Có ~n~ thẻ bài trên bàn, trên tấm thẻ thứ ~i~ (~1 \le i \le n~) ghi số ~a_i~. Mặt có ghi số của tấm thẻ được đặt úp xuống mặt bàn.

Có ~m~ học sinh lần lượt tham gia lật thẻ, mỗi học sinh được chọn hai tấm thẻ bất kỳ, sau đó để tấm thẻ có số nhỏ hơn lại trên bàn và mang tấm thẻ có số lớn hơn về, nếu hai tấm thẻ có số bằng nhau thì học sinh có thể chọn mang về một tấm thẻ bất kỳ trong hai tấm thẻ đó.

Yêu cầu: Gọi ~s~ là tổng các số trên thẻ mà các học sinh mang về. Hãy cho biết giá trị lớn nhất của ~s~ có thể là bao nhiêu?

Dữ liệu: Từ tệp văn bản CAU2.INP

• Dòng đầu tiên chứa lần lượt hai số nguyên dương ~n~, ~m~ (~1 \le m \le n \le 10^5~);
• Dòng thứ hai chứa ~n~ số nguyên ~a_1~, ~a_2~, ..., ~a_n~ (~1 \le a_i \le 10^9; 1 \le i \le n~).

Kết quả: Ghi ra tệp văn bản CAU2.OUT một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

CAU2.INP

6 4
5 3 7 8 1 4

CAU2.OUT

24

CAU2.INP

6 1
5 3 7 8 1 4

CAU2.OUT

8

Ràng buộc:

• Có 50% số test tương ứng 50% số điểm có ~m=1~;
• Có 50% số test còn lại tương ứng 50% số điểm không có ràng buộc gì thêm.

Cho dãy A gồm n số nguyên dương ~a_1, a_2, ..., a_n~.

Yêu cầu: Hãy cho biết trong dãy A có bao nhiêu phần tử có số lượng ước nguyên dương là số lẻ?

Dữ liệu: Từ tệp văn bản CAU3.INP

• Dòng đầu tiên chứa n số nguyên dương n (~1 \le n \le 10^6~);
• Dòng thứ hai chứa n số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^{18}; 1 \le i \le n~).

Kết quả: Ghi ra tệp văn bản CAU3.OUT một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

CAU3.INP

4
4 12 15 1

CAU3.OUT
2

Giải thích:

• Số 4 có 3 ước nguyên dương là 1, 2, 4.
• Số 12 có 6 ước nguyên dương là 1, 2, 3, 4, 6, 12.
• Số 15 có 4 ước nguyên dương là 1, 3, 5, 15.
• Số 1 có 1 ước nguyên dương là 1.

Ràng buộc:

• Có 50% test tương ứng với 50% số điểm có ~n \le 10^3, a_i \le 10^3~;
• Có 30% test khác tương ứng với 30% số điểm có ~n \le 10^4, a_i \le 10^6~;
• Có 20% test còn lại tương ứng với 20% số điểm không có ràng buộc gì thêm.

Tại xứ sở thần tiên Alpha có $n$ chú thỏ đang thu hoạch cà rốt. Chú thỏ thứ ~i~ (~1 \le i \le n~) bắt đầu thu hoạch ở vị trí ~x_i~ và thực hiện ~m_i~ bước nhảy, mỗi bước nhảy được đúng ~k_i~ đơn vị độ dài; chú thỏ thứ ~i~ có cách thu hoạch cà rốt như sau:

• Ở vị trí bắt đầu ~x_i~ thỏ thu hoạch được ~x_i~ củ cà rốt;
• Ở lần nhảy thứ nhất, thỏ thu hoạch được ~x_i + k_i~ củ cà rốt;
• Ở lần nhảy thứ ~t~ (~2 \le t \le m_i~) số cà rốt thỏ thu hoạch được nhiều hơn ~k_i~ củ cà rốt so với lần nhảy thứ ~t-1~.

Yêu cầu: Tính tổng số cà rốt sau khi ~n~ chú thỏ thu hoạch xong. Số lượng cà rốt thu hoạch có thể rất lớn nên chỉ cần đưa ra kết quả sau khi đã chia lấy phần dư cho ~(10^9 + 7)~.

Dữ liệu: Từ tệp văn bản CAU4.INP

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^6~);
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ (~1 \le i \le n~) chứa 3 số nguyên dương ~x_i, m_i, k_i~ (~1 \le x_i, m_i, k_i \le 10^9~).

Kết quả: Ghi ra tệp văn bản CAU4.OUT một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

CAU4.INP

2
2 3 5
7 2 2

CAU4.OUT

65

Giải thích:

• Chú thỏ thứ nhất có ~x_1 = 2~ thu hoạch được số lượng cà rốt là: ~2 + (2+5) + (2+5+5) = 38~;
• Chú thỏ thứ hai có ~x_2 = 7~ thu hoạch được số lượng cà rốt là: ~7 + (7+2) + (7+2+2) = 27~;
• Vậy tổng là ~38 + 27 = 65~.

Ràng buộc:

• Có 60% test tương ứng 60% số điểm có ~n, x_i, m_i, k_i \le 10^3~;
• Có 40% test còn lại tương ứng 40% số điểm không có ràng buộc gì thêm.

Cho dãy ~n~ số nguyên, các phần tử trong dãy được đánh số thứ tự từ 1 đến ~n~. Dãy số được chia thành ~\frac{n}{k}~ đoạn, ~k~ là ước của ~n~, mỗi đoạn có ~k~ số theo quy luật:

• Đoạn thứ nhất có giá trị tăng dần từ 1 đến ~k~;
• Đoạn thứ hai có giá trị giảm dần từ ~2 \times k~ về ~k+1~;
• Đoạn thứ ba có giá trị tăng dần từ ~2 \times k+1~ đến ~3 \times k~;
• Đoạn thứ tư có giá trị giảm dần từ ~4 \times k~ về ~3 \times k+1~;

• ...

• Đoạn thứ ~i~ (~1 \le i \le \frac{n}{k}~):

  • Nếu ~i~ lẻ: có giá trị tăng dần từ ~(i-1) \times k + 1~ đến ~i \times k~;
  • Nếu ~i~ chẵn: có giá trị giảm dần từ ~i \times k~ về ~(i-1) \times k + 1~.

Ví dụ với ~n=24, k=4~, dãy số nguyên có giá trị như sau: 1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13 17 18 19 20 24 23 22 21

Yêu cầu: Hãy tính tổng các số ở các vị trí từ ~l~ đến ~r~ trong dãy số đã cho.

Dữ liệu: Từ tệp văn bản CAU5.INP ghi 4 số nguyên ~n, k, l, r~ trên một dòng, trong đó ~k~ là ước của ~n~ (~1 \le l \le r \le n \le 10^9~).

Kết quả: Ghi ra tệp văn bản CAU5.OUT một số nguyên duy nhất cho biết kết quả bài toán.

Ví dụ:

CAU5.INP

24 1 1 24

CAU5.OUT

300

CAU5.INP

24 4 7 21

CAU5.OUT

209

Ràng buộc:

• Có 50% số test tương ứng 50% số điểm có ~k=1~ hoặc ~k=n~;
• Có 30% số test khác tương ứng 30% số điểm có ~n \le 10^6~;
• Có 20% test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm.