生信刷题之ROSALIND——Part 2

1、Counting Point Mutations

Problem

点突变（point mutation）是突变的一种类型，在遗传材料DNA或RNA中，会使单一个碱基核苷酸替换成另一种核苷酸。
在信息论中，两个等长字符串之间的汉明距离（Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
给定两个等长的字符串 s 和 t，s 和 t 之间的汉明距离记为dH(s,t)，表示 s 和 t 不同的对应符号数。

Given： 两个长度相等的DNA链 s 和 t （不超过1kbp）

Return： The Hamming distance dH(s,t)

Sample Dataset

GAGCCTACTAACGGGAT
CATCGTAATGACGGCCT

Sample Output

7

Code

# Counting Point Mutations
def hamming_distance(s, t):
    return sum(ch1 != ch2 for ch1, ch2 in zip(s, t))


string1 = "GAGCCTACTAACGGGAT"
string2 = "CATCGTAATGACGGCCT"

print(hamming_distance(string1, string2))

with open("rosalind_hamm.txt", "r") as f:
    lines = f.readlines()
    string1 = lines[0]
    string2 = lines[1]
    print(hamming_distance(string1, string2))

Output

7
470

2、Mendel’s First Law

Problem

孟德尔定律是一系列描述了生物特性的遗传规律并催生了遗传学诞生的定律，包括两项基本定律和一项原则即：显性原则、分离定律（孟德尔第一定律），以及自由组合定律和独立分配律（孟德尔第二定律）。

Given： k,m,n为正整数，k+m+n代表一个有机体的种群，其中有k个纯和显性个体，m个杂合显性个体，n个纯和隐形个体。

Return： 随机的两个个体产生一个具有显性等位基因个体的概率。假设任何两个个体都可以交配。

Sample Dataset

2 2 2

Sample Output

0.78333

假设基因型为AA,Aa,aa的个体各有2个，其中A为显性基因，求子代中具有显性等位基因的概率。
子代中含有显性基因的亲代组合有{AA×AA，AA×Aa，AA×aa，Aa×AA，Aa×Aa，Aa×aa，aa×AA，aa×Aa}，子代中不包含显性基因的亲代组合有{Aa×Aa，Aa×aa，aa×aa，aa×Aa}。
因此用总概率减去不包含A的概率更加方便，即1-P(Aa×Aa)-P(Aa×aa)-P(aa×aa)-P(aa×Aa)

Code

# Mendel's First Law
def probability(k, m, n):
    s = k + m + n
    prob_Aa_Aa = m / s * (m - 1) / (s - 1) * 0.25
    prob_Aa_aa = m / s * n / (s - 1) * 0.5
    prob_aa_Aa = n / s * m / (s - 1) * 0.5
    prob_aa_aa = n / s * (n - 1) / (s - 1)
    return round(1 - prob_Aa_Aa - prob_Aa_aa - prob_aa_Aa - prob_aa_aa, 5)


print(probability(2, 2, 2))

with open("rosalind_iprb.txt", "r") as f:
    text = f.read().split()
    k = int(text[0])
    m = int(text[1])
    n = int(text[2])
    print(probability(k, m, n))
 

Output

0.78333
0.67995

3、Translating RNA into Protein

Problem

翻译（Translation），是蛋白质生物合成（基因表达中的一部分，基因表达还包括转录）过程中的第一步。翻译是根据遗传密码的中心法则，将成熟的mRNA分子（由DNA通过转录而生成）中“碱基的排列顺序”（核苷酸序列）解码，并生成对应的特定氨基酸序列的过程。
遗传密码（Genetic code）又称遗传编码，是遗传信息的传递规则，将DNA或mRNA序列以三个核苷酸为一组的“密码子（codon）”翻译为蛋白质的氨基酸序列，以用于蛋白质合成。几乎所有的生物都使用同样的遗传密码，称为“标准遗传密码”；即使是非细胞结构的病毒，它们也是使用标准遗传密码。
20种常见的氨基酸由20个英文字母缩写而成（除了B、J、O、U、X和Z以外的所有字母）。
DNA密码子表与RNA密码子表基本相同，除了使用T来替代U。

Given： 一个RNA链 s 对应的mRNA（长度最多为10 kbp）。

Return： s编码的蛋白质。

Sample Dataset

AUGGCCAUGGCGCCCAGAACUGAGAUCAAUAGUACCCGUAUUAACGGGUGA

Sample Output

MAMAPRTEINSTRING

Code

# Translating RNA into Protein


