eolymp
bolt
Try our new interface for solving problems
Problems

Вампирские числа

Вампирские числа

Илья увлекается математикой. Недавно он прочитал про \textit{вампирские числа}. Они настолько восхитили Илью, что теперь он постоянно придумывает задачи, связанные с этими числами, и пытается их решить. Число \textbf{a}, десятичная запись которого состоит из \textbf{n} цифр (\textbf{n} четно), называется вампирским, если его можно представить в виде произведения двух \textbf{n/2}-значных чисел \textbf{b} и \textbf{c}, причём используя все цифры \textbf{b} и \textbf{c} можно записать число \textbf{a}. Каждую цифру при этом разрешается использовать столько раз, сколько раз она суммарно встречается в \textbf{b} и в \textbf{c}. Числа \textbf{b} и \textbf{c} называются \textit{клыками} числа \textbf{a}. Например, число \textbf{6880} --- вампирское, так как \textbf{6880=80}×\textbf{86}, а число \textbf{1023} --- нет. Для его новой задачи Илья попросил вас найти \textbf{k} различных вампирских чисел, состоящих из \textbf{n} цифр. \InputFile В единственной строке входного файла заданы два числа \textbf{k} и \textbf{n} --- требуемое количество вампирских чисел и количество цифр в каждом из них соответственно (\textbf{1} ≤ \textbf{k} ≤ \textbf{100}, \textbf{4} ≤ \textbf{n} ≤ \textbf{100}, \textbf{n} --- четно). \OutputFile В выходной файл выведите \textbf{k} различных \textbf{n}-значных вампирских числа в формате \textbf{A_i=B_ixC_i}, где \textbf{Ai} --- \textbf{i}-е из найденных вампирских чисел, \textbf{B_i} и \textbf{C_i} --- его клыки (между \textbf{B_i} и \textbf{C_i} следует вывести маленькую латинскую букву "\textbf{x}"). Если ответов несколько, то разрешается вывести любой из них. Гарантируется, что для приведенных во входном файле \textbf{n} и \textbf{k} существует \textbf{k} различных \textbf{n}-значных вампирских чисел.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
1 6
Output example #1
139500=150x930
Source XIII All-Russian Olympiad schoolchildren team programming