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

Có sự thay đổi ở giới hạn bài toán. Vui lòng xem kỹ lại phần giới hạn.

Ở một gia đình nọ có 4 người. Người cha tên là Tổng, người mẹ tên là Hai Số. Không biết hai vợ chồng canh ngày tháng thế nào mà 2 đứa con đều sinh ra cùng ngày tháng mặc dù là khác năm. Hai đứa con có tên là Khó và Lắm.

Tối nay là Trung thu, đôi vợ chồng Tổng, Hai Số lên kế hoạch mua cho 2 đứa con Khó, Lắm mỗi đứa X viên kẹo. Để niềm vui được trọn vẹn, X phải là số ưa thích của cả Khó và Lắm. Dõi theo từng ngày Lắm lớn khôn, cặp vợ chòng ấy đã tìm được thông tin về những số mà Lắm thích. Lắm chỉ thích đúng P số đặc biệt. P số này được cha mẹ của Lắm ghi lại nhưng trong quá trình ghi chép lại gặp một số vấn đề nên có thể có trường hợp 1 số bị lặp lại nhiều lần cho nên danh sách được ghi lại sẽ có Q số. Khó là anh nên có vẻ hơi khó chiều hơn. Vì là một lập trình viên giỏi nên Khó đã viết một thủ tục Find(x) bằng PASCAL và input của thủ tục là một dãy A gồm N số không giảm. Dãy số là cố định và x là số cần kiểm tra xem Khó có thích hay không.

procedure Find(x: longint);

var i,j: longint;

Begin

i := 1;

j := n;

while  i < j do

begin

        if A[i] + A[j] = x

begin

writeln(i,’ ‘,j);

exit;

end;

        ìf A[i] + A[j] > x

j := j-1

    else

i := i+1;

end;

writeln(‘-1 -1’);

end;

Biết rằng nếu cặp số được in ra là (-1, -1 ) thì Khó không thích số đó. Giờ cha mẹ của Khó, Lắm phải tìm xem cặp số được in ra sau khi thực hiện thủ tục Find cho từng số trong danh sách Q số. Vì Q khá lớn nên Tổng, Hai Số đã nhờ tới các bạn lập trình viên VNOI_er giải quyết giúp vấn đề này.

Lưu ý: Mảng A được đánh số từ 1 tới N từ trái sang phải.

DỮ LIỆU VÀO

• Dòng dầu chứa số nguyên dương N.
• Dòng hai chứa N số miêu tả dãy A (A[i] <= A[i+1]).
• Dòng ba chứa số nguyên dương Q.
• Q dòng tiếp theo, dòng thứ i chứa số thứ i trong danh sách Q số mà Lắm thích.

DỮ LIỆU RA

• Gồm Q dòng, dòng thứ i chứa cặp số được in ra khi thực hiện thủ tục Find cho số thứ i.

RÀNG BUỘC

• N ≤ 10⁴, Q ≤ 10⁶.
• 60% số test N ≤ 10³, Q ≤ 10⁵.
• 0 ≤ Ai ≤ 10⁹.
• Các số trong danh sách số đặc biệt của Lắm là số nguyên không âm và tối đa là 2*10⁹.

VÍ DỤ

Dữ liệu vào
6
1 2 3 4 5 6
4
6
9
5
12
Dữ liệu ra
1 5
3 6
1 4
-1 -1