Cho 2 mảng A, B có n phần tử. Phần tử B[i] là trung bình cộng của i phần tử đầu tiên của mảng A. Cho các giá trị của mảng B, tìm mảng A.

Input:

 Dòng đầu: số nguyên n (1 ≤ n ≤ 10^6)

 Dòng thứ hai ghi b số nguyên b1 b2 … bn của mảng B. (|bi| ≤ 10^9)

Output: Ghi n số là các phần tử của mảng A

Ví dụ:

Input:

5
15 20 5 15 30

Output:

15 25 -25 45 90

Cho một xâu gồm n ký tự, trong đó có m ký tự #, mỗi ký tự # như vậy sẽ được thay thế bởi 1 trong k ký tự (trong input sẽ cho). Tìm chuỗi có thứ tự từ điển bé thứ x.

Input:

 Dòng đầu: 4 số nguyên n, m, k, x. (1 ≤ n ≤ 500; 1 ≤ x, m ≤ n; 1 ≤ k ≤ 26)

 Dòng thứ hai: xâu n ký tự.

 m dòng tiếp theo, mỗi dòng chứa k ký tự là những phương án thay thế ký tự # thứ i.

Output: ghi chuỗi có thứ tự từ điển bé thứ x.

Input:

16 3 2 6
pro#ramm#ngis#un
ag
iy
ef

Output:

programmingisfun

Giải thích:

Sau khi thế và sắp xếp thì có 8 xâu như sau:

1. proarammingiseun

2. proarammingisfun

3. proarammyngiseun

4. proarammyngisfun

5. programmingiseun

6. programmingisfun

7. programmyngiseun

8. programmyngisfun

Cho một mảng A có n phần tử, xét tất cả các đoạn con (không liên tiếp) có K phần tử của A, tính tổng của các số lớn nhất của các đoạn con này và modulo 10^9 + 7.

Input:

 Dòng đầu: 2 số nguyên n, K (1 ≤ n ≤ 10^5; 1 ≤ K ≤ 50)

 Dòng thứ hai: mảng A. (1 ≤ Ai ≤ 106)

Output: ghi tổng tìm được

Ví dụ:

Input:

4 2
6 7 6 5

Output:

39