28900번 - Равенство 서브태스크스페셜 저지다국어

문제

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

Сегодня Кастет дал Паддингтону несколько математических заданий. Каждое задание выглядит так: дана последовательность $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>> (без кавычек).

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

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

제한

서브태스크

노트