背景

译自 Northwestern Europe Regional Contest (NWERC) 2022 Problem F。

原题许可协议为 CC BY-SA。

题目描述

Faster Than Light (FTL) 是 Subset Games 制作的一款太空题材俯视视角策略游戏。你控制一艘隶属于 Galactic Federation 的飞船，必须与 Rebel Faction 的飞船作战。敌方飞船由平面上一组轴对齐、互不相交的矩形表示，这些矩形对应飞船的各个房间。

你的飞船已经接近毁灭，但你的武器 hull beam 已经准备好开火。

hull beam 会沿你选择的一个方向射出一条无限长的光束，对每个与之相交的房间造成一点伤害。巧的是，敌方飞船由 $n$ 个房间组成，并且恰好有 $n$ 点生命值。因此，你需要击中每个房间，才能在敌人摧毁你之前摧毁敌人。现在你必须迅速判断，是否能以某种方式放置这条光束。注意，即使光束只是碰到一个房间的边界，也会造成伤害。

:::align{center}

:::

图：样例输入 1 的示意图，其中包含五个灰色房间。红色 hull beam 击中了所有房间，并且在该样例中是唯一合法解。

输入格式

输入包含：

• 一行一个整数 $n$（$1 \leq n \leq 2\cdot 10^5$），表示房间数量。
• 接下来 $n$ 行，每行四个整数 $x_1$、$y_1$、$x_2$ 和 $y_2$（$0 \leq x_1 < x_2 \leq 10^9$ 且 $0 \leq y_1 < y_2 \leq 10^9$），描述一个房间两个相对角点 $(x_1,y_1)$ 与 $(x_2,y_2)$ 的坐标。

保证任意两个房间没有公共内部点。

输出格式

如果可以让 hull beam 一次穿过所有房间，输出 possible。否则，输出 impossible。

5
1 3 3 4
2 2 4 3
4 1 5 3
5 2 7 3
6 3 8 4

possible

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

impossible

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

possible

提示

【数据规模与约定】

对于所有数据，满足 $1 \leq n \leq 2\cdot 10^5$；$0 \leq x_1 < x_2 \leq 10^9$，$0 \leq y_1 < y_2 \leq 10^9$；任意两个房间没有公共内部点。