C1116 [SCOI2005]超级格雷码

内存限制:256 MB 时间限制:1000 ms

题目描述

著名的格雷码是指 $2^n$ 个不同 $n$ 位二进制数(即 $0 \sim 2^n-1$,不足 $n$ 位在前补零)的一个排列,这个排列满足相邻的两个二进制数的 $n$ 位数字中最多只有一个数字不同(例如 $003$ 和 $001$ 就有一个数位不同,而 $003$ 和 $030$ 有两个数位不同,不符合条件)。例如 $n = 2$ 时,$(00, 01, 11, 10)$ 就是一个满足条件的格雷码。

所谓超级格雷码就是指 $B^n$ 个不同的 $n$ 位 $B$ 进制数的排列满足上面的条件。

任务:给出 $n$ 和 $B$,求一个满足条件的格雷码。对于大于 $9$ 的数位用 $A \sim Z$ 表示($10 \sim 35$)。

输入格式

只有一行,为两个整数 $n$ 和 $B$。

输出

一共 $B^n$ 个行,每行一个 $B$ 进制数,表示你所求得的符合条件的排列。

样例

样例输入 1

2 2

样例输出 1

00 01 11 10

提示

$2 \leq B \leq 36, 1 \leq B^n \leq 65535$