struct Solution;
use std::collections::HashMap;
const MOD: u64 = 1_000_000_007;
const P: u64 = 26;
impl Solution {
fn longest_dup_substring(s: String) -> String {
let mut lo = 0;
let mut hi = s.len();
let mut res = "".to_string();
let s: Vec<char> = s.chars().collect();
let n = s.len();
while lo < hi {
let mid = (lo + hi + 1) / 2;
if let Some(s) = Self::exist(mid, &s, n) {
res = s;
lo = mid;
} else {
hi = mid - 1;
}
}
res
}
fn exist(size: usize, s: &[char], n: usize) -> Option<String> {
let mut pos: HashMap<u64, usize> = HashMap::new();
let mut hash: u64 = 0;
let mut pn: u64 = 1;
for i in 0..size {
hash *= P;
hash += (s[i] as u8 - b'a') as u64;
hash %= MOD;
pn *= P;
pn %= MOD;
}
pos.insert(hash, size);
for i in size..n {
hash *= P;
hash += (s[i] as u8 - b'a') as u64;
hash += MOD;
hash -= (pn * (s[i - size] as u8 - b'a') as u64) % MOD;
hash %= MOD;
if let Some(end) = pos.insert(hash, i + 1) {
if s[end - size..end] == s[i + 1 - size..=i] {
return Some(s[i + 1 - size..=i].iter().copied().collect::<String>());
}
}
}
None
}
}
#[test]
fn test() {
let s = "banana".to_string();
let res = "ana".to_string();
assert_eq!(Solution::longest_dup_substring(s), res);
let s = "abcd".to_string();
let res = "".to_string();
assert_eq!(Solution::longest_dup_substring(s), res);
let s = "ababdaebdabedeabbdddbcebaccececbccccebbcaaabaadcadccddaedaacaeddddeceedeaabbbbcbacdaeeebaabdabdbaebadcbdebaaeddcadebedeabbbcbeadbaacdebceebceeccddbeacdcecbcdbceedaeebdaeeabccccbcccbceabedaedaacdbbdbadcdbdddddcdebbcdbcabbebbeabbdccccbaaccbbcecacaebebecdcdcecdeaccccccdbbdebaaaaaaeaaeecdecedcbabedbabdedbaebeedcecebabedbceecacbdecabcebdcbecedccaeaaadbababdccedebeccecaddeabaebbeeccabeddedbeaadbcdceddceccecddbdbeeddabeddadaaaadbeedbeeeaaaeaadaebdacbdcaaabbacacccddbeaacebeeaabaadcabdbaadeaccaecbeaaabccddabbeacdecadebaecccbabeaceccaaeddedcaecddaacebcaecebebebadaceadcaccdeebbcdebcedaeaedacbeecceeebbdbdbaadeeecabdebbaaebdddeeddabcbaaebeabbbcaaeecddecbbbebecdbbbaecceeaabeeedcdecdcaeacabdcbcedcbbcaeeebaabdbaadcebbccbedbabeaddaecdbdbdccceeccaccbdcdadcccceebdabccaebcddaeeecddddacdbdbeebdabecdaeaadbadbebecbcacbbceeabbceecaabdcabebbcdecedbacbcccddcecccecbacddbeddbbbadcbdadbecceebddeacbeeabcdbbaabeabdbbbcaeeadddaeccbcdabceeabaacbeacdcbdceebeaebcceeebdcdcbeaaeeeadabbecdbadbebbecdceaeeecaaaedeceaddedbedbedbddbcbabeadddeccdaadaaeaeeadebbeabcabbdebabeedeeeccadcddaebbedadcdaebabbecedebadbdeacecdcaebcbdababcecaecbcbcdadacaebdedecaadbaaeeebcbeeedaaebbabbeeadadbacdedcbabdaabddccedbeacbecbcccdeaeeabcaeccdaaaddcdecadddabcaedccbdbbccecacbcdecbdcdcbabbeaacddaeeaabccebaaaebacebdcdcbbbdabadeebbdccabcacaacccccbadbdebecdaccabbecdabdbdaebeeadaeecbadedaebcaedeedcaacabaccbbdaccedaedddacbbbdbcaeedbcbecccdbdeddcdadacccdbcdccebdebeaeacecaaadccbbaaddbeebcbadceaebeccecabdadccddbbcbaebeaeadacaebcbbbdbcdaeadbcbdcedebabbaababaacedcbcbceaaabadbdcddadecdcebeeabaadceecaeccdeeabdbabebdcedceaeddaecedcdbccbbedbeecabaecdbba".to_string();
let res = "aeeebaabd".to_string();
assert_eq!(Solution::longest_dup_substring(s), res);
let s = "shabhlesyffuflsdxvvvoiqfjacpacgoucvrlshauspzdrmdfsvzinwdfmwrapbzuyrlvulpalqltqshaskpsoiispneszlcgzvygeltuctslqtzeyrkfeyohutbpufxigoeagvrfgkpefythszpzpxjwgklrdbypyarepdeskotoolwnmeibkqpiuvktejvbejgjptzfjpfbjgkorvgzipnjazzvpsjxjscekiqlcqeawsdydpsuqewszlpkgkrtlwxgozdqvyynlcxgnskjjmdhabqxbnnbflsscammppnlwyzycidzbhllvfvheujhnxrfujwmhwiamqplygaujruuptfdjmdqdndyzrmowhctnvxryxtvzzecmeqdfppsjczqtyxlvqwafjozrtnbvshvxshpetqijlzwgevdpwdkycmpsehxtwzxcpzwyxmpawwrddvcbgbgyrldmbeignsotjhgajqhgrttwjesrzxhvtetifyxwiyydzxdqvokkvfbrfihslgmvqrvvqfptdqhqnzujeiilfyxuehhvwamdkkvfllvdjsldijzkjvloojspdbnslxunkujnfbacgcuaiohdytbnqlqmhavajcldohdiirxfahbrgmqerkcrbqidstemvngasvxzdjjqkwixdlkkrewaszqnyiulnwaxfdbyianmcaaoxiyrshxumtggkcrydngowfjijxqczvnvpkiijksvridusfeasawkndjpsxwxaoiydusqwkaqrjgkkzhkpvlbuqbzvpewzodmxkzetnlttdypdxrqgcpmqcsgohyrsrlqctgxzlummuobadnpbxjndtofuihfjedkzakhvixkejjxffbktghzudqmarvmhmthjhqbxwnoexqrovxolfkxdizsdslenejkypyzteigpzjpzkdqfkqtsbbpnlmcjcveartpmmzwtpumbwhcgihjkdjdwlfhfopibwjjsikyqawyvnbfbfaikycrawcbkdhnbwnhyxnddxxctwlywjcisgqfsctzatdgqqauuvgclicdrpjcphysqdjaflpdbmvnhqggixxzcmpsysbwfkzwxzjictnngufpqhcxlbkodyrqlfomlkiefbmcfenugzqnyqqvgpxonmizkpjdlaqyyowjagzkzrzvcrupfyofeftyfvoqorzvxphhdhydnqiyiczfcgzsecxzsoaobwrixcajabjnvtoerzwayjowahrmuixmmkbtchogfizmvbjnpespxngxjxntohzatlpkcmpphmewevpteharnszafbpbexrvnbedieojezdhnyooiivhnhakilvkobxepbksnqrtxxuqhalvtjspyvporalbliiwjciamlhttaydhxoelimuorjnfvebjhcocbkrgbguwdncodskzzoqrzgavsbjcippetltqaxjhkqacwlgmsbxezqubyzeznnsoqegkykzlxohvitbmjcxllbrvgdijyovpjyeaojlyxqwnheyblznwoyikhqiutotpfukyqkvatxotulvlqzfcvskdccuixthzqrwymzccosjmjqjigehcnfphjuuybaxxukconatzseljyirycbhucxmwwftulfwfmyqyprlnsmxzyfmgjctgeunuuexhbrbsaaingqxqrjvpuhbvcmyztmkgenhonajrkzfrqjinjrbmjyinhwvlcmmxvbgvjgfmaoliosmxbonvlzoiqvkxxtoposygcgkcotohcrauivxxvmrghuauadwojxjligrgstczirnvhqpzwgjbvqzlkxltqnqrfxieggnuriytavbnouwhuamdtlspednyckixkhxedjmotiuucewllthhducwgwmgzxsbkqzfnqfynwisvsctyqdoaiypjivtxkxgoyhwhccklbdjoqykaqzljejlizgbehekmkfetvgfstmypmfnyoundudqlorcogbzoznddfalthwpmiewkmvogmzirbprjftbtffjrkrfminnechitfyfaujgtugadqbrskulsjbaunonxolauvsifevpdyurvfocxtkizflcuvltzuhwyhlbxaphifhtgkfktfnnmocpenrlujsuppbbuorvtubuiyszawzftijwhwgdyubjmmodzybiyunksuixnkariubegpdgctbayaynfskkuyhjvegsjwsbppodvhpjdjlzhxixswdncapxyfjspxeqxdfkhockvrzoisikaymoiqzqbjyoscwegfomlnurwboesfiszetebjblaolnovgvfcpnbemwambkhwcgdbhvkoluhjfxlfrfaeedocdilaboesauplmttewlbojkocklhsbzrtzeyhqtmgroupbzlymupmupsvlkzchclujuozzmngjvktzstsvocxrziuxelruwojzaleyrkjkdleavwqxwgjdbtiywqtdtaamrlcjogxufhgvoqpqkgopbtyqchzhexqgecheahjzxapqjdylzjqhzlzssbjmokncxalgasexztnlzfisxxpeerywlrjdohprewwnlwdbtwmfnnxnoolfhqqxzcvoymdbvmaoliedpvwzyvgyrwjguvoqnxrnaeqwvcfrqkwjmlvxovptultyfuxerelpfgctnpdxluqeruxkxqntosggfjqmrnlnkhhilznpycdrnemnktcsmzufpqgiraphzmgfhevzejhavsypohpttnnowfahpxfwmvxgwfuomxemdkzdlzldesmowzmhwoydnsovwykxqyllbmcurlvtwcfwxvvkxfknwwcwfjkzjtonalgijdsulcfagehiptszrcltbbypopdbmdfkyofelmrdmdbceguyxnkheqqtbletpqmjugpckmjyuuvsbqhyzmposwcgscnishluuhnwkyrkujefpgtsqrmcoortgitpdoagdncxlofkqozgngbtmlyyoyodcmcwetdtltupjrtemrjswekkfjvfecmvagyptjjuwsqpjwlxxosqhpssdvjraaicjfwvesyqfbumjjbqytkinpldxopxjzmvpigmberobyzyxwvwmlmbziduqhmbescgkvhgqtalmaxfsjlysmvrizgvrudstiwmaahtqehfbofvqwgqygvseykmgmhgjbxcrtdjqvojvyhohallyewqelzhjeuqmmsqhkluvqsfmxzbqqokehfoqrlqmwpnwojfowqpqebnuggeuvsszgfywceolvabyvbrwatuyherijsdqvpyyhdyradbammmchqkvdbxpbrxzrpfrsiiezvowrfqejibvociujtcwbygvfwojgfnvvwqlqqgipxhrogppzghtnweodaxuqxknnqnajlnsvheiycsvifvoljsncgnunsqcymnyoeeslrjflpprvtksimffvnuvakskdakvmlkpowfpfzdrcfctikhvvbagrvjlzjydnlmspzyynyjjfxnozpjjgjelipswsmfroitqphzsuqgumlnkxksbzhrsvcnfwufofhurmhksvvfjzggbtgrezkrkqmhduyqgwuwxoxaiifemtwrbilftiuhcgpjvqxldrnlzphdffncevlcyrxlpbwuswjfdegexeoooshdfqtqithpfocyowaqeedikssptyvkabhtaeotcwxccgguuotqvypugpcbwzalxwqbjdcokoxjnqhggpbbfeyjiellsikiqqtxpvzmjsfleepjpbxpeicxfcwbpprzgcrjgjaxshewradetsqsvfmcxptmksecfpynqzpctqpogcgokzrkltsbmwxkmynasohpkzjupapngusnvdjfqezqhyikllgkelewwwhhbdjvxdagnnxscjkotbbmhzkqbjwuwidrnvmztikmqjcxmcpgkoudhydmdvberfuvjnhlnfcsbpzmuquvrgogtfwefhqzkmxxgadtvjpxvurxprbsssihviypclwkjfaatzjxtvlzwaacqlwnqetgkldqaqghuihrgxbbpmjfsvaigqrhiiskkfibaeilqptkdsqqfwxeixuxgkiboaqnuaeutjcydnxyxnmattjrrxmthwvyipgazaxgrrjcvdnyxpktsldhluhicyqprxhljyfhawuvoonrwyklcdlmdvsgqrwqqomisksftsfyeifmupvylkjbagzyctuifbsrugqsbrkvskmundmczltpamhmgqespzgrkxebsvubrlmkwyqhjyljnkeqvdxtjxjvzlrubsiiahciwefwsswgssxmvyvgjrobvubcbgjomqajmotbcgqjudneovfbjtjzwqtsovzshmxeqofssukkvcdwlsdtyplrlgwtehnwvhhegtwkwnqqdiajpcaajsylesadaiflruewhrbrogbujbppunsqgytgnyuhnkejhccavaptbydtqhvyatftxcaaljyhhkkadzdhhzawgndunwwgknnbtqaddpszqgummmnomfqmdxqtwjexsbadfdqhnyixjslsaisscocbabivzokkgiinqqzsrtfpzjmxfkqmuzzlelqjtjidjarkwbwlcqrefokrlwdmuzyffdtajnqoimlzzpcgpjjwlqkusefzbgznhexzojxnzxmmedobgvdabtdoiskozrdrjscxwivaekrkyyfynuktmgyziteavdxfctvkfkrmsdwpaywzbkeojeycwdkectydojttisizruilwokhepscqdnjygiakomkhyujaffxjyxqmvkemqihpcdygprdeaxgjbkonfvgtzayfbmgwsskoyxjlknwwtehhhpjllhkcblyaxnbekoidbbyqvdqqsyfcemylmqskpxifcnhmemkkitqtbfwhmyemkzightkjbhlquticivpeeclpamsqoztxvdtcqbsonxyecnhcadtghkjckhrcdfggnqlwurydzbeybqkcfnnbwkciwaqdzgmcrbltvcuftxsqfpxnoombsbeoqxivgtkrjklxatgcorkdrvmngwlekeopgecefzxtprcoajoopxviijxilxfiwuajsbtcctfcqqgzhyjmonwdbyjlnneidyaqhhothzpzaxcthvbxpdcqofaeamxbqjwhunnqwclhcqhagawjsxygorgbuqryzickyplbaivkabbrkibqzqacabbwmnpndaqvbknbqcjuywxjrdbznndomwbbqfgulwczydrhrocebhygriiwxmwtjjyqqiqrjblxuamddlsiocdoysdaacuovljtpgocephnxuugdyggsnhcqiqhulyhlxiwzvhrtbmvjnhacwunckqzhpcthqgsupptdwkfeprbg".to_string();
let res = "maoli".to_string();
assert_eq!(Solution::longest_dup_substring(s), res);
let s = "baaddcedaabeeebbddcdcdbaedcadbcbedddbbcbcbcdddbdddbdebecedabbdccdabbaaeedcbcacbcdebebaeeecaaddeceabbcaddabeceaceebedcabbcdcdbabdeeeacaceabaaaaeaeabbdecbdebedcedacbecccaeacbadecedbacbcdcebddebabbdddcdbbdccbdaccacaccbaabebcdbeadbdeebddbdddbabbeaeeabbdbcbcaaccdcabaebeadcaddeedcabebcbdbbbcdeeabbbadcbbadddadaddeacdbbbbecdadababacabcceaccdaddbcbbbccbdddacadcddddedeaeabebcdcaccceeecbdcaeebeabedbececeadbdcdcedadbbebedaaeacbedecddcabeddbadaaeceedbbedaadcbdebcbbbdcbeccaadeacdbebaedadadddbebccacecbcecdeeadaebbdbaeeaeebcadcbbedcdddacdeeaaeeeeebdccabbdaecdccaeacbecbdbadccaeeeeaceeabcacebebbccceadebeaeeeeceebaaaecbaccaccbccebeceaecdbbaacaadcecedddbcbacdaecbbddbaedbbbbbeacdeddaecbbdabebaaadceaabdedeadbbdbebbbcedbddaedccedcbebbdbbeaecdaabcdbadbbdbcdcbdeedbcbabebaaaeceebeccddcaaeebbedcdceeeebeaddcdabbcdbebdaabaedbeacccebbccbecaeeacbdaeeccdbdeadcdebbcddaeaebdacdadbecbacbaccdcaddbdcabadcdacadadbdbedadbecacecedccabbceeeeecaeccceedacbaeadacdcddccaeabbcecddddbbabaeeecedbaccabceecbbeedacbbcdddadccedbbcbcadccdddedeceaccdaeedcaebcdadbaededddbebaabdeebacabaaceabdeedabdacbeddadeaeedbddaccaacbababeeaeaecdbdaeabeeedbaeeddbcceecceebabbebebdedbaebbeebddeeccdabaeaecccbeeebacacdbecadabdcdeedeebccababdeeaccbdbbabdecdbdebabdbeeadacbccceebdeddebedbbbcbabdccbddeaceeccbecacdbbaecbbaabebadbbdbababddeccbcebcdbdbcebddaeaedeebacaaaecbdaabdedabcbedadcebbeadbcaadbcdbaeaacddeebcbebbdbecbcdebbcaaaacddebedabdaeeaeeaabbedcdabdceeaaddcbbeadccbcddceedcabbaecabadbadeabdbdcceaedcdbcdaeaebdbdbaacdeccedbaeeabbadaaaecceabceececaacecebabebbdebadeabdaadbbaebeeabebbdbeeccceccdbaceabbbeeecdccebdadeabbeddcdacdbeedbededbbedddabddeacbdbeeedcdeecaebcbabeecadccbedbeaadaebdcabedecdeacaccbeaadabddeadddccccbdcdecebeeceaadbaaabdedadbdccbdeabbdddebebcabbebaaabbbaccecebaecccaadecddbaabeebcabedebdabcbccaeadebabaacddecaccdacaadbbcdbdbdbeddedddebacaeadbaebaddedcebccdbbdcdbcaaaaccdaaceaebdadaceeeabedcacdddeeabecbacdcdbcebabccabecbbeeedbeeccabaeccccceaeaaceebcaacabbbcacdcebabdbcbaeeddaccdeadcbdedeabecdaecadbcbbdbcececbdbcdcbbbbdaacebccbaacbcaaeadbcbeeedaceebaeebadbbcceddbdaedabbdacdeadabeadccadbebcecbcdbaabbecddbaacaccbbbeaeadcebdccbaedaabdadcaebbdcdeaebeecdbbdbaadaedbeecccddacdedcdebbddaeecabebacaacdacdadcecdcaeaeaecbccedabbceebacdedceedeebbbacddacddedbaddaccaebeebeaadbeeeecdcaedadabddebcbcddccadaaadddbdbdccbdebbcededcdabbdbbdbbbedecadbdebebdedeebaadcaebebdececeaabbdaedeebbacecdbcbddeaaabdcbbdbabddabacbdebcbcccebdcccbcddcebdcbededbaadebebedcbebcccdddbabbeecbadcbeeeabbadddbbbcedcebbaabdeceecadaabdeaeabbebabbcedadbddcbedadcaededaedbeaaaeddadddabbeeaddddaaadedccddbcebeadcaebaaeabeeebecccbaddceebceeddabbdddcbeeadbecddebcebebeedcedbeabdbebcccdbbaadbabcbebadbecabbaeccbbeecaeebccdabbdcbadbdacbdccdccebeabceaaecbbeedeaacaddcedccaabaabeaecdadaceacacdcdcadabeacbeeabdcdaeceacdbdccccbbbaebcceaabcbecbabebcaebbbbdeaebbebaeeacbdbaddeaaeacedbdbaedecdbaecbbeddededbadbbadebabecdaadddbadeaabbeaebbaaeeacebcceabaaeabaecbdaeaccbedccceacdaceacceddaccdeddbaccbabdabdbcbeceaadcdaddbadeddbeceacbbebeacecccadcecacbecbacadbaaeaebbabceeddebbcbabbecbdbadcddddcebdabcadbbaeadbeadcceeccbacccbeccbdbaecbbdbeebbebbcbeccebccdcbbabcdaedbaaaaceeebddebdcebaecbadedaaccccabebdadbbcaceabbddeeeebcaebecaaaacaccaacddddcaedcdccbdabbbabbacdabedbbbaecccacadbacbcadabccedcababaedaceebcaccddeecdbcbbcdbbadbbbcccdcbdadbccaacbaeabbaecabccebcddbdbbbccbbcccdebbcabadcaeeecbacadaceeaecddeebeacadeabdabbbcdaeacdebddadbeeedbdbcebedbabbbebeaadabdabebaebaabdcbbceaececabecbdadeecccdebcbecaabbeccaedabbaaddeedaedbdbacdcaccbdbabbdebdebceceddbcddbabeebeecadcabbaedeabebdeeaaebaebaeaaaccbebceedadbcbbbaeceebcaedecbbebddccaadcadccbcababcadacbcabebcbbeecabbeecebeabceddaaeebdbdeeadeeebadbbcaaebcdcdeabaaecababaccaadcdebdeaddcaabaaaaedbadeddecdeaaecaedceabebdcceecdbcbcdaceeacececcadacaebadedebebcbcedcdbcadaddadbbadcebdeacceabaeedecbebbeccbabaaddddacccbddebbcbdedbebcccbbaecceeeccddacccaddecdcbaebdebbbccbdddeadaddacdcebebeedccddedddcbceadbbdddcabddbbbbdbabccbedcacabecabdeccdecebdbbcbdcdcaebbaceededeadcbccdbddbbebeeddbedaeadbdabebdcdbeecdaecbcecedcbeaceacdeebaadeeebaaeecdebeabadbbdbbcbeceebeeecdbdacebdcedbecccabdbaaacbeaecbddcaddbdeeeadeadedabacdeaadaedbdacccbbacadadedecddbcabcebdadeaecbeeaabacaddaeebcbdcabeacbddbecbbbbacbdbbdecebeedbeacdcabcdadcadcbbadaedaddabedbbbbabeddacedbaddcaececbdebeaeeceaecdedccbaadbdabdedbeccaeaddbaaabddbcabcbbbddbedbceddcdbcdbeeebbabbaedcdbdedaccacbddcdbaaadacdaabaeebdcedbdbedeeccaacbdcaaacbacccebcbadeececacbcaaaecccbabecedaebdaebdaecacaebceeddadecedbccdaababccadeeddbbdccecbddbbdacbeaabdaabebdaaebebcbacdccacebccaadaacaacbbaaaaadbdcebabddccebccebdbcbbebeadcbdcbaddcdaceedebdcdabaaeaeccdabadbdeacbaebcbcbadabadacdcebcdeaebddcabccddbababbadddaeaecbedcdeceebdaeebdbbdebabdaeeaedbcbdacdbbcbcaddeaaadcdbcdcacaabecbceabecbccaadaddaaeaccbbacceceddaedcebeccaaabcadaaddeacaebcdbbeeacbaaecddeadddcabbeebecdadbadceadecedccebbbcbdcbbceeedcbdcebaddabbdedceedeeaaabcbcecccadaebdcaeccabaaeebbbbaecbcbccbbacdadebcabbceeddcaebdccaeedcceeddecaaeebeeeadcacbacdaacbbbccdbdecbcaaceddaadacdcecbabdebdececeeecbedacddbaeaecbbcadeecbccccbcedcaddacdeecbaeaadeddcdcbabbabaeadecdcaaaaddbcddbabeeccbdbeaddbeceedbdbdcdcaabebcbacdbedbadbeecbbbdaabcceddcdabbdbdadbdcddeccbebdeaebbbaacceeddcbdadcacdaacebaeccdeacaddcbdbaeadcaaaceadcddeaaedadcadedaedacaaacabcdaaacecdbbabebebdeaadaecdcbbadeeecdbccedeebbddebecadcaeaeacacccecbadedaaeebddaeebbadcedaaadcdbcbcebabeccdddcbdaaadebeddbbdaeaceabecadcdecabdddbcedcdecceacbccbdbcaebbdbaabecedccaaceecbaabbebdeeaceedeadbaacdcebbbabdccaddcecedeebdeadebbacbcadbbcabccddeeccdcbdbcdacecaceddcdbaeececbdcaececdedabcaaaecdccebadedbdbbbdccececaeaebdacaddeacacddccdaccccadbecceaedacaacdabecdbbabecacabdebddcaadeeacccdbabebbbedadebaedeaaeeeaceaabdbccaabeabaaddbeaaadeabaddaabdcebdcebbedadacbeecddbcadbdccbabeeaecdebabdaabbcecdaebecebcaccadceeaaaaeeedbbaddeadacbccadbbeabeedacaddbaadabaebeaeeedbcbeeabebeeeedeaeadeccbbacadadbbceaacaecdcbbbaeacedbabcabddeacadcddaaaddabcccecbbcdaaeaccadbeaabbcdebcebdebdebabdbcdbdceadeccdabbeeaceebaadbdaadbcdeaeadbadcebeeabcbecaeaacbdceccbecadcceeabcabccadcddbdbcaabeadcdbbaeadacbbdddaedbccaadcceaacbaaaacbeaeaebdebdbdeaebcecaceeaebbebcadaadccbccdaedbbdbcceecacddeeadedbedaeddbaccddaecbeaadadcccabbeeabbecebdaacabedceadaebbbbccdccbabbeeebaaedcdecbaeaaaabdabebeacdcecaedbddbbccbcccceaedbeccdcdebaeaccbbdecaeeebcaebbdaacaedeebabecccdcaadecaeadeccedededeaeeddebedcdbeecedaaecdbacdddddeeebebacedabebbbeacbcddaeaeabbbcbcabdabcbdaedabbdbacedbebdcaeebecbacbeaceababecdcdaabaaeadebddeccdaabdececdaeceecabbbeeebceabbbbdebadbcccbcbdbbceeddbbddcbbceeeabbeedbddbdacedddcdabeecbddceabbccbcbededaaaacbeeaecaeccceddebeebeeacdeabbaaedcbedcebcbadaedbaddcaebadadccedeeabdeaeeaeaebaccabbeaebaedccaeadadbeaebbeceddeaecccaaadcabceadbedecddceaaedbeebeacaaebeeadceccddeebcecedaebaedacaedccbaebbedeeacecaceaaddaceaabdaeeeddacecabadabbdebccdccedcdaceeabcdeaeaedbbdeedbdcabecdcaabcaebeeabbbdeedaaecedaabbbaaecadbbbcebaeceaadccdbcaeaddccabcedaabecdeacebabbcdbbbacdbaaeebddeaaedcbccecbdaacaedccbaeaddaddaccccaceecadcadecbcecccabeccabaaceeccbeccbbdddcadbeeaeddcbbbddccacbbccbcdabbbdbbeddaaecddaecaacdcaaadaeccdbdbecededcdcaeadbdbedeeddeccbdbceddabececdaecbacabcedccceebbadeeabddabeceabaeecdaabcedacedbabcbeddddddebaaddecdacbebeadbbebbabeebcecacaebedebedeaeaddbbdbdcbcbcbadcccbddbebcacdebcedbbbacccdbaceacedabdacecdeccaaceaddbbdbeaeadcbadbeccbdccceddbcdbeccabcaaebbdaeccecdbbacbbdccbbededbdeeaeabeedbecadddcbdbcdceedecbaedbbcbabcadbbddabadcdbaeebcaaeeacbbbebbcaecedaebaecdeedcecebeebdabcbecdaecccecbbbbcbacebbaeaadabaadaebabdedcddcbcdddecdaaaaddcdedeceebbaddceeeadbbddaecaadabcedeabbcdddacbccdceeacddebaaacaccdcecbbcabeecdcbaabaececdbdebbcddeeadccddbecebbeaebbcbdddedbecccecacacabbaeababceddcdcaebebaadedddccecbebbbabbbeecddbbabbeeeeceadacadcaadcaedabdcdcacedaddececabbaeaadeebcccbeeeecbcaddacaceceedddabcccddbacbeeecbceeaeddcedaceebacddbcadbbeedaaecbbbecaeadbeaaaddeaeabdceddbbeaceaddaabcbabaecdcbcecdecdaeeeaccacddaaccdbbdeeeceedccbdeeecceaedecbeeaececaecaacbbbdcbcededbbbedbacdddcedbcaaebeaaebaeddeeeddabaddbcbcaeceedebcaacabeecedbacacedddbddcedcddbadadbdaccbbeebdbbaadadbcdeeaaebbacdbdedddcacaebbebbeeecaeacecbaaeccecbcebcdaadeeadcbddcebaeebabeddcddccacbacbceacaccbccbbcdaaebdcbacaebdaabebcaabaaebeddeaeacbcedbccbdebdccadaddacbebceaaabaebbddbcdadbcdcbdeaeecdadcbeabdadecedcdcdcdbeacddeacaaccebacaeddbbcbbdcaedadddebeddbcaeebbcdecbdaaaabcebdedacceadcccbaadedcceeccceabdbcbecccdbcbebcabbbcaebacdbedaaabcddbccadbeddccbeeceaeceacdecadedcabaeecedcbbbcaecdebbacdbdadaedaeacadbebecaaaaebadeedbdcebcecebadebeebddeecbacbadabdcceabebdbaaabaacacbebdddebcaebbbeecbdccbdcabdbddbbbadaceeaeecddcaabadeedeeebbdbbeaecbedbadcbadcecacacdaecbabadcceaadbdcbacbccdeabaabcdbdaaacdaedccbebdcbadccaddbccededeadaddaccaebabcbbdcaedaedccdacbaacecadcdbbaedbcddebadbdaedceebebacdceebeebaadaebeaeabdcbadbbaddbdabaececbaebbcdccedccbadaebdbeecaeedeeceeacdaaccecabeeaedacccccbaacaddacbbcbabbadcccaaabadcabbbadaeeaadacccacedaeecebccabcddeeadacdbaccebdabbaabadbecadadbbadeeebcbddaadececbcebbddebcebbbebccbdbedbdcebacedaeddeddaebcdbdbcbebabdbcbcbbeebaaeeeebcaceacdcdccaedabacddccbbbdabccadbcaaeeeabcbdeccbcbbddbbdaedcddabaccdacebacdccbbecaaeccadabddeaccbeeeecebdeecbceeddadadcacdecacacbddbdacbcdbadbdcddeedcceceecbaeecbcadacbbbabebceaadacceedbdcbcaedbbbaabadbceacccbbbdcbcebecbbabbdababcdbebeedebeabaabeaeaccdcdcecbdebeedbdbaaadbacdadcceeecdbababccbcbdeababbbbbeedbaaaaecccdacdeebdcaadbdcdbcccaabdbbaceceecdddecaeaddccceabadabbedbacdeddeebdceecedbabdcadeaabacaacaacacaeeccdbeebaddddeeececbababdebbadccdbaaedacadaccccceaebecedddebdcdddddeaebecabadecedddaedececddcdcabdcccedceaaececdddbdeddadabdceeaeaacceaedeeccaccedaeacccddabccdacadebcebdbbbbcedeacccdbdcbdcddebbceacbbbcedecabbecbcdcbddcebdebbeeedecbaeacddbcacbcebbbbceabdcceeaeaadeceddcabccbceeaaabebeaedaabecccaeaceacbeddddaaaceaaceceeabebcabededeeaeddedabeaeeaddaadccaeceabaeeadacaceedcbbcecededdecdbaadbecbaeccedaebacbebeecbadcadeadeebcbcbadbecdaebdbccaeaacdcdeadbdbaceacabcbcccbdbdbedeacbbdaebbbcccbeacddadcaeabcaecccbbecadcdddbcdbcbbcbadabaeccedbbcbdbecabcddeacbbeacdcdadecdccdecbdeebadceadbbdabbcedbceabadaaacdddeccbcbddeeceeebbedbcbabdbccdebaaacbbeccccebdbddbacbabbbacacdecbbbcdaacbdcddbabccdeaeeaedeebedbeacddcceecaaadeacdeeeaeaededeadddeddbbacaddbbdbdceceaedceedbaeeadbdbdbeedbadbdacbdecebecaaeebdbadecabbcdeeaccababdcbdaaebdcbbbeabdcbabdecbcbdbcceadabdeabdbbabadcebabeccbbdbabcaeebdaedeebcbacaddeabdbdcbdcbcaecacabbbeaebecbccdacdcdcceeccaeceaedacadecaeaeebbeaebdcbbdcecabbbacebcadbeedeccbaaeebdbeeadceadddeaceadddbbccadccbdbacbddccaceecadbeeddeeecaebbdbeecababcbccccbaedacadcedbbeedabbeaacdeccedeeedaadaddddcebbeeaeaeaecabdbbeaedaaacbecabaaadcdabadddbeaaedbdaaebacbbaaaeaebaedbccbcabaeabcecbeacabecaddeeeaceadcebddccbdcaadcaaacacdeacecbabdaaebdddcdedebacaeadbeecaaebaaacdcebccceddddeceaacaebddaebaeeebddbbabcccadbedcabcdbececacececbcbcebbccbcedbdcecadcbbeebccddaebeeeaddabbcbbbbaaccedcaccbadadcaadbebebaadeaceacbbcacacddcccaababceacdadcaceabcecadeddeacdaacebaabebaebeaceaabddeeccbabbdcacbdacdbdeeacaadddcacbababeeccbbaccccdacdedccdcabbddecacebedaccbbeeabedeadbcadeeaadabceccbeeedbebbbabdbacdadbeabaddceebddebdbabdbdadedcacbbbdbcbbdaacabcadbeddcacacdbcdcbbbbaedbdbcadbbaaedbddbeecabcebbebaedcdcaabdeeccdeeccaeeacabeaaacbdaeabeecaaedabbceebbbdaeeabecdadebcbcddbaaaedceeaeecbeddaaadacdccaacdbbdabaaebccdcbeaedcbeabebaaadadddaadeeededdbebbecaabbdcedebdddaadacbbbcebbccadcbaddccedcedbdebbdddccdcbbbaceaaedbecccceacbeddcebbdeacbeeecbcadcccdabebdbeecbcdaccaacdbdbdabadcabccedcbabeeecceccddcedaaddceaeedcdbebaadcdeaebabaaaedceebccbceaebeeeecbaecbacdcbedabeccaeaeaaddddaaedbebbbbbbabcadcccaabcacacecceeaecddbdabddadccddeaacdbcdceccbebddcabbcbadeccaaddeaebebedacccdceceebaaeceeeddedbaedbbcbaddeddadcbeadbeebdbdebddcacdccccbcceddaabebdcbcabcabaadadabdabadbebebcdcbaedbdeaeeadacacebbeccdeccdadeaacaeccbbbacdecdaebaceadbddcaedabceaebcaaeadaccdabedcedbabbcbbebbeecbaecdcdbadadcebddbdcbeeaccdbcdeeaabdebeaaeedbabcbdbeaaaeededddaedccedeaeecdddabcdededacaabdcccddccacddbdeceadeecbcdcdbadbcdeaeceeadedccceecdabcccccbecedbebcaaccceacbedebeaeaaecdddadeacebbaadcaadbadcbddeddbeedccdeceaebeedbdadbebdbdaceabeeaecebeaaeedabcbbadebbdeeebeaddadaeaacdeacddadcbdaabbddcdedadbebaabccdddcdeeaeecbebdaceadeebceebceddabcadcbcabbaccbcdcadcbeddddcdaddebebcbcdaaddceebcdeeebbccebecdaeeabdadcaadaeeddeeabeaecbccadbbedddbddadeeabdaebbceceabcdebeaeeebebacbdeaeecddddbaecaebeabbcdcdeecdcaeeaeccddbcbedaecebcdddecdbdccbdebeebcebeadaecbbdadbdebcebdadedcedabacdbdbcecebbaedeaceacdacaeaeceaddaceeedeacecaedcecdddaceeadbbdeaccbdbcddeddeebadebdbbedcdebdbcaeaedecdbcecbeceadbdebdadceeadaadcbbcabbeddeccdedcacaebdadeaddccccaedcbcdddbcbededdebcdaebcccaacedbbccdbdccacbdbbedcbcdbedbdbaccaedecdbceadacbdbbcbcdbbbecbcaaceabeccabaabbaddedacbcbbbabcadaabebcbcaeabccdbaaebaedeadcebedaaaabdbcbbdadbbdeadeecbdabcbeceedeeabdcabbaeaeabcebdeddbddaceacbaeabacdacbccbbaeacacbcaeebabadbebdadcacacbbcbabecabaeebbbbbadaabcbcbdaeabedccdebdadcccdabbeebdaeeadbbccddeeababbbbaebeeaaaabdeeeececcbebbacadddbbddbbcadcdaebdcdcacaabdaabcaeedebbbaebcccebccdbbaeeadaaebeeccdbebecebeedecdeaebbcadaccbaddaaabcccaecbdabbbcabbedddcdadebccbbadeabdbdcededbeedaebbdaccedaeaacaacccbdbbdcdbcdcaedbbaabbbecdaddbabababecbbaadecaebbcededbecdcaedbbcceccedcededadbaccdbabaebbacdacebaacbceeaaabcbddcecdaaaedcbdaadcdbcbbacecdbcabcadeaceedabadbbddbaacacceeabaabacbeddebbccbecabeadcecbdbddeaebeabedceababddecbceeeddbbdbbbbeeededaebeebeabbdadeedcaaebdaccecccdaccbcdeaccaabeeaaeeabdccccebacaacdbabdecaecbdecdecbcdccbeaccadaecaeadaaacdeeebbbebbcbbeceacebbbbbdddababcdddddeecebebddedececeaaebcdccbedeadebceeeadcdabebcaaeedeccdabdcbdbdeabaeccbeedcceaccdceabdadecceadcabaaeadceadbbdcaceececdadbdbaababdddedbbdcdabeececaebdeedabdaabcabcdccaebeebacacaedaeabcaaaccaeebbeceabaaaeacaddcceaddbddbcbbbcaedcdceacdebbbceaacacdbeecbcbbdcbaeedeeabcdcbabcccedeadccbbceabdbbeedddacbddcdcbaebebddcbaaebecdabbeaaaddbbbcbeeaddececbeebdaedcdacdcabdeedebaeedbedcecbbbdecddadebcdbaaebecadaeadceadeeaedbcddbedebaaebeeadabeeeadedaadcedcbbbacbadecdeebbedbbdaeaedbaaabbdbbeddaaedcdbdadeebcaeacbbaaeaeaadedcaadddccaaaddcbcbadeeeabbaeeacceaabadecbacbceeadeccaedbaaeeecddddbdabcceadddbaebabbbdbaddcecdaeaeecccbadbdaddceccbcbeaaecacdbabaeccebeebddaceabbcbcaaddbcccdacddcececbbbceccacbbdcaecbebaeaeebceadcacddbaeadadddddbeeccacabecaebaacbaaabbabbaccadcdaaeececdabbcccbaaecaeebddbcbdaccbbbeacaadbddebeddcbbdecaeddbcdbcbdeabdadbcaacebadbaeaedaedecdaccedcedabeabaedbcdeaebabddccabcbadbbdecbcecaaedadacdbcdebeabcdacdbebddcbccadecdbbbebcbeccbadbeeedbbdbdabbbbbbdecbcddadbcebedbdebbadcddebdabddbccedcebbcaeeacacdedccdcebdddaccbbbccabbbeebbdbebdbecedaaabdacddbdedcbabedeabaceccadeedaacddcbbccbcbdcdbabbcdbeeebaabeddcdaebadcecddaadaabecebdbdbbcacaedabadbcecbadcddcebceaebdddeadcbbedcdbedcacbeeadcddeecdbeebbcedbbecceaeeaebacbeeaddbcbbccbeabeabebeeccebcdaacedcabdacdcaabacedcbadcaaabaaaabaeddacacaaeaaabedccebdccacdedbcdadecddabdeadebcdedeabddaebbaaadacadbddeccdbebecacdadbbaadbaedccbeacbaabcbdccddabdbbbbebeacaebecbedebaeadabccdbbcecaeaebcaeeccaceecaaeabdbdbeeadeadcdbddcdaedbccbadaaccccabbcccdedbeeadcabedccddaadedcbcdddedaecbbcbbacbbeabdbebabdaacecbaedbaeacecbcedcbcabdededabeddbdcecbbcaebabdecacdececabcaecdebdaddadbbbaadbecaacbcbebbceccddeeecceecdbeecbadbbadedbbedcdbeceecceddebdabbbcbdceabbadacccbcddedbacadadcdccbbbccbaecbedecedabbbcacdcddcbeccadabebbaccadceadaececcdebcbbadebcbadacdedbdedededbeacaeeecacabbcaeadeacaceaeddaecdecddceccdcecaaecdccaccbbbcbbccabeeabedaebdabaabaadcbcdebabeccdedbbbcadcbcbdaebabdeebbcabacedddbcbdbdbaecaacdadebabaeadbececebeebcdddabbedaeebbecacbeeabddbdcecbeabdcabbdcbebacdabdbbeddecdbbbabacbbbeeccdadcaabbcddebeacaadbecabcaebcedaededeabbccdbadebadabcbcccadeeaacddbedbcbecbbebbeacaaccebecdaabbabcaddceebacaebceebecaaadeedaedaedccdebccbaeaeebacbabecaeaaecbdabaadcbbdabeeebdaabdbbbcaeedceaecbeedededcecebcdaadddeacecbececdecaeeeacebbbcbbabdbbdaecaaacbbdecdbabbaceaabcebcebeddacedecdedabbaadddbaebdcacbcdcdecdeaaeddeaaabbbdcccdccbcbabdcdeaaceecbaedaeeceddbebecdcbbdeeedeebdacbccddbdaecaedbbedaccbecdeaebbdcaceeaccabbadbbebeccceebbdaeccabacaeccbdbcbeebdeadbbeaadadabeabbcdcebaabbbdcdececccbcceaacbcbaeebdeaebcebaeaddabcdddaaddbcecaeaaedaceedaebadbddbadcbbbedecccbabdacbbacecaeebabdebbcdcdedcedadaacbbeeaddaeebcaccdcbdbccebdcaecbeddcbecceabcbdaddacdcddcabcbbabbddcbdddebcbeddbbabbedacceaedbabadcdaaabdcededceddedbccdcddeeeeadcaaccdeddeababcedaaedcdcaccbdbdabcaccceaabddccebadeababeaaccccaaabbbcdacabedbcbeadceecebccbacbdecdbdebbabeeddecdacdacbdaaeccdbeccbdbacbeabcaeedeceeddcedbeebeedacecddecabdabdbdabcadbdacdddcecccbcbcaecacdccecdecabbdadebdaabcacaedecbadbeebecebeacaddaabdeceeeddbdaddbaaebcaaadcaecedbcddcdbccbcddabebdcececdaeebcdccdbacbbaaecdadabdaacdcdbeadcbcecbbebbdbbadbdcebacaedebaeebebbddbccacecddcacebdceeacaeceebeeadcabacacbcbadcdeddecdeecbdacdccacdcceabcbdabeacaacaacbaecdcbadcbbeadebaabacdaecdbeacdacdaaeeedccadaadacdbaeabbedaeadbbbdbeeaeacccebececdbeeebbaeadcceedecebecabadaaeacadbdedbddddcabceccdbdaadceddebdbabeaeadbabbdaceabdbbeaecaecdccecaaceeadeebdeaebdaeaaaadcecdadcaabcdcdaaecbdaebabaeecbbcebeccdaedddcbcdedabeebccacedaddaacecdccabbacbabddccccdbaecaceecaabeeaecccaabbdcaaddcecbeceaaedbdccbecdabbbdabdababaaaacdadbdbebadcebebdbcbbcedecbacecedceaabceaaeedaeabecddaaccdaeaccddeddddebecdedbbcacbbeeababbdaceceaaeadddaddacdecdadbcedcebceeaacbceeeebdbdbcbdebcddabcdabedeebbbddbcadbabdedcdccbecbdceececbcddcbaeeddcceaacaebaddaedebbabcadbbceaeadcaaedaebbbcdedaaebbdbdadedbbbbdabcecdabbebaecbbddebeaecceaabebedecbddcceaecedbadaceccaadcdcbbabacaebecbaccbdadacdedaaacddcaaeeeeedabcbaaecceceeaabbcdedecedbcabbaadcadeabcccaddcecbbaebebceebedaebeddeeeaedabaadcdceddaaadebaabdadaeabbeadbbbaeeadaaadedeeaebbbeccbaeaddaacdbdacaababadccebbbbddcbceabbccccabbccaeaedcccbaeeabddaceabbbecbceaacabaaadaebdaeabcbceeebacdbeccdbaddbbcacbbeadbbddbdaecacbadbacdacacaaacbccebeadeadccbcccceebeeddebaaeabcbececddbccdaddbbbbbadaeaeebeeeccdaaacceaeaaaaabacbdccdccbbebcbdcbacadacebbacdebaedcdeeaddccedcdeabebddccedbabeeaacedcceccaacdbeabecccadcccbccacbacebcdedcedddbeddacddcbbdeaaceaeebbceadbceebcadbbebbbaecedeecaaebddaecebdeebaeeebcdcbebacedaaadaadbbdaedeaedbbbadbecdddbeaaabcccbcccecedaccaedbecbbcdcddebdcceccedacbabaaddbbdeaddccaebabadbaeeebaeadbeebaeeaaabbaaebeceaabeeaebcdbbaeadbbdbacdadbedecdeebeeeaebcbaaacdccacacecabbdbceddddeabeaaaaadaaadcebbaacedcabcdbbcacaccadbbdaebcdedadddccaaabaecebbbccabdabccabebeadebaaebdeaabbcebcbcdaadbaedcbadbcdbbbeccccaaddedbcddebaddbcaabbecccaecbaacaedabcaccaceacecacabdbacdeebaecdaeeebdddeadddeceabbbbacdaaaaeaabdaedbdcdcaadeecedeeddacedebcdebedecbecceecabcdeecbcbbadabedbadbeebbaadcebbbceacccdeabdaaeabdabebbdcbcdeaecdcbcbacdbceaccdeaeaedabdeaabcdcabbbbbbdaaccbabddcbcddbcaacedcdadaaadcbbbbddddeeeeaecddbcbbbdeaaecbcbacdeccecabdcaeaedcdcadbcacbdbeadaeebabacbceabacdcbecbacbdedabacaeddeaadaeaaebcccbdadcdccaedbaddcbaacadbadeeeebbdeccdeeeeabadedeebbcdbdbbecdbeeadeaeeedebcabacebedbceeacbcccbaadacbeeedaaeebbedeedddaebaaaeeaddcddaccbdadbdbbbadebaaecedebddeaedbdebdeddcabbcdcdceabdcdbbabdeddeedcbdbcbbbdcdbddadadeaebbdddaaeddceadcbaececdadcddcbcbebeccdbbbebabaddabeebabeceeededdabaaabacdcdbdaabceccdbbdaceaeedbaccddcaeaccbededecaccbcaebdabcdadbcbbdedcacbeccdacdaabccbabedbeaeaeaabeadeceddbbcdddbeaedcebcccececadaddeeeebbeebcbaeadeadbcddaaaccebdedbddbeeabdaccaaacadebbdacaaebbadeeabbcbbbcbcacaaaecacddbbcbdcdcebbedadcabcccdebabbecabcaebbdcaedbdaddeaecaeebbadceccadddacdeeabdeaeecceccbedbdabdceedcccadbaccaeadecebbecadeeebdaeaebedaeaeeebdddebbaebadacbcbaebebbcdccaeedacaccdeabecabaeccdebaeaeadbeebeacbcbdaaedeebcaddbbdccbdaebdeadabcdbcbaeacadaeaaddececcaabdcceaeeddebdcecedacedaaedacddbbcabdbeaabbddedaebeeeccceeebaecddbcecaecccecdaaddeeaedbdbacbabedbabeeccedcdbbacbabbacbdbaeeddadaabdbaecbdeaaddeacebababcacaecbebdabedeceabdbacdebeadcbeabedacdbedaceadcbeabddecdcccbbebaeebcbaadcdbbddbdccbdcceadaeaceaccecbcebabadcabbeaddcacecbcccbebaeaddbbeebaaaeebbeebdadcdaeebeacedcbeaaadedbcdbbdeeeedaebccacacedaacbebbcccbdbdbbadedbdbadddacabadeabeebeeadedeeadacccdcdeebbebbdeabbbecaadaebddedddeaceebbccdabeeeeaaeacdbecdbbabbcdaacddaeaaaaddcddbcdcdcdaebdadbdaedcdedaaddbadecccbddeeedddbbcadcaeedcbdabbbdbcbbbabaeeceacbdbeeadbeeabdbadbeabbbdaecbeeddbccbceaccbbdabbaedbecabbdadcabcebbbaeebddbcebceaadcadeaedabadbdcbeccedecbceddddaeaebabadadcdbddeecacdbebbdccdbeeaabedccceabecdeedcbedddceedbcccdddcbdebddddbdabaacdabaeedbabaddececeadadaeedddabdbcdcbdeddebbbaaeccdccbaccacbeddeebedeabccdacbaabadebcbdaeceaccaadedaacdbebecccbedcdddecddcaacbbceedadcbdbddaaebebdecbddeeeceaacccabcebdaecbbaeedbdbddddcbecbdddeebecdaacbbdcaaedbbaddedcdcabddbdcbaacaadaabddbceeecbdebaadbbccdecaedbedcbebcdacdcaceaedcebddacbcbaecebcddcbdecaabeaebeddaeddecdbcdeabbdaeedabdccbcadededccccbebcdeacdbdabdcdcbbdbdaabcdedbbdeeebcadeebecbbeedbdebcababdeeaeeecaccacaaeceeabaacbccadceeecccaceaacbcaccdebeaeccdebbdeebcadadcadbceecabdcebebabeaebbaadadadcbcbacdecbebebbaabddcdaeaedcbecaaecabcadcdeadddbadbaccdbbcdbebceceeaabcdbecbcdbadeedaccaecbaeecabeacabbacebceeebebaddeeccdceaacbaacddecadbebadbddbcbaeaeaaccdebadcacddedadeadbbcabccdcceeecbacbccbadaeaaacecebbadadbadeeaabaebcedbeeceaeccceebbdbecbcebceeaaeaebcdcabcaeddacaaacbdedbbaaeebbaabdbdacabecbddaedaddeeeedccecdecdbcccaeecddebbbadbeebcaabccdaaeacabbaddcaceabebedebbddaaaacddedcedcedcbbabaabbaeaeaddbcccdeddacadacacabeebcbabbbbedecccecebbebccadeddacbbacedaebdbcccdcbaccbceeabaedeeaccbaebacdbddaebeecdcaeccddaadedddcadedcbdcecbbaaabcbbeeebaabdeeebbedcdcabaeddcccedaedbddbdbcdadebecacbdaeabebeddabadcbbbedbebbededeccecabaddddedebdebeebccbabcedcddebcccbcbdaaebdcecbeedceededecaedacebaeedaecabeaedaeeadebdccceedbaddeebebddcbcedaacdcaebaccdeabeabcabbdcaecedcbadbcacbbabbdabaedaeaeecdacbeddbcdbadeacbcaacecaabcabcacdbaecbbaebaaabdcedcaabdcebbdedcabdbaaeecbeebddeceddacebadececacccdebbcdecdceadcebacbaabdddeccbedeeaedaeabadbcacaedaacccacaabebcaebeccdabbceddeccdbbeeeccddbaabbaeecddabcbdbeadacaccbbbabeceedaabcbbbaaaedadebaaceabcdcddabeaecaebbaceceeabbebdeaecbccdbcadceebeacaeceaebaecacccdebcabecbecdbaacbeccbcacebdaaceedddedbbbdcdbccddaececadbbbcbddbdbadeccdebacbebababbdedcaceeaeebcdaabdbacccdeabadcdebbaaeaadaebdcaeedacedcaebcaeabdcdababeacbaddaeccceedcaedddbcecacadbacadbcdaeeceeeabbbadcaaaadaebdccabbbadedadbdcdcbccdabeedecadabdedaaacaacdaecbcdbbcaabdcdbebcaccbeecbebcebaadccddebdbdceedccbcbdcecebeabceecbcaddaccaceaccebbdeecddbecdbbadeaedaecceacceeddcacccdeeeecdbbbccaaccecaecaabcccdabdbbaabebdcecbbabaeadddeebacabebceabbdeabbdcabdaebdcecceabaabcbbbadbeeabacebaaeddedaecaccddebebccdbdcabdecbdaeababbcdeccadddbecbebbedecaaecbdbccadbddddaaacecebbbbcbedadbbabcbdccccedcdbdbaaeecacbbecaaccadcdaebdcbededceeedddedabadeadadbcbdceaebcddddebcccdeebbacecaaccadedcbadabdbedcbbebdccbbecacabbdbacdbdecdebcacacdabddbdbbecbcecddcceabebebeeabcdceecedbeddacbcaedaeedabcbdeedabaeecabacddeccdebacdbdeabcebcabeddbdcaebacdcbcbbbbeaeceebadecebaddcdeddccebabdccaadaeadbdadeddcaecacdeaccbdabdcbdbdcdadceeedaecbeeebaaedeaddbdbeabceecbccbebeaceeeaceabddbdbbedabbbdaecaddabdcbddadeccbaeeaecdeaeedaecaacbbaaecabccbcbadeabdcabedbcecbbdedaebedcdbeebedebdcedbbdceeedbbcaabadabcdcabaebacdcbcdcccaceeceddadeaadebceebccbacedbdaceadeacadeecceeaebadceeacaacdedaecaeccdcaaabceeaabdecaabceeaacaadaaddccdbdbadcebeddbbadadbbaaadeadbbbdddebebbbaabcdebbcaeddbbacabdddedeababbabdadeecdabbeecdaeaedcdddcdedebceacaccadcccabadbedaecbeaeebeceacbbbabbcdeadeebaabeeccadddbccaeeddddbbeecaecbdccbeadacdbaedadaeddcaeaedaeaeacdadcedcdabddacededcbeebaabeadaabbeeddeeababbaacabdbeadeadeedceadcbecddacaeaceeebcecadaebdccaeacdedbbecacabddeeeadecddbacddbebeedacdeddacbbbcebbaecaecadccccdebccdcdcbacbcccbdabdadaababdacebddcceddbdecdacbadaaaeaeddeeabcebbccbdbbebedabbdbdcaedebaaecddbacbaaaccdadeddebebdbabeceeaadadaabceecdceadebecacacbaebaebebceccdeebcabedaabcabccabedbbebabaababedeebaabcdaacdcccebcaecceedeebeabeadacbbcdcbbcdbddbcdadbcaceddedabeebbeedaabbccacdacedabbdeacbeebceadcaeacdbceaceaaaeebcbbebdeddbbbeddcbcabaacaadebcdceadcadaececbbbeecddcbbdbcdecaaacedbcbdbeabbbbdeceaebdcddbbebdbebbbcabccaecacbbcaeadcdbcdaadccaceddedaabaabcacacaeddcceadbabdbcbdaeeacabacdcdcbccaedeceacaaadabeabbceeedaabdcdbddebddadbadbbddedecabbbbdabecedbbcceacaacbebdeddbedbeabdbbadbeacbeabceaddadeeececeaaacecaaacbdcdcbcddcecadbbeceadebadececacaeaeccbdbddeadabcebaeeaeeabeccebdaeadaeedddaeaaedabcdbcaaeacabdcaaccbadbeabdbcbdcbeddabdacebcecccddcacbbccedbecbdcdbdeeaaaeeecacbacabbcccccaecacdececaeceacacecbdcbceaedcbdabeecbabbeaadbaaaeceabbaacbbbbddaeeadabaadcadcbeeabececbededccbddcbcdeacaacbabaaaebdcbcecdcbdbbdcbaeeebdaaecccbbbabdaddbdceaaacabdaccaeaccecdadcebdbceddbcbbcebdbbaccedbbeeceaeadbbbaabdaeaeccdcebceebdddaaaaeaeabdbebeddbadbbbddadadadcbccebecccdeeeaaeddaacadbbbbccecbbcdcebeeeaecbedbeecabcdceaeeadaeccecbbcddbacbdbcbbdceeedccbdeadbeeaacaeccaebdabbecabaeecdbdbcacdbcbadcbeeedbcebaacdaccbbcecdbdebabacddddaeadcdddcbedabbcbedcadbabeedeecbadbacbddaccadebcbaadbcbdabedccbbecbbbccabdaeacdaddcdceebedccdaddcdeccacecacbcedaccdbdbcbeeedaabbeddcaaacaceabcecacebcdacecaceabbccccdcbacaeaeebbbbecbecdbcabecccdebacbadcbaeecdcaaabaaecaacdaaccdbaaacdadecadaeecccdacebdddecbaacedbedbcbbbeabdabcdcedadcaebbebaeeebddbebcddabbbdedbeadeaebaccabecdbcbeaaabadbeccccaddbacddacbaeaecccadedaddedbebcecebcdadaccdcbedacbcbdcddceedaebedecdedeaecbeadbccedcbbaedccbeaeebaababeccdbdbdbcddcaaebcbcbaabbdaaabcccbbaeeaabbccddeebadebbdcebdaadbabdcacdeeeacedeaccabcbbeaabcdaecbdacecdabdbabaaadcadcdacaeeccabcaebcdcceaeccbaddecbceccddbbdbbbbadbdadeeaedcdbeddbbbddcebeaadbedebdddbcbddaacaceccbacbacebaebbbcbacddbaacedeeedbcadaaebdababbddabbcbddaccdcddbbdeabaacaeaaddacedaaceeedcedcecceaadbdebdcbeeaabaeca".to_string();
let res = "ddbcddbabee".to_string();
assert_eq!(Solution::longest_dup_substring(s), res);
}