Không hài lòng với lãnh đạo của Farmer John, đàn bò tách khỏi trang trại và thành lập Continental Cowngress đầu tiên. Với nguyên tắc «mỗi bò nhận được điều gì đó mình muốn», chúng chọn cách bỏ phiếu sau:

$M$ bò tham dự ($1 \leq M \leq 4{,}000$) bỏ phiếu cho $N$ dự luật ($1 \leq N \leq 1{,}000$). Mỗi bò bỏ phiếu có hoặc không (đầu vào '$Y$' hoặc '$N$') cho đúng hai dự luật khác nhau $B_i$, $C_i$ ($1 \leq B_i, C_i \leq N$). Phiếu tương ứng là $VB_i$ ($VB_i \in \{\text{Y}, \text{N}\}$), $VC_i$ ($VC_i \in \{\text{Y}, \text{N}\}$).

Quyết định phải đúng ý mỗi bò ở ít nhất một phiếu. Nếu Bessie đồng ý dự luật 1 và phản đối 2, mọi nghiệm hợp lệ phải thông qua 1 hoặc bác bỏ 2 (hoặc cả hai).

Cho các phiếu, xác định kết quả theo quy tắc. Nếu vô nghiệm, in "IMPOSSIBLE". Nếu có ít nhất một nghiệm, với mỗi dự luật hiển thị:

• $Y$ nếu được thông qua trong mọi nghiệm.
• $N$ nếu bị bác bỏ trong mọi nghiệm.
• ? nếu có nghiệm thông qua và có nghiệm không thông qua.

Xét các phiếu sau (hai phiếu mỗi bò):

Dự luật

Hai nghiệm làm mọi bò hài lòng:

• Dự luật 1 được thông qua (thỏa bò 1, 3, 4).
• Dự luật 2 bị bác bỏ (thỏa bò 2).
• Dự luật 3 có thể thông qua hoặc bác bỏ (do đó có hai nghiệm).

Đây thực sự là hai nghiệm duy nhất, nên đáp án là chuỗi ba ký tự sau:

YN?

Dữ liệu vào

Đọc từ đầu vào chuẩn.

• Dòng $1$: hai số nguyên $N$, $M$, cách nhau bởi dấu cách.
• Dòng $2 \ldots M+1$: dòng $i+1$ mô tả phiếu của bò $i$ với bốn trường cách nhau bởi dấu cách: số nguyên, phiếu, số nguyên khác, phiếu khác, $B_i$, $VB_i$, $C_i$, $VC_i$.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

• Dòng $1$: chuỗi $N$ ký tự, ký tự $i$ là "$Y$" nếu dự luật $i$ phải thông qua, "$N$" nếu phải bác bỏ, hoặc "?" nếu không xác định được kết quả từ các phiếu.

Nếu không có nghiệm thỏa mọi bò, in một dòng "IMPOSSIBLE".

Ví dụ

Dữ liệu vào 1

3 4
1 Y 2 N
1 N 2 N
1 Y 3 Y
1 Y 2 Y

Dữ liệu ra 1

YN?

Tác giả bài toán: Louis Wasserman, 2010