Decoding the Caesar Cipher

You are given an encoded message which was encrypted using a Caesar cipher. Your task is to decode the message by trying all possible shifts (from 1 to 25) until one of the given possible words appears as a substring in the decoded message.

The Caesar cipher shifts each letter of the message by a fixed number of positions. In our formulation, for a given shift value \(k\), each letter \(c\) in the message is replaced by \(\text{chr}(((\text{ord}(c) - \text{ord}('a') - k) \mod 26) + \text{ord}('a'))\). If one of the provided words is a substring of the decoded message, print that word immediately. If no word matches after testing all shifts, print "No match found".

Note: The input message contains only lowercase letters.

inputFormat

The first line contains a string representing the encoded message.

The second line contains an integer \(n\) denoting the number of possible words.

The next line contains \(n\) space-separated words.

outputFormat

Print the first matching word found after decoding the message using the Caesar cipher with shifts from 1 to 25. If no matching word is found, print "No match found".

dpef
2
code hello

code