← 返回题目列表

Codeforces · 808/C

C. 茶会

中文机器翻译题面 查看原题

坡旅甲邀请他所有的朋友参加茶会庆祝节日。他有 n 个杯子,为他的 n 个朋友各一个,容量为 a1,a2,...,an。他的茶壶储存了 w 毫升茶 (w ≤ a1 + a2 + ... + an)。波利卡普想要以这样的方式将茶倒进杯子里:

- 每个杯子将容纳至少一半体积的茶
- 每个杯子将包含整数毫升的茶
- 茶壶中的所有茶都会倒入杯子中
- 所有朋友都会满意。

有杯子 i 的朋友不会满意,如果存在这样的杯子 j,杯子 i 含有的茶比杯子 j 少,但 ai > aj。

对于每个杯子输出,应倒入多少毫升茶。如果不可能倒完所有的茶并满足所有条件则输出-1。

输入

第一行包含两个整数 n 和 w (1 ≤ n ≤ 100, $$1 \leq w \leq \sum_{i=1}^{n} a_i$$)。

第二行包含 n 个数字 a1, a2, ..., an (1 ≤ ai ≤ 100)。

输出

输出每杯应含有多少毫升茶。如果有多个答案,请打印其中任何一个。

如果不可能倒完所有的茶并满足所有条件则输出-1。

示例

输入 #1

2 10
8 7

输出 #1

6 4

输入 #2

4 4
1 1 1 1

输出 #2

1 1 1 1

输入 #3

3 10
9 8 10

输出 #3

-1

注意

在第三个示例中,您应该向第一个杯子倒入至少 5 毫升,向第二个杯子至少倒入 4 毫升,向第三个杯子至少倒入 5 毫升。总计为 14,大于可用的 10 毫升。