def translate(sequence):
    rna_codon_table = {
        'UUU': 'F', 'CUU': 'L', 'AUU': 'I', 'GUU': 'V',
        'UUC': 'F', 'CUC': 'L', 'AUC': 'I', 'GUC': 'V',
        'UUA': 'L', 'CUA': 'L', 'AUA': 'I', 'GUA': 'V',
        'UUG': 'L', 'CUG': 'L', 'AUG': 'M', 'GUG': 'V',
        'UCU': 'S', 'CCU': 'P', 'ACU': 'T', 'GCU': 'A',
        'UCC': 'S', 'CCC': 'P', 'ACC': 'T', 'GCC': 'A',
        'UCA': 'S', 'CCA': 'P', 'ACA': 'T', 'GCA': 'A',
        'UCG': 'S', 'CCG': 'P', 'ACG': 'T', 'GCG': 'A',
        'UAU': 'Y', 'CAU': 'H', 'AAU': 'N', 'GAU': 'D',
        'UAC': 'Y', 'CAC': 'H', 'AAC': 'N', 'GAC': 'D',
        'UAA': 'Stop', 'CAA': 'Q', 'AAA': 'K', 'GAA': 'E',
        'UAG': 'Stop', 'CAG': 'Q', 'AAG': 'K', 'GAG': 'E',
        'UGU': 'C', 'CGU': 'R', 'AGU': 'S', 'GGU': 'G',
        'UGC': 'C', 'CGC': 'R', 'AGC': 'S', 'GGC': 'G',
        'UGA': 'Stop', 'CGA': 'R', 'AGA': 'R', 'GGA': 'G',
        'UGG': 'W', 'CGG': 'R', 'AGG': 'R', 'GGG': 'G'
    }

    protein = ""
    for i in range(0, len(sequence), 3):
        conda = sequence[i:i + 3]
        if conda == "UAA" or conda == "UAG" or conda == "UGA":
            break
        else:
            protein += rna_codon_table[conda]
    return protein


s = "AUGGCCAUGGCGCCCAGAACUGAGAUCAAUAGUACCCGUAUUAACGGGUGA"
print(translate(s))


with open("rosalind_prot.txt", "r") as f:
    string = f.read()
    # print(len(string))
    print(translate(string))

Output

