Niezadowolone z przywództwa Farmer John krowy odłączyły się od farmy i utworzyły pierwszy Continental Cowngress. Według zasady „każda krowa dostaje coś, czego chce” wybrały ten system:
Obecne $M$ krów ($1 \leq M \leq 4{,}000$) głosuje nad $N$ ustawami ($1 \leq N \leq 1{,}000$). Każda głosuje tak lub nie (wejście '$Y$' lub '$N$') nad dokładnie dwiema różnymi ustawami $B_i$ i $C_i$ ($1 \leq B_i, C_i \leq N$). Głosy to $VB_i$ ($VB_i \in \{\text{Y}, \text{N}\}$) i $VC_i$ ($VC_i \in \{\text{Y}, \text{N}\}$).
Decyzje muszą zgadzać się z co najmniej jednym głosem każdej krowy. Jeśli Bessie głosuje tak nad ustawą 1 i nie nad 2, każda poprawna odpowiedź przyjmuje ustawę 1 lub odrzuca 2 (lub obie rzeczy).
Na podstawie głosów ustal wyniki zgodne z zasadami. Bez rozwiązania wypisz "IMPOSSIBLE". Jeśli istnieje co najmniej jedno, podaj dla każdej ustawy:
- $Y$, jeśli zostaje przyjęta w każdym rozwiązaniu.
- $N$, jeśli zostaje odrzucona w każdym rozwiązaniu.
?, jeśli istnieją rozwiązania przyjmujące ją oraz takie, które jej nie przyjmują.
Rozważ poniższe głosy (po dwa na krowę):
Ustawy
| $1$ | $2$ | $3$ | |
|---|---|---|---|
| Krowa $1$ | TAK | NIE | |
| Krowa $2$ | NIE | NIE | |
| Krowa $3$ | TAK | TAK | |
| Krowa $4$ | TAK | TAK |
Dwa rozwiązania zadowalają wszystkie krowy:
- Ustawa 1 przechodzi (zadowala krowy 1, 3 i 4).
- Ustawa 2 zostaje odrzucona (zadowala krowę 2).
- Ustawa 3 może przejść lub nie (dlatego są dwa rozwiązania).
To jedyne rozwiązania, więc odpowiedź jest poniższym trzyznakowym napisem:
YN?
Wejście
Czytaj ze standardowego wejścia.
- Wiersz $1$: dwie liczby całkowite $N$ i $M$, rozdzielone spacją.
- Wiersze $2 \ldots M+1$: wiersz $i+1$ opisuje głosy krowy $i$ czterema polami rozdzielonymi spacjami — liczba, głos, druga liczba, drugi głos: $B_i$, $VB_i$, $C_i$, $VC_i$.
Wyjście
Pisz na standardowe wyjście.
- Wiersz $1$: napis długości $N$, którego znak $i$ to "$Y$", jeśli ustawa $i$ musi przejść, "$N$", jeśli musi zostać odrzucona, lub "?", gdy głosy nie rozstrzygają wyniku.
Jeśli nie ma rozwiązania zadowalającego każdą krowę, wypisz jeden wiersz "IMPOSSIBLE".
Przykład
Wejście 1
3 4 1 Y 2 N 1 N 2 N 1 Y 3 Y 1 Y 2 Y
Wyjście 1
YN?
Autor zadania: Louis Wasserman, 2010