K. Similarity (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The easy version and the hard version are different problems. However, it is advisable to get the easy version accepted first.

Many place names bear similarities. Take, for instance, $$$\texttt{Suzhou}$$$ and $$$\texttt{Quzhou}$$$. They are considered similar because they share a common substring $$$\texttt{uzhou}$$$. A substring is a contiguous sequence of characters within a string. For example, in the string $$$\texttt{abcd}$$$, $$$\texttt{bc}$$$ is a substring of it, but $$$\texttt{ac}$$$ is not.

We define the similarity between two strings as the length of their longest common substring. Thus, the similarity between $$$\texttt{Suzhou}$$$ and $$$\texttt{Quzhou}$$$ is $$$5$$$, and between $$$\texttt{Hangzhou}$$$ and $$$\texttt{Chengdu}$$$ it is $$$2$$$.

Your task is to construct $$$n$$$ distinct strings of the same length $$$k$$$, composed solely of lowercase English letters. Out of the $$$\frac{n(n-1)}{2}$$$ total pairings between these strings, the maximum similarity should be exactly $$$m$$$.

Input

One line contains three integers $$$n, m, k$$$ ($$$2\le n \le 300$$$, $$$0\le m \le 50$$$, $$$1\le k \le 100$$$).

Output

If there is no solution, output $$$\texttt{No}$$$ in a single line.

Otherwise, output $$$\texttt{Yes}$$$ in the first line. Then each of the next $$$n$$$ lines contains a constructed string. Note that the strings should be pairwise distinct.

Example
Input
2 4 8
Output
Yes
jiangsuu
xiangtan