4.R

input <- "
SXMSMMXMASMSSSSXAMXMXAMXXAAXMAMSAMMXMAMXSAMXMXMMMMSMMXMXMASMMSMMSSSMAXXMSMSSXMASMXSSSXSMMSSSSSXMASXSAMXSMMSSMXXXXXMASXMXMSSSMMSSMSSSMMMMSSXM
SAMAMSMSMSXAAMAAXMSXMSSSXSXMSMMSASASXSMSMSSMSSMXAAMXMASXSAAMAXASAXMASXSASMASMMSMMAMXSAAXAAXAAAASAMAXAXASAAAAMMSMMSMMMASASAMXSAAAAMASMAASMMAS
SAMXSAAXAMMMMMMXAXSAMMAMAMXMAAXSXMASAAMSXAXAAAXSMSSSSXSAMXMMASMMMSXAMSAAXMAMMMAAMASAMXMMMSSMMMMMASMXMMXSMMSXMAAAAAAAXMASMASAMMSMMMAMMMXMAMAM
SAMXSMSMAMAAXSXSSXSAMMAMAMASXSMSXXXMMMMSMMSMMXMSAAAMXXMXMXXMXXXASAMXMSMSMMXXAXXXMAXAMSXXAAMXSAASMMMSXAAXMAXMSMSMMSXMXMMMSXMXSXMMMMXSXSMSSMMS
MSSXMAXMASMSSMAXMAMXMMASAXMXAMAMXMMMXMXMAMXXAXSMMMSMXMMAMMXMAMSMMMSSXSAXMSASXXSXMSSMMSAMMMSAMMMMAAAAMMMSSXMAMAAAAMMSXXAAXXSASAAAXMASAAAAMAXA
XAXASMXSAMAMAMMMMAMASMMMMSXMSMSMSAASXSXSAMAMSMSAXSAMXAAAXMAMAMAAMAAMAMAMAMASAASAMAAXAXAMASMMSSSSSMMSAMAAMAMAMSSMMSAMMSMXXMMASMSMMSAMXMMMSMMM
MMSMMMAMMSXSAMAASAMXMAAAXMAXMAXAMSMSAMASXSXAMASMMXAAXXXMXMMMASMSMMSSSMSMSMAMMMMAAXXMXMMMXMAAAAXAAMAMMMMASMMXXAAAAMAMMAMXMXAAMXMAAMXSASXMAXAX
XAAAAMMSAAASXMSASASXSSMMSMMMSAMSAMXMAMAMMAMSMAMMXSXMSMSASXMSXSAMXMAXMAXXXAXXXASXMASMXSAMSSMMSXMXMMAXXASAMAASMSSMMSSMMASAASMXSAMMMSMSXSASASXS
MSSMMSMMMMMMMMMAXAMAAXMASASASXMXMAMSAMXXSAMXMAMMXSMAAAMSMAASAMXMSXMXMAMSSMMMSASMMXXAASXMAAAMAAMSXSSSMMMSMMMSXAXXXAAXSAXAXMAASXSAMXAXXSAMXSAS
XAAASXXAAMAAXAMSMMMXMMMMXAMAXAMXAMMSXSXMXSSXSAXXASMMMSMAMMMMAMMAMXXXMASXMAAXMAXASMMMMSAMSSMMMXMAAAMAAMAMMMSMMMSMMMSAMAXSAMXMSAXXSMMMAXAMAMMM
MMSMSAXSSSMMMMAXAXMASAXSMSMXSAMXXXAMMMMMAMMMSMSMASXMXMMMMAXSMMSASMSSSXMASXMXMMMAXMAMSSMMMAMXXSSSSMSSMMASAMAAAAAAAAMMMXMAASAXMXXMXMASMMSMMSAS
AXAXMAMMAXAXAMSMSMMAXMXSAXAMSAMXMMMSAAAMAMSAMXAMAXASXMASMMMMMASAMAXAAXSMMMXAAXMXMMMSAMASXAAAAAAAXAXXASASMSSSMSSXMXSXXXMXAMXXSSMMAMMAXSMAXXMA
XSASMMMMAMMSXSAAMAASXSASXMAMMSMASAMXMXXXAXMASXXSSSMMXMASAAXAMMXXMSMMMMMAAAXSXXMSASXMASXMSAMMMMMMMMMSMMXSXXXMAXMMSMSMSMSAMASXSAAAASMMMAMMMSXM
XSAMMAXMMMMSMSMSMSMMAMASASXMAAXXMASAXXSMSSSMMAXAAMAAXXASMMSSSSMSAMASAAXMMMMMAAAAMMASXMXMAXXXAAAMXSASAXMMMSSMXMAXSASAAAXXSAMXMSMMXMAASAMSASAX
AMAMSXSXMASMAMAMMMAMMMXMXAMMXSSMXXMAMSAMXAAMASMMSMSASMXXAASXAAASASAMSSSSSXASMMXMASAMASMMMAMXSSXSAMXSAMSAMXAMASMMMAMSXSXXMAXAXMMSMXSMMMMASXSM
AMMMXAMASMMMAMAMSSMMXSASXMMSAMAMAMMMMXAMMXMAAXMXXAMXXAXXMMSMSMMSAMAXXXAAAMXAXMXMAMASAAAAAAMXMMXMMMXMMMSASXMMXAAAMXMXXMMMSSMMASAAMMMMASMMMMMM
MSSMSAAAXAASMSMSXAXMMSASAAAMASMMASAMMSMMMXXMSSSMMAMXMSMXSAMMASMMMMSSMMMMMXXSXXAMAXAMXSSMSMSAAAXMAMXAMXXMAAXAMSMSXMXMSMAMAMAMAMMMXAASAXMXXAAM
MAAXSAMXMSMSAMXSMXMXAMAMMMXMMMXSMSASAAMAMAXXAAAMSAMAMAAMMAMSAMMAAAXAAAXAXMMMMMMMSXMMAAAAAASMSMSMAMSAMXMXSSMXAMAMMMAXAXAXXXAMASXXSSMMMSSMSSMS
MMSMSXMAMXMMXMAMMSMMXXAMXXSSXSASASAMMXSAMSSMMSMMSMSMSASXXAMMMMSXMXSSSMSMSMAAAASMMASMMSAMMMMAMAMXXXASMMSAAAASMMAMAXSSSXSSMMASASMXAXAAAAAAAAAS
MMAAXAMXXSAMXSSMASMAMXSXSSMASXAMMMMMXMXAMAAXXAXXSXSASAMMMSSMMASMMMXAXXAAAMMMSASAXXMAAAAXMXMAMAMMMSMMXAMMSMMAAMMXSMMAXAMAMSAMAXAMMXSMMXSSMMMS
MSMSMMSAMXAMAMAMAXMASMMAMXMXMMSMSAMSXMSSMSSMMSXXMAMAMAMSAAAXMASASMMAMSMSMSMAMXSAMSMSMSSMSASASASAAXXXMMMMAAMSMMSAMASAMXMAMXMMXMSXSAXMAXMAMMAX
AAXXAAXAXMAMXXAMXXMASAMSMMMSMAXMMAMMAMAMMXAMAXSMMSMSMXMMMSSMXXSAMXMAMXAAAAAMXAMMMAAXAAXASXSAXXSMSMMXMXSSMSXAAAMASMMMSXMAMAXMXXXAAXSXMASAAMAM
SXXMMMSXMMSXMSSSMMMASXXAAAAAMAMMMSMXAMASMXAMXMASAAXMSMXMAXAAXMMMMASAMMSMSMSSMAXMXMXMMMMAMMMMMMXMXASAMAMAAXMMMMSAMMASAASASXSXSAMMMSMMXXMAMMAS
AMSXSAMXSAMXAAAMAMSXMASXXMMSXSAAAXASMSXAMMXXAAXMXSMMAXMXMSMSMXAXSXSASAAAAXAXMAMSMSMXMMXXXAAAXXAMXSMXSASMMMXXAXSXAMMXMAMXAAAAXAAXXXMASMXSAMAM
XMAXMASAMASXMMSMSMSASXXMASXMAMMMMSASAAAMXASXMSMSMMASMMMAMMAMASAMMASAMXSSMMMSMSXSAAAASAMXSMSSMSASMAAASXSAMAMSMMMXSSSSXSMSMMMMMXSMXMMASAAAAMXS
SAMXSAMXSMMXMAXXXASXMXAMXSAMAMXXXMXMXMMXMMAAAAAAASAMXMSASMAMXXXAMMSMMAMAMXXAMMAMSMMMSAAMMMMAMSAAXMMMSASXMAMAAAXAXAAMAAXAXMAXSXMMSAMXMMMMXMXM
MAXAMASXSAMXSASXMAMXSXMAMMAMMMXMMXXXSMSXSMSMMMSMMXXSAMSASXMXAMXMSAMXMXSAMSSMMMAMXSXMXMXSAMSAMXMAXMAXMMMMSSSSSMSXMMMMSXSSSSSSMXAAMXMXSASMMMMS
SXMASMMMSAXXMASAMXXAXASMXXMMXXMSAAMMMMAMSAXAAXXXXSMMAMMAMMSMSSXAMXMXXAXAMMAMXSAMMAMSAMASAMXASMMSMSMSSXAASAAXXAAMMXMAXMAMAMXAMSSMSAAAMAAMAAAX
MAMAMASASAMXMAMXMMMMSAMXXSSSSXAMXMMAAAASMAMSMSMSMMXXXMMMMASAAAMMMSSSMSMSMSMMMMASXAMMMMASAMSSMXAXXXMXMSMSMMMMSSMAAXMXXAXMXMSAXAAASMXXMMMSSMSS
MMMASMMAXXAMMMSMMMAASXMMMAAAMMAMXMMMMSMSMSMXXMASAAASMMXSMASMMXAAAAAXAMAMMMAAMMMMMXSXXMASAMMXAMXMMMMAMSXAAXMAXAXSSXSMXSXSMASXMMSMSASMXSMAXXAX
SASXSXMMMSXXMAAAASMMSASAAMMMMASMSSMSAXAXAAMMSSSMMMXSAMMMMXXAXXSSMXSMSMAXAMSMSASASAAXMAXSAMXMMMAAAAXAXXAXXMMXSAMXAASAMAAAMAMAMAMXMAMXAAMASXMM
AMSAMXMMASAMXSSSMSMXSAMXSXXMXSAAAAAAAMAMMMSAMXAMXMXSXMAMXASXMXMAAXMXMMXSMMMXSASASMAMSXAMAMMAMSSXSSSSSMMSAAAXAMXMMMMSAMXXMASXMASAMSMMAMMXXAAA
SXXAMXMMAXAAMAMAMXAAMAMXXMAMXXMMMMMMMMXMSAMASXMMAXMSASXXMAASMSXMSMXAXSASXSAAMXMXMASMXXXXAMAMXAXMXAXAAMAAXMMSAMMXSXXAXXMXXAXAMXSAMAAMMXMAXSMM
ASXSMXMMSSMXMAMAMMMASAMXMSMXXSXMAXAXMXAAAASAMAASASASXMAASXMXXAAXAXSMMMXMASMXXAMXSAXXSMMSMSSXMASMMSMXMMMXXMXMAXSAMXMMMAMXSSMSMMMMSSMMMAMSMXAA
MAMAAXXAMAMASMSSMMXMMASXMAMXMASASXSSMMSMSAMXSSMMMMAMMMMMMAASMSSMMXXXASAMXMMMSSSMMASAMAXMXAMXMSAMXMASMSSMSSSSMMMASMAAMAXAAAAXMAAAMMSXSAAAASXM
XXMAMMMXXAMAAAAAASXMMMMMSASXMASMMXXAXXXAMXMAMMMXXMXMAMXMSMMMAAAAXSASAXXMMAXXAAAAMAMXMSMSASMMXMAMXMAMAAAAMXAAAXSMSMMSMSSSMMMMSSSMSAAMSMSMXMAA
XXASASXASXMSSMMSMMAMASXXSAXXSAMASXSSMMMMMAMXMAMXMMAMXMAAXXXXMMXMMXAMMSSMSAMMMSMMMASAXMAMMXAXAMAMSMMXMXMMMMSMMXMAMMSMAMAXAMXMMMXAMMMXXAXMASXM
XMAXAAXMASAAXMAXAXXMAMAAMAMXMXMAMAAAMAAMSXSSSSMASAMMSAMXMASMXSXMXMXMMAXAAAMXAXAAMXSAMMSMXSAMASAMAAAMSASASAAAXMMAMSASMMAMMMAMAXMXMSMSMSMMMXAA
SXAXXMMXAMMSMMMMAXSMSXSAMAMXAAMSMMMMMSXMXMAXAAMASAAASASAMMMMAXMAMSAMXMMXMMMMXSSMMMSAMAMXAXAMXSXMSSMXSASAMSSSMMSMSMAMXMXMMSMSMSAMXAAXAAAMSSMM
AMXSSMXMXMSAMASMXMMAXAMXSXSMMMXMAMMXXXSSMSMMSMMMXXMASMSASXAMXSMMMMSAAXMMMAXMAXASAASXMXXMSSMMXSAXMAMXMMMAMAMAMAAMXMAMXMSSMSAXMAMXSMSMMMMMAASX
MAXAMXAMMMMASAXAMXMAMAMAAAMXSAMSSMAAXMASAAMMMMSSMXMAMMSAMMSSMMMSAAXXXXMASMSXMMAMMMMASMSMMAMXAXMMSAMXMXSAMXSAMSMMASASAMAAAMXMMSMMXAAXXAAMSXMM
XSMXXSXSAXSAMXSSXMASXXMXSXXAMAXAMXXMMMMMMMSAASAXAXMXSAMAMAXXMSASMSMASMMMXAAXXMAMSASXMAAMMAMMMSXXMAMSAMXMMXMXMMXSAXXMMSSMMMMSAAASMSMSSSSMMASA
SXSAAMMSAMMXMAMXASAMXSMMMAMSSMMSSMSMSAAMMXSMSMMXSAMAMXSAMXSMXMASAMXMMAMAMXMMXMSXSASMASMSSXMAAMXMSXMAMMAXMAMMMMXMMSMSAMXMAASMMSSMAAXXXAMAMAAS
SASMXMAMXMAXMAXMAMXSAMXAMAMAAMAMAXAAXSMSAASXXMXAXAMAXMMAXMAXAMAXMASXSSMAXSAMXAMXMMMXMAXAASMMSSSXSAMSMSSSSSXMAMXAAAXAMASXMXSAMXMASASMMXMAMMMA
MAMXMSSSSSSSSSSMSMMMXSAMXAMXMMASMMMSMXMXMASAMXMXSASXSMSAMSMXXXMXXASXMASAMSAMXSSSXAAXSMMMSMMAXAMASAMMAXAAXAASASXMMMSAMXSAXASMMAXMASXAXMSXSSSM
MAMAAXAAAAXAAAMAAAAAMMASMXMASMXSMMMAAXAMXAXAMAAXSAMXAASXMAMMSAMSMXSASXXXMMAXAXAMMMSXMXMSMMMSMAMAMAMMAMMMMSMMASXASAMXXXSAMXSASMSXXMMMMMMXMAAX
MAXXMMMMMMMMMMMSSSMSSXAAMXXMXMAMAAMMXXSSMMSAMXSAMXMMMMMXSXXASAMXMMSAMMMMSSSMXMMMASMMXAXMAXAMXXMXSAMXXAMAMXAMAMMMMMSMAMMASXSAMXMXAMAMXXXAMSMM
SSSMMAXAXXXSMSXMAAAAMMMMXASXMSSSMMSMSMMAAASXMXMXMAXAXSSMMSMASXMAMAMSMAAAXAXAAMASMSAXXMSSMMSMMMMXAASMSSMAMSAMMSMSAMAAXXMAMMSASAMMSSSSSSSMMAMX
XAAASXMMMAAMMSAMXMAMXMASMMSAAAAMMSAMAASMMMMMMASMSMSSXMAAAXMMMMSASASMSXSXMXMSASASXSXMSMAAAAMAAAMAMMMAAAXAMAMXAAMMASMSMXMAMAMMXAXAAAAAAAMSAAMX
MMMMMMASMSMXAMXMAMXXMSAXAASMMMMMMSASXXMAXXASMXMAMXAMASXMMSMAMASMSXSAMXXXMMXAXMAXAMMAAMSSMMSSMMMMSMXXMSMXMXSMMSMSAMXMASMMMSSSSSMMSSMMMMMAMSMM
ASXSMSASAAAMSSMXXSAAXMSMMMSXMXMAXSAMXMMSMSXSAXMMMMASXMASXXXAMASASMMXMAMAMSXMAXSMASASMXMAXMMMMSMSAMXSAAAASASAXAAMASXMMMAMXMAMAMMMAMMXXXXMAXXA
SXAAXMASMMMMMAXMASMSMAMXMASASXSMMMSMMSMMASASAMSMSAAXMMXSXASMSASMMMSMMASAMAMXMAMXXMAMXSXAMMAAAAMXAMAAMMSMMASMMMSMSXMAXSAMAMAMAMASAMMAMXSMXMAX
MMMMMMAMXXXASAMMAMAXMAMAMAXAMAXSXAXMAAAMSMXMAMAAAMMMSMAMMXMMMMSASAAMSASXSAMAMMSASMAMAMMMSSSMSSSSSMSMXMAAMXMAAXAXMASMMAMSXSXSXSMSASXXXASMSSSM
SAXMASMMXASXMAXMSSSXMSSSMSMSMMMMMMMSSSSMMMAXAMMSMXSAAMSSSSSMSSSXMMXXMASASXSXSAAAMMMMMSMXAAAAXXMAXAMASXSSMMMSMSMSMXMMAMXMASMMXSXMXMASMMMAAAAS
SMMMXMAASMMMXSMAXAMASAAAAXAMXSAXSAAMMAAMXXSSSSMXXAMMASXAAAAAXASAXMXMMMMMMMMXMXMSMXSAMAAMXSMMMSMAMXMASAMAXAXAAAAAAAXMAXXMAMASAMMXSAAXAAMMMXMM
MAAXAXMMSAAMAXMMMAMXMMXMMMASXXASMMXMMMMSXXMAXMXSMASMMSMMMSMMMSMMMMMMAAAAAAXAMXXAAASASMSMMMASAMMXSMSAMAMMMMSMSMSMSMSSXSXMASAMAMAXAMXMSMXSSMAX
XSXSSSMASXMMMMASMMXMAXXXXMSMASXMXMMSSMASMMMAMMASMAAAAXXXAXXXSXSXAAASXSSSSSMMSAMXMMSAMMAMXSAMAXXAXAXXMAMXAXAXAMXAAXXMMMAMAMXSMMSMMSMXMMSAXSXM
MMXAAMAMXXXMXMAMMXAAASMMAXXMAMMAXXAAAMXMAMXMMMAXMSSMMSXMMMMXMASXXXMMXAMMAMXSAMSAXXXMXSAMMMAMXASMMMMMSMMSSSMSAMXXXSAAAMAMASMSXXXAXAXAAXMMMMXM
XMASMMSAMXMXSMMSMSAXMAAXSSSMSSSMMMMSSMSSSMMSXMMSAAAAAXMAMASAMXMASMSSMSMMAMSXAMSMSMAMXMAXMMAMXMAXAMAMASAAAAMAMASAAXMAMSASMMMXMMSMMMSMSMMXMMAA
ASAXXAMAMASAMXMAMMMMMSAMXAAAAMAAXXAMAMAAXMAMAMSSMSSMMSAXSASASAMAMAAXAAXSXSSMMMXMAMAMMSMMSSMSMXMXXXASMSMMXSMMSAMMAMAXMSAMAXMMSAAAMXXAXAXAAXAS
MMAXMXXAXSMMXXSASXSAAXMMMMMMMSSMMMAMAMMXMMSSSMXSAAMAMXXXMXXMMMMSMMMMSSMMXXXAAAASASXMXAAAMAAAXAXXMSASXSASAAXAMXSXMMMMAMMSMMXAMXMMMMMMMSSSSSMM
MMSMMSMXMMASAASMSAMXSXMXASXSAXXAXMASMSXAMMAAXSSMMMSMXMASMSSSSXAAAAXMAMMSSSSSMSMSXSAMSSMMSMMMSASAAMAMASAMSSMXSMSMSAASXMAAXAMSSSSSSXSAAXXMAAAX
XAXAAMMMASAMMMMAMMMMAAMSMSASXMSMMMMAAMXXSSMMMXMAMXMMAXMASAAAXMSSXMSMASXAAMAAAXAMAMAMAAMMAXXXXAXMXMAMAMAMXXXXAAXXMSXMAMSSMMAXXAAAMAXMXXAMSMMM
MMSMMSXAMMMMXXMMMXMMMSMAAMAMAAAXXMMXAMXXMMAMMMSXMASMSSSXAMMMMMMXAASMASMMSMSMMMASMSSMSXMMAMMMMSMMMSASASMMMAMSMMMSMMMSMMXAMXSXMMMMMMMMAMSAMXAA
XXAAAXMSXSMSSXSAMXSAAAXXMMAMMSMSASMSAMXAXSAMAAAASMMMXMAMMSXXXSASMMMMAMAXAMXMAMXAXAXAXMMMXMAAAMAAAXASASXAMAMAMAAAAAAAMXMAMAXASASXAASMASAAMSSM
XSSSXSAXASAAXXMASASMSMSSXSXSXAMAAAASAMSMMSXSMSSMMMSSSSMXAAXMAMMSMAMASXSSXSXSSSMSMMSAMXSAMSSSSSMMSSMMAMMXXAXASMMXSMSMSASAMASMMXSSSXSSXSAMXAMA
XMAAAXAMMMMXSASAMAXXXMXMAMAMXXSMSXAMAAMAMXMSAMXAXSXAAMXMMSSMAMXXXAXAAAXMASXAAXAAAXMXMAMAMAAAAAMMXXXAAMMMSSSMSXSAAAAMSMSXMAXAMAMMMMMMMMAXMASM
MMMMMMXMXAXAXAMSSXMSSMAMAMAMMMXMMMXSMMMAMXAMSMMSMAMMMMAASAXXAMXMXSSMMMMMAMMMMMMXSXMAMXMMMSMXMASMMSMXMAXMAMAAXAAMMMMXSAMXMSSMMAMAAXAMXXXMMAMM
AAXMASAMXXSMXMAMXAMXASMSXSXSXXAAXSMXASXSSSSMAXXMMMASMSASMXXMXSXSAMXMASAXMAMSAAXSMMSASMXXAMXXXXAXAAXMXSMMSSMMMSMSSXXAMAMMMXAXSASXXSAMXXSAMAAX
SMXXAMASXMXXSXSXSMMSMMMMMMXMAMMSASAMXMAXAAXSSXSMAXAMXMMAMMSSXSAMSSXSASXMAMXXXXXAAXSASAAMSMSMMSMMSMMSAMXAAAASXMAAXAMXXSMMSMMMMASAASMSAMSAMXSM
XAAMXSMMAXSAMXMASMXXAAAXSSSMXSAMXXMAMMMMMMMAXAXSMMAMAMSASAXMASMSAMXSAMMSMXMXSSSSXMXMMMMMMAMAAAXMMXAMASMMSSMMAMMMSMXMSMAAXAAAMXMMMMXMAMSAMAXM
AMSSMAMSXMMAAMMAXMXMSSSMAAAAAXXSAMMSXAAAAMSAMSMSXMAXAXSAMASMMMXMAMAMAMMAMMMMAAMXXMXXMMSXMAMSSMSAMXXXAMXMAXASXMAMAMASASMMSSSSSMXXMMMSSMXAMXMX
SXAAMAMMMXSMMMSAMXSMAAMMMMMMMMMXAMXMSSSSSXMASMAMMMMXMMMXMASASMMMSMXMAMXAMAAMMSMMAMAMMAAAMSMMAAXMMSSMASMMAMMMMXAXASMSASMXAMAMAAMXXMASAMSXXXXX
MMSSMXSXXAXASASASASMMXMMXSXASASXSMXXAMXAAXSXMMSMSASASXSAMMSMMXMAXASXSSSSSSXSAMASXSASMMXSMAASMMSXAAAMXMASXSAAAXSXMSXSAMXASMAMXSAMXMXSAMAMMMMS
MAMXMASMMSSMMASMMASXSMSAASMXSXMAAMMMSSMSMMAMXXAXSASASASMSMMXSAMXSAAAAMXMAMAMASAXASAMXMAXMXMMAAXMMSSMXXXAASMMSMMAXXAMXSXMXSMSXMMMMSASAMMAAAAA
MASAMASXAAAAMAMMMSMAXAMMXMAXXMMSMMAAMXXAXMASXSXMMMMAMAMMAXXXMAMAMXMMMMAMAMMSMMASMMSMAXMMAMSXMMSMMAXAMXMMMMXXMASMMMXMAAAXAXXMMMAXAAAMXMXSSSSM
SASXMASMSMSMMMSXSAMXMSMSMSXAAMMMXSMMSASMXMAXMAXSAMMSMXMSASMMSSMMSSMMMSXSASXSASAMXAMSXMXMSMSASXAASMMMAAXXXXXXMAMMASAMXMXMMSXMAMSMSMSSMXXMAMAX
MASAMXSMMXXAMXSMSASAMXAAASMMMMAMMMXSMAMMAMMXSAMXAMAMAMAMAXAAAAMXAXAAMMMXMXXXAMXSASMMSAXXMASAMSSXMAXMSXSXXMASMAMSSSXSSSMAAMXMAXXAXAMAAASXMSSM
SAMXXMSASASASAMAXSMAMMMMSMAXMSMSAMSAMXMXAMMMMASMSMMSAMMMSSMMSSMMSSSMSXAXSSSMAMAMAMAAXSMXMXMXMXMAMMMXAASMSAMXMAMMAMAXAAXMMMXXMXMAMXMMSMMAXAMX
MAXMAXSAMASXMAXAXXXAXXAMAMMMMMXSASMMSMSSMXAASAMMMAAXASXAAMMMAAMXAAAAXMMSMAXSAMASASAMMXXMMMSMMAXAMXSMSXSAXXXMXMXMAMXMXMMXASMAMSMMMAXXXXSSMSSS
SAMASMMXMAMMAMXSSMSMXSASASMSXSAMXMMAMMXAASMXMXSXSMMSMMMMXMAMXAMMMSMMMMMAMMMSXMXMXSASAXMAMAAAMMSSXXMAXAMXMSMSAAMSSMAMMAXSAXSAMXAAMMXMXMXAAAAA
MASMMAAXMASAMXAMAAAMXXAMASMSAMXXXMMASMSMMMMAAAMMMMMAMXSSXSXSASAMXAAAAASMMXXMASASMSAMXSASMSSSMXAMXSMSMMMSXAAMMMMAAMASMMMAMMSMSMSMSSSXAMSMMMSM
SAMXSMMXMASASMSSSSSMMMMMXSAMSMMMSSSMMMAAMASMMAXAAASASXAXAAASAMXSSSSMSAMXSXAASAMXAMXMAMXMXXMAMMASASAAAAAXSMSMSAMXSMXMAAXMMXXXSAAAAAMXXXAMXMAX
MMSASAXXMASAAAAAAAMAAAXMAMXMMSAASASAXXMXSASXXMAMSXSASMSMMMMMAMMMAMXXMMXMAXMXXMXMSMAMMMAMXMMMXSSMAXXAXMSMMXXAMASAAAASXMMXMAMAMSMMMXMASMMSSSMS
SMXAXMMSMASMMMMSMSSSSSSMASXMAMMXSAMXMMSAMXSMMMSAAXMXMAMSXAXAMXMMMMSXSSMSAMSASXMAXSMSSSMSMSAXASAMXMXSAMXAXAMXSAMMSMXAMXSAMAMXXAXASXMMSAXXAAAA
MMMSSMAXAMSAXMXXAAAAAAAMASMSMSMAMAMXMAMASMMXSAMMAMXAMSMSSMXXMAXAXXXAAAXMAMMASXMAXAXAXAAAAMASMSXSXMAMMXSXMSSMMXMAXMMXMASAXXSMSXXXSAAXSXMMSMMM
SXAMAMXMMXMASMMMSMMMSMMMMMAAAAMASAMMXAMSMXAAMAMXAASMSMMMSMASMMSASMMMMMMMAMMXMAMXMMMSSSMSXSAMXMASMMMSMAMMMXAMXAMXSMSXMASMMSMMXSSMSMMMMAAXMXXX
AMSSMMXMSAMXMAAAAXXAAXXSXMSMSMSASASXMSSXAMMMSAMSMMMMAAAAMXXSAAMAMAAXMXSXXSMMSSMAAXAMXAAAAMXMAMXMAMXAMASASXXMSXSMAXSMMMSAMXAAAXMASAMASXMMMMAM
MXAMXMAMAASXSSMMSSMSSSMXAXMAMMMAXXMAAMAMXMAXXMMMXAAXSSMSXMAMMMMXMSMMMASXAMXMAAXSMMSSSMMMSMMMXXSSMMSXMASAMXAXAASMSMMAAAMXMSXMASMAMAMMSMMAMAAX
XMAMAAXXAXAMXAASXMAAMAMXMMXMXSMSMXMMMMASXMASXSAMMSSMXXAAXMAMMMMMMAMXMASMSMAMSSMXAAXXMAXAAXMASMMAXASMMMMXMSMMMSMAXASXMMSAXMAMSAMXSSMAXAXAMSSS
AXSSSSMMMMMXSXMMMMMMMAMMXSXMMXAMMSSMMSAMXMASMMAXXAMXMMSMXSAXAAAAMASAMMSAAXXMAAXSMMSASAMSSXSASASXMMSAMXASMAMXMAMMMXMAAASAMXSMXXXMAMMSMXXAMAMX
SXMAAMAASASXSAXSAAAXMMXSAMASAMXMAAAAAMAMXMAMAXAMAMXSAXAAMSAMSSSSSMSASAMMMSMXMAMXAXXAMXMAAAMASXMAAASAMMMMSMSSSMSMSSMMMMMSAMXAMXMMAXAAAMXSMMSS
AXMSMMMMSASASMMMSASMXSAMASAMMSXMMSSMMSXMXMMSSMMMXSAXSXMSMMXMAAMMAMXMMAMAXAMMSMSAMXMAMXMMSMMAMXSMMMSAMXMAMXAAAAXAAXASAMXAMAMAMSXMMMMSSXAMXXXA
MXAMASAAMMMMMMXXAMMAAMMMMMXSXMASAAMAMSXSAAAAAAXXAMXSMXXMXMMMMMMSSMSMSMSMSMSAASAXXAAAMAXAMASXSASXMASMMXMSSMMMMMMMMXXXAAMMSSSXMXSAASAAMMMSAMAM
XMAXAMMXMAAAAXMMMSMMMMAAXMASAAMMMXXSMSASMSMSSMMMSSSXMAMMAMMMSAMMXAXAAAAAMAMMSMMSXSMSSSMMSAMMSASMSAMXXAXMAMASXMSAXXSMSMXXAAXMAAXXAMMMMMXAAMAX
MSAMSMMSSSSSXSAAASASAXSXSMAXMMMXXXAXAMAMAXXMAAXAAXMASXMSSMSASMSMMMMSMXMSMAXXAAXMXXAAMAAAMMSAMAMXMASXSMMSAMASAASMSMSAAMXMMMMSMSSSSMSAASMSSSXS
XMAMMAXXMAMAXXMMXSAMAMMASMSSXXMASMAMAMSMMMASMMMMXMSAMXMAXMMASXAMASAMXXSXXMMMXSMMAMMMMSMMSASXMMMMSSMMMMAXXMXSMMMAAAMSMSAMAMAAXXAAMAMSMMAMXMAM
XXAMSAMMMSMMMMSMMMAMXMMAMAXMASMASMMMMMXAXXMMMMAXMAMASXMSSXMMMMMSAMMMSMSAXSASXXMMAXMAMMXMSAXXSAAMXMSASXSSSSMSAAMXMSMXXSMSAMSASMAMMAMMSMSMSMSM
SSMMXMAXAMAAASAAAXAMXSMMMXMMASMMMAXMMAXXMMSAMSAXSASAMXAAXXSAMXXMMXAXAAMAMMASAAXSAMSASMMMMSMXSSSSMMXSXAMAAMASMMSSMXASASASXMAXSAMMSAXMAXAAAAAM
XAMAMMSMSSSMXAXSMSMSXSAXMMMSASAMSAMXMASMAXSAMMAMSAMXSXSMSASASMMASMMSMSMXMMAMMSMMAMMASAAAAMMAMXMXAMMXMMMMMMMSMXMASMXMAMMMSMSXMAMAXXMSMSMSMMMX
SAMXSMAMXAAXSMMMAAXXASXMAAAMMMAMXMMMMAMMSMMXMXMXMSMMXAAXXMSAMXMAMAASXXMASMXMAAXXSMMSMMSMSMMASXMXAMXMASAXXMAMMXSAMMSMXMXAAXMASMMSSXMAXAAAXMSS
SAMXMMAXMSMMAXASMMSMXMMSSMSSXSSMMSAMMASAAXXAMASAAAMMMMMXXXMXXAMASMMMMMMASXSMSMXAMAXAAXXMXXSASAASMMMSAMMSMMMSAAMAMXASASMXSAMMMAAMAMSAMMSMSAAX
SMXASXSSMXXAXMXXAAXMAMXMAMAMXAXAASASXMSMMASMSASMSMMXSAMXMASMSMSXXMAXMSMASXXXMASMSXMMXMMMMAMAXMMMMAXMAMXAAMXMMXMAMXMSXXAXMXMMSMMMSAMXXXMASMSM
SMMXSAMXAMXSSMXSMMMSAMMSMMASMMMMMSMMXMSASMAAMAMMXAXAMAAMSAMAAAXAMMMMAAMMMMXAMXMXAMXSAXAAAXMASMSMSSMSAMSMSXXXSMSSSSXMMSMMMSMXAMXXMMXSAAMAMXAA
XXAMMXMMXMAMAXMAXSASXSAMAMSSMAAAASMASMSAMXXMAMMXSMMMSMXXMAXSMSMSMASXSMSAAXMXMAXXXSMSASMMMSAXXAAAMMAMMXAAMMMMMAXAAMXMAAAMAAMXAMXXXXASMSMAAXXS
AXSXXAXAAMASAMMSXMASXMAMSMAMXSSXXSMASXMXMASXSSMXXAAAAXMXXXMMSMAXMASAAXSMXSASXMXSMMAMAMXAASXMMSMMSMSMMSMXMAXAAXMMMMAMSSSMMSSSSMMMSMMSAMMSSSMM
SAMXSMSSXSXSXMXAMMAMMMXXXAMXAMAMSMMMSASXMXSAMXMASMMSSSMSAMXMAMSMSXMXMMXXASMXAMMXAMSMAMXMMSAXAAASAAMAMXSAAMSXMSSXAMXMMAAMXAAMMAAXMASMMMAAAAXM
MAXAAAAXMMMMAXXMSMASMMMAMAXMAMAMAAMXXAMAXXMMMSMAXAAXAAAXMMAMMSXMASAMXAXMASXXSMASXMMMASMMMMMMXXSMMXXAMASXSXXXASAMXMMAMXMXMMSMSSMMSXMAAMMSSMMS
SSMMMSMSMAAXAMXMAXASAAXXSXMXMSSSSSMMSSMMMMSMSAMMSMAMMMMMXXAMXMXXMASXXXSAMXMSMMMXMAXMAXMASXSAMSAMXSSXMAMSAMXAMMAMAMSXMMSXXXMMXAXASXSXMSAMAAXA
MXAAAAXSMSSSMSXMAMSSMSAAMMMMXAAAAXAXAMASMXAXSAMXAXXXXASMMMXSAAXMXXMMMMAXXSXAXXMASMMMSSSMSMMAXSAMXXASAMXMMXAMASXMAXASMASXMMMXSMMMSASAXMMSSMSM
MSXMSMXMXXMAMMASXSXMAMMXMAAASMSMMMSMMSAXASXMXMMSXSMMSMSAXAASMMMMSMMAAXMMMMMMSAMXXMASAAAAXAMXMMAMXSAMXMMAMMSSMXASMSAAMASASMMASAMAMAMMXMAMMAXX
MAAMAMSMSSSMMSAMMMAMXMXAMSSXSXAAXXXAMMMSXXMASMMSAXXAAXSAMSMXAXSAXASMXSAAXMAXMXSXMASMMSMMMSMMMXMMMXAMXMAAMAAMXMMMMMXMAMSAMAMMSAMMMMAXAMAXMSMM
MMSMASXAAMAXMMMSASMMXMSXXAXXMXMXMMXMMAAXXAMXMAASASXSXXMAMXASMMMXXXAAXSMMSSMSAMMMMSXSAXMMAXAXXASASMAXSMSSSMMSSSMXAXASXMMAMXSXSAMXMSMSMSAXSAAA
XAAXXMMMMSSMXAXXMAAASMMSMMSSMSSMASASXMXSXXMXSMMMAMXAMSSMMXMAMAMAMMMXMSAMXAASXSAAMXAMXSAMASAMSMSASXMMXAAMAAXAAAXSXSASXMMAMMAASXMAXAAAXAASXMXS
MSSSSXMXAAAMSMSMMSMMMAAAXAXAAAXAXSASAMXSXSAMXAXMXMXMMXASXXSMSAMAXXAXSXMSSMMMASXSSMSMMSMAMMXMMAMAMMSMMMMSSMMMMMMXMSAMAMSMSAMXMASMSMSMSMSMXXSM
AXAAXMASMXAMAAAXMAAXSMMMMASMMMSMAMAMASXMASXXXXXMASXXSSMMMAMAXXXMXMMSXAXMASMMAMMMMAMMMMXMMMMSMAMAMAAMAAMMAMMSAXXAMMAMSMAAMXXAMXMXMAXAMXAAAMAM
SMMMMAAXMASMMSMSSSSXSMAMMMMAMXMMAMAMMSAMAMMMMSMSMSXMAMAAMAMMMSMXAAMXXAMSMMXMAXAAMAMMAMAAAAMXSMXMMSSSMSMXAMASASXSSSMMASXSSSSSSSMASMMAMSMSMMMS
XAAXSMMSSXMAAXAAAXMAMMSAAASAMMAXXMASAXXMASAAXXMAAXXSSMSMSMSAXMAMSMSAXMMASMASXSSSSMXSASXSSMSAMXMSXMAXAAXSSMMSAMAMMMSMASXMAAXXAMSASASXMXAXXXXS
XSXXAMAMXAMMMMSMMMXMAAXMSMSMSMSXSMXMMSXMXSASXMSMSMMMMAAAAAXXSMSMAAMMMXSASMXSMAMAMAXMASXAXAXMMAMAAMAMMMMMMAMSMMAMAAMMAMAMMAMMXMMXSAMXSMMMXSAS
MXMMMSMMMSMSAMMAXAMXMXSAXXMMAMXASAAAAAAMXSXMAXSXAMSAMSMMMSMMMAMAMXMMAMMAXMXXAAMAMAXMAMMMMSMMSXSMSMAXAXSXSAMXASXSMSSMMSXMXMMMAMMMXMMMSAAAMMAM
AXAAXAAAAAXSASXSMSAAXMMMMASXXXMAMSSMMXSMAMAMXMSAMXAXMXXMAMXAMMMAXAXMSSSSSMXASXMSMSAMAMAAAAAXXXXAMMSMMMAASMXSAMXXXMXAASAMXMASAMAMMXXXSSMSMMXM
MMMMMSSMXXXMMMAXAXSMMMAAMAMXMASAMXMASAMMAXSASXSXXAMMMMSAMXSMSASMSSSMAXAAAASXMSXMAMMSASXMSSSMMMMMMAXASAMXMAASXSMMMMMMMXASASASMSMSAMSMXXMAMSAM
XMXSAXMAMSMSSMMMSMAXASASXMXSAAXAMSAAMAMMAMXAMAMMMSXASAMAMMSAMASXAMAMMSMMMMMAAMMMAMXMMSXAXXXAAAAAMAMAMXSAMXMXAXMAAAMAXMXMAMASAAXXXAMMAMMSXSAS
XAAAXSAASAAAMASAMXSMXSAXASXMMMMAMAMSSSMMSMMAMXMASAAASXSAMMMSMAMMSSSMAAXAXXSMMMASAMAMXSMMMXSSSSSMSAMAMXSAMMXMAMXMMMSASAAMXMAMMMSMMMASXSAMXSSM
XMAMMMXMSMMMSAMMSXMSMMMSAMXMAMSAMASXAXMAXAMXMAMMMMMMMASASMAMMXMXAMAMSSSMSMMXXSMSASASAMAMMAMMMAAASMMSSMXXMXAASMMSAMXAMXAMXMAMSASAMXAXXMAXASMS
SSMMSXMXXXSXMXXMAMMASAAMAMAMAXMAMXSMAMMASXMSSXSASXSXXXMMAMAMSMSMMSMMAAXXAAASMMMSASAMMSAMMASAMMMMMAAMAXSMXXASXAASAMMMMXMXMXSAMASASMAMXMSMMMAM
MAAASASXMMAAXSMSAMMAXXMMAXXMSXSAMMMMMXMASAXXAASAMAMXMSMXAMAXAAXMXAXMMMMSSSMSAAXMAMXMMSAXSASASXMAMMMSAMXAMSMMMMMSAMAMAMSAMXXMMXMAMMMAAAAAXMAM
XSMMMXMAAASMMSAMAXMSMSMSMSAXAASASAAAXXMASMSMMMMMMAMASASMSXSAMXMXSSSXSAAAMXMMMMSMAMSMASAMMXSXMASXSAXMXMAXMAAXXSAMXSASAMMASASXSSMMMMXSMSSSXSSS
MXASXSSSMXAMAMXMAMSMAAAAASMMMXMASMSMSMXXSAMXAXMASXSMSAMXXAMXMASAAAAASMSXMASXMASXAAAMMXMXXAMASAMXSAMSASASXXMMXMASXMMSASXSMASAXSXXAXXXMAMXAXAM
MSAMAAAAXSMXSXXXXXAAMMMMMMSSMMMXMMMMMMMMMXMSMSSMAMAMMMMAMMMXMAMMXMMMMXMAMAXAMASXSSSSXSXSMXSAMASXMAMMXMASMMSAXSAMMSMSAMXAMMMMMMSSSSMMSMMXSMSA
MMMMMMMMMASAMXAMXSMSSXXXMMMMAASASAXAAAMAAAXAAMAMMSSMAAMXSASMMSSMXMSXMSSSMSSMMXSMMAAMAAAXXAMAMXMAMMMXSMMMAXSAMSASAAMMAMXMASAXAAAXXAMAAAXMXAXA
XAXXAXXXXAMMXSMAMXAAAMAMAAAMSMSASMSSSSSMSSSMSMXSAMXSXSAASMSAMAAXXMASMAAAAXAMAASMMMMMMMSMMSMSMSSSMAAMXAAXSMMAMXAMMMMXAMXXASXSMSXSSXMMXMMAXMXX
SMSMXMMMMMSXMASXAMMMSAXMSSSXMXMAMXMMMMAAAAAAXMXXAMAMMMMXSXSAMSSMXSASMAXMMMAXMMSAMXXAXAAAXAAMAMAASMSSSXMXMAMSMMXMMSSSMSXMASMXMAAMMMSSMMSSMMSM
AXAXAXAAAMAAAMXSMMSAXXXMAMMMXXMXMAAAAMAMMSMMMMMSMMAMXAXXMAMAMXXAAMASXMSSXSAMMXMMMMXMMSSSMMSMAMXMASAAAXSASMMMAXSAAAAAAMXSAMXMMMMMAAAAAAAAAAAA
MSMMMSXMXXAXMSAXMASMXSMMASMMXXMAMXXSSSMSXXXXAAAAXSAMSSSMMXMSAMXMMMAMAMAMXSXMMASXMMAMMXMAMXMXXMAXMMMSMMMAXMASAMSAMMSMMMAMASMMMSMSMMXSMMXMMSSS
MAXAMSMSSXSAAMASMXSAASXSASAAAXSSMSMMAAAXXXXSSMXSMSMMMXAXAMXXASXMAMASAMAXMMAMSMSAMSSSMASAMMMXMXXSAMAAAXXXMMXMXMXAMXAAAMASAAAMXAAXAXXMXSMSMAAX
SASXAXASAAMXMASMXAMMMSAMXSMMXXAAASMMSMMMMXXMAXAMMXMAXSMMMMMSXMASASMXAMMMAMAMSAMXMAMAXASXSAMXMAXMAMSSSMMXMXXMXMSSMXMMASAXMSXMMMMMSMXXAXAAAMMM
MASXMMMMMMMAMSMMXXSMAMAMMXMAXMMMMMAMASXAMXSSSMMSASXSXMMXAAXSMSAMXMASXMSASMASMAMAMXSAMXSMXASAMSMSAMAMAASAMSXMAAAXMASMASAXMMMMASAMAASMMMSMSAMS
MAMMXAXAXXSAMAAAAMXMASAMSAMXSSXAAAMMAMSASAMXAAAAXMAMXAASXSMXAMSSXMASAASAMSXMMAMXSAMXSXSASXMASAASMMAMSAMASAASMSMXSASMAMAMAAMSASASMSXAAAXSXMSX
MMSASMSMSASXSSSMMAMSXSASMXMXSAMSSSXMXXSXMXSSSMMSSMXMAMASAAMMXMMSXMSSMMMSMXXMAXSAMXXSAMXXSSSSMMXMXSSMXMSMMMXMMAMXMXSMASMSMXMMASMMXMMSMSSMMSSX
"

