회전초밥전문점 준혁초밥은 초밥을 담은 접시를 원모양의 컨베이어 벨트로 운반하고 있다.

컨베이어 벨트는 반시계방향으로 돌고 있다.

현재, 가게 내에는 손님 1부터 손님 N까지 N명의 손님이 있고, 손님은 컨베이어 벨트에 시계 반대방향으로 앉아있다.

손님 N옆에는 손님 1이 앉아있다.

손님은, 한 사람이 한 개씩 접시를 갖고 있다.

각 접시에는 가치라고 불리는 숫자가 정해져 있어서, 가게를 나갈 때에 손님은 자신이 가지고 있는 접시의 가치와 같은 양의 돈을 지불한다.

준혁초밥에서는 색다른 타임 세일을 하고 있다.

이 타임세일에는, Q번에 나누어 차례대로 요리사로부터 접시가 제공된다.

i(1 ≤ i ≤ Q)번째 접시의 내용은 3개의 수 (S_i, T_i, P_i)로 표시된다.

타임세일의 룰은 다음과 같다.

타임 세일이 시작하기 직전, 초밥장인 준혁이는 컨베이어 벨트에 있는 접시를 모두 회수한다.

그 후, 아래의 과정을 i = 1, 2, ... , Q까지 반복한다.

1. 준혁이가 손님 S_i 앞 위치 컨베이어 벨트에 가치 P_i의 접시를 놓는다.

2. 접시는 손님 S_i의 위치부터 손님 T_i의 위치 까지 컨베이어 벨트 위를 이동한다.

각각의 손님은 자신의 앞의 접시에 대해 다음 행동을 한다.

- 만약, 그 접시의 가치가 자신이 갖고 있는 접시의 가치보다 작으면, 자신의 접시와 컨베이어 벨트의 접시를 교환한다.

- 만약, 그 접시의 가치가 자신이 갖고 있는 접시의 가치 이상이면, 접시를 교환하지 않는다.

3. 접시가 T_i에 도착한 후, 준혁이가 그 접시를 회수한다.

당신은 준혁이 밑에서 장인수업을 듣고 있는 제자이고, 가게 접시의 설거지를 맡고 있다.

접시의 가치에 따라 설거지 방법이 다르다.

당신은 설거지를 준비하기 위해서, 타임세일 Q번에 대해 준혁이가 어떤 가치의 접시를 회수하는지 알고 싶다.

각각의 손님이 타임세일 직전에 가지고 있는 접시의 정보와 타임세일에 제공될 접시의 정보가 주어졌을 때, 준혁이가 회수하는 각 접시의 가치를 구하는 프로그램을 작성하라.

회전초밥 timer 12s memory 512MB

회전초밥 12s 512MB