Билеты в Провал

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

요약

2^n개의 티켓에 각각 바코드 x와 시리즈 번호 y가 주어질 때, (i AND j) = 0을 만족하는 두 인덱스 i, j를 골라 x[i] + y[j]를 최대로 만드는 문제다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 비트 연산, 분할 정복
정답자: 아직 제출이 없습니다

문제

Как-то раз, в Пятигорске, Остап Бендер решил заработать денег. Для этого он начал продавать билеты в открытый для всех Провал. Провал --- это глубокий природный колодец-пещера с подземным озером. Всего для распространения у Остапа было $2^n$ билетов.

У Остапа в роду были программисты, и поэтому все билеты он пронумеровал целыми числами от $0$ до $2^n-1$ . После этого, на каждом билете оказалось по три числа --- штрих-код, номер серии билета и номер, написанный ручкой Остапа Бендера.

Первым покупателям Остапа оказался программист, который захотел купить два билета, отвечающих следующим условиям:

побитовое логическое <<И>> номеров билетов, написанных Остапом, равно нулю
сумма штрих-кода первого билета и номера серии второго билета максимальна

Поскольку Остап не очень силен в быстрых подсчетах, помогите ему найти два таких билета.

입력

В первой строке дано одно натуральное число $n$ ( $1 \le n \le 20$ ). Далее в $2^n$ строках содержится информация о билетах. В $i$ -ой строке входного файла даны два числа $x$ и $y$ ( $0 \le x, y \le 10^9$ ) --- штрих-код и номер серии билета, номер которого в нумерации Остапа равен $i-2$ .

Поскольку билеты фальшивые, то у разных билетов могут совпадать номер серии и/или штрих-код.

출력

Выведите два числа --- номера двух билетов, которые Остап должен продать покупателю. Если возможных ответов несколько, то выведите любой.

힌트

Обратите внимание, что ответы 2 1 и 1 2 различны, поскольку штрих-код берется с первого проданного билета, а серия --- со второго.

Обратите внимание на то, что ответ 0 0 тоже является корректным.

예제2

예제 1
입력
```
2
0 0
1 4
3 3
5 5
```
예상 출력
```
2 1
```
예제 2
입력
```
1
0 0
0 1
```
예상 출력
```
0 1
```