# part 1

get_adjacent_4tuples <- function(mat) {
  n <- nrow(mat)
  idx_mat <- matrix(1:(n * n), nrow = n, ncol = n, byrow = TRUE)


  # horizontal
  h_tuples <- cbind(
    c(idx_mat[, 1:(n - 3)]),
    c(idx_mat[, 2:(n - 2)]),
    c(idx_mat[, 3:(n - 1)]),
    c(idx_mat[, 4:n])
  )

  # vertical
  idx_mat_t <- t(idx_mat)
  v_tuples <- cbind(
    c(idx_mat_t[, 1:(n - 3)]),
    c(idx_mat_t[, 2:(n - 2)]),
    c(idx_mat_t[, 3:(n - 1)]),
    c(idx_mat_t[, 4:n])
  )

  # diagonal
  d1_tuples <- cbind(
    c(idx_mat[1:(n - 3), 1:(n - 3)]),
    c(idx_mat[2:(n - 2), 2:(n - 2)]),
    c(idx_mat[3:(n - 1), 3:(n - 1)]),
    c(idx_mat[4:n, 4:n])
  )

  # anti-diagonal
  idx_mat_rev <- idx_mat[, n:1]
  d2_tuples <- cbind(
    c(idx_mat_rev[1:(n - 3), 1:(n - 3)]),
    c(idx_mat_rev[2:(n - 2), 2:(n - 2)]),
    c(idx_mat_rev[3:(n - 1), 3:(n - 1)]),
    c(idx_mat_rev[4:n, 4:n])
  )

  return(rbind(h_tuples, v_tuples, d1_tuples, d2_tuples))
}

m <- do.call(rbind, strsplit(readLines(textConnection(input)), ""))

get_adjacent_4tuples(m) |>
  apply(1, \(r) {
    xmas <- c("X", "M", "A", "S")
    identical(m[r], xmas) || identical(m[r], rev(xmas))
  }) |>
  sum() |>
  print()


# part 2

generate_3x3_submatrices <- function(mat) {
  n <- nrow(mat)
  i <- expand.grid(row = 1:(n - 3 + 1), col = 1:(n - 3 + 1))

  return(
    seq_len(nrow(i)) |>
      lapply(\(k) {
        mat[
          i$row[k]:(i$row[k] + 3 - 1),
          i$col[k]:(i$col[k] + 3 - 1),
          drop = FALSE
        ]
      })
  )
}


is_X_MAS <- function(mat) {
  d <- diag(mat)
  ad <- mat[cbind(1:3, 3:1)]
  xmas <- c("M", "A", "S")

  return(
    (identical(d, xmas) || identical(d, rev(xmas))) &&
      (identical(ad, xmas) || identical(ad, rev(xmas)))
  )
}


m |>
  generate_3x3_submatrices() |>
  sapply(is_X_MAS) |>
  sum() |>
  print()