Bạn có một trò chơi điện tử do công ty JOI phát hành. Trò chơi được làm khá tốt, và bạn vẫn vui vẻ chơi mỗi ngày.

Một ngày nọ, một màn chơi được các game thủ gọi là “trốn tìm” xuất hiện. Có vẻ màn chơi này có lỗi, khiến ngay cả những người chơi giỏi cũng chỉ có xác suất vượt qua rất nhỏ.

Sau nhiều lần thử sức, bạn nhận ra rằng mình có thể vượt qua màn chơi nếu đưa ra quyết định thật nhanh, và nghĩ đến việc viết chương trình để làm điều đó.

Màn trốn tìm diễn ra trên một khu vực có nhiều chướng ngại vật. Khu vực này là một hình chữ nhật được chia thành các ô vuông \(1\times1\). Mỗi ô được biểu diễn bằng một cặp số nguyên \((x,y)\), với \(1\le x\le100\,000\) và \(1\le y\le1\,000\,000\,000\). Ô \((1,1)\) nằm ở góc trên bên trái; ô \((x+1,y+1)\) là ô cách ô \((1,1)\) một khoảng \(x\) ô về bên phải và \(y\) ô xuống dưới.

Mỗi chướng ngại vật chiếm \(w\) ô liên tiếp có cùng tọa độ \(y\), tạo thành một hình chữ nhật gồm \(w\times1\) ô. Một chướng ngại vật được mô tả bằng tọa độ \((x,y)\) của ô có tọa độ \(x\) nhỏ nhất trong nó và độ dài \(w\). Các chướng ngại vật chỉ nằm ở những ô có \(y\ge2\), và không có hai chướng ngại vật nào chồng lên nhau.

Khi màn chơi bắt đầu, người chơi di chuyển quanh khu vực. Người chơi có thể đến bất kỳ ô nào, kể cả ô có chướng ngại vật.

Sau một khoảng thời gian nhất định, kẻ địch xuất hiện và tấn công. Khi đó, người chơi bắt buộc phải ẩn mình trong một chướng ngại vật: chỉ cần đứng ở một ô có chướng ngại vật là đã ẩn mình trong đó. Nếu chọn được chướng ngại vật thích hợp, người chơi sẽ tránh được đòn tấn công và có cơ hội phản công. Tận dụng cơ hội này sẽ giúp vượt qua màn chơi.

Kẻ địch có \(M\) loại vũ khí, chẳng hạn như súng ngắn, súng trường, pháo không giật, súng điện từ, v.v. Các vũ khí được đánh số riêng biệt từ \(1\) đến \(M\). Vũ khí thứ \(i\) có sức tấn công \(a_i\), nghĩa là nó có thể phá hủy số chướng ngại vật bằng giá trị đó. Nếu người chơi đang ẩn mình trong một chướng ngại vật bị phá hủy thì sẽ chịu sát thương.

Theo thiết kế ban đầu, kẻ địch sẽ chọn ngẫu nhiên một giá trị \(x\), xuất hiện ở ô \((x,1)\), rồi dùng một vũ khí được chọn ngẫu nhiên để tấn công xuống dưới. Tuy nhiên, do lỗi của trò chơi, kẻ địch luôn chọn đúng tọa độ \(x\) của người chơi và tấn công thẳng về phía người chơi.

Bạn quyết định dùng chương trình tự viết để tìm chỗ ẩn nấp tối ưu riêng cho từng vũ khí, nhằm có thể ứng phó với bất kỳ vũ khí nào kẻ địch sử dụng. Trong các chỗ ẩn nấp giúp tránh được đòn tấn công, chỗ tối ưu là chỗ có tọa độ \(y\) nhỏ nhất, để người chơi dễ phản công. Nếu có nhiều chỗ như vậy, chọn chỗ có tọa độ \(x\) nhỏ nhất.

Yêu cầu

Cho thông tin về các chướng ngại vật và sức tấn công của từng vũ khí, hãy viết chương trình tìm chỗ ẩn nấp tối ưu cho mỗi vũ khí. Nếu dù ẩn nấp ở đâu cũng bị tấn công, hãy xuất \((-1,-1)\) để biểu thị rằng không có chỗ ẩn nấp.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N,M\), cách nhau bởi dấu cách, lần lượt là số chướng ngại vật và số loại vũ khí.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(x_i,y_i,w_i\), cách nhau bởi dấu cách, mô tả chướng ngại vật thứ \(i\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(a_j\), là sức tấn công của vũ khí thứ \(j\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(M\) dòng. Dòng thứ \(j\) chứa hai số nguyên \(x_j,y_j\), cách nhau bởi dấu cách, là tọa độ của chỗ ẩn nấp tối ưu khi kẻ địch sử dụng vũ khí thứ \(j\). Nếu không có chỗ nào tránh được đòn tấn công của vũ khí này, ghi -1 -1.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

• \(1\le N\le50\,000\): số chướng ngại vật.

• \(1\le M\le50\,000\): số loại vũ khí.
• \(1\le x_i\le100\,000\): tọa độ \(x\) nhỏ nhất trong các ô của chướng ngại vật thứ \(i\).
• \(2\le y_i\le1\,000\,000\,000\): tọa độ \(y\) của chướng ngại vật thứ \(i\).
• \(1\le w_i+x_i-1\le100\,000\), trong đó \(w_i\) là độ dài của chướng ngại vật thứ \(i\).
• \(1\le a_j\le N\): sức tấn công của vũ khí thứ \(j\).
• Các chướng ngại vật không chồng lên nhau.

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) nhóm kiểm thử, mỗi nhóm \(10\) điểm và chứa \(2\) bộ dữ liệu, tổng cộng \(20\) bộ dữ liệu. Chỉ nhận điểm của một nhóm khi chương trình cho kết quả đúng trên cả hai bộ dữ liệu trong nhóm, kết thúc bình thường (trả về mã \(0\)) và tuân thủ giới hạn thời gian, bộ nhớ.

• Các nhóm test có tổng cộng \(30\) điểm thỏa mãn \(x_i+w_i-1\le10\,000\) với mọi \(1\le i\le N\), đồng thời \(N\le1\,000\).

Ví dụ

13 2
2 2 10
14 3 9
15 6 12
3 7 5
16 8 9
15 10 3
4 13 10
11 11 11
5 4 11
11 14 12
6 9 7
20 4 8
13 5 5
4
7

15 10
-1 -1