string_width

import gleam/bit_array
import gleam/int
import gleam/list
import gleam/regex
import gleam/string

// sources:
// UAX #11 east asian width: https://www.unicode.org/reports/tr11/
// Grapheme Clusters in Terminals: https://mitchellh.com/writing/grapheme-clusters-in-terminals
// get-east-asian-width: https://github.com/sindresorhus/get-east-asian-width
// string-width: https://github.com/sindresorhus/string-width
// ansi-regex: https://github.com/chalk/ansi-regex
// musl-libc wcwidth: https://git.musl-libc.org/cgit/musl/tree/src/ctype/wcwidth.c

pub type Option {
  /// Many terminal emulators do not handle grapheme clusters well and will
  /// instead show their decomposition. To make sure a given string always fits
  /// even on those terminals, the functions in this package will copy this
  /// behaviour as well.
  /// 
  /// If you pass this option, the returned numbers will more accurately represent
  /// the width of a string on a website or in an editor, and will match the
  /// behaviour of the Javascript [string-width](https://www.npmjs.com/package/string-width) package.
  /// 
  /// See also [Grapheme Clusters and Terminal Emulators](https://mitchellh.com/writing/grapheme-clusters-in-terminals)
  /// for a better explanation on how terminals behave.
  HandleGraphemeClusters
  /// Do not ignore ansi escape sequences.
  CountAnsiEscapeCodes
  /// Some characters are marked by Unicode as "ambiguous", meaning they may
  /// occupy 1 or 2 cells, depending on the context, current language, selected
  /// font, surrounding text, and more.
  ///
  /// Unicode recommends treating these characters as narrow by default,
  /// but you can change this behaviour using this option.
  AmbiguousAsWide
}

type Options {
  Options(
    count_ansi_escape_codes: Bool,
    ambiguous_as_wide: Bool,
    handle_grapheme_clusters: Bool,
  )
}

fn parse_options(options: List(Option)) -> Options {
  let defaults = Options(False, False, False)
  use record, option <- list.fold(options, defaults)
  case option {
    CountAnsiEscapeCodes -> Options(..record, count_ansi_escape_codes: True)
    AmbiguousAsWide -> Options(..record, ambiguous_as_wide: True)
    HandleGraphemeClusters -> Options(..record, handle_grapheme_clusters: True)
  }
}

/// Get the width of a line, when printed using a monospace font.
/// 
/// Line breaks are ignored. If the given string contains newlines,
/// the result is undefined.
/// 
/// ### Examples
/// 
/// ```gleam
/// line("äöüè", [])
/// // --> 4
/// 
/// line("안녕하세요", [])
/// // --> 10
///
/// line("👩‍👩‍👦‍👦", [])
/// // --> 8
/// 
/// line("👩‍👩‍👦‍👦", [HandleGraphemeClusters])
/// // --> 2
/// 
/// line("\u{1B}[31mhello\u{1B}[39m", [])
/// // --> 5
/// ```
pub fn line(str: String, options: List(Option)) -> Int {
  let options = parse_options(options)
  let str = case options.count_ansi_escape_codes {
    True -> str
    False -> strip_ansi(str)
  }
  do_line(options, str)
}

fn do_line(options: Options, str: String) -> Int {
  case options.handle_grapheme_clusters {
    True -> graphemes_width(options, str, 0)
    False -> {
      use sum, cp <- list.fold(string.to_utf_codepoints(str), 0)
      sum + wcwidth(options, string.utf_codepoint_to_int(cp))
    }
  }
}

/// The required number of rows and columns to display the given text.
/// 
/// The number of rows is equal to the number of lines, while the number of
/// columns represents the maximum line width.
/// 
/// ### Examples
/// 
/// ```gleam
/// dimensions("안녕하세요", [])
/// // --> #(1, 10)
/// 
/// dimensions("hello,\n안녕하세요", [])
/// // --> #(2, 10)
/// ```
pub fn dimensions(str: String, options: List(Option)) -> #(Int, Int) {
  let options = parse_options(options)
  let str = case options.count_ansi_escape_codes {
    True -> str
    False -> strip_ansi(str)
  }

  use #(rows, cols), line_str <- list.fold(string.split(str, on: "\n"), #(0, 0))
  #(rows + 1, int.max(cols, do_line(options, line_str)))
}

