E. Вика и блинчики
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В родном городе Вики, Владивостоке, очень красивое море.

Часто можно видеть ребят, запускающих «блинчики» или «лягушки». Так называется процесс кидания камня в море под небольшим углом, отчего он далеко летит и несколько раз отскакивает от водной глади.

Вика много раз запускала «блинчики» и знает, что если кинуть камень от берега перпендикулярно береговой линии с силой $$$f$$$, то он сперва коснётся воды на расстоянии $$$f$$$ от берега, затем оттолкнётся и вновь коснётся воды на расстоянии $$$f - 1$$$ от предыдущей точки касания. Так камешек будет лететь по прямой, всё сокращая расстояния между точками, в которых он касается воды, пока не упадёт в море.

Формально, точки в которых камень соприкоснётся с водной гладью будут иметь следующие координаты: $$$f$$$, $$$f + (f - 1)$$$, $$$f + (f - 1) + (f - 2)$$$, ... , $$$f + (f - 1) + (f - 2) + \ldots + 1$$$ (если считать, что $$$0$$$ — координата береговой линии).

Как-то раз прогуливаясь вечером по набережной Владивостока, Вика увидела, как группа ребят запускала «блинчики» в море с одной и той же точки с разными силами.

Ей стало интересно, какое максимальное количество ребят могут запустить камешек со своей силой $$$f_i$$$, так чтобы все $$$f_i$$$ были различными целыми положительными числами, и при этом все $$$n$$$ камешков в процессе полёта коснулись воды в точке с координатой $$$x$$$ (если считать, что $$$0$$$ — координата береговой линии).

Немного подумав, Вика ответила на свой вопрос. После этого она начала анализировать, а как будет изменятся ответ на её вопрос, если координату $$$x$$$ домножать на некоторые положительные целые числа $$$x_1$$$, $$$x_2$$$, ... , $$$x_q$$$, выбранные ей для анализа.

Вике сложно справится с таким анализом самостоятельно, поэтому она обратилась к вам за помощью.

Формально, Вику интересует ответ на её вопрос для координат $$$X_1 = x \cdot x_1$$$, $$$X_2 = X_1 \cdot x_2$$$, ... , $$$X_q = X_{q-1} \cdot x_q$$$. Так как ответ для таких координат может быть очень большой, найдите его по модулю $$$M$$$. Гарантируется, что число $$$M$$$ является простым.

Входные данные

В первой строке входных данных содержится три целых числа $$$x$$$ ($$$1 \le x \le 10^9$$$), $$$q$$$ ($$$1 \le q \le 10^5$$$) и $$$M$$$ ($$$100 \le M \le 2 \cdot 10^9$$$) — изначальная координата, для которой Вика ответила на вопрос самостоятельно, количество чисел $$$x_i$$$, на которые Вика будет домножать изначальную координату и простой модуль $$$M$$$.

Во второй строке входных данных содержится $$$q$$$ чисел $$$x_1, x_2, x_3, \ldots, x_q$$$ ($$$1 \le x_i \le 10^6$$$) — описанные в условии числа.

Выходные данные

Выведите $$$q$$$ целых чисел, где $$$i$$$-е число соответствует ответу на вопрос Вики для координаты $$$X_i$$$. Все ответы выводите по модулю $$$M$$$.

Примеры
Входные данные
1 2 179
2 3
Выходные данные
1
2
Входные данные
7 5 998244353
2 13 1 44 179
Выходные данные
2
4
4
8
16
Входные данные
1000000000 10 179
58989 49494 8799 9794 97414 141241 552545 145555 548959 774175
Выходные данные
120
4
16
64
111
43
150
85
161
95
Примечание

В первом примере, чтобы камешек коснулся водной глади в точке с координатой $$$2$$$, его нужно кинуть с силой $$$2$$$. Чтобы камешек коснулся воды в точке с координатой $$$2 \cdot 3 = 6$$$, его нужно кинуть с силой $$$3$$$ или с силой $$$6$$$.

Во втором примере можно запустить «блинчик» с силой $$$5$$$ или $$$14$$$, чтобы он коснулся в воды в точке с координатой $$$7 \cdot 2 = 14$$$. Для координаты $$$14 \cdot 13 = 182$$$ есть $$$4$$$ варианта сил — это $$$20$$$, $$$29$$$, $$$47$$$, $$$182$$$.