In the biological autosomic inheritance, each characteristic of one individual is determined by a pair of genes (a gene is a part of a chromosome). When a pair of genes presents different information for one characteristic, the dominance of one gene over the other naturally influences the way an individual externally presents that characteristic. In the case of total dominance, a dominant gene imposes the external appearance of its information over the other gene of the pair. The information of a recessive gene (the dominated gene) is only externally shown if there is no dominant gene in the pair. The information of a dominant gene is represented by a capital letter, while the information of a recessive gene is represented by a small letter. One individual that possesses a pair of genes with equal information for the same characteristic is called homozigotic, otherwise it is called heterozigotic. In the guinee-pigs, the gene for the black colour (B) is dominant over the gene for the white colour (w). The descendants’ genetic types (composition of the pair of genes) of two parents are obtained by generating the different possible combinations of the 4 genes of the parents. Each ascendant contributes with only one gene to the pair of genes of the descendant. For instance, one heterozigotic guinee-pig (Bw) presents the same colour of one black homozigotic guinee-pig (BB). The descendants of two black homozigotic guinee-pigs (BB) have 100% probability of also being black homozigotic individuals. An analogous situation occurs with the descendants of two white homozigotic guinee-pigs (ww), i.e., they have 100% probability of also being white homozigotic individuals. The descendants of one black homozigotic guinee-pig (BB) and one white homozigotic guinee-pig (ww) have 100% probability of being black heterozigotic individuals. The figure above illustrates this description.
2/2 Imagine that you don’t know, for a particular guinee-pig, who were its parents (1-ascendants), or its grand-parents (2-ascendants), or its great-grand-parents (3-ascendants). Your task is to write a program that lists the genes of the possible n-ascendants (ascendants of level n) of that individual and the associated probability of each pair of possible n-ascendants. Assume the maximum value of n is 35. Input The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line. The first line of the input contains the genes of the guinee-pig for whom you want to know the probable n-ascendants. The second line contains the value of n, i.e., the level of ascendant generation that you want to study. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output is a list of lines, each one containing the concatenated genes of each member of the possible pair of n-ascendants, followed by the corresponding probability, truncated to 2 fractional digits. The concatenation of the 2 pair of n-ascendant genes must ensure that the resultant string is the biggest one, considering BBBB > BBBw > BBwB > . . . > wwwB > wwww. The output must be sorted in descending order by value of the concatenation of the 2 pair of n-ascendant genes. Note: Before printing any floating point value add 10−11 to avoid round off error. Sample Input Bw 1 ww 8 Sample Output BBBw 20.0% BBww 40.0% BwBw 20.0% Bwww 20.0% BBBB 15.58% BBBw 16.12% BBww 16.67% BwBw 16.67% Bwww 17.21% wwww 17.75%