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 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
Name |
---|