Cho số nguyên dương ~n~, đếm số cách để chia ~n~ chiếc kẹo thành các phần bằng nhau (mà không phá vỡ hay làm hỏng chiếc kẹo nào).

Input

Gồm một số nguyên dương ~n~ duy nhất. (~n \leq 1000~)

Output

In ra số cách chia ~n~ chiếc kẹo thành các phần bằng nhau.

Sample Test

Input:

10

Output:

4

Giải thích:

Các cách chia thoả mãn là:

• Chia thành ~1~ phần, mỗi phần ~10~ chiếc kẹo.
• Chia thành ~2~ phần, mỗi phần ~5~ chiếc kẹo.
• Chia thành ~5~ phần, mỗi phần ~2~ chiếc kẹo.
• Chia thành ~10~ phần, mỗi phần ~1~ chiếc kẹo.

Biết rằng giá tiền điện được tính như sau:

• Từ KW thứ ~1~ đến ~50~ giá ~1.678~ nghìn đồng/KW
• Từ KW thứ ~51~ đến ~100~ giá ~1.734~ nghìn đồng/KW
• Từ KW thứ ~101~ đến ~200~ giá ~2.014~ nghìn đồng/KW
• Từ KW thứ ~201~ đến ~300~ giá ~2.536~ nghìn đồng/KW
• Từ KW thứ ~301~ đến ~400~ giá ~2.834~ nghìn đồng/KW
• Từ KW thứ ~401~ trở đi giá ~2.927~ nghìn đồng/KW

Cho một số nguyên ~x~ là số KW điện tiêu thụ của một hộ gia đình. Tính số tiền mà hộ gia đình đó phải trả.

Input

Gồm một số nguyên ~x~ duy nhất. (~1 \leq x \leq 1000~)

Output

In ra số tiền phải trả theo đơn vị đồng.

Sample Test 1

Input:

10

Output:

16780

Sample Test 2

Input:

468

Output:

1108036

Note:

• ~50~ số điện đầu (từ ~1~ đến ~50~) có giá ~1678 \times 50 = 83900~ (đồng)
• ~50~ số điện tiếp (từ ~51~ đến ~100~) có giá ~1734 \times 50 = 86700~ (đồng)
• ~100~ số điện tiếp (từ ~101~ đến ~200~) có giá ~2014 \times 100 = 201400~ (đồng)
• ~100~ số điện tiếp (từ ~201~ đến ~300~) có giá ~2536 \times 100 = 253600~ (đồng)
• ~100~ số điện tiếp (từ ~301~ đến ~400~) có giá ~2834 \times 100 = 283400~ (đồng)
• ~68~ số điện cuối (từ ~401~ đến ~468~) có giá ~2927 \times 68 = 199036~ (đồng)
• Tổng số tiền phải trả là ~83900 + 86700 + 201400 + 253600 + 283400 + 199036 = 1108036~ (đồng)

Cho mảng ~A~ gồm ~N~ phần tử, mảng ~B~ gồm ~M~ phần tử. Bạn sẽ thực hiện ~N - M + 1~ thao tác, trong đó thao tác thứ ~i~ diễn ra như sau:

Xét các phần tử ~A_i, A_{i+1}, \ldots, A_{i + M - 1}~ và tăng chúng lần lượt lên ~B_1, B_2, \ldots, B_M~ (Hay nói cách khác, ~A_{i + j - 1}~ sẽ được tăng lên ~B_j~).

Bạn cần in ra dãy ~A~ sau khi thực hiện hết các thao tác.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~M~ ~(1 \le M \le N \le 10^5)~.
• Dòng thứ hai gồm ~N~ số nguyên dương miêu tả dãy ~A~ ~(A_i \le 10^9)~.
• Dòng thứ ba gồm ~B~ số nguyên dương miêu tả dãy ~B~ ~(B_i \le 10^9)~.

Output:

• In ra dãy ~A~ sau khi thực hiện các thao tác.

Subtask:

• Subtask ~1~ (~30\%~ số điểm): ~N,M \le 1000~
• Subtask ~3~ (~30\%~ số điểm): ~B_i = 1~
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm

Sample Input 1

3 2
5 1 3
1 2

Sample Output 1

6 4 5

Có hai robot đang chuyển động thẳng đều, cùng chiều trên cùng một con đường, robot thứ nhất đang ở vị trí ~S_1~ đang di chuyển với vận tốc là ~V_1 \ m/s~, robot thứ hai đang ở vị trí ~S_2~ di chuyển với vận tốc là ~V_2 \ m/s~. Hỏi sau bao nhiêu lâu thì hai robot gặp nhau?

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

