input (2665B)
1 abaacccccccccccccaaaaaaaccccccccccccccccccccccccccccccccccaaaaaa 2 abaaccccccccccccccaaaaaaaaaaccccccccccccccccccccccccccccccccaaaa 3 abaaaaacccccccccaaaaaaaaaaaaccccccccccccccccccccccccccccccccaaaa 4 abaaaaaccccccccaaaaaaaaaaaaaacccccccccccccccccdcccccccccccccaaaa 5 abaaaccccccccccaaaaaaaaccacacccccccccccccccccdddcccccccccccaaaaa 6 abaaacccccccccaaaaaaaaaaccaaccccccccccccciiiiddddcccccccccccaccc 7 abcaaaccccccccaaaaaaaaaaaaaaccccccccccciiiiiijddddcccccccccccccc 8 abccaaccccccccaccaaaaaaaaaaaacccccccccciiiiiijjddddccccaaccccccc 9 abccccccccccccccaaacaaaaaaaaaaccccccciiiiippijjjddddccaaaccccccc 10 abccccccccccccccaacccccaaaaaaacccccciiiippppppjjjdddddaaaaaacccc 11 abccccccccccccccccccccaaaaaaccccccckiiippppppqqjjjdddeeeaaaacccc 12 abccccccccccccccccccccaaaaaaccccckkkiippppuupqqjjjjdeeeeeaaccccc 13 abccccccccccccccccccccccccaaccckkkkkkipppuuuuqqqjjjjjeeeeeaccccc 14 abccccccccccccccccccccccccccckkkkkkoppppuuuuuvqqqjjjjjkeeeeccccc 15 abcccccccccccccccccccccccccckkkkooooppppuuxuvvqqqqqqjkkkeeeecccc 16 abccaaccaccccccccccccccccccckkkoooooopuuuuxyvvvqqqqqqkkkkeeecccc 17 abccaaaaacccccaaccccccccccckkkoooouuuuuuuxxyyvvvvqqqqqkkkkeecccc 18 abcaaaaacccccaaaacccccccccckkkooouuuuxxxuxxyyvvvvvvvqqqkkkeeeccc 19 abcaaaaaaaaaaaaacccccccccccjjjooottuxxxxxxxyyyyyvvvvrrrkkkeecccc 20 abcccaaaacaaaaaaaaacaaccccccjjoootttxxxxxxxyyyyyyvvvrrkkkfffcccc 21 SbccaacccccaaaaaaaaaaaccccccjjjooottxxxxEzzzyyyyvvvrrrkkkfffcccc 22 abcccccccccaaaaaaaaaaaccccccjjjooootttxxxyyyyyvvvvrrrkkkfffccccc 23 abcaacccccaaaaaaaaaaaccccccccjjjooottttxxyyyyywwvrrrrkkkfffccccc 24 abaaacccccaaaaaaaaaaaaaacccccjjjjonnttxxyyyyyywwwrrlllkfffcccccc 25 abaaaaaaaaaaacaaaaaaaaaaccccccjjjnnnttxxyywwyyywwrrlllffffcccccc 26 abaaaaaaaaaaaaaaaaaaaaaaccccccjjjnntttxxwwwwwywwwrrlllfffccccccc 27 abaaccaaaaaaaaaaaaaaacccccccccjjjnntttxwwwsswwwwwrrlllfffccccccc 28 abaacccaaaaaaaacccaaacccccccccjjinnttttwwsssswwwsrrlllgffacccccc 29 abccccaaaaaaccccccaaaccccccccciiinnntttsssssssssssrlllggaacccccc 30 abccccaaaaaaaccccccccccaaccccciiinnntttsssmmssssssrlllggaacccccc 31 abccccaacaaaacccccccaacaaaccccciinnnnnnmmmmmmmsssslllgggaaaacccc 32 abccccccccaaacccccccaaaaacccccciiinnnnnmmmmmmmmmmllllgggaaaacccc 33 abaaaccccccccccccccccaaaaaacccciiiinnnmmmhhhmmmmmlllgggaaaaccccc 34 abaaaaacccccccccccaaaaaaaaaccccciiiiiiihhhhhhhhmmlgggggaaacccccc 35 abaaaaaccccaaccccaaaaaaacaacccccciiiiihhhhhhhhhhggggggcaaacccccc 36 abaaaaccccaaaccccaaaacaaaaacccccccciiihhaaaaahhhhggggccccccccccc 37 abaaaaaaacaaacccccaaaaaaaaaccccccccccccccaaaacccccccccccccccccaa 38 abaacaaaaaaaaaaaccaaaaaaaaccccccccccccccccaaaccccccccccccccccaaa 39 abcccccaaaaaaaaacccaaaaaaaccccccccccccccccaacccccccccccccccccaaa 40 abccccccaaaaaaaaaaaaaaaaacccccccccccccccccaaacccccccccccccaaaaaa 41 abcccccaaaaaaaaaaaaaaaaaaaaaccccccccccccccccccccccccccccccaaaaaa