곧은 막대기를 세 개씩 가지고 있는 학생들이 모든 막대기를 바닥으로 던졌다. 각자 가지고 있던 막대기를 최대 한 개를 제거할 때, 바닥에 있는 나머지 막대기들이 서로 겹치지 않을 수 있는 지를 알아보기로 하였다. 단, 막대기가 제거될 때 다른 막대기의 위치는 변하지 않는다고 가정한다.

예를 들어, 학생 세 명이 각자 가지고 있는 막대기 ①②③, ④⑤⑥, ⑦⑧⑨를 바닥에 던진 막대기 모양이 아래와 같을 때, 막대기 한 개씩 ②, ④, ⑧을 제거하면 나머지 여섯 개의 막대기는 서로 겹치지 않게 된다.

또한, 학생 두 명이 던진 막대기 모양이 아래와 같은 경우에는 각자 어떠한 막대기를 한 개씩 제거하더라도 나머지 막대기들 중에서 적어도 두 개는 서로 겹치게 된다.

바닥에 던져진 막대기의 양 끝점의 좌표가 주어졌을 때, 바닥에 남아 있는 막대기들이 서로 겹치지 않도록 각자 가지고 있던 막대기들 중에서 제거할 최대 한 개의 막대기를 찾는 프로그램을 작성하시오. 실행시간은 0.5초를 넘을 수 없다.

입력

• 첫째 줄에는 학생들의 수를 나타내는 정수 N 이 주어진다. N 은 2 이상 1,000 이하이다.
• 두 번째 줄부터 3N 개의 줄에는 한 줄에 막대기 한 개의 양 끝에 해당되는 두 끝점의 좌표를 나타내는 네 개의 정수 X1,Y1,X2,Y2 가 빈칸을 사이에 두고 나타난다. 각 정수는 한 개의 막대기의 두 끝점의 좌표 (X1,Y1) ,(X2,Y2) 를 나타낸다. 이 정수들은 -10,000 이상 10,000 이하이다. 두 번째 줄부터 나타나는 각 막대기는 1번부터 3N 번까지 순서대로 번호가 부여되며, 연속적인 세 개의 번호 3i-2,3i-1,3i(1 <= i <= N) 는 i 번째 학생이 가지고 있는 막대기 세 개의 번호를 나타낸다.

입력 데이터는 다음 세 조건을 항상 만족한다고 가정한다.

• (조건 1) 막대기들의 끝점의 좌표가 같은 경우는 없다.
• (조건 2) 세 개의 끝점이 임의의 일직선상에 위치하는 경우는 없다.
• (조건 3) 세 개의 막대기가 한 점에서 만나는 경우는 없다.

출력

• 첫째 줄에는 서로 겹치지 않도록 막대기를 제거할 수 없는 경우에는 -1을 출력한다. 그렇지 않은 경우에는 첫째 줄에 제거된 막대기의 수인 K ( 0 <= K <= N)를 출력한다. K 가 최소일 필요는 없다.
• 두 번째 줄에는 제거된 막대기 K 개의 번호를 빈칸을 사이에 두고 오름차순으로 출력한다. 단, K 가 0인 경우에는 막대기 번호를 출력하지 않는다.

입출력 예

입력

2
0 6 9 6
5 -1 8 5
1 5 3 -1
5 8 8 1
9 0 0 0
1 1 3 8

출력

-1

입력

3
38 183 175 290
73 142 313 247
190 260 213 170
38 235 312 25
175 72 293 268
240 24 420 182
70 181 192 181
73 282 417 142
195 47 388 210 

출력

3
2 4 8

출처:제29회한국정보올림피아드(2012.7.13) 고등 4/4
special judge: zlzmsrhak