Problem Description

Given $N$ positive integers $A_1, A_2, \dots, A_N$ and a target integer $K$.

If a positive integer $X$ is a common multiple of $A_1, A_2, \dots, A_N$, then we call $X$ an optional number.

Now, you need to find the smallest positive integer $P$ such that for any optional number $X$, $\text{lcm}(X, P)$ (the least common multiple of $X$ and $P$) is divisible by $K$.

Input Format

The first line contains two integers $N$ and $K$.

The second line contains $N$ integers $A_1, A_2, \dots, A_N$.

Output Format

Output one integer, representing the smallest positive integer $P$ that satisfies the condition.

3 12
6 4 9

1

2 10
4 6

5

Hint

Constraints

For $20\%$ of the testdata, $1 \leq N \leq 20$, $1 \leq K, A_i \leq 10^6$.

For all testdata, $1 \leq N \leq 2 \times 10^5$, $1 \leq K, A_i \leq 10^{18}$.

Translated by ChatGPT 5