{"version":3,"file":"splaytree.umd.cjs","sources":["../src/node.ts","../src/index.ts"],"sourcesContent":["\nexport default class Node<Key, Value> {\n  public key:Key;\n  public data:any;\n  public left:Node<Key, Value>|null;\n  public right:Node<Key, Value>|null;\n  public next:Node<Key, Value>|null = null;\n\n  constructor (key:Key, data?:any) {\n    this.key    = key;\n    this.data   = data;\n    this.left   = null;\n    this.right  = null;\n  }\n}","import Node from \"./node\";\nimport { Key, Value } from \"./types\";\n\nexport type Comparator<Key> = (a: Key, b: Key) => number;\nexport type Visitor<Key, Value> = (\n  node: Node<Key, Value>\n) => 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(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(\n  i: Key,\n  t: Node<Key, Value>,\n  comparator: Comparator<Key>\n): Node<Key, Value> {\n  const N = new Node(null, null);\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(\n  i: Key,\n  data: Value,\n  t: Node<Key, Value>,\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 if (cmp >= 0) {\n    node.right = t.right;\n    node.left = t;\n    t.right = null;\n  }\n  return node;\n}\n\nfunction split(\n  key: Key,\n  v: Node<Key, Value>,\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(\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(\n  root: Node<Key, Value>,\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 = any> {\n  private _comparator: Comparator<Key>;\n  private _root: Node<Key, Value> | null = null;\n  private _size: number = 0;\n\n  constructor(comparator = 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 if (cmp > 0) {\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(i: Key, t: Node<Key, Value>, comparator: Comparator<Key>) {\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?: any): 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(\n    low: Key,\n    high: Key,\n    fn: Visitor<Key, Value>,\n    ctx?: any\n  ): 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() {\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) {\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(\n        this.toList(),\n        createList(keys, values),\n        comparator\n      );\n      size = this._size + size;\n      this._root = sortedListToBST({ head: mergedList }, 0, 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(\n    printNode: NodePrinter<Key, Value> = (n) => String(n.key)\n  ): 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    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    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(\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(keys: Key[], values: Value[]): Node<Key, Value> {\n  const head = new Node<Key, Value>(null, null);\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(root: Node<Key, Value>): Node<Key, Value> {\n  let current = root;\n  const Q = [];\n  let done = false;\n\n  const head = new Node<Key, Value>(null, null);\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(\n  list: TreeNodeList<Key, Value>,\n  start: number,\n  end: number\n) {\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>,\n  l2: Node<Key, Value>,\n  compare: Comparator<Key>\n): Node<Key, Value> {\n  const head: Node<Key, Value> = new Node<Key, Value>(null as Key, null); // dummy\n  let p = head;\n\n  let p1: Node<Key, Value> = l1;\n  let p2: Node<Key, Value> = 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  if (p1 !== null) {\n    p.next = p1;\n  } else if (p2 !== null) {\n    p.next = p2;\n  }\n\n  return head.next!;\n}\n\nfunction sort(\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    let tmp = keys[i];\n    keys[i] = keys[j];\n    keys[j] = tmp;\n\n    tmp = values[i];\n    values[i] = values[j];\n    values[j] = tmp;\n  }\n\n  sort(keys, values, left, j, compare);\n  sort(keys, values, j + 1, right, compare);\n}\n"],"names":["Node","key","data","DEFAULT_COMPARE","a","b","splay","i","comparator","N","l","r","cmp","y","insert","t","node","split","v","left","right","merge","printRow","root","prefix","isTail","out","printNode","indent","Tree","x","current","compare","visitor","ctx","Q","done","low","high","fn","keys","values","index","d","successor","predecessor","toList","presort","size","sort","loadRecursive","mergedList","mergeLists","createList","sortedListToBST","n","newKey","newData","start","end","middle","head","p","list","l1","l2","p1","p2","pivot","j","tmp"],"mappings":"2NACA,MAAqBA,CAAiB,CAOpC,YAAaC,EAASC,EAAW,CAFjC,KAAO,KAA6B,KAGlC,KAAK,IAASD,EACd,KAAK,KAASC,EACd,KAAK,KAAS,KACd,KAAK,MAAS,IAChB,CACF,CCDA,SAASC,EAAgBC,EAAQC,EAAgB,CAC/C,OAAOD,EAAIC,EAAI,EAAID,EAAIC,EAAI,GAAK,CAClC,CAOA,SAASC,EACPC,EACA,EACAC,EACkB,CAClB,MAAMC,EAAI,IAAIT,EAAK,KAAM,IAAI,EAC7B,IAAIU,EAAID,EACJE,EAAIF,EAER,OAAa,CACX,MAAMG,EAAMJ,EAAWD,EAAG,EAAG,GAAG,EAEhC,GAAIK,EAAM,EAAG,CACX,GAAI,EAAG,OAAS,KAAM,MAEtB,GAAIJ,EAAWD,EAAG,EAAE,KAAK,GAAG,EAAI,EAAG,CACjC,MAAMM,EAAI,EAAE,KAIZ,GAHA,EAAE,KAAOA,EAAE,MACXA,EAAE,MAAQ,EACV,EAAIA,EACA,EAAE,OAAS,KAAM,KACvB,CACAF,EAAE,KAAO,EACTA,EAAI,EACJ,EAAI,EAAE,IAER,SAAWC,EAAM,EAAG,CAClB,GAAI,EAAE,QAAU,KAAM,MAEtB,GAAIJ,EAAWD,EAAG,EAAE,MAAM,GAAG,EAAI,EAAG,CAClC,MAAMM,EAAI,EAAE,MAIZ,GAHA,EAAE,MAAQA,EAAE,KACZA,EAAE,KAAO,EACT,EAAIA,EACA,EAAE,QAAU,KAAM,KACxB,CACAH,EAAE,MAAQ,EACVA,EAAI,EACJ,EAAI,EAAE,KACR,KAAO,MACT,CAEA,OAAAA,EAAE,MAAQ,EAAE,KACZC,EAAE,KAAO,EAAE,MACX,EAAE,KAAOF,EAAE,MACX,EAAE,MAAQA,EAAE,KACL,CACT,CAEA,SAASK,EACPP,EACAL,EACAa,EACAP,EACkB,CAClB,MAAMQ,EAAO,IAAIhB,EAAKO,EAAGL,CAAI,EAE7B,GAAIa,IAAM,KACR,OAAAC,EAAK,KAAOA,EAAK,MAAQ,KAClBA,EAGTD,EAAIT,EAAMC,EAAGQ,EAAGP,CAAU,EAC1B,MAAMI,EAAMJ,EAAWD,EAAGQ,EAAE,GAAG,EAC/B,OAAIH,EAAM,GACRI,EAAK,KAAOD,EAAE,KACdC,EAAK,MAAQD,EACbA,EAAE,KAAO,MACAH,GAAO,IAChBI,EAAK,MAAQD,EAAE,MACfC,EAAK,KAAOD,EACZA,EAAE,MAAQ,MAELC,CACT,CAEA,SAASC,EACPhB,EACAiB,EACAV,EAIA,CACA,IAAIW,EAAO,KACPC,EAAQ,KACZ,GAAIF,EAAG,CACLA,EAAIZ,EAAML,EAAKiB,EAAGV,CAAU,EAE5B,MAAMI,EAAMJ,EAAWU,EAAE,IAAKjB,CAAG,EAC7BW,IAAQ,GACVO,EAAOD,EAAE,KACTE,EAAQF,EAAE,OACDN,EAAM,GACfQ,EAAQF,EAAE,MACVA,EAAE,MAAQ,KACVC,EAAOD,IAEPC,EAAOD,EAAE,KACTA,EAAE,KAAO,KACTE,EAAQF,EAEZ,CACA,MAAO,CAAE,KAAAC,EAAM,MAAAC,CAAA,CACjB,CAEA,SAASC,EACPF,EACAC,EACAZ,EACA,CACA,OAAIY,IAAU,KAAaD,GACvBA,IAAS,OAEbC,EAAQd,EAAMa,EAAK,IAAKC,EAAOZ,CAAU,EACzCY,EAAM,KAAOD,GACNC,EACT,CAOA,SAASE,EACPC,EACAC,EACAC,EACAC,EACAC,EACA,CACA,GAAIJ,EAAM,CACRG,EAAI,GAAGF,CAAM,GAAGC,EAAS,OAAS,MAAM,GAAGE,EAAUJ,CAAI,CAAC;AAAA,CAAI,EAC9D,MAAMK,EAASJ,GAAUC,EAAS,OAAS,QACvCF,EAAK,MAAMD,EAASC,EAAK,KAAMK,EAAQ,GAAOF,EAAKC,CAAS,EAC5DJ,EAAK,OAAOD,EAASC,EAAK,MAAOK,EAAQ,GAAMF,EAAKC,CAAS,CACnE,CACF,CAEA,MAAqBE,CAAgC,CAKnD,YAAYrB,EAAaL,EAAiB,CAH1C,KAAQ,MAAiC,KACzC,KAAQ,MAAgB,EAGtB,KAAK,YAAcK,CACrB,CAKO,OAAOP,EAAUC,EAAgC,CACtD,YAAK,QACG,KAAK,MAAQY,EAAOb,EAAKC,EAAM,KAAK,MAAQ,KAAK,WAAW,CACtE,CAKO,IAAID,EAAUC,EAAgC,CACnD,MAAMc,EAAO,IAAIhB,EAAKC,EAAKC,CAAI,EAE3B,KAAK,QAAU,OACjBc,EAAK,KAAOA,EAAK,MAAQ,KACzB,KAAK,QACL,KAAK,MAAQA,GAGf,MAAMR,EAAa,KAAK,YAClBO,EAAIT,EAAML,EAAK,KAAK,MAAOO,CAAU,EACrCI,EAAMJ,EAAWP,EAAKc,EAAE,GAAG,EACjC,OAAIH,IAAQ,EAAG,KAAK,MAAQG,GAEtBH,EAAM,GACRI,EAAK,KAAOD,EAAE,KACdC,EAAK,MAAQD,EACbA,EAAE,KAAO,MACAH,EAAM,IACfI,EAAK,MAAQD,EAAE,MACfC,EAAK,KAAOD,EACZA,EAAE,MAAQ,MAEZ,KAAK,QACL,KAAK,MAAQC,GAGR,KAAK,KACd,CAMO,OAAOf,EAAgB,CAC5B,KAAK,MAAQ,KAAK,QAAQA,EAAK,KAAK,MAAQ,KAAK,WAAW,CAC9D,CAKQ,QAAQM,EAAQQ,EAAqBP,EAA6B,CACxE,IAAIsB,EACJ,OAAIf,IAAM,KAAa,MACvBA,EAAIT,EAAMC,EAAGQ,EAAGP,CAAU,EACdA,EAAWD,EAAGQ,EAAE,GAAG,IACnB,GAENA,EAAE,OAAS,KACbe,EAAIf,EAAE,OAENe,EAAIxB,EAAMC,EAAGQ,EAAE,KAAMP,CAAU,EAC/BsB,EAAE,MAAQf,EAAE,OAEd,KAAK,QACEe,GAEFf,EACT,CAKO,KAAwC,CAC7C,IAAIC,EAAO,KAAK,MAChB,GAAIA,EAAM,CACR,KAAOA,EAAK,MAAMA,EAAOA,EAAK,KAC9B,YAAK,MAAQV,EAAMU,EAAK,IAAK,KAAK,MAAQ,KAAK,WAAW,EAC1D,KAAK,MAAQ,KAAK,QAAQA,EAAK,IAAK,KAAK,MAAO,KAAK,WAAW,EACzD,CAAE,IAAKA,EAAK,IAAK,KAAMA,EAAK,IAAA,CACrC,CACA,OAAO,IACT,CAKO,WAAWf,EAAmC,CACnD,IAAI8B,EAAU,KAAK,MACnB,MAAMC,EAAU,KAAK,YACrB,KAAOD,GAAS,CACd,MAAMnB,EAAMoB,EAAQ/B,EAAK8B,EAAQ,GAAG,EACpC,GAAInB,IAAQ,EAAG,OAAOmB,EACbnB,EAAM,EAAGmB,EAAUA,EAAQ,OACrBA,EAAQ,KACzB,CACA,OAAO,IACT,CAEO,KAAK9B,EAAmC,CAC7C,OAAI,KAAK,QACP,KAAK,MAAQK,EAAML,EAAK,KAAK,MAAO,KAAK,WAAW,EAChD,KAAK,YAAYA,EAAK,KAAK,MAAM,GAAG,IAAM,GAAU,KAEnD,KAAK,KACd,CAEO,SAASA,EAAmB,CACjC,IAAI8B,EAAU,KAAK,MACnB,MAAMC,EAAU,KAAK,YACrB,KAAOD,GAAS,CACd,MAAMnB,EAAMoB,EAAQ/B,EAAK8B,EAAQ,GAAG,EACpC,GAAInB,IAAQ,EAAG,MAAO,GACbA,EAAM,EAAGmB,EAAUA,EAAQ,OACrBA,EAAQ,KACzB,CACA,MAAO,EACT,CAEO,QAAQE,EAA8BC,EAA6B,CACxE,IAAIH,EAAU,KAAK,MACnB,MAAMI,EAAI,CAAA,EACV,IAAIC,EAAO,GAEX,KAAO,CAACA,GACFL,IAAY,MACdI,EAAE,KAAKJ,CAAO,EACdA,EAAUA,EAAQ,MAEdI,EAAE,SAAW,GACfJ,EAAUI,EAAE,IAAA,EACZF,EAAQ,KAAKC,EAAKH,CAAO,EAEzBA,EAAUA,EAAQ,OACbK,EAAO,GAGlB,OAAO,IACT,CAKO,MACLC,EACAC,EACAC,EACAL,EACkB,CAClB,MAAMC,EAAI,CAAA,EACJH,EAAU,KAAK,YACrB,IAAIhB,EAAO,KAAK,MACZJ,EAEJ,KAAOuB,EAAE,SAAW,GAAKnB,GACvB,GAAIA,EACFmB,EAAE,KAAKnB,CAAI,EACXA,EAAOA,EAAK,SACP,CAGL,GAFAA,EAAOmB,EAAE,IAAA,EACTvB,EAAMoB,EAAQhB,EAAK,IAAKsB,CAAI,EACxB1B,EAAM,EACR,SACSoB,EAAQhB,EAAK,IAAKqB,CAAG,GAAK,GAC/BE,EAAG,KAAKL,EAAKlB,CAAI,EAAG,OAAO,KAEjCA,EAAOA,EAAK,KACd,CAEF,OAAO,IACT,CAKO,MAAc,CACnB,MAAMwB,EAAc,CAAA,EACpB,YAAK,QAAQ,CAAC,CAAE,IAAAvC,KAAU,CACxBuC,EAAK,KAAKvC,CAAG,CACf,CAAC,EACMuC,CACT,CAKO,QAAkB,CACvB,MAAMC,EAAkB,CAAA,EACxB,YAAK,QAAQ,CAAC,CAAE,KAAAvC,KAAW,CACzBuC,EAAO,KAAKvC,CAAI,CAClB,CAAC,EACMuC,CACT,CAEO,KAAkB,CACvB,OAAI,KAAK,MAAc,KAAK,QAAQ,KAAK,KAAK,EAAG,IAC1C,IACT,CAEO,KAAkB,CACvB,OAAI,KAAK,MAAc,KAAK,QAAQ,KAAK,KAAK,EAAG,IAC1C,IACT,CAEO,QAAQ,EAAI,KAAK,MAAgC,CACtD,GAAI,EAAG,KAAO,EAAE,QAAU,EAAE,KAC5B,OAAO,CACT,CAEO,QAAQ,EAAI,KAAK,MAAgC,CACtD,GAAI,EAAG,KAAO,EAAE,SAAW,EAAE,MAC7B,OAAO,CACT,CAKO,GAAGC,EAAwC,CAChD,IAAIX,EAAU,KAAK,MACfK,EAAO,GACP,EAAI,EACR,MAAMD,EAAI,CAAA,EAEV,KAAO,CAACC,GACN,GAAIL,EACFI,EAAE,KAAKJ,CAAO,EACdA,EAAUA,EAAQ,aAEdI,EAAE,OAAS,EAAG,CAEhB,GADAJ,EAAUI,EAAE,IAAA,EACR,IAAMO,EAAO,OAAOX,EACxB,IACAA,EAAUA,EAAQ,KACpB,MAAOK,EAAO,GAGlB,OAAO,IACT,CAEO,KAAKO,EAA8C,CACxD,IAAIpB,EAAO,KAAK,MACZqB,EAAY,KAEhB,GAAID,EAAE,MAAO,CAEX,IADAC,EAAYD,EAAE,MACPC,EAAU,MAAMA,EAAYA,EAAU,KAC7C,OAAOA,CACT,CAEA,MAAMpC,EAAa,KAAK,YACxB,KAAOe,GAAM,CACX,MAAMX,EAAMJ,EAAWmC,EAAE,IAAKpB,EAAK,GAAG,EACtC,GAAIX,IAAQ,EAAG,MACNA,EAAM,GACbgC,EAAYrB,EACZA,EAAOA,EAAK,QACAA,EAAK,KACrB,CAEA,OAAOqB,CACT,CAEO,KAAKD,EAA8C,CACxD,IAAIpB,EAAO,KAAK,MACZsB,EAAc,KAElB,GAAIF,EAAE,OAAS,KAAM,CAEnB,IADAE,EAAcF,EAAE,KACTE,EAAY,OAAOA,EAAcA,EAAY,MACpD,OAAOA,CACT,CAEA,MAAMrC,EAAa,KAAK,YACxB,KAAOe,GAAM,CACX,MAAMX,EAAMJ,EAAWmC,EAAE,IAAKpB,EAAK,GAAG,EACtC,GAAIX,IAAQ,EAAG,MACNA,EAAM,EAAGW,EAAOA,EAAK,MAE5BsB,EAActB,EACdA,EAAOA,EAAK,MAEhB,CACA,OAAOsB,CACT,CAEO,OAA0B,CAC/B,YAAK,MAAQ,KACb,KAAK,MAAQ,EACN,IACT,CAEO,QAAS,CACd,OAAOC,EAAO,KAAK,KAAM,CAC3B,CAKO,KAAKN,EAAaC,EAAkB,CAAA,EAAIM,EAAmB,GAAO,CACvE,IAAIC,EAAOR,EAAK,OAChB,MAAMhC,EAAa,KAAK,YAKxB,GAFIuC,GAASE,EAAKT,EAAMC,EAAQ,EAAGO,EAAO,EAAGxC,CAAU,EAEnD,KAAK,QAAU,KAEjB,KAAK,MAAQ0C,EAAcV,EAAMC,EAAQ,EAAGO,CAAI,EAChD,KAAK,MAAQA,MACR,CAEL,MAAMG,EAAaC,EACjB,KAAK,OAAA,EACLC,EAAWb,EAAMC,CAAM,EACvBjC,CAAA,EAEFwC,EAAO,KAAK,MAAQA,EACpB,KAAK,MAAQM,EAAgB,CAAE,KAAMH,CAAA,EAAc,EAAGH,CAAI,CAC5D,CACA,OAAO,IACT,CAEO,SAAmB,CACxB,OAAO,KAAK,QAAU,IACxB,CAEA,IAAI,MAAe,CACjB,OAAO,KAAK,KACd,CACA,IAAI,MAAgC,CAClC,OAAO,KAAK,KACd,CAEO,SACLrB,EAAsC4B,GAAM,OAAOA,EAAE,GAAG,EAChD,CACR,MAAM7B,EAAgB,CAAA,EACtB,OAAAJ,EAAS,KAAK,MAAQ,GAAI,GAAOJ,GAAMQ,EAAI,KAAKR,CAAC,EAAGS,CAAS,EACtDD,EAAI,KAAK,EAAE,CACpB,CAEO,OAAOzB,EAAUuD,EAAaC,EAAuB,CAC1D,MAAMjD,EAAa,KAAK,YACxB,GAAI,CAAE,KAAAW,EAAM,MAAAC,GAAUH,EAAMhB,EAAK,KAAK,MAAQO,CAAU,EACpDA,EAAWP,EAAKuD,CAAM,EAAI,EAC5BpC,EAAQN,EAAO0C,EAAQC,EAASrC,EAAQZ,CAAU,EAElDW,EAAOL,EAAO0C,EAAQC,EAAStC,EAAOX,CAAU,EAElD,KAAK,MAAQa,EAAMF,EAAMC,EAAOZ,CAAU,CAC5C,CAEO,MAAMP,EAAU,CACrB,OAAOgB,EAAMhB,EAAK,KAAK,MAAQ,KAAK,WAAW,CACjD,CAEA,EAAE,OAAO,QAAQ,GAAI,CACnB,IAAI8B,EAAU,KAAK,MACnB,MAAMI,EAAwB,CAAA,EAC9B,IAAIC,EAAO,GAEX,KAAO,CAACA,GACFL,IAAY,MACdI,EAAE,KAAKJ,CAAO,EACdA,EAAUA,EAAQ,MAEdI,EAAE,SAAW,GACfJ,EAAUI,EAAE,IAAA,EACZ,MAAMJ,EAENA,EAAUA,EAAQ,OACbK,EAAO,EAGpB,CACF,CAEA,SAASc,EACPV,EACAC,EACAiB,EACAC,EACyB,CACzB,MAAMX,EAAOW,EAAMD,EACnB,GAAIV,EAAO,EAAG,CACZ,MAAMY,EAASF,EAAQ,KAAK,MAAMV,EAAO,CAAC,EACpC/C,EAAMuC,EAAKoB,CAAM,EACjB1D,EAAOuC,EAAOmB,CAAM,EACpB5C,EAAO,IAAIhB,EAAKC,EAAKC,CAAI,EAC/B,OAAAc,EAAK,KAAOkC,EAAcV,EAAMC,EAAQiB,EAAOE,CAAM,EACrD5C,EAAK,MAAQkC,EAAcV,EAAMC,EAAQmB,EAAS,EAAGD,CAAG,EACjD3C,CACT,CACA,OAAO,IACT,CAEA,SAASqC,EAAWb,EAAaC,EAAmC,CAClE,MAAMoB,EAAO,IAAI7D,EAAiB,KAAM,IAAI,EAC5C,IAAI8D,EAAsBD,EAC1B,QAAS,EAAI,EAAG,EAAIrB,EAAK,OAAQ,IAC/BsB,EAAIA,EAAE,KAAO,IAAI9D,EAAKwC,EAAK,CAAC,EAAGC,EAAO,CAAC,CAAC,EAE1C,OAAAqB,EAAE,KAAO,KACFD,EAAK,IACd,CAEA,SAASf,EAAOvB,EAA0C,CACxD,IAAIQ,EAAUR,EACd,MAAMY,EAAI,CAAA,EACV,IAAIC,EAAO,GAEX,MAAMyB,EAAO,IAAI7D,EAAiB,KAAM,IAAI,EAC5C,IAAI8D,EAAID,EAER,KAAO,CAACzB,GACFL,GACFI,EAAE,KAAKJ,CAAO,EACdA,EAAUA,EAAQ,MAEdI,EAAE,OAAS,GACbJ,EAAU+B,EAAIA,EAAE,KAAO3B,EAAE,IAAA,EACzBJ,EAAUA,EAAQ,OACbK,EAAO,GAGlB,OAAA0B,EAAE,KAAO,KACFD,EAAK,IACd,CAEA,SAASP,EACPS,EACAL,EACAC,EACA,CACA,MAAMX,EAAOW,EAAMD,EACnB,GAAIV,EAAO,EAAG,CACZ,MAAMY,EAASF,EAAQ,KAAK,MAAMV,EAAO,CAAC,EACpC7B,EAAOmC,EAAgBS,EAAML,EAAOE,CAAM,EAE1CrC,EAAOwC,EAAK,KAClB,OAAAxC,EAAM,KAAOJ,EAEb4C,EAAK,KAAOA,EAAK,KAAM,KAEvBxC,EAAM,MAAQ+B,EAAgBS,EAAMH,EAAS,EAAGD,CAAG,EAC5CpC,CACT,CACA,OAAO,IACT,CAEA,SAAS6B,EACPY,EACAC,EACAjC,EACkB,CAClB,MAAM6B,EAAyB,IAAI7D,EAAiB,KAAa,IAAI,EACrE,IAAI8D,EAAID,EAEJK,EAAuBF,EACvBG,EAAuBF,EAE3B,KAAOC,IAAO,MAAQC,IAAO,MACvBnC,EAAQkC,EAAG,IAAKC,EAAG,GAAG,EAAI,GAC5BL,EAAE,KAAOI,EACTA,EAAKA,EAAG,OAERJ,EAAE,KAAOK,EACTA,EAAKA,EAAG,MAEVL,EAAIA,EAAE,KAGR,OAAII,IAAO,KACTJ,EAAE,KAAOI,EACAC,IAAO,OAChBL,EAAE,KAAOK,GAGJN,EAAK,IACd,CAEA,SAASZ,EACPT,EACAC,EACAtB,EACAC,EACAY,EACA,CACA,GAAIb,GAAQC,EAAO,OAEnB,MAAMgD,EAAQ5B,EAAMrB,EAAOC,GAAU,CAAC,EACtC,IAAIb,EAAIY,EAAO,EACXkD,EAAIjD,EAAQ,EAEhB,OAAa,CACX,GAAGb,UACIyB,EAAQQ,EAAKjC,CAAC,EAAG6D,CAAK,EAAI,GACjC,GAAGC,UACIrC,EAAQQ,EAAK6B,CAAC,EAAGD,CAAK,EAAI,GACjC,GAAI7D,GAAK8D,EAAG,MAEZ,IAAIC,EAAM9B,EAAKjC,CAAC,EAChBiC,EAAKjC,CAAC,EAAIiC,EAAK6B,CAAC,EAChB7B,EAAK6B,CAAC,EAAIC,EAEVA,EAAM7B,EAAOlC,CAAC,EACdkC,EAAOlC,CAAC,EAAIkC,EAAO4B,CAAC,EACpB5B,EAAO4B,CAAC,EAAIC,CACd,CAEArB,EAAKT,EAAMC,EAAQtB,EAAMkD,EAAGrC,CAAO,EACnCiB,EAAKT,EAAMC,EAAQ4B,EAAI,EAAGjD,EAAOY,CAAO,CAC1C"}