Ресторан

시간 제한1초메모리 제한1024 MB

요약

식당 1번부터 n번까지에 대한 세 사람의 선호 순위가 주어질 때, 다른 모든 식당보다 적어도 두 사람의 순위에서 앞서는 식당을 찾고, 없으면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 조합론, 배열, 구현, 그리디
정답자: 아직 제출이 없습니다

문제

Тор, Ракета и Грут ходят по торговому центру и выбирают ресторан, в котором они поужинают. У каждого из них свои предпочтения, Тору нравятся рестораны с большим выбором стейков, Ракете нравятся бургеры, а Грут предпочитает пиццу. Так или иначе, каждый из них выставил все рестораны (с номерами от $1$ до $n$ ) в порядке своих приоритетов.

Как же им выбрать ресторан? Будет неловко, если они пойдут в какой-то ресторан, а кафе напротив будет более предпочтительно и у Ракеты, и у Грута. А кафе может оказаться хуже другой забегаловки по мнению Тора и Ракеты... Они решили выбрать ресторан, который не будет уступать никакому другому ресторану.

Более формально, нужно найти такой ресторан, что любой другой ресторан будет менее предпочтителен у не менее чем двух Мстителей. Помогите им найти такой ресторан, или скажите что его не существует.

입력

В первой строке содержится $n$ --- число ресторанов ( $1 \le n \le 100\\,000$ ).

Во второй строке содержится перестановка чисел от $1$ до $n$ --- список ресторанов в порядке предпочтения у Тора, от более предпочтительного к менее предпочтительному.

В третьей строке в аналогичном формате записаны предпочтения Ракеты, а в четвертой строке --- предпочтения Грута.

출력

Выведите номер самого лучшего ресторана, или $-1$ , если его не существует.

예제2

예제 1
입력
```
3
1 2 3
2 3 1
3 1 2
```
예상 출력
```
-1
```
예제 2
입력
```
4
2 1 3 4
3 1 4 2
4 1 2 3
```
예상 출력
```
1
```