시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB43814811234.251%

문제

우선순위 스케줄링은 우선순위가 높은 프로세스가 리소스를 먼저 사용하도록 하는 스케줄링 기법이다. 프로세스의 우선순위를 적절하게 할당할 수 있다면 우선순위가 높은 프로세스를 먼저 처리하는 것이 합리적일 것이라는 고찰로부터 고안되었다.

하지만 우선순위가 높은 프로세스들이 계속해서 요청된다면 우선순위가 낮은 프로세스는 순위에 밀려 영원히 실행되지 않을 수도 있게 된다. 이런 현상을 starvation이라고 한다. 프로세스 간 우선순위 책정이 항상 정확하게 이루어진다는 보장이 없기 때문에 우선순위가 낮다고 해서 실행되지 않아도 되는 것은 아니다. 우선순위가 높은 프로세스를 먼저 처리하지만 모든 요청된 프로세스가 고루 실행될 수 있도록 하려면 starvation을 해결해야 한다.

aging은 starvation을 근본적으로 해결하는 방법이다. aging은 실행되지 않고 준비 큐에 대기 중인 프로세스들의 우선순위를 점진적으로 증가시킨다. 이렇게 하면 실행되지 못하고 큐에 남은 프로세스는 어느 순간부터는 최고 우선순위를 가지게 되고 반드시 실행될 수 있다.

용광이는 운영체제 과목의 자유 과제로 aging이 적용된 우선순위 스케줄러를 제출해서 고득점을 노려보기로 했다. 용광이가 구현할 우선순위 스케줄러는 다음과 같은 조건을 만족한다.

  • 각 프로세스에 입력된 순서대로 번호를 부여한다. 첫 번째로 입력된 프로세스에는 1번, 두 번째로 입력된 프로세스에는 2번, ..., K번째로 입력된 프로세스에는 K번을 부여한다.
  • 현재 실행되고 있는 프로세스가 없다면, 지금까지 실행 요청된 프로세스 중 우선순위가 가장 높은 프로세스가 실행된다.
  • 우선순위가 같은 프로세스가 여러 개라면 실행 시간이 짧은 프로세스가 먼저 실행된다.
  • 우선순위가 같고 실행 시간이 같은 프로세스가 여러 개라면 부여된 번호가 작은 프로세스가 먼저 실행된다.
  • 실행 요청되었지만 실행되지 않은 프로세스는 단위 시간당 우선순위가 1씩 증가한다.
  • 한 프로세스가 실행 중인 동안에는 다른 프로세스가 요청되어도 실행을 중단하지 않는다.

용광이는 우선순위 스케줄러를 완성했지만 자기가 만든 스케줄러가 정확하게 동작하는지는 알 수 없었다. 이래서는 과제 제출을 할 수 없다.

용광이가 고득점의 꿈을 버리지 않도록 스케줄러가 올바르게 동작하는지 확인해주는 프로그램을 만들어보자.

입력

첫 번째 줄에는 프로세스의 개수 \(N\)이 주어진다.

다음 \(N\)개의 줄에는 \(i\)번 프로세스의 정보를 나타내는 3개의 정수 \(t_i\), \(p_i\), \(b_i\)가 공백으로 구분되어 주어진다.

\(t_i\)는 \(i\)번 프로세스가 실행 요청된 시점이며, 비내림차순으로 주어진다.

\(p_i\)는 \(i\)번 프로세스의 초기 우선순위이며, \(p_i < p_j\)면 \(i\)번 프로세스보다 \(j\)번 프로세스의 우선순위가 더 높음을 뜻한다.

\(b_i\)는 \(i\)번 프로세스의 실행 시간이다.

출력

프로세스가 실행되는 순서대로, 해당 프로세스의 번호를 공백으로 구분하여 출력한다.

제한

  • 1 ≤ \(N\) ≤ 3 × 105
  • 0 ≤ \(t_i\) ≤ 3 × 105
  • 0 ≤ \(p_i\) ≤ 103
  • 0 ≤ \(b_i\) ≤ 103

예제 입력 1

3
0 0 5
1 2 3
2 1 2

예제 출력 1

1 2 3

예제 입력 2

5
0 1000 8
0 1 4
0 2 3
3 5 3
9 11 2

예제 출력 2

1 3 5 4 2