leetcode_c_111.cpp

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long int ll;

	void shortest_distance(vector<vector<long long>>&matrix) {
        
		long long n = 26;
		for (long long i = 0; i < n; i++) {
			for (long long j = 0; j < n; j++) {
				if (matrix[i][j] == -1) {
					matrix[i][j] = 1e9;
				}
				if (i == j) matrix[i][j] = 0;
			}
		}
		for (long long k = 0; k < n; k++) {
			for (long long i = 0; i < n; i++) {
				for (long long j = 0; j < n; j++) {
					matrix[i][j] = min(matrix[i][j],
					                   matrix[i][k] + matrix[k][j]);
				}
			}
		}




		for (long long i = 0; i < n; i++) {
			for (long long j = 0; j < n; j++) {
				if (matrix[i][j] == 1e9) {
					matrix[i][j] = -1;
				}
			}
		}
	}
    long long minimumCost(string s, string t, vector<char>& o, vector<char>& c, vector<int>& cost) {
//         s="afxpetvcptrumumyuatmmbfyrrsaqaupipktubuchawwibtnyygcsbofkcpnorsunwayzlngcuonavgkmrzitvqfvngzdgendpcjowkguhqdmyeglghbfowgossqjjgmfqtgavlzgvliuudsljszvjdzowoqxvopyekpymoiojemmcpurqwppgbaigjfdriznjtfqbkrealsywnunmplgsszdgsdlipstuqzmtfbbxfovneqiwerdkuxsnxlqrbmiwiwkbibdrcqcxweiskxwpervkubgsgifnlzggnnhcpxzdnbmthushfkfrubiuvrjrbzukitelstlmsixhuntobvdfjknigbmlfcixnjepiairhtgayxxezgtcqnaiatcubdvhokmbcpuveitwmvcsjehyesdyizfqfgzjfzzqttahnkexrpxhkjtiqmhfkbkjxptwasrwsxnsxghmlkgkaldvwadobirvwmgkmtfavqstnbmfsntaeohejmvqmeytjllyqsgwdeorqxlwaitpekexxmxundqdosrqzgcenasriciwwsfduofzzfzbijujsgyezhgrabkvrbvlxsjrtvczwesntqvyxnyatfztaraqchrvqiagayjnrnjleamktfmvexjczshhgpdiavdynvtwgvbofarglfvecvwohguykjxmmjoelhjfihvvgqrcobpdfmgtmfyhtjvgovmlhldydigurjyzemblpitwkwmlsvvsbejfrvbdghwdabupxqytpdaylsupeswdbmstrbplkpnbpdfjsvrqsdhbuohjtbaaamtbqrepqrjxdxjgsxwsqmdnutvebwbtahvipvycurmmxosedkjuobbwtlsrczhylvgojuunuzrxolmbpnbiavevtewhxdxytjwzdmvokljrxdblwlhqtpvwatoofqgoknhjhsbrfmulydgyhniirrhbdpbptrrrkbrafpdgdozcbsgfplgiziqmlzslekehhfzvpfjtbngytzgtkeszwubpyywdemyrhyjifekfoarghujmhobuizufzijpmddrwuqcpbouzuogfsqvihtgrwnmntizuzmgijvokbimgwocrdthgqsxdcbkwxfwldpfijzpnnpemiqbwmiwlcvrhkfmcrtagidxdcdjxhelpzedbopmunetvwsjuhjmlriyzqeptvsumxrxqxtfnlqhjqeokkoussiqztsddcladlwkvyvktndbahykshoqqahmjknmfbscutqxgdqnggvldzeobqfepnqbfcmmnaxupuufbvdqvrufcixodugcpsiirwgrjxnjqolcohmzpznpqfnshwewmdwbdlulknjuvpaweubszhiehgoglctxhwupjvtmprvnlwugomroumqlzlnzuwcmwujmvdmgtkwbomveqetfhsoiexnamqicskbkwmzirjkcwcaxbhdbxskhbhpqbydsbpnlnarxdfyucfzgrzdiyykxyrdlhubyphvkvafgqobdxobbxrlnnpjtvaqqxxnhpoibduwxgjljbfyjzevuzkcsicsirpckcnibepjfmltsevohepahtmwspfsminncfczimiceelygerhgtsczunrfhdmtiygmcgsqrlegtvdofbrehltvnutnyegtljzjifmzoejvprntqaacyooeijxkbkarcyrjhthbbregnomlawsdqwmxqktiqzbittxaeippyjkoeufochpqtiwrvqxurlnxpgzdrlratfvvknrgkioosxfjcjtqaqcdtseuejwdizmsaqeogwdgbrcdmhiwzqnchvaeqcslpagvyzrdawzjhhorzrccsipytlrdvmwiohqxdnhantupbvinasnlcdbqwagcipbwwbbcbujnfawozpyxviqmqjtsewilsyesxmyljjtobgiocsgcjjmavuezyesccqctpfilukdflsknkwbecmfbphakoajzdi";
// t="bxocjldpthbdzazbjnmwkiwnszotuhsjwcmqgjzcucbarnaurzygnnfipybbumkjkxslsbedmtmmwsmyypbwpalnlpjygovydzdsfvcfiqjrolctfapwodsmkmgqgkbkgxzscdifxngpipsboynpbiswfwpjuwjiuifcehsfqwhlwhglazkjrirvklieczwgnjylgtlsedstjyymiqzbyynxfufrazzinmfwjfkexeswzajiikwubfmqcfwvrtkbqbggtwjancnoxafmmamsvapdyoaqecllspjlmrpntuglltmhkvvfbprhjosgcnrqydqhpsmhrclqxlittolfzdijbhiymbzkrxvmlrfcvkpsnlzhayzorbspmrhyjwdtnehdctqszuvultxjxrifxlqjohikfqpxdeykgwbufmxxonteewskkcjxigpeahaztrucabehgpgxldtdycgetcdykxfsmjposdabadqiebdpuqkwkwoiioggxgdenmldchgchajrqkhnujnaxguvavdcwcgwnkgmcbaudbwrnonnmwkxhszsorhmsbaftkokqtdqpckaedqubajorjlrcglplmiumorstyjbeehijvazarixxycoupdcggimlflalphjgkxifujiibxhikrfjcinbwueurzlyeosfoxnueafyeaziopwozksxlrkmsvhyvqeqejybffroojalqozpobviqldyeacwusdteuqvxsoqmlaaswiebzzdaippddzogxekaubqkssbxckbcahjvfxjwbkbptmvfvkrektcnqqymeqhequxjnvpnrmrbxszjhqczcvrrlnrbywizizzkdtijfbmauzrgtcgkqtpivzdlbszgpjxnjhcpnpixukrtocmafyvyhmjtjzgtfrrlscbshbtogxqegvpsnqneffxyedmwgyrzzyvqvpfenlmkfqgdoroviplodwdbkhvmjkgoxpmtgihgjihfvqsittqmiogipdqtorgzkmxujkljhivaskhnvsqucepribcfodrkwusnvdecqbxtgoeaofmxovukrsogtqrxitikbwjfxgmwkmtjoxmuvpyitxsfmikbvdljdkomihadvwgovsmqvdfngjmkloqdbznuwhwmeujtkyxptfjxpfefpfkumwmaapxxyxuafprhkeiowmxnhjjslpsssjxmgvcsidcncrpibknnhkwrxfzeiydgijyelmxeevengaurhugwxeitbumonjivwrpkbgbacczqjjuyxizemgoekpobmojvyjkzrfruvyadxmnjhrhjbmymauzjlwfdufpszccozwayxmaxdgrzxroufdiwdwqtafhtojkvfsxkhavpdllawxvhwfwewdyjfpxabrnfdfuwnuomqvzvuyjijhetzfgazmkdsosorbyixxzldbkzkimyhflmjpshazdxrockmcgkuctezqnzwybbrmsnzjjxublhuqgeudcfklumzugjpuvmwegtdsiwkblsktjldwjchikwdxckbvznuaxgmshjuljveqidpsqmtgownceackneuoapvkzmrpodcdfzjfxxqhnxighmabtqmwtjhikoqfpbbbvpyvqkiieatjvcrcyepxhpnmsskpfzjchhawaebyqtaegxzltgqiieathhpnybqosxzauyivyyrtdymgpewjlclkxjkmizajugmfiysouzsdcfvkftwbsiajoixciajxpxnwbrcgxcpnxbsvvoexogtmcomctfyimwgptccyejxnbbxpuebhaiczhsmnblzpqakyvflsbijueyloplouhfnnjyxmmpezjsqsywtlkvzdzraegjolywdnftqmlewlntobyfyrigyaeinqggdtkobsqdxgbnimtlywurwszijgowatbodcajoqtttgxpiyifemhbfpyrwisgpuhsnsncigprugthdsyigtuashwkrbwtjlcemp";
// o={'f','x','p','e','t','v','c','p','r','u','m','u','y','u','a','t','m','m','f','r','s','q','a','u','k','t','u','u','h','w','i','t','n','y','g','c','s','b','o','f','c','p','n','o','r','s','n','w','a','y','z','l','n','g','u','n','v','k','m','z','i','v','q','v','n','g','z','d','g','e','n','c','j','w','g','u','h','m','e','g','l','g','h','f','w','s','j','j','g','t','g','a','v','l','u','d','j','z','j','z','o','q','x','v','p','y','e','k','m','o','i','o','j','m','c','p','u','w','p','p','g','b','a','g','f','d','z','t','f','b','k','a','s','y','w','u','n','m','p','d','g','s','d','l','s','q','m','t','f','b','b','x','f','v','n','q','d','s','n','l','q','b','m','i','w','k','i','b','d','r','q','c','x','w','i','s','x','p','e','r','i','l','z','g','h','c','x','d','t','h','s','f','k','f','b','i','u','v','r','b','z','k','t','e','s','l','x','o','b','m','f','c','x','j','p','i','i','h','a','e','g','c','q','c','u','b','c','p','v','e','t','v','j','h','z','f','q','f','g','z','z','a','h','n','k','x','x','h','k','j','t','q','m','h','f','k','b','j','a','s','w','s','n','h','m','k','l','d','d','o','b','i','r','k','a','s','b','e','o','h','q','e','y','l','l','s','g','e','r','w','a','i','e','x','x','u','q','o','q','e','i','i','w','u','o','z','z','u','j','s','y','z','g','a','k','b','v','c','w','e','n','t','x','y','z','c','r','n','j','e','m','v','j','h','h','g','p','d','a','t','v','f','a','r','l','o','x','e','l','h','p','d','m','y','t','j','y','r','y','e','m','l','j','f','b','d','u','y','u','p','r','s','j','m','q','r','p','x','d','j','x','w','s','m','t','a','p','c','u','m','o','l','r','c','v','o','u','r','n','b','i','a','v','e','w','d','y','v','r','l','q','o','q','o','k','h','s','b','m','y','d','n','i','i','p','t','r','b','c','g','f','l','z','l','k','y','y','w','d','z','f','r','w','o','u','z','o','s','h','w','i','w','o','t','h','x','d','c','f','p','f','z','r','h','a','d','j','h','b','o','j','u','m','p','t','t','l','j','q','u','s','y','k','h','q','s','c','t','g','q','v','a','f','v','x','i','x','o','n','w','l','j','a','h','r','n','m','a','b','c','p','f','k','y','p','v','g','b','n','t','x','w','j','y','v','s','l','w','c','e','d','b','r','u','m','z','e','r','e','x','r','h','t','z','t','a','i','q','v','q','n','g','d','r','a','v','x','f','t','a','g','a','y','y','d','w','b','i','e','w','c','j','l','c','a'};
// c={'x','o','c','j','l','d','p','t','b','d','z','a','b','j','n','m','w','k','w','z','o','u','h','s','m','q','g','z','u','a','r','a','u','z','y','g','n','n','f','i','y','b','b','u','m','k','k','x','s','l','s','b','e','d','t','m','s','y','y','b','w','a','l','l','p','j','y','g','o','v','y','d','s','v','f','i','q','o','c','t','f','a','p','o','s','m','g','k','b','z','s','c','n','g','p','s','y','p','i','w','p','j','u','w','i','u','i','f','h','s','f','q','w','l','h','g','l','k','j','r','i','r','v','l','e','c','g','y','l','t','l','d','t','j','y','m','i','q','z','f','u','f','r','a','i','f','j','f','k','e','x','e','s','z','a','i','b','c','f','v','r','k','b','q','b','t','j','a','n','c','o','x','a','f','m','a','s','a','p','d','l','j','l','m','t','u','l','t','v','v','b','r','h','j','g','c','n','r','q','q','h','s','h','r','l','x','t','d','i','r','v','m','r','c','k','p','n','z','y','b','p','r','h','n','e','u','v','u','t','x','x','f','q','o','x','d','e','y','k','u','f','o','n','t','e','w','k','c','j','x','i','p','e','a','h','a','z','r','e','h','p','g','l','y','c','c','y','k','m','j','p','o','s','d','b','u','w','g','g','x','m','d','c','c','h','r','q','n','j','g','u','v','w','g','n','k','c','a','b','o','k','h','z','h','m','a','t','q','t','d','p','k','e','q','b','o','p','l','i','u','o','r','j','e','j','i','x','g','l','l','g','k','f','i','b','x','h','i','r','b','e','z','l','y','o','e','i','z','k','s','q','e','f','o','j','a','q','a','w','s','d','m','e','b','d','a','o','k','b','x','f','v','m','u','n','v','n','b','x','z','q','c','z','v','n','i','d','j','f','a','z','z','l','b','j','n','c','i','c','m','a','f','y','m','j','z','t','b','o','e','s','y','d','w','g','r','y','v','p','n','l','q','g','d','o','d','w','h','t','h','g','i','v','t','o','v','s','q','u','o','a','k','r','r','x','i','i','w','g','m','t','d','l','o','m','d','v','w','m','f','n','m','t','k','x','p','u','w','y','x','o','w','n','s','s','c','r','b','k','r','x','g','w','e','t','p','k','g','c','z','u','j','u','x','h','z','f','c','r','u','w','h','k','d','u','z','t','z','l','o','m','q','u','m','w','g','w','j','h','w','v','h','v','i','q','e','p','n','q','q','j','c','h','y','i','e','t','n','y','y','p','l','u','d','k','t','b','x','c','g','x','v','o','e','g','o','p','t','e','m','z','p','x','r','q','o','s','s','a','t','e','p','d','s','w'};
// cost={800694,940365,412762,722642,233405,867327,986489,857448,812505,618952,761531,749293,691593,364110,826696,846267,590085,973853,991397,955420,840896,855826,326803,604539,911204,533416,278493,396440,573020,948073,734309,943630,995942,979853,980962,797458,997376,897641,927620,964598,940658,929219,985247,342213,775826,80668,538025,913207,507160,719829,971021,997390,749956,845266,718277,860309,545763,929565,864975,999885,877721,537620,975102,962192,263155,800309,826344,829202,923926,759965,581111,125806,335539,458805,727793,477856,305584,762869,924296,565465,398654,739548,687880,810991,810135,839628,988551,538863,792723,984620,997543,340434,965939,957785,857003,720457,651517,855759,807162,474221,955393,991779,909403,984891,337606,990187,998691,884991,140205,391037,534477,860075,548631,168846,710170,427859,983410,652710,979207,809733,902318,390734,906849,568407,950327,988726,768203,984088,740049,967347,839142,949235,859548,993146,842498,811015,538780,996092,510671,487576,695695,721591,769396,798416,974337,974152,343407,941431,712520,636141,371347,797609,956612,438391,667791,926905,541554,270744,964669,343235,493760,643798,852283,565625,791170,660682,906422,981690,666621,106134,988309,578136,629340,800764,743442,966871,156078,587469,715012,741557,490996,848776,726606,268227,808977,995950,993651,999753,847569,946226,902527,988049,587433,824682,863561,956036,947408,945373,799270,581401,884782,530840,872210,754664,946457,477936,763296,987573,911237,725006,395738,987351,373175,670337,547616,675919,746817,549935,694228,193157,247911,476763,984375,935185,544999,936912,627240,961544,390765,945807,926651,623383,682627,935826,881358,797563,990242,990054,805843,243405,788556,996078,867096,910353,767057,868403,838297,554636,883768,790474,996598,737638,913356,890387,982758,588676,915820,925299,911343,662947,940765,754353,964918,893939,948587,994363,865109,998584,897363,735587,369873,426551,769267,654292,944989,759770,767346,969405,877212,475595,231314,248323,603512,819614,239344,864560,926035,992486,812717,659183,691504,617362,844272,714350,868344,499477,975051,918842,803721,445837,931077,901822,778093,721472,925569,657959,962113,124693,981674,195973,499925,956645,911456,905199,959102,910932,492045,730685,990111,977780,327892,167542,739372,306093,605281,376336,600942,445824,953049,480044,806635,872997,980860,970002,508619,933031,995096,519999,366787,616634,908021,364971,996648,747694,900801,913872,998815,744372,636341,963614,953108,877998,863466,462955,928736,944048,914962,974267,999823,952188,278264,565775,895763,296182,605673,843049,949854,933645,470615,897916,559029,849722,698781,382142,970293,767076,842178,983607,942695,72318,82643,978063,999738,768903,967059,669460,971643,786753,950568,922500,836497,981787,754063,976289,470619,846462,635866,950040,775560,823931,808309,844970,595537,885344,472894,596137,991090,852911,877495,636935,753145,967513,329532,851769,998335,894210,341047,654809,906700,985048,863719,890959,125528,845214,779849,999535,812519,979156,662202,955616,736207,513238,915711,728987,874026,984519,464955,847074,778988,855875,450241,807118,931461,646233,943871,463377,963529,889438,785634,545177,511785,646731,411674,560267,962310,416141,834948,507627,992117,283132,473527,776068,951973,908654,964462,970291,643841,943748,460151,137111,794423,611752,986260,636055,361935,181959,925700,988989,225077,986663,674752,949388,973954,782501,800217,526589,768887,341620,605202,718239,517451,844875,815768,969671,852948,487172,805374,834289,912904,698593,445151,471472,930006,759854,554545,770322,679645,897757,503557,788331,533518,618881,487767,947088,764974,635819,699868,923166,913588,588114,583016,980063,798841,412810,909986,957064,855938,850507,942940,372404,859308,937795,889889,780600,686081,501757,772988,201246,880021,849715,755798,823352,938260,943164,994377,736794,937141,725246,989661,722092,819099,804648,966907,859279,986478,911779,577562,150004,980970,990433,949850,990639,654116,993360,768594,751815,512473,987171,951498,905918,936018,989754,561289,866710,261393};
        vector<vector<long long>>matrix(26,vector<long long>(26,1e9));
        if(s.length()!=t.length()){
            return -1;
        }
        
      for(int i=0;i<26;i++) matrix[i][i]=0;
    for (int i = 0; i < o.size(); ++i) {
        matrix[o[i] - 'a'][c[i] - 'a'] = min(matrix[o[i] - 'a'][c[i] - 'a'], static_cast<long long>(cost[i]));
    }

        // cout<<s.length()<<endl<<c.size()<<" ";
        // for(int i=0;i<c.size();i++){
        //         matrix[int(o[i]-'a')][int(c[i]-'a')]=min((long long)cost[i],matrix[int(o[i]-'a')][int(c[i]-'a')]);
        // }
        // for(int i=0;i<c.size();i++){
        //     if(matrix[int(o[i]-'a')][int(c[i]-'a')]==1e9){
        //         matrix[int(o[i]-'a')][int(c[i]-'a')]=-1;
        //     }
        // }
        shortest_distance(matrix);
        long long ans=0;
        for(int i=0;i<s.size();i++){
            if(s[i]==t[i])continue;
            if(s[i]!=t[i]){
                if(matrix[int(s[i]-'a')][int(t[i]-'a')]==-1){
                    return -1;
                }
                ans=(ans+matrix[int(s[i]-'a')][int(t[i]-'a')]);
            }
        }
        return ans;
    }

