Unlocking the Explorer's Lock

During an expedition, little \( \zeta \) encountered a large lock. This lock is equipped with \( n \) dials. The \( i\)-th dial can be set to any integer in the range \( [l_i, r_i] \) (inclusive), where \( l_i \le r_i \). The freedom degree of the lock is defined as the greatest common divisor (GCD) of the numbers chosen on all dials:

[ \gcd(x_1, x_2, \ldots, x_n) \ge k ]

The lock opens if its freedom degree is at least \( k \). Your task is to find a setting of the dials such that the above condition holds, or report that no such setting exists.

inputFormat

The first line contains two integers \( n \) and \( k \) (the number of dials and the threshold, respectively).

The following \( n \) lines each contain two integers \( l_i \) and \( r_i \) representing the range of the \( i\)-th dial.

It is guaranteed that \( l_i \le r_i \) for all \( i \).

outputFormat

If there is a valid setting, output \( n \) integers, where the \( i\)-th integer is the value chosen for the \( i\)-th dial. The chosen numbers must satisfy \( l_i \le x_i \le r_i \) for every \( i \) and \( \gcd(x_1, x_2, \ldots, x_n) \ge k \).

If no valid setting exists, output -1.

sample

3 2
1 3
2 4
2 6

2 2 2