시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB93333.333%

문제

홀수 개의 사탕 봉지가 있다. 각각의 봉지에 들어있는 사탕은 두 종류로, 사과 맛 사탕과 포도 맛 사탕 두 종류가 있다. 물론 어떤 봉지에는 한 종류의 사탕만 들어있을 수도 있다. 사탕은 투명한 봉지에 들어 있기에, 봉지를 뜯지 않고도 각각의 봉지에 사탕이 몇 개씩 들었는지를 알 수 있다고 한다.

민식이와 영식이는 이 사탕 봉지들을 적절히 나눠 가지려고 한다. 봉지를 뜯기는 번거롭고, 홀수 개의 봉지를 적절히 몇 개씩 골라서 가지기로 했다. 같은 개수의 봉지를 가질 수는 없기에, 특별히 형인 민식이가 동생인 영식이에게 자신보다 사탕 봉지를 하나 더 가져갈 수 있도록 허락해 주었다.

자신이 가져갈 사탕 봉지를 고르던 영식이는, 민식이보다 더 많은 개수의 사탕을 가져가는 일은 너무 쉬운 일이라는 것을 깨달았다. 하지만 민식이보다 사과 맛 사탕도 많이 가져가고, 포도 맛 사탕도 많이 가져갈 수는 없을까 하는 생각이 문득 들었다. 같아서도 안 되며 반드시 많도록.

사탕 봉지의 개수 2K+1과, 각각의 사탕 봉지에 들어 있는 사과 맛 사탕과 포도 맛 사탕의 개수가 주어진다. 영식이를 도와 이 중 K+1개의 사탕 봉지를 고르되, 고른 봉지에 들어 있는 사과 맛 사탕의 합이 남아 있는 사과 맛 사탕보다도 많고, 포도 맛 사탕의 합도 남아 있는 포도 맛 사탕보다도 많도록 하는 프로그램을 작성하시오.

입력

두 개의 테스트 셋에 대해서 문제를 풀어야 한다. 각 테스트 셋의 첫째 줄에 사탕 봉지의 개수 2K+1이 주어진다. 이는 3 이상 499,999 이하의 홀수이다. 이어서 2K+1개의 줄에 걸쳐 각각의 봉지에 들어 있는 사과 맛 사탕의 개수와 포도 맛 사탕의 개수가 빈 칸을 사이에 두고 주어진다. 입력받은 순서대로 1번 봉지, 2번 봉지, …, 2K+1번 봉지로 생각하면 된다. 주어지는 모든 수는 10억 이하의 음이 아닌 정수이다.

출력

테스트 셋 별로 두 줄에 걸쳐 답을 출력하되, 각 줄에는 조건을 만족하도록 영식이가 가져가야 할 K+1개의 사탕 봉지의 번호를 증가하는 순서대로 빈 칸을 사이에 두고 출력한다. 아무 답이나 하나 출력하면 되며, 불가능한 경우에는 -1을 출력한다.

예제 입력 1

3
1 10
10 1
9 9
5
100 1
200 2
300 3
400 4
500 5

예제 출력 1

1 2
1 3 4