Sliding Window Sequence Comparison

You are given a long sequence A of length \(N\) consisting of digits (0-9) and \(M\) short sequences, each of length \(L\), also consisting of digits (0-9). For each short sequence \(B\), your task is to simulate the following process to check whether \(B\) occurs in \(A\):

1. Start with a sliding window on \(A\) of length \(L\) beginning at position 1. If the segment has less than \(L\) characters, pad the right end with the character # so that the segment always has exactly \(L\) characters.
2. Compare the windowed segment and \(B\) digit by digit from left to right. Increase a comparison counter by 1 for each digit compared.
3. If a mismatch is encountered at any digit, shift the window one position to the right (i.e. if the current window covers positions \(x\) to \(y\), the next window covers positions \(x+1\) to \(y+1\); again, pad with # if needed) and restart the digit‐by-digit comparison.
4. If the segment matches \(B\) completely, stop the process immediately.
5. If you have tried all possible starting positions from 1 to \(N+1\) (note that when the starting index exceeds \(N\) the segment is composed entirely of padded # characters) and none of them match \(B\), then stop.

For each short sequence, output the total number of digit comparisons made before the process stops for that sequence.

Note: All formulas in this statement are formatted in \(\LaTeX\). Make sure to follow the simulation process exactly.

inputFormat

The first line contains three integers \(M\), \(N\), and \(L\) separated by spaces, where \(M\) is the number of short sequences, \(N\) is the length of the long sequence \(A\), and \(L\) is the length of each short sequence \(B\).

The following \(M\) lines each contain a short sequence \(B\) (a string of \(L\) digits).

The last line contains the long sequence \(A\) (a string of \(N\) digits).

outputFormat

Output \(M\) lines, each line containing a single integer. The integer is the total number of digit comparisons made during the simulation for the corresponding short sequence.

sample

1 5 3
234
12345

4