• Dòng đầu tiên gồm số nguyên dương ~S_1~ mô tả vị trí của robot thứ nhất~;~
• Dòng thứ hai gồm số nguyên dương ~V_1~ mô tả vận tốc của robot thứ nhất~;~
• Dòng thứ ba gồm số nguyên dương ~S_2~ mô tả vị trí của robot thứ hai~;~
• Dòng thứ tư gồm số nguyên dương ~V_2~ mô tả vận tốc của robot thứ hai.

Các đơn vị khoảng các được tính bằng mét, thời gian được tính bằng giây và ~S_1≠S_2 \ ;~ ~S_1,S_2,V_1,V_2≤10^9~.

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

In ra một số nguyên là phần nguyên của kết quả - thời gian mà hai robot gặp nhau. Nếu hai robot không thể gặp nhau thì in ra ~-1~.

Ví dụ

Input

2
5
7
3

Output

2

Giải thích: Sau ~2.5~ giây hai robot sẽ gặp nhau:

• ~2+5 \times 2.5=14.5 ~.
• ~7+3 \times 2.5=14.5~ .

Phần nguyên của ~2.5~ là ~2~.

Input

2
3
7
5

Output

-1

Giải thích: Hai robot càng đi càng xa nhau.

Cho dãy số gồm ~n~ số nguyên ~a_1, a_2, …, a_n~ và ~2~ số nguyên không âm ~L, R (L ≤ R)~.

Yêu cầu: Đếm số cặp ~(i, j)~ thỏa mãn điều kiện: ~i ≤ j~ và ~L ≤ |a_i+…+a_j| ≤ R~.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~n, L, R~ ~(n ≤ 3*10^5 ; 0 ≤ L ≤ R ≤ 10^9)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2,…, a_n (|a_i|≤ 10^9)~

Output

• Một số nguyên duy nhất là số lượng cặp ~(i, j)~ đếm được.

Subtask

• Subtask 1 (~30\%~ số điểm): ~n \le 10^3~.
• Subtask 2 (~50\%~ số điểm): ~n \le 10^5~ và ~a_i \ge 0~.
• Subtask 3 (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Test

Input

3 0 1
1 -1 2

Output

4

Sau khi chơi với ngọc chán chê, Tí sắp ~n~ viên ngọc ra một đường thẳng và bắt đầu nhìn ngắm chúng. Tí nhận thấy rằng có không quá ~k~ màu ngọc khác nhau trên bàn và viên ngọc thứ ~i~ từ trái sang thì có màu ~a_i~. Tí muốn chia dãy ngọc thành các đoạn liên tiếp sao cho mỗi đoạn đều có đủ ~k~ màu. Hỏi Tí có bao nhiêu cách chia thỏa mãn như vậy?

Yêu cầu: In số cách chia thỏa mãn sau khi ~\mod 10^9+7~

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,k~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~.

Output

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

Constraints

• ~1\leq k\leq n\leq 10^6~
• ~1\leq a_i\leq k~

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~k = 1~.
• Subtask ~2~ (~20\%~ số điểm): ~n\leq 5000~.
• Subtask ~3~ (~20\%~ số điểm): ~n\leq 10^5, k\leq 100~.
• Subtask ~4~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Example

Sample Input ~1~

5 2
1 2 2 1 2 

Sample Ouput ~1~

3

Explanation

Có ~3~ cách chia như sau: ~(1\ 2) | (2\ 1\ 2), (1\ 2\ 2) | (1\ 2)~, hoặc ~(1\ 2\ 2\ 1\ 2)~.

Cho mảng ~A~ gồm ~n~ số nguyên và ~q~ truy vấn, mỗi truy vấn có dạng ~(l, r)~. Nhiệm vụ của bạn là in ra giá trị nhỏ nhất trong các phần tử ~A_l, A_{l+1}, \ldots, A_r~ cho mỗi truy vấn.

Input

• Dòng đầu tiên gồm hai số nguyên ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên ~A_i~.
• ~q~ dòng tiếp theo mỗi dòng gồm hai số nguyên ~l, r~.

Output

• In ra đáp án cho mỗi truy vấn. Nếu có nhiều chỉ số thỏa mãn, in ra chỉ số nhỏ nhất.

Điều kiện

• ~1 \le n, q \le 2 \times 10^5~.
• ~1 \le A_i \le 10^9~.
• ~1 \le l \le r \le n~.

Ví dụ

Input:

4 2
1 3 4 1
1 4
2 3

Output:

1
3