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

Một số được gọi là số nguyên tô đối xứng nếu nó là một số nguyên tố và khi đọc số này từ trái sang phải hay từ phải sang trái đều như nhau. Chẳng hạn số 131 là số nguyên tô đối xứng.

Yêu cầu: Cho trước một số nguyên dương x. Hãy tính xem có bao nhiêu số nguyên tố đối xứng lớn hơn 10 và bé hơn x.

Input: một số nguyên dương x

Output: Ghi số nguyên m thỏa mãn yêu cầu của đề bài.

Giới hạn:

• Có 50% test tương ứng với x ≤ 10^4

• Có 30% test tương ứng với x ≤ 10^6.

• Có 20% test tương ứng với x ≤ 10^10.

Ví dụ:

Input:

150

Output:

3

Có 3 số nguyên tố đối xứng lớn hơn 10 và bé hơn 150 là 131; 101 và 11 .