Тоннель
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вернемся во времена, когда Злой Морти выдвигался на пост президента Цитадели. Мало кто знает, но самые осторожные Рики установили за ним слежку. В том числе они следили за его перемещениями по одному важному подземному тоннелю.

Совет Риков установил около тоннеля камеры наблюдения, одну на въезде и одну на выезде. В день выборов в тоннель въехали друг за другом $$$n$$$ машин, все машины движутся равномерно и с одинаковой скоростью. Камеры зафиксировали время въезда и выезда каждой машины. Обгон в тоннеле запрещен, однако известно, что внутри есть ровно одно место для разворота, и ровно одна из въехавших машин развернулась и выехала с того же конца тоннеля, что и въехала (разворот машины происходит мгновенно).

Камеры установлены так, что записи с них перемешиваются, и после проезда обычно остается только последовательность $$$a$$$, где $$$a_i$$$ — время въезда $$$i$$$-й машины в тоннель и $$$b$$$, где $$$b_i$$$, соответственно — время выезда $$$i$$$-й машины из тоннеля. Гарантируется, что $$$max(a) < min(b)$$$, то есть время въезда последней машины в тоннель строго меньше, чем время выезда первой, и все $$$a_i$$$ различны. Однако последовательность $$$b$$$ тоже была утеряна, и теперь вместо нее осталась только перестановка $$$c$$$, обозначающая порядок выезда машин из тоннеля: $$$c_i$$$ равно номеру машины (от $$$1$$$ до $$$n$$$), которая выехала из тоннеля $$$i$$$-й по счету.

Совет Риков по последовательностям $$$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$$$ — порядок выезда машин из тоннеля. Машина с номером $$$c_i$$$ выехала из тоннеля $$$i$$$-й по счету ($$$1 \le c_i \le n$$$).

Выходные данные

Выведите одну строку: «begin», если разворот расположен ближе к началу; «end», если разворот расположен ближе к концу; и «impossible» — если место разворота однозначно установить невозможно.

Примеры

Входные данные
5
10 20 30 40 50
2 3 4 1 5
Выходные данные
end
Входные данные
4
7 6 8 3
2 4 1 3
Выходные данные
impossible
Входные данные
5
6 2 3 10 9
1 2 3 5 4
Выходные данные
begin