Coins

There are coins available in various fixed denominations, expressed in kopecks (for example, 3 and 5 kopecks), and they are available in unlimited quantities. Write a program, COINS, that:

1. Determines if a given amount S (in kopecks) can be formed using the available coin denominations.

2. If possible, represents this amount using the fewest number of coins.

Input

The input file begins with the amount S (0 ≤ S ≤ 1000000000) on the first line. The second line contains N, the number of different denominations (1 ≤ N ≤ 20). The following N lines list the denominations A_{1}, A_{2}, ..., A_{N} in ascending order, where each denomination satisfies (0 < A_1 < A_2 < ... < A_N ≤ 1000000000).

Output

The output file should start with the symbol "+" on the first line if the amount S can be represented using the given denominations, or the symbol "-" if it cannot. If a representation is possible, the subsequent N lines should specify the number of coins of each denomination required to form the amount S using the minimum number of coins.

Examples