MAMAPRTEINSTRING
MQFRAVSIRSRGTPRGGKFLGFKGLKGICQYWLNNSFNGVWVGSIAEKFSSHITSAKRASILEAPNFRLIRNDRPLPDKPATVDVKRALRSGTRTGPTPMFLVTEASKHVLHNILETPFDELSFRIALSRCVSLINYVNHLAGYHKHHTNPWRFQHALSSIILMKCPFIHSISGWTQRHNTHELSEKSAVSAAVGQIPARCSPPKLRSERLPALAHVSKYRRLGLLADRISLSMEQLIINLRCSLRKESHAKVSFAVCLGTSKVRTDVGSAICILGSVEAYVDCKSVSIVNGLSILLIIPPLFKWARSSRMCKQRRASTAALKLSGTKGRIPRPTTRVPLCCRCRALSDGSNCQWLAPRGLRAIYDASRFANCGSRLLAADVPYHPAALRISSSRGFQVATDLPMYITGISLHDSISGCHWPPGRRLDCTPSGSREQCTLQLKRSLLYALTAAIDTLGIPMGGTCSAGYRDSIRVCNLEGFHWKGVCVRPVSFNEVGRLRIWGDCRASLLSVNALYAHFPFLLKTISLDIDERQTAHRSLCFYFGSSCSESTVYNIKQGRFRAQNFDFSGFCRESRRGRVGSERLRVGNQLSTGKNRYRRKRRTLVQLTMNQPPQLKFYLLKRAAFFNPEQQCIVPPIAERIEMVVLARDQIIMQLPVEQRTHRSVRCPSVKRATNYETHYLMHTLRPCYISEVHFQIARRLRGPSHQEIRSIPDNCPAICPALVRIRDVRRNRRLLTLRTVQRRDYPIKCPLPFSASALTIHPHPGQKRKCTLTHKNCALCMSLLDRVDARELPHKSATLLRSSQKSRPRDTGNVIKWCEPAQPQDSFAALAATRSPNIYVDSAATSSPSTGDGVPDPEWPSHTTYRYRRTYMPTVDNSPVERNSRAGLLGVSTPTPKEIRRGELAQLAARTLKRTKFTKPDTCLRGFLNVPRPFAPAGLSLTIHNKVCISALTHLSRHIEQYISTVPTRVVTPTRVNISAMPRIALVIHPSHVNVCSVGLDPTHRPKLYSALGGRLFMRFVVNLEVSIRPLLTTPMTAQQMRSRVVYSCLHLSTLRPRTVSNPFSLSTPAATHCDTPPVVVRGFGSVYYTSLKILLALIALPCISTGSMSVREGRTKTAGAPSRQKLATKQVTLNDLVPIMLHLRSPLLLSPVCHIDSATRLWDFHLSSVRILKLVSTCFCPHLLRFNSGSIPTAAWLPAPVRCLRSAALRYVSKLPRRHSVHINRMVLWPFSLGNCIDPSVSRVLTIHRRLRGLMCGMLKPTGLRSNGFILIGALLEVLGALNNSELKDTSPTTARVLLVVRHRFGQPSLTEGGVRAASRETVVSSLVHVREIIGLTVQLKPILWSSAMRLILGKQRRFELPRGVDLVAELPISSRETGSFSRPIDRLHPCNLIVLRAYRLGHGLITIYANQSIHCHISPDRIFVFSGPYEVSMNAQTQRGGFPASFQRDSKTLDCQRLWRHDLFSIFCVQASTPLYIEVELTWGSILLQGNPLSMRCGCSCTVDGPNTEIWSYITSVGYTPSANVDRLVGSVAIHVIQFSRGTFVVTRSVLPDCHSETMRDETTRGLLIVSLMTAALMCRVRGMVPYRPTTYAGASWSHPTHMQFEHTVQLLGLCLINCSMPAWVQLTGIHLVMSSGPHGARTRSAFAGRGVVCCLHTGTKSQFPGLAECFNDNPSVYYNMVILFYPVQTETSMRQKPVDGGPSSLNDSMVLLDQWQPIHLRCDEWLGCLGTDGLKLRSAAKKPVNATNDTFGAWTKNAIPCFWVFSDLRRNLIASSDFLGSVTTTCCEEGIIYYAPVLVRAPTQIIYVYRVFSPPAKERAHLGPKFQWNVALHCPTLVRGKRKSPMKRSMSRSAPGGVPLVLIRSSWSWLLECPGEAIEPVECLMLHFPSDRARDRGSSQCDSVLASLGIRGRFSDEALPEQSSYTVLVRALIKYRQAAALGAAANKVGPRTGPHPLDVYEPQAPETLFGFRIGILINIGRVKHVLVTTRGEALGLRLPRYKNQIHMTVIVTSRLTRRLSGAGAVFVLRAHAPASRTAQIPIALQLYDKELPPCAVKSCYNVVVVITDTSYRRSFSRSGLVVQGVQLSIILIRGGFATPLFRSPRGLIAEVAKGGFTCFRASIHSVSEKSTSWSRIVLRYMQYGILSICHDTLRLIFLHVLLTIFNCVEHGVYLSKRTGRSSLLVSGKVDALETRRMHPTCHHLTSVFAVWGVLLLTTTLILYLWARPLLAPIAIMPVRTVRVQAIVQLSRGVSLRHKSNVIVGPPSVIGELKVPSPPKVRVYHDVSGCGAVKTLTHLVRTESQQNRFPSISQLVDFPGILSKPKSACVESSVEILRHLYLTVQTSSYYPLVYINGLINSLYATSYNLRRSGLFGWDPDLKRGCSGSIPLSLPNYIGCTGWQKRRIASSPTARVNTFSRALVHMARDMTWTQRTREEYRARLEGLRREIHQTLGEITVKVSYRRRRATSFQHTDNRSRITLEVSRSCGLQDMDTDAVHGFSATYGRAGHQHKWQRKELELQRGVRKKVIYEHIPYRQLAWASLQKLHRRPRTGVTPPLPGELLLRVSRLSGSAHRSVQKFSSETPYTSASVGLQGFDSGGVSNISQENLLPMVYNIKTWCNTVRVPCMAKCVRKRNAKVVNRKEKSILTETRPSVKLRIDLQGPRRLALPTFQFYTGNDACPPLLALWKDSLRAGARMSSNRYITVGPTRAQPRINSVRGCFPPCRSHSELPSGNKCHNGTFSWRTSRGKAFVQPLHSSSTWPQKQRQANSYLVEDAPRVQHRRSHQVCKTDYEAGLIIRLTMRSSFLQQRAPMSPCTNPWDPDLANISNCSLCILIRDLLDSSPHGTRATSSDMHNGGLQKLATDIRTTPDVLKQELSCCMFGGSPEGTLISGSSEYGSLASTSLDARVRVCAVGRISSVPRNVIAALVERFVTQFDTYLQSLT

4、Finding a Motif in DNA

Problem

Motif往往是DNA上的反复出现的序列片段，经常是一些具有序列特异性的蛋白的结合位点（如，转录因子）或者是涉及到重要生物过程的（如，RNA 起始，RNA 终止， RNA 剪切等等）。

给定两个字符串 s 和 t，t 是 s 的子字符串（t的长度小于 s）。
在“AUGCUUCAGAAAGGUCUUACG”中所有出现的“U”的位置为2、5、6、15、17和18。
在“AUGCUUCAGAAAGGUCUUACG”中所有出现的“UGCU”的位置为2。
注意，如果 t 作为 s 的子字符串出现不止一次，那么它在 s 中会有多个位置（参见下面的示例）。
再注意，python的索引是从0开始的！

Given： 两个DNA链 s 和 t （每个长度不超过1 kbp）。

Return： t 出现在 s 中的所有位置。

Sample Dataset

GATATATGCATATACTT
ATAT

Sample Output

2 4 10

Code

# Finding a Motif in DNA


def find_motif(s, t):
    location = ""
    for i in range(len(s) - len(t) + 1):
        if s[i:i + len(t)] == t:
            location += str(i + 1) + " "
    return location


s = "GATATATGCATATACTT"
t = "ATAT"
print(find_motif(s, t))

with open("rosalind_subs.txt", "r") as f:
    lines = f.readlines()
    s = lines[0].strip()
    t = lines[1].strip()
    print(find_motif(s, t))

