Five Hundred Arhats

Time limit2sMemory limit1024 MB

Summary

Given n arhat strides, find non-negative step counts whose weighted sum is exactly K, or report -1 if no such walk exists.

Level: Medium6 of 10
Topics: Number theory, Dynamic programming, Shortest path
Solved: No attempts yet

Problem

The Goryeo Five Hundred Arhats painting, designated National Treasure No. 1883, shows 500 arhats who have attained enlightenment. Hanbyeol, who is fond of history, liked the painting so much that he hung it in his room and went to sleep. That night he had a strange dream in which he met all 500 arhats. While he spent a pleasant time with them, he noticed something unusual about their steps. Each arhat's stride is a positive integer that stays the same for that arhat, but two different arhats may have strides that are equal or different.

As a programmer with a lively curiosity, Hanbyeol wondered: Is there a way for the arhats to walk so that the total distance they cover is exactly $K$ ?

To answer his question, determine whether the arhats can walk in such a way, and if so, find an example.

Input

The first line contains $n$ and $K$ , the number of arhats and the total distance. From the second line through line $n+1$ , line $i$ contains one integer $a_i$ , the stride of arhat $i-1$ .

Output

If no way of walking makes the total distance equal to $K$ , print $-1$ . Otherwise, print $n$ non-negative integers. Each integer is the number of steps taken by an arhat, and the printed values must satisfy the conditions of the problem.

Constraints

$1\le n\le 500$
$1\le K\le 10^{18}$
$1\le a_i \le 250000$

Examples2

Example 1
Input
```
3 10
1 2 4
```
Expected output
```
0 1 2
```
Example 2
Input
```
5 9
2 4 6 8 10
```
Expected output
```
-1
```