/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
整数 N,L が与えられます． 以下の条件をすべて満たす 3N 個の文字列の組 (S_1,S_2,\cdots,S_{3N}) を一つ求めてください．
-
S_i は
0,1,2からなる長さ L の文字列である． -
S_i はすべて互いに異なる．
-
すべての j (1 \leq j \leq L) および c=
0,1,2について，次が成り立つ．- S_i のうち，j 文字目が c であるようなものはちょうど N 個存在する．
-
S_1,S_2,\cdots,S_{3N} の中で，辞書順で最も大きい文字列を t で表すことにする． このときの t は，t としてありうる文字列の中で辞書順最小の文字列である．
制約
- 1 \leq N \leq 5 \times 10^4
- 1 \leq L \leq 15
- 3N \leq 3^L
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N L
出力
以下の形式で答えを出力せよ．
S_1
S_2
\vdots
S_{3N}
なお，条件を満たす解が複数存在する場合，どれを出力しても正解とみなされる．
入力例 1
2 2
出力例 1
00 02 11 12 20 21
この出力例はすべての条件を満たしています．
例えば，2 文字目が 0 であるような文字列は 2 個存在しています．
また，この例では t=21 ですが，t がこれより辞書順で小さくなることはありません．
Score : 500 points
Problem Statement
Given are integers N and L. Find a tuple of 3N strings (S_1,S_2,\cdots,S_{3N}) that satisfies all of the following conditions.
-
S_i is a string of length L consisting of
0,1,2. -
All S_i are pairwise distinct.
-
For every j (1 \leq j \leq L) and every c=
0,1,2, the following holds.- For exactly N of the strings S_i, the j-th character is c.
-
Let t be the lexicographically largest string among S_1,S_2,\cdots,S_{3N}. t for this tuple is the lexicographically smallest among all strings that t can be.
Constraints
- 1 \leq N \leq 5 \times 10^4
- 1 \leq L \leq 15
- 3N \leq 3^L
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L
Output
Print the answer in the following format:
S_1
S_2
\vdots
S_{3N}
If there are multiple solutions satisfying the conditions, any of them will be accepted.
Sample Input 1
2 2
Sample Output 1
00 02 11 12 20 21
This Sample Output satisfies all conditions.
For example, there are two strings whose second character is 0.
Also, we have t=21 in this sample, and t is never lexicographically smaller than this.