Corwin was able to intercept n messages about Eric's troop movements. True, they turned out to be encrypted, but it does not matter! Will you help him decipher these messages? This shouldn't be difficult, as Corwin knows at least one substring in every original message.
For encryption, Eric is known to use a Caesar cipher, that is, a cipher in which the letter with the number i is replaced by the letter with the number i + k , where k is some number.
Since modern compilers do not support the Amber alphabet, we will replace characters with their serial number - a number from 1 to q, where q - the number of characters in the alphabet.
Each message is x long, and each known substring of its decryption is y.
Your goal is to restore all original messages.
Input
First line reads numbers n (\(1 <= n <= 100\)) and q (\(1 <= k <= 100\))
The following
3 * n lines contain numbers
xi,
yi (
\(1 <= b_i <= a_i <= 100\)) and 2 arrays of numbers representing the message and its decryption substring.
Imprint
In the line number
i print the decoded version of the message with the number
i.
There must be
MUST NOT at the end of this line
Examples
| # |
Input |
Output |
| 1 |
1 11
10 4
11 7 1 1 2 6 7 1 1 8
2 7 7 8
| 6 2 7 7 8 1 2 7 7 3 |