Summer FLASG Advanced | VeverițaAdvanced

This was the problem page during the contest. Access the current page here.
Time limit: 0.15s Memory limit: 64MB Input: Output:

ASG a decis după 4 luni să iasă afară să atingă iarbă și să-și mai ia niște țevi noi de dat în cap. A remarcat că în spatele curții lui se află niște veverițe care-l tot deranjau, așa că a decis să scape de ele. Flaviu, neștiind ce e cu toată dezordinea și mersul haotic al lui ASG, s-a dus în curte și l-a văzut nervos. El l-a chemat înapoi în casă pentru a se calma cu o înghețată și apoi l-a rugat să îl ajute cu o problemă de matematică pe care a primit-o de la meditație.

Fie aa un șir de NN numere naturale nenule. Se definește funcția ff astfel:

f(x)=x+dxd1adf(x) = x + \sum_{\begin{subarray}{c}d | x\\d \geq 1\end{subarray}} a_{d}

Cerință

Dându-se QQ întrebări de tipul xx, să se afle cel mai mare număr yy cu proprietatea că f(y)xf(y) \leq x.

Date de intrare

Pe prima linie se găsesc două numere naturale QQ și NN.

Pe a doua linie sunt NN numere naturale ce reprezintă șirul aa.

Pe următoarele QQ linii se află câte un număr xx, reprezentând o întrebare.

Date de ieșire

Pe fiecare dintre cele QQ linii se vor găsi câte un singur număr reprezentând răspunsurile la întrebări. Dacă nu există soluție se va afișa -1.

Restricții și precizări

  • 1N,Q200 0001 \leq N, Q \leq 200\ 000
  • 1ai1 0001 \leq a_i \leq 1\ 000
  • 1x200 000 0001 \leq x \leq 200\ 000\ 000
  • 1yN1 \leq y \leq N
    # Punctaj Restricții
    1 40 1N,Q2 0001 \leq N, Q \leq 2 \ 000
    2 60 Fără alte restricții.

Exemplul 1

stdin

6 4
2 3 2 5 
6
4 
2
10
5
8

stdout

1
1
-1
3
1
3

Log in or sign up to be able to send submissions!