407800: GYM102896 B Brain-teaser

There is a type of a brain-teaser known as cryptoarithmetics. The classic example, published in the July 1924 issue of Strand Magazine by Henry Dudeney, is:

A solution to such a puzzle is an assignment of letters to decimal digits from 0 to 9 that satisfies the following constraints:

• Each letter must represent a different decimal digit.
• The leading digit of each number must not be zero.
• The result must be a correct equality — the sum of the first two decimal numbers is equal to the third one.

The only solution to the above puzzle is $$$\tt{O} = 0$$$, $$$\tt{M} = 1$$$, $$$\tt{Y} = 2$$$, $$$\tt{E} = 5$$$, $$$\tt{N} = 6$$$, $$$\tt{D} = 7$$$, $$$\tt{R} = 8$$$, and $$$\tt{S} = 9$$$, producing the following equality: $$$9567 + 1085 = 10652$$$.

A good brain-teaser, like the classic one, has a unique solution. You are given the first two words in a brain-teaser and your task is to find all the possible third words from the given dictionary that produce a good brain-teaser with a unique solution.

The first and the second lines of the input contain a word each — two addends of the brain-teaser. The third line of the input contains an integer $$$n$$$ — the number of words in the dictionary, followed by $$$n$$$ lines with the dictionary words. The words in the dictionary are lexicographically ordered.

All words in the input consist of 2 to 15 uppercase letters. All the tests, with the exception of the first test, use the same dictionary of $$$279\,496$$$ Collins Dictionary Scrabble Words (2019). The first two words come from this dictionary, too. Note that you can find the second test with the full dictionary inside the downloadable file with the problem examples. It is provided together with the problem statements.

On the first line output a single integer $$$m$$$ — the number of words from the dictionary that produce a good brain-teaser with the first two given words. On the next $$$m$$$ lines output the words in the same order as in the dictionary.

SEND
MORE
3
FUN
HONEY
MONEY

1
MONEY

DUB
UPSPEAK
279496
... not shown ...

2
UPMAKER
UPTAKEN