U508234 The Magical River Bird

~~**Please submit in [Chinese version](https://www.luogu.com.cn/problem/T472989?contestId=183429)!**~~ I wish a good future to enjoy, and a good memories to traceback.

Little ζ discovered a large lock during his adventure. This lock has $n$ dials, where the $i$-th dial can be set to any integer from $l_i$ to $r_i$ (inclusive, and $l_i ≤ r_i$ is guaranteed). We define the lock’s “degree of freedom” as the greatest common divisor (GCD) of all numbers shown on the dials. The lock opens when its “degree of freedom” is greater than or equal to $k$. Your task is to find a valid combination to open the lock, or report if it’s impossible.

无

无

**「Sample 1 Explanation」** For the only test case, the $\gcd$ is 10. All five samples can be tested using the provided attachment. Note that some samples may have multiple valid solutions; the sample output shows just one possible solution. **「Data Constraints」** For 100% of testcases：$ 1 \le T \le 5 $，$ 2 \le n \le 10^4 $，$ 1 \le l_i \le r_i \le 10^9 $，$ 1 \le k \le 1000 $。 **This problem uses subtask scoring。** * Subtask 1（10 pts）：$ k=1 $。 * Subtask 2（15 pts）：$ n \le 10 $，$ r_i - l_i + 1 \le 5 $。 * Subtask 3（15 pts）：$ r_i \le 10^3 $。 * Subtask 4（10 pts）：$ k \le 5 $，$ l_i, r_i $ are randomly generated with uniform distribution in range $ [1, 10^9] $, this subtask has only one test point. * Subtask 5（15 pts）：For all cases，$ \exist 1 \le i \le n,l_i=r_i $。 * Subtask 6（35 pts）：No additional constraints. **「About Additional Files」** A `checker.cpp` is provided as a testing tool. Place your input content, program output, and reference answer in `restore.in`, `restore.out`, and `restore.ans` respectively. These three files must be in the same directory as `checker.cpp`. Run `checker.cpp` to see the testing results. Your input must satisfy the constraints for $100\%$ of test cases. Note that if your input/output/answer format or range is incorrect, the results from checker.cpp are unpredictable. Therefore, please ensure your three files are correctly formatted first.