hehe 蚤在下山市发现了当地特色的玩具小火车！

hehe 蚤立马迫不及待的开始玩了起来。小火车运行在一个长度为 $p$ 的圆形铁轨上。小火车上有 $n$ 个拨杆，把第 $i$ 个拨杆向左拨可以让小火车向前开 $a_i$ 单位距离，而向右拨可以让小火车向后开相同距离。每个拨杆最多被拨一次。

hehe 蚤想让小火车开回原位，他想让你告诉他，该怎么拨拨杆才能让小火车运行后回到原位。你不必拨每一个拨杆，但不能一个拨杆都不拨，否则就不好玩了。

显然拨杆的顺序并不会影响最后火车的位置，所以你只需要输出每个拨杆的拨法。

一句话题意：给定 $n,p$ 和长度为 $n$ 的整数序列 $a$，你需要输出整数序列 $b$ 满足：

1. $b_i\in \{-1,0,1\}$ 且不全为 $0$。

2. $\sum a_ib_i\equiv 0\pmod p$

保证 $2^n\gt p$。

输入格式

第一行两个整数 $n,p$ 表示集合大小和模数。

第二行 $n$ 个整数 $a_i$ 表示集合内容。

输出格式

若无解输出 IMPOSSIBLE。

否则输出一行 $n$ 个 $-1$ 到 $1$ 的整数，第 $i$ 个整数为 $-1$ 表示第 $i$ 个拨杆向左拨，$1$ 表示第 $i$ 个拨杆向右拨，$0$ 表示第 $i$ 个拨杆将不会被操作。

如有多组解输出任意一组均可。

样例一

input

3 7
1 2 3

output

1 1 -1

explanation

小火车会向后开 $1+2=3$ 单位距离，向前开 $3$ 单位距离，回到原位。

样例二

见附件下载中的 ex_train2.in 和 ex_train2.ans。

数据范围

数据随机是指：$a_i$ 在 $[0,p)$ 范围内独立均匀随机。

第 $3$ 个子任务有 $5$ 组测试数据。

对于所有数据，保证 $1\leq p\lt 2^n, 1\leq n\leq 40,0\leq a_i\lt p$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$