童年时你学会的求余运算，更专业的名称是模运算。进入大学后，小明和小璐知道了模运算中逆元的概念。
已知互质的正整数n和a，a<n，将n作为模，则a的逆元b是满足如下条件的正整数：b<n并且(a*b)%n=1。实际上a的逆元是唯一的。
例如：设n=9,a=2，n和a互质，a的唯一的逆元b是5。
输入二行，第1行是整数n（n<10000）和k个正整数（k<100）。第2行是k个大于1的正整数a1, a2,……, ak，均小于n，用空格分开。
输出一行，k个整数。分别表示a1, a2,……, ak的逆元。若ai与n不互质，则对应输出0。

测试案例：
输入

9 7
5 6 7 8 2 3 4

输出：

2 0 4 8 5 0 7