Cho ~n~ cọc, cọc thứ ~i~ có ~a_i~ ~(a_i>0)~ quân. Cho hai người chơi là ~A~ và ~B~ lần lượt thực hiện lượt chơi. Tại mỗi lượt chơi, người chơi có thể chọn 1 cọc (còn quân) bất kỳ rồi lấy bớt quân cờ ở cọc này từ ~1~ đến hết quân. Người chiến thắng là người lấy được quân cờ cuối cùng.

Biết rằng, người ~A~ là người thực hiện lượt chơi đầu tiên và cả hai người đều chơi rất giỏi.

Hãy cho biết trong lượt chơi đầu tiên của người ~A~ cần phải chọn cọc nào và lấy bao nhiêu quân cờ trên cọc đó để chắc chắn dành chiến thắng.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương ~n~ ~(1≤n≤10^6)~ cho biết số cọc
• Dòng tiếp theo ghi lần lượt các số nguyên ~a_1,a_2,…,a_n~ ~(0≤a_i≤10^9)~ trong đó số ~a_i~ cho biết số quân cờ trên cọc thứ ~i~.

Kết quả:

• Ghi tất cả các trường hợp người ~A~ chọn trong lượt chơi đầu tiên để dành chiến thắng, mỗi trường hợp gồm hai số ~x,y~ trong đó ~x~ cho biết chỉ số cọc mà người ~A~ chọn và ~y~ cho biết số quân cờ người ~A~ lấy trên cọc ~x~. Mỗi kết quả được ghi trên 1 dòng theo thứ tự tăng dần của ~x~.
• Trong trường hợp không có cách chọn thì ghi ~-1~

Ví dụ:

Input

4
12 8 5 14 

Output

1 9
2 1
4 13 

Ràng buộc:

• Có 20% số test có ~n≤100~ và ~a_i≤100~ ~(i=1…n)~
• Có 60% số test khác có ~n≤1000~ và ~a_i≤1000~ ~(i=1…n)~
• Có 20% số test còn lại không có ràng buộc gì thêm