가희와 프로세스 2

시간 제한3.5초메모리 제한512 MB

요약

각 프로세스의 id, 남은 실행 시간, 우선순위가 주어질 때 스케줄러가 T초에 실행하는 프로세스의 id를 구합니다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 정렬, 수학
정답자: 아직 제출이 없습니다

문제

가희는 스케줄러를 구현하라는 과제를 받았습니다. 스케줄러가 실행할 프로세스를 고르는 기준은 다음과 같습니다.

우선순위 값이 가장 큰 프로세스
우선순위 값이 가장 큰 프로세스가 여러 개라면, $id$ 가 가장 작은 프로세스

가희가 만든 스케줄러는 다음 알고리즘으로 실행됩니다.

기준에 따라 실행할 프로세스를 선택합니다. 선택된 프로세스의 $id$ 를 $id_s$ 라 하고, $id_s$ 인 프로세스를 실행합니다.
1초가 지난 후, $id$ 가 $id_s$ 인 프로세스를 제외한 나머지 프로세스들의 우선순위가 1 상승합니다. $id$ 가 $id_s$ 인 프로세스의 실행을 마치는 데 필요한 시간은 1 감소합니다.
남은 실행 시간이 있는 프로세스가 있다면 1번으로 돌아가고, 그렇지 않으면 종료합니다.

동시에 실행되는 프로세스는 하나뿐이며, 1초일 때 스케줄러는 처음에 선택한 프로세스를 실행합니다. 가희는 $t$ 초일 때 스케줄러가 어떤 프로세스를 선택하는지 알고 싶습니다. 가희를 도와주세요.

입력

첫 번째 줄에 $Q$ , $n$ 이 주어집니다.

두 번째 줄부터 $n+1$ 번째 줄까지 프로세스에 대한 정보 $A_i$ , $B_i$ , $C_i$ 가 공백으로 구분되어 주어집니다. 이는 $i$ 번째 프로세스의 $id$ 가 $A_i$ 이고, 실행을 마치는 데 필요한 시간이 $B_i$ 초이고, 초기 우선순위가 $C_i$ 임을 의미합니다.

$n+2$ 번째 줄부터 $n+1+Q$ 번째 줄까지 문제 $Q$ 개에 대한 정보가 아래와 같이 주어집니다.

$T_c$

$T_c$ 는 $T_c$ 초일 때 스케줄러가 선택한 프로세스의 $id$ 값을 묻는 문제입니다.

출력

문제에 대한 답을 $Q$ 개의 줄에 출력합니다.

제한

$1 \le n \le 10^5$
$1 \le Q \le 50$
$1 \le A_i, B_i, C_i \le 10^{12}$
문제에서 주어지는 $T_c$ 값은 1 이상이며, $10^{17}$ 과 모든 프로세스의 실행을 마치는 데 필요한 시간의 총합 중 작은 값 이하입니다.

예제2

예제 1
입력
```
5 2
1 5 1
2 5 1
1
3
5
7
10
```
예상 출력
```
1
1
1
1
2
```

예제 2

입력

5 2
1 5 1000000
2 10000000000 1
1
2
3
1000
10000000000

예상 출력