-- Lexicographical trie
-- (c) Vadim Vinnik, 2011
 
import Char
 
data TrieNode = TrieNode Char Bool Trie
    deriving Show
 
type Trie = [TrieNode]
 
--
trieInsert :: Trie -> String -> Trie
 
trieInsert [] (char:[]) = [TrieNode char True []]
 
trieInsert [] (char:wordRest) = [TrieNode char False (trieInsert [] wordRest)]
 
trieInsert (node@(TrieNode char1 bFinal trieChildren):trieSiblings) word@(char2:wordRest)
      | char1 == char2 && wordRest == [] = (TrieNode char1 True trieChildren):trieSiblings
      | char1 == char2                   = (TrieNode char1 bFinal (trieInsert trieChildren wordRest)):trieSiblings
      | char1 >  char2                   = (trieInsert [] word) ++ (node : trieSiblings)
      | otherwise                        = node : (trieInsert trieSiblings word)
 
--
trieExists :: Trie -> String -> Bool
 
trieExists [] _ = False
 
trieExists ((TrieNode char1 bFinal trieChildren):trieSiblings) word@(char2:wordRest)
      | char1 == char2 && wordRest == [] = bFinal
      | char1 == char2                   = trieExists trieChildren wordRest
      | otherwise                        = trieExists trieSiblings word
 
--
trieListAll :: Trie -> [String]
 
trieListAll [] = []
 
trieListAll ((TrieNode char bFinal trieChildren):trieSiblings) =
    (if bFinal then [[char]] else []) ++
    (map (char:) (trieListAll trieChildren)) ++
    (trieListAll trieSiblings)
 
--
trieEndings :: Trie -> String -> [String]
 
trieEndings [] _ = []
 
trieEndings trie [] = trieListAll trie
 
trieEndings (node@(TrieNode char1 bFinal trieChildren):trieSiblings) word@(char2:wordRest)
    | char1 == char2 = (if bFinal then [""] else []) ++ trieEndings trieChildren wordRest
    | otherwise      = trieEndings trieSiblings word
 
--
trieCompletions :: Trie -> String -> [String]
 
trieCompletions trie word = map (word++) (trieEndings trie word)
 
--
trieFromText :: String -> Trie
 
trieFromText string = foldl trieInsert [] (words string)
 
 
--
main = do s <- getLine
          let t = map (\c -> (if isAlpha c then c else ' ')) s
          let r = trieFromText t
          print (trieEndings r "wh")
          print (trieCompletions r "wh")
          print (trieEndings r "th")
          print (trieCompletions r "th")
 

