Равенство

Для того, чтобы сосчитать, сколько мармелада понадобиться сварить в каждый из дней, Паддингтону необходимо быть неплохо подкованным в арифметике, ведь заключенных в наше время очень много!

Сегодня Кастет дал Паддингтону несколько математических заданий. Каждое задание выглядит так: дана последовательность $a\_1 a\_2 \dots a\_n$, состоящая из $n$ цифр (иными словами, $0 \le a\_i \le 9$ для всех $i$). Вместе с последовательностью Паддингтону дается два числа $k$ и $m$.

Задача Паддингтона состоит в том, чтобы поставить между некоторыми парами соседних цифр знаки сложения, умножения или равенства, чтобы получилось верное выражение по модулю $m$. При этом требуется, чтобы знаков равенства было ровно $k$. Между некоторыми парами соседних цифр можно не ставить никаких знаков, в таком случае эти цифры <<склеятся>> в одно число.

Формально, Кастет будет проверять правильность выполнения задания так: сначала он объединит блоки цифр, идущих подряд, между которыми не стоит знаков равенства. При объединении цифр $b\_1, b\_2, \dots, b\_l$ получается число $b\_1 \cdot 10^{l - 1} + b\_2 \cdot 10^{l - 2} + \dots + b\_{l - 1} \cdot 10 + b\_l$. После этого Кастет разобьет выражение на блоки, разделенные знаками равенства. Этих блоков должно быть ровно $k + 1$, иначе задание не будет зачтено. Затем, в каждом блоке будет подсчитано значение выражения. После этого Кастет проверит, что все получившиеся значения дают одинаковый остаток от деления на $m$, и в этом случае задание будет выполнено. Кастет проверяет задания лояльно, поэтому он разрешает Паддингтону использовать числа с ведущими нулями.

Задания бывают двух уровней сложности: в заданиях первого уровня Паддингтон может использовать только знаки сложения и равенства, а в заданиях второго --- знаки сложения, равенства, а также умножения.

К сожалению, Паддингтон отвлекся на написание письма тете Люси, и не успел выполнить задания. Помогите ему справится с ними!

Первая строка входных данных содержит единственное целое число $q$ --- количество заданий, которое необходимо выполнить ($1 \le q \le 1000$).

Далее следуют описания $q$ заданий. Описание каждого задания состоит из двух строк.

Первая строка описания задания содержит четыре целых числа $n$, $k$, $m$, $t$ --- длина последовательности цифр в задании, количество знаков равенства, которые нужно использовать в ответе, число, остатки от которого будут сравниваться и уровень сложности задания, соответственно ($1 \le k < n \le 200$, $1 \le m \le 1000$, $1 \le t \le 2$). Если $t = 1$, то можно использовать только знаки сложения и равенства, а если $t = 2$, то можно использовать дополнительно знаки умножения.

Вторая строка описания задания содержит последовательность из $n$ цифр $a\_i$, записанных подряд ($0 \le a\_i \le 9$).

Обратите внимание на ограничения, данные для подзадач.

Для каждого задания, описанного во входном файле, в отдельной строке выведите ответ на него.

В случае, если у задания нет решения, выведите единственное слово <<Fail>> (без кавычек).

В случае, если решение есть, выведите исходную последовательность, поставив в нужных местах нужные знаки сложения, умножения и равенства. Никаких разделительных символов в выражении выводить не нужно. В случае, если решений несколько, выведите любое из них.

Для лучшего понимания формата входных и выходных данных изучите тест из примера.