Farmer John의 지도력에 불만을 가진 소들은 농장에서 탈퇴하고 첫 Continental Cowngress를 만들었습니다. “모든 소가 원하는 것 중 일부를 얻는다”는 원칙에 따라 다음 투표 방식을 정했습니다.
참석한 $M$마리 ($1 \leq M \leq 4{,}000$)가 $N$개 법안 ($1 \leq N \leq 1{,}000$)에 투표합니다. 각 소는 정확히 서로 다른 두 법안 $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$.
- 가결되는 해와 가결되지 않는 해가 모두 있으면
?.
다음 투표 (소마다 두 표)를 생각해 봅시다.
법안
| $1$ | $2$ | $3$ | |
|---|---|---|---|
| 소 $1$ | 찬성 | 반대 | |
| 소 $2$ | 반대 | 반대 | |
| 소 $3$ | 찬성 | 찬성 | |
| 소 $4$ | 찬성 | 찬성 |
모든 소를 만족시키는 해는 두 개입니다.
- 법안 1은 가결 (소 1, 3, 4를 만족).
- 법안 2는 부결 (소 2를 만족).
- 법안 3은 가결 또는 부결 가능 (따라서 두 해가 존재).
실제로 이 두 해뿐이므로 답은 다음 세 글자 문자열입니다.
YN?
입력
표준 입력에서 읽으세요.
- 줄 $1$: 공백으로 구분한 두 정수 $N$, $M$.
- 줄 $2 \ldots M+1$: 줄 $i+1$은 소 $i$의 투표를 공백으로 구분한 네 필드, 정수, 표, 다른 정수, 다른 표로 나타냅니다: $B_i$, $VB_i$, $C_i$, $VC_i$.
출력
표준 출력에 쓰세요.
- 줄 $1$: 길이 $N$인 문자열이며 $i$번째 글자는 법안 $i$가 반드시 가결이면 "$Y$", 반드시 부결이면 "$N$", 투표로 결과를 정할 수 없으면 "?"입니다.
모든 소를 만족시키는 해가 없으면 한 줄에 "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