В далеком 2094 году в Киберславле, простояв в очереди длиной полквартала, Q покупателей пришли в продовольственный магазин. Здесь на полках расположены товары N типов, каждый из которых стоит ai крышек. Причём запас товаров в таком профиците, что можно считать количество товаров каждого типа неограниченным.
Каждый покупатель хочет приобрести товаров на максимально возможную сумму из имеющихся у него средств, но может и оказаться, что крышек недостаточно для покупки какого-либо из товаров. Вместе с тем у покупателя должно остаться ненулевое количество крышек. Два товара одного типа он купить не может в силу политики магазина, направленной на сохранение продовольственного профицита. Также каждый покупатель может приобретать только рядом стоящие товары, так как такие магазины обслуживаются роботами-продавцами на салазках.
Для каждого покупателя определите ненулевую сумму, которая окажется у него после покупки товаров по вышеуказанным правилам.
В первой строке через пробел записаны два числа N и Q (1 ≤ N, Q ≤ 104) – количество типов товаров и покупателей соответственно.
Во второй строке через пробел записаны N чисел ai – цена каждого товара (1 ≤ ai ≤ 109).
В третьей строке через пробел записаны Q чисел bi – количество денег у каждого покупателя (1 ≤ bi ≤ 109).
В единственной строке через пробел выведите Q чисел – минимальную ненулевую сумму, которая останется у каждого покупателя.
Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
2 5
6 5
2 1 7 9 7
2 1 1 3 1
