Problem G
Influencers

You are a manager at an ad agency looking to hire the best new influencers to promote your clients’ products. Since you want to build an effective team, you’re looking for influencers who have positive effects on other influencers when they appear together.

Meanwhile, $n$ influencers gathered in a mansion for a week to try to gain followers. Over the course of the week, some pairs of influencers produced videos together. Since the influencers are very competitive with each other, each influencer produced the same number of videos. Since the influencers are also lazy, no one produced more than $7$ videos.

At the end of the week, each influencer had either gained followers, lost followers, or deleted their social media accounts. You want to assign each influencer $i$ (including the ones who deleted their accounts) an integer score $s_ i$ that measures their effect on the influencers that they worked with. Specifically, for each influencer $i$, let $S_ i$ be the sum of $s_ j$ over all $j$ such that influencers $i$ and $j$ made a video together. Then it should be true that for every influencer that gained followers, $S_ i > 0$, and for every influencer that lost followers, $S_ i < 0$. There is no constraint on $S_ i$ for influencers $i$ who deleted their accounts.

Calculate such an assignment of scores $s_ i$, or determine that it is impossible.

Input

The input starts with one line containing integers $N$ and $M$ where $2 \leq N,M \leq 10^5$. This denotes that there are $N$ influencers labeled $1$ through $N$ and they produced a total of $M$ videos.

The second line contains an $n$-character string $f$, where the $i$th character of $f$ will be + if influencer $i$ gained followers, - if influencer $i$ lost followers, and ? if influencer $i$ deleted their account.

Finally, there are $M$ lines each containing distinct integers $a,b$, indicating that influencers $a$ and $b$ produced a video together.

It is guaranteed that all influencers produced the same number of videos $k$, where $1 \leq k \leq 7$. It is also guaranteed that each pair of influencers produced at most $1$ video together.

Output

Output $N$ lines, where line $i$ contains the integer $-10^9 \leq s_ i \leq 10^9$, satisfying the conditions in the problem, or the word “Impossible” if the conditions cannot be satisfied. If there are multiple solutions, print any.

If a solution exists, it is guaranteed that a solution exists which satisfies the conditions

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

-2
3
1
0
-2
-2

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

-1
1
0
0
0
0

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

Impossible