• Nếu a_i mod 3 = 0, thì tiền thuê mới là a_i + a_j.
• Nếu a_i mod 3 = 1, thì tiền thuê mới là 2a_i + (a_j div 2).
• Nếu a_i mod 3 = 2, thì tiền thuê mới là 4a_i + (a_j div 4).

Theo luật của chủ chung cư Sao Khuê, mỗi một năm chỉ có không quá một cửa hàng được phép mở rộng và khi có cửa hàng mở rộng dãy các cửa hàng được đánh số lại bắt đầu từ 1 từ trái qua phải. Sau N−1 năm, chủ chung cư Sao Khuê giật mình khi phát hiện ra rằng chỉ còn lại duy nhất một cửa hàng ở chung cư. Để tìm hiểu quá trình phát triển của cửa hàng, chủ chung cư đã tìm đến sổ sách. Đáng tiếc là do sự bất cẩn của kế toán, sổ sách ghi nhận chi tiết đã bị thất lạc, chỉ còn lại giá thuê các cửa hàng trong năm đầu tiên và năm thứ N−1.

Yêu cầu: Hãy giúp chủ chung cư Sao Khuê khôi phục thông tin về quá trình phát triển của cửa hàng hiện nay.

Dữ liệu

• Dòng đầu tiên ghi số N.
• Dòng thứ hai chứa dãy số nguyên dương a₁, a₂, ..., a_N.
• Dòng thứ ba chứa số nguyên là số tiền thuê cửa hàng hiện nay.

Kết qủa

Ghi ra N−1 dòng, dòng thứ i chứa hai số nguyên theo thứ tự là chỉ số của cửa hàng mở rộng và cửa hàng đóng cửa trong năm thứ i, i=1, 2, ..., N−1. (Nếu có nhiều cách khôi phục, chỉ cần đưa ra một cách tùy ý).

Giới hạn

• Dữ liệu luôn đảm bảo có ít nhất một cách khôi phục.
• Trong tất cả các test: 1 ≤ N ≤ 30; a_i ≤ 32000, i =1, 2, ..., N.
• Có 50% số lượng test với N ≤ 15.

Ví dụ

<strong>Dữ liệu:</strong>
3
3 2 4
21
 
<strong>Kết qủa</strong>
1 2
1 2