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.|

VPHSTAR - Ngắm sao

Chíp có sở thích ngắm sao vào mỗi buổi đêm. Đêm nay, trời đặc biệt đầy sao. Chíp đếm được có N ngôi sao trên trời, Chíp ghi nhớ mỗi ngôi sao và đánh số chúng từ 1 đến N. Mỗi ngôi sao được biểu diễn bằng một đường tròn trên mặt phẳng tọa độ, ngôi sao thứ i có tâm nằm ở tọa độ (Ai, Bi) và bán kính Ri. Những ngôi sao có thể đè lên nhau.

Chíp đứng ở trên mặt đất, tức là trục hoành, và nhìn thẳng lên trời. Chíp muốn biết ngôi sao gần nhất mà mình nhìn thấy được là ngôi sao nào, để có thể chọn chỗ đứng thích hợp ngắm ngôi sao mình thích. Vì vậy, Chíp đặt ra Q câu hỏi, mỗi câu hỏi gồm một số Xi, hỏi rằng nếu đứng ở vị trí (Xi, 0) thì ngôi sao gần nhất Chíp nhìn thấy là ngôi sao nào.

Tại vị trí (Xi, 0), vẽ một tia song song và cùng chiều với trục tung, đường tròn đầu tiên nó chạm vào thì ngôi sao tương ứng với đường tròn đó là ngôi sao đầu tiên Chíp nhìn thấy. Bạn hãy giúp Chíp trả lời Q câu hỏi này nhé.

Input

            Dòng đầu tiên gồm hai số nguyên N, Q.

            N dòng tiếp theo, dòng thứ i gồm ba số nguyên Ai, Bi, Ri mô tả ngôi sao thứ i.

            Q dòng tiếp theo, dòng thứ i gồm một số nguyên Xi mô tả truy vấn thứ i.

Output

            In ra Q dòng, mỗi dòng gồm một số nguyên là chỉ số ngôi sao gần nhất Chíp nhìn thấy nếu đứng ở (Xi, 0). Nếu nhìn thấy được nhiều ngôi sao gần nhất thì in ra chỉ số của ngôi sao có chỉ số nhỏ nhất. Nếu tại vị trí đó nhìn thẳng lên không có ngôi sao nào thì in ra '-1'.

Giới hạn

            1 ≤ N ≤ 50000.

            1 ≤ Q ≤ 50000.

            1 ≤ Ai, Bi, Ri, Xi ≤ 105.

            Bi > Ri (Những ngôi sao hoàn toàn cao hơn mặt đất).

            40% số điểm có 1 ≤ N ≤ 1000, 1 ≤ Q ≤ 1000.

Example

Input:

4 5

2 3 2

6 9 2

5 5 2

4 7 3

4

7

8

1

9 Output:

1

3

2

1

-1 Hình minh họa cho test ví dụ


Được gửi lên bởi:VOJ Team
Ngày:2016-03-20
Thời gian chạy:3s
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ừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:Vũ Phúc Hoàng

hide comments
2016-10-05 10:01:36
Cho hỏi có test nào hiểm k mà s nộp toàn 0đ -_-
2016-07-24 17:11:19
Yeye cmt đầu tiên ==))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.