fn graphemes_width(options: Options, str: String, width: Int) {
  case string.pop_grapheme(str) {
    Ok(#(grapheme, str)) -> {
      let grapheme_width = do_grapheme_cluster(options, grapheme)
      graphemes_width(options, str, width + grapheme_width)
    }
    Error(Nil) -> width
  }
}

/// Estimate the required width for a single grapheme cluster.
/// 
/// **Note:** that the exact width is context-dependent, so this value may not
/// exactly match what you might expect!
/// 
/// If you encounter a mismatch that is consistent across multiple terminal
/// emulators, please open an issue or ping me on Discord!
pub fn grapheme_cluster(grapheme: String, options: List(Option)) -> Int {
  do_grapheme_cluster(parse_options(options), grapheme)
}

fn do_grapheme_cluster(options: Options, grapheme: String) -> Int {
  use max, cp <- list.fold(string.to_utf_codepoints(grapheme), 0)
  case string.utf_codepoint_to_int(cp) {
    0xfe0f -> int.max(max, 2)
    cp -> int.max(max, wcwidth(options, cp))
  }
  // int.max(max, wcwidth(options, string.utf_codepoint_to_int(cp)))
}

/// Estimate the required width for a single unicode code point.
/// 
/// **Note:** that the exact width is context-dependent, so this value may not
/// exactly match what you might expect!
/// 
/// If you encounter a mismatch that is consistent across multiple terminal
/// emulators, please open an issue or ping me on Discord!
pub fn codepoint(chr: UtfCodepoint, options: List(Option)) -> Int {
  wcwidth(parse_options(options), string.utf_codepoint_to_int(chr))
}

/// 
pub fn int_codepoint(cp: Int, options: List(Option)) -> Int {
  wcwidth(parse_options(options), cp)
}

fn wcwidth(options: Options, cp: Int) -> Int {
  // see: https://git.musl-libc.org/cgit/musl/tree/src/ctype/wcwidth.c
  case is_ignorable(cp) {
    True -> 0
    False ->
      case is_ambiguous(cp) {
        True ->
          case options.ambiguous_as_wide {
            True -> 2
            False -> 1
          }
        False ->
          case is_wide(cp) {
            True -> 2
            False -> 1
          }
      }
  }
}

fn strip_ansi(str: String) -> String {
  // see: https://github.com/chalk/ansi-regex/blob/main/index.js
  let assert Ok(re) =
    regex.from_string(
      "[\u{1B}\u{9B}][[\\]()#;?]*(?:(?:(?:(?:;[-a-zA-Z\\d\\/#&.:=?%@~_]+)*|[a-zA-Z\\d]+(?:;[-a-zA-Z\\d\\/#&.:=?%@~_]*)*)?(?:\u{07}|\u{1B}\u{5C}|\u{9C}))|(?:(?:\\d{1,4}(?:;\\d{0,4})*)?[\\dA-PR-TZcf-nq-uy=><~]))",
    )
  regex.replace(re, str, "")
}

// the data for these functions is generated by the generate.gleam script.
// the general idea is heavily inspired by the tables used in musl libc.

fn is_ignorable(cp: Int) -> Bool {
  case cp <= 0x1ffff {
    True -> table_lookup(nonspacing, cp)
    False -> cp >= 0xe0000 && cp <= 0xe0fff
  }
}

fn is_ambiguous(cp: Int) -> Bool {
  case cp <= 0xffff {
    True -> table_lookup(ambiguous, cp)
    False -> {
      { cp >= 0xff100 && cp <= 0x1f10a }
      || { cp >= 0x1f110 && cp <= 0x1f12d }
      || { cp >= 0x1f130 && cp <= 0x1f169 }
      || { cp >= 0x1f170 && cp <= 0x1f18d }
      || { cp >= 0x1f18f && cp <= 0x1f190 }
      || { cp >= 0x1f19b && cp <= 0x1f1ac }
      || { cp >= 0xe0100 && cp <= 0xe01ef }
      || { cp >= 0xf0000 && cp <= 0xffffd }
    }
  }
}

