A. Square Sum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an integer $$$m$$$ and a sequence of integers $$$z_1,\dots,z_n$$$.

For each $$$z_i$$$, calculate the number of integers $$$x$$$, $$$y$$$ ($$$0 \leq x, y \lt m$$$) such that $$$$$$ x^2 + y^2 \equiv z_i \pmod m. $$$$$$

Input

First line of input contains two integers $$$m$$$ ($$$1 \leq m \leq 10^9$$$) and $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$z_i$$$ ($$$0 \leq z_i \lt m$$$).

Output

For each $$$z_i$$$, output the number of pairs $$$x$$$, $$$y$$$ ($$$0 \leq x, y \lt m$$$) such that $$$x^2 + y^2 \equiv z_i \pmod m$$$.

Examples
Input
3 3
0 1 2
Output
1 4 4
Input
4 4
0 1 2 3
Output
4 8 4 0
Input
5 1
3
Output
4