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

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 độ (A_i, B_i) và bán kính R_i. 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ố X_i, hỏi rằng nếu đứng ở vị trí (X_i, 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í (X_i, 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 A_i, B_i, R_i mô tả ngôi sao thứ i.

            Q dòng tiếp theo, dòng thứ i gồm một số nguyên X_i 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 ở (X_i, 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 ≤ A_i, B_i, R_i, X_i ≤ 10⁵.

            B_i > R_i (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