Илья в последнее время начал увлекаться археологией. Недавно он нашел два числа, записанных в системе счисления по основанию m. Каждое из найденных чисел состояло ровно из n цифр. Илья сразу начал искать информацию об этих числах, он узнал, что числа — это часть шифра, а тот, кто разгадает шифр, обретет невиданное сокровище.
После длительных исследований Илья понял: чтобы разгадать шифр, нужно сделать следующее:
- Переставить цифры в первом числе некоторым образом, аналогично, переставить цифры во втором числе некоторым образом. В результате этой операции у чисел могут появиться лидирующие нули.
- Поцифренно сложить числа по модулю m. Другими словами, нужно получить третье число, длины n, каждая цифра которого, есть сумма соответствующих цифр найденных чисел. Например, пусть есть два числа, записанных в троичной системе счисления, 001210 и 012111, тогда, если их сложить поцифренно по модулю 3, получится число 010021.
- Ключ к шифру — это максимально возможное число, которое можно получить на предыдущем шаге.
Помогите Илье, найдите ключ к шифру.
Выходные данные
Выведите n цифр в системе счисления по основанию m — полученное третье число. Цифры выводите в порядке от старших разрядов к младшим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 7
5 4 3 2
5 6 5 4
|
6 4 2 1
|
|
2
|
5 5
2 4 4 1 3
1 0 1 2 4
|
4 4 4 3 2
|