Giải bài trực tuyến

(Nguồn gốc từ bài BALLGAME)

Cho một dãy các lỗ có sức chứa vô hạn được đánh số từ 1 đến N. Trò chơi tiến hành như sau:

_ Tại thời điểm nào đó, một người đứng ở vị trí x bất kì và ném bóng.

_ Quả bóng được ném đi sẽ lọt vào lỗ trống gần nó nhất

_ Mỗi quả bóng có một độ xoáy (có thể giống hoặc khác nhau); nếu một quả bóng có độ xoáy là x thì nó sẽ xoáy trên miệng lỗ mà nó rơi vào trong x phút trước khi rơi hẳn xuống lỗ.

_ Một ô được định nghĩa là trống khi không có quả bóng nào đang xoáy trên miệng lỗ đó, nếu tại một lỗ có một quả bóng đang xoáy thì thời điểm quả bóng ngừng xoáy cũng là thời điểm lỗ bắt đầu trống.

Cho các truy vấn có dạng T X Y với T là thời điểm ném bóng, X là vị trí ném bóng, và Y là độ xoáy. Với mỗi truy vấn yêu cầu in ra vị trí của lỗ trống gần vị trí X nhất (nếu X trống thì tất nhiên vị trí này sẽ là X). Nếu tồn tại 2 ô trống đều gần X nhất thì in ra vị trí bên trái.

Input

_ Dòng đầu chứa 2 số N và M (với N là số lỗ và M là số truy vấn) (N<=100000; M<=100000)

_ M dòng sau mỗi dòng chứa 2 số T X Yvới ý nghĩa như trên. (lưu ý là các truy vấn đc cung cấp theo thứ tự thời gian) (0<=T,Y<=10^9; 1<=X<=N)

Output

_ Với mỗi truy vấn, in ra trên một dòng vị trí lỗ trống mà quả bóng đó sẽ lọt vào, nếu ko tồn tại vị trí nào thì in ra 0

Example

Input:
5 7
3 3 7
7 4 8
10 5 4
13 4 3
15 2 8
16 5 2
18 3 7

Output:
3
4
5
3
2
5
3