int main()
{
    // cin.tie(NULL);
    // cout.tie(NULL);
    int t=1;
    while(t--){
        vector<vector<int>>nums={{2,3,3,10}};
        // cout<<pow(nums[0][0],nums[0][1]);
        map<int,int>mp;
        int pufblic = 9;
        unordered_map<int,int>m;
        mp[10]=5;
        mp[1]=9;
        mp[11]=2;
        m[10]=5;
        m[1]=9;
        m[11]=2;
        for(auto i:m){
            // cout<<i.second<<' '<<i.first<<endl;
        }
        vector<char>a={'a'};
        vector<char>b={'b'};
        vector<int>o={1};
        cout<<minimumCost("a","b",a,b,o)<<endl;
        int main=99;
        
        // cout<<(pow(pow(nums[0][0],nums[0][1])%10,nums[0][2]))%nums[0][3];
    }
// 9
// 4
// 8
// 7
// // s='ahymwvveassnabpnivvlhwnymipzyywplahbppaeisazybzbuyveobnollbmlubwehounmhepwsyallupvhuawlvoszyiwlabulzhvmiulilmysvsezbhbylaowmbybpylozvnublnsyweapaauhehswollnmlbeoanennnuoybymnnyhlmmvivbhwmhnibspusezippnybyhyzzbypyamlsylhiinlmwveibnmwpspmnnlmpnzmapouposwowavimbhuaoosiewymbiuwaoesblyhpoebhapnaeiveiezznwzoowhmsbvoiziiymelohboohmvzishzviabwzuzoamysphamowvlwlmmoyoyzewuowbhupobwzzouhllszpsnyubnaheyaouozuzpelomhpwezevyuobbhnwnlyeyusoslenbolmeunaopvhanibpvvloiplhobipzbobsbsbbhpyvoslhwupwvhsyhizluziahamay';
// t='iwevmnllzbiespsmeoeunnvzuymnymvoeyuyhozuminepwaezpeeayhualvhlboeewaboosplonuzheuziyymhbnywnwzyameyshvbhnzvvbeznniaswzslzbsasvbewzzzmvulvvhzmohzmyummypaeowusvlmlyvmvaizuvomvipbpwnbimppoymiesmymioeemzpbwbvuszpvbpwmnyvypyzemsniaavnmiphiyvimzoozuepbowbpvmpelahvupuwzlbbywvyusawobouslblvbpvluylnsiauiwzawiowsnmvawepielbavvpbmvylvlylzunmbnaesoimuvwsmybmnybbhwbyuimmoebpvwnpiyebzzuwhiovubuynyvybipbzsnuopuhpzosmnhlnlmnneumshwaiyyspbpbiaiovyyvomhanunieisazshvyubmbvnbpiwipmuzbymnozwzaaawenlwiowpsvleppzellhei';
// o={'n','s','a','s','s','b','h','l','e','n','e','w','y','m','n','e','a','n','p','n','u','i','b','m','z','s','v','o','n','n','a','o','l','p','s','v','b','h','b','s','y','i','a','v','o','p','p','l','a','p','o','e','l','a','m','h','o','v','e','s','n','w','v','w','y','n','o','o','e','e','h','h','z','z','z','s','s','z','h','y','u','i','l','y','h','u','s','e','b','b','o','h','p','l','e','n','v','l','s','h','m','z','z','h','z','b','w','u','o','b','u','m','o','b','e','n','a','v','b','b','n','i','l','h','a','p','w','p','i','u','n','b','h','b','b','n','s','v','u','n','v','v','e','h','l','s','l','o','s','o','b','i','i','n','e','h','u','i','w','w','u','b','s','z','h','b','l','e','a','o','m','z','l','n','o','v','v','e','h','e','v','e','l','i','s','s','y','b','w','o','i','s','h','b','b','y','e','y','h','o','p','s','i','p','n','l','w','y','u','a','v','y','s','l','v','w','z','l','p','m','w','s','y','b','w','z','w','n','e','s','e','e','e','s','a','n','o','y','i','y','o','e','o','e','w','n','h','s','v','l','o','m','l','e','n','p','z','u','a','z','s','n','i','y','a','y','h','i','v','z','y','b','i','p','p','z','z','n','a','w','n','e','n','p','z','s','i','a','y','b','m','w','m','b','h','n','y','v','v','n','u','l','h','u','a','o','b','y','y','h','a','l','v','s','e','y','u','l','n','l','e','m','w','h','l','z','m','l','a','l','i','s','w','p','s','v','l','n','w','m','l','b','o','b','b','y','w','l','i','w','e','l','v','n','y','w','b','y','b','l','h','z','e','e','n','z','e','i','n','i','n','u','w','o','o','y','w','w','p','u','b','s','a','i','e','v','o','n','s','z','m','z','n','p','e','z','w','w','n','i','i','n','e','w','b','e','z','y','w','a','i','u','h','w','v','s','z','e','z','b','y','i','e','z','u','u','m','a','n','v','e','s','s','o','p','y','m','v','u','p','p','z','s','m','y','b','v','v','b','h','v','z','w','p','o','h','p','z','a','y','y','p','v','p','y','l','e','l','h','a','z','y','m','s','u','l','h','l','v','v','h','m','s','n','h','p','v','e','a','p','y','y','n','z','y','y','l','v','n','n','e','y','y','z','i','z','e','s','b','m','n','y','h','w','v','m','a','s','z','v','h','a','w','e','b','w','i','b','y','s','a','w','u','b','m','i','v','p','e','p','z','s','l','l','z','h','e','y','i','v','n','m','b','n','a','l','p','z','w','h','z','z','w','e','l','l','o','w','l','n','h','y','n','p','y','l','u','w','n','n','n','m','h','h','w','l','e','z','a','a','h','u','o','u','y','n','b','z','o','h','u','h','l','n','b','a','n','s','i','n','n','n','e','n','v','o','z','i','b','n','y','b','l','m','e','l','m','z','e','s','m','z','n','z','a','e','n','z','z','y','m','l','h','p','n','i','m','p','o','m','m','w','m','n','n','y','n','b','s','o','w','e','h','w','b','e','l','b','o','b','o','u','a','m','n','s','m','u','h','a','l','h','y','s','n','o','w','o','o','u','a','m','l','a','e','l','w','n','z','a','b','o','y','m','p','p','i','u','v','z','m','w','e','e','l','a','h','w','a','s','l','p','o','v','m','u','a','n','h','m','s','w','o','e','y','w','o','i','e','v','h','z','p','l','h','z','n','s','w','e','u','e','s','i','h','b','a','y','e','m','m','b','w','n','v','n','b','p','a','s','o','h','z','o','o','u','n','h','e','b','u','u','a','o','s','s','z','l','i','v','n','h','s','z','e','s','h','y','h','l','y','y','y','z','z','b','a','u','o','y','n','l','i','y','i','h','b','n','u','i','a','z','n','e','b','a','n','h','a','a','w','b','i','u','v','m','n','b','n','v','p','u','y','i','y','b','i','w','y','h','p','n','p','i','z','v','o','e','n','o','e','e','e','s','l','p','w','i','i','i','y','a','h','z','y','p','z','o','l','w','a','l','e','h','m','l','n','w','s','p','m','y','o','w','a','o','a','n','w','y','m','e','v','v','o','n','a','b','m','b','y','s','v','o','m','u','m','b','s','h','n','a','y','l','n','z','h','w','m','b','v','e','n','e','s','l','o','m','v','n','o','b','o','b','z','a','o','s','y','u','u','v','y','i','p','m','b','y','z','n','a','v','p','w','a','n','z','z','a','e','l','y','v','n','a','h','u','o','z','m','a','o','a','e','m','y','n','m','h','o','z','n','w','o','u','e','i','l','w','e','n','a','w','v','z','e','m','w','y','m','v','n','n','m','m','y','a','w','e','y','w','h','m','i','o','w','e','e','w','p','h','w','y','m','m','n','l','i','v','z','p','s','n','y','w','z','b','z','s','h','i','n','y','y','v','z','e','v','h','e','n','z','u','z','h','o','b','u','e','y','b','s','o','w','o','p','o','h','s','o','a','v','m','s','o','p','p','h','l','b','a','v','i','m','v','p','v','i','u','h','i','e','b','e','z','w','u','l','l','l','i','s','z','e','l','n','b','l','p','a','z','b','z','v','p','v','i','l','w','o','y','i','o','p','w','a','y','p','h','w','y','b','y','i','h','l','h','h','e','y','l','l','h','s','h','v','w','i','l','v','m','s','o','e','s','v','u','o','z','i','n','h','i','u','l','w','z','a','s','n','h','y','n','y','z','v','u','l','b','i','e','l','p','h','o','i','o','s','v','u','n','a','y','m','e','b','n','o','n','z','b','o','e','w','a','a','i','z','i','h','n','i','s','p','w','h','m','v','v','s','p','e','h','b','b','e','z','m','u','p','z','h','y','h','s','e','e','l','b','n','l','y','y','n','m','b','y','i','b','b','s','e','e','w','o','y','v','o','l','u','m','e','e','h','l','n','m','w','w','a','o','a','e','m','a','i','m','u','m','b','i','i','u','a','b','y','y','z','w','y','n','v','o','s','e','m','o','s','w','h','l','n','n','n','e','o','l','s','l','l','y','y','p','u','o','u','o','u','n','n','o','y','o','y','m','h','i','w','s','s','p','l','n','w','n','h','l','z','v','i','p','a','s','e','m','v','w','h','o','p','m','u','l','a','i','o','o','y','e','i','v','e','a','y','h','y','h','h','b','h','v','w','w','i','s','s','a','a','s','v','i','u','n','n','y','h','z','s','e','y','z','z','b','i','o','y','l','l','b','b','i','b','w','m','u','v','o','b','u','o','e','o','n','b','w','v','s','a','m','b','l','z','h','z','b','n','s','o','s','n','n','p','v','u','b','z','o','h','y','a','e','v','e','h','n','y','s','n','i','b','m','l','l','e','h','o','h','e','n','p','n','b','o','l','e','n','e','b','w','a','l','i','o','u','h','m','i','i','i','m','v','h','w','l','a','s','i','y','e','w','m','w','o','e','v','l','a','u','o','y','l','w','u','a','v','n','l','v','h','i','y','z','i','z','z','i','s','y','l','e','w','p','l','h','p','s','w','w','h','i','n','m','z','l','h','o','e','h','y','p','p','a','l','i','o','o','a','i','v','n','i','e','b','y','e','w','p','y','s','o','z','a','o','n','m','o','p','e','z','m','v','z','h','m','u','h','w','a','n','h','b','h','u','h','i','p','u','n','m','z','n','n','e','e','b','y','l','o','b','h','n','w','v','v','l','b','p','l','b','u','w','h','z','o','i','w','b','y','a','y','p','z','z','v','l','n','b','l','h','s','s','e','l','m','s','n','s','b','w','v','l','z','n','y','n','a','b','l','p','e','h','l','s','h','a','p','e','w','o','l','z','p','n','p','m','b','n','v','p','n','o','e','w','h','y','n','i','l','m','i','i','u','b','h','b','n','y','z','p','l','s','s','v','e','u','e','a','y','n','y','l','u','i','i','l','h','z','m','e','h','o','z','h','n','w','l','e','b','z','w','z','z','l','n','l','u','w','m','m','h','a','v','l','p','n','s','l','a','e','v','z','p','m','b','n','a','w','w','e','p','w','o','m','i','p','w','s','b','i','e','b','z','o','m','y','b','o','v','l','w','b','v','w','p','m','l','a','h','s','a','h','i','v','i','e','w','b','a','l','p','u','z','s','w','p','i','w','m','p','y','z','w','z','n','y','h','y','o','v','n','m','n','y','a','l','o','n','e','w','i','w','m','s','h','s','l','s','w','m','v','l','w','a','b','w','a','h','b','z','h','a','i','i','o','u','y','n','w','h','b','i','u','m','h','o','n','z','z','a','p','u','o','m','l','m','b','a','l','y','h','v','v','v','h','n','w','i','h','b','l','z','l','m','m','l','p','m','o','n','u','n','o','s','e','e','e','e','z','y','i','z','n','e','u','v','l','h','w','l','l','z','y','b','v','y','n','u','n','z','s','w','w','e','o','o','w','i','a','h','b','w','h','i','w','s','z','u','p','h','b','h','p','p','o','l','h','e','z','o','w','a','h','w','v','i','w','w','y','o','h','n','n','p','w','e','a','n','m','w','e','u','z','p','p','e','v','o','p','e','b','b','b','n','w','m','y','i','w','h','i'};
// c={'z','u','z','i','z','y','w','e','m','b','u','l','l','u','e','s','n','s','m','b','p','y','w','v','m','y','l','b','h','i','y','b','o','l','u','i','e','v','o','w','p','a','z','u','i','o','b','w','m','b','n','a','y','y','v','a','v','m','s','m','v','n','e','m','o','h','p','n','w','s','y','n','w','y','u','m','a','y','s','m','n','e','w','e','u','m','m','z','z','z','v','i','w','s','y','v','i','a','y','m','y','b','p','e','v','z','y','p','a','m','b','y','s','o','n','w','n','h','m','z','u','n','b','e','v','s','o','z','z','b','y','i','w','n','l','s','y','i','w','b','u','e','i','u','m','m','w','b','i','s','m','p','v','u','u','w','m','a','l','m','w','s','u','p','w','m','h','n','s','s','v','e','u','z','v','e','u','a','l','p','l','y','n','p','u','m','b','l','h','s','a','y','s','n','p','m','m','v','u','b','l','u','u','b','m','o','b','p','a','y','l','w','i','y','i','e','m','m','n','s','o','z','u','h','v','b','u','b','i','u','p','z','w','z','s','o','m','p','w','z','n','n','l','n','p','m','y','u','e','n','m','h','y','m','h','m','n','p','l','i','u','a','v','l','l','z','e','n','o','b','o','v','y','n','i','v','h','a','e','b','p','l','m','h','y','b','y','n','m','h','p','u','o','p','w','b','e','o','o','a','o','a','i','m','w','v','y','e','e','l','e','a','m','w','p','b','a','o','s','z','z','s','p','v','v','i','b','v','u','n','w','y','a','h','a','l','y','a','v','o','h','v','u','e','y','m','n','a','u','n','w','m','m','y','e','o','l','b','p','e','w','m','i','s','z','i','z','u','y','b','z','m','v','n','p','u','m','n','m','p','v','b','s','w','l','b','n','o','z','w','p','e','u','m','z','h','b','u','h','z','e','v','l','p','v','z','n','z','h','i','p','w','o','y','l','n','h','w','b','m','l','a','i','w','a','w','a','l','a','n','b','n','u','b','b','p','v','o','m','o','n','b','i','o','u','v','p','y','m','l','n','p','u','h','p','s','s','n','w','p','m','n','b','z','p','m','z','b','z','v','n','v','s','a','b','s','y','a','b','h','z','y','m','p','e','n','h','y','s','n','n','n','i','i','u','p','s','b','w','y','w','l','z','n','p','e','b','a','n','y','z','b','s','o','i','p','m','w','h','h','i','m','o','b','v','u','w','i','m','a','e','e','p','o','a','w','o','h','m','i','p','u','e','a','m','s','p','w','y','b','e','v','w','i','v','z','l','l','o','y','s','v','m','a','b','m','m','a','h','u','n','z','h','n','u','w','a','p','m','a','a','s','z','l','e','a','u','i','z','e','u','p','v','n','b','o','w','p','p','z','a','l','z','m','h','b','w','u','b','v','h','u','w','a','o','z','m','m','z','u','l','l','m','y','y','a','i','n','v','z','o','v','e','h','n','y','a','u','n','n','a','o','s','i','y','m','v','w','b','p','s','b','s','y','o','w','v','v','u','b','a','z','a','o','w','n','e','s','l','z','s','o','l','i','i','z','p','n','w','u','h','m','z','b','w','p','a','i','a','o','u','v','z','l','a','w','a','b','y','i','i','b','u','o','s','h','m','b','h','a','y','p','m','b','a','b','s','m','m','m','y','m','l','m','y','m','s','b','s','u','b','e','s','n','w','v','p','p','z','p','w','h','z','u','z','p','i','u','n','v','o','n','y','e','i','o','b','b','b','v','y','o','b','m','n','v','i','h','y','i','i','w','v','l','p','o','v','z','s','y','l','w','n','a','i','i','m','u','w','i','b','n','w','v','i','z','o','u','n','e','o','v','u','b','e','o','v','a','i','e','v','m','a','p','z','a','o','p','m','m','e','l','h','w','m','i','w','w','v','v','e','e','n','l','h','u','o','p','p','p','h','l','o','p','w','n','a','u','o','w','s','i','l','e','n','l','b','m','m','v','s','w','b','b','e','i','a','m','v','u','u','i','v','i','v','l','e','l','h','a','s','n','b','o','p','y','i','a','i','z','u','o','z','u','e','l','n','e','b','p','h','s','e','o','a','v','e','o','v','i','u','i','e','y','h','p','o','e','y','v','p','i','u','n','e','l','y','b','v','e','p','b','o','y','m','m','p','s','y','m','n','p','m','o','a','n','v','b','b','a','w','e','u','e','h','p','s','w','w','y','m','p','o','a','y','y','i','i','s','z','a','o','y','i','u','i','b','a','u','s','n','s','u','v','u','e','h','h','v','u','s','s','o','m','b','b','m','z','u','l','o','w','n','y','h','w','a','e','m','p','o','e','p','o','o','p','i','u','l','u','m','y','u','p','z','b','l','n','p','i','e','o','w','y','u','e','w','b','e','s','w','a','e','u','o','v','z','u','n','i','p','b','w','m','o','u','u','m','y','a','w','s','m','l','u','l','z','o','p','v','e','z','p','b','v','s','p','l','y','p','v','b','i','n','v','h','n','l','z','i','i','y','a','s','b','b','n','u','m','a','u','v','i','u','u','n','w','w','n','m','v','a','n','a','z','h','i','z','w','u','y','z','s','h','l','h','b','u','o','u','b','n','l','b','y','l','b','z','s','p','z','l','w','z','a','v','z','m','m','o','n','b','w','a','u','o','u','z','e','h','h','m','v','l','b','y','b','n','p','v','z','w','w','o','v','m','l','l','y','b','y','p','z','o','y','m','a','m','s','w','n','y','w','y','v','v','u','b','y','a','b','y','n','h','w','z','s','y','w','s','i','p','b','y','v','l','p','y','v','y','s','a','u','l','b','u','i','m','e','b','i','b','y','e','i','l','v','i','l','o','p','a','z','o','a','u','p','b','p','m','h','p','v','z','o','i','n','p','p','w','i','y','y','a','y','z','o','v','y','m','s','p','y','o','b','w','v','v','b','s','s','v','s','u','v','m','a','a','u','v','z','v','p','b','i','w','v','l','m','e','e','b','z','n','v','p','i','b','l','i','h','h','o','v','u','p','b','i','w','b','u','l','m','l','i','p','b','n','a','e','z','b','p','z','o','y','n','e','n','z','b','m','v','e','e','w','a','s','l','m','s','l','i','z','i','m','v','w','m','i','v','m','n','w','m','n','u','w','m','e','e','i','n','o','i','n','o','s','n','o','h','p','l','m','n','i','u','z','u','e','a','w','a','w','b','m','h','z','n','z','y','u','s','b','p','p','s','m','y','s','y','h','e','h','l','n','l','l','w','s','v','m','i','h','n','n','a','m','i','s','h','b','u','y','p','v','m','b','b','p','b','h','n','n','i','a','b','o','l','w','a','m','m','y','v','z','w','a','n','e','a','e','m','y','v','p','a','a','z','l','a','o','a','u','y','p','y','y','l','b','h','y','u','m','y','v','m','w','a','s','e','o','m','m','z','i','y','v','n','o','p','v','i','v','b','w','v','p','a','m','h','l','o','b','u','y','y','u','n','u','z','b','e','h','e','z','a','u','m','z','m','s','y','z','l','m','m','n','m','m','i','a','v','b','s','a','l','v','n','l','i','s','z','w','n','l','l','b','p','e','e','b','h','m','b','e','w','w','b','l','i','y','b','s','o','l','h','n','v','v','e','v','s','o','a','m','v','m','u','s','v','y','b','a','v','s','a','b','p','i','v','y','v','p','p','b','a','z','l','a','w','l','l','u','b','v','z','u','p','m','h','s','b','n','y','o','z','b','b','n','n','s','m','p','u','u','s','m','s','z','n','y','u','s','w','e','u','z','o','u','n','i','o','l','v','s','o','z','z','n','u','w','n','v','w','s','a','h','v','z','u','h','y','o','u','p','i','p','o','w','n','b','o','o','e','v','m','s','h','z','z','a','o','n','h','s','v','l','o','v','y','m','m','m','l','z','w','e','e','p','m','l','m','e','s','e','a','i','z','i','l','y','s','h','u','y','n','h','u','u','a','l','a','a','n','a','b','a','h','u','y','m','o','m','h','a','e','u','z','l','s','s','u','s','o','y','b','y','s','o','e','m','y','e','z','b','n','w','u','v','n','y','y','i','p','l','u','p','u','e','m','l','n','i','p','o','e','s','y','v','m','u','i','e','u','p','z','e','b','m','b','u','w','v','i','n','h','a','z','l','s','e','b','m','b','v','b','z','b','h','o','o','l','b','o','l','w','z','e','w','e','p','n','y','w','o','m','h','v','o','a','u','u','e','h','z','y','e','e','i','v','m','b','a','w','l','p','p','s','v','u','n','u','a','s','w','h','n','m','b','l','m','v','a','i','s','w','u','o','l','u','h','h','n','o','n','m','l','o','w','e','h','i','v','w','l','h','p','m','o','s','p','y','n','m','p','v','w','w','p','v','u','p','n','m','s','l','p','e','z','w','p','i','u','e','s','l','m','n','n','l','a','m','p','n','h','a','e','m','h','v','y','u','l','a','a','l','m','v','l','n','o','n','z','e','a','p','s','n','m','s','n','a','h','n','l','h','l','z','m','y','o','m','y','u','l','s','p','l','v','n','a','o','w','b','e','a','w','w','w','z','s','b','u','s','e','e','p','m','y'};
// cost={745546,681763,567802,714000,250223,676168,444410,527553,539719,237541,696428,560465,863906,796296,428070,18490,54402,542636,460145,966528,362462,104880,646640,461359,97243,827845,398969,647258,941991,742668,890530,756048,250972,626893,855304,619312,569762,925139,241103,548379,142738,237066,643035,81116,653135,438231,217017,511962,589779,761220,274768,576117,512613,532612,911093,165413,607172,256053,330723,280576,539232,29355,86424,843231,510568,531223,335530,169903,595277,970232,781022,457910,514351,153815,49601,994502,179631,869857,32952,333217,915309,887802,802546,273560,659751,996122,771046,983170,958044,187888,526229,610546,507368,296596,62715,549555,574593,673622,308748,272856,412850,912078,327031,989337,488811,981765,661273,708178,402096,678953,64500,565907,29632,266317,162603,498262,149281,198824,415695,582258,710013,632530,593250,726557,376302,556283,723094,103059,563190,930834,413921,912243,942797,809930,205611,360333,505711,403206,511661,757042,2587,65183,638120,900128,244108,842270,583688,433020,385635,970188,201558,895196,815759,371550,969739,790222,192498,856654,366323,162824,761898,885782,472667,881741,50718,856868,729025,153568,183938,785581,978433,178420,36718,980518,722308,846508,129694,922120,875977,958437,829292,901764,223022,54508,91451,696587,296292,372111,330427,94751,240179,920309,625113,655515,53380,199111,779722,740547,275893,134560,521589,75700,704270,675800,223555,498114,859480,783623,598320,848217,481148,40259,211602,133653,249063,489866,982043,369468,820016,88747,56924,472490,744326,984575,952303,451550,461246,215017,872423,174571,902338,354921,689923,379313,39192,493143,338779,432564,995503,789668,532861,394816,509010,335514,956309,161917,528559,502754,380156,482050,102915,653536,716749,771848,558804,428575,763886,190742,35579,910388,148331,928518,773604,731743,703187,517991,332759,31865,892423,888418,488412,455388,682592,162706,46575,273998,675481,630129,821792,623992,92449,646546,227624,619640,376448,113627,907357,822664,768252,436908,414919,376532,367798,996233,898369,315181,254958,886578,806368,570893,667358,232732,781302,20486,635668,505767,910229,281404,549057,234184,850962,993037,180347,995001,537229,130576,170715,227581,450962,38319,995500,467131,443954,363223,468117,693128,797836,87421,930647,735005,499716,944535,15368,614121,894985,878955,647855,611444,429414,720601,907776,305848,684956,754183,360360,820611,148939,209256,389422,875899,788364,704627,408081,889216,302811,84012,501190,222222,285015,537056,926960,671920,727750,712250,859813,560317,936771,804974,38617,112347,657472,349524,948895,220442,919060,410733,671861,59670,115222,18437,421935,402667,952659,359492,107517,174016,335381,120919,693320,493234,28882,516657,385527,594992,183044,498100,375970,656038,582516,562858,842441,344796,249881,728476,936845,555379,168346,764278,460890,627204,760016,718531,312849,343716,146605,847797,412324,770817,997073,698216,6433,981591,701829,870131,106888,992509,120202,737576,669674,974594,352619,478527,681497,825584,870237,52311,86608,774034,863886,169466,760189,966845,739579,769171,837087,392633,528448,43153,756124,782428,412871,124970,727659,761198,366027,42849,723087,71523,396592,298069,575351,692517,870601,910203,819934,224171,376718,942653,959486,783646,940182,943389,727976,934182,762334,825406,826468,380175,393901,786480,968803,45222,412620,557176,707016,301397,408047,319872,35011,973284,602580,911328,804989,849311,202158,133925,566611,455779,388872,884644,57943,612912,242980,957422,640734,406246,359628,90468,46733,68352,811190,522628,729739,388037,970684,170350,957660,897053,766505,697395,122802,716134,524811,10704,363598,395669,15621,402576,622634,207547,329132,568789,42927,793882,992385,936744,843169,17407,579486,978648,65623,453399,82438,302473,895213,191140,84663,964567,334948,584605,279351,855283,768757,854262,791212,143244,22280,254372,699882,542064,154116,402009,573732,596475,136357,667009,192461,333571,651359,498148,264500,327962,688586,207423,221014,323453,491887,111474,291248,743416,41606,815834,15682,286665,949632,847448,278135,341523,803342,710757,386801,811336,542875,284401,368544,616987,559014,493903,272966,388472,71458,996416,583457,703207,520939,833234,41035,910245,400242,822713,651366,786152,663452,333255,348086,675160,486986,691430,722759,11632,256061,236388,318884,902427,351687,394097,988340,704090,641027,867553,945850,346569,384335,685283,768858,918237,971009,968089,640257,195421,735032,375259,878303,787732,682473,583086,560303,831204,150365,845066,982457,997699,225214,581953,514431,592709,449820,681180,665926,290023,92856,502918,997737,287383,667610,743262,385733,918184,871462,254925,478463,587693,870581,807961,393432,907516,583909,965727,551166,114789,607859,737419,287396,930049,207488,259590,224168,997774,507006,902955,959411,15573,419967,566330,740591,147624,223686,342806,417240,528981,251008,477683,622966,147675,434248,745501,361172,830234,662158,609960,991800,755482,655482,364608,2054,192450,32204,515958,343361,735735,650889,432841,949277,737551,759871,866151,164790,456990,679841,674903,601145,807569,122322,232318,22027,792274,816110,784717,219860,321509,226092,663431,65752,466402,248668,997316,626638,436405,664138,151216,449458,969387,442830,796743,769514,758344,915402,954060,347897,154759,759590,660693,790760,892561,910156,234708,849694,985792,218985,275596,131315,435738,910223,734405,906818,50687,90961,778409,393540,643802,117304,259957,313133,643237,599232,492604,353068,639539,592236,748359,341202,759526,897024,960534,151267,495683,117581,436645,67995,192494,928947,803499,792307,276988,981699,703994,402187,813587,40009,128206,694483,971920,24610,513999,950964,84439,662098,197499,706754,396664,438792,864285,186260,456557,201360,240773,814145,137394,283636,871647,600691,208441,505194,646020,826223,450701,113352,405523,938813,551855,764841,437983,950506,124876,205883,703248,993868,686347,470669,22400,280205,366946,134427,311869,671388,171669,579547,699544,659105,463100,304819,10749,999994,549174,567554,495722,952684,914595,782761,869004,760462,593845,411679,366651,827120,62089,828962,682228,226286,849112,983118,719601,87399,324260,881281,855055,604642,599891,314389,87985,932996,680946,762888,278762,871098,678445,583977,217951,788836,311767,534963,213735,801050,9738,237942,912108,16109,928335,192247,873846,384203,745219,835453,261339,809891,804523,748063,273016,674052,899614,196176,847449,682136,820471,957935,224631,180060,383565,569996,755395,548703,547900,364947,40795,569927,895159,411637,557664,307047,510513,236072,709179,168168,213936,879842,835273,496111,610127,842599,724929,336221,38309,172467,223785,758648,434128,343438,887239,692024,318957,626578,544591,813415,889330,485774,972040,93838,433236,817884,515085,133522,808349,692180,980715,596208,641256,245910,899699,738602,956312,198419,729243,944476,340437,16096,716234,237847,153886,600972,668797,879147,86919,170206,916717,742166,212071,969419,938388,648433,820324,721991,239984,107959,862425,743157,682366,958879,149135,888873,559736,930533,211120,513955,965011,635085,639110,59381,660611,88438,826847,940202,162013,719677,190782,802316,392533,974990,969207,632511,609997,559313,605428,738650,665137,854532,375572,42977,276271,883878,404800,898642,850849,968582,206980,540489,211292,841465,45919,732996,974712,265692,485894,330930,987715,28920,772409,558118,347916,336389,975532,946869,485005,717121,322289,805591,260129,283407,409842,608901,769608,262609,868680,150412,250276,862655,431676,659797,397736,664856,808420,765630,751992,680014,819183,894873,522466,209119,773015,809828,536462,908741,538278,281485,662106,679842,827766,284321,265729,446012,211126,516813,709083,685207,890477,330507,76366,522354,359562,268747,614783,522968,739746,225984,448560,9119,577341,770359,564200,598435,840874,807493,204387,974224,483583,318379,52297,375005,656480,806896,789046,457878,651572,573819,397285,87264,36008,110193,443127,747969,186469,404698,910006,786697,610653,275889,673675,954962,184649,37885,752362,382825,666977,447612,543497,901970,852474,914872,409264,649293,733529,347193,532603,321480,329650,796372,372252,814411,422257,155568,260821,809384,493217,861200,62208,19784,291325,185977,983068,617627,592857,285848,901523,954600,418955,581769,448375,495066,743285,297641,214873,262574,490304,457709,499578,123019,173911,258018,262493,619814,961220,44230,553801,315602,581545,585942,230181,774581,222011,865918,779467,85406,783695,763210,981832,798695,423792,882483,629800,352013,701195,464269,316083,652281,860163,403379,660298,993716,156547,437881,283930,990291,815908,382855,963992,948311,588590,984521,226393,74469,372064,516814,968999,415986,594691,797246,993768,126928,515990,524959,846496,208433,610283,416984,253484,553819,386233,507756,973732,699011,744756,293065,428406,860329,997951,30647,135191,379464,968112,990898,259367,887434,251274,641293,52732,506313,489205,707924,416314,108982,753276,86650,398438,549196,823553,716909,155733,760241,842197,562155,882097,374240,774624,151279,858133,247368,403726,958835,41688,740912,664994,119470,540820,556828,853056,997567,51798,661037,966416,824595,54330,427538,630306,230641,313063,678792,846208,749721,522367,520003,568063,65371,173449,979612,527738,462153,30891,712249,920607,582269,436568,117141,886165,691390,678997,180139,710703,817383,400653,233390,275787,167022,250964,706120,713575,814426,123300,297226,784899,317963,11692,685315,558024,47180,468661,961030,208090,520048,214230,978509,465713,469886,590928,43838,958053,206167,456028,900897,494674,679264,336724,918705,460056,514795,761728,727671,906912,532608,208005,480501,788281,951524,117605,868184,886911,715086,686515,218372,335913,622634,215582,841308,765697,521641,855451,974207,296797,352386,331562,194417,542647,316381,732832,735848,939376,151648,85738,637705,230568,330994,964159,113465,104065,815929,842175,452184,208363,554141,613997,980938,482348,44024,491596,977984,122403,947676,136572,388274,311427,234153,765002,800652,633678,111081,167162,439782,716204,49942,88253,366449,518710,941124,148894,967328,126465,869698,792973,128848,826988,997529,770050,46916,774655,828605,6695,671320,122709,648007,75041,120632,646807,229430,414552,887732,446124,498971,37414,372375,287871,298821,177365,214767,913650,316285,572629,84592,807294,567401,398834,424064,128223,6877,976451,983521,409477,788438,481941,208673,619785,529241,17483,841595,698661,927425,820420,933487,940215,381124,672565,39023,633179,778057,433066,426441,335307,429641,924531,805546,966668,389168,210431,714597,926873,202844,763058,65712,102758,970611,518046,240562,54001,695774,618022,393770,883760,394688,131523,80693,351057,197606,46835,13060,330329,775150,607325,333000,6049,303863,809347,393021,832842,875674,487843,471336,596338,549804,964137,376305,802935,320041,656897,440629,548263,640134,108906,925949,726496,758563,539355,759336,864257,375444,294951,652646,127076,416929,400785,581259,216444,518672,530443,157441,778502,180730,729877,249838,659311,643467,569040,210400,670747,96242,766532,939360,715843,985977,393306,972725,28556,312314,397858,595525,536131,933421,749830,92325,937264,777393,758062,361478,702126,155241,474185,186137,584587,130729,106449,979237,595206,549330,839443,538445,722499,825383,917558,58094,607121,528011,922575,80624,238098,229113,532597,83441,426222,479632,25782,794685,602948,816402,745616,926308,599511,120439,808760,205693,209620,416451,966777,802211,173289,938363,992900,942710,680558,975787,294698,372390,758259,202174,782457,816893,811575,704174,130829,616238,460849,479680,467205,563264,597385,884204,381576,306848,494027,306294,387402,301638,51520,351422,811488,872987,278959,413602,238894,954438,915608,106309,850819,285998,655253,322554,378838,618348,472244,770392,390460,728416,56569,379208,418824,82552,961064,379090,375578,470276,380860,889904,256269,865919,262658,178663,390263,57640,961445,771557,98980,199529,617708,132182,149755,841450,307840,393419,369032,841794,213308,26250,148919,981709,470433,140083,800677,695970,296943,157916,884850,555473,224834,737664,448131,138399,233886,622201,996243,193488,853277,899481,825328,173090,808072,973347,470654,448665,104418,371371,127945,322820,379354,758636,432780,60233,479147,272805,885212,812582,207693,898357,830472,543399,599285,310551,47764,751076,891407,821225,531749,107874,24627,997875,410483,619872,909838,908931,593811,801023,663999,827617,776902,927011,410865,104563,746498,826135,519618,238110,675809,614916,630865,587568,991230,700939,928457,554060,953072,479416,729104,219257,456588,56036,778286,999837,654942,985912,579015,587939,564656,523593,290444,111317,585520,641179,878799,460857,770753,58382,707870,984730,150692,626942,727040,367257,703972,224255,505393,964178,457079,810175,562458,306283,948908,703240,715826,240792,603373,646955,420278,686600,971832,823806,306051,990133,935575,232634,245426,913458,969608,446491,273862,143748,525157,680641,757900,596980,240239,152004,327003,625528,318716,763162,866439,896344,862230,963535,581602,120545,394584,49009,406446,436564,669418,174593,61803,257752,856265,657247,93349,40616,94280,663833,939219,658438,190838,108234,961030,234333,755616,299687,393305,861760,554683,494508,265468,687607,859629,966727,894847,404392,783668,206930,221659,183315,770578,256785,991998,367723,886879,613923,379377,273966,901598,52474,246238,163973,864200,255208,711518,721972,274409,729010,928898,223965,482200,576029,842105,685853,351304,307830,670828,806865,46667,188709,390373,57230,183345,315385,894412,397915,56187,361122,324410,891360,182995,840763,86910,693552,595481,634876,274274,463754,17075,338613,644078,139632,141994,365908,245805,587343,950711,114119,209397,127254,627334,841833,481858,385070,626044,200800,258987,717987,324440,7777,158749,700113,881919,783898,803135,791266,244154,146355,452094,854591,440271,978627,53783,515615,941336,956932,178679,818600,211272,838675,460318,407562,165101,341824,454658,34685,704265,961656,334980};
        
    // vector<int>v={1,7,6,18,2,1};
    // vector<int> a=solution(v,3);
}