Gahee and Process 2

Time limit3.5sMemory limit512 MB

Summary

Given n processes with id, remaining time, and priority, find which process id the scheduler runs at second T for each query.

Level: Medium7 of 10
Topics: Binary search, Sorting, Math
Solved: No attempts yet

Problem

Gahee was assigned to implement a scheduler. The criteria for choosing the process to run are as follows.

The process with the largest priority value.
If several processes share the largest priority value, the process with the smallest $id$ .

The scheduler Gahee wrote runs with the following algorithm.

Choose the process to run according to the criteria. Let $id_s$ be the $id$ of the chosen process. Run the process with $id_s$ .
After 1 second, the priority of every process except the one with $id$ equal to $id_s$ increases by 1. The time needed to finish the process with $id$ equal to $id_s$ decreases by 1.
If any process still has remaining execution time, return to step 1. Otherwise, stop.

Only one process runs at a time. At second 1, the scheduler runs the process it chose first. Gahee wants to know which process the scheduler selects at second $t$ . Please help Gahee.

Input

The first line contains $Q$ and $n$ .

The next $n$ lines, from line 2 to line $n+1$ , each contain $A_i$ , $B_i$ , and $C_i$ separated by spaces. This means the $i$ -th process has $id$ equal to $A_i$ , needs $B_i$ seconds to finish, and has initial priority $C_i$ .

From line $n+2$ to line $n+1+Q$ , each query is given as follows.

$T_c$

$T_c$ is a query asking which process $id$ the scheduler selects at second $T_c$ .

Output

Print the answer to each of the $Q$ queries on its own line.

Constraints

$1 \le n \le 10^5$
$1 \le Q \le 50$
$1 \le A_i, B_i, C_i \le 10^{12}$
Each $T_c$ is at least 1 and at most the smaller of $10^{17}$ and the total time needed to finish all processes.

Examples2

Example 1
Input
```
5 2
1 5 1
2 5 1
1
3
5
7
10
```
Expected output
```
1
1
1
1
2
```

Example 2

Input

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

Expected output