fn is_wide(cp: Int) -> Bool {
  case cp <= 0x1ffff {
    True -> table_lookup(wide, cp)
    False -> {
      // NOTE: this assumes we checked ambiguous first!
      cp >= 0x20000 && cp <= 0x40000
    }
  }
}

fn table_lookup(table: BitArray, value: Int) -> Bool {
  let hi = int.bitwise_shift_right(value, 8)
  let md = int.bitwise_shift_right(int.bitwise_and(value, 0xff), 3)
  let lo = int.bitwise_and(value, 7)

  int.bitwise_shift_right(at(table, at(table, hi) * 32 + md), lo) % 2 != 0
}

fn at(bits: BitArray, at position: Int) -> Int {
  // NOTE: This bit array size option is in patterns is not supported for JavaScript compilation.
  // let bit_index = position * 8
  // case bits {
  //   <<_:size(bit_index), x:int, _:bits>> -> x
  //   _ -> panic
  // }

  case bit_array.slice(bits, at: position, take: 1) {
    Ok(<<x>>) -> x
    _ -> panic
  }
}

const nonspacing = <<
  16, 17, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 17, 33,
  17, 17, 17, 34, 35, 36, 37, 38, 39, 40, 17, 17, 41, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 42, 43, 17, 17, 44, 45, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 46, 17, 47, 48, 49, 50, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 51, 17, 17, 52, 53, 17, 54, 55, 56,
  17, 17, 17, 17, 17, 17, 57, 17, 17, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68,
  69, 70, 71, 17, 72, 73, 74, 75, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 76, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 77, 17, 17, 17, 17, 17, 17,
  17, 17, 78, 79, 17, 17, 17, 80, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 81, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 82, 17, 83, 84, 17, 17, 17, 17, 17, 17, 17, 85, 17, 17, 17, 17, 17,
  86, 79, 87, 17, 88, 89, 17, 17, 90, 91, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
  17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 255, 255, 255, 255, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 128, 255, 255, 255, 255, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 127, 255,
  255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 248, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 254, 255, 255,
  255, 255, 191, 182, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 23, 0, 0, 0, 0, 0, 248,
  255, 255, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 192, 159, 159, 61, 0, 0, 0,
  0, 2, 0, 0, 0, 255, 255, 255, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 192, 255, 1, 0,
  0, 0, 0, 0, 0, 248, 15, 32, 0, 0, 192, 251, 239, 62, 0, 0, 0, 0, 0, 14, 0, 0,
  0, 0, 0, 0, 128, 255, 0, 0, 0, 0, 0, 252, 255, 255, 251, 255, 255, 255, 7, 0,
  0, 0, 0, 0, 0, 20, 254, 33, 254, 0, 12, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 16, 30,
  32, 0, 0, 12, 0, 0, 64, 6, 0, 0, 0, 0, 0, 0, 16, 134, 57, 2, 0, 0, 0, 35, 0, 6,
  0, 0, 0, 0, 0, 0, 16, 190, 33, 0, 0, 12, 0, 0, 252, 2, 0, 0, 0, 0, 0, 0, 144,
  30, 32, 96, 0, 12, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 1, 32, 0, 0, 0, 0, 0, 0,
  17, 0, 0, 0, 0, 0, 0, 208, 193, 61, 96, 0, 12, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0,
  144, 64, 48, 0, 0, 12, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 24, 30, 32, 0, 0, 12, 0,
  0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 4, 92, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 242,
  7, 128, 127, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 242, 31, 0, 127, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 3, 0, 0, 160, 2, 0, 0, 0, 0, 0, 0, 254, 127, 223, 224, 255, 254,
  255, 255, 255, 31, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 224, 253, 102, 0, 0,
  0, 195, 1, 0, 30, 0, 100, 32, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 224, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 28, 0, 0, 0, 12, 0, 0, 0, 12, 0, 0, 0, 12,
  0, 0, 0, 0, 0, 0, 0, 224, 63, 64, 254, 15, 32, 0, 0, 0, 0, 0, 176, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 96, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 135, 1, 4, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 9, 0, 0, 0, 0, 0, 0, 64, 127, 229, 31, 248,
  159, 0, 0, 0, 0, 0, 0, 255, 191, 255, 127, 0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0,
  208, 23, 4, 0, 0, 0, 0, 248, 15, 0, 3, 0, 0, 0, 60, 59, 0, 0, 0, 0, 0, 0, 64,
  163, 3, 0, 0, 0, 0, 0, 0, 240, 207, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 247, 255, 253, 33, 16, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 0,
  248, 0, 0, 0, 124, 0, 0, 0, 0, 0, 0, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 255, 31, 226, 255, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 0, 0,
  0, 0, 0, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 240,
  63, 0, 0, 0, 192, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 68, 8, 0, 0, 96, 16, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 48, 0, 0, 0, 255, 255, 3,
  128, 0, 0, 0, 0, 192, 63, 0, 0, 128, 255, 3, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0,
  200, 51, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 126, 102, 0, 8, 16, 0, 0, 0,
  0, 0, 16, 0, 0, 0, 0, 0, 0, 157, 193, 2, 0, 0, 0, 0, 48, 64, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 33, 0,
  0, 0, 0, 0, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 254, 254, 0, 0, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 1, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 192, 7, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 110, 240, 0, 0, 0, 0, 0, 135, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 96, 0, 0, 0, 0, 0, 0, 0,
  240, 0, 0, 0, 0, 0, 0, 0, 0, 62, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 240, 0, 0, 0, 0, 0, 0, 0, 0, 192, 255, 1, 0, 0, 0, 0,
  0, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 255,
  127, 0, 0, 0, 0, 0, 25, 128, 3, 0, 0, 0, 0, 0, 120, 6, 4, 0, 0, 0, 0, 0, 0, 0,
  7, 0, 0, 0, 128, 239, 31, 0, 0, 0, 0, 0, 0, 0, 8, 0, 3, 0, 0, 0, 0, 0, 192,
  127, 0, 158, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 211, 64, 2, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 248, 7, 0, 0, 3, 0, 0, 0, 0, 0, 0,
  24, 1, 0, 0, 0, 192, 31, 31, 0, 0, 0, 0, 0, 0, 0, 0, 248, 1, 64, 5, 0, 6, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 255, 92, 0, 0, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 248,
  133, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 60, 176, 1, 0, 0, 48, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 248, 167,
  1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 191, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 160, 188, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 255, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 88, 8, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 240, 12, 1, 0, 0, 0, 254, 7, 0, 0, 0, 0,
  248, 121, 128, 0, 126, 14, 0, 0, 0, 0, 0, 252, 127, 3, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 127, 191, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252, 255,
  255, 252, 109, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 126, 180, 191, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 163, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  24, 0, 3, 0, 0, 0, 0, 0, 192, 7, 5, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 129, 255, 63, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 192, 255, 227, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 31, 0, 0, 0, 0, 0, 0, 0, 127, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 0, 0, 0, 0, 0,
  0, 0, 128, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 96, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255,
  255, 255, 255, 255, 63, 255, 255, 127, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 3, 248,
  255, 231, 15, 0, 0, 0, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  255, 255, 255, 255, 255, 255, 127, 248, 255, 255, 255, 255, 255, 31, 32, 0, 16,
  0, 0, 248, 254, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 127, 255, 255, 249, 219, 7,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 64, 0, 0, 0, 0,
  0, 0, 0, 240, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 240, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 192, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 127, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 240, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0,
