IOI'95 Task: Bar Codes
#
Task: Bar Codes

A bar-code symbol consists of alternating dark and light bars,
starting with a dark bar on the left.
Each bar is a number of units wide.
Figure 1 shows a bar-code symbol
consisting of 4 bars that extend over 1+2+3+1=7 units.

Figure 1: Bar-code symbol over 7 units (see top) with 4 bars (see bottom)
In general,
the bar code *BC*(*n*,*k*,*m*) is the set of all symbols
with *k* bars that together extend over exactly *n* units,
each bar being at most *m* units wide.
For instance,
the symbol in Figure 1 belongs to *BC*(7,4,3)
but not to *BC*(7,4,2).

0: 1000100 | 8: 1100100
1: 1000110 | 9: 1100110
2: 1001000 | 10: 1101000
3: 1001100 | 11: 1101100
4: 1001110 | 12: 1101110
5: 1011000 | 13: 1110010
6: 1011100 | 14: 1110100
7: 1100010 | 15: 1110110

Figure 2: All symbols of *BC*(7,4,3)
Figure 2 shows all 16 symbols in *BC*(7,4,3).
Each `1' represents a dark unit, each `0' a light unit.
The symbols appear in lexicographic (dictionary) order.
The number on the left of the colon (`:') is the rank of the symbol.
The symbol in Figure 1 has rank 4 in *BC*(7,4,3).

## Input Data

The first line of file `INPUT.TXT` contains
the numbers *n*, *k*, and *m* (1<=*n*,*k*,*m*<=33).
On the second line is a number *s* (0<=*s*<=100).
The following *s* lines each contain some symbol
in *BC*(*n*,*k*,*m*),
represented by ``0`'s and ``1`'s
as in Figure 2.
## Output Data

On the first line of file `OUTPUT.TXT` your program should write
the total number of symbols in *BC*(*n*,*k*,*m*) (Subtask A).
On each of the *s* following lines, it should write
the rank of the corresponding symbol in the input file (Subtask B).
## Example Input and Output

Figure 3 gives
possible input and output files for the example above.
____________ _____________
|INPUT.TXT | |OUTPUT.TXT |
|__________| |___________|
|7 4 3 | |16 |
|5 | |4 |
|1001110 | |15 |
|1110110 | |3 |
|1001100 | |4 |
|1001110 | |0 |
|1000100 | |___________|
|__________|

Figure 3: Example input and output

IOI 95