Word Blitz!

BUET CSE Fest 2019 Inter...
Limits 2s, 512 MB

I am sure you have heard of the famous messenger game Word Blitz! You can play the game with an opponent. The game consists of a $4\times4$ board. Each cell of the board consists of a letter like the picture below.

You have to connect some distinct adjacent cells in the board to form a string. If the string you have made exists in the english dictionary, it will be considered valid.

To form a string, you start with one of the 16 cells. You can go to any adjacent untouched cell from the current cell. A cell will be considered adjacent to another if it shares a border or a corner (similar to King's move in chessboard). The string you have formed can have any length between 1 and 16 (inclusive).

For this problem, we will be considering the game where the maximum allowed length of the string will be 8. You will be given a dictionary having $N$ words and a board configuration. Can you tell the number of valid distinct words W in the board?

(You are blessed because the problem author had a much more complex problem in mind based on this game. But a kind person asked the problem author to show mercy.)

Input

The first line contains an integer $N$ ($1 ≤ N ≤ 500000$) denoting the number of words in the dictionary.

Each of the next $N$ lines contain a word consisting of English uppercase letters. The words will have maximum length of 8.

The next line is blank.

Each of the next 4 lines contain a string of length 4 consists of English uppercase letters. These 4 lines describe the board configuration.

The same word won't be mentioned twice in the dictionary. The words will be in lexicographical order. Lexicographical order means the way the words would have appeared in an actual dictionary.

Output

Print a single integer $W$ in a line denoting the number of distinct valid words which can be formed from the given board configuration. The next $W$ lines should contain the valid words found in the board. These words should be printed in lexicographic order (the order of input).

Sample

InputOutput
5
POLAR
RISE
SAP
SIT
SPACEX

LAPS
ROSE
TIME
SOFT

4
POLAR
RISE
SAP
SIT

Here's how the word POLAR is formed. The starting cell is the cell that contains the letter P.

There are two ways to form the word SIT. Notice that it is mentioned only once in the output.

Submit

Login to submit.

Statistics

50% Solution Ratio
noshin_faizaEarliest, Jan '20
noshin_faizaFastest, 0.2s
noshin_faizaLightest, 18 MB
noshin_faizaShortest, 1585B
Toph uses cookies. By continuing you agree to our Cookie Policy.