12.py

import math
import collections
from collections import Counter
import random
import re
from tqdm import tqdm

PROD = """
GGGGGDDDDSSSEEEEEEEEEEEEEEEUFFOOOOOOOYYKKKKXKKKKKKKKKKKKKNVVVVVVVVVVVVVVVVVVVYYEEZNNNNNNNNNNBNSSNNNWUUUUUUKKKKKKKKKKKKKKKKKKKKHHHHHHHHHHHHHH
GGDDDDDDDSSSSEEEEEEEEEEEEEEFFFOOOOOOOYYKKKKKKKKKKKKKKKKKNNNVVVVVVVVVVVVVVVVEYYEEENNNNNNNNNNNNNSNNNWWWWWUUIITTKKKKKKKKKKKKKKKKHHHHHHHHHHHHHHH
GGGDDDDDDSSSEEEEEEEEEEEEEFFFFFOKOOOOOOOOKOKKKKKKKKKKKKKKKNNVVVVVVFVVVVVVVVVEEEEEENENNNNNNNNNNNNNNNWWWWWUUTTTTTTKKKKKKKKKKKKKKKHHHHHHHHHHHHHH
GGGGDDDDSSSSESEEEEEEEEEEEEEFFFOOOOOOOOOOKKKKKKKKKKKKKKKKNNNVVVVVVFFFVVVVEEEEEEEEEEEENNNNNNNNNNNNNWWWWWUUUUTTTTTKKKKKKKKKKKKKKKKHHHHHHHHHHHHH
GGGDDDDDTSSSSSSESSEEEEEEEEEFFFFOOOOOOOOOKKKKKKKKKKKKKKKKNNNVVVVVVFFFVVVVEEEEEEEEEEBBBNNNNNNNNNNNWWWWUUUUUTTTTTTTTKKKKKKKKKKKKKKHNHHHHHHHHHHH
GGGBDDDDTSSSSSSSSSSEEEEECFFFFFONOOOOOOOOOOKKKKKKKKKKKKNNNNVVVVVVVFFFVVVVEEEEEEEEEEBBBBBBNNNNNNNNWWWXUUUUUTTTGTTTTTTTKKKKKKKKKKKHNHHHHHHHHHHH
GBBBDDDDSSSSSSSSSSSJEEELFFFFFFOOOOOOOOOOOOKKKSKKKKKKKKKNNNNVVVVVVVVVVVVEEEEEEEEEEBBBBBBNNNNNNNWWWWWFFFFFFFFFFFFFFFTKKKKKKKKKKKHHNHHHHHHHHHHH
GGBBBBBUUUUUUUSSSSSSSLLLFFLFFFOOOOOOOOOOOOKKKKKKKKKKKNNNNNNMMMMVVVVVVVVEEEEEEEEEEBBBBBBBNNNNNNWWWXXFFFFFFFFFFFFFFFFFFFFFFFFKKKHHHHHHHHHHHHHN
BBBBBUUUUUUUUUUSSSSSLLLLLLLFFLOOOOOOOOOOOOKRKKRRKKKKKKKNMMMMMVVVVVVVVVVVEEVVEEEEEBBBBBBBNNNNNXXXXXXFFFFFFFFFFFFFFFFFFFFFFFFKKKHHHZZVHHHHXHHN
BBBBBUUUUUUUUUUAAAAALLLAAAAAAALOOOOOOOOOOOORRRRRRKKKKKQMMMMMMMVMMVGGVVVVVVVVEEEEEBBBBBBNNNUNNXXXXJXFFFFFFFFFFFFFFFFFFFFFFFFKKKHHHZZVFFHHHHNN
BBBBBUUUUUUUUUUAAAAAAAAAAAAAAAZOOOOOOOAOOOOAARRRRRKKRRRMMMMMMMMMMGGGGGVVVVVVEEUEEBBBUUNNNNUUXXXXXXXFFFFFFFFFFFFFFFFFFFFFFFFKKKKKZZVVVVVEHVNN
BBBBBUUUUUUUUUUUAAAAAAAAAAAAAAJJJJOOAAAAAORAARRRRRRRRRMMMMMMMMMMMGGGGGVGGGGEREEWESSUUUUUUUUXXXXXXXXFFFFFFFFFFFFFFFFFFFFFFFFKKKKKKZZVVVVVVVNN
BBBBBUUUUUUUUUUUAAAAAAAAAAAAAAJJJOOOAAAAAAAAARRRRRRRRRMMMMMMMMMMMGGGGGGGGGEEEEWWWUUUUUUUUUUXXXXXXXXXXXXXVFFFFFFFFFFFFFFFFFFQQQKKKVVVVVVVVVVV
BBBBBUUUUUUUUUUUUUUAAAAAAAAAAAZZIDAAAAAAAAAAAAAARRRRRRRFMMMMMMMMMGGGGGGGGGGGFEWWWUUUUUUUUUUXXXXXXXXXXXXZZFFFFFFFFFFFFFFFFFFSQQKQQVVVVVVVVVVV
KKKBBUUUUUUUUUUUUUUAAAAAAAAAAAIIIDAAAAAAAAAAAAAAARRRRRFFMFMMMMMMMGGGGGGGGGEGGWWWWUUUUUUUUXXXXXXXXXXXXAZZZFFFFFFFFFFFFFFFFFFSQQKQQQQVVVVVVVVV
KKBBBUUUUUUUUUUUUUUAAAAAAAAAAAIIAAAAAAAAAAAAAAAAAARRRRFFFFFMFFMMNGGGGGGHEEEEWWWWUUUUUUUXXXXXXXXXXXXXXAZZZFFFFFFFFFKKKKSSCSSSQQQQVVVVVVVVVVVV
KKBBKKKKSUUUUUUUUUUAAAAAAAAZZZIIIIAAAAAAAAAAAAAAAARRRRFFFFFFFFFFGGGGGGGHEEEEEWWWUUUUTUUXXXXXXXXXXXXXXZZZZZZZZZOKKKKKSSSSSSSSSSVVVVVVVVVVVVVV
KKKKKKKKSUUUUUUUAAAAAAAAAAAZZZIIIIAAAAAAAAAAAAAAAARRRFFFFFFFFFFFFGGGGGGEEEEEEWTTYYTTTDUXXXXXXXXXXXXXXEZAAAAAAAAAKSSKSSSSSSSSSSXVVVVVVVVVVVVV
KKKKKKKKKUUUUUUUIEIAAAAAAAZZZZIIIIKIAAAAAAAAAAAAAARRRFFFFFFFFFFFRGGGGRREEEEEEWTTTTTTTTUXXXXXXXXXXXXXIIZAAAAAAAAAGSSSSSSSSSSSSSXXVVVVVVDVVVVV
KKKKKKKKKUUUUUUUIEIEZZZZZZZZZZZIIIIIAAAAAAAAAAAARRRRRFFEFFFFFFFFRGGGGRRRRRRRWWTTTTTTTGGGGGXXGXXXXGXAAAAAAAAAAAAASSSSSSSSSSSSSXXVVVVVVVDVVVVV
KKKKKKKKKUUUUUUUEEIYZZZZZZZZZZGWOIUAAAAAAAAABBAARRRRZTTFFFFFZFRRRRRRRRRRRRRRRTTTTTTTTTTGGGGGGXXXXGGAAAAAAAAAAAAAGSSSSSSSSSSSXXXVVVVVDVDDVVVV
KKKKKKKKKEEEEEEEEEIYYYYTTGWWWZWWIIUUAXAAAAAAYYYYRRRRZZZZZZZZZFRRTTTTTRRRRRRRRRTTTTTTTTGGGGGGXXXGGGGAAAAAAAAAAAAAGSSSSSSSSSSSXXXXXVVVDDDDDDVV
KKKKKKKKKEEEEEEEEEEYYYYTGGWHWZWWWIUHHXAAAAAAYYYYYRRZZZZZZZZZZZRRRTRRRRVRRRVVTTTTTTTTTTTGGGBBBBBGGGGAAAAAAAAAAAAAGGSSSSSSSSSXXXXXVVVDDDDDDDVV
KKKKKKKKKEEEEEEEEEEYGVGTGGHHHWWHIIUHHHYYYYAYYYYBBZZZZZZZZZZZZZZRRRRRRRVVVRVVAATTTTTTTTTTTBBBBBBBBGGAAAAAAAAYGGGGGGWGSPPPPPSXXXXXXVDXDDDDDDVV
KKKKKKKKKEEEEEEGGGGGGGGGGGHHHHWHHHHHHHHYYYAYYYYBZZZZZZZZZZZZZZRRRRRRRRVVVVVVAATTTTTTTTTTHBBBBBBYGGGAAAAAAAAGGGGGGGGGGPPPPPPPXXXXXXDDDDDDDDDV
KKKKKYYKKEEEEEGGGGGGGGGGGGHHHHHHHHHHHHHYYYYYYYZZZZZZZZZZZZZZZZZRRRRRRVVVVVVVVAATTTTTTTTHHBBBBBYYYYYAAAAAAAAGYGGGGGGGGPPPPPPPPXXXXXXDDDDDDDDD
KKKYYYYKKKEEEEGGGGGGGGGGGGHHHHHHHHHHHHPYYJYYYYYYZZZZZZZZZZZZZZZRRRRRRVVVVVVVVVAATTTTTTTTBBBBBUUYYYYYYYAAAAAYYGGGGGGPPPPPPPPPXXXXDDDDDDDDDDDM
KKFFYYYEEEETEGGGMMMMMMMGGGHHNNHHHHHHHHPPPJYJJJJJJGGZZZZZZZZSSSRRRRRVVVVVVVVVCCVTTTTTTTTTTUBUUUUYGYAYYYAAAAAPYGGGGGGPPPPPPOPPXXXXDDDDDDDDDDDD
YFFFYQYYYYEEEEGGMMMMMMMGGGGNNNNNNNNHHHPJJJJJJJJJJJGZZZZZZZZSSRRRRRRRRHVVVVVVVCVTTTJTTTTTUUUUUAAAAAAAAAAAAAAGGGGGPGPPPPPOOOPXXXXXDDDDDDDDDDDD
YYYYYYYYYYEEEYLLMMMMMMMGGGGNNNNNNNNHPPPJJJJJJJJJJJJZZZIZZZZRSRRRHHRHHHVVVVVVVVVTTVVTUUUTUUUUUAAAAAAAAAAYYYBGGGGGPPPPPPPOOOOOOXOOODDDDDDDDDDZ
YYYYYYYYYYYYYYYLMMMMMMMGGGGNNNNNNNNNPPPJJJJJJJJJJIIIIIIIZZRRSRRHHHHHHHHVHVVVIIVVVVVVUUUUUUUUUAAAAAAAAAAAYBBGGGGPPPPPPPOOOOOOOOOOOODDDDDDZZDZ
YYYYYYYYYYYYYYYGMMMMMMMGGGNNNNNNNNRSRPPPPJJJJJJJJIIIIIIIZRRRRRHBBHHHHHHHHHHVVVVVVVNUUUUUUUUUUAAAAAAAAAAAAAAGGGPPPPPPPPPPOOOOOOOOOOOODZZDZZZZ
YYYYYYYYYYYYYYYGMMMMMMMGGGNNNNNNNNRRRRRRJJJJJJJJJIIIIIIZPRPHHHHHHHHHHHHHHJJVVVVVVVNUUUUUUUUUOAAAAAAAAAAAAAAAGGPPPPPPPPOOOOOOOOOOOOOOOOZZZZZZ
YYYYYYYYYYYYYYYXMMMMMMMGGGGGNNNNNRRRRRRRRJJJJJJJJIIIIIIZPPPHHHHHHHHHHHHHHHHVVVVVVVNUUUUUUUUUOOJOOOAAAAAAAAAAGPPPPPPPPPOOOOOOOOOOOOOOOOZZZZZZ
YYYYYYYYYYYYYYYYMMMMMMMGGGNNNNNNNNRRRRRRRRRJJJJJJIIIIZZZZZPHHHHHHHHHHHHHHHHHVVVVVVNUUUUUUUUUOOOOOOAAAAAAAAAAAPPPPPPPPPPPPOOOOOOOOOOOOOOZSSZZ
YYYYYFYYYYYYYYYYMMMMMMMNGNNNNNNNNNRRRRRRRRRHJJJRJIIIIIZZZZZHHHHHHHHHHHHHHHHVVVVVVNNUUUUUOUOOOOOOOMAAAAAAAAAAPPPPPPPPPPPPPOOOOOOOOOSSOSSSSZZZ
YYYYYKPYTYYYYYYYMMMMMMMNNNNNNNNNNRRRRRRRRRRHRTJJJIIZZZZZZZZZHHHHHHHHHHHHHPPPVVVVVGNUUUUOOOOOOOOOOMMMOAAAAAAPPPPPPPPPPPPPOOOOOOOOOSSSSSSSSSSZ
YYYYKKKTTTYYYYYYMMMMMMMNNNNNNANAARRRRRRRRRRRRJJIIIIIZZZZZZZZHHHHHHHHHHHHZZZVVVVVGGNUUUUOOOOOOOOOMMOOOAPAHHHPPPPPPPPPPPPPPOOOOOOOOOSSSSSSSSSZ
YYYYYKKKKTKKKKKMMMMMMMMNNNNNNAAAARLRRRRRRRRRRRIIIIIIZZZZZZZZHMHHHHHHWHZZZZZVVVVVGUUUUUUTOOOOOOOOOOOOLOAAHHHHPPPPPPPPPPPPPOOOOOOOOOSSSSSSSSSZ
YYYYYYYKKKKKKKZZZMMMMNNNNNNNAAAAARLLRRRRRRRRRIIIIIIIZZZZIZZZZHHHHTHHZZZZVZZHHVVUUUUUUUZOOOOOOOOOOOOOOOCAAHHHHHPHPPPPPPPPPPPOSSOOOOOSBSSSSSJJ
YYYYYYYKKKKKKKKKKMMMMMMNNNNAAAAAAAARRRRRRRRRRRPPIIIIIZIIIZZZZZHLHTHHZZZZZZZHHUUUUUUHUUUHOOOOOOKKKSSSSSCAAHHHHHHHHPPPPPPPPPSSSSSSOOOOBSSSSSJJ
YYYYYYYKKKKKKKKMMMMMMMMNNNNAAAAAAAAAARRRRRRRRPPPPPIIIIIIZZZZZHHLZTZIZZZZZZZZZUUUUHHHUUUHHOOHOOKKKKKSSSSHHHHHHHHHPPPPPPPPPPPSNNNXNNNNNSSSSJJJ
YYYYYYYKKKKKKKKKKMMMMMNNNNNAAAAAAAAAARRRRRRRRPPPPIIIIIIZZZZZZZZZZTZZZZZZZZZUUUUUUUHHHHHHHHOHHKKKKKKSSSSSSHHHHHHHHPPPPPPPCCCNNNNNNNNNNWSSJJJJ
YRYYYYKKKKYYYKKKMMMMMMNNKKKKKKAAMMAAARRRRRRRPPPPPIIIIIIZZZZZZZZZZZZZZZZZZZTUUUUUUUUHHHHHHHHHHKKKKKDSSSSSSSHHHGGGHHHPPPPCCCCNNNNNNNNNNWWWJJJJ
RRRYYYYYYYYYYYYYMMMMMNNNKKKKKKKAAMMAARRRRRRRPPPPPPPIIOIZZZZZZZZZZZVVZZZZZZTTTUUUTTUPPHHHHHHHHKKKKKKFSSHHHSHHGGGGGHNPPPCCRRCNNNNNNNNNNWWWJJJC
RRRRYYYYYYYYYYYMMMMMHNNNVVKKKKKAHHMARRRRRRRRRPPPPFFOIOZZZZZZZZZVVVVVVZZZZZTTTUUUTTTPPPPHHHHHHKKKKKKKKKKHHHHHHGGGGGNNNPCCRRRRNNNNNNNNNWWWWJJC
RRRRRRRYYYYYYYOOEOOMHHNNNNHHNNNHHIMMIRRRRRRRPPPPYOOOOOOZOOOOOVVVVVVVVZLZZZTTTTTTTTPPPPPPHHHHHKKKKKKKKKKHHHHHHGGGGGGNGRRRRRRRRNNNNMNNWWWWWVVC
RRRRRRYYYYYYYOOOOOOMMHHNNTNNNNNHHIIIIRIIIPRRRRLOOFOOOOOOOOOOOVPVVVVVVVLZZTTTTTTTTTPPPPHHHKKKKKKKKKKKHHHHHHHHHGGGGGGGGGRRRRRRRNNNMMMMMWWWVVVV
GRRRRYYYYYYYYOOOOOOOOOHOITNNNNNNHHIIRRIIIPPRRROOOOOOOOOOOOOOOOPVLLLLLLLZZTTTTTTTTTTPPPPHHKKKKKKKKKKHHHHHHMHHHGGGGGGGGGRRRRRRRNNNMMMMMWMWVVVV
GRRRRRYYYYYVYOOOOOOOOOOOIINNNNNCCHIIIIIIIIPPPPOOOOOOOOOOOOOOOOPVVYLLLLLZTTTTTTTTTTTTPPGRHKKKKKKKKKKHHHHHMMMMMGGGGGGGGGRRRRRRRRNNMMMMMMMWWVVV
GRRRRRYVYYYVYBOOOOOOOOIIIIOONNNCCIIIIIIIPPPPPPPPOOOOOOOOOOOOOOOVYYLLLLLTTTTTTTTTTNNNRRGRHHRKKFKKBKKBHHHMMMMMMGGGGGGGGGGRRRRRRNNMMMMMMMMWVVVV
GGGGGGYVVVVVVVVOOOOOOOIIIIIINDNICCIIIIIIPPPPPPPPOOOOOOOOOOOOOOOOYLLLLLTTTTTTTTTTTNNRRRRRRRRRFFFBBBBBMMMMMMMMGGGGGGGGGGGRRRRRRRRRMMVVVMMMVVVV
GGGGGGYVVVVVVVVVOOOOOOIIIIIIZIIIICIIIIPPPPPPPPPPOOOOOOOOOOOOMMMLLLLLLLLLTTTTTTNNNNNNRRRRRRRRBFFFBBBBMMMMMMMGGGGGGGGGGGGGSRRRRRRRRCVVVVVMVVVV
GGGGGGGGVVVVVVVVOOOOOOIIIIIIIIIIIIIIIPPPPPPPPPPPOOOOOOOOOOOOOMMLLLLLLLLLLTTTENNNNNNNRRRRRRRRRFYFBBBBMMMMMMMMGGGGSSSAGGGKSSRCCCRRCCVVVVVVVVVV
GGGGGGGGVVVVVVVVOOOOOOIIIIIIIIIIIPPIIPPPPPPPPPOPPOOOROOOOOOOOOMMLLLLLLLELLTTENENNNNRRRRRRRFFBFFFFFFFMMMMMMMMMGGMISSSSSGSSSSJCCCCCVVVVVFFFVVV
GVGGGGGRRVVVVLVOOOOOOOIIIIIIIIIIIAPPPPOOOOOPOOOPPPOOOOOOOMMMMMMLLLLLLLLEEEEEEEENNNNNIIIRRRFFFFFFFFFMMMMMMMMMMGMMMSSSSSSSSSSSVCCCCVVVVVFFFFFF
VVGGGGRRRVVVVLVOOOOOOOOIIIIIIIIIIAPAAAAOOOOOOPOOOOOOOOOOOSSMMMMMMLLLLLLEEEEEENNNNNNNIIIRRRFFFFFFFFFMMMMMPPMMMMMMSSSSSSSSSSSSCCCCVVVVVVFFFFFF
VVRRRRRRRVVVLLKLOOOLLLOIIMMIIIAAIAPAAAAOOOOOOOOOOOOOOOHHOSSSSMSMLLLLLLLLEEEEENNNNNNNIIIRRRFFFFFFFFFMFMMMPMMMMMMMMMSSSSSSSSKKCCCCCCCVVVFFFFFF
VVVVVRRRRVVVLLLLLLLLLLOOOIIIAAAAAAAAAAAAOOOOOOOOOOOOOOOSSSSSSSSMLLLLLLEEEEDNNNNNNNNNIIIRRGFFFFFFFFFMFMMHPMMPPPPMMMSSSSSSSSKCCCCVCCVVVVFFFFFF
VVVVVRRRRVVLLLLLLLULLLOOOOOIAAAAAAAAAAABOOOOOOOOOOOOOOOSSSSSSSSMMLSSSLEEDEDLNDNNNNNNIIIGGGFFFFFFFFFMFMMPPPMMPPPPSSSSSSSSZKKKKVVVVVVVFFFFFFFF
VVVVVVVRRVVLLLLLLLLLLLLOOOOOAAAAAAAAAAAAAAOOOOOOOOOOOOOSSSSSSSSSMLLSSEEYDDDDDDDNNNNNIIIGUFFFFFFFFFFFFMKPPPPPPPPSSSSZSZZZZKKKVVVVVVVFFFFFFFFF
VVVVVVVVRVLLLLLLLLLLLLLOOOOOOAAAAAAAAAAAAAAOOOOOOOOOOOSSSSSSSSSLLLSSEEEEDDDDDDIIIIIIIIIUUFFFFFFFFFFFFMKPPPPPPPPPSSSZSZZZZZKVVVVVVVVVFFFFFFFF
VVVVVVVVVVVLLLLLLLLLLLLLLOOOAAAAAAAAAAAAAOOOOOOOOOOOOOSSSSSSSSSSSSSSSESSSDDDDDIIIIIIIIIUUFFFFFFFFFFFFPPPPPPPPPPSSSSZZZZZZZZVVVVVVVVFFFFFFFFF
IIVVVVVVVVVVLLLJLLLLLLLOLOOUAAAAAAAAAAAAAOOOOOOOOOOOSSSSSSSSSSSSSSSSSSSSSDDDDYIIIIIIIUUUFFFFFFLFFFSFFVVPPPPPPPPPPSSZZZZZZZZIVIVVIVVIFFFFFFFF
IIIVHHHHHHVMMMLMSLLLLOOOOOUUAAAAAAAAAAAAAOOOOOOOEEEEEEESSSSSSSSSSMSSSSSSSDDDYYIIIIIIIGUUIFFPPFFFFFFFVVLLLLPPPPPPPPZZZZZZZZIIIIIIIIIIIIFFFFFF
IVVVVHHHHHMMMMMMMMMLLOOUUOUAAAUAAAAAAAAAALNOOOOOEEEEEEEEEEEEESSSSSSSSSSSSYDYYYYYYYYGGHIIIIFYYYFPFFFVVVLLLLPQPPPPPZZZZZZZZZIIQIIIIIIIIIFFFFFF
PVVVHHHHHHBMMMMMMMMMOOUUUUUUUUUAUAAAAAFANLNNNOOOEEEEEEEEEEEEESSSSSSSSSYYYYYYYYYYYYGGGHHIIIIYYYFVVSVVVVLLLLPPPPPPPPZZZZZZZZQQQQIIILIIIIIFFFFK
PTVHHHHHHHBMMMMMMMMMOOOUUUUUUUUUUAUAAAANNNNNOOOOEEEEEEEEEEEEESSSSSSSSSSYYYYYYYYYYGGGGHHHHIIYYYYYVVVVVVLLLLVPEPPPZZZZZZZZZQQQQQQLLLLIXFFFFFFF
TTHHHHHHHHMMMMMMMMMMMOUUUUUUUUUUUUUAAANNNNNNNOOAEEEEEEEEEEEEESSSSSSSSYYYYYYYYYYYYYGYYHHHHHIYYYYYYVVVVVLLLLLVVPPPZZZZZZZZZVVVVVVVVVVLXXFFFFFF
DTTTHHHHHHMZMMMMMMMMMMUUUUUUUUUUUUAAAAANNNNNNNAAEEEEEEEEEEEEESSSSSSSSSYYYYYYYYYYYYYYYYHHHHISYYYYVVVVVVLLLLLVPPAAZZZZZZZZZVVVVVVVVVVLXXXFFFFF
DTTTTNHHHZZZMMMMMMMMMMUUUUUUUUUUUUUQANANNNNNNNAAAGUUAEEEEEEEESSSSSSYYYYYYYYYYYYYYYYYYYHHHSSSSYYVVVVVVVLLLLLVVVAZZZZZZZZZZVVVVVVVVVVVVVXXXXFF
DTTTTTHHHHZZMMMMMMMIIIUFUUUJWUUUDDXXNNNNNNNNNNNAGGUCAAAACCCCCSASSSSSSYYYYYYYYYYYYYYYYOOHKKSSSYVVVVVVVVLLLLVVVVVZZEEZZZZZZVVVVVVVVVVVVVXXXXFF
DDTTTTHHHHHHWMMMMMIIIIIUUUUJWWWDDXXXXXNNNNNNNNNGGUUCACACCCCAAAAAASSSSYYYYYYYYYYYYYPYOOOHSSSSSSSWVVVVGVVVVVVVVVOOZEZZZZZZZVVVVVVVVVVVVVXXXXXX
DTTTTTHHQHHHMMBMMMIIIIIIIIIWWWWWDXXXXXNNNNNNNNNUUUUCCCCCCCCAAAAAAASSOOYYYYYYYYYYYYYYOOOOOSSSSSSSBVBBVVVVVVOVVYOOOZZZVVVVVVVVVVVVVVVVVVXXXXXX
DTTTDHHHQHHHBBBBMBIIIIIIIWWBWWWFXXXXXXXXNNNNNUKKUUUCCCCCCCCCCCAAAASOOVYGGGYYYYYYYYYYYOOOSSSSSSSSBBBBBBVVVVOOOOEOOFZZVVVVVVVVVVVVVVVVVVXXXXXK
DDTDDDJHJJBBBBBBBBIIIIIIWYWWWWWWEXXXXXXXNQUUUUUUUUUUCCCCCCCAAAAAAOOOOOOGGGYYYYYYYOOOOOOOSSSSSSSSBBBBBVVVVVOOOOOOOOOZVVVVVVVVVVVVVVVVVVXXXXXK
DDDDJDJJJBBBBBBBBBBBIIIWWYWWWWWWEXXXXXXDNNUUUUUUUUUUUUUCCCCAAAAAAAAOOBOGGGYYJYYYYYNOOOOOEESSSSSBBBOOOOOVOOOOOOOOOOORVVVVVVVVVVVVVVVVVVXXXXXX
DDDDJDJJJBBZZBBBBBBBBBIWWWWWWWWWXXXXXXXXNNUUUUUUUUUUUUCCCCCAAAAAAAOOOOOGGGGJJYYYYYNONNOOOESEBBBBBBOOOOOOOOOOOOOOOOORVVVVVVVVVVVVVVVVVVXXXXVV
DDDDJJJJJBBBBBBBBBBBBYWWWWWWWWWWKXXXXXXXNNXXUUUUUUUUUUCCCCCAAAAAAAOOOOGGGGGCJJYYYNNOONOOEEEEBBBBBBBBOOOOOOOOOOOOORRRVVVVVVVVVVVVVVVVVVTXXXVV
DDDJJJJJJHBBBBBBBBBBYYQQQWWWWWWKKKXXXXXXXXXXUUUUUUUUUUUCECCAAAAAAAAGOOGGGGCCCJJNNNNNNNNNNNNNNBBBBBBBXXXOOOOOOOOOORRRVVVVVVVVVVVVVXXXXXTLXXVV
DDDDDJJJJHBBBBBBBBBBBQQHHWWWWWWWKXXXKKXXXUUUUUUUUUUUUUEEECAAAAAAAAGGGGGGGGCCCCNNNNNNNNNNNNNNBBBBBBBBXXXXXXOOOOJOORRRVVVVVVVVVVVVVXTXXXTLXXVV
DDDDDJJJJBBBBBBBBBBBQQQNWWWNWWWKKKXKKKKKXUUUUUUUUUUUUUUEEAAAAAAAAAGGGGGGGGCCCCCNNNNNNNNNNNNNBBBBBBBBBXXXXXXOXCXRRRRRVVVVVVVVVVVVVTTTTTTTVVVV
DDDDVVJJXXBBBBBBMBBBQQQNNWWNWWWWKKKKKKKKXLUUUUUUUUUUUUUEEAAAAAAAAAAGTGNCCGCCCCCCCNNNCCVXNXBBBBBXBBBXXXXXXXXXXXXXRRRRVVVVVVVVVVTTTTTTTTTMEEVV
VDVDVVVXXXBBBBBBBBBQQQQNNNNNNWWWWKKKKKKKXXVVVVUUUUUUUUUEEEEEEEEAAAATTGNNCCCCCCCCCCCCCCCXXXXBXXXXXXXXXXXXXXXXXXXXRRRRRRBBBBTTTTTTTTTTTTTMEEVV
VVVVVVVXXBBBNBBBQQBBQQQNNNNNNNNNVKVKKKKVXXVVVVUUOUUUEUEEEEEEDEEEWCCCTGNNNCCCCCCCCCCCCCCXXXXXXXXXXXXXXXXXXXXXXXRXRRRBBBBBBBBTTTTTTTTTTTTEEEEE
VVVVVVVVXXQBNBQQQQQQQQQQNNNNNNNNVVVKKKKVVVVJIIIIIIIIIIIIEEEEEEEECCCCCNNNCCCCCCCCCCCCCXXXXXXXXXXXXXXXXXXXXXXXRRRRRRBBBBBBBBBTTTTTTTTTTTTEEEEE
VVVVVVVXXXQQQQQQQQQQQQQQNNNNNNNNVVVVKVVVVJJJIIIIIIIIIIIIEEEEFFCCCCCCCCOOCCCCCCCCCCCCXXXXXXXXXXXXXXXXXXXXXXXXRRRRRBBBBBBBBBBTHHHHHHHTETTEEEEE
VVVVVVVXXQQQQQQQQQQQQQQQQNNNLNNNNVVVVVVVJJJJIIIIIIIIIIIIEEEFFFCCCCCCCOOOOOCCCCCCCCCCXXXXXXXXXXXFXXXXXXXXXXXXXRRRRRBBBBBBBBBTHHHHHHHTETIEEEEE
VVVVVVVVXQQQQQQQQQQQQQQQTTTTOOOOVVVVVVVVJJJJJJEIIIIIIIIIEEFFFFFFFCCCCOOOOOFCCCCCCCCCCCXXXXXXXXXXUXXXXXXXXXXXTTRRBBBBBBBBBVVTHHHHHHHEEEEEEEEE
VVVVVVHHQQQQQQQQQQQQQQQQQTTTOOOOOOVVVVVVPJJJJJJIIIIIIIIIEEFEEEEFZCCCOOOOOFFCCCCCCCCCCXXXXXXXXXXUUXXXXXXXXXXXTTTRRBBBBBBBVVVTHHHHHHHEEEEEEEEE
VVVVVVHEQQQQQQQQQQQQQQQQTTTOOOOOOOVVVVVPPJJJJIIIIIIIIIIIEEEEEEZZZZCOOOOOOOFCCCCCCCCCCCXXXXXXXXXUQXTTXXXXXXXXTTTTRRBBBVVVVVVTHHHHHHHEEEEEEEEE
VVVVVREETEEEEQQQQQQQTTTTTTTTOOOOOOVOVVVPPJJJJIIIIIIIIIIIEEEEEEEZZZZZOOAAOAFCCCCCCCCCCCXXXXXXXXQQQQQTTTXXXXXTTTTTRRRBBBBVVVVVHHHHHHHEEEEEEEEE
VVVVDEEEEEEYQQQQQQKQKKKKTTOOOOOOOOOOOOOPPPPJJIIIIIIIIIIIEEEEEEZZZZZZAAAAOAFPCCCCCCCDFXXXXXXXXQQQQQQTTTTTTTTTTTTTTTRBCCVVVVVVVHHHHHHTTEEEEEEE
VVVVDDEEEEEEHQQQQQKKKKKKKOOOOOOOOOOOPPPPPPPJJJJIIIIIIIIIEEEEEEEEIZZZZZAAAAADCCCCDCCDXXXGXXQQXQQQQQTTTTTTTTTTTTTTTTTTCCCVVVVVVHHHHHHTEEEEEEEE
VVVDDDEEEEEYHQQQQQQKKKKKKKKOHOOOOOOPPPQPPQQJQQQIIIIIIIIIEEEEEEEEZZZZAAAAAADDDDDDDCCDDXXXXXQQQQQQQQTTTTTTTTTTTTTTTTCCCCCVVVVVVVVVVTTTEEEEEEEE
VVVDDEEEEEYYYYYYQYGKKKKKKKKKOOOOOOOPPQQQQQQQQQQQQQPPEEEEAEEEEEEEZFZZKAAAADDDDDDDDDDDDDDHHHQQQQQQQZATTTTTTTTTTTTTTTCCCCCVVVVVVVVVVVEEEEEEEEEE
VVVDEEEEEEEYYYYYQYGKKKKKKKKKKOOOOMPPPQQQQQQQQQQQQPPPPLELAEEEEEEEEFKKKAADDDDDDDDDDDDDDDDAHHQQQQQQQZANTTTTTTTTTTTTTTCCCVVVVVVVVVVVVVEEEEEEEEEE
LVVDEEEEEEYYYYYYYYYKKKKKKKKKKOOOMMMMPPQQQQQQQQQQQPPPPPELAAAEEEEPEFKKKDDDDDDDDDDDDDDDDDDAHHQQQQQQQZATTTTTTTTTTTTTTTCCCVVVVVVVVVVVIEEEEEEEEEEE
VVVEEEEEEEYYYYYYYYYYYKKKKKKKKKMOMMMMPPPQQQQQQQQQQQPPAPAAAAAMEEEPPKKKKDDDDDNDDDDDDDDDDDAAQQQQQQQQQAATTTTTTTTTTTTTTCCCCVAVAVVVVVVVVUUUUCCPPEEE
RRRRRRREEYYYYYYYYYWYYYYKKKKKKPMMMMPPPQPQQQQQQQQQQQQPAAAAAAAEEEPPPKKKDDDDDTNDPCDDDDDDDDAAAQQQQQQYQQAAATAATTTTCTTTCCCCAAAAAAAVVVVVVVUCCCPPCCCC
RRRRRRRRRRYYYYYYYYYYYYYKKKKKKKBMMMPPQQQQQQQQQQQQQQAAAAAAAATTEEPPKKKKKKKTTTTCCCCDDDDAAAAAAQQQQQQYQYAAAAAATTTTCCCCCCCAAAAAAAAVAAVVPCCCCCCCCCCJ
RRRRRRRRRYYYYYYYYYYYYYYKKKKKKKKMMMCCWWQQQQQQQQQQQAAAAAAAAAEEEEKKKKKKKKKTTTTCCCSDDDDDAAAYYGQQQQYYYYAAAAAAAAATCCCCCCCCCAAAAAAAAAAACCCCCCCCCCCC
RRRRRRRRRYYYYYYYYYYYYYYKMMKKMKMMMMCCCCCQQQQQQQQAAAAAAAAAAAAAAADDKKKKKKTTTTCCVCCCCCDDDAAYGGQQYYYYYYAAAAAAAAATAACCCCCCCAAAAAAAAAAAACCCCCCCCCCC
RRRRRRRRRYYYYYYYYYYYYYYKKMMMMMMMCCCCCCCQQQJQQQAAAAAAAAAAAAAADDDDDKTVKTTTTCCCVCCCCCCDDCAAGGGGGYYYYAAAAAAAAAAAAACDDDDCCAAVAAAAAAFACCCCCCCCCCCC
RRRRRRRRRYYYYYYYYYYYYYYYMMMMMMMCCCCCCCCQAIISQQQAAAAAAAAAAAAAADDDDKTTTTTTTCCCCCCCCCDDDCAAGGGGGYYYYAYAAAAAAAAACCCCDDDCCDDVAABAAAACCCCCCCCCCCCC
TRRRRRRORYYYYYYYYYYKYTTMMMMMMCCCCCCIIICCIXISQQAADAAAAAAAAAAAADDDDTTTTTTTTCTTCCCCCCCCCCAGGGGGGYGYYYYYAAAAAAAAACCCDDDDDDDDDAAAAAAACCCCCCCCCCCC
TTRRRROOOYYYYYYYWYYTYTTTTMMMMMCCCCCCCIIIIIIQQQADDDDAAMAAAAAADDODOOTTTTTTTTTCCECCCCCCCCGGGGGGGGGGGYYYYYAAAAACCCCDDDDDDDDDDAAAAAACCCCCCCCCCCCC
TTTRTROOOOYYYYYYTTTTTTTTTTMMMMCCCCCIIIIIIIIQZZDDDDAAMMAAAAADDOOOOTTTTTTTTTTCCCCCCCCCCCGGGGGGGGGGGGGAAAAAAAAACCDDDDDDDDDDDCAAAAAACCCCCCCCCCCC
TTTTTOOOOYYLLYLYLTTTTTTTTTMMTTCZCICIIIIIIIIIDDDDDMMMMMMAAAOOOOOOOOJTTTTTTTTTTCCCCCCCCGGGGGGGGGGGGGAAAAAAAAACCCDDDDDDDDDCCCCAACCCCCCCCCCCCCCC
TTTTTOOOOOOOLLLLLTTTTTTTTTTTTTCIIIIIIIIIIIIIDDDDDDDMMMMMAAOOOOOOOOOTTTTTTTTCCCCCCCCCGGGGGGGGGGGGGNNNAAALACACCDDDDDDDDDDCCCCAACCCCCCCCFFCCCCQ
TTTTTTOOOOOOOLLLLLLATTTTTTTTTTIIIIIIIIIIIIINNNNNNDMMKKMNOOOOOOOOOOOOOOTTTTTTCTCSCCCSGGGGGGGGGGGOOONNNAACACCCDDDDDDDDDDDDCCCCCCCFFFFFFFFFFCCQ
TTTTTTOOOOOOOLLOLLLAATTTTTTTKTIIIIIIIIIIIIINNNNNNDUUKKKOOOOOOOOOOOOOOOTTTTTTTTCSSCCSDGGGGGGGGGGGOOONNACCACCCDDDDDDDDDDDDCCCCCCCCFFFFFFFFFFFF
TTTTTOOOOOOOOOOOLAAAATTTTTKKKTIIIIIIIIIIIIINNNNNNUUUUUUOOOOOOOOOOOOOOOOTTTTTTTSSSSSSDDSSGGGGFGGGOOOCCCCCCCDDDDDDDDDDDDDDCCCCCCCFFFFFFFFFFFFF
TTTTTOOOOOOOOOOOOAHAATATKKKKTTTKIIIIIISIIEEEEUUUUUUUUUUJOOOOOOOOOOOOOOTTTTTTTSSSSSSSSSSFFFFFFFFGGOOOOACCCCCDDDDDDDDDDDDCCCCCCFFFFFFFFFFFFFFF
TTTTTOOOOOOOOOOOOOAAATAKKKKKTKKKEEIIIEEIIEEEEEUUUUUUUUUJJOOOOOOOOOOOOOTTTTTTTTSSSSSSSSFFFFFFFFGGOOOOOCCCCCCIIDDDDDDDDDDCCCCCCFFFFFFFFFFFFFFF
TTTTTTOOOOOOOOOXOOAAAAAAAKKKKKKKKKEEEEEIIIIEEEEUUUUUUUUPOOOOOOOOOOOOTTTTTTTXTSSSSSSSSSSSFFFOOOOOOOOOOOCCCICIIDDDDIDDDDDDDDCCCCCFFFFFFFFFFFFF
TTTTTTOOOOOOOOOOAAAAXXXAKKKKKKKKKKEEEEEEEEEEEEEUUUUUUUUPOPPOOOOOOOOTTTTTTTFSSSSSSSSSSSSSFFOOOOOOOOOOOOCCCIIIIIDDDIIIDTDDDCCCCCCFFFFFFFFFFFFF
TTTTTTOOOOOOOOOOXAAAAAXXKKKKKKKPPEEEEEEEEEEEEEEEEUUUUUPPPPPPUUUUOUUTTTTTTTFFFBBSSSSSSSKXFFFOOOOOOOOOOOCCIIIIIIIIIIIIITTDDFHHCHCHHFFFFFFFFFFF
TTTTTTTOOOOOOOXXXXXXXXXXXKKKKKPPEEEEEEEEEEEEEEEEEPUUUPPPPPPGPUUUUUUTTTTTTTTFFFFSSSSSKKKXFFFXOOOOOOOOOOOOOIIIIIIIIIIIITTTTHHHHHHHHFFFFFFFFFOF
TTRRTTTOOOOQOOXDDXXXXXXXXXKKPPPPEEEEEEEEEEEEEEEEEPPPPPPPPPPPPPUUUUURRTTTTTBFFFFFSSSSSKKXXXXXOOOOOOOOOOOOOIIIIIIIIIITTTGGTHHHHHHHHHHFFFFFFFFF
RRRRRRTTOOOQQDXXDDXXXXXXXXKKPPAAEEEEEEEEEEEEEEEEEEPPPPPPPPPPPPUUUURRRRRTTBBFFFFVFSSSSSKXXXXXXOOOOOOOOOOOIIIIIIIIIIITTTGGEEHHHHHHHHHFFFFFFFFF
WWRRRRTTTTOOQDDDDDXXXXXXXXKKPPAAAAENNEEAEEEEEEEEEEPPPPPPPXPPHPUUUURRRRRTTBBBFFFFFSSSSSXXXXXXXXOOOOOOOOOIIIIIIIIIIIIIIGGGEHHHHHHHHHFFFFFFFFCC
WWRRRRRTRRROQQQDDDDDDXXXXXXXXPAAACNNNEEAAAEEEEEEEQQQQPPPXXPXXXXXXRRRRREETTFFFFFFFFFFSKXXXXXXYXOOOOAAOOOOOIIIIIIIIIIITTGGHHHHHHHHHHFFFFWWFCCC
WURRRRRRRRRDDQDDDDDDDXXXXXXXPPAAANNNNNAAAAAEEELLPQQQQPPMXXXXXXXXXRRREREEEEFFFFFFFFUSSSXXXXXXXXXXXOAAOFFFFIIIIIIIIIITTTGGGHHHHHHHHHFFZFNNCCCC
UUUUURRRRRRDDDDDDDDDDDDXXXXXPXAAAANNAAAAAAAALELLLQQQQPMMMMMXXXXXXRRREEEEEEEEFFFFFFUSSUUXXXXXXXXXOOAAOFFAFIIIIIIPPPPPPPPGGGHHHHHHHHHHHNNNNNCC
TTUUUURRRRDDDDDDDDDDDDDDXXXXPXAAAANNAAAAAAOOLLLLLQQQQMMMMMMPPXXRRRRRREEEEEEEEEFFFUUUUUUUXXXXXOXOOOAAAAAAAIIIIIIPPPPPPPPPPPGHHHHHHHHHINNNNNCC
TTUUURRRNRRRNDDDDDDDDDXXXXXXXXXXAAAAAAAAAAOLLLQQQQQQQMMMMMPPPXRRRRRRREERRRREEEEKUUUUUUUCXXOOOOOOOAAAAAAAACCIXHHPPPPPPPPPPPGHHHHHHHHHINNNNNNC
TTUNNRRRNRNRNNDDDDDDDDDDXHXXXXXXAAAAAAAAAQQQQQQQQQQQQMMPPPPPPXRRRRRRRRRRRRREEEKKUUUUUUUCOOOOCOOOOAAAAAAAACXXXXSPPPPPPPPPPPGHHHHHHHHHHNNNNNNN
TTTTNNNNNNNNNNDDDDDDDDDDXHXXXAAAAAAAAAAAAQQQQQQQQQQQQOMPPPPPPXRRRRRRRRRRRRKKKEKKKUUCCCUCCCCCCOOOOAAAAAALACXWXXSISZZPPPPPPPGGHHTHHTHNNNNNNNNN
TTTTNNNNNNNNNNNNDDDDDDDDDDAAAAAAAAAAAAAAOQQQQQQQQQQQPPPPPPPPPVRRRRRRRRRRRKKKKKKKUUUCCCCCCCCCOOOOOOHAAAAAACXWWXSSSZZPPPPPPPKKKTTTTTHHNNNNNNNN
TTTTNNNNNNNNNNNNDDDDYYYYDDDAAAAAAAAAAAAAHHOORRROOQQQOPPPPPPPPPRRRRRRRRRRRRKKKKKKUUUCCCCCCCCCCCOOOOHHAAAAAHHWWWHHSSZPPPPPPPGTTTTTTTTNNNNNNQQQ
TTTTNNNNNNNNNNNDDYDYYYYYYAAAAAAAAAAAAAAHHHORRRRROOOOPPPPPPPPPPPPRRRRRRRKKKKKKKKKUUCCCCCCCCCCCCOOOHHHHHAHHHHWWHHSSSSPPPPPPPTTTTTTTTNNNNNNQQQQ
TTTNHNNNNHHHHNNDYYYYYYYYYAAYYAAAAAAAAAHHHRMMRRRROOOPAPPPPPPPPPPPPKRRRRRRKKKKKKCCUUCCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHSGPPPPPPPTTTTTTTTTNNNNNNNNQ
TTTNNNNNNHHHHHHDYYYYYYYYYKKYYYBYAAAAAAHHMRMMMRRRRRPPPPPPPPPPPPPKPKRRRRRIKKKKKKCCCCCCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHGPPPPPPPTTTTTTTTTTNNNNNNNN
TTNNTNNNNHHHHHHYYYYYYYYYYKKYYYYYAAAAAAHMMMMMMRRRRRRRRRPPPPPPLPPKKKKRRRRIIKKKKKKCCCCCCCCCCCCCCCLLLCCHHHHHHHHHHHHHHHGPPPPPPPTTTTTTTTTTTNNNNNNN
TTTTTTNHNHHHHHYYYYYYYYYYYKJYYYYYAAAAAHHMMMMXRRRRRRRRRRRPPPPPRKKKSSSSRRRRSSSKKKKKCCCCCCCCCCCCCCCCCCCHHHHHHHHHHHXXXXXXXXUUUTTTTTTTTTTNNNNNNNNN
NNNTNNNHHHHHHHHYYYYYYYYYYYYYYYYYYAHAHHHHHMMXXRXRRRRRRRRRPPRRRRRKSSSSSSSSSSSKKKKKKCCCCCCCCCCCCCCCCHHHHHHHHHHHHHHHXXXXXUUUUTTTTTTTTTTNNNNNNNNN
NNNNNHHHHHHHHHHYYYYYYYYYYYYYYYYYYHHHHHHHHXXXXXXRRRRRRRRRRPRRRRRKSSSSSSSSSSSSKKKKQCCCCCCCCCCCCMCCHHHHHHHHHHHHHHHHXXXXXXUUUTTMTTNNNTTNNNNNNNNN
NNNNNNNNHHHHHHHYHYYYYYYYYYYYYYYYYHHHHHHHXXXXXXXRRRRRRRRRRRRRRRRKSSSSSSSSSSSSKKKKQQQQCCQCQQQQQHHHHHHHHHHHHHHHHHHXXXXXXXXXXTTNNNNNNNNNNNNNNNNN
NNNNNNNNHHHHHHHHHYYYYYYYYYYYYYYYYYYHHHHHXXXXXXXRRRRRRRRRRRRRRRSSSSSSSSSSSSSSKKKKQQQQQQQQQQQQQQHHHHHHHHHHHHHHHXXXXXXXXXXXXXTNNNNNNNNNNNNNNNNN
"""

