Удачи!
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маша и Петя играют в игру: Марьям выбирает n случайных целых чисел, каждое от 2 до m включительно, числа выбираются независимо, каждое число может принять любое значение от 2 до m с равной вероятностью (представьте, что она n раз бросает кубик с m - 1 гранями). Обратите внимание, что некоторые числа могут быть равны. Затем она повторяет следующие действия k раз: выбирается случайное подмножество чисел (каждое число берется с вероятностью 0.5), и выписывается произведение этих чисел. Сделав это, она показывает все k полученных произведений Пете, его цель — угадать n чисел, которые были у Маши, зная только n, m, и полученные произведения.

Пример игры с n = 3, m = 4, k = 4 сначала Маша выбирает 3 случайных числа от 2 до 4 включительно — давайте считать, что она случайно выбрала a1 = 3, a2 = 3 и a3 = 4. Затем она вычисляет четыре произведения случайных подмножеств этих трех чисел. Например, произведения a1a2 = 9, a3 = 4, a1a2a3 = 36 и 1 = 1 (1 — произведение пустого множества чисел). Петя получает числа 9,4,36 и 1 от нее, а так же значения n = 3 и m = 4. В этом случае, просто посмотрев на число 36 можно понять, какие числа были в наборе, так как единственный способ получить 36 в виде произведения 3 чисел, каждое из которых от 2 до 4 — 3·3·4. Так что Петя говорит, что первоначальные числа были 3, 3 и 4, и угадывает.

В некоторых других случаях угадать оригинальные номера не так просто. Например, может случиться так, что все произведения равны 1. В этом случае нет никакого способа узнать что-либо о числах, так что Петя не может всегда угадывать. Тем не менее, если известно, что Маша играет честно, то есть действительно использует настоящие случайно сгенерированные числа, то Петя может использовать эти знания, чтобы угадывать достаточно часто!

Вам будет предложено сыграть за Петю r раз, ваше решение будет считаться правильным, если хотя бы x ответов будут правильными.

В первой задаче r = 100, x = 50, n = 3, m = 5, k = 7.

Во второй задаче r = 8000, x = 1120, n = 12, m = 8, k = 12.

Входные данные

Первая строка входного файла содержит пять целых чисел r, x, n, m и k. Следующие r строк описывают независимые игры. Каждая строка содержит один набор из k произведений. Гарантируется, что все наборы в входе генерируются случайным образом, независимо, в соответствии с процедурой, описанной выше.

Выходные данные

Выведите в выходной файл r наборов по n чисел от 1 до m - ваше предположение о скрытых номерах Маши для соответствующего набора произведений. Вы можете вывести числа для каждого набора в любом порядке, но в нем обязательно должно быть точно n чисел, каждое от 2 до m включительно (обратите внимание, что m < 10, поэтому ни одно из чисел не будет больше одной цифры). Не ставьте пробелы между цифрами. Если для какого-то теста ваша программа не может сделать догадку, выведите любой набор из n чисел от 2 до m (например, n двоек).

Примеры тестов

Входные данные
2 1 3 4 4
9 4 36 1
1 1 1 1
Выходные данные
334
234