| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 4 | 3 | 3 | 75.000% |
Соседу Джека, потомственному магу Кевину, поручили заняться организацией праздничного парада гоблинов, вампиров и призраков. Чтобы соблюсти все древние традиции и задобрить духов, шествие должно непременно проходить на квадратной площади, сторона которой --- некоторая степень двойки. Задача Кевина --- украсить ее.
Для украшения площади ее необходимо покрыть треугольными плитками равного размера. Плитки должны иметь форму равнобедренного прямоугольного треугольника с длиной катета $2^i$ для некоторого целого $i$, и разбиваться на пары, образующие квадраты со стороной $2^i$.
Скажем, что плитка с длиной катета $2^i$ имеет размер $i$. У Кевина есть $n$ плиток с размерами $a_i$, то есть с катетами $2^{a_1}$, $2^{a_2}$, \ldots, и $2^{a_n}$ соответственно. При этом он всегда может получить из треугольника со стороной $2^k$ четыре треугольника со стороной $2^{k-1}$ для любого $k$.
Кевин считает, что чем больше сторона плиток, тем оформление площади красивее, поэтому хочет покрыть площадь треугольниками с максимальной возможной стороной.
К сожалению, он еще не определился с размерами площади, которую хочет оформлять. Поэтому он просит вас для каждой из $m$ интересующих его площадей со сторонами $2^{b_j}$ найти максимально возможную сторону плитки, которой можно покрыть площадь, используя только плитки, имеющиеся у него в наличии.
Первая строка содержит два целых числа $n$ и $m$, разделенные пробелом ($1 \leq n \leq 5 \cdot 10^5$; $1 \leq m \leq 5 \cdot 10^5$) --- количество плиток, которые есть в наличии, и количество интересующих Кевина размеров площадей.
В следующей строке через пробел перечислены $n$ целых чисел $a_i$ ($0 \leq a_i \leq 2 \cdot 10^5$) --- размеры плиток.
В третьей строке содержатся $m$ чисел $b_i$ ($0 \leq b_j \leq 2\cdot 10^5$) --- размеры интересующих Кевина площадей.
Для каждого из $m$ запросов выведите в отдельной строке максимально возможный размер плитки, которым Кевин может целиком покрыть площадь со стороной $2^{b_j}$, или же $-1$, если всей имеющейся у него плитки не хватит, чтобы покрыть площадь такого размера.
5 3 1 1 1 2 1 0 2 4
0 1 -1
7 7 1 1 1 2 2 1 2 0 1 2 3 4 5 6
0 1 2 -1 -1 -1 -1
В примере дано пять треугольных плиток: четыре со стороной $2^1$ и одна со стороной $2^2$.