>>

const ambiguous = <<
  8, 9, 10, 11, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 15, 16, 17, 18, 19, 20, 21,
  13, 13, 13, 22, 13, 13, 13, 13, 13, 13, 23, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
  13, 13, 13, 13, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
  24, 24, 24, 24, 24, 24, 24, 24, 24, 13, 13, 13, 13, 13, 25, 26, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 146, 101, 223, 247, 64, 0, 129,
  193, 67, 55, 141, 87, 2, 0, 10, 8, 192, 8, 14, 129, 23, 47, 12, 0, 192, 8, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 64, 85, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 144, 46, 1, 175, 0, 0, 0, 0,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0,
  0, 254, 255, 251, 3, 254, 255, 251, 3, 0, 0, 0, 0, 0, 0, 2, 0, 255, 255, 255,
  255, 255, 255, 255, 255, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 121, 51, 247, 0, 45, 72, 0, 0, 0, 0, 0, 0,
  16, 128, 30, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 2, 72, 0, 70, 8,
  0, 0, 0, 0, 24, 120, 255, 15, 255, 3, 0, 2, 255, 3, 0, 0, 0, 3, 0, 0, 20, 0,
  128, 0, 0, 0, 141, 137, 34, 228, 169, 95, 240, 48, 0, 17, 4, 0, 243, 204, 0, 0,
  204, 0, 32, 2, 32, 0, 0, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 251, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 15, 255, 255, 255, 255, 15, 0, 255, 255, 60, 0, 251, 3, 204, 48,
  195, 201, 3, 0, 60, 128, 0, 0, 96, 194, 0, 80, 0, 0, 0, 0, 5, 0, 0, 0, 187,
  183, 0, 0, 0, 0, 0, 192, 0, 0, 0, 128, 192, 191, 239, 255, 11, 251, 211, 219,
  0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 192, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 192, 3, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 32,
