Codeslinger 2011 Problem

The 2011 programming tournament is over but take your own shot at this year's problem. The sponsor's of the tournament, Main Street Softworks, would like to hire some programmers who are proficient in C. If you can solve this problem in C without hunting for someone else's answer, Main Street Softworks would be interested in talking to you about working for them. So, take a shot at it and send them your solution. Click the story link to see the problem.

Here is the problem as given to the contestants. There is also a large and small dataset to process and md5 checksums to verify your result.

Problem
-------
Given a list of words, we want to know all permutations of each word that
result in matching words of a dictionary.

Assuming the English dictionary, some valid permutations are as follows:


    Word                              Valid Permutations
    -------------------------------   ----------------------------
    apt                               pat, tap
    ate                               eat, tea
    care                              race
    monday                            dynamo
    plates                            staple


Input
-----
Number of dictionary words will be from 0 to 200000.
Each word will be on its own line.
All characters will be lower case alpha.

Standard Input Format:

    [NUM_DICTIONARY_LINES]
    [DICTIONARY_WORD_LINES]
    [LOOKUP_WORD_1]
    [LOOKUP_WORD_2]
          .
          .
          .
    [LOOKUP_WORD_N]
    [EOF]


Output
------
Standard output; write out the lookup word followed by each of its valid
permutations in lexicographical order;

Example
-------
Input:

    6
    apt
    ate
    tap
    pat
    care
    race
    apt
    tap
    care

Output:

    apt pat tap
    tap apt pat
    care race

Prize
-----
    1. $300 - First Correct Solution (must run under 3 min on large data set)
    2. $150 - Fastest Correct Solution (must be completed within 2 hours of contest start)
    2. $50  - First Correct Solution in C