V Rímskej ríši sa plebejci zhromažďovali vo svojich klubovniach, kde síce zabíjali čas, no nie mozgové bunky. Práve naopak — rozvíjali svoje matematické schopnosti rôznymi hrami. Každý týždeň si vymysleli novú hru, ktorú potom spolu hrávali.

Najnovšiu hru nazvali „Calculi“.

Každý deň odohrali niekoľko partií tejto hry. Hra sa hrá na hracej ploche v tvare šachovnice, na ktorej sa nachádzajú číslice od 0 po 9 a znamienka + a −. Každé políčko obsahuje práve jeden symbol.

Pripraviť hraciu plochu trvá celkom dlho, takže si na nej zahrajú viacero kôl. V každom kole sa určí jedno kladné celé cieľové číslo.

Úlohou plebejcov je nájsť trasu po hracej ploche tak, aby vytvorili výraz, ktorého výsledkom je dané cieľové číslo. Kolo vyhráva ten, kto nájde najmenší takýto výraz.

No a vašou úlohou bude vyhrať všetky kolá, teda nájsť výrazy ktoré sú neporaziteľné.

Úloha

Na vstupe dostanete mriežku s hracou plochou, kde je každé políčko +, - alebo číslica. Na tejto hracej ploche sa odohrá niekoľko kôl a pre každé kolo dostanete cieľové číslo.

Trasa je postupnosť políčok na hracej ploche taká, že každé dve po sebe idúce políčka v tejto postupnosti spolu susedia na hracej ploche. Na hracej ploche sa vieme z jedného políčka dostať na druhé pohybom hore, dole, doprava, alebo doľava. Navštívené políčka na trase sa môžu ľubovoľne opakovať.

Pre každé kolo nájdite trasu, pre ktorú platí:

• začína a končí na políčku s číslicou,
• strieda číslice a znamienka (t.j. číslica → znamienko → číslica → …),
• vytvorí platný matematický výraz, ktorého výsledok je rovný cieľovému číslu daného kola.
• trasa je najkratšia spomedzi všetkých trás spĺňajúcich prvé $3$ body
• výraz zodpovedajúci trase je lexikograficky najmenší spomedzi všetkých trás spĺňajúcich prvé $4$ body

Napríklad, nech by v nejakom kole bolo cieľové číslo $6$ a existujú na danej hracej ploche trasy, ktorým prislúchajú nasledujúce výrazy (splňujúce prvé $3$ body): 2-3+7, 2+5-1, 1+1+1+3. Potom hľadaný výraz je 2+5-1, lebo má minimálnu dĺžku a spomedzi výrazov s touto dĺžkou je lexikograficky najmenší (+ je menšie ako -).

Môžete predpokladať, že cieľové čísla sú v kolách zvolené tak, aby na danej hracej ploche existovala jemu zodpovedajúca hľadaná trasa, a teda aj výraz, ktorý máte vypísať.

Formát vstupu a výstupu

V prvom riadku je celé číslo $1 \leq T \leq 5$, ktoré udáva počet partií, ktoré dostanete na vstupe. Nasleduje postupne popis každej z $T$ partií v následujucom formáte:

V jej prvom riadku sú čísla $W$, $Q$. Rozmer hracej plochy aktuálnej partie a počet kôl, pre ktoré máte zistiť hľadaný výraz.

Ďalej je na vstupe $W$ riadkov reťazcov dĺžky $W$, pozostávajúce zo znakov +-0123456789, ktoré znázorňujú hraciu plochu.

Po hracej ploche nasleduje jeden riadok s $Q$ cielovými číslami, pre ktoré je potrebné nájsť výraz podľa podmienok popísaných vyššie.

Nech $S$ je najväčšie cieľové číslo, ktoré sme dostali na vstupe. V jednotlivých sadách platia nasledovné obmedzenia:

V prvej sade navyše platí, že hracia plocha neobsahuje -.

Postupne pre každú partiu a každé kolo, v poradí v akom sa vyskytli na vstupe, vypíšte na nový riadok vyhrávajúci výraz.

Príklady

2
5 3
2+1-2
+3-4+
5+2+1
-4-0-
9+5+1
20 30 40
3 2
2+1
+4+
5+1
2 20

1+5+5+9
3+4+5+9+9
4+9+9+9+9
2
5+5+5+5

Prvá partia by sa nemohla vyskytnúť v prvej sade, keďže hracia plocha obsahuje mínus. Úlohou bolo nájsť trasy k číslam $20, 30$ a $40$. Mohli by sme $20$ vyjadriť ako 5+5+5+5 ale 1+5+5+9 je lexikograficky menšie.

Druhá partia by sa už mohla vyskytnúť aj v prvej sade. Máme len dve čísla: $2$ a $20$. Číslo $2$ by sme mohli vyjadriť ako 1+1, ale na hracej ploche sa nachádza 2 a to je kratší výraz.