D. Least Uncommon Divisor
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

For two positive integers $$$x$$$ and $$$y$$$, define $$$lud(x,y)$$$ as the smallest positive integer $$$z$$$ that divides $$$x$$$ and doesn't divide $$$y$$$. If there is no such element, then $$$lud(x,y) = -1$$$.

For example:

$$$lud(6,4) = 3$$$

$$$lud(8,10) = 4$$$

$$$lud(10,20) = -1$$$

Given an array $$$a$$$ of size $$$n$$$ and an integer $$$x$$$, for each $$$i$$$ $$$(1 \le i \le n)$$$, find $$$lud(x,a_i)$$$.

Input

The first line contains two integers $$$n$$$ and $$$x$$$ $$$(1 \le n \le 10^6)$$$ $$$(1 \le x \le 10^{12})$$$, the length of the array $$$a$$$ and the integer $$$x$$$ respectively.

The second line contains $$$n$$$ integers $$$(1 \le a_i \le 10^{12})$$$, the elements of the array $$$a$$$.

Output

Print $$$n$$$ integers, the $$$i_{ith}$$$ of which is $$$lud(x,a_i)$$$.

Example
Input
5 30
6 10 15 35 60
Output
5
3
2
2
-1