407344: GYM102769 D Defend City

Alex is a professional computer game player.

These days, Alex is playing a war strategy game. His city can be regarded as a rectangle on the Cartesian plane. Its lower-left corner is $$$(0,0)$$$, and its upper-right corner is $$$(n+1,n+1)$$$.

Alex builds $$$n$$$ defensive towers to protect the city. The defensive tower $$$i$$$ is located at $$$(x_i,y_i)$$$, and its direction is $$$d_i$$$. The defensive towers with different directions protect different areas:

• if $$$d_i = 1$$$, the defensive tower $$$i$$$ can protect area $$$\{(a,b)\mid a \ge x_i, b \ge y_i\}$$$;
• if $$$d_i = 2$$$, the defensive tower $$$i$$$ can protect area $$$\{(a,b)\mid a \le x_i, b \ge y_i\}$$$;
• if $$$d_i = 3$$$, the defensive tower $$$i$$$ can protect area $$$\{(a,b)\mid a \le x_i, b \le y_i\}$$$;
• if $$$d_i = 4$$$, the defensive tower $$$i$$$ can protect area $$$\{(a,b)\mid a \ge x_i, b \le y_i\}$$$.

If Alex launches $$$e$$$ defensive towers, he will consume $$$e$$$ energy per hour. He wants to launch as few defensive towers as possible so that all points $$$(x,y)\ (x,y\in \mathbb{R},0 \le x,y \le n+1)$$$ in his city can be protected. Can you find the optimal strategy?

The first line of the input gives the number of test cases, $$$T\ (1 \le T \le 10^4)$$$. $$$T$$$ test cases follow.

For each test case, the first line contains an integer $$$n\ (1 \le n \le 10^6)$$$, where $$$n$$$ is the number of defensive towers.

Each of the following $$$n$$$ lines contains three integers $$$x_i,y_i\ (1 \le x_i, y_i \le n)$$$ and $$$d_i\ (1 \le d_i \le 4)$$$, representing the position and direction of defensive tower $$$i$$$.

The sum of $$$n$$$ in all test cases doesn't exceed $$$5 \times 10^6$$$.

For each test case, output one line containing "Case #x: y", where $$$\texttt{x}$$$ is the test case number (starting from $$$1$$$), and $$$\texttt{y}$$$ is the minimum number of defensive towers. If it is impossible to protect all the city, output "Impossible" (without quote).

2
3
1 1 1
2 2 2
3 3 3
4
1 1 1
2 2 3
2 1 2
1 2 4

Case #1: Impossible
Case #2: 4