{"version":3,"file":"splaytree.umd.cjs","names":[],"sources":["../src/node.ts","../src/index.ts"],"sourcesContent":["export default class Node<Key, Value> {\n  public key: Key;\n  public data: Value;\n  public left: Node<Key, Value> | null = null;\n  public right: Node<Key, Value> | null = null;\n  public next: Node<Key, Value> | null = null;\n\n  constructor(key: Key, data?: Value) {\n    this.key = key;\n    // insert(key) without data leaves it undefined, as before\n    this.data = data as Value;\n  }\n}\n","import Node from \"./node\";\n\nexport type Comparator<Key> = (a: Key, b: Key) => number;\nexport type Visitor<Key, Value> = (node: Node<Key, Value>) => undefined | boolean | void;\nexport type NodePrinter<Key, Value> = (node: Node<Key, Value>) => string;\n\n/* follows \"An implementation of top-down splaying\"\n * by D. Sleator <sleator@cs.cmu.edu> March 1992\n */\n\nfunction DEFAULT_COMPARE<Key>(a: Key, b: Key): number {\n  return a > b ? 1 : a < b ? -1 : 0;\n}\n\ntype TreeNodeList<Key, Value> = { head: Node<Key, Value> | null };\n\n/**\n * Simple top down splay, not requiring i to be in the tree t.\n */\nfunction splay<Key, Value>(\n  i: Key,\n  t: Node<Key, Value>,\n  comparator: Comparator<Key>,\n): Node<Key, Value> {\n  const N = new Node<Key, Value>(null as Key);\n  let l = N;\n  let r = N;\n\n  while (true) {\n    const cmp = comparator(i, t!.key);\n    //if (i < t.key) {\n    if (cmp < 0) {\n      if (t!.left === null) break;\n      //if (i < t.left.key) {\n      if (comparator(i, t.left.key) < 0) {\n        const y = t.left; /* rotate right */\n        t.left = y.right;\n        y.right = t;\n        t = y;\n        if (t.left === null) break;\n      }\n      r.left = t; /* link right */\n      r = t;\n      t = t.left;\n      //} else if (i > t.key) {\n    } else if (cmp > 0) {\n      if (t.right === null) break;\n      //if (i > t.right.key) {\n      if (comparator(i, t.right.key) > 0) {\n        const y = t.right; /* rotate left */\n        t.right = y.left;\n        y.left = t;\n        t = y;\n        if (t.right === null) break;\n      }\n      l.right = t; /* link left */\n      l = t;\n      t = t.right;\n    } else break;\n  }\n  /* assemble */\n  l.right = t.left;\n  r.left = t.right;\n  t.left = N.right;\n  t.right = N.left;\n  return t;\n}\n\nfunction insert<Key, Value>(\n  i: Key,\n  data: Value | undefined,\n  t: Node<Key, Value> | null,\n  comparator: Comparator<Key>,\n): Node<Key, Value> {\n  const node = new Node(i, data);\n\n  if (t === null) {\n    node.left = node.right = null;\n    return node;\n  }\n\n  t = splay(i, t, comparator);\n  const cmp = comparator(i, t.key);\n  if (cmp < 0) {\n    node.left = t.left;\n    node.right = t;\n    t.left = null;\n  } else {\n    node.right = t.right;\n    node.left = t;\n    t.right = null;\n  }\n  return node;\n}\n\nfunction split<Key, Value>(\n  key: Key,\n  v: Node<Key, Value> | null,\n  comparator: Comparator<Key>,\n): {\n  left: Node<Key, Value> | null;\n  right: Node<Key, Value> | null;\n} {\n  let left = null;\n  let right = null;\n  if (v) {\n    v = splay(key, v, comparator);\n\n    const cmp = comparator(v.key, key);\n    if (cmp === 0) {\n      left = v.left;\n      right = v.right;\n    } else if (cmp < 0) {\n      right = v.right;\n      v.right = null;\n      left = v;\n    } else {\n      left = v.left;\n      v.left = null;\n      right = v;\n    }\n  }\n  return { left, right };\n}\n\nfunction merge<Key, Value>(\n  left: Node<Key, Value> | null,\n  right: Node<Key, Value> | null,\n  comparator: Comparator<Key>,\n) {\n  if (right === null) return left;\n  if (left === null) return right;\n\n  right = splay(left.key, right, comparator);\n  right.left = left;\n  return right;\n}\n\ntype StringCollector = (s: string) => void;\n\n/**\n * Prints level of the tree\n */\nfunction printRow<Key, Value>(\n  root: Node<Key, Value> | null,\n  prefix: string,\n  isTail: boolean,\n  out: StringCollector,\n  printNode: NodePrinter<Key, Value>,\n) {\n  if (root) {\n    out(`${prefix}${isTail ? \"└── \" : \"├── \"}${printNode(root)}\\n`);\n    const indent = prefix + (isTail ? \"    \" : \"│   \");\n    if (root.left) printRow(root.left, indent, false, out, printNode);\n    if (root.right) printRow(root.right, indent, true, out, printNode);\n  }\n}\n\nexport default class Tree<Key = number, Value = unknown> {\n  private _comparator: Comparator<Key>;\n  private _root: Node<Key, Value> | null = null;\n  private _size: number = 0;\n\n  constructor(comparator: Comparator<Key> = DEFAULT_COMPARE) {\n    this._comparator = comparator;\n  }\n\n  /**\n   * Inserts a key, allows duplicates\n   */\n  public insert(key: Key, data?: Value): Node<Key, Value> {\n    this._size++;\n    return (this._root = insert(key, data, this._root, this._comparator));\n  }\n\n  /**\n   * Adds a key, if it is not present in the tree\n   */\n  public add(key: Key, data?: Value): Node<Key, Value> {\n    const node = new Node(key, data);\n\n    if (this._root === null) {\n      node.left = node.right = null;\n      this._size++;\n      this._root = node;\n    }\n\n    const comparator = this._comparator;\n    const t = splay(key, this._root, comparator);\n    const cmp = comparator(key, t.key);\n    if (cmp === 0) this._root = t;\n    else {\n      if (cmp < 0) {\n        node.left = t.left;\n        node.right = t;\n        t.left = null;\n      } else {\n        node.right = t.right;\n        node.left = t;\n        t.right = null;\n      }\n      this._size++;\n      this._root = node;\n    }\n\n    return this._root;\n  }\n\n  /**\n   * @param  {Key} key\n   * @return {Node|null}\n   */\n  public remove(key: Key): void {\n    this._root = this._remove(key, this._root, this._comparator);\n  }\n\n  /**\n   * Deletes i from the tree if it's there\n   */\n  private _remove(\n    i: Key,\n    t: Node<Key, Value> | null,\n    comparator: Comparator<Key>,\n  ): Node<Key, Value> | null {\n    let x;\n    if (t === null) return null;\n    t = splay(i, t, comparator);\n    const cmp = comparator(i, t.key);\n    if (cmp === 0) {\n      /* found it */\n      if (t.left === null) {\n        x = t.right!;\n      } else {\n        x = splay(i, t.left, comparator);\n        x.right = t.right;\n      }\n      this._size--;\n      return x;\n    }\n    return t; /* It wasn't there */\n  }\n\n  /**\n   * Removes and returns the node with smallest key\n   */\n  public pop(): { key: Key; data: Value } | null {\n    let node = this._root;\n    if (node) {\n      while (node.left) node = node.left;\n      this._root = splay(node.key, this._root!, this._comparator);\n      this._root = this._remove(node.key, this._root, this._comparator);\n      return { key: node.key, data: node.data };\n    }\n    return null;\n  }\n\n  /**\n   * Find without splaying\n   */\n  public findStatic(key: Key): Node<Key, Value> | null {\n    let current = this._root;\n    const compare = this._comparator;\n    while (current) {\n      const cmp = compare(key, current.key);\n      if (cmp === 0) return current;\n      else if (cmp < 0) current = current.left;\n      else current = current.right;\n    }\n    return null;\n  }\n\n  public find(key: Key): Node<Key, Value> | null {\n    if (this._root) {\n      this._root = splay(key, this._root, this._comparator);\n      if (this._comparator(key, this._root.key) !== 0) return null;\n    }\n    return this._root;\n  }\n\n  public contains(key: Key): boolean {\n    let current = this._root;\n    const compare = this._comparator;\n    while (current) {\n      const cmp = compare(key, current.key);\n      if (cmp === 0) return true;\n      else if (cmp < 0) current = current.left;\n      else current = current.right;\n    }\n    return false;\n  }\n\n  public forEach(visitor: Visitor<Key, Value>, ctx?: unknown): Tree<Key, Value> {\n    let current = this._root;\n    const Q = []; /* Initialize stack s */\n    let done = false;\n\n    while (!done) {\n      if (current !== null) {\n        Q.push(current);\n        current = current.left;\n      } else {\n        if (Q.length !== 0) {\n          current = Q.pop()!;\n          visitor.call(ctx, current);\n\n          current = current.right;\n        } else done = true;\n      }\n    }\n    return this;\n  }\n\n  /**\n   * Walk key range from `low` to `high`. Stops if `fn` returns a value.\n   */\n  public range(low: Key, high: Key, fn: Visitor<Key, Value>, ctx?: unknown): Tree<Key, Value> {\n    const Q = [];\n    const compare = this._comparator;\n    let node = this._root;\n    let cmp;\n\n    while (Q.length !== 0 || node) {\n      if (node) {\n        Q.push(node);\n        node = node.left;\n      } else {\n        node = Q.pop()!;\n        cmp = compare(node.key, high);\n        if (cmp > 0) {\n          break;\n        } else if (compare(node.key, low) >= 0) {\n          if (fn.call(ctx, node)) return this; // stop if smth is returned\n        }\n        node = node.right;\n      }\n    }\n    return this;\n  }\n\n  /**\n   * Returns array of keys\n   */\n  public keys(): Key[] {\n    const keys: Key[] = [];\n    this.forEach(({ key }) => {\n      keys.push(key);\n    });\n    return keys;\n  }\n\n  /**\n   * Returns array of all the data in the nodes\n   */\n  public values(): Value[] {\n    const values: Value[] = [];\n    this.forEach(({ data }) => {\n      values.push(data);\n    });\n    return values;\n  }\n\n  public min(): Key | null {\n    if (this._root) return this.minNode(this._root)!.key;\n    return null;\n  }\n\n  public max(): Key | null {\n    if (this._root) return this.maxNode(this._root)!.key;\n    return null;\n  }\n\n  public minNode(t = this._root): Node<Key, Value> | null {\n    if (t) while (t.left) t = t.left;\n    return t;\n  }\n\n  public maxNode(t = this._root): Node<Key, Value> | null {\n    if (t) while (t.right) t = t.right;\n    return t;\n  }\n\n  /**\n   * Returns node at given index\n   */\n  public at(index: number): Node<Key, Value> | null {\n    let current = this._root;\n    let done = false;\n    let i = 0;\n    const Q = [];\n\n    while (!done) {\n      if (current) {\n        Q.push(current);\n        current = current.left;\n      } else {\n        if (Q.length > 0) {\n          current = Q.pop()!;\n          if (i === index) return current;\n          i++;\n          current = current.right!;\n        } else done = true;\n      }\n    }\n    return null;\n  }\n\n  public next(d: Node<Key, Value>): Node<Key, Value> | null {\n    let root = this._root;\n    let successor = null;\n\n    if (d.right) {\n      successor = d.right;\n      while (successor.left) successor = successor.left;\n      return successor;\n    }\n\n    const comparator = this._comparator;\n    while (root) {\n      const cmp = comparator(d.key, root.key);\n      if (cmp === 0) break;\n      else if (cmp < 0) {\n        successor = root;\n        root = root.left;\n      } else root = root.right;\n    }\n\n    return successor;\n  }\n\n  public prev(d: Node<Key, Value>): Node<Key, Value> | null {\n    let root = this._root;\n    let predecessor = null;\n\n    if (d.left !== null) {\n      predecessor = d.left;\n      while (predecessor.right) predecessor = predecessor.right;\n      return predecessor;\n    }\n\n    const comparator = this._comparator;\n    while (root) {\n      const cmp = comparator(d.key, root.key);\n      if (cmp === 0) break;\n      else if (cmp < 0) root = root.left;\n      else {\n        predecessor = root;\n        root = root.right;\n      }\n    }\n    return predecessor;\n  }\n\n  public clear(): Tree<Key, Value> {\n    this._root = null;\n    this._size = 0;\n    return this;\n  }\n\n  public toList(): Node<Key, Value> | null {\n    return toList(this._root);\n  }\n\n  /**\n   * Bulk-load items. Both array have to be same size\n   */\n  public load(keys: Key[], values: Value[] = [], presort: boolean = false): this {\n    let size = keys.length;\n    const comparator = this._comparator;\n\n    // sort if needed\n    if (presort) sort(keys, values, 0, size - 1, comparator);\n\n    if (this._root === null) {\n      // empty tree\n      this._root = loadRecursive(keys, values, 0, size);\n      this._size = size;\n    } else {\n      // that re-builds the whole tree from two in-order traversals\n      const mergedList = mergeLists(this.toList(), createList(keys, values), comparator);\n      size = this._size + size;\n      this._root = sortedListToBST({ head: mergedList }, 0, size);\n      this._size = size;\n    }\n    return this;\n  }\n\n  public isEmpty(): boolean {\n    return this._root === null;\n  }\n\n  get size(): number {\n    return this._size;\n  }\n  get root(): Node<Key, Value> | null {\n    return this._root;\n  }\n\n  public toString(printNode: NodePrinter<Key, Value> = (n) => String(n.key)): string {\n    const out: string[] = [];\n    printRow(this._root, \"\", true, (v) => out.push(v), printNode);\n    return out.join(\"\");\n  }\n\n  public update(key: Key, newKey: Key, newData?: Value): void {\n    const comparator = this._comparator;\n    // if `key` is missing, split() removes nothing and `newKey` is a new node\n    if (this._root === null) this._size++;\n    else {\n      this._root = splay(key, this._root, comparator);\n      if (comparator(key, this._root.key) !== 0) this._size++;\n    }\n    let { left, right } = split(key, this._root, comparator);\n    if (comparator(key, newKey) < 0) {\n      right = insert(newKey, newData, right, comparator);\n    } else {\n      left = insert(newKey, newData, left, comparator);\n    }\n    this._root = merge(left, right, comparator);\n  }\n\n  public split(key: Key): {\n    left: Node<Key, Value> | null;\n    right: Node<Key, Value> | null;\n  } {\n    return split(key, this._root, this._comparator);\n  }\n\n  *[Symbol.iterator]() {\n    let current = this._root;\n    const Q: Node<Key, Value>[] = []; /* Initialize stack s */\n    let done = false;\n\n    while (!done) {\n      if (current !== null) {\n        Q.push(current);\n        current = current.left;\n      } else {\n        if (Q.length !== 0) {\n          current = Q.pop()!;\n          yield current;\n\n          current = current.right;\n        } else done = true;\n      }\n    }\n  }\n}\n\nfunction loadRecursive<Key, Value>(\n  keys: Key[],\n  values: Value[],\n  start: number,\n  end: number,\n): Node<Key, Value> | null {\n  const size = end - start;\n  if (size > 0) {\n    const middle = start + Math.floor(size / 2);\n    const key = keys[middle];\n    const data = values[middle];\n    const node = new Node(key, data);\n    node.left = loadRecursive(keys, values, start, middle);\n    node.right = loadRecursive(keys, values, middle + 1, end);\n    return node;\n  }\n  return null;\n}\n\nfunction createList<Key, Value>(keys: Key[], values: Value[]): Node<Key, Value> | null {\n  const head = new Node<Key, Value>(null as Key);\n  let p: Node<Key, Value> = head;\n  for (let i = 0; i < keys.length; i++) {\n    p = p.next = new Node(keys[i], values[i]);\n  }\n  p.next = null;\n  return head.next;\n}\n\nfunction toList<Key, Value>(root: Node<Key, Value> | null): Node<Key, Value> | null {\n  let current = root;\n  const Q = [];\n  let done = false;\n\n  const head = new Node<Key, Value>(null as Key);\n  let p = head;\n\n  while (!done) {\n    if (current) {\n      Q.push(current);\n      current = current.left;\n    } else {\n      if (Q.length > 0) {\n        current = p = p.next = Q.pop()!;\n        current = current.right;\n      } else done = true;\n    }\n  }\n  p.next = null; // that'll work even if the tree was empty\n  return head.next;\n}\n\nfunction sortedListToBST<Key, Value>(\n  list: TreeNodeList<Key, Value>,\n  start: number,\n  end: number,\n): Node<Key, Value> | null {\n  const size = end - start;\n  if (size > 0) {\n    const middle = start + Math.floor(size / 2);\n    const left = sortedListToBST(list, start, middle);\n\n    const root = list.head;\n    root!.left = left;\n\n    list.head = list.head!.next;\n\n    root!.right = sortedListToBST(list, middle + 1, end);\n    return root!;\n  }\n  return null;\n}\n\nfunction mergeLists<Key, Value>(\n  l1: Node<Key, Value> | null,\n  l2: Node<Key, Value> | null,\n  compare: Comparator<Key>,\n): Node<Key, Value> | null {\n  const head = new Node<Key, Value>(null as Key); // dummy\n  let p = head;\n\n  let p1 = l1;\n  let p2 = l2;\n\n  while (p1 !== null && p2 !== null) {\n    if (compare(p1.key, p2.key) < 0) {\n      p.next = p1;\n      p1 = p1.next;\n    } else {\n      p.next = p2;\n      p2 = p2.next;\n    }\n    p = p.next;\n  }\n\n  // one of the lists is used up: append the rest of the other\n  p.next = p1 !== null ? p1 : p2;\n\n  return head.next;\n}\n\nfunction sort<Key, Value>(\n  keys: Key[],\n  values: Value[],\n  left: number,\n  right: number,\n  compare: Comparator<Key>,\n) {\n  if (left >= right) return;\n\n  const pivot = keys[(left + right) >> 1];\n  let i = left - 1;\n  let j = right + 1;\n\n  while (true) {\n    do i++;\n    while (compare(keys[i], pivot) < 0);\n    do j--;\n    while (compare(keys[j], pivot) > 0);\n    if (i >= j) break;\n\n    const key = keys[i];\n    keys[i] = keys[j];\n    keys[j] = key;\n\n    const value = values[i];\n    values[i] = values[j];\n    values[j] = value;\n  }\n\n  sort(keys, values, left, j, compare);\n  sort(keys, values, j + 1, right, compare);\n}\n"],"mappings":";;;;;;;;;gNAAA,IAAqB,EAArB,KAAsC,CACpC,IACA,KACA,KAAuC,KACvC,MAAwC,KACxC,KAAuC,KAEvC,YAAY,EAAU,EAAc,CAClC,KAAK,IAAM,EAEX,KAAK,KAAO,CACd,CACF,ECFA,SAAS,EAAqB,EAAQ,EAAgB,CACpD,OAAO,EAAI,EAAI,EAAI,EAAI,EAAI,GAAK,CAClC,CAOA,SAAS,EACP,EACA,EACA,EACkB,CAClB,IAAM,EAAI,IAAI,EAAiB,IAAW,EACtC,EAAI,EACJ,EAAI,EAER,OAAa,CACX,IAAM,EAAM,EAAW,EAAG,EAAG,GAAG,EAEhC,GAAI,EAAM,EAAG,CACX,GAAI,EAAG,OAAS,KAAM,MAEtB,GAAI,EAAW,EAAG,EAAE,KAAK,GAAG,EAAI,EAAG,CACjC,IAAM,EAAI,EAAE,KAIZ,GAHA,EAAE,KAAO,EAAE,MACX,EAAE,MAAQ,EACV,EAAI,EACA,EAAE,OAAS,KAAM,KACvB,CACA,EAAE,KAAO,EACT,EAAI,EACJ,EAAI,EAAE,IAER,MAAO,GAAI,EAAM,EAAG,CAClB,GAAI,EAAE,QAAU,KAAM,MAEtB,GAAI,EAAW,EAAG,EAAE,MAAM,GAAG,EAAI,EAAG,CAClC,IAAM,EAAI,EAAE,MAIZ,GAHA,EAAE,MAAQ,EAAE,KACZ,EAAE,KAAO,EACT,EAAI,EACA,EAAE,QAAU,KAAM,KACxB,CACA,EAAE,MAAQ,EACV,EAAI,EACJ,EAAI,EAAE,KACR,MAAO,KACT,CAMA,MAJA,GAAE,MAAQ,EAAE,KACZ,EAAE,KAAO,EAAE,MACX,EAAE,KAAO,EAAE,MACX,EAAE,MAAQ,EAAE,KACL,CACT,CAEA,SAAS,EACP,EACA,EACA,EACA,EACkB,CAClB,IAAM,EAAO,IAAI,EAAK,EAAG,CAAI,EAkB7B,OAhBI,IAAM,MACR,EAAK,KAAO,EAAK,MAAQ,KAClB,IAGT,EAAI,EAAM,EAAG,EAAG,CAAU,EACd,EAAW,EAAG,EAAE,GACxB,EAAM,GACR,EAAK,KAAO,EAAE,KACd,EAAK,MAAQ,EACb,EAAE,KAAO,OAET,EAAK,MAAQ,EAAE,MACf,EAAK,KAAO,EACZ,EAAE,MAAQ,MAEL,EACT,CAEA,SAAS,EACP,EACA,EACA,EAIA,CACA,IAAI,EAAO,KACP,EAAQ,KACZ,GAAI,EAAG,CACL,EAAI,EAAM,EAAK,EAAG,CAAU,EAE5B,IAAM,EAAM,EAAW,EAAE,IAAK,CAAG,EAC7B,IAAQ,GACV,EAAO,EAAE,KACT,EAAQ,EAAE,OACD,EAAM,GACf,EAAQ,EAAE,MACV,EAAE,MAAQ,KACV,EAAO,IAEP,EAAO,EAAE,KACT,EAAE,KAAO,KACT,EAAQ,EAEZ,CACA,MAAO,CAAE,OAAM,OAAM,CACvB,CAEA,SAAS,EACP,EACA,EACA,EACA,CAMA,OALI,IAAU,KAAa,EACvB,IAAS,KAAa,GAE1B,EAAQ,EAAM,EAAK,IAAK,EAAO,CAAU,EACzC,EAAM,KAAO,EACN,EACT,CAOA,SAAS,EACP,EACA,EACA,EACA,EACA,EACA,CACA,GAAI,EAAM,CACR,EAAI,GAAG,IAAS,EAAS,OAAS,SAAS,EAAU,CAAI,EAAE,GAAG,EAC9D,IAAM,EAAS,GAAU,EAAS,OAAS,QACvC,EAAK,MAAM,EAAS,EAAK,KAAM,EAAQ,GAAO,EAAK,CAAS,EAC5D,EAAK,OAAO,EAAS,EAAK,MAAO,EAAQ,GAAM,EAAK,CAAS,CACnE,CACF,CAEA,IAAqB,EAArB,KAAyD,CACvD,YACA,MAAyC,KACzC,MAAwB,EAExB,YAAY,EAA8B,EAAiB,CACzD,KAAK,YAAc,CACrB,CAKA,OAAc,EAAU,EAAgC,CAEtD,MADA,MAAK,QACG,KAAK,MAAQ,EAAO,EAAK,EAAM,KAAK,MAAO,KAAK,WAAW,CACrE,CAKA,IAAW,EAAU,EAAgC,CACnD,IAAM,EAAO,IAAI,EAAK,EAAK,CAAI,EAE3B,KAAK,QAAU,OACjB,EAAK,KAAO,EAAK,MAAQ,KACzB,KAAK,QACL,KAAK,MAAQ,GAGf,IAAM,EAAa,KAAK,YAClB,EAAI,EAAM,EAAK,KAAK,MAAO,CAAU,EACrC,EAAM,EAAW,EAAK,EAAE,GAAG,EAgBjC,OAfI,IAAQ,EAAG,KAAK,MAAQ,GAEtB,EAAM,GACR,EAAK,KAAO,EAAE,KACd,EAAK,MAAQ,EACb,EAAE,KAAO,OAET,EAAK,MAAQ,EAAE,MACf,EAAK,KAAO,EACZ,EAAE,MAAQ,MAEZ,KAAK,QACL,KAAK,MAAQ,GAGR,KAAK,KACd,CAMA,OAAc,EAAgB,CAC5B,KAAK,MAAQ,KAAK,QAAQ,EAAK,KAAK,MAAO,KAAK,WAAW,CAC7D,CAKA,QACE,EACA,EACA,EACyB,CACzB,IAAI,EAeJ,OAdI,IAAM,KAAa,MACvB,EAAI,EAAM,EAAG,EAAG,CAAU,EACd,EAAW,EAAG,EAAE,GACxB,IAAQ,GAEN,EAAE,OAAS,KACb,EAAI,EAAE,OAEN,EAAI,EAAM,EAAG,EAAE,KAAM,CAAU,EAC/B,EAAE,MAAQ,EAAE,OAEd,KAAK,QACE,GAEF,EACT,CAKA,KAA+C,CAC7C,IAAI,EAAO,KAAK,MAChB,GAAI,EAAM,CACR,KAAO,EAAK,MAAM,EAAO,EAAK,KAG9B,MAFA,MAAK,MAAQ,EAAM,EAAK,IAAK,KAAK,MAAQ,KAAK,WAAW,EAC1D,KAAK,MAAQ,KAAK,QAAQ,EAAK,IAAK,KAAK,MAAO,KAAK,WAAW,EACzD,CAAE,IAAK,EAAK,IAAK,KAAM,EAAK,IAAK,CAC1C,CACA,OAAO,IACT,CAKA,WAAkB,EAAmC,CACnD,IAAI,EAAU,KAAK,MACb,EAAU,KAAK,YACrB,KAAO,GAAS,CACd,IAAM,EAAM,EAAQ,EAAK,EAAQ,GAAG,EACpC,GAAI,IAAQ,EAAG,OAAO,EACjB,AACA,EADI,EAAM,EAAa,EAAQ,KACrB,EAAQ,KACzB,CACA,OAAO,IACT,CAEA,KAAY,EAAmC,CAK7C,OAJI,KAAK,QACP,KAAK,MAAQ,EAAM,EAAK,KAAK,MAAO,KAAK,WAAW,EAChD,KAAK,YAAY,EAAK,KAAK,MAAM,GAAG,IAAM,GAAU,KAEnD,KAAK,KACd,CAEA,SAAgB,EAAmB,CACjC,IAAI,EAAU,KAAK,MACb,EAAU,KAAK,YACrB,KAAO,GAAS,CACd,IAAM,EAAM,EAAQ,EAAK,EAAQ,GAAG,EACpC,GAAI,IAAQ,EAAG,MAAO,GACjB,AACA,EADI,EAAM,EAAa,EAAQ,KACrB,EAAQ,KACzB,CACA,MAAO,EACT,CAEA,QAAe,EAA8B,EAAiC,CAC5E,IAAI,EAAU,KAAK,MACb,EAAI,CAAC,EACP,EAAO,GAEX,KAAO,CAAC,GACF,IAAY,KAIV,EAAE,SAAW,EAKV,EAAO,IAJZ,EAAU,EAAE,IAAI,EAChB,EAAQ,KAAK,EAAK,CAAO,EAEzB,EAAU,EAAQ,QAPpB,EAAE,KAAK,CAAO,EACd,EAAU,EAAQ,MAUtB,OAAO,IACT,CAKA,MAAa,EAAU,EAAW,EAAyB,EAAiC,CAC1F,IAAM,EAAI,CAAC,EACL,EAAU,KAAK,YACjB,EAAO,KAAK,MACZ,EAEJ,KAAO,EAAE,SAAW,GAAK,GACvB,GAAI,EACF,EAAE,KAAK,CAAI,EACX,EAAO,EAAK,SACP,CAGL,GAFA,EAAO,EAAE,IAAI,EACb,EAAM,EAAQ,EAAK,IAAK,CAAI,EACxB,EAAM,EACR,MACK,GAAI,EAAQ,EAAK,IAAK,CAAG,GAAK,GAC/B,EAAG,KAAK,EAAK,CAAI,EAAG,OAAO,KAEjC,EAAO,EAAK,KACd,CAEF,OAAO,IACT,CAKA,MAAqB,CACnB,IAAM,EAAc,CAAC,EAIrB,OAHA,KAAK,SAAS,CAAE,SAAU,CACxB,EAAK,KAAK,CAAG,CACf,CAAC,EACM,CACT,CAKA,QAAyB,CACvB,IAAM,EAAkB,CAAC,EAIzB,OAHA,KAAK,SAAS,CAAE,UAAW,CACzB,EAAO,KAAK,CAAI,CAClB,CAAC,EACM,CACT,CAEA,KAAyB,CAEvB,OADI,KAAK,MAAc,KAAK,QAAQ,KAAK,KAAK,EAAG,IAC1C,IACT,CAEA,KAAyB,CAEvB,OADI,KAAK,MAAc,KAAK,QAAQ,KAAK,KAAK,EAAG,IAC1C,IACT,CAEA,QAAe,EAAI,KAAK,MAAgC,CACtD,GAAI,EAAG,KAAO,EAAE,MAAM,EAAI,EAAE,KAC5B,OAAO,CACT,CAEA,QAAe,EAAI,KAAK,MAAgC,CACtD,GAAI,EAAG,KAAO,EAAE,OAAO,EAAI,EAAE,MAC7B,OAAO,CACT,CAKA,GAAU,EAAwC,CAChD,IAAI,EAAU,KAAK,MACf,EAAO,GACP,EAAI,EACF,EAAI,CAAC,EAEX,KAAO,CAAC,GACN,GAAI,EACF,EAAE,KAAK,CAAO,EACd,EAAU,EAAQ,UAElB,GAAI,EAAE,OAAS,EAAG,CAEhB,GADA,EAAU,EAAE,IAAI,EACZ,IAAM,EAAO,OAAO,EACxB,IACA,EAAU,EAAQ,KACpB,MAAO,EAAO,GAGlB,OAAO,IACT,CAEA,KAAY,EAA8C,CACxD,IAAI,EAAO,KAAK,MACZ,EAAY,KAEhB,GAAI,EAAE,MAAO,CAEX,IADA,EAAY,EAAE,MACP,EAAU,MAAM,EAAY,EAAU,KAC7C,OAAO,CACT,CAEA,IAAM,EAAa,KAAK,YACxB,KAAO,GAAM,CACX,IAAM,EAAM,EAAW,EAAE,IAAK,EAAK,GAAG,EACtC,GAAI,IAAQ,EAAG,MACN,EAAM,GACb,EAAY,EACZ,EAAO,EAAK,MACP,EAAO,EAAK,KACrB,CAEA,OAAO,CACT,CAEA,KAAY,EAA8C,CACxD,IAAI,EAAO,KAAK,MACZ,EAAc,KAElB,GAAI,EAAE,OAAS,KAAM,CAEnB,IADA,EAAc,EAAE,KACT,EAAY,OAAO,EAAc,EAAY,MACpD,OAAO,CACT,CAEA,IAAM,EAAa,KAAK,YACxB,KAAO,GAAM,CACX,IAAM,EAAM,EAAW,EAAE,IAAK,EAAK,GAAG,EACtC,GAAI,IAAQ,EAAG,MACN,EAAM,EAAG,EAAO,EAAK,MAE5B,EAAc,EACd,EAAO,EAAK,MAEhB,CACA,OAAO,CACT,CAEA,OAAiC,CAG/B,MAFA,MAAK,MAAQ,KACb,KAAK,MAAQ,EACN,IACT,CAEA,QAAyC,CACvC,OAAO,EAAO,KAAK,KAAK,CAC1B,CAKA,KAAY,EAAa,EAAkB,CAAC,EAAG,EAAmB,GAAa,CAC7E,IAAI,EAAO,EAAK,OACV,EAAa,KAAK,YAKxB,GAFI,GAAS,EAAK,EAAM,EAAQ,EAAG,EAAO,EAAG,CAAU,EAEnD,KAAK,QAAU,KAEjB,KAAK,MAAQ,EAAc,EAAM,EAAQ,EAAG,CAAI,EAChD,KAAK,MAAQ,MACR,CAEL,IAAM,EAAa,EAAW,KAAK,OAAO,EAAG,EAAW,EAAM,CAAM,EAAG,CAAU,EACjF,EAAO,KAAK,MAAQ,EACpB,KAAK,MAAQ,EAAgB,CAAE,KAAM,CAAW,EAAG,EAAG,CAAI,EAC1D,KAAK,MAAQ,CACf,CACA,OAAO,IACT,CAEA,SAA0B,CACxB,OAAO,KAAK,QAAU,IACxB,CAEA,IAAI,MAAe,CACjB,OAAO,KAAK,KACd,CACA,IAAI,MAAgC,CAClC,OAAO,KAAK,KACd,CAEA,SAAgB,EAAsC,GAAM,OAAO,EAAE,GAAG,EAAW,CACjF,IAAM,EAAgB,CAAC,EAEvB,OADA,EAAS,KAAK,MAAO,GAAI,GAAO,GAAM,EAAI,KAAK,CAAC,EAAG,CAAS,EACrD,EAAI,KAAK,EAAE,CACpB,CAEA,OAAc,EAAU,EAAa,EAAuB,CAC1D,IAAM,EAAa,KAAK,YAEpB,KAAK,QAAU,KAAM,KAAK,SAE5B,KAAK,MAAQ,EAAM,EAAK,KAAK,MAAO,CAAU,EAC1C,EAAW,EAAK,KAAK,MAAM,GAAG,IAAM,GAAG,KAAK,SAElD,GAAI,CAAE,OAAM,SAAU,EAAM,EAAK,KAAK,MAAO,CAAU,EACnD,EAAW,EAAK,CAAM,EAAI,EAC5B,EAAQ,EAAO,EAAQ,EAAS,EAAO,CAAU,EAEjD,EAAO,EAAO,EAAQ,EAAS,EAAM,CAAU,EAEjD,KAAK,MAAQ,EAAM,EAAM,EAAO,CAAU,CAC5C,CAEA,MAAa,EAGX,CACA,OAAO,EAAM,EAAK,KAAK,MAAO,KAAK,WAAW,CAChD,CAEA,EAAE,OAAO,WAAY,CACnB,IAAI,EAAU,KAAK,MACb,EAAwB,CAAC,EAC3B,EAAO,GAEX,KAAO,CAAC,GACF,IAAY,KAIV,EAAE,SAAW,EAKV,EAAO,IAJZ,EAAU,EAAE,IAAI,EAChB,MAAM,EAEN,EAAU,EAAQ,QAPpB,EAAE,KAAK,CAAO,EACd,EAAU,EAAQ,KAUxB,CACF,EAEA,SAAS,EACP,EACA,EACA,EACA,EACyB,CACzB,IAAM,EAAO,EAAM,EACnB,GAAI,EAAO,EAAG,CACZ,IAAM,EAAS,EAAQ,KAAK,MAAM,EAAO,CAAC,EACpC,EAAM,EAAK,GACX,EAAO,EAAO,GACd,EAAO,IAAI,EAAK,EAAK,CAAI,EAG/B,MAFA,GAAK,KAAO,EAAc,EAAM,EAAQ,EAAO,CAAM,EACrD,EAAK,MAAQ,EAAc,EAAM,EAAQ,EAAS,EAAG,CAAG,EACjD,CACT,CACA,OAAO,IACT,CAEA,SAAS,EAAuB,EAAa,EAA0C,CACrF,IAAM,EAAO,IAAI,EAAiB,IAAW,EACzC,EAAsB,EAC1B,IAAK,IAAI,EAAI,EAAG,EAAI,EAAK,OAAQ,IAC/B,EAAI,EAAE,KAAO,IAAI,EAAK,EAAK,GAAI,EAAO,EAAE,EAG1C,MADA,GAAE,KAAO,KACF,EAAK,IACd,CAEA,SAAS,EAAmB,EAAwD,CAClF,IAAI,EAAU,EACR,EAAI,CAAC,EACP,EAAO,GAEL,EAAO,IAAI,EAAiB,IAAW,EACzC,EAAI,EAER,KAAO,CAAC,GACF,GACF,EAAE,KAAK,CAAO,EACd,EAAU,EAAQ,MAEd,EAAE,OAAS,GACb,EAAU,EAAI,EAAE,KAAO,EAAE,IAAI,EAC7B,EAAU,EAAQ,OACb,EAAO,GAIlB,MADA,GAAE,KAAO,KACF,EAAK,IACd,CAEA,SAAS,EACP,EACA,EACA,EACyB,CACzB,IAAM,EAAO,EAAM,EACnB,GAAI,EAAO,EAAG,CACZ,IAAM,EAAS,EAAQ,KAAK,MAAM,EAAO,CAAC,EACpC,EAAO,EAAgB,EAAM,EAAO,CAAM,EAE1C,EAAO,EAAK,KAMlB,MALA,GAAM,KAAO,EAEb,EAAK,KAAO,EAAK,KAAM,KAEvB,EAAM,MAAQ,EAAgB,EAAM,EAAS,EAAG,CAAG,EAC5C,CACT,CACA,OAAO,IACT,CAEA,SAAS,EACP,EACA,EACA,EACyB,CACzB,IAAM,EAAO,IAAI,EAAiB,IAAW,EACzC,EAAI,EAEJ,EAAK,EACL,EAAK,EAET,KAAO,IAAO,MAAQ,IAAO,MACvB,EAAQ,EAAG,IAAK,EAAG,GAAG,EAAI,GAC5B,EAAE,KAAO,EACT,EAAK,EAAG,OAER,EAAE,KAAO,EACT,EAAK,EAAG,MAEV,EAAI,EAAE,KAMR,MAFA,GAAE,KAAO,IAAO,KAAY,EAAL,EAEhB,EAAK,IACd,CAEA,SAAS,EACP,EACA,EACA,EACA,EACA,EACA,CACA,GAAI,GAAQ,EAAO,OAEnB,IAAM,EAAQ,EAAM,EAAO,GAAU,GACjC,EAAI,EAAO,EACX,EAAI,EAAQ,EAEhB,OAAa,CACX,EAAG,WACI,EAAQ,EAAK,GAAI,CAAK,EAAI,GACjC,EAAG,WACI,EAAQ,EAAK,GAAI,CAAK,EAAI,GACjC,GAAI,GAAK,EAAG,MAEZ,IAAM,EAAM,EAAK,GACjB,EAAK,GAAK,EAAK,GACf,EAAK,GAAK,EAEV,IAAM,EAAQ,EAAO,GACrB,EAAO,GAAK,EAAO,GACnB,EAAO,GAAK,CACd,CAEA,EAAK,EAAM,EAAQ,EAAM,EAAG,CAAO,EACnC,EAAK,EAAM,EAAQ,EAAI,EAAG,EAAO,CAAO,CAC1C"}