비밀 코드

세 명의 비밀 요원 A, B, C는 자신들의 비밀 코드가 서로 같은지 확인하려고 한다. 비밀을 유지하기 위해 이들은 만날 시각을 정하지 않고, 하루 중 시간 구간 [0, S] 동안 카페에 무작위로 나타나기로 했다. tA, tB, tC를 각각 A, B, C가 카페에 도착한 시각이라 하자. 즉 tA, tB, tC는 시간 구간 [0, S]에서 균등하게 선택된 확률 변수이다.

코드 확인은 다음과 같이 진행된다. 더 일찍 도착한 요원은 미리 정해진 대기 시간 동안 다음 요원이 나타나기를 기다린다. 두 요원이 카페에서 만나면 둘 다 자신의 코드가 같은지 확인한다. 코드 확인을 마친 뒤 더 일찍 도착한 요원은 즉시 카페를 떠난다. 그다음 두 번째 요원은 세 번째 요원이 카페에 나타날 때까지 기다린다. 세 번째 요원이 자신의 대기 시간 안에 나타나면 두 요원은 카페를 떠난다.

세 요원 A, B, C의 대기 시간은 이미 wA, wB, wC로 정해져 있다. 각 도착 시각 tA, tB, tC는 반드시 정수일 필요가 없는 0과 S 사이의 실수이고, 각 대기 시간 wA, wB, wC는 0 < wA + wB, wB + wC, wA + wC < S를 만족하는 양의 정수이다. 코드 확인에는 시간이 걸리지 않는다고 가정한다. 요원은 나중에 도착한 요원과 코드를 확인하면 즉시 카페를 떠난다. 그림 G.1을 통해 이 절차를 설명하겠다.

그림 G.1. 코드 확인의 성공과 실패에 대한 네 가지 경우.

코드 확인이 성공하려면 세 요원 사이에 적어도 두 번의 만남이 필요하다. 도착 순서가 A, B, C일 때 Case-1과 Case-4는 성공하는 경우의 예이고, Case-2와 Case-3은 그렇지 않다. Case-1에서 요원 A는 tA + wA까지 기다리지 않고 시각 x = tB에 즉시 카페를 떠난다. Case-2가 실패하는 경우라는 것은 쉽게 알 수 있다. Case-2에서는 A의 대기 시간이 B와 C의 대기 시간과 겹치더라도, B는 C와 코드를 확인할 수 없다. B와 이미 코드를 확인한 요원 A가 시각 x에 카페를 떠나기 때문이다. 따라서 B와 C 사이에 코드를 확인할 방법이 없다. Case-3과 Case-4에서도 A가 시각 x에 카페를 떠난다는 점에 유의하자.

코드 확인이 성공할 확률은 네 정수 (S, wA, wB, wC)에 따라 달라진다. 네 정수 (S, wA, wB, wC)로 정해지는 n개의 서로 다른 시나리오가 주어진다. 이 n개의 시나리오를 이 확인 확률 순서로 정렬하려고 한다.

n개의 시나리오가 주어졌을 때, 확률이 감소하지 않는 순서로 시나리오 번호를 출력하는 프로그램을 작성하시오.

프로그램은 표준 입력에서 입력을 읽는다. 입력의 첫 줄에는 정수 n (3 ≤ n ≤ 20)이 주어지며, n은 시나리오의 수이다. 다음 n개 줄에는 각각 네 양의 정수 S, wA, wB, wC가 이 순서대로 주어지며, 0 < wA + wB, wB + wC, wA + wC ≤ 1,000인 시나리오 (S, wA, wB, wC)를 나타낸다.

프로그램은 표준 출력에 출력을 쓴다. 확률이 감소하지 않는 순서대로 n개 시나리오의 번호를 한 줄에 출력한다. 1 ≤ i < j ≤ n인 시나리오 i와 j의 확률이 같으면 i를 j보다 먼저 출력한다.

Input:

3
100 12 13 14
110  8  9 15
200 23 30 40

Expected output:

2 1 3

Input:

6
201 15 16 16
375 30 32 27
900 75 73 67
203 16 17 16
373 31 32 27
895 73 75 66

Expected output:

1 2 3 6 5 4