H. Tunnel
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

A surveillance system is monitoring movements through an important underground tunnel. The system consists of two cameras near the tunnel, one at the entrance and one at the exit.

Today $$$n$$$ cars entered the tunnel one after the other. All cars move uniformly and at the same speed. The cameras recorded the entry and exit times of each car. Overtaking in the tunnel is prohibited, but it is known that there is exactly one place for a U-turn inside and exactly one of the entering cars made a U-turn and exited from the same end of the tunnel as it entered (the car's U-turn happens instantly).

The cameras are set up in such a way that the recordings from them are mixed, and after all of the cars pass through only the sequences $$$a$$$ and $$$b$$$ remain. Here $$$a_i$$$ is the entry time of the $$$i$$$-th car into the tunnel, and $$$b_i$$$ is the exit time of the $$$i$$$-th car from the tunnel. It is guaranteed that $$$\max(a) \lt \min(b)$$$, i.e. exit time of any car is greater than any entry time.

Your task is to determine where the U-turn place is located: closer to the beginning of the tunnel, closer to the end, or if it is impossible to determine unequivocally.

However, this task is even further complicated by the loss of sequence $$$b$$$. The only thing that could be recovered is a permutation $$$c$$$ of numbers from $$$1$$$ to $$$n$$$ where $$$c_i$$$ is the number of the car that exited the tunnel $$$i$$$-th in order. Can you determine the U-turn's position based only on $$$a$$$ and $$$c$$$?

Input

The first line contains an integer $$$n$$$ — the number of cars ($$$1 \le n \le 10^5$$$).

The second line lists $$$n$$$ different integers $$$a_i$$$ — the entry times at which cars entered the tunnel. Car number $$$i$$$ entered the tunnel at time $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$).

The third line lists $$$n$$$ different integers $$$c_i$$$ — the order of the cars exiting the tunnel. Car number $$$c_i$$$ exited the tunnel $$$i$$$-th in order ($$$1 \le c_i \le n$$$).

Output

Output one line "begin" if the U-turn is located closer to the beginning; "end" if the U-turn is located closer to the end; and "impossible" if the U-turn place cannot be determined unequivocally.

Examples
Input
5
10 20 30 40 50
2 3 4 1 5
Output
end
Input
4
7 6 8 3
2 4 1 3
Output
impossible
Input
5
6 2 3 10 9
1 2 3 5 4
Output
begin