LS0gTGV4aWNvZ3JhcGhpY2FsIHRyaWUKLS0gKGMpIFZhZGltIFZpbm5paywgMjAxMQoKaW1wb3J0IENoYXIKCmRhdGEgVHJpZU5vZGUgPSBUcmllTm9kZSBDaGFyIEJvb2wgVHJpZQogICAgZGVyaXZpbmcgU2hvdwoKdHlwZSBUcmllID0gW1RyaWVOb2RlXQoKLS0KdHJpZUluc2VydCA6OiBUcmllIC0+IFN0cmluZyAtPiBUcmllCgp0cmllSW5zZXJ0IFtdIChjaGFyOltdKSA9IFtUcmllTm9kZSBjaGFyIFRydWUgW11dCgp0cmllSW5zZXJ0IFtdIChjaGFyOndvcmRSZXN0KSA9IFtUcmllTm9kZSBjaGFyIEZhbHNlICh0cmllSW5zZXJ0IFtdIHdvcmRSZXN0KV0KCnRyaWVJbnNlcnQgKG5vZGVAKFRyaWVOb2RlIGNoYXIxIGJGaW5hbCB0cmllQ2hpbGRyZW4pOnRyaWVTaWJsaW5ncykgd29yZEAoY2hhcjI6d29yZFJlc3QpCiAgICAgIHwgY2hhcjEgPT0gY2hhcjIgJiYgd29yZFJlc3QgPT0gW10gPSAoVHJpZU5vZGUgY2hhcjEgVHJ1ZSB0cmllQ2hpbGRyZW4pOnRyaWVTaWJsaW5ncwogICAgICB8IGNoYXIxID09IGNoYXIyICAgICAgICAgICAgICAgICAgID0gKFRyaWVOb2RlIGNoYXIxIGJGaW5hbCAodHJpZUluc2VydCB0cmllQ2hpbGRyZW4gd29yZFJlc3QpKTp0cmllU2libGluZ3MKICAgICAgfCBjaGFyMSA+ICBjaGFyMiAgICAgICAgICAgICAgICAgICA9ICh0cmllSW5zZXJ0IFtdIHdvcmQpICsrIChub2RlIDogdHJpZVNpYmxpbmdzKQogICAgICB8IG90aGVyd2lzZSAgICAgICAgICAgICAgICAgICAgICAgID0gbm9kZSA6ICh0cmllSW5zZXJ0IHRyaWVTaWJsaW5ncyB3b3JkKQoKLS0KdHJpZUV4aXN0cyA6OiBUcmllIC0+IFN0cmluZyAtPiBCb29sCgp0cmllRXhpc3RzIFtdIF8gPSBGYWxzZQoKdHJpZUV4aXN0cyAoKFRyaWVOb2RlIGNoYXIxIGJGaW5hbCB0cmllQ2hpbGRyZW4pOnRyaWVTaWJsaW5ncykgd29yZEAoY2hhcjI6d29yZFJlc3QpCiAgICAgIHwgY2hhcjEgPT0gY2hhcjIgJiYgd29yZFJlc3QgPT0gW10gPSBiRmluYWwKICAgICAgfCBjaGFyMSA9PSBjaGFyMiAgICAgICAgICAgICAgICAgICA9IHRyaWVFeGlzdHMgdHJpZUNoaWxkcmVuIHdvcmRSZXN0CiAgICAgIHwgb3RoZXJ3aXNlICAgICAgICAgICAgICAgICAgICAgICAgPSB0cmllRXhpc3RzIHRyaWVTaWJsaW5ncyB3b3JkCgotLQp0cmllTGlzdEFsbCA6OiBUcmllIC0+IFtTdHJpbmddCgp0cmllTGlzdEFsbCBbXSA9IFtdCgp0cmllTGlzdEFsbCAoKFRyaWVOb2RlIGNoYXIgYkZpbmFsIHRyaWVDaGlsZHJlbik6dHJpZVNpYmxpbmdzKSA9CiAgICAoaWYgYkZpbmFsIHRoZW4gW1tjaGFyXV0gZWxzZSBbXSkgKysKICAgIChtYXAgKGNoYXI6KSAodHJpZUxpc3RBbGwgdHJpZUNoaWxkcmVuKSkgKysKICAgICh0cmllTGlzdEFsbCB0cmllU2libGluZ3MpCgotLQp0cmllRW5kaW5ncyA6OiBUcmllIC0+IFN0cmluZyAtPiBbU3RyaW5nXQoKdHJpZUVuZGluZ3MgW10gXyA9IFtdCgp0cmllRW5kaW5ncyB0cmllIFtdID0gdHJpZUxpc3RBbGwgdHJpZQoKdHJpZUVuZGluZ3MgKG5vZGVAKFRyaWVOb2RlIGNoYXIxIGJGaW5hbCB0cmllQ2hpbGRyZW4pOnRyaWVTaWJsaW5ncykgd29yZEAoY2hhcjI6d29yZFJlc3QpCiAgICB8IGNoYXIxID09IGNoYXIyID0gKGlmIGJGaW5hbCB0aGVuIFsiIl0gZWxzZSBbXSkgKysgdHJpZUVuZGluZ3MgdHJpZUNoaWxkcmVuIHdvcmRSZXN0CiAgICB8IG90aGVyd2lzZSAgICAgID0gdHJpZUVuZGluZ3MgdHJpZVNpYmxpbmdzIHdvcmQKCi0tCnRyaWVDb21wbGV0aW9ucyA6OiBUcmllIC0+IFN0cmluZyAtPiBbU3RyaW5nXQoKdHJpZUNvbXBsZXRpb25zIHRyaWUgd29yZCA9IG1hcCAod29yZCsrKSAodHJpZUVuZGluZ3MgdHJpZSB3b3JkKQoKLS0KdHJpZUZyb21UZXh0IDo6IFN0cmluZyAtPiBUcmllCgp0cmllRnJvbVRleHQgc3RyaW5nID0gZm9sZGwgdHJpZUluc2VydCBbXSAod29yZHMgc3RyaW5nKQoKCi0tCm1haW4gPSBkbyBzIDwtIGdldExpbmUKICAgICAgICAgIGxldCB0ID0gbWFwIChcYyAtPiAoaWYgaXNBbHBoYSBjIHRoZW4gYyBlbHNlICcgJykpIHMKICAgICAgICAgIGxldCByID0gdHJpZUZyb21UZXh0IHQKICAgICAgICAgIHByaW50ICh0cmllRW5kaW5ncyByICJ3aCIpCiAgICAgICAgICBwcmludCAodHJpZUNvbXBsZXRpb25zIHIgIndoIikKICAgICAgICAgIHByaW50ICh0cmllRW5kaW5ncyByICJ0aCIpCiAgICAgICAgICBwcmludCAodHJpZUNvbXBsZXRpb25zIHIgInRoIikK

