class Queue {
  constructor() {
    this.items = [];
    this.head = 0;
  }
 
  enqueue(value) {
    this.items.push(value);
  }
 
  dequeue() {
    if (this.head >= this.items.length) return undefined;
    const value = this.items[this.head];
    this.head++;
    return value;
  }
 
  peek() {
    return this.items[this.head];
  }
 
  size() {
    return this.items.length - this.head;
  }
 
  isEmpty() {
    return this.size() === 0;
  }
}

function runCircularQueue(capacity, operations) {
  const buffer = new Array(capacity);
  let head = 0;
  let tail = 0;
  let size = 0;
  const results = [];
 
  for (const op of operations) {
    if (op[0] === 'enqueue') {
      if (size === capacity) {
        results.push(false);
      } else {
        buffer[tail] = op[1];
        tail = (tail + 1) % capacity;
        size += 1;
        results.push(true);
      }
    } else if (op[0] === 'dequeue') {
      if (size === 0) {
        results.push(null);
      } else {
        const value = buffer[head];
        head = (head + 1) % capacity;
        size -= 1;
        results.push(value);
      }
    }
  }
 
  return results;
}

class Queue {
  constructor() {
    this.items = [];
    this.head = 0;
  }
 
  enqueue(value) {
    this.items.push(value);
  }
 
  dequeue() {
    if (this.head >= this.items.length) return null;
    const value = this.items[this.head];
    this.items[this.head] = undefined;
    this.head++;
    return value;
  }
 
  size() {
    return this.items.length - this.head;
  }
}

class SegmentTree {
  constructor(arr) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    if (this.n > 0) this._build(arr, 1, 0, this.n - 1);
  }
 
  _build(arr, node, start, end) {
    if (start === end) {
      this.tree[node] = arr[start];
      return;
    }
    const mid = Math.floor((start + end) / 2);
    this._build(arr, 2 * node, start, mid);
    this._build(arr, 2 * node + 1, mid + 1, end);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
 
  update(index, value) {
    this._update(1, 0, this.n - 1, index, value);
  }
 
  _update(node, start, end, index, value) {
    if (start === end) {
      this.tree[node] = value;
      return;
    }
    const mid = Math.floor((start + end) / 2);
    if (index <= mid) {
      this._update(2 * node, start, mid, index, value);
    } else {
      this._update(2 * node + 1, mid + 1, end, index, value);
    }
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }
 
  rangeSum(left, right) {
    return this._query(1, 0, this.n - 1, left, right - 1);
  }
 
  _query(node, start, end, l, r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return this.tree[node];
    const mid = Math.floor((start + end) / 2);
    return this._query(2 * node, start, mid, l, r)
         + this._query(2 * node + 1, mid + 1, end, l, r);
  }
}

class Trie {
  constructor() {
    this.root = { children: new Map(), end: false };
  }
 
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, { children: new Map(), end: false });
      }
      node = node.children.get(ch);
    }
    node.end = true;
  }
 
  search(word) {
    const node = this._traverse(word);
    return node !== null && node.end;
  }
 
  startsWith(prefix) {
    return this._traverse(prefix) !== null;
  }
 
  _traverse(s) {
    let node = this.root;
    for (const ch of s) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }
}

class BST {
  constructor() {
    this.root = null;
  }
 
  insert(value) {
    this.root = this._insert(this.root, value);
  }
 
  _insert(node, value) {
    if (node === null) return { val: value, left: null, right: null };
    if (value < node.val) {
      node.left = this._insert(node.left, value);
    } else if (value > node.val) {
      node.right = this._insert(node.right, value);
    }
    return node;
  }
 
  contains(value) {
    let node = this.root;
    while (node !== null) {
      if (value === node.val) return true;
      node = value < node.val ? node.left : node.right;
    }
    return false;
  }
 
  inorder() {
    const result = [];
    function walk(node) {
      if (node === null) return;
      walk(node.left);
      result.push(node.val);
      walk(node.right);
    }
    walk(this.root);
    return result;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // key -> node
 
    // Dummy sentinel nodes
    this.head = { key: null, val: null, prev: null, next: null };
    this.tail = { key: null, val: null, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
 
  _removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
 
  _addToFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }
 
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._removeNode(node);
    this._addToFront(node);
    return node.val;
  }
 
  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.val = value;
      this._removeNode(node);
      this._addToFront(node);
    } else {
      if (this.map.size >= this.capacity) {
        const lru = this.tail.prev;
        this._removeNode(lru);
        this.map.delete(lru.key);
      }
      const node = { key, val: value, prev: null, next: null };
      this._addToFront(node);
      this.map.set(key, node);
    }
  }
}

