IOI '95 - Eindhoven, Netherlands
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 bars that extend over
units.
Figure 1: Four fences and some of their letter strings (joints not to scale)
In general, the bar code is the set of all symbols with
bars that together extend over exactly
units, each bar being at
most
units wide. For instance, the symbol in Figure 1 belongs to
but not to
.
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
Figure 2 shows all 16 symbols in . 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 in
.
Input Specification
The first line of input contains the numbers ,
, and
. On the second line is a number
. The following
lines each contain some symbol in
, represented by
0
s and 1
s as in Figure 2.
Output Specification
On the first line of output, your program should write the total number
of symbols in (Subtask A). On each of the
following
lines, it should write the rank of the corresponding symbol in the input
(Subtask B).
Sample Input
7 4 3
5
1001110
1110110
1001100
1001110
1000100
Sample Output
16
4
15
3
4
0
Comments