Tiến sĩ Hanks là một chuyên gia nổi tiếng trong lĩnh vực công nghệ sinh học (Bio-Tech). Hiện tại, ông đang chuẩn bị cho một thí nghiệm tế bào: nuôi cấy mẫu tế bào.

Hiện trong tay tiến sĩ Hanks có \(N\) loại tế bào, được đánh số từ \(1 \sim N\), mỗi loại tế bào thứ \(i\) sau \(1\) giây có thể phân chia thành \(S_i\) tế bào cùng loại (\(S_i\) là số nguyên dương). Bây giờ ông cần chọn một loại tế bào để đưa vào đĩa nuôi cấy, cho chúng tự do phân chia. Sau một khoảng thời gian, ông sẽ chia đều số tế bào trong đĩa nuôi cấy vào \(M\) ống nghiệm để tạo thành \(M\) mẫu thử dùng trong thí nghiệm.

Số ống nghiệm \(M\) rất lớn, đến mức kiểu dữ liệu thông thường không thể lưu trữ được, nhưng may mắn là \(M\) luôn có thể biểu diễn dưới dạng \(m_1^{m_2}\), trong đó \(m_1\) và \(m_2\) đều là số nguyên dương có thể lưu trong kiểu dữ liệu cơ bản.

Lưu ý: Trong toàn bộ quá trình thí nghiệm, không được phép chia nhỏ một tế bào. Ví dụ, nếu tại một thời điểm có 4 tế bào, tiến sĩ Hanks có thể chia đều chúng vào 2 ống nghiệm, mỗi ống 2 tế bào. Nhưng nếu có 5 tế bào thì không thể chia đều vào 2 ống nghiệm, nên ông phải chờ thêm để số lượng tế bào tiếp tục phân chia sao cho có thể chia đều, hoặc đổi sang nuôi một loại tế bào khác.

Để bắt đầu thí nghiệm càng sớm càng tốt, sau khi chọn một loại tế bào để nuôi, tiến sĩ Hanks sẽ dừng việc nuôi cấy ngay khi số tế bào có thể vừa đủ chia đều vào \(M\) ống nghiệm và bắt đầu thí nghiệm.

Giờ đây, ông muốn biết nên chọn loại tế bào nào để thí nghiệm có thể bắt đầu trong thời gian ngắn nhất.

Định dạng vào

• Dòng đầu tiên là số nguyên dương \(N\), số loại tế bào.
• Dòng thứ hai là hai số nguyên dương \(m_1, m_2\), cách nhau bởi dấu cách. Tổng số ống nghiệm \(M = m_1^{m_2}\).
• Dòng thứ ba gồm \(N\) số nguyên dương, với số thứ \(i\) là \(S_i\), biểu diễn số tế bào mà loại thứ \(i\) tạo ra sau 1 giây.

Định dạng ra

• Một số nguyên duy nhất, biểu diễn thời gian ít nhất (tính bằng giây) kể từ khi bắt đầu nuôi tế bào cho đến khi có thể tiến hành thí nghiệm.
• Nếu không thể chia đều vào \(M\) ống nghiệm với bất kỳ loại tế bào nào, in ra -1.

Input 1

1 
2 1 
3

Output 1

-1

Giải thích:

Sau 1 giây có 3 tế bào, sau 2 giây có 9, sau 3 giây có 27... Tất cả đều là số lẻ, nên không thể chia đều vào 2 ống nghiệm → in -1.

Input 2

2
24 1
30 12

Output 2

2

Giải thích:

• Loại thứ 1 sau 3 giây mới chia đều cho 24.
• Loại thứ 2 sau 2 giây đã chia đều được cho 24. → chọn loại 2, kết quả là 2.

Ràng buộc dữ liệu

• Với 50% số test: \(m_1^{m_2} \le 30000\)
• Với toàn bộ dữ liệu:
  • \(1 \le N \le 10000\)
  • \(1 \le m_1 \le 30000\)
  • \(1 \le m_2 \le 10000\)
  • \(1 \le S_i \le 2 \times 10^9\)