随着学期末工作量的增加，你接到了给实验室冰箱补充汽水的任务。冰箱有 $s$ 个槽位，每个槽位可容纳 $d$ 瓶汽水，你现在有 $n$ 瓶新汽水需要放入冰箱。冰箱里现有的汽水都是冰镇好的，但新汽水还没冰镇，需要放在冰箱里冷却一段时间才能饮用。

你只能从冰箱前方补充汽水，因此在理想情况下，你会先把冰箱里现有的汽水全部取出，放入 $n$ 瓶新汽水，然后再把旧的冰镇汽水放在新汽水的前面。但现实中，你还要应对两场考试和一个即将到期的作业，你实在太忙了，没法做这些繁琐的工作。

相反，你打算直接把新汽水放在冰箱槽位的前面，并祈祷一切顺利。不过，你仍然可以聪明地选择将新汽水放入哪些槽位。每当有学生来拿汽水时，他们会从冰箱中所有非空槽位中等概率随机选择一个，并从该槽位的前面拿走一瓶。你决定通过合理分配新汽水，使得接下来 $m$ 个学生拿到的汽水都是冰镇汽水的概率最大化。

Picture by Fitness First via Vimeo, cc by

输入格式

输入的第一行包含四个整数 $n, m, s$ 和 $d$ ($1 \le n, m, s, d \le 100$)，分别表示新汽水的数量、需要优化的学生人数、冰箱槽位数量以及每个槽位的容量。接下来一行包含 $s$ 个整数 $c_1, \dots, c_s$ ($0 \le c_i \le d$)，其中 $c_i$ 表示冰箱第 $i$ 个槽位当前已有的汽水数量。

你可以假设冰箱有足够的空间容纳这 $n$ 瓶新汽水。

输出格式

如果存在一种方案使得接下来 $m$ 个学生都能拿到冰镇汽水，则输出 $s$ 个整数，描述一种能使该概率最大化的新汽水补充方案。这 $s$ 个整数中的第 $i$ 个表示放入第 $i$ 个槽位前面的新汽水数量。如果存在多种最优方案，输出其中任意一种即可。否则，如果无法保证接下来 $m$ 个学生都能拿到冰镇汽水，则输出 “impossible”。

样例

输入格式 1

5 3 3 4
0 1 4

输出格式 1

2 3 0

输入格式 2

2 7 6 4
0 1 2 2 0 1

输出格式 2

impossible