Sau khi dựng xong nhà kho chứa cỏ, dì Poly quyết định dùng ~m~ tấm gỗ còn thừa để gia cố hàng rào vườn rau, ngăn không cho gà vào phá. Hàng rào hiện tại được ghép từ ~n~ tấm gỗ có cùng độ rộng, tấm thứ ~i~ có độ cao ~a_i~.

Các tấm gỗ còn thừa được chất lên xe ba gác thành một chồng. Tính từ trên xuống, tấm thứ ~j~ trong chồng có độ cao ~b_j~.

Jim kéo xe đi dọc theo hàng rào từ tấm ~1~ đến tấm ~n~. Khi muốn gia cố tấm hàng rào nào đó, Jim sẽ lấy một tấm gỗ từ xe và đóng chồng lên tấm đó (mỗi tấm hàng rào chỉ được đóng thêm tối đa một lần). Khi đóng tấm ~b_y~ lên tấm hàng rào ~x~, độ cao mới của tấm hàng rào ~x~ trở thành ~a_x + b_y~.

Jim chỉ có thể lấy tấm gỗ ở trên cùng của chồng. Nếu tấm trên cùng không phù hợp, Jim có thể vứt bỏ một số tấm trên cùng cho đến khi gặp tấm vừa ý. Các tấm đã vứt bỏ sẽ mất vĩnh viễn, không thể xếp lại lên xe, và Jim cũng không quay lại lấy những tấm đã loại.

Độ cao của hàng rào sau khi gia cố được tính bằng độ cao tấm thấp nhất trong ~n~ tấm.

Yêu cầu

Hãy tìm cách gia cố để độ cao hàng rào (tức ~\min~ các độ cao cuối cùng) là lớn nhất có thể. Đồng thời, hãy in ra một phương án gia cố đạt được giá trị lớn nhất đó.

Dữ liệu

• Dòng 1: số nguyên ~n~ (~1 \le n \le 10^5~).
• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^8~).
• Dòng 3: số nguyên ~m~ (~1 \le m \le 10^5~).
• Dòng 4: ~m~ số nguyên ~b_1, b_2, \dots, b_m~ (~1 \le b_j \le 10^8~). (tấm ~b_1~ ở trên cùng)

Kết quả

In theo cấu trúc:

• Dòng đầu: hai số nguyên ~h~ và ~k~ — ~h~ là độ cao lớn nhất có thể của hàng rào, ~k~ là số tấm gỗ đã đóng thêm.

• Trong ~k~ dòng tiếp theo: mỗi dòng chứa hai số nguyên ~x~ và ~y~:

  • ~x~ là chỉ số tấm hàng rào được gia cố,
  • ~y~ là chỉ số tấm gỗ trên xe được dùng (theo thứ tự ban đầu từ trên xuống).

Các cặp ~(x,y)~ phải có thứ tự thực hiện hợp lệ khi Jim đi từ trái sang phải: ~x~ tăng dần và ~y~ tăng dần (tương ứng với việc chỉ lấy/loại tấm gỗ theo thứ tự từ trên xuống).

Nếu có nhiều phương án, in ra bất kỳ.

Ví dụ

Ví dụ 1

Input

6
2 5 4 1 7 5
7
2 3 1 3 2 4 6

Output

5 3
1 2
3 4
4 7

Giải thích

Ví dụ 1

Chọn gia cố:

• Tấm ~1~ dùng gỗ ~b_2=3~: ~2+3=5~ (bỏ ~b_1=2~).
• Tấm ~3~ dùng gỗ ~b_4=3~: ~4+3=7~ (bỏ ~b_3=1~).
• Tấm ~4~ dùng gỗ ~b_7=6~: ~1+6=7~ (bỏ ~b_5=2~, ~b_6=4~).

Các tấm còn lại đã có độ cao ≥ ~5~, nên độ cao hàng rào (tấm thấp nhất) đạt ~5~.

Ràng buộc và chấm điểm

• ~1 \le n, m \le 10^5~
• ~1 \le a_i, b_j \le 10^8~
• Mỗi tấm hàng rào được gia cố tối đa ~1~ lần.
• Chỉ được dùng các tấm gỗ theo thứ tự từ trên xuống, có thể vứt bỏ nhưng không thể lấy lại.