Which Lamps Are Lit on the Register?

A register of n qubits has 2^n basis states, one for each string of n bits, and a state of the register is a list of 2^n amplitudes: amplitude i belongs to basis state number i. To know which bit string number i stands for, everyone has to agree on an order. In this path, basis state |b_0 b_1 \dots b_{n-1}\rangle has index int("b0b1...", 2): qubit 0 is the leftmost bit, the most significant one, and qubit n-1 is the rightmost. In 3 qubits, |011\rangle is index 3: qubit 0 reads 0, qubits 1 and 2 read 1. (Some toolkits number the qubits the other way round; here the leftmost is qubit 0.)

The control panel of a chip shows one lamp per qubit, lit when that qubit reads 1. Write basis_label(n, index) that returns a pair (bits, ones):

• bits is the bit string of basis state index, exactly n characters long (leading zeros kept);
• ones is the list of the qubits that read 1, in increasing order (an empty list if none do).

Examples

Input:  n = 3, index = 3
Output: ("011", [1, 2])

Input:  n = 3, index = 4
Output: ("100", [0])
Explanation: 4 is 100 in binary. The leftmost bit is qubit 0, so qubit 0 is the one that reads 1.

Input:  n = 1, index = 0
Output: ("0", [])

Goals

• Turn the index of a basis state into its bit string of length n
• Use the convention that qubit 0 is the leftmost, most significant bit
• List which qubits are 1 in a basis state