#P15729. 与或天平

与或天平

题目描述

工程师澪在调试一台只会做位运算的天平。对于两个非负整数 a,ba,b,记 a∧ba\wedge b 为它们的按位与,a∨ba\vee b 为它们的按位或。

给定一个长度为 2N2^N 的非负整数数组

A0,A1,…,A2N−1.A_0,A_1,\ldots,A_{2^N-1}.

你需要找到一对下标 i,ji,j,满足

0≤i,j≤2N−10\le i,j\le 2^N-1

且

Ai+Aj<Ai∧j+Ai∨j.A_i+A_j < A_{i\wedge j}+A_{i\vee j}.

如果存在多对满足条件的下标,输出任意一对即可;如果不存在,输出 -1。

输入格式

第一行包含一个整数 NN。

第二行包含 2N2^N 个整数:

A0,A1,…,A2N−1.A_0,A_1,\ldots,A_{2^N-1}.

输出格式

如果存在答案,输出两个整数 i,ji,j,表示满足条件的一对下标。

否则,输出 -1。

数据范围

  • 0≤N≤200\le N\le 20;
  • 0≤Ai≤1070\le A_i\le 10^7;
  • 输出的 i,ji,j 应满足 0≤i,j≤2N−10\le i,j\le 2^N-1。

样例 1

输入

2
0 1 1 2

输出

-1

样例 2

输入

2
0 1 1 3

输出

2 1

样例 3

输入

0
100

输出

-1