V2FyIGFuZCBQZWFjZSBpcyBnZW5lcmFsbHkgdGhvdWdodCB0byBiZSBvbmUgb2YgdGhlIGdyZWF0ZXN0IG5vdmVscyBldmVyIHdyaXR0ZW4sIHJlbWFya2FibGUgZm9yIGl0cyBkcmFtYXRpYyBicmVhZHRoIGFuZCB1bml0eS4gSXRzIHZhc3QgY2FudmFzIGluY2x1ZGVzIDU4MCBjaGFyYWN0ZXJzLCBtYW55IGhpc3RvcmljYWwgd2l0aCBvdGhlcnMgZmljdGlvbmFsLiBUaGUgc3RvcnkgbW92ZXMgZnJvbSBmYW1pbHkgbGlmZSB0byB0aGUgaGVhZHF1YXJ0ZXJzIG9mIE5hcG9sZW9uLCBmcm9tIHRoZSBjb3VydCBvZiBBbGV4YW5kZXIgSSBvZiBSdXNzaWEgdG8gdGhlIGJhdHRsZWZpZWxkcyBvZiBBdXN0ZXJsaXR6IGFuZCBCb3JvZGluby4gVG9sc3RveSdzIG9yaWdpbmFsIGlkZWEgZm9yIHRoZSBub3ZlbCB3YXMgdG8gaW52ZXN0aWdhdGUgdGhlIGNhdXNlcyBvZiB0aGUgRGVjZW1icmlzdCByZXZvbHQsIHRvIHdoaWNoIGl0IHJlZmVycyBvbmx5IGluIHRoZSBsYXN0IGNoYXB0ZXJzLCBmcm9tIHdoaWNoIGNhbiBiZSBkZWR1Y2VkIHRoYXQgQW5kcmVpIEJvbGtvbnNraSdzIHNvbiB3aWxsIGJlY29tZSBvbmUgb2YgdGhlIERlY2VtYnJpc3RzLiBUaGUgbm92ZWwgZXhwbG9yZXMgVG9sc3RveSdzIHRoZW9yeSBvZiBoaXN0b3J5LCBhbmQgaW4gcGFydGljdWxhciB0aGUgaW5zaWduaWZpY2FuY2Ugb2YgaW5kaXZpZHVhbHMgc3VjaCBhcyBOYXBvbGVvbiBhbmQgQWxleGFuZGVyLiBTb21ld2hhdCBzdXJwcmlzaW5nbHksIFRvbHN0b3kgZGlkIG5vdCBjb25zaWRlciBXYXIgYW5kIFBlYWNlIHRvIGJlIGEgbm92ZWwgKG5vciBkaWQgaGUgY29uc2lkZXIgbWFueSBvZiB0aGUgZ3JlYXQgUnVzc2lhbiBmaWN0aW9ucyB3cml0dGVuIGF0IHRoYXQgdGltZSB0byBiZSBub3ZlbHMpLiBUaGlzIHZpZXcgYmVjb21lcyBsZXNzIHN1cnByaXNpbmcgaWYgb25lIGNvbnNpZGVycyB0aGF0IFRvbHN0b3kgd2FzIGEgbm92ZWxpc3Qgb2YgdGhlIHJlYWxpc3Qgc2Nob29sIHdobyBjb25zaWRlcmVkIHRoZSBub3ZlbCB0byBiZSBhIGZyYW1ld29yayBmb3IgdGhlIGV4YW1pbmF0aW9uIG9mIHNvY2lhbCBhbmQgcG9saXRpY2FsIGlzc3VlcyBpbiBuaW5ldGVlbnRoLWNlbnR1cnkgbGlmZS5bMTRdV2FyIGFuZCBQZWFjZSAod2hpY2ggaXMgdG8gVG9sc3RveSByZWFsbHkgYW4gZXBpYyBpbiBwcm9zZSkgdGhlcmVmb3JlIGRpZCBub3QgcXVhbGlmeS4gVG9sc3RveSB0aG91Z2h0IHRoYXQgQW5uYSBLYXJlbmluYSB3YXMgaGlzIGZpcnN0IHRydWUgbm92ZWw=

War and Peace is generally thought to be one of the greatest novels ever written, remarkable for its dramatic breadth and unity. Its vast canvas includes 580 characters, many historical with others fictional. The story moves from family life to the headquarters of Napoleon, from the court of Alexander I of Russia to the battlefields of Austerlitz and Borodino. Tolstoy's original idea for the novel was to investigate the causes of the Decembrist revolt, to which it refers only in the last chapters, from which can be deduced that Andrei Bolkonski's son will become one of the Decembrists. The novel explores Tolstoy's theory of history, and in particular the insignificance of individuals such as Napoleon and Alexander. Somewhat surprisingly, Tolstoy did not consider War and Peace to be a novel (nor did he consider many of the great Russian fictions written at that time to be novels). This view becomes less surprising if one considers that Tolstoy was a novelist of the realist school who considered the novel to be a framework for the examination of social and political issues in nineteenth-century life.[14]War and Peace (which is to Tolstoy really an epic in prose) therefore did not qualify. Tolstoy thought that Anna Karenina was his first true novel