Farmer John の指導に不満を持った牛たちは農場から離脱し、最初の Continental Cowngress を設立しました。「どの牛も望みの一部を得る」という原則で、次の投票制度を決めました。
出席する $M$ 頭 ($1 \leq M \leq 4{,}000$) は $N$ 個 ($1 \leq N \leq 1{,}000$) の法案に投票します。各牛はちょうど 2 つの異なる法案 $B_i$ と $C_i$ ($1 \leq B_i, C_i \leq N$) に賛成か反対（入力で '$Y$' または '$N$'）を投じます。それぞれ $VB_i$ ($VB_i \in \{\text{Y}, \text{N}\}$)、$VC_i$ ($VC_i \in \{\text{Y}, \text{N}\}$) とします。
各牛が少なくとも一票について希望通りになるように可決・否決を決めます。例えば Bessie が法案 1 に賛成、法案 2 に反対なら、有効な解では法案 1 が可決されるか法案 2 が否決される必要があります（両方でも構いません）。
全投票から、規則に従う各法案の結果を求めてください。解がなければ "IMPOSSIBLE" を出力します。解が一つ以上あれば、各法案について次を表示します。
- 全ての解で可決されるなら $Y$。
- 全ての解で否決されるなら $N$。
- 可決される解と否決される解の両方があるなら
?。
次の投票（各牛 2 票）を考えます。
法案
| $1$ | $2$ | $3$ | |
|---|---|---|---|
| 牛 $1$ | 賛成 | 反対 | |
| 牛 $2$ | 反対 | 反対 | |
| 牛 $3$ | 賛成 | 賛成 | |
| 牛 $4$ | 賛成 | 賛成 |
全ての牛を満足させる解は二つあります。
- 法案 1 は可決（牛 1、3、4 を満足させます）。
- 法案 2 は否決（牛 2 を満足させます）。
- 法案 3 は可決でも否決でもよい（これにより解が二つになります）。
実際、解はこの二つだけなので、答えは次の 3 文字の文字列です。
YN?
入力
標準入力から読み込んでください。
- 行 $1$：空白区切りの 2 整数 $N$ と $M$。
- 行 $2 \ldots M+1$：行 $i+1$ は牛 $i$ の投票を空白区切りの 4 フィールド、整数、票、別の整数、別の票の順に示します：$B_i$、$VB_i$、$C_i$、$VC_i$。
出力
標準出力に書き出してください。
- 行 $1$：$N$ 文字の文字列で、$i$ 番目は法案 $i$ が必ず可決なら "$Y$"、必ず否決なら "$N$"、投票から結果を確定できなければ "?" です。
全ての牛を満足させる解がなければ、1 行に "IMPOSSIBLE" を出力してください。
入出力例
入力 1
3 4 1 Y 2 N 1 N 2 N 1 Y 3 Y 1 Y 2 Y
出力 1
YN?
問題作成：Louis Wasserman, 2010