Quiz Master
Contest: Codeforces Round 845 (Div. 2) and ByteRace 2023
Difficulty rating: 1700
Tags: binary search, math, number theory, sortings, two pointers

A school has to decide on its team for an international quiz. There are $$$n$$$ students in the school. We can describe the students using an array $$$a$$$ where $$$a_i$$$ is the smartness of the $$$i$$$-th ($$$1 \le i \le n$$$) student.

There are $$$m$$$ topics $$$1, 2, 3, \ldots, m$$$ from which the quiz questions will be formed. The $$$i$$$-th student is considered proficient in a topic $$$T$$$ if $$$(a_i \bmod T) = 0$$$. Otherwise, he is a rookie in that topic.

We say that a team of students is collectively proficient in all the topics if for every topic there is a member of the team proficient in this topic.

Find a team that is collectively proficient in all the topics such that the maximum difference between the smartness of any two students in that team is minimized. Output this difference.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, print the answer on a new line. If there is no solution, output $$$-1$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we have participants with smartnesses $$$3$$$ and $$$7$$$, and $$$m = 4$$$. Thus, there is no student with smartness divisible by $$$2$$$. Since $$$2 \leq m$$$, there is no way to choose a team.

In the second test case, we can select the participant with smartness $$$2$$$ to be the only one on the team. This way the team will be collectively proficient in both topics $$$1$$$ and $$$2$$$.

In the third test case, consider the team with participants of smartnesses $$$4, 5, 6, 7$$$. This way the team will be collectively proficient in all topics $$$1, 2, \ldots, 7$$$.

Example input:
3
2 4
3 7
4 2
3 7 2 9
5 7
6 4 3 5 7

Example output:
-1
0
3

Editorial:
We can sort the smartness values and use two pointers.
The two pointers indicate the students we are considering in our team. Let $$$l$$$ be the left pointer and $$$r$$$ be the right pointer.
$$$a_l$$$ is the minimum smartness of our team and $$$a_r$$$ is the maximum. If this team is collectively proficient in all topics, then the difference would be $$$a_r - a_l$$$.
Now, if $$$l$$$ is increased, the team may lose proficiency in some topics. $$$r$$$ would either stay the same or increase as well for the team to become proficient again.
For a team to be proficient, each number from $$$1$$$ to $$$m$$$ should have a smartness value which is a multiple of it.
To check for proficiency, we can maintain a frequency array $$$f$$$ of size $$$m$$$ and a variable $$$count$$$ to indicate the number of topics that have found a multiple.
When we add a student to the team, we iterate through all the factors of their smartness which are less than or equal to $$$m$$$ and increase their frequency. If an element had a frequency of $$$0$$$ before, then $$$count$$$ is increased by $$$1$$$.
Similarly, when we remove a student from the team, we go through all the factors less than or equal to $$$m$$$ and decrease their frequency. If an element now has $$$0$$$ frequency, then $$$count$$$ is decreased by $$$1$$$.
$$$count$$$ being equal to $$$m$$$ at any point indicates a collectively proficient team.