The Continental Cowngress

Unhappy with Farmer John's leadership, the cows have left the farm and founded the first Continental Cowngress. Governing by the principle that "every cow gets something she wants," they adopt the following voting scheme.

The $M$ cows in attendance ($1 \le M \le 4000$) vote on $N$ legislative bills ($1 \le N \le 1000$). In the end each bill is either passed or rejected.

Each cow casts a "yes" or "no" vote (written Y or N) on exactly two distinct bills $B_i$ and $C_i$ ($1 \le B_i, C_i \le N$ and $B_i \ne C_i$). The two votes are $VB_i$ and $VC_i$, each Y or N.

The bills must be passed or rejected so that every cow gets her way on at least one of her two votes. For example, if a cow votes "yes" on bill 1 and "no" on bill 2, then in any valid outcome bill 1 must pass or bill 2 must be rejected (or both).

Given every cow's two votes, determine the fate of each bill. If no outcome can satisfy every cow, the answer is IMPOSSIBLE. Otherwise, for each bill report:

• Y — the bill passes in every valid outcome;
• N — the bill is rejected in every valid outcome;
• ? — some valid outcome passes the bill and some other valid outcome rejects it.

• Line 1: two space-separated integers $N$ and $M$.
• Lines 2 to $M+1$: line $i+1$ describes cow $i$ with four space-separated fields — an integer, a vote, another integer, and another vote: $B_i$, $VB_i$, $C_i$, $VC_i$.

• If at least one valid outcome exists, output a single line of $N$ characters; the $i$-th character is Y if bill $i$ must pass, N if bill $i$ must be rejected, or ? if it cannot be determined.
• If no outcome satisfies every cow, output the single line IMPOSSIBLE.