Output

2 4 10 
14 29 156 178 194 201 225 332 339 429 436 443 450 591 696 713 720 780 854 902 937 

5、Consensus and Profile

Problem

在1、Counting Point Mutations中，我们计算了两个长度相同的字符串之间的最小符号不匹配数，以模拟寻找两个同源DNA链之间的进化路径上发生的最小点突变数的问题。如果我们有几条我们希望同时分析的同源链，那么自然的问题是找到一个平均情况下的链来代表给定链的最可能的共同祖先。

Example

DNA Strings
A T C C A G C T
G G G C A A C T
A T G G A T C T
A A G C A A C C
T T G G A A C T
A T G C C A T T
A T G G C A C T

Profile
A   5 1 0 0 5 5 0 0
C   0 0 1 4 2 0 6 1
G   1 1 6 3 0 1 0 0
T   1 5 0 0 0 1 1 6

Consensus	
A T G C A A C T

Given： 一个FASTA格式的文件。最多包含10个等长（最多1 kbp）DNA字符串。

Return： A consensus string and profile matrix for the collection（如果存在多个可能的Consensus，则可以返回其中任何一个。）

Sample Dataset

>Rosalind_1
ATCCAGCT
>Rosalind_2
GGGCAACT
>Rosalind_3
ATGGATCT
>Rosalind_4
AAGCAACC
>Rosalind_5
TTGGAACT
>Rosalind_6
ATGCCATT
>Rosalind_7
ATGGCACT

Sample Output

ATGCAACT
A: 5 1 0 0 5 5 0 0
C: 0 0 1 4 2 0 6 1
G: 1 1 6 3 0 1 0 0
T: 1 5 0 0 0 1 1 6

Code

# Consensus and Profile

def read_fasta(file):
    sequences = {}
    with open(file, "r") as f:
        for line in f:
            line = line.strip()
            if line[0] == ">":
                name = line[1:]
                sequences[name] = ""
            else:
                sequences[name] += line
    return sequences


def get_consensus_and_profile(sequences):
    n = len(sequences[0])
    profile = {"A": [0] * n, "C": [0] * n, "G": [0] * n, "T": [0] * n}
    for seq in sequences:
        for i, base in enumerate(seq):
            profile[base][i] += 1
    consensus = ""
    for i in range(n):
        max_count = 0
        max_base = ""
        for base, counts in profile.items():
            if counts[i] > max_count:
                max_count = counts[i]
                max_base = base
        consensus += max_base
    result = [consensus]
    for base in ['A', 'C', 'G', 'T']:
        counts = " ".join(str(x) for x in profile[base])
        result.append(f"{base}: {counts}")
    return '\n'.join(result)


sequences = read_fasta("code5_example.txt").values()
sequences = list(sequences)
print(get_consensus_and_profile(sequences))

sequences = read_fasta("rosalind_cons.txt").values()
sequences = list(sequences)
print(get_consensus_and_profile(sequences))

Output

