G. Journey to Nome
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It's time for the Iditarod Sled Dog Race! The Iditarod is an intense race that stretches from Willow, Alaska all the way to Nome, Alaska. The race can take a couple weeks to complete, so it's important to find places to take a break.

Dallas Seavey is one of the competitors in the race, and he has a favorite number $$$M$$$. In the race, there is a checkpoint every mile, but Dallas will only stop at the $$$i$$$th checkpoint if $$$i$$$ is relatively prime with $$$M$$$. (Stopping at any other checkpoint would be bad luck.)

Two numbers are relatively prime if they share no common factors other than 1. You are given this special number $$$M$$$, and a list of $$$N$$$ integers. Dallas wants to know: for each integer $$$a_i$$$ in the list, what is the $$$a_i$$$th-smallest positive integer that is relatively prime with $$$M$$$?

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 10^6, 2 \le M \le 10^5$$$). The second line contains $$$N$$$ integers $$$a_1, a_2, …, a_N$$$ ($$$1 \le a_i \le 10^9$$$).

Output

Print out one line containing $$$N$$$ positive integers, where the $$$i$$$th integer is the $$$a_i$$$th-smallest positive integer that is relatively prime with $$$M$$$. Note that 1 is relatively prime with every number.

Example
Input
3 6
3 7 12
Output
7 19 35