Nhân dịp kỉ niệm 100 năm thành lập, ngân hàng EDU dự định dành không quá ~n~ đồng cho sinh viên vay vốn không lãi suất. Có ~m~ sinh viên đăng ký vay vốn, các sinh viên được đánh số từ ~1~ đến ~m~, sinh viên thứ ~i~ đăng ký vay ~t_i~ đồng ~(i = 1, 2, ..., m)~. Ngân hàng muốn đáp ứng được cho nhiều sinh viên nhất và đương nhiên nếu sinh viên thứ ~i~ được vay vốn thì phải bảo đảm nhận đúng ~t_i~ đồng. Trong các cách lựa chọn các sinh viên vay vốn thỏa mãn điều kiện, ngân hàng muốn chọn cách cho vay mà sinh viên vay ít nhất là lớn nhất.

Yêu cầu: Cho ~t_1, t_2, ..., t_m~ và ~Q~ giả định ~n_1, n_2, ..., n_Q~, trong đó, ~n_k~ là giả định thứ ~k (k = 1, 2, ..., Q)~, khi ngân hàng dự định dành không quá ~n_k~ đồng cho sinh viên vay vốn, với mỗi giả định này, hãy đưa ra cách cho vay thỏa mãn điều kiện đề bài.

Input

• Dòng đầu chứa hai số nguyên ~m, Q~.
• Dòng thứ hai chứa ~m~ số nguyên dương ~t_1, t_2, ..., t_m (t_i ≤ 10^9~).
• Dòng thứ ba chứa ~Q~ số nguyên dương ~n_1, n_2, ..., n_Q (n_i ≤ 10^{18}~).

Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.

Giới hạn:

• Có 25% số test ứng với 25% số điểm của bài có ~m, Q ≤ 10~;
• Có 25% số test khác ứng với 25% số điểm của bài có ~m, Q ≤ 300~;
• Có 25% số test khác ứng với 25% số điểm của bài có ~m, Q ≤ 6000~;
• Có 25% số test khác ứng với 25% số điểm của bài có ~m, Q ≤ 90000~;

Output

• Gồm ~Q~ dòng, mỗi dòng chứa hai số nguyên ~s, v~, trong đó ~s~ là số lượng sinh viên được vay vốn, ~v~ là số tiền mà sinh viên được vay ít nhất tương ứng với giả định trong dữ liệu vào.

Sample

Input #1

5 2
1 3 2 3 5
6 8

Output #1

3 1
3 2

Problem source: Kc97ble - Free Contest 40