TEST = """
AAAA
BBCD
BBCC
EEEC
"""

TEST2 = """
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
"""

TEST3 = """
AAAAAA
AAABBA
AAABBA
ABBAAA
ABBAAA
AAAAAA
"""

TEST4 = """
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
"""

TEST5 = """
ZZZZZZZ
ZZZZZZZ
ZZDDZGZ
ZZZZGGG
ZZZZGGG
"""

# with open("sam.txt", "r") as f:
#     PROD = f.read()


x = TEST5
x = PROD
x = x.strip()

# Data in differnt formats for quick access
text = x
lines = x.split("\n")
grid = [list(line) for line in lines]

# grid = list(zip(*grid))

result = 0

# ok we need to find all the differenet "regions"
# then find their perimeter <- wtf?
# and find their area <- this is just length of the region if region is a list of cells


regions = []
# points we have already added in a region
mapped = set()
for i in range(len(grid)):
    for j in range(len(grid[0])):
        if (i, j) in mapped:
            continue

        # ok this is a new region. what is the key?
        key = grid[i][j]

        region = []

        # lets flood fill up/down/left/right and add to region
        q = [(i, j)]
        while q:
            x, y = q.pop()
            if (x, y) in mapped:
                continue

            if grid[x][y] == key:
                region.append((x, y))
                mapped.add((x, y))

                # add the neighbours
                if x > 0:
                    q.append((x - 1, y))
                if x < len(grid) - 1:
                    q.append((x + 1, y))
                if y > 0:
                    q.append((x, y - 1))
                if y < len(grid[0]) - 1:
                    q.append((x, y + 1))

        regions.append((key, region))

