Egypt is one of the regions where culture developed earliest in the world. Ancient Egyptian mathematics achieved significant accomplishments. As can be seen from surviving ancient Egyptian mathematical papyri such as the "Moscow Mathematical Papyrus" and the "Rhind Mathematical Papyrus," the mathematical knowledge of the ancient Egyptians included arithmetic, algebra, and geometry. Egypt used a decimal numbering system very early on; they were able to solve certain additive equations and possessed preliminary knowledge of arithmetic and geometric progressions.

Let $A$ and $B$ be two strings consisting of lowercase English letters. A set of strings $S$ is a set consisting of $n$ strings, where each string consists of lowercase English letters. Select a string $C$ from the set $S$, which forms the following additive expression with strings $A$ and $B$:

$$A+B=C$$

where strings $A$, $B$, and $C$ are all right-aligned by position.

For example: when $A=\texttt{ab}$, $B=\texttt{ac}$, and $C=\texttt{da}$, the corresponding additive expression is:

$$\texttt{ab} + \texttt{ac} = \texttt{da}$$

This expression establishes an additive equation. If we replace the lowercase letters in the expression with digits $0 \sim 9$ such that the expression becomes a correct decimal vertical addition calculation, such a replacement is called a solution to the additive equation.

For example: $a=1, b=4, c=7, d=3$ is a solution to the above additive equation.

Obviously, an additive equation can have multiple different solutions. For the sake of clarity, the canonical solution of an additive equation is defined as follows:

1. All lowercase English letters appearing in the expression correspond one-to-one with a digit from $0 \sim 9$, meaning the same letter corresponds to the same digit, and different letters must correspond to different digits.
2. All lowercase English letters in the solution appear exactly once without repetition.
3. The lowercase English letters in the solution appear at least once in the expression.
4. The digit corresponding to the first letter of a string in the expression cannot be $0$, even if the string length is $1$.

A solution that satisfies these requirements is called a canonical solution of the corresponding additive equation. When at least one character corresponds to a different digit in two canonical solutions of the same additive equation, these two canonical solutions are said to be different.

Additive Equation Problem: For given strings $A$, $B$, and $C$, assuming their corresponding additive equation has $x$ canonical solutions, determine whether $x \pmod m$ is equal to $k$.

Input

The first line of input contains a string $A$.

The next line contains a string $B$.

The next line contains three integers $n, m, k$.

The next $n$ lines each contain a string $S_i$, describing a string in $S$.

Output

Output $n$ lines, each containing the string YES or NO, indicating whether the additive equation corresponding to $C=S_i$ satisfies the requirement.

Examples

Input 1

abc
efbe
7 3 2
dcbc
fbed
bcdd
bdga
abdb
fedc
ghijk

Output 1

NO
NO
YES
YES
NO
NO
NO

Subtasks

Let $s$ denote the maximum length of each string: