Masala #N6CXIW0ZUH

Robolandiya Markaziy bankida \(N\)ta banknota qolgan, va ularning qiymati \(A_1, A_2, ..., A_N\) robodollarga teng. Robolandiya banknotalarining bir ajoyib xususiyati bor: ixtiyoriy \(A_i\) va \(A_j\) banknotalar uchun \((1 \le i, j \le N)\) ulardan biri boshqasiga qoldiqsiz bo‘linadi.

Bankning \(Q\)ta potensial mijozi bor va har bir mijoz ma’lum bir miqdorda pul qarzga olmoqchi. Agar mijoz bankdan \(X_i\) robodollar qarz olmoqchi bo‘lsa, bank bu pullarni qaytimsiz bera oladigan bo‘lsa, buning uchun eng minimal nechta banknotalar ishlatish mumkin? Sizning vazifangiz shu savolga javob berish. Agar qaytimsiz qarz berishning iloji bo‘lmasa \(-1\) deb chiqaring. 

E’tibor bering, sizning dasturingiz mijozlarga pullarni bermaydi, ya’ni so‘rovlar bir biriga ta’sir etmaydi.

Kirish oqimining birinchi qatorida bitta butun son - \(N\) - jami banknotalar soni beriladi. \((1 \le N \le 2 \cdot 10^5)\)
Kirish oqimining ikkinchi qatorida probel bilan ajratilgan \(N\)ta butun son - \(A_1, A_2, ..., A_N\) - banknotalar qiymati kiritiladi. Istalgan ikki sondan biri boshqasiga bo‘linishi kafolatlanadi. \((1 \le A_i \le 10^{18})\)
Kirish oqimining uchinchi qatorida butun son - \(Q\) - mijozlar soni kiritiladi. \((1 \le Q \le 2 \cdot 10^5)\)
Kirish oqimining to‘rtinchi qatorida probel bilan ajratilgan \(Q\)ta butun son - \(X_1, X_2, ..., X_Q\) - mijoz so‘rab kelgan qarz miqdori kiritiladi. \((1 \le X_i \le 10^{18})\)

Har bir mijoz uchun qarz berish mumkin bo‘lgan minimal banknotalar sonini chiqaring, buning iloji bo‘lmasa \(-1\) chiqaring.