Недовольные руководством Farmer John, коровы отделились от фермы и образовали первый Continental Cowngress. По принципу «каждая корова получает что-то желаемое» они выбрали такую систему голосования:
Присутствуют $M$ коров ($1 \leq M \leq 4{,}000$), голосующих по $N$ законопроектам ($1 \leq N \leq 1{,}000$). Каждая голосует «за» или «против» (ввод '$Y$' или '$N$') ровно по двум различным проектам $B_i$ и $C_i$ ($1 \leq B_i, C_i \leq 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$-й символ — "$Y$", если проект $i$ обязан пройти, "$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