Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BALGAME2 - Ball Game (version 2)

(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

Được gửi lên bởi:PNL
Ngày:2009-05-30
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:ngockingspeed

hide comments
2021-03-23 16:59:20
bài khó quá
2016-09-24 15:55:57
Code:
http://shink.in/Vi5cO
2016-07-25 21:40:27
vl thật, trâu cũng ac
2015-12-26 10:48:32
trâu cx ac,splay ez

Last edit: 2015-12-26 10:48:59
2009-07-03 16:03:36 Cảnh Toàn Nguyễn
bài này đề bài sáng sủa hơn ballgame \:d/
2009-05-30 07:36:46 PNL
Đã add một số test, các bạn có thể submit. Sẽ add thêm test sau kì thi tốt nghiệp THPT :))

Last edit: 2009-05-31 08:57:50
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.