你是一家广告公司的经理，正在寻找最优秀的网红来推广客户的产品。因为你想组建一支高效的团队，所以你正在寻找那些在共同出镜时能对其他网红产生积极影响的网红。

与此同时，$N$ 名网红在一栋豪宅里聚集了一周，试图吸引粉丝。在这一周里，一些网红两两合作制作了视频。由于网红们彼此之间竞争非常激烈，每个网红制作的视频数量都相同。又因为网红们很懒，没有人制作了超过 $7$ 个视频。

在这一周结束时，每个网红要么涨粉了，要么掉粉了，要么注销了他们的社交媒体账号。你想给每个网红 $i$（包括那些注销了账号的网红）分配一个整数评分 $s_i$，用来衡量他们对合作过的网红的影响。具体来说，对于每个网红 $i$，令 $S_i$ 为所有与网红 $i$ 合作制作过视频的网红 $j$ 的 $s_j$ 之和。那么，对于每个涨粉的网红，应当满足 $S_i > 0$；对于每个掉粉的网红，应当满足 $S_i < 0$。对于注销了账号的网红 $i$，$S_i$ 没有限制。

计算这样一种评分分配方案 $s_i$，或者判断是否不可能实现。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$，其中 $2 \le N, M \le 10^5$。这表示有 $N$ 个网红，编号为 $1$ 到 $N$，他们总共制作了 $M$ 个视频。

第二行包含一个长度为 $N$ 的字符串 $f$，其中第 $i$ 个字符如果为 + 表示网红 $i$ 涨粉了，为 - 表示网红 $i$ 掉粉了，为 ? 表示网红 $i$ 注销了账号。

接下来有 $M$ 行，每行包含两个不同的整数 $a$ 和 $b$，表示网红 $a$ 和 $b$ 共同制作了一个视频。

保证所有网红制作的视频数量 $k$ 均相同，其中 $1 \le k \le 7$。同时保证任意两个网红之间最多共同制作了 $1$ 个视频。

输出格式

输出 $N$ 行，其中第 $i$ 行包含一个整数 $-10^9 \le s_i \le 10^9$，满足题目中的条件。如果无法满足条件，则输出单词 Impossible。如果存在多个解，输出任意一个。

如果存在解，保证存在一个满足以下条件的解：

$$\sum_{i=1}^N s_i^2 \le 10^5$$

样例

输入样例 1

6 9
--++--
1 2
2 3
3 4
4 5
5 6
6 1
1 5
2 4
3 6

输出样例 1

-2
3
1
0
-2
-2

输入样例 2

6 9
?-++--
1 2
2 3
3 4
4 5
5 6
6 1
1 5
2 4
3 6

输出样例 2

-1
1
0
0
0
0

输入样例 3

4 4
++--
1 2
1 4
3 2
3 4

输出样例 3

Impossible