Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Cơn mưa rào bất chợt làm dịu đi cái nắng hè oi ả. Trên hàng mái tôn, những giọt nước mưa vẫn còn đọng lại. Hai giọt nước mưa nói chuyện với nhau, một giọt to, một giọt nhỏ.

Giọt nước nhỏ than thở:

“Anh này, nếu như được rơi xuống những gốc cây xanh, ta có thể hoá thành một phần sức sống của những cây ấy. Nhưng chẳng may nếu rơi xuống nền đường thì ta sẽ lại bốc hơi đi một cách vô ích. Lúc tỉnh dậy thì mình lại không phải giọt nước khi trước… Nghĩ đến thôi cũng thấy rùng mình. Như anh giọt nước ở trước tôi lúc nãy ấy, anh ấy mới bay hơi qua đây thôi”

Giọt nước to liền cười lớn, vừa cười vừa nói:

“Ha ha! Khi trời nóng thì nước vẫn bốc hơi từ cây, nên dù anh có ngấm được vào cây thì sau đó cũng sẽ lại bay hơi đi thôi. Cuộc đời của chúng ta vốn đã vậy rồi, cứ tan rồi lại hợp, hợp rồi lại tan. Mà chả phải anh cũng sẽ như gã đi trước kia thôi sao, vì hai người ờ cùng một chỗ mà!”

Nghe giọt nước to nói vậy, giọt nước nhỏ chợt giật mình. Đúng là giọt nước trước đó đọng ở cùng một chỗ với giọt nước nhỏ.

“Không đâu, tôi nghĩ không phải vậy đâu. À đúng rồi, những ngọn gió sẽ đưa tôi xuống dưới gốc cây kia!” – Giọt nước nhỏ cố trấn an mình.

“Bây giờ đang lặng gió lắm, tôi không nghĩ là chút nữa sẽ có gió đâu” – Giọt nước to giọng nửa thật nửa đùa.

“Không! Tôi không tin anh đâu!”

…

Cuộc nói chuyện cứ thế tiếp tục cho đến khi cả hai cùng rơi xuống.

Input

Dòng đầu tiên gồm 2 số nguyên N, M (1 ≤ N, M ≤ 10⁵) là số lượng mái nhà và số lượng các giọt mưa.

N dòng tiếp theo, mỗi dòng gồm 3 số nguyên x₁, x₂, y (1 ≤ x₁, x₂, y ≤ 10⁵, x₁ < x₂) biểu diễn các mái nhà. Các mái nhà là các đoạn thẳng trên hệ toạ độ Oxy, có 2 điểm đầu mút là (x₁, y) và (x₂, y).

M dòng tiếp theo, mỗi dòng gồm 1 số nguyên x (1 ≤ x ≤ 10⁵) là toạ độ trục Ox của các giọt nước mưa. Các giọt nước mưa không có toạ độ trục Oy, và chúng được coi là nằm trên tất cả các mái nhà.

Dữ liệu đảm bảo các mái nhà có cùng toạ độ trục Oy không giao nhau, các giọt nước có toạ độ đôi một khác nhau.

Output

Một giọt nước mưa sẽ rơi theo phương song song với trục Oy, toạ độ trục Oy giảm dần, còn toạ độ trục Ox giữ nguyên. Nếu chạm phải một mái nhà, giọt nước mưa sẽ lăn sang mép (đầu mút đoạn thẳng) gần hơn của mái nhà, rồi từ mép ấy rơi tiếp xuống. Trong trường hợp cả hai mép cách đều vị trí giọt mưa, giọt mưa sẽ lăn sang bên trái. Mặt đất là phương trình đường thẳng y = 0.

Với mỗi giọt nước mưa, hãy tìm toạ độ trục Ox của nó khi rơi xuống mặt đất.

Example

Input:
3 4
1 5 1
3 4 3
5 7 3
3
4
5
8

Output:
1
5
5
8