The famous Gray code is an arrangement of $2^n$ distinct $n$-bit binary numbers (i.e., $0$ to $2^n-1$, with leading zeros padded to $n$ bits) such that any two adjacent binary numbers in the arrangement differ by at most one digit (for example, $003$ and $001$ differ by one digit, while $003$ and $030$ differ by two digits, which does not satisfy the condition). For example, when $n=2$, $(00, 01, 11, 10)$ is a Gray code that satisfies the condition.

A "Super Gray code" is an arrangement of $B^n$ distinct $n$-digit base-$B$ numbers that satisfies the condition above.

Task: Given $n$ and $B$ ($2 \le B \le 36$, $1 \le B^n \le 65535$), find a Gray code that satisfies the condition. For digits greater than $9$, use $A \sim Z$ to represent them ($10 \sim 35$).

Input

The input consists of a single line containing two integers $n$ and $B$.

Output

Output $B^n$ lines, each containing one base-$B$ number, representing the arrangement that satisfies the conditions.

Examples

Input 1

2 2

Output 1

00
01
11
10