ATGCAACT
A: 5 1 0 0 5 5 0 0
C: 0 0 1 4 2 0 6 1
G: 1 1 6 3 0 1 0 0
T: 1 5 0 0 0 1 1 6
GGTAACCGACCAAACAAATCCACAACCCCAGCCGATAATCCAGTAACAACTATCGCGGAGGCGATAAACAGCAAACGAAACCTAAGCGGACAGCTACAATATCAAGAAACAATAGGTTTTGAATCAGCGGACTTCCAAAAGACCTGTGCTACAAACAGTACCCAACAAAAATAGTCTATCCCGAACCACATCAGACTGATGTGGCATTAACATAACATGAACCAACGCTGGGAGAACGGTTAGAACAGTAACGCTGCCTCGCTCAGGTAGCGAACAGATTACACCAGACGCACTAAACACACACGGGACCGCTATCCACAACTTAGGGCTCCGTGCTAATCACTTCCATACCGGGAAAAATGGCAATCTAAGTTGAGCCCAACACCGAAATCCCTCGGAGCCCCACAGCGGAGGTGATTGAGGACAGGGGAAATTTGCGAAGGCGGCTCGGTACCGACAGGTAGGAAAAACGAGAAGCATATCAAACGCAAATAAGGTAATACCACAGACGCACATACAACCAAGAAGCTAACCATCACAGCCTTCAACGAGAAACCAAAAAGGACACAAATATTGCAAAGGCTATCGTAAACGATACAAATTACCATCCGAGCGCAATCGAACACTGGAGACCCACAAACTAACACTCAATAATACCTGTATATCAAATCATCAGTCGACCCCGCATAAGAGTCCAGGGGCCAAGCAGCTAGCGCACACATCGAGATTTCCAGAAAACCACGCCATTAACTGGTACTCTCTGAGGCTCCCCCGTTCTACCATACCCATCACACGCCGATAAACCTTGGTCGAGGGTAATGATTTTCGAACACCCCAATGCATTAGACTCAATAAGTGAAACCAGCGGTGGGTTTAACATAGAACTCCACCGGCCACCTGCGCAGCCCACACAAATCATGACAGTAAATACACCAAATCATAGCCCTGAGAGTGCTCCGACTCCTATCCACCAAAGAAGCCAATCATCGTGCAA
A: 2 1 3 3 5 1 2 3 4 1 1 6 3 3 2 5 3 3 3 0 1 5 1 4 3 2 2 4 1 5 1 1 3 1 4 1 3 3 2 3 1 3 2 3 4 4 2 3 5 1 2 5 1 2 0 2 1 2 3 2 2 1 2 3 1 3 4 3 1 4 2 1 4 3 4 3 2 5 3 5 2 2 2 4 3 3 1 3 2 3 3 4 2 2 3 4 3 4 5 3 6 2 1 5 4 1 6 5 4 3 4 3 2 5 1 0 3 1 3 0 0 6 4 2 2 4 2 2 2 2 4 1 3 2 1 0 4 4 5 4 3 3 0 0 2 2 0 2 1 2 4 0 3 4 3 0 3 2 2 5 0 2 1 3 3 2 4 3 5 3 4 1 3 1 1 2 2 4 1 2 3 2 0 6 4 2 1 4 2 4 1 2 3 3 4 2 2 2 5 2 1 2 2 2 2 5 2 3 4 4 1 3 2 4 3 1 3 2 2 4 5 2 3 6 3 1 1 2 1 4 3 1 3 2 5 3 2 3 1 0 2 3 1 7 4 2 4 1 2 3 5 1 2 1 3 2 0 0 3 0 3 2 2 2 4 2 3 2 3 1 1 2 4 4 2 5 3 3 1 1 3 3 5 1 1 5 1 4 1 3 2 3 2 2 3 4 3 3 3 1 3 1 3 2 2 3 2 3 1 0 1 1 0 4 2 0 1 6 1 3 3 2 2 1 5 1 2 2 3 3 3 3 2 3 0 3 3 5 4 2 2 4 2 3 3 2 2 6 3 5 3 1 2 1 2 4 4 5 3 4 1 2 2 4 3 4 3 2 3 3 4 3 1 2 1 3 3 2 2 2 3 4 2 5 2 1 3 5 4 5 2 2 2 0 2 2 2 2 4 2 1 1 1 2 3 1 6 4 0 2 1 3 1 2 1 2 6 3 3 2 4 1 2 3 0 5 2 3 2 2 4 5 3 3 1 1 1 2 0 4 3 3 1 2 2 1 3 3 1 2 1 3 4 1 1 3 4 2 3 2 2 2 4 2 4 5 3 4 5 6 2 3 3 1 3 4 2 1 4 1 5 3 2 4 4 5 1 2 1 3 4 5 0 3 4 2 3 2 3 3 3 4 3 3 3 3 3 3 4 2 1 1 4 3 3 2 4 1 3 5 2 1 3 5 2 4 5 1 3 3 4 4 3 2 4 3 1 3 2 4 2 3 3 2 3 2 4 6 2 2 3 2 3 3 4 2 1 4 3 4 4 5 3 2 3 2 4 2 3 3 4 2 6 1 2 3 0 5 4 6 3 2 2 1 5 1 2 1 2 3 4 5 2 1 4 1 3 3 3 4 4 2 1 3 1 0 5 2 3 1 1 3 1 2 2 2 4 3 2 1 2 5 3 1 3 1 2 3 2 3 2 4 2 0 2 4 0 5 5 6 2 2 4 3 1 4 2 2 2 3 5 2 3 5 2 4 1 3 3 1 3 6 2 5 3 2 5 5 5 1 2 4 1 3 3 1 2 2 2 4 3 2 1 1 3 2 3 3 4 4 2 4 3 1 1 1 4 1 2 1 2 0 2 4 4 2 2 5 1 0 3 4 2 0 2 2 3 3 3 4 3 1 2 1 4 2 4 1 2 1 2 1 4 3 6 4 5 3 2 2 5 0 3 3 2 3 3 3 3 3 4 1 1 3 3 3 2 1 3 1 0 2 1 4 2 3 2 2 2 2 3 2 3 3 1 2 2 1 4 2 3 4 1 4 2 2 0 4 2 2 5 3 3 1 2 2 1 1 4 1 5 3 3 1 2 2 1 2 2 0 1 1 4 3 3 2 1 4 3 1 2 4 1 2 3 3 0 2 3 3 1 4 1 1 3 0 3 3 1 1 2 4 3 2 3 2 5 1 3 2 5 4 0 4 5 1 1 2 4 3 3 2 1 4 2 1 2 2 1 2 1 2 1 2 2 4 4 3 5 3 3 3 3 4 2 2 0 1 7 1 2 1 2 2 1 7 1 4 3 2 2 3 1 5 1 0 3 1 6 2 4 2 3 4 3 2 2 4 2 3 3 1 3 1 2 3 6 4 0 3 2 3 2 2 3 3 5 2 1 4 3 4 1 0 2 3 2 2 5 2 3 1 1 2 0 3 1 0 2 3 2 3 2 0 2 3 3 3 2 4 1 2 4 4 4 1 3 4 2 2 1 3 4 2 1 3 2 1 1 1 1 2 6 3
C: 3 1 2 2 2 3 4 1 2 5 6 1 3 2 4 2 2 3 1 5 4 1 4 3 1 8 4 5 4 0 3 4 4 2 1 3 3 3 1 5 4 3 2 2 1 2 6 2 2 4 1 2 2 3 4 4 0 1 3 3 3 6 2 3 2 3 2 2 5 2 2 4 4 3 2 4 2 2 3 2 5 4 1 2 3 2 5 1 2 2 4 3 3 3 2 1 4 4 3 2 0 2 6 1 2 2 1 2 3 4 0 1 1 2 1 3 1 1 0 1 3 1 3 0 4 1 0 3 2 1 2 4 2 3 4 6 1 2 3 3 2 2 5 4 2 2 1 2 3 0 3 4 1 2 1 4 2 1 3 1 5 5 5 1 3 4 2 3 2 1 2 3 3 4 2 4 3 0 3 3 5 3 3 3 2 5 4 3 3 3 3 6 3 0 0 3 1 2 1 1 3 1 2 0 3 0 1 2 1 4 4 3 1 3 2 4 3 2 1 3 0 3 5 4 3 4 1 3 3 1 3 1 2 2 1 3 4 2 2 3 1 3 1 0 2 4 2 1 1 1 0 3 2 6 1 0 5 4 2 6 1 3 1 3 1 2 1 2 3 2 3 2 1 0 5 2 1 3 1 2 3 5 1 4 3 2 3 2 5 0 3 3 3 2 1 3 3 4 3 3 3 5 3 3 2 1 2 3 3 4 2 4 2 3 1 4 5 3 4 1 2 5 2 1 1 2 2 2 4 1 4 5 0 1 3 5 1 4 3 2 3 0 4 1 1 4 3 3 2 2 5 5 2 3 3 2 0 2 3 3 2 2 2 5 2 2 0 4 2 3 2 2 3 2 0 2 1 5 5 3 2 1 3 1 3 4 1 2 2 2 2 4 3 4 0 4 0 2 3 2 4 4 4 3 3 4 1 0 4 1 2 3 3 2 2 2 2 1 2 2 1 1 2 2 4 4 2 0 3 3 1 3 2 1 3 3 3 3 2 3 3 1 1 3 1 2 5 0 4 3 2 1 4 4 5 3 3 5 2 2 3 3 1 3 0 1 1 3 0 1 3 1 2 3 3 2 2 3 3 1 1 1 4 3 4 2 4 3 3 1 1 1 1 1 2 2 2 1 2 2 1 0 5 4 3 4 2 0 1 4 2 6 2 4 2 1 3 4 3 1 3 5 3 1 1 2 3 3 4 1 4 2 4 4 4 2 4 2 6 2 3 4 5 2 1 3 1 2 3 2 3 1 1 3 1 4 4 1 2 2 2 2 2 3 1 5 2 4 1 1 3 2 2 2 2 2 5 3 2 2 2 3 4 2 1 3 4 3 3 2 2 1 5 0 2 2 3 5 2 1 3 1 2 3 3 4 1 2 4 6 3 2 1 4 1 5 2 1 2 4 1 2 2 4 2 4 2 2 2 3 1 3 3 4 4 2 4 3 3 2 3 2 2 2 4 3 3 0 4 3 1 3 1 2 2 1 5 6 1 2 0 1 0 3 2 4 2 3 2 2 4 3 2 4 1 0 2 4 2 2 4 7 3 6 1 3 2 2 2 2 0 4 3 3 4 7 2 2 2 3 3 4 5 3 4 3 4 2 1 4 2 3 1 4 2 6 2 4 1 5 3 3 4 1 2 0 0 2 2 4 3 3 4 1 0 4 0 3 4 3 1 5 1 5 5 3 1 0 1 3 5 1 1 1 1 3 3 3 4 3 5 1 3 2 2 1 3 2 3 5 4 4 4 2 2 2 3 3 2 4 5 3 2 0 4 4 5 2 2 4 2 5 3 3 2 3 4 3 1 2 0 3 3 4 3 3 3 2 1 2 4 2 0 2 0 1 3 4 3 2 1 1 3 1 0 2 4 1 2 2 4 3 5 4 4 4 2 3 3 1 5 3 1 1 3 1 1 3 0 3 2 2 0 3 0 4 2 1 1 2 2 3 4 3 2 3 2 2 3 2 3 3 3 3 3 3 2 4 1 3 3 1 1 2 7 3 4 3 1 5 4 1 1 3 5 0 5 5 1 0 5 3 5 1 2 4 5 3 3 5 1 4 3 1 3 2 5 1 2 1 2 5 3 2 2 1 2 3 1 1 3 2 4 3 2 2 1 2 6 4 1 3 1 4 3 5 2 2 3 2 3 2 2 2 5 0 5 5 1 2 3 2 5 5 1 2 1 4 7 1 5 4 4 1 1 2 2 2 3 4 5 1 1 1 4 3 3 4 0 3 3 5 0 3
G: 4 6 1 3 1 3 4 4 2 2 1 0 3 2 0 1 2 3 2 1 3 3 2 2 3 0 0 0 3 2 4 4 1 6 2 2 1 3 3 1 3 2 3 1 4 2 2 2 2 4 2 2 3 3 6 1 6 4 2 5 4 2 3 2 3 2 1 2 3 2 4 3 1 1 3 2 4 2 1 0 1 3 0 2 2 4 2 4 3 2 2 2 4 2 0 3 0 1 0 1 2 2 2 0 0 4 2 2 2 2 2 3 2 2 6 4 1 3 3 4 6 1 0 3 1 2 7 3 3 6 2 3 1 1 1 4 1 3 1 2 5 2 2 2 0 3 2 4 3 2 1 4 3 3 3 3 3 5 1 0 4 1 2 3 3 2 2 2 0 3 1 1 3 5 2 1 1 3 2 3 1 3 5 0 1 0 1 2 3 1 2 1 2 4 3 2 3 4 2 2 5 2 5 5 3 3 3 1 1 1 4 3 3 0 2 1 1 2 5 2 4 3 1 0 2 1 4 3 2 5 4 5 2 3 3 2 2 4 5 3 2 2 4 0 3 1 1 4 3 3 3 3 3 3 2 4 3 3 1 1 4 3 2 2 3 4 5 2 3 4 3 4 2 2 1 2 4 3 3 2 2 1 2 2 3 2 4 3 0 5 2 2 2 1 3 3 1 0 1 3 1 2 2 3 3 5 4 2 3 2 5 3 3 2 2 2 0 1 2 3 3 2 2 2 1 5 3 4 2 2 0 0 4 2 4 0 0 0 2 2 2 2 2 1 2 1 3 0 1 0 1 1 3 5 4 2 4 0 2 1 3 3 4 0 2 1 3 2 0 1 1 4 2 2 5 3 5 0 2 3 2 4 2 3 2 3 5 2 1 1 1 2 2 3 3 4 5 3 2 3 2 2 1 3 3 4 0 5 3 4 5 1 4 4 3 4 1 2 1 4 2 4 3 2 2 1 3 4 4 4 3 1 2 2 1 1 4 3 4 2 3 4 5 2 5 6 1 3 3 5 4 2 2 1 4 4 1 1 3 4 4 1 3 4 6 2 3 2 2 3 3 5 2 4 3 1 5 3 1 3 1 2 0 2 1 2 4 4 3 3 2 0 4 3 0 3 4 3 2 2 2 3 1 2 3 1 3 5 2 3 6 3 1 3 3 3 2 3 1 3 2 1 1 1 4 1 0 5 3 1 0 3 1 1 1 1 4 3 1 1 4 1 2 2 2 2 2 2 2 5 1 4 3 2 3 2 3 1 2 1 1 0 4 4 3 1 0 2 3 3 1 2 1 2 2 5 4 1 1 1 4 4 2 3 4 2 2 4 1 2 2 2 1 5 1 3 2 1 3 3 3 3 2 2 3 3 3 1 0 1 6 3 4 2 4 0 2 3 2 3 5 3 2 2 3 3 2 4 3 2 6 1 2 3 1 2 2 0 2 1 2 2 3 3 1 2 2 3 4 3 2 1 3 1 1 4 2 1 2 5 2 3 1 0 1 1 1 1 1 3 4 1 2 2 3 6 2 1 3 1 2 0 3 2 4 2 2 1 1 2 4 1 4 2 2 0 2 4 3 5 4 4 3 2 1 4 2 2 6 2 1 1 4 3 3 2 2 2 3 1 1 2 4 5 3 5 4 3 2 0 3 3 0 4 2 0 3 3 3 2 3 2 4 2 2 1 1 3 3 3 0 2 5 4 1 1 3 2 1 1 1 3 4 2 4 4 2 0 3 0 1 3 0 5 3 1 3 1 2 3 0 1 2 2 3 1 4 2 2 3 2 1 3 3 3 3 3 4 4 2 2 1 3 3 2 0 2 4 5 3 3 4 2 5 7 4 2 2 1 3 4 2 2 3 2 1 3 6 3 2 4 2 1 1 1 3 2 3 1 4 2 1 1 2 2 6 4 3 3 2 3 2 1 0 3 5 3 6 3 2 2 3 1 2 3 3 3 6 2 3 4 4 1 1 1 2 3 2 0 0 2 4 3 2 1 1 2 3 1 1 2 4 5 3 4 1 2 1 2 6 1 4 3 2 4 4 1 3 1 3 3 2 1 2 2 1 1 3 2 5 2 1 1 4 0 3 2 1 2 3 3 3 0 2 3 3 3 2 2 2 1 0 5 2 3 1 0 3 2 4 3 6 3 3 2 3 0 1 6 2 2 1 2 3 2 3 2 0 1 3 4 1 0 4 3 4 3 3 4 1 1 3 3 3 4 3 1 4 5 1 4 0 1 2
T: 1 2 4 2 2 3 0 2 2 2 2 3 1 3 4 2 3 1 4 4 2 1 3 1 3 0 4 1 2 3 2 1 2 1 3 4 3 1 4 1 2 2 3 4 1 2 0 3 1 1 5 1 4 2 0 3 3 3 2 0 1 1 3 2 4 2 3 3 1 2 2 2 1 3 1 1 2 1 3 3 2 1 7 2 2 1 2 2 3 3 1 1 1 3 5 2 3 1 2 4 2 4 1 4 4 3 1 1 1 1 4 3 5 1 2 3 5 5 4 5 1 2 3 5 3 3 1 2 3 1 2 2 4 4 4 0 4 1 1 1 0 3 3 4 6 3 7 2 3 6 2 2 3 1 3 3 2 2 4 4 1 2 2 3 1 2 2 2 3 3 3 5 1 0 5 3 4 3 4 2 1 2 2 1 3 3 4 1 2 2 4 1 2 3 3 3 4 2 2 5 1 5 1 3 2 2 4 4 4 1 1 1 4 3 3 4 3 4 2 1 1 2 1 0 2 4 4 2 4 0 0 3 3 3 1 2 2 1 2 4 5 2 4 3 1 3 3 4 4 3 2 3 3 0 4 4 2 3 4 3 2 2 5 3 2 2 1 4 1 3 3 2 3 4 2 1 2 1 5 5 2 1 2 3 3 1 2 1 4 2 3 2 3 5 3 0 3 3 3 3 3 2 2 2 3 1 2 2 3 4 2 2 5 1 5 4 4 0 3 3 2 1 4 6 3 2 3 2 1 4 3 2 4 4 3 2 6 1 1 4 3 4 2 5 4 3 2 1 4 3 1 3 3 1 1 2 2 3 2 2 4 3 2 1 3 3 4 2 5 3 3 1 4 4 4 2 1 3 1 2 3 1 3 1 3 2 1 1 3 2 5 2 3 3 5 0 3 3 1 3 3 3 4 2 1 1 3 1 3 3 2 3 2 2 4 2 1 4 4 2 3 4 3 3 4 0 3 3 1 1 2 1 3 4 5 5 2 2 4 1 1 2 3 3 2 1 1 4 2 0 3 4 0 4 0 0 2 2 2 2 1 4 2 1 0 2 3 1 3 0 2 1 3 2 1 3 1 3 2 5 3 4 4 1 1 1 1 1 3 3 3 4 5 3 4 3 1 4 3 3 4 3 1 1 1 2 2 2 3 1 1 0 3 0 2 4 1 2 3 1 3 3 3 3 3 3 2 1 0 5 2 1 2 3 1 4 1 2 1 3 1 2 0 4 4 3 3 0 3 1 3 3 3 2 2 2 2 4 3 3 3 3 1 1 3 2 4 2 3 3 2 4 1 5 4 0 1 1 3 1 1 1 2 4 0 4 2 2 4 3 2 2 2 4 3 4 2 1 2 2 0 4 5 2 3 3 1 5 3 2 0 2 4 2 3 3 2 3 4 2 2 0 3 3 2 2 4 1 3 2 1 2 3 3 3 2 4 2 0 1 3 4 1 2 4 1 3 5 0 1 2 4 3 2 5 1 2 0 4 2 5 0 7 2 4 3 2 1 2 4 0 2 5 1 3 3 4 3 3 3 1 1 3 1 2 3 3 4 3 2 4 1 0 4 3 2 2 3 3 1 1 2 0 1 1 1 2 1 2 4 4 2 3 3 3 0 3 1 3 0 3 4 0 3 1 3 2 4 4 5 2 3 2 2 2 2 2 1 1 3 1 3 2 0 1 3 5 4 3 1 1 6 3 2 5 3 2 4 2 5 4 4 2 2 2 2 3 6 2 3 2 1 3 0 4 5 2 5 2 1 2 2 5 4 1 3 1 2 4 1 1 1 1 3 3 2 2 2 1 5 3 3 1 2 3 5 4 2 2 5 2 3 4 0 0 3 4 0 3 4 3 3 4 4 5 4 3 1 2 3 1 1 3 4 2 3 3 1 5 4 1 2 5 5 2 1 0 3 4 3 0 2 9 3 2 0 4 1 2 3 3 2 4 1 3 3 3 0 4 3 2 1 5 4 4 1 1 1 4 4 2 2 3 2 0 4 4 3 1 3 2 4 2 2 0 2 2 0 4 2 2 0 1 2 3 2 1 3 0 0 2 2 3 3 2 5 2 2 4 1 3 3 3 3 6 3 0 2 7 3 2 2 4 3 2 2 1 4 1 0 5 3 3 4 2 1 6 3 0 2 1 1 4 3 3 4 4 4 1 3 3 4 1 2 5 2 4 3 0 2 0 3 2 1 2 3 2 1 1 3 3 3 2 4 1 1 4 1 4 5 2 3 3 2