Problem G. Guess the array

Author:N. Grebenyuk   Time limit:2 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Aleksey lost his favourite array a! He remembers that the array consisted of n non-negative integers, and its sum was equal to sum.

Recently Aleksey found his calculations on this array. His calculations consist of n numbers bi such that

bi = (ai + ai + 1)mod k for 1 ≤ i < n

bn = (an + a1)mod k (ai — favourite array numbers)

Help Aleksey to find any correct favourite array a corresponding to the array b, or tell him that he has made a mistake, and there is no such array. Notice, that all elements of source array are non-negative integers that are not greater than 104.

Input format

The first line contains three integers n, k, sum.

The next line contains n non-negative integers bi.

Output format

If the answer exists, print "YES" in the first line and n space separated numbers of array a in the second line. If there are multiple answers, print any of them.

Print "NO" if there is no such array.

Constraints

2 ≤ n, k ≤ 104

0 ≤ sum ≤ 109

0 ≤ ai ≤ 104

0 ≤ bi < k

Sample tests

No. Standard input Standard output
1
6 4 21
3 1 3 1 3 3
YES
1 2 3 4 5 6
2
2 7 32
4 4
YES
11 21
3
6 4 21
1 3 2 1 3 2
NO

0.108s 0.024s 13