C. Attack on Titans
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In Attack on Titans, humanity lives in fear of giant humanoid creatures called Titans. In order to defend themselves, the humans built three walls: Wall Maria, Wall Rose, and Wall Sina. Wall Maria is made up of $$$n$$$ separate sections, with the $$$i$$$th section having height $$$m_i$$$. Wall Rose and Wall Sina also have $$$n$$$ sections each, with heights $$$r_i$$$ and $$$s_i$$$ respectively.

Find the tallest section height common to all three walls: the maximum value of $$$h$$$ with $$$h = m_i = r_j = s_k$$$ for some indices $$$1 \leq i,j,k \leq n$$$. Note that for a height $$$h$$$ to be common to all three walls, each wall must have a section of height $$$h$$$, but these sections are not required to be at the same position on all three walls.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of sections in each wall. The second, third, and fourth lines each contain $$$n$$$ space-separated integers: the second line lists the heights $$$m_i$$$ of the sections in Wall Maria, the third the heights $$$r_i$$$, and the fourth the $$$s_i$$$. Each height satisfies ($$$1 \leq m_i, r_i, s_i \leq 10^5$$$).

Output

Print a single integer: the tallest section height common to all three walls. If there is no section height common to all three walls, print $$$-1$$$ instead.

Example
Input
5
1 2 3 8 5
5 6 7 8 9
8 12 14 19 12
Output
8