Daisy 是 RainyDay, LLC 的高级软件工程师。她刚刚在他们的产品中实现了三个新功能:第一个功能使他们的产品正常工作,第二个功能使他们的产品快速,第三个功能使他们的产品正确。公司鼓励至少对新功能进行一些测试,因此 Daisy 任命她的实习生 Demid 为新功能编写一些测试。
有趣的是,这三个功能在 Demid 的开发服务器(索引为 1)上通过了所有测试,但在其他一些服务器上可能无法通过测试。
Demid 完成此任务后,Daisy 指定您将这三个功能部署到您公司的所有 $$$n$$$ 服务器上。对于每个功能 $$$f$$$ 和每个服务器 $$$s$$$,Daisy 会告诉您她是否希望将功能 $$$f$$$ 部署在服务器 $$$s$$$ 上。如果她希望部署它,即使该功能 $$$f$$$ 未能通过服务器 $$$s$$$ 上的测试,也必须完成部署。如果她不希望部署它,您可能不会将其部署在那里。
贵公司拥有两种用于向服务器部署新功能的重要工具:持续部署 (CD) 和持续测试 (CT)。可以在几对服务器之间建立CD,形成有向图。 CT 可以设置在某些服务器上。
如果 CD 配置为从服务器 $$$s_1$$$ 到服务器 $$$s_2$$$,则每次 $$$s_1$$$ 收到新功能 $$$f$$$ 时,系统都会启动 $$$f$$$ 到 $$$s_2$$$ 的以下部署过程:
- 如果功能 $$$f$$$ 已部署在服务器 $$$s_2$$$ 上,则不执行任何操作。
- 否则,如果服务器 $$$s_1$$$ 上未设置 CT,则服务器 $$$s_1$$$ 仅将功能 $$$f$$$ 部署到服务器 $$$s_2$$$,而不进行任何测试。
- 否则,服务器 $$$s_1$$$ 运行功能 $$$f$$$ 的测试。如果服务器 $$$s_1$$$ 上的测试失败,则不会执行任何操作。如果测试通过,则服务器 $$$s_1$$$ 会将功能 $$$f$$$ 部署到服务器 $$$s_2$$$。
您将配置 CD/CT 系统,之后 Demid 将在他的开发服务器上部署所有三个功能。您的 CD/CT 系统必须将每个功能准确部署到 Daisy 想要的服务器集。
贵公司没有太多的计算资源,因此您最多可以从一台服务器到另一台服务器建立 CD $$$264$$$ 次。
输入
第一行包含整数 $$$n$$$ ($$$2 \le n \le 256$$$) — 您公司中的服务器数量。
接下来的 $$$n$$$ 行每行包含三个整数。如果 Daisy 希望将第 $$$j$$$ 功能部署到第 $$$i$$$ 服务器,则第 $$$i$$$ 行中的第 $$$j$$$ 整数为 $$$1$$$,否则为 $$$0$$$。
接下来的 $$$n$$$ 行每行包含三个整数。如果第 $$$i$$$ 服务器上第 $$$j$$$ 功能的测试通过,则第 $$$i$$$ 行中的第 $$$j$$$ 整数为 $$$1$$$,否则为 $$$0$$$。
Demid 的开发服务器有索引 $$$1$$$。保证 Daisy 希望将所有三个功能部署到 1 号服务器,并且所有三个功能都通过了 1 号服务器上的测试。
输出
如果无法在最多 $$$264$$$ 对服务器之间配置 CD 来配置 CD/CT 系统,则输出单行“Impossible”。
否则,输出的第一行必须包含“Possible”行。
下一行必须包含 $$$n$$$ 以空格分隔的整数 — CT 的配置。如果您在第 $$$i$$$ 服务器上设置 CT,则第 $$$i$$$ 整数应为 $$$1$$$,否则为 $$$0$$$。
下一行必须包含整数 $$$m$$$ ($$$0 \le m \le 264$$$) — 您要设置的 CD 对的数量。
接下来的 $$$m$$$ 行必须描述 CD 配置,每行有两个整数 $$$s_i$$$ 和 $$$t_i$$$ ($$$1 \le s_i, t_i \le n$$$; $$$s_i \ne t_i$$$),建立从服务器 $$$s_i$$$ 到服务器的新功能的自动部署$$$t_i$$$。
示例
输入 #1
3 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1
输出 #1
Possible 1 1 1 2 3 2 1 3
输入 #2
2 1 1 1 0 0 1 1 1 1 1 1 0
输出 #2
Impossible
注意
第一个样本测试的 CD/CT 系统如下所示。