Masala #0255

Xotira 64 MB Vaqt 1000 ms
14

To’g’ri to’rtburchak

Sunnat va Zarif juda ham yaqin do’stlar ular odatda birlashib xalqaro olimpiadalarga tayyorgarlik ko’rishadi, vaholangki Sunnat o’ta kuchli matematik, Bir kuni do’stlar bir o’yin o’ynashmoqchi bo’lishdi, shartni Zarif topdi, Zarif bergan \(K\) ta sonlardan eng katta yuzali to’g’ri to’rtburchak (kvadrat ham bunga mos keladi) shakl yasash.

Bu holatda Zarif Sunnatni qiynab qo’yish maqsadida doimi to’g’ri to’rtburchak yasash imkoni yo`q sonlarni berishi mumkin, bu holatni oldini olish maqsadida o’yinga Husayn ham qo’shildi, Husayn Zarifga \(N\) ta son beradi va bu sonlardan Zarif \(K\) tasini Sunnatga berishi kerakki Sunnat to’g’ri to’rtburchak hosil qila olmasin agar ilojini topolmasa eng kichik yuzali to’g’ri to’rtburchak yasaydigan holatga keltirishi kerak.

Sizga Husayn Zarifga beradigan \(N\) ta sonni beramiz siz Zarif ham Sunnat ham optimal o’ynaganida bo’lishi mumkin bo’lgan eng katta to’g’ri to’rtburchak yuzasini toping agar iloji bo’lmasa \(-1\) chiqaring!

 


Kiruvchi ma'lumotlar:

Birinchi qatorda \(N (0 < K \le N \le 10^6)\) sonlar soni va Zarif tanlab olishi kerak bo'lgan sonlar soni.

Keyingi qatorda \(N\) ta butun \(A_i (0 < A_i \le 10^9)\) sonlari beriladi

 

Chiquvchi ma'lumotlar:

Yagona butun son masala yechimini chiqaring!


Misollar
# input.txt output.txt
1
5 5
1 2 1 4 2 
2
2
10 7
1 2 2 4 1 6 1 1 9 5 
-1
3
9 5
1 1 2 1 1 3 6 6 4 
-1