题目描述

给定正整数 $n,m$，以及一个长度为 $m$ 的正整数序列

$$A_1,A_2,\ldots,A_m.$$

请构造一个长度为 $m$ 的正整数序列

$$B_1,B_2,\ldots,B_m,$$

使其满足下列等式：

$$1+\frac{2^m-1}{n} = \frac{(A_1+B_1)(A_2+B_2)\cdots(A_m+B_m)}{B_1B_2\cdots B_m}.$$

输入格式

第一行包含两个正整数 $n,m$。

第二行包含 $m$ 个正整数 $A_1,A_2,\ldots,A_m$。

输出格式

输出满足题目等式的正整数序列

$$B_1,B_2,\ldots,B_m,$$

各数之间用空格分隔。

每个 $B_i$ 必须满足：

$$1\le B_i\le 3\times 10^{18}.$$

如果存在多组满足条件的序列，输出任意一组即可。

如果不存在满足条件的序列，输出 -1。

数据范围

$$1\le n\le 10^{15},$$ $$1\le m\le 50,$$ $$1\le A_i\le 1000.$$

样例 1

输入

3 4
1 2 2 1

输出

1 2 16 3

样例 2

输入

10 3
27 283 42

输出

81 1415 672