import re

test_input = """
1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc
"""

input = """
1-9 x: xwjgxtmrzxzmkx
4-6 r: rrrkrgr
4-5 v: vvfvvvn
5-16 m: pxmrtmbmqmcldmmm
15-16 s: bsshsszslssssslqdsss
10-12 g: gggggggggzgvg
2-7 n: dntnrng
11-14 j: xrjflbmjszzjbjjh
2-6 r: frxrrrfjnmr
6-7 h: hplhgcsphh
4-5 w: wwwwz
1-6 g: ggdggnggg
3-4 c: cccc
5-8 k: kjgmkkfwxkwqkkgfnv
14-15 h: xpwhdjhhjhrdjkhfh
6-7 g: vgggggdhgsp
1-3 r: rtdcrthphrkzxh
15-16 j: jjjjjjstjjjjhjjjjj
8-10 k: kkkkpkkqkv
1-4 s: sssssj
2-3 d: hdbmbpswddwkkr
6-7 s: ssscssnss
8-9 z: zzzzzzzftz
7-8 t: glwvkgtn
3-10 n: nnnnnnnnnnn
5-7 z: lzzzzfhj
8-9 l: llllllltn
1-2 p: dpcppp
2-5 d: hcfdltbgt
13-16 r: rrdrrqrrrrrsbrrr
7-16 l: lllltllllllllllllrll
9-14 z: vzzzpzfzdzzzzzzfczz
3-5 f: ffffb
6-8 s: csssssjrbdsgs
9-18 r: rrrrrrbrrrjzdrrrcrr
2-5 d: fdzxdj
13-14 c: cclcccccccccmc
9-10 z: zzvszszjbnzzz
5-9 s: ssqshwsss
4-11 x: hxxxxjvdxcqplp
4-6 t: mxtrtttttttttt
3-8 w: wmwwwnbmtw
5-6 x: xsczxd
2-7 w: pwvtgkwwwrpjr
7-9 w: wwwwwwwwj
3-9 h: hhhhbhhhschhh
1-4 p: tlwx
4-5 w: lhzjwwwwmv
6-7 p: ppppglprp
2-16 m: jqmmmmmzmmmmmjmbxmw
8-10 g: zhggpgrrlctggg
7-18 z: pltbcznlvtzgzczzchbz
10-11 t: jttttgtttttt
3-8 k: kkkkkkkkkkk
19-20 x: xxxxxxxxxxxxxxxxxxwr
9-16 l: llllllflllllxpllzl
10-12 m: mmjmmmmmmvms
1-4 c: cdxvxczcc
7-10 n: nnnnfnvpncn
10-17 z: zszzzrzczxzfzzzzlz
4-9 k: kkkdkkkkfk
12-13 m: mmgmmqfgmmtmm
4-6 s: tdmmcs
10-16 n: nkfpnncncnnntmtc
2-3 w: vwhwf
7-17 w: wwfwwwqhwwwwcwwww
5-8 q: tkqrtqqsqkwq
9-10 p: ptpppppppd
1-5 f: cnncnmnf
2-9 k: kkjdsnsqkgprtqb
9-11 n: nplnnnnnnnmnn
4-6 r: rrkrzrr
3-5 z: zzzzsq
17-18 r: rrrrrrrrrrrrrrrrrx
5-8 c: rcccdcclc
1-9 c: vcccccccbc
9-10 x: xxxxcbxxxm
2-5 c: cccfn
8-9 c: cccccnctc
4-8 l: flrhfzwllm
1-5 l: fllfllrklx
5-10 j: jrjkrjjjjxgjqj
5-10 v: dsxvmvvjtsc
4-6 v: bsqvdghvnzdfvjcfvvv
6-11 m: mmmmmmmmmmpm
6-9 q: qqgqkcccsgqqjspj
2-5 n: nvsrc
14-15 n: nnnnnnnnnnnbnms
3-4 m: mmbm
3-11 h: hhbhhhhhhhhhhhhhhhh
7-9 k: kkkkbknkjv
11-15 g: ggvgggfgbgvvzjgxghgg
3-4 z: zzzz
2-5 w: wwwhww
9-14 j: jjjjjjjjtjjjjw
2-4 j: jjbljsj
6-9 w: bwtkbttwqvwk
1-3 l: lllpjl
9-10 g: ggfmggggsrggggg
3-5 t: ttwzxl
5-7 k: kkwtbckkk
9-11 r: rbgrrhrrrrrr
9-12 g: ggggggsggglnggg
1-5 b: bbbwjs
6-7 m: xkjmdmm
6-8 g: gggggwgw
12-15 v: vrvvvqvvpvzvvvvrhqv
15-17 s: hsnjsrsdxpjswsxsss
9-12 r: rnhnrrsrrrrr
1-3 d: ddnd
1-11 m: mmtxkcdrvcmx
1-18 k: kxkkkskkkkkktkkmkc
5-9 h: vfxhhshhvhhbhr
2-3 k: wtrcckttcqrj
2-7 q: wnqcqqxw
1-9 s: sqsssslsssssssssss
4-6 p: mwvpppzp
1-4 v: qlvnvv
10-11 z: lzzzzzzzznt
2-14 q: qwqqqqqqqqqqqfqqr
15-20 d: dddddzddddddddlddddt
11-15 m: fvsqwbnqmbnmgcm
3-4 c: fncnfdjzcxwbpcrn
4-7 z: jsxzzszzqtwzmcznfs
5-6 x: glxxxxrxfxxwl
5-13 b: pdbvhwjwnbdwbrbbjwf
7-8 h: hhthhhvvt
8-11 f: pfffffxffpbf
5-6 n: ndtlxnnnqdmcnv
10-12 s: sssssswssdshssss
15-16 s: ssssssssssqsssss
4-5 s: sssss
3-4 g: ggggg
3-4 c: ccjv
7-12 v: rrrngfwhslsbpvbmwnn
4-10 n: nxnbnnnbxnnn
7-15 d: fggdddpgslqgdwhdndw
6-10 h: hhzzghhfdchhjnm
8-9 c: cccccccnc
9-10 h: hhhhhhhhll
2-16 w: nwfwwwzwvrbmwwww
10-13 k: kkkksjkkskqtkkmkknks
4-9 f: fffwfffbkc
4-11 v: gcfkvvvvfvv
2-5 l: llflftlmlglc
7-10 l: llldljllgsbl
10-19 g: svcsnlshppvrxzghhzg
3-8 d: dddwdzvmddd
3-5 m: kpmmjpmmmdz
13-14 n: nnnnnnnnnnnnns
3-8 b: bkbbbbbbbbbbbbbd
2-4 g: jghfggh
8-11 m: mmmmmmrmmmm
9-12 j: pbjjpjnjxjjfsjzsjps
6-7 r: rrrrrrrr
8-13 v: vvvvvvvbbvvvvvw
4-17 p: tpppppprzpspbpplppr
2-3 h: wbhhzxhllh
2-15 c: nvbcckcpccrtccwccsc
12-13 j: jjjjjjjjjjjzhj
4-10 p: dznzpnxzppl
5-8 r: jrrrsrrrrr
7-10 q: gjqjcqqqqsqfqqq
8-12 k: kkkkkkkkkkkg
3-14 m: mmtmmmmmmmmmmmmmm
3-12 t: khgttqtcltshttwqgt
14-15 b: bbbbbbbbbbbbbqb
14-15 f: fffqfmffpnffffg
5-16 j: jlghwmmrbdvdfjbj
7-8 v: vvkbvvrv
2-11 m: qmcgxcshgwmfm
11-12 m: cmmmzfmcmmzmmmmjmr
6-7 n: hnnbnnnw
4-8 m: mvdtmstm
4-7 m: bcrmmjbpmmmsdnrmm
1-4 w: wwwww
12-14 j: jjjjjjjjjjjrjhj
2-9 h: ghhczbhblx
2-11 v: vmvvvvvggvjpvchvvpc
6-7 f: ffwfflghpwfl
3-14 k: krkmjkgkzcckjbkkk
1-2 c: cfcp
15-17 z: ztzzzdzzzzzzzzzzt
4-13 p: bmrpdwphzqvppktz
4-5 j: jjvjtj
14-20 h: hvchvhhhhbhthlhhhhhh
1-3 j: kqjp
9-13 x: fsxxxkxxbpkxmhlrdtfx
13-14 w: wwpxwwwwwwgtwwcwwww
2-5 p: wppxkq
13-15 x: xxxzxxxbxxxxxxvxs
5-11 q: qvqqqqxqqqqfqqq
8-12 q: qqqqqqqvqqqq
8-10 m: mmmmmmmjmn
17-18 t: ttttrttttsttttttttt
9-13 h: hhhhhqhjlvhhqhhwh
8-9 s: ssssshsst
9-10 v: qvvtvsvcmzvvnpgvv
7-12 d: djcpndppsdddfdsdd
2-3 z: dgzwvbrzzbgw
1-4 k: kwkl
1-9 d: dkdmdsdwdzvlpv
10-11 h: hhhhhhhhhhh
9-10 f: ffffffffff
4-7 d: ssddddxp
18-19 j: jjjjjjjjjjjjjjjjjsj
7-11 m: mkmmrmmlrzsmgm
1-7 k: kkkkkkknk
4-5 w: wwwwj
6-13 s: xslmsfgsssssmslsstqd
4-5 z: zzzch
9-11 j: jjjjjjjjjjj
4-7 h: hjhhkdh
5-14 v: vvvvglvvdvvvvv
5-6 q: shqnjdqqq
1-5 q: dqqqq
5-7 z: zzznzzz
5-9 s: vwsfsxssd
4-5 f: sffffv
5-7 b: xllbbdb
1-14 j: rtzjqkpnkjlrhjcjqj
8-10 w: wwwwwwwfwxz
3-6 g: sggtlggswf
11-14 n: nnbnnncnnsgnnmknn
6-15 c: cclcnccctcrcxqmd
5-8 l: lmllxwpl
4-11 p: pppppppcpkdp
1-4 w: zwwx
1-3 g: nlfpgfzqkzn
11-12 w: vbwwgwvwrwlwwmwwwjw
4-12 j: vzfjgjrkzdrxqfh
1-2 r: frrq
1-4 k: vkkkkk
11-13 d: pndlftgdpdhld
1-4 r: prrvrrrrfrrrrr
8-9 m: fmmxmmmmmmm
1-2 x: xcpxc
4-16 n: rhbndvjnnsnfnwnnm
2-10 g: fkzwxtqmgm
11-19 p: bpppqpppppplpppphpsr
9-13 g: ggggthggggpjgqgslggq
4-5 m: mzmmxcfwmdpz
2-13 t: tttttttptttts
3-7 q: qqvqqqcqq
6-9 j: jsjjjjccjwjcjjj
7-10 r: rdlrrrrrrr
9-12 r: wrrzsrcrgcbrhqvrhlp
6-7 j: jjxjjzhxj
6-7 m: mmmmmmmm
1-3 m: mldvdmxmbk
10-11 f: ffffnffffkqf
5-17 f: ffffsfffftfffkffn
4-5 b: fbwbhvx
14-16 g: ggggggggthgggggsvd
2-3 s: cvsbw
5-10 g: qltgnfghgcrgpnzdsvng
5-6 p: ppjbpnppxg
3-8 j: lgjrzwdvdnwvrnj
2-4 c: cdcc
6-7 l: llflrhlllgklh
1-2 p: tppp
16-17 g: gggggggvggggggggg
3-14 f: fhfdffftfbggpkfgf
16-18 b: bbbbbbbbbbbbbbbbbbbb
5-10 v: thqvvkvlwvdvjzzst
13-14 p: ppppppppppppptc
11-14 t: tkttczttttsttmcnltm
3-4 w: nvxl
4-6 f: fpflfwftk
4-6 h: xhhhhh
15-17 t: tttttttttttttttlv
10-17 j: jjjjjjjjjsjjjjjjd
2-4 s: jcgs
7-9 q: qsqqjhqndsqkqqpvqqr
2-3 p: tnpplcmdpfn
2-5 c: crvmk
1-7 d: tsmzcgddnddddrdxsq
8-9 c: rlfcpctpncv
6-9 f: tkzfhffdf
13-15 s: sssmsscfvsssdsg
6-8 s: ssjsssjrscsss
7-10 f: fffffffkfff
1-6 k: jqtdhpknkkk
11-12 t: tttttttttttf
9-16 d: swjbddfpfbntmprdd
18-19 v: dvvvvvvvvvvvvvvvkvvv
2-5 j: kjjcqjj
11-12 d: dddddddcddld
14-16 f: fffffffffffffffk
4-7 x: nxxxxxxn
10-18 p: pppppppppppppppppr
8-9 k: ktkjkkkkfvklkz
9-15 h: hhhhhhhhchhhhhhhhh
18-19 v: hvkvvvvvvvvvvvvvvqc
1-8 s: xzbxgsxshgl
2-6 p: ppsjpglptchpzbdhj
6-7 n: nnnnnnnc
2-7 j: jhtjjjjj
11-12 b: vnblqbxkbbwb
4-5 z: czzzcztsz
4-9 x: wxpvxxxfxfxx
9-12 w: wwwwwwwwwgwwww
2-5 k: cntkkq
10-12 l: vljplljlllllllll
1-4 t: tfmvst
6-7 d: rddddddwd
2-6 h: bhvwhl
5-8 c: ccsgccncwgjtcbhccckk
5-6 r: rrrrmr
3-8 h: hcrhhjrbhh
2-4 s: xndshswk
2-7 m: mmrqmmlp
7-9 n: nnnbfpmnfnknxnndn
6-7 f: fvffffb
6-8 h: vhhhhhtk
6-7 j: jjjjjwjjs
1-5 r: rwrrrr
3-4 t: tlzk
2-7 k: kkkkkkk
6-11 q: rqqqqqwflqqjqq
5-7 l: llllglll
6-14 r: rrkrrxrmrrrrrc
1-8 w: lrwpzvhhcwtbrwwpwww
3-13 b: kbjhskpbrwqpbcbbkb
6-9 d: ddddbddhdddddddddmg
14-15 n: nnnnnnnntnnnnhf
2-18 k: cgjpktthdbfxrclqwzpl
5-14 w: wwwwwbfwzwcwcwz
5-7 s: tfhssgrsnbssfl
1-18 l: wdkwkdlslbllllgzfm
1-17 h: jhhhhhhhhhhhthhhhh
7-13 w: wwvwwwwwrwwww
1-3 r: rgrdrx
9-11 t: dnxckkwpttv
2-12 c: cgqxrszcckcd
4-13 q: qkchpbqqtrtdztrq
2-9 d: ddddsddddd
9-19 p: pppppgppppqpppppppp
8-9 l: lllhlllll
7-8 h: hhhhhkhvwbhmh
11-12 w: wwwwwwwwwwwnwwww
2-3 d: jhcd
13-16 n: nnnnnnnnnnnnndnnmnn
6-7 d: dllpddkdd
6-7 n: nnnnnkp
7-14 v: vvbcvrvvkmvvsv
5-7 j: jjjjcjs
4-10 l: ldllllllll
4-5 x: rxxxx
15-16 q: qqqqqqqqqqqlqqqw
13-15 m: mmmmmmmmmbmmzmbm
7-10 k: skkkkkkkkq
9-15 m: mghxpjzqdhjcbmdl
2-4 t: ttsnwzbdj
6-7 s: hqtkgtr
3-4 n: twpknn
1-3 l: wrldlsdl
5-6 l: qlxncf
4-5 s: dvsxs
7-9 t: rktsrfwttttgwtzgft
1-3 l: flsf
6-10 c: cchczccccj
1-3 k: bktw
2-4 h: zdqxgrfkfhljhqhkgmfc
16-17 s: sssssssssssssssvs
4-8 p: plpfmnhsppnpwnx
5-10 k: kkkkknkqkk
4-11 s: nsqnssssvqsm
6-14 j: jjjzjwczkjjjxjjcjjxj
3-7 t: tnnbjjhtd
7-8 l: llllllll
4-11 z: cwsvrtszxrgh
2-11 x: sxcxxxjxrxkxdxx
11-15 m: mmxmbxmmdmmmmfmmfmm
10-13 l: tllllwzlzlrbllllhnp
5-6 k: kkkjkmkkkg
4-7 f: wqqfmffffkp
1-9 b: bbbbbmbbbbhbbdzbbtn
10-12 h: hhhhdwbhhqrhhhdnxhr
1-8 r: qfpnfrrrrz
16-20 b: bbbbbbbbbbbbbbbbbbbb
1-5 c: hwqccmwcctcnclcb
6-13 c: clccccqqcccjczpgj
13-14 j: jjjjjjjjjjjjjh
2-4 j: jkfp
2-7 d: qqxdcdjqg
5-6 r: prrrrd
7-8 l: llllllll
2-3 w: nwlm
9-12 v: vnknxncvgvrww
6-16 s: sjnwfsksnszcglxs
5-17 z: zzmkzzzzzntzjzbwpdjz
12-17 j: ljjjjjjhjjwtjjjjdjwj
8-10 s: dnnjlfkxls
2-6 m: jmmqmdkjm
9-11 m: mmmcmmmfsmmm
14-16 p: ppppptpppphrpxpppp
4-15 d: dfkfxdddldddddddlddp
12-14 q: qqqqqqqqqqqwwgq
1-6 g: tgggggmggggdg
10-18 w: wwwwwwwwwbwjwwwwwt
8-9 t: ttkttcttsrgrzlftpt
3-5 j: jjjjjjjjjjjjjl
17-18 c: ccccccczcccccccccs
4-9 d: hjddddddddm
2-4 x: lxjfp
11-12 v: vvvvvvvvvvjv
1-4 z: fmzblzvzm
4-5 h: hhshhh
3-6 t: ptvrtt
7-15 k: kkkjzkckgckskpkk
12-15 w: wwwwwwwwwwwftwdw
3-5 z: jrhns
5-6 n: pxmnzn
1-3 b: bbbkbbbbbbwb
1-10 r: rrjrqrrwrrrqv
11-12 w: wwwwwwwwwwwwwww
5-6 j: jsjjjp
6-11 h: lhbbvmhwrhh
18-19 q: qqqqqqqcxqqqqqqqqxwq
17-18 l: llllllllllllllllxql
3-4 j: jjljjn
8-10 z: zzzzwnzlzggz
6-7 t: tttttft
11-12 f: ffffffffffnf
2-8 b: hqbbbbbsbb
4-5 w: stljwbxpw
1-2 z: grxfpw
6-8 w: wwwwpwwxw
8-14 z: zqzzzzzvzzzzzzgz
4-11 b: cckgrcmbpvbbw
2-9 d: xqxbdddjds
3-6 x: xxrxxx
15-16 n: nnnnnnnnnnnnnndnn
6-11 x: lqmxxxsxxfxxxxlx
1-12 s: vssssshssmsk
1-16 m: bmgkkmwmmzvmmmmmwflv
3-15 t: thkvttsltnbgztt
9-17 z: zzzzzzzzzzzzzzzzzz
4-6 f: fjwfff
3-9 d: ddddddddd
6-10 k: kjkbkkckxkknqkkdc
6-7 n: nsnckwnmn
7-13 t: ptbtjqttwwtftpntdq
7-10 r: wrhhrrrrrwrrrrvqrms
2-3 c: zcrwhtccb
5-7 m: nnwmmdmmmccv
3-5 j: rtjjmjrjl
5-6 s: dssjhsdmbksrks
16-18 c: ccccclcccclccccccc
7-16 b: qpzgqxdbssmzptrv
6-8 b: bnsbbgdbggxbbszbm
1-10 h: lrpstqvhhhhf
4-6 s: tvssppwvss
3-4 g: qqqhcd
4-7 c: qxcqzccckxcpcxcw
1-13 m: nbwdmspmmwbbmm
1-2 j: xjrczrk
9-10 w: wwwwwwwwwd
2-4 h: hhhq
7-10 j: bjmrrjsjthjnnjjxjjd
3-7 f: srfwwfvf
3-4 b: nbbzb
3-5 n: nnnnn
7-8 f: fxfnfffzpqffgdf
10-12 k: kkpkkkpnkkmkjbkk
9-10 k: jkkkkkkkwqk
4-6 z: rzzzzs
4-7 v: vvvtvvjq
6-12 z: dzjnzczzpzgzzzx
6-8 s: smsvbkswslssrdfjsc
5-7 b: bwbbbbbbr
1-3 d: kddbsmmbv
3-4 b: bbbb
5-8 r: rqrrdrrr
7-8 m: mmmmmmzm
9-11 q: xvnlfvhxqfql
3-4 w: wfwj
1-3 q: gqqcqg
1-2 q: cqlxrq
6-12 s: swwjjssjsstmqfssdh
2-4 q: bqqq
5-6 c: ccccbscgfc
14-15 x: xxcxxxxxxxxxxxm
6-12 f: fzfchfnrxfrdffhfl
14-17 g: gggggggggggggjgpgg
5-8 n: njkcngznn
10-13 d: dddlqddddvddr
2-4 c: xgcg
2-10 s: sxsnsdmszwmsss
6-12 q: qbcqspqqqkqrq
6-16 n: xnnnnnnnnnnnnnnfnnn
6-12 s: tssnssmsssssssssnhr
1-4 v: vwvvv
8-10 h: rzmhhjvqhht
1-4 t: ttjdjftfctt
1-4 k: nkkz
1-2 q: vkvqkqq
9-19 n: qxmjqxnxnblqnnqfgsrd
15-16 h: hhhhhhhhhhhhhhghz
2-5 g: jggpxdgwjpsrv
12-13 c: xccccpccrcccc
1-13 g: nfgbghqrljstggcgq
14-17 g: gggggggggggggmggggg
4-14 s: sssbsssssssssgs
1-10 d: rcxvxcgddnhwd
4-14 g: vccvdldqdgzltq
8-10 z: zzdczzvrzzzzr
5-10 t: ctgtttftqtrbt
3-5 v: vvrvx
9-10 w: wwwwwwwwwwwww
4-6 c: hgccmcccc
16-18 s: ssssssssssstssscsh
2-7 z: zzflfrtdx
4-10 v: vvlsvvvvkrc
10-16 d: ddddwddddbdgdddwd
3-4 v: gkbqbtrv
3-4 h: cjdqvwhhththvx
3-5 b: bbbkbrb
3-5 m: ptkqdgsmbcmmblwp
4-17 q: mlqqgsqqqfqkcqqxqq
6-17 m: mdvqvmmxlmzmvmmdm
1-3 r: hrrtrrrrrrrrrwlr
3-5 j: jjjjhj
11-12 q: dqpqqqqqqnzlqq
8-11 d: dddnddnddtdddd
3-16 d: dpddxtlqsqldrpddq
7-13 z: szhzmmzzzzmzzzz
6-18 h: mkxxqtbnnjgnvxnhhhc
4-5 n: nknfrhpn
16-17 d: dddddddgdddddddddd
14-16 w: wwwwwwwwwwwwwwwww
2-3 t: rttfdstqpdtg
3-4 s: gghrfxbfshqssj
1-9 j: bjjjjjjjhjjj
1-2 p: xmpgppppppp
9-14 k: vqpxrkmskfpnxq
1-5 x: xxxxx
1-14 p: bsxnwvpkphdppphpkwp
5-12 d: xdddmzddfddc
9-10 v: gvvvvvgvhnvw
2-7 x: xxxxxwgsvmqnkxv
3-15 c: ccscccccwccccccc
5-8 w: nsvgwzdf
7-14 w: wwwwwwwwwwwfwswcw
5-10 r: qrrlwcrrwz
7-12 f: hfnphfpjffstff
2-6 h: hqjhmph
3-13 x: cpxxxzcrbjxxxb
4-8 k: kkkkktkkkkfkf
7-10 g: gggghghsgwf
8-9 s: sswswssggss
6-10 l: qlllljllhlll
8-11 c: cccwccrbcbccc
5-6 x: xxxxxxg
1-3 w: cwpww
8-11 v: vvvvvvvvvwvv
1-2 b: bbgl
7-10 b: zbkbcbbbsbb
13-15 t: tttttgtttttttktttt
12-14 x: xxxxxxxxxxxxxqf
6-7 k: kmrkkwmk
4-5 m: mmxjmdrhzkmxxphjmz
2-3 t: tnvtndw
4-5 x: xxtxxtxzf
1-3 m: nwmglfscmwrjtzp
10-11 c: cnccckcckcwdc
14-19 b: tvbmrqtchwblbqbbqbb
9-10 x: fxxxxxxxjxx
4-5 g: gggggkggx
8-12 k: kkkkkfkpkqkwkkk
2-6 v: chpvkvt
4-10 r: rmbjmcrgrrfrtmblhw
4-6 n: rnnwtn
3-10 v: htclcjhjkdv
10-13 w: wwwhhwwwrwwzww
18-20 w: wwwwwwjwwwwwwwwvwtww
7-8 w: phrwbwwmc
16-17 q: qqqqqqqqqqqqqqqqx
2-5 k: kzknsxkkgtvmwlfrmrg
3-4 b: zbbbb
5-8 v: hfclvvpc
3-15 t: ctfthpmgznjnhgtth
1-6 t: httttq
5-6 w: wwxhgww
3-5 m: fmtnmmm
11-17 n: xnnchnzpsmcslvzcn
5-6 m: mmmmcm
1-7 r: rwsgcgvjmtxwkqtr
6-16 m: mmmmmmmmmmmqmmmmmm
5-10 s: sssggssssjsssmsss
9-14 p: ppfppzppnvmpqdvpp
2-4 l: wclwrlrdvh
6-17 g: gggmkglggwgpgkmglt
5-7 z: zzzbzpz
4-5 q: qbqqlzpqg
10-19 h: hhhhhhhhhrhhqhhhhhhh
6-7 m: nfnxmsmhtmhsmmmmgmsl
2-3 m: mkfmmm
8-10 j: xrjdnjjjnjjcjjjjjj
3-6 x: xwrjxhjxx
6-7 z: zzzzzzzg
8-17 k: kkkkkkkkkkkkkkkkk
6-9 n: rnnxnnbwnsnnwn
6-8 m: mkmmmsmm
4-6 q: qqfxqqq
2-8 s: hxmfbkszk
6-7 r: rrrrrrr
2-5 h: hhqzhhhh
5-15 b: bhbvnrbrbblbbhh
12-13 d: ddddddtdddvhddd
5-6 f: fmfcfwf
4-7 j: njqfxjjjqjjvdj
6-9 g: fggkggzgghrv
9-12 b: vbblbxpfrbjbgpwxb
1-8 s: tzcdrktsqjsxssfsssh
10-14 f: fffffffffcffffffffff
13-17 p: pqpppppcpbwpppnprppk
16-17 n: nnnmnnnnnnnnnnnsj
10-16 k: kkkkkkkkkkkkkkktk
8-11 w: wwwwwwwwwwm
2-5 q: qqqqqq
2-7 m: mmmmmxg
2-9 m: mmvlggdmr
3-9 s: wxdbmlcrlpnzmkfdfs
12-16 z: zlxzgznqqfzsqtwc
6-7 f: flvmfffjffbmgfzfgfp
2-3 g: cgggqgxqgv
2-3 f: rffvf
1-8 h: vhhhhhhvhhvhhhhf
6-12 x: vzdxxxgxtxzxxxqc
4-5 w: rwwwwww
7-10 r: brwrcrrkcsj
6-10 q: jvqqqqqqqmq
5-18 v: lvhvvwvvvvvlvlvvmv
6-9 z: zzvzcwlzslhlzqsf
3-6 x: sdknfxvwtcfcjgmv
8-9 l: lqcwlllsllll
1-4 k: dgklv
2-6 q: qqqptfqqqqq
4-7 m: mrmcmmmm
4-5 r: rrrblg
1-8 c: qcccccvntc
6-7 m: mzbxmmmnhmqcmmqvbmcp
2-4 t: ptvqx
9-10 s: gpssssssgss
4-18 b: bbbbbbbbbbbbbbbbbfb
4-5 f: ffffgf
3-6 l: lslglw
1-5 l: ltzlllsdlmrllkvbztvr
15-19 l: llllllllllllllnllll
10-11 j: jjjjpjjjjjncj
2-3 w: wfwgd
1-7 r: vrrrzrr
3-7 k: kkkjckkkgkbtvm
9-12 k: kkkkkrckcrkk
1-6 b: hpbjbvb
6-8 s: ssssssvss
2-4 x: mpxk
6-10 x: xxxmrwhgxxxjx
7-8 x: xxphxxxxx
6-19 n: mdrlnnpnjndqgnkfwnnn
2-5 q: qjwtbmkhtnxm
15-17 j: xjjjjjbjqjjjjjjqjjjw
5-7 x: pxxxxsxxsxx
3-6 t: ttttrp
8-11 f: fffffffffrkzf
6-8 r: glsprkbp
10-12 m: mmmmmmmmmmmsm
13-14 z: zzszzzszzbzzzplzzz
19-20 c: ccccchwccccccccccncb
7-12 z: qzggglzlhshnrwt
12-14 z: zzzzzzzzhzzwzc
1-2 s: sssl
1-3 q: fsqmwq
1-6 z: zmzztzkzznmflqffz
9-11 b: bwbbjbbbtlbbn
4-6 s: nktszz
2-5 j: nqjhjkb
7-16 l: lrlllllllmllswlsl
2-3 f: fjqvfff
7-15 w: hwxghddqwwwwwww
2-4 z: zgzfx
5-6 h: vhhjhthh
13-14 h: hhhhhhfhhhhhhhphhhh
16-17 k: kkkkkkkkkkkkkkknx
7-15 l: dllllllmlllfllf
2-6 w: mtkwwwww
2-7 k: zpkkgldk
7-9 d: htmtjddddddqvddcd
4-9 v: rvfbbwzdwcvvqv
6-11 m: mmvmbvmmmsmmlmmm
3-8 p: xpxppsgpbxp
2-6 f: vffbszhvvrdfkxc
8-11 v: lvrrlvvqqvr
5-17 h: hdhhbhhzhhhhhhsbl
8-10 f: fhgffgfrfqtf
9-12 s: ssssfssdpssswf
9-12 m: mmmmmmmmpzgmmm
7-9 l: zlmllvwlllldl
8-11 m: mmdmfmmdxbmxbmm
1-4 m: fklssmffwzgqcvdpm
13-14 c: cczcccccccccccc
5-9 f: frtkfpffsfff
5-8 f: ffffgffr
3-8 m: mmxsmmmb
1-6 m: mdmmmm
1-2 h: hhdtmhwfpt
4-14 d: dmrkdvddmdsdddbsgd
6-7 c: cxccgcccc
6-12 v: xcqvjvvsdvvvpv
11-14 d: gltkjvddwjdkrln
2-13 f: ggffllflfbfffqkfmf
10-13 c: xkvcccccrmccccc
17-19 q: qqsqqqqqqqqqqqqqfqmq
8-10 t: ttttlttwtlt
4-5 f: wffrd
2-16 v: tvhvvqvrvvvvvvqvvf
2-4 c: cccc
3-8 z: zrzzpzlzzhsdxqqfx
6-10 k: kkkkkkkkkk
5-7 r: rvrrvrz
14-15 w: wwwwwwwlwwwwncwvwjk
6-11 q: qfhxqqgqqqsvcpr
4-7 f: kflfffzff
2-14 t: rtttttptlxsttt
11-15 t: ttttttttttftbvqttt
6-10 c: cckwlchltchcczgw
3-8 s: ssssvsqnss
1-8 h: mhhhhrhhh
13-15 b: bbbbbbbbbbbbbbnb
15-17 p: dpppppppppspppcps
5-12 l: xbfjglklphtl
2-4 v: vvvvbvwpvvvrv
3-5 k: plhjkkqkskz
6-12 z: zzzzzczzzzzk
2-3 j: xvjljj
6-7 r: rlrrrrrrzrrzrrr
1-12 t: mqrkgpktbsqxg
10-13 z: pzmzzxpnzxpgzzzhzz
5-13 s: gslsskvgxssssnpj
10-14 m: mmmmmmsmmmmmmk
2-5 b: tnbdsfwdzxrkjdb
2-15 h: hnxhzhmhhhhhwwb
1-4 c: ccccccc
9-10 b: bbbbbbbbbl
4-5 j: jsjjj
3-6 n: xmmnppbn
11-12 m: mmmmmmmmmmmm
2-4 r: jrgrcpvgctrrr
3-4 g: gggr
14-17 n: nhnpnnnnznnnnnnnknnm
4-5 k: krkkf
11-17 h: hhdhhhhhhhhghhkhx
5-19 q: dqbcqqqqsqqzqqqqqqv
5-16 t: ttrkttttstwttttqdt
11-18 h: dhhhhhhhhjhtjhhhhhh
5-8 c: ccccrccfc
1-3 v: nvvnv
7-12 m: prmmzmtmmmssdmmmmt
15-16 r: rrrrrrrrrrrrrqfr
7-19 b: djbbbbqjbdtbslbgbbmb
10-13 w: wwwwwwwwwwwwww
5-15 p: mbpcjqmmhpppkfmrbcww
2-4 n: nxbjknms
5-11 s: hxhcsldmxshdksvsss
12-16 q: qqqqqqqpqcdqqtwkqvq
2-7 j: tjlpcjjjjnj
6-7 s: ssssskm
1-4 t: tttttx
5-10 q: pqmnqrlqchbjzqqvq
11-15 q: qqqqqqqqqqhqrqqrqq
3-5 k: jhkgkxkqfskg
14-15 f: ffvffmfffffffsffqm
4-5 x: xxfxhfxx
2-4 b: ktbv
3-4 t: wjtwxvxctrcttb
1-3 s: shssg
8-12 z: skkzbdpzdkzzz
1-3 f: rlfffqft
5-8 s: fsrcnjsgsmgs
7-17 v: vvvvvvvvvvvvvvvvvvv
4-5 k: kklmq
8-17 h: hhhhhlvghwkhrfzhxh
17-18 n: nnnnnnnnnnnnnnnnnn
3-10 h: mhhhhrhznwvhh
8-9 x: xmxxxxxxx
4-5 p: ppppk
11-13 t: tttttttttttjtcn
3-4 q: qqvhz
3-8 l: gbpqclnkwlhdlml
12-13 f: fffffffffffrf
3-11 s: ssjssssssslssss
6-7 b: bbbbbwbb
7-9 r: krrrrrfrj
13-14 b: bbbbbbbbbvbbbp
2-4 x: ltgbx
7-10 r: smrrrrkjrrr
3-7 n: vnqpngjdgrw
7-18 t: ttltqtsktrjgxtqhtt
2-5 v: dvvxbvvvnk
2-5 n: nnnnnpn
1-3 t: nttmtx
3-4 z: zpszz
1-12 p: pmpxphlpppppppqppp
3-4 v: qvvvvvv
9-12 g: gwgggggggtgqgg
2-4 n: knpn
3-13 d: hncbdrvpddddcfddd
5-9 s: ssnspslslsfkpskss
1-2 s: ssczgkvtlp
5-6 p: pmvpzpppkm
1-4 j: jjhr
5-6 s: ssssxl
1-3 t: ttrt
16-18 n: nnpnnnnnnnnnnnnnnnn
4-5 n: nnfnl
1-4 b: bbbb
7-8 l: nljlllkhl
11-12 n: nnnnnsnnnnnnnpn
5-10 k: kkkkckkkkhkkkkk
7-10 s: zfsssfldxsvqsxdsqs
5-6 q: qqqqqp
6-7 q: qqqqqqq
14-16 w: wwdhmwwjwwwwnwwlwwwv
8-9 l: llllllldll
12-14 c: ccrccccccccrcccccccc
1-3 n: qnwnh
1-4 l: mlll
1-3 s: sssssss
4-15 h: mhclhhhjllhhhgh
15-16 x: xxxxxxtxxxxxtxttxx
2-4 r: rmjh
6-9 z: zzzzzpszt
17-18 n: nnwnnnnnnnnnnnnnppnn
8-11 v: vmvmvlvbvvvvv
7-8 b: bbbbbbdf
2-5 k: kkdkk
8-9 d: dddsldddvxlhd
7-8 h: hhhhkhxshxhn
12-14 c: vcchpxcnmgkctpqcc
1-5 w: wwwwww
1-2 x: xdmk
1-9 p: pbfvrdpqqn
2-4 s: mtnvzhnzs
4-6 t: cttxvtttx
4-8 t: qttmtzttkwftrjk
7-9 c: cccccccccc
2-18 j: zjjqxjfqqlmjrjhjqx
2-5 q: qmkqgq
5-11 k: kkkkkkslzkkkkkrx
16-18 h: hhhhhhhhhqhthhhvhh
5-13 h: hhfhhhhhmhhshhhhhhh
10-12 r: rkrrrrrmrrrrrr
8-10 n: rnnckhmjnxmfggsgtnnn
19-20 c: qsccznccccccnccccccq
1-4 k: wtkck
7-8 s: sssmssjssss
3-5 l: llslv
3-7 t: tvgjqgjbvtgpkt
13-15 b: bbbbbbbbqbblrbbb
9-10 z: zzzzzznzzb
6-16 c: kpcnsccgccxfwccl
2-3 d: ddbd
10-16 v: vvvvqrvvsvvvvvvl
3-12 d: dzdxxhddnlkddddk
8-9 b: khbbbfbbbbb
11-12 z: zzzzzzzzzzzz
5-15 n: bnlvnnrjbnqlnnn
1-2 q: mqqpzjc
11-13 h: hhhhhhchhhhjhh
8-11 x: nxfcxbjqxdlcxxxkxxx
14-18 v: vvbqvvvvvvvvvvvvvvvv
7-8 f: pgtlfffmjffnt
10-18 m: mnkrmmmmmqmmmmmmmjm
1-4 l: lghlhcnwprlgvw
3-4 p: npxplpwl
12-15 s: sfkwnvsssvssssfsssrp
3-7 z: ztqnzlxjmzzbjfnxcw
17-18 q: qqqqqqqqqqqqqqqqqq
3-6 z: jczztzzbhmzzw
3-7 f: skffttjffqfnchfrf
4-6 m: hmqmcrmw
10-11 t: dftttqttttttl
7-13 p: spxnpgtzpppjpwppptp
8-9 q: jqxqqqqxqq
3-4 h: hhhh
10-13 z: pgzxhxxpzzssj
5-9 x: xfrdmjxmrxrqjpxbfxxx
8-17 d: ddpddddddddsgddzddn
1-4 g: vggdggggggggggggggg
10-12 m: mmdqsmwvjjmv
2-7 s: ssqsssk
13-14 n: nnvnnnnnnnnnsgnn
2-16 k: kkkkkkkkkkknkkkk
3-6 p: dprphc
2-10 k: mpkstkxkdb
2-3 s: ssxs
9-19 t: ttjttjttrtsqtmttttt
4-5 j: jrjjtsjjd
6-7 x: xxxpxjx
13-15 q: fqfqqqqhqcqfqqbqqq
1-3 z: zfgrzl
6-8 n: nnnnnphm
1-8 b: bbbbbbbbb
4-5 h: thhgj
4-8 v: vvvcvvvp
8-9 t: ktttttttt
3-4 f: wftbcfnmhkfdpjbns
6-7 v: vvvvvlv
16-17 z: zzzzhfzzzzzzkzzzwzzz
1-2 q: qqqfq
10-11 p: zpjzcppvcppppppppj
10-15 c: vlccbcgcclcczfcfcc
11-17 t: tsntktwzhsfttfwtx
1-7 h: nhhhhhb
6-13 b: bbbphnbbwbbbb
8-9 x: xgxxxlxfxx
14-16 m: mmmmmmmmmmmmmmmm
3-4 x: xxbxx
6-9 c: xkccsfccrccv
10-18 h: jphhbshwghrxpnhnlhxh
6-10 f: nlxbgvftfh
3-4 p: ppwf
1-6 s: kjwjwshcnqwxgwslvl
2-3 m: mmlk
2-3 g: gmgg
3-6 r: rrrvrmr
1-6 s: szgpksczqd
12-14 t: ttttttpjvtqwtltt
1-2 r: hrrrrvrrzj
1-13 m: xmmmmmsmmmcsnmmmmfmm
10-11 f: fffffffffsf
13-15 d: ddddddddddddhdq
7-14 k: jkkkkkkkrkmkkkk
6-9 g: ggggggggg
14-16 l: lllllllvlllllwtx
1-3 g: ggggt
3-4 m: mmkd
5-10 g: jgsgvggwggj
17-18 p: ppppppppppppppphpp
1-2 q: qqjwhq
2-6 q: qqgqqzk
11-16 t: ttwttttttctttthgt
1-5 m: zmmmsm
12-16 r: rrrrrrrrrqrgrrrj
4-5 v: xcvvghvrczpcgn
1-3 x: xbfmxxfxxf
3-5 j: hjbjm
5-14 l: lllltlllllqllll
3-4 x: xsxnxgtx
6-18 g: gggggggggggggggggd
8-12 t: tgttttqtcttttt
4-6 p: pppppd
6-7 x: xxxxxxx
3-4 c: fdcclrccccvg
11-12 v: vnvvvvzdvcrk
1-9 z: zztzqzzzzcz
1-12 v: vmvvvvvvvvvmvvvv
9-16 v: vvvvvvvvvvvvvvvf
2-7 h: xhtsfmvthhhrhdhhbbc
5-6 c: qkccccd
8-12 z: zzzzzzzjzzhbzz
2-4 n: shlnnkxn
19-20 v: vvvvvvvvvvvvvvvvvvcv
7-8 h: hhkhhhkhh
5-19 p: sxslgwvkszswqxtqpvf
5-8 m: mmmmmrmbm
2-5 j: jrnjjzjfhjdkjqjtkwk
7-13 f: ffffffsfffffwfff
6-9 w: wmwwdwwwsz
12-15 f: nsffpfsdsjsfsffk
13-16 k: kkkkkkkkkkkkkkhw
6-17 s: ssssslssssssssssss
3-5 c: srdscnncclqqcncsw
9-11 p: pkppppppppp
5-10 q: qqqqqqqqqpqq
12-14 n: nnnnnnnnnnnnnn
6-11 h: hhhhhqhhhhhvhhhh
2-12 f: fgfrpzcstfffffxff
2-12 n: nnxmnmnnnnknrpmnv
6-7 m: jmmmmcnpkm
4-6 v: mvkcwvmvvjvrvlv
18-20 h: hhrmbrhhhhlhhvhmhhhb
9-13 g: ggggggzgggsgfgxg
9-15 m: pmmxmmmmmmmmmmm
1-7 l: zlmsmlxpvvlzv
2-15 g: sslggkdglqgxpgkx
17-18 c: ccccccccccccccccmc
10-11 w: wwwwwpcwwwpwwd
3-5 w: wwwwk
8-9 f: vfbvffsfcf
4-6 r: rrrrrr
2-4 n: nrnknn
1-4 l: lxllllll
10-11 f: qdfwvfffdfvwffgfkfgf
3-4 b: xgxbdqxbfvzrl
2-8 b: pbbkbbgbxr
1-2 d: ddxdnv
4-8 d: dndfcnhd
"""

def run(input, part=1):
    passwords = input.strip().splitlines()
    PW = re.compile(r"(\d+)-(\d+) (.): (.*)")
    good = 0
    for password in passwords:
        m = PW.match(password)
        if not m:
            print(f"Could not parse: {password}")
            return
        l, h, letter, pw = m.groups()
        l, h = int(l), int(h)
        if matches(l, h, letter, pw, part):
            good += 1
    return good

def matches(l, h, letter, pw, part):
    if part == 1:
        return l <= pw.count(letter) <= h
    elif part == 2:
        return ((pw[l-1] == letter) + (pw[h-1] == letter)) == 1
    else:
        raise ValueError("Bad part (must be 1 or 2)")

print("Part 1")
print("Test input")
print(run(test_input))
print("Puzzle Input")
print(run(input))


print("Part 2")
print("Test input")
print(run(test_input, part=2))
print("Puzzle Input")
print(run(input, part=2))
