Boggle Solver

Statement

Goal

You are given the task to solve a Boggle game.
The rules are quite simple : Given a rectangular grid of letters of size NxM and a dictionary of W words, find all the words of the dictionary that are contained in the grid.
A word is contained in the grid if it can be built by connecting adjacent (vertical, horizontal or diagonal) letters of the grid without using any letter twice for the same word.

You should return the sorted list (the words should appear in the same order you would find them in a dictionary) of the words found in the grid.

NB : If you are not familiar with this game, you can find more informations on the Boggle game here : https://en.wikipedia.org/wiki/Boggle

Input

Line 1 : A positive integer N for the number of rows of the grid.
Line 2 : A positive integer M for the number of columns of the grid.
Line 3 : A positive integer W for the number of words in the dictionary.
N next lines : A string of size M for the letters in each row of the grid.
W next lines : A string for each word of the dictionary.

Output

Lines : The sorted list of each words found in the grid.

Constraints

0 < N <= 16
0 < M <= 16
0 < W <= 100

Example

Input

3
3
4
ace
pls
wut
paris
place
pulse
scalp

Output

place
pulse
scalp

Tags

Tries, Arrays

Difficulty

Medium

Test cases

Warming up Test

Input

3 3 4 ace pls wut paris place pulse scalp

Output

place pulse scalp

Validator 1 Validator

Input

3 3 3 dip lur tfm mud pilum nope

Output

mud pilum

Easy grid Test

Input

4 4 7 adel bfci sump eltc bad muse museum abuse trump fuel fuels

Output

abuse bad fuel fuels muse

Validator 2 Validator

Input

4 4 7 tett reci tbfi itne bee bet beer beef fine refine recipt

Output

bee beer bet fine refine

It is getting complicated... Test

Input

11 3 7 com rpl cit oae fod zrb gia oag fsz tei twd commerce commercial complicated test tested twisted comma

Output

complicated test twisted

Validator 3 Validator

Input

6 9 8 fbropikbo rllpeueab motselflp uzuthuopb kaegndrga tnlsatetx annoying beer frozen portable soul tangeant teleport test

Output

frozen portable tangeant test

That is a big grid ! Test

Input

8 8 8 evlbasdj zenglmax jcditfex hfonsawh nqurvryr jesffgbq iulhnxzt wdcmeaxx codingame consigned consignee counting counter feasable fun sunset unsigned

Output

codingame consigned consignee counting feasable fun

Validator 4 Validator

Input

10 10 12 aledipolqu swebecnlui jalmopqehs tiudbelimi eyhslazpie zihuhduine mopzikeuih bxkazeipuz jkhzoriahj zabnmrepog codingame decibel decibels demodulate hardcoded ideal ideally modulated people pushable usually usuality

Output

decibel decibels demodulate ideal people pushable usuality

Lots of words Test

Input

9 4 56 aced omin sult gesi crrv duae chpl siot imuw applications believer multiverses argumentive epicurises multiverse design pattern polaristic reargument mischarges mouseline outparcel outpursue perseline polariser polarises tyranic arguesome arguments arrestive crestline curarises elaphures epicurise graphiums guilesome largesome mischarge recursive relumined resilient resultive seraphims sharesmen object puppy purvises raresome reargues regravel reguline relivers relumine reparses repurges repursue resilium resliced reslimed revilers revilest rilesome schapers scholars seraphic

Output

arguesome argumentive arguments arrestive crestline curarises elaphures epicurise epicurises graphiums guilesome largesome mischarge mischarges mouseline multiverse multiverses outparcel outpursue perseline polariser polarises polaristic purvises raresome reargues reargument recursive regravel reguline relivers relumine relumined reparses repurges repursue resilient resilium resliced reslimed resultive revilers revilest rilesome schapers scholars seraphic seraphims sharesmen

Validator 5 Validator

Input

8 7 80 topelba vedpdti uesocci atlleub slotrsv ainpilr lamdulm intyoqd directed interlocus interloped misallots mistelles interpolated interpolates nanopills nanopulse pedestals pedestrian podocerid pointelle pointless pointlets precostal recitable celloists codevelop colonel colonists babibel colonist copepods coseeded develops developed satellect precolonial collectable collectible directable satellite talinolol alamillos antecosta antipoles aetolian alamillo alstonia anisates antelope antisuit attested burelles celloist celloists clopidol codesets collated collatee colletid colonial developped directed entities maillets maillots pointers pointlet poloists polonial manilles maniotes mistells mustard nailists nanopill nanorobot notalian pedestal pointels polonian postells precoded precodes reclosed estonian interpol slitlets

Output

aetolian alamillo alamillos alstonia anisates antecosta antelope antipoles antisuit burelles celloist celloists clopidol codesets codevelop collated collatee collectable collectible colletid colonial colonist colonists copepods coseeded developed developped develops directable estonian interlocus interloped interpol interpolated interpolates maillets maillots manilles maniotes misallots mistelles mistells nailists nanopill nanopills nanopulse notalian pedestal pedestals podocerid pointelle pointels pointers pointlet pointlets poloists polonial polonian postells precoded precodes precolonial precostal recitable reclosed satellect slitlets talinolol

Solution language

Solution

Stub generator input

Comments

3 Comments

CodinBot Unnamed CodinGamer

over 3 years ago

I hope you received enough feedback from the community to improve your contribution. Once you have made the necessary updates, publish your contribution!

CopperFr Unnamed CodinGamer

duplicate

dwarfie Unnamed CodinGamer

duplicate https://www.codingame.com/...