Hamming Distance Coding Problem

Given three integers \(n\), \(b\), and \(d\), find \(n\) distinct binary codes of length \(b\) (each code is represented by exactly \(b\) bits consisting of 0 and 1) such that the Hamming distance between any two codes is at least \(d\). The Hamming distance between two codes is defined as the number of positions in which the corresponding bits differ. For example, consider the two hexadecimal numbers 0x554 and 0x234:

0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
          xxx  xx

They differ in 5 bit positions, thus their Hamming distance is \(5\).

The Hamming distance between two binary codes \(x\) and \(y\) with \(b\) bits can be written in LaTeX as:

$$ H(x,y)=\sum_{i=1}^{b} \mathbf{1}(x_i\neq y_i), $$

where \(\mathbf{1}(\cdot)\) is the indicator function.

inputFormat

The input consists of a single line containing three integers \(n\), \(b\), and \(d\) separated by spaces:

• \(n\): The number of binary codes to generate.
• \(b\): The number of bits in each binary code.
• \(d\): The minimum required Hamming distance between any two codes.

outputFormat

Output \(n\) lines, each line containing a binary code of length \(b\) (with possible leading zeros) such that the Hamming distance between any two codes is at least \(d\). If there are multiple solutions, output any one of them.

sample

4 3 2

000
011
101
110

</p>