Вернемся во времена, когда Злой Морти выдвигался на пост президента Цитадели. Мало кто знает, но самые осторожные Рики установили за ним слежку. В том числе они следили за его перемещениями по одному важному подземному тоннелю.
Совет Риков установил около тоннеля камеры наблюдения, одну на въезде и одну на выезде. В день выборов в тоннель въехали друг за другом $$$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» — если место разворота однозначно установить невозможно.
510 20 30 40 502 3 4 1 5
end
47 6 8 32 4 1 3
impossible
56 2 3 10 91 2 3 5 4
begin