let rec take_while f xs = 
  match xs with
  | [] -> []
  | x :: rest -> if f x
                 then x :: take_while f rest
                 else []
 
let rec drop_while f xs = 
  match xs with
  | [] -> []
  | x :: rest -> if f x
                 then drop_while f rest
                 else xs
 
let span f xs = (take_while f xs, drop_while f xs)
 
let string_to_char_list s =
  let rec string_to_char_list_impl i l =
    if i < 0 
    then l 
    else string_to_char_list_impl (i - 1) (s.[i] :: l) in
  string_to_char_list_impl (String.length s - 1) []
 
let char_list_to_string cs = 
  String.concat "" (List.map (fun x -> String.make 1 x) cs)
 
let next_permutation word = 
  let rec next_permutation_impl char_list =
    match char_list with
    | x0 :: rest0 -> 
       (match next_permutation_impl rest0 with
        | (true, rest1) -> (true, x0 :: rest1)
        | (false, rest1) -> 
           (match rest1 with
            | [] -> (false, x0 :: rest1)
            | x1 :: _ ->
               if x0 < x1
               then 
                 let (left, right) = span (fun x -> x > x0) rest1 in
                 let chunk = 
                   (match (List.rev left, List.rev right) with
                    | ([], _) -> raise (Failure "Chpoke")
                    | (l :: revLeft, revRight) -> List.concat [[l]; revRight; [x0]; revLeft])
                 in (match chunk with
                     | (x2 :: rest2) -> (true, x2 :: rest2)
                     | [] -> raise (Failure "Chpoke"))
               else (false, x0 :: rest1)))
    | [] -> (false, [])
  in
  let char_list = string_to_char_list word in
  match next_permutation_impl char_list with
  | (true, result) -> Some (char_list_to_string result)
  | _ -> None
 

CmxldCByZWMgdGFrZV93aGlsZSBmIHhzID0gCiAgbWF0Y2ggeHMgd2l0aAogIHwgW10gLT4gW10KICB8IHggOjogcmVzdCAtPiBpZiBmIHgKICAgICAgICAgICAgICAgICB0aGVuIHggOjogdGFrZV93aGlsZSBmIHJlc3QKICAgICAgICAgICAgICAgICBlbHNlIFtdCgpsZXQgcmVjIGRyb3Bfd2hpbGUgZiB4cyA9IAogIG1hdGNoIHhzIHdpdGgKICB8IFtdIC0+IFtdCiAgfCB4IDo6IHJlc3QgLT4gaWYgZiB4CiAgICAgICAgICAgICAgICAgdGhlbiBkcm9wX3doaWxlIGYgcmVzdAogICAgICAgICAgICAgICAgIGVsc2UgeHMKCmxldCBzcGFuIGYgeHMgPSAodGFrZV93aGlsZSBmIHhzLCBkcm9wX3doaWxlIGYgeHMpCgpsZXQgc3RyaW5nX3RvX2NoYXJfbGlzdCBzID0KICBsZXQgcmVjIHN0cmluZ190b19jaGFyX2xpc3RfaW1wbCBpIGwgPQogICAgaWYgaSA8IDAgCiAgICB0aGVuIGwgCiAgICBlbHNlIHN0cmluZ190b19jaGFyX2xpc3RfaW1wbCAoaSAtIDEpIChzLltpXSA6OiBsKSBpbgogIHN0cmluZ190b19jaGFyX2xpc3RfaW1wbCAoU3RyaW5nLmxlbmd0aCBzIC0gMSkgW10KCmxldCBjaGFyX2xpc3RfdG9fc3RyaW5nIGNzID0gCiAgU3RyaW5nLmNvbmNhdCAiIiAoTGlzdC5tYXAgKGZ1biB4IC0+IFN0cmluZy5tYWtlIDEgeCkgY3MpCgpsZXQgbmV4dF9wZXJtdXRhdGlvbiB3b3JkID0gCiAgbGV0IHJlYyBuZXh0X3Blcm11dGF0aW9uX2ltcGwgY2hhcl9saXN0ID0KICAgIG1hdGNoIGNoYXJfbGlzdCB3aXRoCiAgICB8IHgwIDo6IHJlc3QwIC0+IAogICAgICAgKG1hdGNoIG5leHRfcGVybXV0YXRpb25faW1wbCByZXN0MCB3aXRoCiAgICAgICAgfCAodHJ1ZSwgcmVzdDEpIC0+ICh0cnVlLCB4MCA6OiByZXN0MSkKICAgICAgICB8IChmYWxzZSwgcmVzdDEpIC0+IAogICAgICAgICAgIChtYXRjaCByZXN0MSB3aXRoCiAgICAgICAgICAgIHwgW10gLT4gKGZhbHNlLCB4MCA6OiByZXN0MSkKICAgICAgICAgICAgfCB4MSA6OiBfIC0+CiAgICAgICAgICAgICAgIGlmIHgwIDwgeDEKICAgICAgICAgICAgICAgdGhlbiAKICAgICAgICAgICAgICAgICBsZXQgKGxlZnQsIHJpZ2h0KSA9IHNwYW4gKGZ1biB4IC0+IHggPiB4MCkgcmVzdDEgaW4KICAgICAgICAgICAgICAgICBsZXQgY2h1bmsgPSAKICAgICAgICAgICAgICAgICAgIChtYXRjaCAoTGlzdC5yZXYgbGVmdCwgTGlzdC5yZXYgcmlnaHQpIHdpdGgKICAgICAgICAgICAgICAgICAgICB8IChbXSwgXykgLT4gcmFpc2UgKEZhaWx1cmUgIkNocG9rZSIpCiAgICAgICAgICAgICAgICAgICAgfCAobCA6OiByZXZMZWZ0LCByZXZSaWdodCkgLT4gTGlzdC5jb25jYXQgW1tsXTsgcmV2UmlnaHQ7IFt4MF07IHJldkxlZnRdKQogICAgICAgICAgICAgICAgIGluIChtYXRjaCBjaHVuayB3aXRoCiAgICAgICAgICAgICAgICAgICAgIHwgKHgyIDo6IHJlc3QyKSAtPiAodHJ1ZSwgeDIgOjogcmVzdDIpCiAgICAgICAgICAgICAgICAgICAgIHwgW10gLT4gcmFpc2UgKEZhaWx1cmUgIkNocG9rZSIpKQogICAgICAgICAgICAgICBlbHNlIChmYWxzZSwgeDAgOjogcmVzdDEpKSkKICAgIHwgW10gLT4gKGZhbHNlLCBbXSkKICBpbgogIGxldCBjaGFyX2xpc3QgPSBzdHJpbmdfdG9fY2hhcl9saXN0IHdvcmQgaW4KICBtYXRjaCBuZXh0X3Blcm11dGF0aW9uX2ltcGwgY2hhcl9saXN0IHdpdGgKICB8ICh0cnVlLCByZXN1bHQpIC0+IFNvbWUgKGNoYXJfbGlzdF90b19zdHJpbmcgcmVzdWx0KQogIHwgXyAtPiBOb25lCg==