Даша-путешественница решила использовать все заработанные за несколько лет отчисления на шоппинг. А где же еще лучше магазины, чем в Нлогонии?
Всего в Нлогонии \(n\) магазинов, пронумерованных от \(1\) до \(n\). В \(i\)-м из этих магазинов можно купить положительное целое число \(a_i\).
В каждый из последних \(m\) дней Даша покупала по одному числу в некоторых магазинах. В каждый из этих дней лисенок Жулик покупал по одному числу во всех магазинах, в которых Даша не купила число в этот день.
Дора считает, что Жулик соперничает с ней; она считает, что выиграла у Жулика в день \(i\), если и только если наименьшее общее кратное чисел, которые она купила в \(i\)-й день строго больше наименьшего общего кратного чисел, которые купил в \(i\)-й день Жулик.
Наименьшем общем кратном (НОК) набора целых чисел называется наименьшее положительное целое число, делящееся на все числа из набора.
К сожалению, Даша забыла, чему равны значения \(a_i\). Помогите Даше определить, существуют ли такие положительные целые числа \(a_i\), что она выигрывала у Жулика каждый день. Сами значения \(a_i\) находить не нужно.
Обратите внимание, возможно, что некоторые значения \(a_i\) в решении совпадают.
Выходные данные
Выведите единственную строку, содержащую "possible", если существуют положительные целые числа \(a_i\) такие, что в каждый день наименьшее общее кратное чисел, купленных Дашей, было строго больше наименьшего общего кратного всех чисел, купленных Жуликом в тот же день. В противном случае выведите "impossible".
Обратите внимание, вам не нужно находить сами подходящие числа.
Примечание
В первом примере возможные числа \(a_i\) равны \(3, 4, 3, 5, 2\). В первый день Даша покупает числа \(3, 4\) и \(3\), НОК которых равен \(12\), а Жулик покупает числа \(5\) и \(2\), НОК которых равен \(10\). Во второй день Дора покупает числа \(3, 5\) и \(2\), НОК которых равен \(30\), а Жулик покупает числа \(3\) и \(4\), НОК которых равен \(12\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 5
3 1 2 3
3 3 4 5
|
possible
|
|
2
|
10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
|
impossible
|