The easy subproblem is so small that we can solve it completely by brute force: for each input, iterate over all possible insults until you find one with a suitable strength.
This approach would, obviously, be too slow for the hard subproblem.
The first possible improvement would be to generate the possible results only once. Once we do that, we can sort them into buckets according to their strength, and we will be able to answer queries in constant time. Sadly, this still doesn’t work: there are 10 0003 possible insults, so we don’t have enough time and space to generate and store all of them.
There are many ways how to solve the hard subproblem. Here are a few.
We may notice that the precomputing solution described above spends too much time on precomputation and too little time on answering queries. We can therefore use some kind of a meet-in-the-middle technique to obtain a better tradeoff.
During precomputation we will generate all pairs of words from the first two wordlists and we will store them into buckets according to their total strength.
Then, whenever we want an insult with a specific strength s, we can iterate over all words from the third wordlist, and for each word (with strength s3) we look into the corresponding bucket (strength s − s3) for the rest of the insult. If we get a insult we have already generated before, we skip it and find another.
Considering a reasonably low number of skips with same value, the time complexity is O(m2 + nm).
You may notice that there are 10 0003 possible insults in hard input but only 3 000 000 possible strengths. It is also easy to verify that word strengths are distributed reasonably. Therefore, there is a lot of possible insults of each type.
In order to speed up the naive precomputing solution we mentioned in the beginning, we can simply use random sampling. If we only keep a small-ish random sample of each wordlist, the solution becomes fast enough and it will still be able to find enough answers to the input insults. You just needed to make sure that you selected enough words close to minimum and maximum strength, because the number of valid combinations there is small.
The task can also be solved using a knapsack-like dynamic programming algorithm: for each strength we store some of the ways how we got there.