# print(*regions, sep="\n")

from copy import deepcopy

# for each region, we need to find the perimeter
for key, points in regions:

    all_other_points = []
    for _, other_points in regions:
        if other_points != points:
            all_other_points.extend(other_points)

    # perimeter = 0

    # # Create a set of edges for the region
    edges = []
    for x, y in points:

        edges.append(((x, y), (x + 1, y)))

        edges.append(((x + 1, y), (x + 1, y + 1)))

        edges.append(((x + 1, y + 1), (x, y + 1)))

        edges.append(((x, y + 1), (x, y)))

    cleaned_edges = [
        # every edge that only appears once
        edge
        for edge in edges
        if (edges.count(edge) + edges.count((edge[1], edge[0]))) == 1
    ]

    edges = cleaned_edges

    horizontal_edges = [
        list(sorted(edge)) for edge in edges if edge[0][0] == edge[1][0]
    ]
    vertical_edges = [
        list(sorted(edge, key=lambda x: x[0]))  # sort by x component of each edge
        for edge in edges
        if edge[0][1] == edge[1][1]
    ]

    horizontal_edges.sort(key=lambda x: x[0][1])
    raw_horizontal_edges = deepcopy(horizontal_edges)
    vertical_edges.sort(key=lambda x: x[0][0])

    # print("Vertical Edges are")
    # for edge in vertical_edges:
    #     print("\t", edge)
    # print(vertical_edges)

    # we need to collpase these edges together

    # collapse horizontal edges
    while True:
        # print("HHHHH", horizontal_edges)
        new = []
        marked = [False] * len(
            horizontal_edges
        )  # this indicates if we used this to do something
        for i in range(len(horizontal_edges)):
            if marked[i]:
                continue

            for j in range(i + 1, len(horizontal_edges)):
                if marked[j]:
                    continue

                if horizontal_edges[i][1] == horizontal_edges[j][0]:

                    # if there is a perpendicular edge to either in vertical, we cant collapse
                    x1, y1 = horizontal_edges[i][1]
                    x2, y2 = horizontal_edges[j][0]

                    if any(
                        ((x1 - 1, y1) in edge and (x1, y1) in edge)
                        or ((x2 - 1, y2) in edge and (x2, y2) in edge)
                        for edge in vertical_edges
                    ) or any(
                        ((x1 + 1, y1) in edge and (x1, y1) in edge)
                        or ((x2 + 1, y2) in edge and (x2, y2) in edge)
                        for edge in vertical_edges
                    ):
                        # print("CANT COLLAPSE", horizontal_edges[i], horizontal_edges[j])
                        continue
                        new.append(horizontal_edges[i])
                        new.append(horizontal_edges[j])
                        break

                    marked[j] = True
                    marked[i] = True

                    new.append((horizontal_edges[i][0], horizontal_edges[j][1]))
                    break

            if not marked[i]:
                new.append(horizontal_edges[i])

        new.sort(key=lambda x: x[0][1])
        if new == horizontal_edges:
            break

        horizontal_edges = new

    # collapse vertical edges
    while True:
        # print("VVVVV", vertical_edges)
        new = []
        marked = [False] * len(vertical_edges)
        for i in range(len(vertical_edges)):
            if marked[i]:
                continue

            for j in range(i + 1, len(vertical_edges)):
                if marked[j]:
                    continue

                if vertical_edges[i][1] == vertical_edges[j][0]:

                    # if there is a perpendicular edge to either in horizontal, we cant collapse
                    x1, y1 = vertical_edges[i][1]
                    x2, y2 = vertical_edges[j][0]

                    print(
                        "Trying to merge vertical edges",
                        vertical_edges[i],
                        vertical_edges[j],
                    )

                    if any(
                        ((x1, y1 + 1) in edge or (x1, y1 - 1) in edge)
                        and ((x1, y1) in edge)
                        for edge in raw_horizontal_edges
                    ):
                        print("CANT COLLAPSE", vertical_edges[i], vertical_edges[j])
                        continue
                        new.append(vertical_edges[i])
                        new.append(vertical_edges[j])
                        break

                    marked[j] = True
                    marked[i] = True

                    new.append((vertical_edges[i][0], vertical_edges[j][1]))
                    break

            if not marked[i]:
                new.append(vertical_edges[i])

        new.sort(key=lambda x: [x[0][1]])

        if new == vertical_edges:
            break

        vertical_edges = new

    # print("Collapsed Vertical Edges are")
    # for edge in vertical_edges:
    #     print("\t", edge)

    # we need to find how many unique sides this region has
    sides = len(horizontal_edges) + len(vertical_edges)

    # print(f"Region {key} has a {sides} sides")
    # print(*edges)

    # # use shapely and matplotlib to plot the edges
    if key == "Z" and False:
        import matplotlib.pyplot as plt
        from shapely.geometry import LineString

        fig = plt.figure(1, figsize=(5, 5), dpi=90)
        ax = fig.add_subplot(111)

        # Convert edges to a list of coordinates
        edge_coords = []
        for edge in horizontal_edges:
            (x1, y1), (x2, y2) = edge
            edge_coords.append([(x1, y1), (x2, y2)])
        for edge in vertical_edges:
            (x1, y1), (x2, y2) = edge
            edge_coords.append([(x1, y1), (x2, y2)])

        # Plot each edge as a separate line
        for edge in edge_coords:
            xs = [p[0] for p in edge]
            ys = [p[1] for p in edge]
            ax.plot(
                ys,
                xs,
                # color="#6699cc",
                color=f"#{random.randint(0, 0xFFFFFF):06x}",
                alpha=0.7,
                linewidth=3,
                solid_capstyle="round",
                zorder=2,
            )

        # # show
        plt.show()

    # result += perimeter * len(points)

    print(
        f"A region of {key} plants with price {len(points)} * {sides} = {sides * len(points)}"
    )
    result += sides * len(points)

print(result)