AT_tkppc2015_f.吹奏楽部 (Brass Band)

joisino姐姐决定参观吹奏乐部。当她走进音乐室时，发现顾问老师正面临一个难题。由于joisino姐姐的程序设计能力出众，老师向她求助。

问题的具体内容如下：

1. 吹奏乐部总共有 $N$ 种乐器，每种乐器编号为 $1$ 到 $N$。使用编号为 $i (1 \le i \le N)$ 的乐器的人数正好是 $i$。
2. 为了让乐器演奏的效果达到最佳，使用乐器 $i$ 的 $i$ 名演奏者需要均匀地分布在舞台上，站在划分后的 $i+1$ 等分位置上。最终，所有 $N$ 种乐器的演奏者将排列于舞台的同一水平线上。
3. 假定每个人都没有宽度。如果有两人或以上站在同一位置，只有编号最小乐器的演奏者可以站在那里，其余人需要下台。
4. 比赛有 $M$ 位评委，他们在舞台前依次排列。
5. 第 $j (1 \le j \le M)$ 位评委位于舞台长为 $1$ 的情况下，左端起第 $P_j / Q_j$ 的位置。
6. 每位评委能够看到的演奏者人数是固定的，已知评委 $j$ 能看到 $K_j$ 人。
7. 为了给练习提供参考，joisino姐姐希望知道每位评委在其视野中最远的演奏者所使用的乐器编号。

需要注意的是，若最远处有两人，绝不可能只看到其中一人。在这种情况下，请输出编号较小的乐器。如果编号一样，则随意输出一个。

joisino姐姐将编写一个程序，基于供给她的已知信息（乐器数量 $N$、评委人数 $M$、评委 $j$ 的位置 $P_j / Q_j$、评委视线中的演奏者人数 $K_j$），计算每位评委看到的最远演奏者所用的乐器编号。

输入以如下格式提供：

第一行包含两个整数 $N$ 和 $M$，分别表示有多少种乐器和多少位评委。

接下来的 $M$ 行中，第 $j$ 行包含三个整数 $P_j$、$Q_j$ 和 $K_j$，描述评委 $j$ 的位置是 $P_j / Q_j$ 以及他能看到的演奏者人数 $K_j$。

• $1 \le N \le 3 \times 10^4$
• $1 \le M \le 30$
• $1 \le P_j < Q_j \le N + 1$
• $1 \le K_j \le \sum_{i=1}^{N} i$

保证所有输入都满足：每位评委看到的演奏者总人数不会超过舞台上演奏者的总人数。

输出包含 $M$ 行。每行输出对应评委所看到的最远演奏者的乐器编号。

配分

本题有部分得分。

• 数据集 1 满足 $N \le 5000$，正确解答可得 15 分。

• 数据集 2 无其他限制，正确解答可得 105 分。

样例解释

• 在某个例子中，舞台上演奏者的排列可视如下图。（蓝线表示舞台边缘，数字表示所用乐器的编号）。评委 1 从其所在的绿箭头位置，看到绿色括号内的 3 名演奏者。括号内最远的是编号为 1 的演奏者，所以输出 1。评委 2 从其红箭头的位置，可以看到红括号内的 4 名演奏者。括号中最远的演奏者是编号为 2 和 5 的人，所以应输出编号较小的 2。

本翻译由 AI 自动生成