class MedianFinder {
  constructor() {
    this.low = new MaxHeap();
    this.high = new MinHeap();
  }
 
  addNum(num) {
    if (this.low.size() === 0 || num <= this.low.peek()) {
      this.low.push(num);
    } else {
      this.high.push(num);
    }
    if (this.low.size() > this.high.size() + 1) {
      this.high.push(this.low.pop());
    } else if (this.high.size() > this.low.size()) {
      this.low.push(this.high.pop());
    }
  }
 
  findMedian() {
    if (this.low.size() > this.high.size()) {
      return this.low.peek();
    }
    return (this.low.peek() + this.high.peek()) / 2;
  }
}
 
class MaxHeap {
  constructor() { this.data = []; }
  size() { return this.data.length; }
  peek() { return this.data[0]; }
  push(value) {
    this.data.push(value);
    this._siftUp(this.data.length - 1);
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this._siftDown(0);
    }
    return top;
  }
  _siftUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.data[parent] < this.data[i]) {
        [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
        i = parent;
      } else break;
    }
  }
  _siftDown(i) {
    const n = this.data.length;
    while (true) {
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      let largest = i;
      if (left < n && this.data[left] > this.data[largest]) largest = left;
      if (right < n && this.data[right] > this.data[largest]) largest = right;
      if (largest === i) break;
      [this.data[i], this.data[largest]] = [this.data[largest], this.data[i]];
      i = largest;
    }
  }
}
 
class MinHeap {
  constructor() { this.data = []; }
  size() { return this.data.length; }
  peek() { return this.data[0]; }
  push(value) {
    this.data.push(value);
    this._siftUp(this.data.length - 1);
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this._siftDown(0);
    }
    return top;
  }
  _siftUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.data[parent] > this.data[i]) {
        [this.data[parent], this.data[i]] = [this.data[i], this.data[parent]];
        i = parent;
      } else break;
    }
  }
  _siftDown(i) {
    const n = this.data.length;
    while (true) {
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      let smallest = i;
      if (left < n && this.data[left] < this.data[smallest]) smallest = left;
      if (right < n && this.data[right] < this.data[smallest]) smallest = right;
      if (smallest === i) break;
      [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
      i = smallest;
    }
  }
}

class Card {
  get cardValue() {
    throw new Error('Not implemented');
  }
}
 
class PlayingCard extends Card {
  static VALUES = {
    'A': 1, '2': 2, '3': 3, '4': 4, '5': 5,
    '6': 6, '7': 7, '8': 8, '9': 9, '10': 10,
    'J': 11, 'Q': 12, 'K': 13,
  };
 
  static VALUE_NAMES = Object.fromEntries(
    Object.entries(PlayingCard.VALUES).map(([k, v]) => [v, k])
  );
 
  constructor(suit, value) {
    super();
    this.suit = suit;
    this._value = PlayingCard.VALUES[value];
  }
 
  get cardValue() {
    return this._value;
  }
 
  toString() {
    return `${PlayingCard.VALUE_NAMES[this._value]} of ${this.suit}`;
  }
}
 
class Joker extends Card {
  constructor(color) {
    super();
    this.color = color;
  }
 
  get cardValue() {
    return 14;
  }
 
  toString() {
    return `${this.color} Joker`;
  }
}
 
class Hand {
  constructor(cards) {
    this.cards = [...cards];
  }
 
  toString() {
    return this.cards.map(c => c.toString()).join(', ');
  }
 
  compareTo(other) {
    const a = [...this.cards].sort((x, y) => y.cardValue - x.cardValue);
    const b = [...other.cards].sort((x, y) => y.cardValue - x.cardValue);
    for (let i = 0; i < Math.min(a.length, b.length); i++) {
      const diff = a[i].cardValue - b[i].cardValue;
      if (diff !== 0) return diff;
    }
    return 0;
  }
}
 
class Game {
  constructor() {
    this.cards = [];
    this.hands = [];
  }
 
  addCard(suit, value) {
    this.cards.push(new PlayingCard(suit, value));
  }
 
  addJoker(color) {
    this.cards.push(new Joker(color));
  }
 
  cardString(i) {
    return this.cards[i].toString();
  }
 
  cardBeats(a, b) {
    return this.cards[a].cardValue > this.cards[b].cardValue;
  }
 
  addHand(cardIndices) {
    this.hands.push(new Hand(cardIndices.map(i => this.cards[i])));
  }
 
  handString(i) {
    return this.hands[i].toString();
  }
 
  handBeats(a, b) {
    return this.hands[a].compareTo(this.hands[b]) > 0;
  }
}

class NumArray {
  constructor(nums) {
    this.prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i];
    }
  }
 
  sumRange(left, right) {
    return this.prefix[right + 1] - this.prefix[left];
  }
}