Double bill screens

Assign the films of a one-day festival to its two screens, screen 1 and screen 2, so that every programming rule holds.

There are n films, numbered 0 to n - 1, and every film plays on exactly one of the two screens. rules is a list of [kind, i, j] entries. In every rule i and j are film numbers (they may be equal); the rule kinds are:

• "apart": films i and j must be on different screens.
• "same": films i and j must be on the same screen.
• "not1": films i and j must not both be on screen 1.
• "not2": films i and j must not both be on screen 2.
• "on": film i must be on screen j (here j is 1 or 2, not a film number).

A rule with i == j applies to that single film as written, so ["apart", 4, 4] can never be satisfied and ["not1", 4, 4] means film 4 is not on screen 1.

Many assignments can be valid. The festival director wants the one that sends films to screen 1 as eagerly as possible: compare assignments film by film from film 0, and prefer the assignment that has screen 1 at the first film where two assignments differ.

Input: n and rules.

Output: a string of n characters, "1" or "2", where character k is the screen of film k in the preferred assignment. If no assignment satisfies every rule, return "IMPOSSIBLE". With n = 0 the answer is the empty string "".

There can be a few hundred rules, so trying every assignment, or backtracking film by film, is far too slow.