Prizes

Interview

Time limit2sMemory limit256 MB

Summary

Distribute d candies among n ranked teams so that per-member counts strictly decrease by rank and sum to exactly d, or report impossibility.

Level: Medium4 of 10
Topics: Greedy, Math, Implementation
Solved: No attempts yet

Problem

Andrey Sergeyevich works as a kindergarten teacher. Recently he came up with a new fun game, and to take part in it all the children split into n teams. As prizes for the participants, Andrey Sergeyevich prepared d candies.

After the game it turned out that the team in i-th place had exactly xi participants.

Now Andrey Sergeyevich faces a difficult task: he has to distribute the candies. The following conditions must hold.

All members of one team must receive the same number of candies: let the members of the team in i-th place receive ai candies each.
Every child must receive at least one candy: ai > 0.
Members of a team in a higher place must receive more candies: if i < j, then ai > aj.
All candies must be distributed: a1x1 + a2x2 + ... + anx**n = d.

Help Andrey Sergeyevich hand out the candies to the children, or report that this is impossible.

Input

The first line contains two integers n and d (1 ≤ n ≤ 100, 1 ≤ d ≤ 106). The second line contains n integers x1, ..., xn (1 ≤ xi ≤ 100 for all i from 1 to n).

Output

If the candies can be distributed, print YES on the first line, and on the second line print n integers: a1, a2, ..., a**n. If the candies cannot be distributed in the described way, print NO.

Examples2

Example 1
Input
```
2 100
2 1
```
Expected output
```
YES
34 32
```
Example 2
Input
```
2 6
2 1
```
Expected output
```
NO
```