You need to hire some people to paint a fence. The fence is composed of $10000$ contiguous sections, numbered from $1$ to $10000$.

You get some offers from painters to help paint the fence. Each painter offers to paint a contiguous subset of fence sections in a particular color. You need to accept a set of the offers, such that:
 - Each section of the fence is painted.
 - At most 3 colors are used to paint the fence.

If it is possible to satisfy these two requirements, find the minimum number of offers that you must accept.

-----Input-----
The first line of input contains an integer $N$, the number of offers. Then follow $N$ lines, one for each offer, each containing “$C$ $A$ $B$” where $C$ is the color, which is an uppercase string of up to 10 letters, $A$ is the first section and $B$ is the last section to be painted. $1 \leq A \leq B \leq 10000$.

You may assume that $1 \leq N \leq 300$.

-----Output-----
Output one line containing the number of offers that need to be accepted, or “IMPOSSIBLE” if there is no acceptable set of offers.

-----Examples-----
Sample Input 1:
2
BLUE 1 5000
RED 5001 10000
Sample Output 1:
2

Sample Input 2:
3
BLUE 1 6000
RED 2000 8000
WHITE 7000 10000
Sample Output 2:
3

Sample Input 3:
4
BLUE 1 3000
RED 2000 5000
ORANGE 4000 8000
GREEN 7000 10000
Sample Output 3:
IMPOSSIBLE

Sample Input 4:
2
BLUE 1 4000
RED 4002 10000
Sample Output 4:
IMPOSSIBLE

Source: kattis | Difficulty: HARD


Solutions: