隧道

时间限制：1秒
内存限制：512 MB
输入：标准输入
输出：标准输出

题目描述

回到邪恶莫蒂竞选 Citadel 总统的时代。很少有人知道，最谨慎的瑞克们对他进行了监视，其中包括监视他在一条重要地下隧道中的移动。

瑞克委员会在隧道附近安装了监控摄像头，一个在入口处，一个在出口处。选举当天，$n$ 辆车依次驶入隧道，所有车辆匀速且速度相同。摄像头记录了每辆车的进入和离开时间。隧道内禁止超车，但已知隧道内恰好有一个掉头点，并且恰好有一辆驶入的车辆掉头并从同一端驶出（掉头瞬间完成）。

摄像头的设置使得记录混合，通常只留下序列 $a$，其中 $a_i$ 是第 $i$ 辆车进入隧道的时间，以及 $b$，其中 $b_i$ 是第 $i$ 辆车离开隧道的时间。保证 $\max(a) < \min(b)$，即最后一辆车进入隧道的时间严格早于第一辆车离开的时间，且所有 $a_i$ 互不相同。然而序列 $b$ 也丢失了，现在只留下了一个排列 $c$，表示车辆离开隧道的顺序：$c_i$ 是第 $i$ 辆离开隧道的车辆编号（从 $1$ 到 $n$）。

瑞克委员会根据序列 $a$ 和 $c$ 不知为何无法确定掉头点的位置——是靠近隧道入口、靠近隧道出口，还是无法唯一确定。这些信息将极大有助于他们监视邪恶莫蒂的行踪（我们知道，这可能导致完全不同的结果）。你能回答这个问题吗？

输入格式

第一行包含一个整数 $n$ —— 车辆数量（$1 \le n \le 10^5$）。

第二行包含 $n$ 个互不相同的整数 $a_i$ —— 车辆进入隧道的时间。第 $i$ 辆车在时间 $a_i$ 进入隧道（$1 \le a_i \le 10^9$）。

第三行包含 $n$ 个互不相同的整数 $c_i$ —— 车辆离开隧道的顺序。第 $i$ 辆离开隧道的车辆编号为 $c_i$（$1 \le c_i \le n$）。

输出格式

输出一行：如果掉头点靠近入口，则输出 "begin"；如果靠近出口，则输出 "end"；如果无法唯一确定，则输出 "impossible"。

示例

示例 1

输入：

5
10 20 30 40 50
2 3 4 1 5

输出：

end

示例 2

输入：

4
7 6 8 3
2 4 1 3

输出：

impossible

示例 3

输入：

5
6 2 3 10 9
1 2 3 5 4

输出：

begin