Continental Cowngress Voting

The cows have seceded from Farmer John's leadership and formed the first Continental Cowngress. They will vote on N legislative bills. There are M cows in attendance, and each cow casts a vote on exactly two distinct bills. For each vote, a cow votes either Y (yes) or N (no). A cow is satisfied if for at least one of her votes the outcome meets her preference; that is, if she votes Y then the corresponding bill must pass, and if she votes N then the bill must fail.

Your task is to assign each bill a status (pass or fail) in such a way that every cow is satisfied. If no such assignment exists, output IMPOSSIBLE. Otherwise, for each bill output a single character as follows:

• Y if in every valid solution the bill passes,
• N if in every valid solution the bill fails,
• ? if there exist valid solutions where the outcome for the bill differs.

Hint: For a cow that votes Y on bill i and N on bill j, her condition can be modeled by the formula \[ x_i \lor \lnot x_j \] where \(x_i\) is true if bill i passes and false otherwise.

inputFormat

The first line contains two integers: N (the number of bills, 1 ≤ N ≤ 1000) and M (the number of cows, 1 ≤ M ≤ 4000).

Each of the next M lines describes a cow's two votes in the following format:

B_i V_i C_i W_i

Here, B_i and C_i are the 1-indexed bill numbers, and V_i and W_i are each either Y (yes) or N (no), representing the vote on the corresponding bill.

outputFormat

If no assignment of pass/fail to bills exists to satisfy every cow, output a single line containing IMPOSSIBLE.

Otherwise, output a single string of length N where the i-th character corresponds to bill i and is:

• Y if bill i passes in every valid solution,
• N if bill i fails in every valid solution,
• ? if both outcomes for bill i are possible.

sample

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

YN?