那是 1825 年 4 月 25 日。英国发明家 William Fothergill Cooke 和英国科学家 Charles Wheatstone 正在研究电报系统的早期原型。该系统由一个发送器和一个接收器组成。发送器可以向接收器发送消息,我们将其建模为一个正整数序列。然而,这个原型远非完美,因此经常会出现发送的整数实际上没有被接收到的情况。不过,整数在连接过程中绝不会被篡改,因此所有接收到的整数都保证是发送过的。
Cooke 和 Wheatstone 的电报机可以通过 5 根指针指向传输的字母来传输字母。CC BY-SA 4.0,由 Geni 上传至维基共享资源
为了弥补这一缺陷,Cooke 和 Wheatstone 提出了一种纠错码。他们共同商定了一个包含 $n$ 个可能消息的固定列表,并为每个消息分配了一个正整数列表。要发送列表中的某个消息,他们只需发送对应的整数列表。有时,某些整数可能会丢失或以不同的顺序到达,但如果保留了足够多的整数,他们希望仍然只有一种可能的消息。
你是一名邮递员,因此你将通信技术的创新视为对你工作保障的直接威胁。你决定干扰 Cooke 和 Wheatstone,以推迟他们电报系统的开发。你已经了解了他们的纠错码,并秘密获取了他们的消息列表以及所有整数列表的副本。你已经找到了一种强行中断某个整数传输的方法,因此你决定利用这一点来破坏他们的系统。为了避免引起怀疑,你决定在发送消息时,至少应保留两个整数不被中断。因此,你的目标是确定是否可以通过中断除其中两个整数之外的所有整数,来使任何消息变得具有歧义。这样,每当要发送这样的消息时,你就可以通过中断相应的整数来使其产生歧义。
注:有人可能会指出,Cooke 和 Wheatstone 实际上直到 1837 年才发布电报设计,但显然,这只意味着你成功解决了这个问题!:)
输入格式
输入包含以下内容:
- 第一行包含一个整数 $n$ ($2 \le n \le 50\,000$),表示可能的消息数量。
- 接下来 $n$ 行(每行对应一条消息),每行包含一个整数 $k$ ($2 \le k \le 10^5$),表示分配给该消息的整数个数,紧接着是这 $k$ 个整数 $x$ ($1 \le x \le 10^9$)。保证一条消息中的 $k$ 个整数两两不同。
所有消息中包含的整数总数最多为 $10^5$。
输出格式
如果存在一对不同的整数,它们被分配给了多个消息,请以任意顺序输出这两个整数,然后输出它们所分配到的其中两个消息的下标(从 1 开始编号)。否则,输出 impossible。
如果存在多个有效解,你可以输出其中任意一个。
样例
输入样例 1
3 5 1 9 3 7 5 4 2 4 6 8 4 7 5 3 2
输出样例 1
3 5 3 1
输入样例 2
3 2 42 1337 2 42 123456789 2 1337 123456789
输出样例 2
impossible