>>

const wide = <<
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 18, 16, 19, 20, 21,
  16, 16, 16, 22, 16, 16, 23, 24, 25, 26, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  28, 28, 28, 28, 29, 16, 16, 16, 16, 30, 16, 16, 28, 28, 28, 28, 28, 28, 28, 28,
  28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 31, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 28, 28, 16, 16, 16, 32, 33, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 34, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
  28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 35, 28, 28, 28, 28, 36, 37, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 38, 28, 39, 40, 16, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 41, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 42, 43, 44, 45,
  46, 47, 48, 49, 16, 50, 51, 16, 16, 16, 16, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 96, 0, 0, 48, 0,
  0, 0, 255, 0, 0, 255, 15, 0, 0, 0, 0, 128, 0, 252, 8, 0, 2, 12, 0, 96, 48, 64,
  16, 0, 0, 4, 44, 36, 32, 12, 0, 0, 0, 1, 0, 0, 0, 80, 184, 0, 0, 0, 0, 0, 0, 0,
  224, 0, 0, 0, 1, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24, 0, 0, 0, 0, 0, 0,
  33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 251, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 15, 0, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 63, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 127, 254,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 127, 254, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 224, 255, 255, 255, 255, 255, 254, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 127, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 63, 128, 255, 255, 255, 255, 255, 127, 255, 255, 255, 255, 255,
  0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 31, 255, 255, 255, 255, 255, 255, 127,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 31, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 15, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 3, 0, 0, 255, 255, 255, 255, 247, 255, 127,
  15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 254, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 127, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 31, 0, 3, 0, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 0, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 63, 0, 0, 0, 0, 128, 255, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 239, 111, 255,
  255, 255, 255, 7, 0, 4, 0, 0, 0, 39, 0, 240, 0, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 15, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 127, 0, 255, 255, 127, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 64, 254, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 255, 255,
  255, 255, 255, 15, 255, 1, 3, 0, 63, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 255, 255, 255, 255, 1, 224, 191, 255, 255, 255, 255, 255, 255,
  255, 255, 223, 255, 255, 15, 0, 255, 255, 255, 255, 255, 135, 15, 0, 255, 255,
  17, 255, 255, 255, 255, 255, 255, 255, 255, 127, 253, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 159, 255, 255, 255, 255, 255, 255, 255, 63, 0, 120, 255, 255, 255, 0, 0,
  4, 0, 0, 96, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 248, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255,
  255, 63, 16, 231, 240, 0, 24, 240, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 15, 1, 0, 0, 240, 255, 255,
  255, 255, 255, 247, 191, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 255, 31, 255, 131, 255, 255, 255, 255, 255, 255, 127,
  192, 255, 159, 255, 3, 255, 1,
>>