Problem Description

Joisino decided to visit the brass band club next. When Joisino went to the music room with interest, she found the advisor老师 feeling troubled. Joisino, being an excellent programmer, was approached by the teacher for consultation.

The content of the consultation is as follows:

1. The brass band club uses $ N $ instruments, each assigned a number from $ 1 $ to $ N $. There are $ i $ players for instrument $ i $ ( $1 \leq i \leq N$ ).
2. To make instrument $ i $ sound beautifully, the $ i $ players using it need to stand evenly at positions dividing the stage horizontally into $ i+1 $ equal parts. All $ N $ instrument players stand in a single line on the stage.
3. The width of a person is ignored, but if two or more people stand exactly at the same position, only the person using the instrument with the smallest number can stand there, and others cannot stand on the stage.
4. There are $ M $ judges, each assigned a number from $ 1 $ to $ M $. They stand parallel to the stage.
5. Judge $ j $ ( $1 \leq j \leq M$ ) is at a position $ P_j / Q_j $ from the left end of the stage, when the horizontal length of the stage is considered as $ 1 $.
6. Each judge has a fixed viewing distance. Judge $ j $ can see players within a certain distance from them, and the number of such players is known to be $ K_j $.
7. For reference in practice, we want to know the number of the instrument played by the player farthest from each judge.
   Joisino, being an excellent programmer, decided to create a program that, based on the current information (number of instruments $ N $, number of judges $ M $, position of judge $ j $ $ P_j / Q_j $, number of players seen $ K_j $), finds the number of the instrument played by the farthest player seen by judge $ j $.

If there are two farthest players, it is impossible that only one of them is seen. Also, if there are two such players, output the number of the instrument with the smaller number (if they are the same, output that number).

Input Format

Input is given from standard input in the following format:

$ N $ $ M $ $ P_1 $ $ Q_1 $ $ K_1 $ $ P_2 $ $ Q_2 $ $ K_2 $ : $ P_M $ $ Q_M $ $ K_M $

• The first line contains the number of instruments $N (1 \leq N \leq 3*10^4)$ and the number of judges $M (1 \leq M \leq 30)$, separated by spaces.
• The next $ M $ lines, where the $ j $-th line contains integers $P_j (1 \leq P_j < Q_j)$, $Q_j (2 \leq Q_j \leq N+1)$, and $ K_j $, separated by spaces, representing the position of judge $ j $ and the number of players they see.
• In all inputs, the number of players seen by a judge does not exceed the total number of players.

Output Format

Output consists of $ M $ lines. The $ j $-th line should contain the number of the instrument played by the farthest player seen by judge $ j $.
Also, include a newline at the end of the output.

Sample Input and Output

Sample Input #1

5 2
3 5 3
1 4 4

Sample Output #1

1
2

Sample Input #2

7 5
3 8 7
2 5 12
4 8 7
1 5 13
3 5 6

Sample Output #2

1
5
7
4
6

Notes/Hints

Scoring

This problem has partial scoring.

1. For dataset $ 1 $, where $N \leq 5000$, a correct answer earns $ 15 $ points.
2. For dataset $ 2 $, with no additional constraints, a correct answer earns $ 105 $ points.

Sample Explanation 1

• In this case, the players are arranged on the stage as shown in the diagram below (blue lines represent the edges of the stage, and numbers indicate the players with that instrument number are there). Judge $ 1 $ sees $ 3 $ players in the range of the green brackets from the position of the green arrow. The farthest player in the bracket is player $ 1 $, so output $ 1 $. Judge $ 2 $ sees $ 4 $ players in the range of the red brackets from the position of the red arrow. The farthest players in the bracket are players $ 2 $ and $ 5 $, so output the smaller number $ 2 $.

Sample Explanation 2

• In this case, the viewing range of judge $ 4 $ extends beyond the edge of the stage.

见题面 Input 部分

见题面 Output 部分