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: Tính số bước nhảy ít nhất để thỏ đến được vị trí của củ cà rốt.

Input

• Dòng duy nhất chứa 3 số nguyên ~x_1, x_2, a~ (~1 \le x_1 \le x_2 \le 10^{12}, 1 \le a \le 10^3~).

Output

• Ghi ra một số nguyên duy nhất là kết quả bài toán.

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?

Input

• Dòng đầu tiên chứa 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, \dots, a_n~ (~1 \le a_i \le 10^9; 1 \le i \le n~).

Output

• Ghi ra một số nguyên duy nhất là kết quả bài toán.

Cho dãy ~A~ gồm ~n~ số nguyên dương ~a_1, a_2, \dots, 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ẻ?

Input

• Dòng đầu tiên chứa 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, \dots, a_n~ (~1 \le a_i \le 10^{18}; 1 \le i \le n~).

Output

• Ghi ra một số nguyên duy nhất là kết quả bài toán.

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, 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 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 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 đã lấy phần dư cho ~(10^9 + 7)~.

Input

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

Output

• Ghi ra một số nguyên duy nhất là kết quả bài toán.

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~ (~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~;

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.

Input

• Dòng duy nhất chứa 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~).

Output

• Ghi ra một số nguyên duy nhất là kết quả bài toán.