31591번 - Combination Lock 스페셜 저지다국어

문제

Your house is protected by a combination lock containing $n$ rotating discs, numbered from 1ドル$ to $n$. On a typical combination lock, each rotating disc has 10ドル$ symbols, represented by integers between 0ドル$ to 9ドル,ドル inclusive. Since you are a mathematician, your combination lock is not typical. Instead, each rotating disc on your combination lock may have a different number of symbols. In particular, rotating disc $i$ has $b_i - a_i + 1$ symbols, represented by integers between $a_i$ to $b_i,ドル inclusive.

The combination lock is unlocked when each rotating disc displays one integer, and any pair of two integers displayed by the rotating disc are coprime. Two integers are coprime if they do not have any common positive factors other than 1ドル$.

You want to unlock the combination lock, so you want to determine what integer to be displayed on each combination lock to satisfy the requirement above. It is possible that your combination lock was sabotaged when you were gone so it might be impossible to unlock your combination lock.

입력

The first line of input contains one integer $n$ (2ドル ≤ n ≤ 50$). Each of the next $n$ lines contains two integers. The $i$-th line contains $a_i$ and $b_i$ (1ドル ≤ a_i ≤ b_i ≤ 50$).

출력

Output one line containing $n$ integers, where the $i$-th integer represents the integer to be displayed by rotating disc $i$ to unlock the combination lock. If there are multiple solutions, you can output any of them. If there is no solution, output just the integer -1.

제한

힌트