input = """1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc""".split('\n')

input = """15-16 p: ppppppppppplppppp
4-9 m: xvrwfmkmmmc
14-15 w: wwwwdwwwwwwwwnwww
7-16 q: qhqdljqtdqqdqqjjcqq
18-20 s: hdpzqqzpngbsmncssscl
4-6 k: kkkkkkk
3-8 x: xxfxxxxxxbkxjzxxxxxq
3-4 v: vvgg
4-5 q: gqqjqqq
2-4 g: rxgf
4-14 z: zzzzzzzzszmvszzzzqz
8-15 k: cckkkkdxkhhkkwkzkl
2-7 m: mntkfmxm
3-11 k: skppkkhjsskkkwzml
7-8 b: tbchbbbfjbbldgkbb
1-3 b: bbbb
12-16 v: vvvvvvvvvvvxvvvvv
5-6 m: mzdfpmn
4-7 c: cvtcssccjtlczb
2-14 c: zdqkdtcxzndgcr
2-6 l: rklhmfmlw
9-14 k: bkxhkdvkzbgkkx
5-6 r: plrrzp
2-13 w: wwwgwwtwwwwww
14-15 d: dddddddddddddjmd
9-12 p: zpklcbpqjgtf
19-20 s: ssssssssssssssssssfw
4-14 s: sssssssssssssmsss
7-9 k: qkkjjjsllkkkpknhk
2-6 h: xhhhdhx
3-5 j: djjljjsqgc
1-5 t: ttktgjstttrtt
1-4 v: nvcm
1-3 v: vhvvqdhmdppbhh
1-3 z: zzqj
2-6 n: xbnkgkknwn
5-6 m: mmmmsb
5-7 n: rnpnnznc
12-14 j: jjjbjjjnjqjvjpjj
7-10 t: ttgtttkttttdgqg
6-9 l: lllllllllllldlll
2-4 m: mtmmmm
1-8 h: hnjhjkmkvhhhgdrvnz
10-11 r: rcxrrrxrqrrrbrhrrl
8-17 x: xdhxjvxcxfxxxxxxn
17-19 p: ppppqpspppppppppppp
10-13 k: nknkkkpknkkkkw
1-6 k: kjpkkkkk
5-7 h: fmblhthhdtz
8-10 g: ggggggrggggg
7-9 s: zrgswsmwksvhssssn
1-4 b: cbbpb
6-8 m: mmmmzmmx
6-12 l: lplcllrswmjlcqwnlgr
5-9 l: dlplljlllflkhlklb
1-12 q: qqzqqqqqdqqqqqqq
10-11 p: kxppppggqcl
2-13 t: gsfftttrtfzzfctvxztk
3-4 f: ffcv
8-13 z: zlzzjzskzzkgkz
1-15 z: zzzzzzzzzzzzwzzzzz
6-7 k: kkkmkkjj
7-8 q: wzwqqfqqqqnlqjhbpxq
7-8 m: mmmlmbnpmgmmv
5-8 v: vvhtvsmnvwwhv
7-9 n: xnnnnnnksnn
9-10 p: vppflpppxn
3-4 h: hhhh
1-7 j: fjjjjjbj
1-5 g: grgwg
1-8 h: lhhhhhhlh
6-7 m: mjmmvqmmdf
14-16 z: zzzzzzzzmjzzzzzzzzgz
13-14 c: rckctczsnlqkjf
2-14 s: shmvnmsmmsssgsg
7-9 n: nnnntxkns
6-7 q: xqqqqqgq
13-15 q: qqqqqqqqqqqrqqq
2-12 s: gqssskssssskt
1-2 v: vvxgvp
1-12 p: rpppqhnfjpppbdlpfvwl
2-4 z: zzzz
3-6 t: tttmttj
2-8 h: chhfbrdhv
2-4 j: jjzjrs
1-3 z: zzzz
6-19 m: tmmrmmxtmmmmhmsmmmlm
2-3 s: nssgss
5-9 m: mmlmmmmmbm
1-4 n: sdwr
11-18 t: tttttjtmtttttttbtkpt
4-5 s: ssshsg
3-6 t: twtnnt
14-17 r: rrrrvhrrrrrrrrrrhjrr
6-8 w: wplxwwwwwrwbqtwww
2-4 s: ssss
11-18 g: pmgcrgsgqgzgggdwlh
1-3 q: qqqqq
4-6 g: ggggdp
11-16 w: wwwxwwwwgxfwwksdw
5-12 c: cccpcccmcccwjcvgcc
3-7 p: pxpzzmppxvrpvchplp
7-9 n: nnnlbnvnwnn
4-11 q: jqwqqhnhnmqqqqn
11-12 g: gxggcgggfgglgg
11-15 d: jxsfqrfddddpfjdg
5-6 w: wwwrww
3-19 d: ddddddddddddddddddwd
2-10 v: vmckfhtzjrn
1-3 h: mhbfh
1-7 x: hxxxxxqx
4-5 v: thxwnb
1-3 x: xlcx
11-15 t: tgtttttttttbtttdtdt
4-5 b: bbbqbbqb
4-13 r: wrrrdkrrrwrrrfrrr
6-7 l: lldllvlllt
17-18 v: vvvvwgvvvvvkrthgll
11-12 t: mbhjbcgqtfqpp
3-8 m: mmtzmmdkf
3-12 w: wcwwzmwsfwmw
7-11 c: cccccckcccx
2-7 z: hzzrhdzmjwjr
4-5 f: kfdsffbrpczwfk
7-8 g: ggggkftcg
1-10 k: kkkkkkkkkk
8-11 d: dhddjddrvkgfbdd
1-7 r: svxrhft
3-11 m: nmsmmmmmqmlbsmm
4-6 b: bbbnbpnbbbbbbbbbb
1-5 b: rbbbb
6-7 f: rcwmfff
5-6 l: hlclllll
1-5 t: tthptzt
3-4 z: fxzzzz
11-12 r: rrrrrrrrrmwr
13-14 g: lgggpgggggggqlgdg
10-13 b: bbbbbbbbbbbbb
13-16 m: mmmmmwmmmmmmcmmsm
3-4 s: sssc
16-17 b: jwhbwzftrjrdzbjkb
2-5 x: xxhcxxx
3-4 x: xxpxx
7-11 b: bbbbbbbgbbbbb
8-19 p: ppwqppbpslpppfphzmz
12-14 r: hczhdgrrcpdmgk
8-18 r: wvdprmvrtvtbccdlvrg
3-9 b: bbbbbbbbzb
3-4 j: jjwkjpj
4-5 j: jwjkq
2-3 b: rrbfkb
2-5 w: bfsws
2-3 f: gffhfcsfklqf
5-7 p: pppppzjfp
13-15 s: gsszjhcsnjknsws
7-15 q: qwqqscqsqmlqqqqwq
10-12 p: krvdljmxjpjpptm
11-12 j: mjjcjjcjdjjj
3-6 s: psmsxcs
2-4 d: mdmdd
8-14 t: jttrttxqtttttlttt
2-4 r: xrrrbr
5-10 g: pgggtvklffghkwgbhgb
3-7 g: fgwgpggpg
1-4 r: rrrrrrr
1-3 f: hxsfbc
11-14 n: nnnnnnnnnnnnnnnnnnn
2-5 w: wwwwpmdnxwlm
2-4 r: rfrtrrrrrr
1-2 m: mtjcmmm
2-10 v: vvvcvvvpvvxj
1-11 r: rrrprfwwrgrmjrbbcrqr
3-4 f: fjkf
7-8 k: kkkkfxvh
3-9 v: vvvvvrvvjnv
5-6 r: rrrrrr
3-6 x: xjvhxxkxxx
4-9 x: rxfghxtff
13-15 f: fffffffffffjxdkbfff
2-4 q: xrzhqkbjsldz
6-8 l: llllllllllllslll
8-11 k: plpqkqngkxrkk
3-5 p: pcppq
2-7 q: hjhzmqzt
3-4 t: ttfhhztttft
3-5 k: kkqkk
6-17 b: lhnnnbcctjvfflcpl
1-4 j: jjjjj
10-11 m: mmmmmvmmmpmmm
16-18 n: nnnnnnnnnnxnnnbnnfn
6-7 z: szmrvzz
6-13 r: qphmsrhsbrhkr
4-10 t: zstrwmhtblxgcttnrt
3-11 v: vvvvvvvvvvpv
3-4 s: smssk
4-9 b: xbbdbcbbsbpbb
6-11 r: rrrrxrrgrrr
11-13 t: ttttnttttttttttt
5-11 d: cddncjdmvfdr
5-6 b: fpbbbbmkdbm
3-4 j: cjpj
3-7 n: bjnqkjzhsxgmznrj
6-7 d: dddlxdddd
11-12 s: wssssssrssfmsss
13-17 g: ggggggggggggggggg
6-7 h: hhhhhhh
6-9 q: qqgqsqrqq
2-14 s: spjhcggszczxzmpfv
2-6 n: hjnxnjn
3-5 b: bbbbrbb
7-9 n: dllxnbptvcs
5-9 s: shssbdssls
7-8 d: ddjdfddzdd
11-12 f: ftfffffzjfpdff
5-10 l: xfczlllvlvlllnllxw
10-11 t: tttktksttdtttt
1-4 l: vlcl
4-5 c: hcccc
4-5 b: bbtbx
9-12 w: wwwwwgwwwtww
14-20 x: kxdxwxbxxxxjkxxxdjzc
5-6 m: mzmmmmxpmh
13-14 s: swsssssssslssl
3-4 c: xgmc
3-7 p: rqpprwwktjpmnjqpx
1-14 s: sphwrndcqtlzcbrsppr
12-17 l: lllfslwlbjlllllll
1-11 d: ddddddddddddd
4-7 j: jjjjjjjjjjj
6-7 z: ztpmzzz
3-5 c: hcccncncczccc
8-12 z: zzzzzmzfzszgmmzz
2-7 d: dvddddd
3-8 q: tcbgclbgs
5-16 b: bbbbbbbbbbbbbmbb
3-4 f: tmjdffrfq
15-18 v: vvvvvvvvvkcvvvvvmbv
6-13 v: vvvvvnvvvbcvjvv
4-6 g: gbggdgphgwfnwg
10-16 d: dddddddddhdddddd
6-12 h: hxhhhhhfjhhhx
1-4 g: wghgnmg
6-14 n: xfznfnncfnnnnmnqnn
1-9 d: dcxdzfjdqjhlprmlgr
5-6 d: sgghtdkbllvjddhdddrd
2-3 f: rffdfpr
4-5 m: fmmmm
5-7 p: gzlqbpkl
6-7 w: qwwgdwwcw
2-3 x: qxxtfnxx
3-5 n: nnvnrn
4-5 l: lllndx
6-8 c: hjrcccccdvcst
8-16 w: ftwmgvxwcnbnhnxlvdfl
4-15 d: jldsrczptcggwvd
4-6 h: hhmhhh
2-6 j: jtnlnlg
14-18 q: qqqqqqqqqqqqqnqqqqq
5-6 p: xlhmshqtplxfzgpj
9-10 r: rrrtrrrrrrrr
1-5 p: shqhvbcnmphrdk
8-14 q: qqtqqdqqqqqqvxqq
4-9 c: zvdccctccc
6-7 n: lnfhdndhtnlnpnnf
15-16 c: rbcrqqcbmcddnpwc
4-7 s: mssssdst
5-9 l: qlgqlkftlkjb
8-11 j: jjjjzmkjljzwmjjqbjq
3-4 j: jfmr
2-5 r: rfrrq
1-4 m: msmmmc
3-4 j: vfjhvjqcjnzpl
2-4 c: cvcc
4-5 d: dddfgddd
2-5 z: dndsb
2-7 h: hhmqhthhhhl
11-15 l: llllkllllwlljllglpl
2-3 j: cjjjgjnp
15-16 g: gggggggggggvggxlg
7-8 p: pnppppjj
17-18 h: hhhhhhhhhhhhhhhhhh
2-3 f: frlf
5-6 v: vvvvvv
10-11 n: nnnnnngnnnnrnnndrv
4-8 f: jhqdjfnfft
14-15 l: llllqlllvllllllssl
5-6 w: wkjwgch
4-11 h: jxjhhhnhhhhhtch
10-11 m: mmmmmmmmmrrm
4-10 m: mwjtqmwgnq
16-17 v: lprvzvvvvvvvhvvmvvv
5-7 g: gggfggg
11-14 l: lllzllldplhdllll
3-13 s: qcvwtwstkvrrfzs
16-18 g: ggjgggcggggggggzglg
3-4 s: sscfs
11-13 c: cjcccfccscwcclcccb
6-8 k: zkkkklphkk
1-7 j: nkqkqbl
1-8 h: sshmwjhkkjfhgfhhd
4-5 v: rvvvvvvv
2-3 h: phhhb
13-14 j: prdbjqmvbmjspr
12-19 l: mllljlllllllllllllt
13-15 x: rgnqfdxsvlplxjx
7-10 r: rrrrrrrrrbr
1-4 b: bbbbmbb
8-9 f: gfndcxcvm
5-6 n: bnmnnnnxjfrn
4-5 n: nnnpxn
7-9 r: rgrrsrrrwrrr
1-6 p: mppxpp
4-5 k: nckkmkzkxg
1-4 s: sssssjsszssssssn
2-3 g: sxpw
2-5 r: rrmrcgrrrlrq
5-9 n: nkxnnnnrnp
14-15 b: bbbbbbbbpbbbbcmbb
1-4 c: rsrswbcf
3-4 g: ggxctzgs
5-6 p: ppppfp
5-7 s: sswssssqbs
5-11 z: zhvlzwfgpgzzzz
8-9 m: mmmmmmmml
13-14 s: sssssssssssssb
9-12 f: fhstmfffkmjrfffpr
3-4 z: zzzz
7-8 z: zzbzzzpwz
2-12 d: mdddcdsddddrdd
1-10 s: xhqvwjvbspskb
6-13 z: zzzzzzzzzzzzrzz
4-7 r: rwrrtrsrrpr
2-9 g: lgpkjldqwvhntvwgb
7-11 t: xdttntttvtzttzjf
8-15 v: cnvvjrzvvvvvprfrv
1-2 g: vggmh
11-13 t: tzzfrvhmtctttttthtnt
16-17 s: ssssssvsssssssssp
2-6 f: frfhfdf
6-8 h: jhhhhhwmh
7-8 n: rmnclfgn
10-11 m: mmmmmmmmmxn
9-13 h: hhhhhhhhhhhqhhhh
10-11 q: qqphmqqqlqq
10-18 q: qqqpcqgqqqqqqqqqdqqp
2-15 s: pqmfksdwbkklrlm
15-16 p: pppppppppppppprx
6-11 d: vddddswgdjz
2-8 m: mrmmpmms
7-8 x: xxxxxxxxx
3-6 g: bmgtgwjnrdq
1-11 j: jgjjjjpjjjjjjj
1-6 r: rqqvmrbrbrztwk
3-7 h: hhfhhhkwd
5-9 w: wwwwwwwwwwwww
11-12 g: gvvczkkmtsgtpsgbg
4-10 q: qqqqqqqqqqq
4-6 t: tttvtwqt
9-10 h: hhhhhhhhkw
8-12 s: cssssssfxssmsrwssssf
2-5 c: sgwzjggz
3-6 m: mmzmmz
10-13 v: mvvvvqdvvfhvfv
3-6 j: slvljjkbtjdqvq
2-6 s: sbsssgsfmsjssssssps
5-7 r: xcdwvgrrrprzflmrcv
4-6 l: bdbdvlllltlv
6-14 s: sxsssqsqsssvsssssss
10-12 j: jjkjljjjjzjlvmw
19-20 d: ddddxddddwddddddrjdd
3-5 x: mjxxk
9-10 c: ccvbcbcccccc
3-4 t: kpvn
5-6 v: qcgpvw
5-7 l: ljjllpklctzlv
6-14 h: dxhhgzhhtdhthrjqn
11-14 q: qqqqqqqqqqnqqzqq
1-8 p: pshzfpnpp
7-12 l: mwclllllflklhl
2-10 j: jmjgwjjjjjtfj
5-6 j: jjkmjmjbjj
4-14 f: ffbgdffrdffffh
5-10 t: tttnbtrhchdt
6-10 c: kccrcjcscmccct
10-18 c: cccvccccchccccccvqc
2-9 p: ppprplrrpp
11-12 x: xxxxxxxxxxxxt
17-18 w: wwtrwxwwwmwwwwwwww
6-7 r: rrrfrrzrrg
1-3 r: gflrrg
10-19 z: zqczjxrzrpzzzdfzgzd
4-6 n: nnnnnknnnnnnjnnnnn
7-9 n: nnnnnnnnw
4-9 k: qnvkkfphktkt
6-8 f: fffrftfpfffrfcfff
3-6 q: qqqqqvqqq
5-6 x: llxdwx
7-10 n: nnnnnnnnnnnnnnnn
12-15 j: jjjjjjvjjjjwjjv
6-9 f: dnjjlvkfrkf
11-17 h: hhhmhxnhhjvhhrwjmhh
9-16 f: fffffffffffffffff
3-4 q: qqqqk
6-8 b: gwxlbzzprtn
7-17 g: grqqztqvggjjgdggfgg
1-10 k: ksghkhvzkxjgxks
10-14 f: pbsffkfftfffff
1-6 n: bnnfnb
1-2 c: hdzqlbcnzjvs
1-19 z: zzvzzzzzzzzzzzzzzzz
8-12 m: vvmmbmmvkmmmm
2-9 t: ttwtxthgtptttttg
2-4 r: rlhvrrqjtswfsb
9-16 s: dssnssjftsssshsp
10-11 z: zzzzzzzzmhs
5-9 j: tjrgpjcjl
8-11 t: xtlntfwttnp
1-4 m: kcxbmdmmk
3-4 x: xxldxxnq
4-14 v: pvqkvbbvsjjxvtvvsrrv
4-7 v: bpwtsvm
10-12 j: jjjnjjjjjjjj
5-9 h: dmqpdshshh
9-11 h: prhhhhhhfvgh
2-4 d: qdddd
3-6 j: jjjjjjj
7-13 m: gjpmplmtmmhvm
6-7 x: xxxxpzw
6-9 k: kswkfhkzkkr
3-8 m: mxmdmqmxhsdrms
12-13 b: bbbrbbbbbbbbbbbbb
5-6 h: cphxvkmhghh
6-14 k: kksgdkvhwkkxbkcvb
4-5 z: zzzmg
9-13 l: lllllllllllll
17-19 b: pbbbbbbbbbbbkbbbbbpb
5-6 p: ppvqcqp
2-7 n: snlcnszdc
1-3 m: qmmz
4-6 w: wwwwwwww
6-8 f: mfffffff
1-8 l: lllllllrlllll
3-10 d: fmwvkqdhgh
3-8 v: vvvvzsvx
12-14 m: mpmmmmmmmmmdmnm
11-12 m: mpmmmmmmmmzwm
5-18 g: khsdgtssgvkwwnwhbg
15-16 q: sqtqlqqvqqqqqfqdw
3-7 p: pffbppdpnhqpzht
10-19 r: rrrrrrrrrlrrrrrrrrf
1-2 d: mfdrnswwhg
2-3 d: lcdd
13-14 k: kkkkskkkkkkkrm
1-4 j: jjdt
7-9 r: rrrrrrnrdrrrrr
1-14 v: vvhvvvvhvvvvvvkvnvvv
2-4 c: crsncccbwccvb
12-14 w: xwwwwwwwwwdfwjww
16-18 l: llllllldllllllldlfl
14-16 p: jpvhrsgpdhhqwpdp
9-10 m: bnfmvmmmmsmmmm
9-13 t: tpmsttfcctksdktdfqx
1-3 c: gzcvchdwdbq
2-3 v: xrvvvwn
1-4 b: bbbb
13-16 s: snsssssgssssjssjs
2-5 t: gwtcl
1-6 s: qsssmdsssm
7-14 z: bhgrzzjzgzmzzzzz
1-3 p: ppnptchxppvw
11-16 b: bbmbbbbdbbhjbbbvbjc
4-8 x: xzmkxrvxqxvt
1-2 m: mmmm
1-4 r: wrjb
7-11 d: dddddhdckbddc
4-5 w: wwwmw
10-12 p: pppppppgpppp
2-6 v: vtvvvrv
5-9 w: gwwwlwwjnw
8-11 j: jjjjjjdvjjcjjj
6-7 s: sssmsss
6-20 d: dsrnfpphdznqdjfbqvql
2-7 x: rlhprqxswxckpxh
3-4 q: qhqq
4-9 z: wzgzrzzzznzqrzvjvtn
6-8 d: cldrblzkmhmc
5-7 t: ttttjtht
3-10 l: lllhzklllllll
14-15 k: kkskkkkkkkkkkkkkkkkk
6-12 q: qqqqqgqqqqqr
12-15 f: fcffffffrfffffflmfw
5-7 l: nhltlhq
10-12 j: tjjfkbgjzcwsp
6-7 r: rrvrrmqr
9-11 m: mmmkmmggmfmhtmmrm
11-19 d: dkddrdddnddcdwdvldd
6-7 n: lnnnnfltcz
7-9 j: jjjgjjjjjj
11-14 m: mmmmmmmmmrmzmmmmmmmm
5-6 m: mdnxmmtmmjkmlzpzj
2-9 g: hgmjfsvdgkgsbr
5-6 t: sbttttkb
5-9 t: tnttwrhttt
3-18 t: fnwszlmqhlzdzhmkmt
3-4 b: bbmbbbzzbbbnbbx
8-16 l: vxlllllkllllllljl
5-13 m: xmxqfgjjtxrrfwpzjmjq
14-15 q: qqqqqqqqqfqqqfq
7-10 w: wwwwwwbwst
11-12 j: djjjjjjjwjsljj
2-9 j: pjjzxjlbjmjjjj
6-7 r: rrrrtrr
4-5 x: plnxmrxxxrkv
10-11 b: cbblcbbsmhnbbbbndb
1-6 v: vvxvvwv
8-12 t: ftttttltttttttttt
4-5 p: jzpjf
1-5 g: zbwrgrk
4-6 q: kzjnpf
5-7 b: gbbbbbbbbw
10-11 r: rprjzrrrrqm
18-19 k: xkkvkkkkzkdkzkkkkjtc
10-15 x: xxxxrxfxxxxxxhx
2-4 p: xqvp
13-14 t: tttntttttttttt
5-18 p: qpljzcpxppzhbqpprrjz
4-5 l: lllll
4-7 m: mmmmmpm
3-8 b: bbzbbbtglbb
1-4 l: lqlm
5-7 v: vxvvvpvvv
9-11 n: nnznhdrnbnxnnn
2-7 h: chdvhrh
4-7 v: twgvkvvfhzv
2-6 q: mqfqvq
10-11 j: jjjjjjjhjqldj
5-8 m: rvmpmggmhmpmmj
7-8 j: jjhjjjpj
12-13 z: zzzzzzzqzzzpz
5-12 p: qptzdzpsppppn
14-19 k: kkkkkkkkkkkkkgkkkkk
8-12 v: vvpdvfvvvvvttpcv
9-13 x: mxvxxxxxvxsxwxxxbj
6-15 w: fwrwqzwwtwwbwwg
4-5 t: tttttjtw
3-4 d: sddxfd
3-4 t: rjxwfzktkvszlhttjd
18-19 c: cckccqccfccnnjcczgrr
7-9 k: kkkkkkkklkk
4-5 v: dvvlsvjv
7-9 c: cccccrccccccccc
9-10 x: xxxwxxxxxx
1-4 k: kkhk
3-4 k: kjztk
1-5 m: bhcmm
2-4 f: ffff
8-14 s: sspsssttslsssslwss
3-4 k: qkjk
14-17 k: kxrmldkdcpnxckhfkwqz
4-5 q: qqqfngfqqq
1-3 b: nfstkpdbbdtbghdt
2-5 q: pqhrqqnfrskvzz
3-7 r: mhrwxrrrrskdjrb
2-8 w: wvffwwqkww
4-5 w: wwwwqww
5-11 h: cchhhrmjdkhqwchhbhz
3-6 z: nzzkgzp
5-7 l: cwllllltlllll
17-18 q: cmhblsqvqjqwqqvrwtqp
6-19 m: mmdmmlbmmmmmmmmmmmrm
17-20 b: bbbbbbbbbbbbbbbbsbbt
3-4 m: xmgj
9-14 r: qkktgxrsfxgknrj
2-4 s: khcjpl
4-17 w: nfwcmjnkczdxvsvzx
3-10 r: jrrggrwfrrrjrprrngtr
6-11 n: rpnnltfnxtj
12-16 q: qqqqqsvqqqqwqqqq
1-3 w: mdwd
8-9 j: jjjjjjjbj
9-17 k: mkkklkkkkvkkmpknvkk
4-5 g: htgghp
18-19 c: ccczcggccxccclcccgc
2-4 p: pfnp
3-4 w: vwfq
9-16 j: jjljjjjjvjjjjjjjjtj
12-17 v: vvcgvvvvvcvzvvsvlvv
2-11 t: xhqtmtwtttgtttthtt
3-4 h: hhswh
5-6 w: wwwwwww
5-9 c: ccscccckc
4-8 b: bbkgbbbgb
5-6 q: dkqrqp
11-12 t: ttttnttttpqdttg
3-6 h: hhfwhhd
12-13 r: rrrrrrrrrrrrrrrr
3-20 r: rrrrrrrrrrrrrrrrrrrr
4-5 c: ctcccqcwcc
4-11 l: llldwlvlmlqgl
6-7 t: ktbttkqtt
3-7 t: jmtvtrttcwf
2-8 d: bjdvqzbg
5-10 k: qqmkvkknxjmkckk
6-7 z: zzzzzzzl
2-12 p: wmtjnsxzgkkcwnwc
2-18 g: wvhbzrwgnlrrhnhcznv
4-8 q: mfqcdghqmxqzcljczqt
1-3 t: nktl
2-16 x: vxzczxqbgfgrcghx
15-16 j: vjtjjjnzjzfjjbcwdl
11-14 w: wwwwwwwwwwpwwww
2-11 m: mnmmmmmsmmnmmmm
2-3 l: llqglv
8-11 d: ddddddlmddgddddsdd
11-14 w: wwwwwwwwwlzwwhw
15-17 s: ssksssrsdssswpmdm
11-14 x: xxxxxxxxxhxxxxx
12-14 q: mqqqqfqqpqqqqqqqk
3-4 x: rxjx
7-14 w: wpwwwwwqgwwwwhsw
8-16 s: sssssssgssssssvcss
4-5 g: gxgggg
6-8 b: bbbbbdbxbbbbb
15-16 x: dfxxxxxxxxxqxxxxxrx
2-3 x: cxxnr
2-4 d: tdjdpzrrbpmmbdx
6-10 l: lllllllllllll
10-14 s: sssssssssmsssrss
1-4 c: ccdc
1-4 w: bxzwjqdwpwlwjn
2-5 l: vqllflll
10-17 z: zmjrzzzzzszzzslzzmzz
4-9 c: dcckccjpmcq
12-14 w: wwrwxwwwlwwwwwwww
1-4 s: kjsc
5-11 w: wlwwwwwwpwj
3-6 q: dpcqqfq
9-11 l: lllllrfnmnblfrll
5-8 r: rrrxhrrgr
3-13 h: hhhhhhhhhhhbhhchh
2-5 f: pffqfw
1-3 x: xxxx
2-4 g: rgpgtwwrfxdbgs
1-4 f: xffnf
7-19 k: kprtbkxkkkrkkkkkkdh
15-16 z: zzzzzzzzzzzzzzjmz
3-4 p: xppp
10-13 l: jlblmllgllgll
1-5 s: fsssx
3-6 d: dbjddt
9-10 s: ssssssssqs
1-7 s: szjnqdss
5-11 c: cccctsccccbcc
2-3 d: cbdhd
5-16 j: jjjjxjjjjjjqjjjjjj
9-17 g: gjgggglgxgggggggn
1-2 r: dhrmmccfnthtxmmxp
8-12 q: qqpqmqqzqbqqkn
5-13 q: qqqqwqqqqqfqqq
2-9 m: kzwvwzqrmvn
3-6 c: fscccgc
14-15 h: hhhhhhpbhhhhhhhhh
1-5 c: cxltc
4-5 d: dvddd
4-5 t: vfctz
3-4 r: rrlr
1-16 w: wwwwwwwwwwwwwwwwwww
2-4 f: ffcf
13-14 h: sbchhxhhxrxdlb
8-10 s: sssxgcshsjs
18-19 t: tttttttpttttrtttttp
5-13 b: bdmpbkbjdhbbbqkb
3-5 z: wrskzzzq
7-10 f: fgfffffffffff
2-5 b: qrbmskdkbs
3-7 x: xnctxxkqxvz
14-15 d: dddddddddddvdtd
10-13 d: dddsrddzcldnbndntx
10-14 w: wwwwwwwwwwwwlwww
9-10 v: svvgsvvwvvvvvn
4-10 g: gggggggggggg
2-8 x: xgxxxxxr
3-11 b: fbrwbzfbbkbs
8-9 f: qvdxcfqffxdlhlndqj
8-13 k: rkxdkfkbxbskkkgvkk
5-9 t: xtttmtpsptztts
1-4 v: vvvkvvvvvvvvv
11-12 n: nnnnnnnnnnpn
1-2 f: htkv
3-7 s: qfszssf
4-5 j: njjjjjjj
7-8 f: fdffffbjfk
3-5 v: qcncphtnjnqvr
6-11 l: lmwlptlllllll
5-7 q: zvqlwqqcqqdqbm
2-6 h: hhhhhhh
5-9 v: nvslbccbvpqfgt
9-17 k: mzvbktkkkckktkkdkkk
5-6 f: fffflf
12-14 t: ttttttlttntptmth
17-18 k: flnshklxckpjkkzkkk
6-11 w: wwwwwwwwwwwwwwwf
9-13 j: jrpjjjwvjjjjjtzj
6-8 b: bbqbbfbzbb
10-13 q: qqqqqqqqqqqqq
12-15 t: blftxfwtsldttstztnt
4-5 g: mggqg
10-19 z: fzcvzpkznjrzgsfwzrv
5-9 t: txcgtnvnt
6-7 w: wwwwwdm
10-14 g: bgggglgtggggxkxggggg
6-8 f: srjfqgrr
2-4 w: wrbbwk
8-9 s: sdjcssswxn
7-8 w: zwwwwwwwwwv
1-5 l: llvlxll
1-18 h: hqbhdchhhhgqfhwhjh
8-12 t: dqttttthtttlttxnt
5-8 s: gssbtqsszscxsxt
8-9 r: rrdvrrlrxrrrf
7-14 s: xssrszdrqspbjk
2-5 l: lwllv
1-4 q: qdxkkdtqccdfpjlcjpsn
12-13 z: zzzzzzzzzzzjpz
1-8 r: gsrcbxpp
2-4 w: jwwwnd
2-4 w: mwmwsnmdrrmzstcqnfx
16-17 j: jjjjjjjjjjjjjjjzjj
10-11 w: vwsvvfwnfdzwwn
8-13 r: rrzrrrrrhrrrrrvrr
12-13 v: vvpvvvvvvvvcp
5-16 t: tptwxtzstbtstvlwt
3-4 x: nxxxx
3-4 w: hwpm
1-4 w: xkpw
2-7 t: tcnmnstc
10-14 v: bjvfmvwmlfmzvntvv
1-8 n: zdnmntxjznx
4-9 n: nnnnnnnnnfnnn
3-5 v: vvvvvkvvvvv
9-11 p: dbvrspsqpswqbs
3-11 l: lllllllxllll
15-16 t: tttjttttttttttvkt
2-5 z: zzhzt
4-5 x: xxxxxnx
1-4 r: rrrr
1-3 t: fpgvpvft
16-17 g: ggggzggggggggggggggg
6-7 f: fffffzd
3-8 t: tttttttttt
5-6 k: dpxbkk
9-10 s: sssssssssx
6-7 d: xdddddd
7-13 d: psjkdzdwkpzhdv
2-7 l: llllllxllllllllll
4-6 h: jhjhnhhhhhhhhldhhhj
15-16 q: qqdqkqqqtqqqtxrqqlt
2-14 f: tbthxfczjjkffffh
11-12 m: mlmnqvmhmpzz
13-15 l: llllllllclllzlpg
5-8 j: jjjjjjjj
2-3 g: gbmtnjgq
3-4 g: rgqfggl
10-15 w: wwxwwkwcwgwwbwx
4-5 w: wwwnd
3-6 h: vcpsbhhgkhrnjcpnhtv
2-6 q: qqqqqtxqq
8-10 l: lllllllnlm
3-4 c: ccgsg
2-12 p: fpfnfwvzrrwppgj
4-11 p: hxsjlvtxnpndg
1-2 h: tchph
3-5 w: tkhjdw
2-3 b: brkzbtl
13-14 d: dddbddwdvxjdcz
2-3 m: mmmf
7-8 r: rrrrdrrrr
6-8 w: hwwwwwwwqsq
6-7 x: sxkxbxxxtxxx
5-10 f: pqpffjxfzf
2-4 k: bknl
2-9 x: xxqxsxxtp
1-10 v: vzwhxdmfzkcvfjkltl
6-7 d: zdrfljdwr
10-11 h: bcngmvshhhh
11-12 t: ttttttttttft
7-8 b: rjbbbqbb
9-10 c: ccccccccdwc
14-15 h: hhthhhhhhhhhhhhhwhv
1-3 d: dsddfgb
14-15 v: vvvhvvvvvvvvvvvxv
5-8 w: wbswsttmqwzpdwwwts
5-7 w: vwdwtwmrljq
3-4 b: mzbbqsdhrtbdlf
2-5 n: prxnnn
6-11 g: fgggggggggkggb
5-10 q: kqpwlthzbvjwztmdttl
2-9 v: wkglnxwscznvqwjzg
1-13 x: xxxxxxxxxxxxfx
4-6 s: ssshsq
13-14 l: lljllmllglllllnlll
2-10 b: mbvlbjmhrj
4-14 j: pjpjkncfzchgzgpvcxsj
4-5 k: kkpnpkkr
5-8 x: xdtxdxxxxmffxxf
1-6 n: nnnnnn
3-4 r: btmrrdr
1-5 c: ccccfccccccccc
5-6 q: qwpqqq
2-8 h: gxhhppdf
7-9 l: llhllhlll
13-17 f: fffffffffffffffff
1-14 w: wtvkwddfbpklwwtqf
1-4 j: pjjj
4-6 t: tltcszzt
2-11 k: skjzfjrfktsbvkk
3-5 f: cfmfbgfs
7-10 h: hhchhhrrhfhhzrh
2-3 n: nnrkn
3-5 s: lsvcwg
19-20 r: rrrrrrrrrrrrrrcrrrrt
5-11 h: hkhbhghxhhh
7-9 m: bhrmwpfmv
3-4 n: nnzzs
5-10 n: nnnnnndnncvnnj
1-2 n: nfnd
4-6 l: klwldlvllnt
1-9 k: kkkkkkkkkk
2-3 m: cjhq
7-10 l: lllllllllll
15-16 j: jlwvstmfjjjjrgcr
5-7 d: vfdrddjwdp
4-6 t: tttrtl
3-10 g: dxjmwdhqgslgkvz
12-15 d: dddldddddtdmldw
2-3 v: dvvtbht
7-9 n: nlnnnmvnnnnnkn
4-8 v: kvvtvlvs
2-9 f: ffffgvxsfpxfxzr
4-5 z: czzbwwzzzw
5-6 x: hjxxldx
5-7 b: bwbxmbshlvp
3-4 f: pzffwr
5-6 r: frlgnhmrf
2-3 w: kwwd
4-5 s: szsrs
11-12 j: jjjjjjjjjjhc
3-4 v: vvvv
4-5 b: pbggdlhbbdfdj
3-12 j: njrbhvwxmmwfrfmmbw
15-16 m: qqvbjcmrmhmlljnj
1-9 h: hhhhhhhhmchhhhhhhh
6-11 p: ppppppppppgpp
14-15 p: gppgpbprpppzppppvp
3-15 z: zzgmzzzxzzxzzzqz
7-9 x: rxxxxxxxrvwxxx
4-5 x: jxxsxxxq
5-7 t: xtggtktxt
19-20 m: mmvvmmmmlmzmmmmqmmmt
1-3 z: zzzzzcznzzzz
1-5 t: zqthftmx
3-9 x: rwxxmxnxxx
11-12 x: xxxxxxxxxxwh
11-15 v: vvvvvvtvvvvvpvcv
14-17 d: dddddddddddddddddd
13-17 l: llllllllllllllllhlll
3-8 m: mtrnwmdmmq
15-16 n: nnnnnnnnnnnnnnrcnnn
9-11 w: wfwwwwctwwq
7-10 b: bbbsbbbbbbkbbbb
12-18 k: thxrfrwhzxhfpnjqkk
3-4 f: wffs
1-4 t: tmvktrpdt
5-8 k: kkkkskkw
9-12 w: wgwwwwwwwwwww
6-7 r: rrrprfc
2-4 g: gxgk
9-12 p: hjpppppppphb
7-11 f: fffffffvfffff
1-4 r: bclrhrqlpjmrv
7-15 s: lgrsrpskbgsmqgw
8-14 j: jhqfjjjjjjjjjjj
10-11 d: dddddgfdddddd
3-4 j: gjrm
1-5 x: xgvwrx
2-11 r: lrxrzvplwxq
5-10 f: xffffffffff
3-4 g: ssgrflgvgg
9-18 d: dlrqctvdrdcddrxjbd
2-5 p: pppppp
2-4 l: fscks
2-18 v: pgvgxwwljphbkfwlhv
1-3 h: xdmnfptbgghqbzvrd
13-16 q: sqqqqqqqqqqqqqjq
4-6 v: vvvvtv
11-16 b: bbbbbvbbbbblpbmbb
9-15 l: vcqwdtfblfwxpqv
2-5 c: cfccm
4-5 g: ggglvzgpg
6-7 w: wwwdwgwfkwnkw
3-4 d: dsbd
7-8 g: ggfggghg
2-10 x: xxxxxnxkxflmxxjxxx
5-7 h: pthdhsz
3-7 p: xcndbvbbh
9-11 n: nhnnnqnnlcwnn
3-4 p: pbpp
2-5 h: hshhz
9-13 g: grkngqlwbkrjn
14-19 r: rrrrrrrrrrrrrrgrrrrr
2-3 r: krtcfphwm
9-10 v: vwvvvvvwsvvqvv
2-5 b: kbmgpbrn
4-7 l: lzlmlltll
13-17 w: wwwwwwwwwwwwcwwwpw
1-3 q: qtqh
1-3 v: fxbcv
6-11 v: vvvxvvvmbvpvh
5-18 s: ssxpkssmgnssssldsvss
11-13 q: qqqqqqsqfqqqq
1-7 r: wrprrjvrrrrwrrrr
13-17 q: qqqqqqtqqqqqmqqqq
12-13 f: ftwffffftfxffqtbxfff
12-16 r: tzqrqrwlnrrhkpgn
5-6 p: pppbgpp
9-10 r: rgrrxnrrrr
16-17 d: dxkfdrdtmdlchlddd
7-9 k: kkkktkkkkk
6-8 p: pppppppc
11-17 j: jjjjjjjjjjjjjjjjjjjj
8-9 q: qqqqkccwmqjqqq
7-10 c: cccflcccccjsh
3-18 k: dbzgrzqppcvkkjmskpr
2-9 v: rvwbhvhpwjmf
6-10 s: swhsspsshc
1-3 n: nnnt
13-14 s: dzqvjztkgsnbsbs
1-5 n: nnsnnnn
9-17 v: vvvzvvvvqvvxvvzvpv
7-10 m: gdqmmhmxmt
6-12 d: dfdkrvjdwbgg
1-8 q: qqfqtqtq
8-9 n: nnnnsnnhmn
2-4 p: pwpz
2-5 r: wlzzk
4-6 z: zplxzzz
6-11 s: sssssrssssx
16-18 t: ttvttttwtttttttvtlbt
1-12 r: rgsrkfgmrbbbhcrtr
11-15 n: pgqnnnnnnsnfwnw
2-4 b: dthd
5-10 r: xkllrwxbvrrbtlk
17-19 w: wwwwwwwwwwwwwwwwwwv
5-7 t: ztcsdtqts
1-5 b: vbfbd
6-12 g: kzggwgcgggthglgmg
14-15 l: xlhlglllllsllmvdllll
1-6 l: lglldglpqlxr
9-10 p: wpppqpptppppnp
2-20 s: ghrpccsrgqzgrcbqhjjb
2-15 f: fnfflfmgfbwhfwffdtd
1-2 v: vbpcktv
15-16 r: rrrrjvsqjrvrjntdrd
14-18 z: zzzzzzzzzzzzzqzzzk
12-16 h: hhhhhhhhhhhhhhhhhl
17-18 b: hbbfjdblmbnbgsbcdwg
3-5 b: xnbbbtb
3-10 x: xqxmxrvsxxwxth
4-6 q: qqqqqqq
8-9 r: rrrrrrrrr
12-16 q: qrqqqzgxcqqrqqxv
10-11 p: rppppppphtndp
2-7 h: zhhpjkhvplbr
13-15 l: llllllllllllllp
15-18 k: kkkkkkkkkkkkkkkkkk
2-4 g: ggjgl
3-7 g: xpnjmsgtgqmxn
1-2 k: kcgktft
9-10 j: jjjjjjjqjjj
2-7 b: fbbbbbbbbthbwc
3-7 j: phpptgrjppxw
8-9 m: qrgmtmbqhrx
8-10 l: hldllllzblllllvd
11-18 b: bmbbbtnwtbpbhdfwzz
1-5 h: hthbhsplh
2-6 g: wxgtvtcznqf
4-5 s: sssss
2-3 f: ffffff
3-4 k: krtm
2-7 q: qqlbcqqq
4-5 f: fffffwnh
6-8 k: lkwkkpkk
11-12 t: kchhtptngttttgtl
18-19 m: mmmmmmzmmmfmmmmmmscm
8-10 n: znsnmrnrnnmf
1-12 v: vdjkjhvwbbbrnz
1-2 k: rkjsrzkckvkbzzd
5-6 d: dwdddzd
7-8 d: ddddwddddj
8-9 w: wwwwwwwxww""".split('\n')

count_good = 0
count_bad = 0
for line in input:
    policy, password = line.split(": ")
    nums, char = policy.split()
    low, high = [int(x) for x in nums.split("-")]

    count = password.count(char) 
for line in input:
    policy, password = line.split(": ")
    nums, char = policy.split()
    low, high = [int(x) for x in nums.split("-")]

    count = password.count(char) 

    if low <= count <= high:
        count_good += 1
    else:
        count_bad += 1

print("Day 2 Part 1:", count_good)

count_good, count_bad = 0, 0
for line in input:
    policy, password = line.split(": ")
    nums, char = policy.split()
    low, high = [int(x) for x in nums.split("-")]

    count = password.count(char) 

    if password[low-1] == char and password[high-1] != char:
        count_good += 1
    elif password[low-1] != char and password[high-1] == char:
        count_good += 1
    else:
        count_bad += 1

print("Day 2 Part 2:", count_good)
