题目描述

Alex 是一位电竞选手。

这些天，Alex 正在玩一款战争策略游戏。他的城池可以被看做笛卡尔平面上的一个矩形，它的左下角为 $(0,0)$，右上角为 $(n+1,n+1)$。

Alex 建造了 $n$ 座防御塔来保卫城池。防御塔 $i$ 位于 $(x_i,y_i)$，方向为 $d_i$。方向不同的防御塔能够保护不同的区域，具体来说：

• 若 $d_i = 1$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \ge x_i, b \ge y_i\}$；
• 若 $d_i = 2$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \le x_i, b \ge y_i\}$；
• 若 $d_i = 3$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \le x_i, b \le y_i\}$；
• 若 $d_i = 4$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \ge x_i, b \le y_i\}$。

如果 Alex 启用了 $e$ 座防御塔，他每小时将会消耗 $e$ 的单位能量。他想要启用尽量少数量的防御塔，使得城池中的任何点 $(x,y)$（$x,y \in \mathbb{R}$，$0 \le x,y \le n+1$）都能被保护。你能找到最优策略吗？

输入格式

输入的第一行给出了测试点组数 $T$，接下来是 $T$ 组测试点。

对于每组测试点，第一行包含一个整数 $n$，其中 $n$ 是防御塔的数量。

接下来的 $n$ 行，每行包含三个整数 $x_i,y_i$ 和 $d_i$，表示防御塔 $i$ 的位置和方向。

输出格式

输出一行包含 "\texttt{Case #x: y}"，其中 \texttt{x} 是测试点编号（从 $1$ 开始），以及 \texttt{y} 是最少数量的防御塔。如果不可能保护整座城池，输出 "\texttt{Impossible}"（不包括引号）。

样例

输入： $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$

数据范围与提示

• 对于 $10\%$ 的测试数据，满足 $n \le 20$，$\sum n \le 100$。
• 对于 $30\%$ 的测试数据，满足 $n \le 100$，$\sum n \le 500$。
• 对于 $40\%$ 的测试数据，满足 $n \le 1000$，$\sum n \le 5000$。
• 对于 $70\%$ 的测试数据，满足 $n \le 10^5$，$\sum n \le 5 \times 10^5$。
• 对于全部测试数据，满足 $1 \le T \le 10^4$，$1 \le n \le 10^6$，$\sum n \le 5 \times 10^6$，$1 \le x_i,y_i \le n$，$1 \le d_i \le 4$。

由于本题输入量较大，请使用较快的读入方式。