На таинственном острове капитан Флинт оставил карту сокровищ, на которой записаны подсказки в виде последовательности чисел — массив a. У пиратов есть стартовое значение x, которое им нужно преобразовать, следуя всем шагам на карте, чтобы добраться до сокровища.

Для каждого значения x, которое они выбирают, пираты идут по массиву a от начала до конца и выполняют следующие действия для каждого элемента массива:

Таким образом, в конце маршрута значение x становится новым числом, указывающим на местоположение клада.

К сожалению, пираты оказались очень слабы в математике (хотя бутылки рома считают отлично), поэтому они попросили у вас помощи в поиске клада. У них есть q чисел, возможные стартовые значения числа x. Вам необходимо для каждого из этих чисел вывести число, которое получается из него после действий, приведенных выше.

В первой строке вводится 2 целых числа n, q — количество чисел в массиве a и количество возможных начальных значений (1 ≤ n, q, ≤ 10⁶).

Во второй строке через пробел вводятся n целых чисел, задающих массив a. (|a_i| ≤ 10⁶).

В следующих q строках вводятся по одному целому числу x_i — возможные стартовые значения. (|x_i| ≤ 10⁶).

Выведите q строк. В i-й строке выведите единственное число — число, которое получилось после выполнения всех действий к числу x_i.