Algorithmic Templates

    
  

  


  


  


  

int lowerBound(int[] values, int target) {
    int left = 0;
    int right = values.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (values[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}
def lower_bound(values: list[int], target: int) -> int:
    left, right = 0, len(values)
    while left < right:
        mid = left + (right - left) // 2
        if values[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left
def lowerBound(values: Array[Int], target: Int): Int =
  var left = 0
  var right = values.length
  while left < right do
    val mid = left + (right - left) / 2
    if values(mid) < target then left = mid + 1
    else right = mid
  left
int lowerBound(const std::vector<int>& values, int target) {
    int left = 0, right = values.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (values[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

    
  

  


  


  


  

int searchRotated(int[] values, int target) {
    int left = 0;
    int right = values.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (values[mid] == target) return mid;
        if (values[left] <= values[mid]) {
            if (values[left] <= target && target < values[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (values[mid] < target && target <= values[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}
def search_rotated(values: list[int], target: int) -> int:
    left, right = 0, len(values) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if values[mid] == target:
            return mid
        if values[left] <= values[mid]:
            if values[left] <= target < values[mid]:
                right = mid - 1
            else:
                left = mid + 1
        elif values[mid] < target <= values[right]:
            left = mid + 1
        else:
            right = mid - 1
    return -1
def searchRotated(values: Array[Int], target: Int): Int =
  var left = 0
  var right = values.length - 1
  while left <= right do
    val mid = left + (right - left) / 2
    if values(mid) == target then return mid
    if values(left) <= values(mid) then
      if values(left) <= target && target < values(mid) then right = mid - 1
      else left = mid + 1
    else if values(mid) < target && target <= values(right) then left = mid + 1
    else right = mid - 1
  -1
int searchRotated(const std::vector<int>& values, int target) {
    int left = 0, right = static_cast<int>(values.size()) - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (values[mid] == target) return mid;
        if (values[left] <= values[mid]) {
            if (values[left] <= target && target < values[mid]) right = mid - 1;
            else left = mid + 1;
        } else if (values[mid] < target && target <= values[right]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

    
  

  


  


  


  

int firstFeasible(int low, int high) {
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (feasible(mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}
def first_feasible(low: int, high: int) -> int:
    while low < high:
        mid = low + (high - low) // 2
        if feasible(mid):
            high = mid
        else:
            low = mid + 1
    return low
def firstFeasible(low0: Int, high0: Int): Int =
  var low = low0
  var high = high0
  while low < high do
    val mid = low + (high - low) / 2
    if feasible(mid) then high = mid
    else low = mid + 1
  low
int firstFeasible(int low, int high) {
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (feasible(mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}

    
  

  


  


  


  

void scanInward(int[] values) {
    int left = 0;
    int right = values.length - 1;
    while (left < right) {
        use(values[left], values[right]);
        if (moveLeft(values[left], values[right])) left++;
        else right--;
    }
}
def scan_inward(values: list[int]) -> None:
    left, right = 0, len(values) - 1
    while left < right:
        use(values[left], values[right])
        if move_left(values[left], values[right]):
            left += 1
        else:
            right -= 1
def scanInward(values: Array[Int]): Unit =
  var left = 0
  var right = values.length - 1
  while left < right do
    use(values(left), values(right))
    if moveLeft(values(left), values(right)) then left += 1
    else right -= 1
void scanInward(const std::vector<int>& values) {
    int left = 0, right = static_cast<int>(values.size()) - 1;
    while (left < right) {
        use(values[left], values[right]);
        if (moveLeft(values[left], values[right])) left++;
        else right--;
    }
}

    
  

  


  


  


  

int compact(int[] values) {
    int write = 0;
    for (int read = 0; read < values.length; read++) {
        if (keep(values[read])) values[write++] = transform(values[read]);
    }
    return write;
}
def compact(values: list[int]) -> int:
    write = 0
    for read, value in enumerate(values):
        if keep(value):
            values[write] = transform(value)
            write += 1
    return write
def compact(values: Array[Int]): Int =
  var write = 0
  for read <- values.indices do
    if keep(values(read)) then
      values(write) = transform(values(read))
      write += 1
  write
int compact(std::vector<int>& values) {
    int write = 0;
    for (int read = 0; read < values.size(); read++) {
        if (keep(values[read])) values[write++] = transform(values[read]);
    }
    return write;
}

    
  

  


  


  


  

int scanFixedWindow(int[] values, int width) {
    int window = 0;
    for (int i = 0; i < width; i++) window += values[i];
    int best = score(window);
    for (int right = width; right < values.length; right++) {
        window += values[right] - values[right - width];
        best = combine(best, score(window));
    }
    return best;
}
def scan_fixed_window(values: list[int], width: int) -> int:
    window = sum(values[:width])
    best = score(window)
    for right in range(width, len(values)):
        window += values[right] - values[right - width]
        best = combine(best, score(window))
    return best
def scanFixedWindow(values: Array[Int], width: Int): Int =
  var window = values.take(width).sum
  var best = score(window)
  for right <- width until values.length do
    window += values(right) - values(right - width)
    best = combine(best, score(window))
  best
int scanFixedWindow(const std::vector<int>& values, int width) {
    int window = 0;
    for (int i = 0; i < width; i++) window += values[i];
    int best = score(window);
    for (int right = width; right < values.size(); right++) {
        window += values[right] - values[right - width];
        best = combine(best, score(window));
    }
    return best;
}

    
  

  


  


  


  

int longestWindow(int[] values) {
    int best = 0;
    for (int left = 0, right = 0; right < values.length; right++) {
        add(values[right]);
        while (!valid()) remove(values[left++]);
        best = Math.max(best, right - left + 1);
    }
    return best;
}
def longest_window(values: list[int]) -> int:
    left = best = 0
    for right, value in enumerate(values):
        add(value)
        while not valid():
            remove(values[left])
            left += 1
        best = max(best, right - left + 1)
    return best
def longestWindow(values: Array[Int]): Int =
  var left = 0
  var best = 0
  for right <- values.indices do
    add(values(right))
    while !valid() do
      remove(values(left))
      left += 1
    best = best.max(right - left + 1)
  best
int longestWindow(const std::vector<int>& values) {
    int left = 0, best = 0;
    for (int right = 0; right < values.size(); right++) {
        add(values[right]);
        while (!valid()) remove(values[left++]);
        best = std::max(best, right - left + 1);
    }
    return best;
}

    
  

  


  


  


  

int shortestWindow(int[] values) {
    int best = values.length + 1;
    for (int left = 0, right = 0; right < values.length; right++) {
        add(values[right]);
        while (valid()) {
            best = Math.min(best, right - left + 1);
            remove(values[left++]);
        }
    }
    return best == values.length + 1 ? 0 : best;
}
def shortest_window(values: list[int]) -> int:
    left = 0
    best = len(values) + 1
    for right, value in enumerate(values):
        add(value)
        while valid():
            best = min(best, right - left + 1)
            remove(values[left])
            left += 1
    return 0 if best == len(values) + 1 else best
def shortestWindow(values: Array[Int]): Int =
  var left = 0
  var best = values.length + 1
  for right <- values.indices do
    add(values(right))
    while valid() do
      best = best.min(right - left + 1)
      remove(values(left))
      left += 1
  if best == values.length + 1 then 0 else best
int shortestWindow(const std::vector<int>& values) {
    int left = 0, best = static_cast<int>(values.size()) + 1;
    for (int right = 0; right < values.size(); right++) {
        add(values[right]);
        while (valid()) {
            best = std::min(best, right - left + 1);
            remove(values[left++]);
        }
    }
    return best == values.size() + 1 ? 0 : best;
}

    
  

  


  


  


  

int[] prefixSums(int[] values) {
    int[] prefix = new int[values.length + 1];
    for (int i = 0; i < values.length; i++) {
        prefix[i + 1] = prefix[i] + values[i];
    }
    return prefix;
}

int rangeSum(int[] prefix, int left, int right) {
    return prefix[right] - prefix[left];
}
def prefix_sums(values: list[int]) -> list[int]:
    prefix = [0]
    for value in values:
        prefix.append(prefix[-1] + value)
    return prefix

def range_sum(prefix: list[int], left: int, right: int) -> int:
    return prefix[right] - prefix[left]
def prefixSums(values: Array[Int]): Array[Int] =
  val prefix = Array.fill(values.length + 1)(0)
  for i <- values.indices do prefix(i + 1) = prefix(i) + values(i)
  prefix

def rangeSum(prefix: Array[Int], left: Int, right: Int): Int =
  prefix(right) - prefix(left)
std::vector<int> prefixSums(const std::vector<int>& values) {
    std::vector<int> prefix(values.size() + 1);
    for (int i = 0; i < values.size(); i++) {
        prefix[i + 1] = prefix[i] + values[i];
    }
    return prefix;
}

int rangeSum(const std::vector<int>& prefix, int left, int right) {
    return prefix[right] - prefix[left];
}

    
  

  


  


  


  

int[] applyRangeUpdates(int size, int[][] updates) {
    int[] diff = new int[size + 1];
    for (int[] update : updates) {
        diff[update[0]] += update[2];
        diff[update[1] + 1] -= update[2];
    }
    int[] values = new int[size];
    for (int i = 0, running = 0; i < size; i++) {
        running += diff[i];
        values[i] = running;
    }
    return values;
}
def apply_range_updates(size: int, updates: list[tuple[int, int, int]]) -> list[int]:
    diff = [0] * (size + 1)
    for left, right, delta in updates:
        diff[left] += delta
        diff[right + 1] -= delta
    values, running = [0] * size, 0
    for i in range(size):
        running += diff[i]
        values[i] = running
    return values
def applyRangeUpdates(size: Int, updates: Array[Array[Int]]): Array[Int] =
  val diff = Array.fill(size + 1)(0)
  for update <- updates do
    diff(update(0)) += update(2)
    diff(update(1) + 1) -= update(2)
  val values = Array.fill(size)(0)
  var running = 0
  for i <- 0 until size do
    running += diff(i)
    values(i) = running
  values
std::vector<int> applyRangeUpdates(int size, const std::vector<std::array<int, 3>>& updates) {
    std::vector<int> diff(size + 1);
    for (auto [left, right, delta] : updates) {
        diff[left] += delta;
        diff[right + 1] -= delta;
    }
    std::vector<int> values(size);
    for (int i = 0, running = 0; i < size; i++) {
        running += diff[i];
        values[i] = running;
    }
    return values;
}

    
  

  


  


  


  

int bestSubarray(int[] values) {
    int best = values[0];
    int current = values[0];
    for (int i = 1; i < values.length; i++) {
        current = Math.max(values[i], current + values[i]);
        best = Math.max(best, current);
    }
    return best;
}
def best_subarray(values: list[int]) -> int:
    best = current = values[0]
    for value in values[1:]:
        current = max(value, current + value)
        best = max(best, current)
    return best
def bestSubarray(values: Array[Int]): Int =
  var current = values(0)
  var best = values(0)
  for value <- values.drop(1) do
    current = value.max(current + value)
    best = best.max(current)
  best
int bestSubarray(const std::vector<int>& values) {
    int current = values[0], best = values[0];
    for (int i = 1; i < values.size(); i++) {
        current = std::max(values[i], current + values[i]);
        best = std::max(best, current);
    }
    return best;
}

    
  

  


  


  


  

void dfs(TreeNode node) {
    if (node == null) return;
    visit(node);
    dfs(node.left);
    dfs(node.right);
}
def dfs(node) -> None:
    if not node:
        return
    visit(node)
    dfs(node.left)
    dfs(node.right)
def dfs(node: TreeNode): Unit =
  if node != null then
    visit(node)
    dfs(node.left)
    dfs(node.right)
void dfs(TreeNode* node) {
    if (node == nullptr) return;
    visit(node);
    dfs(node->left);
    dfs(node->right);
}

    
  

  


  


  


  

void bfs(TreeNode root) {
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    if (root != null) queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.remove();
        visit(node);
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}
def bfs(root) -> None:
    queue = deque([root] if root else [])
    while queue:
        node = queue.popleft()
        visit(node)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
def bfs(root: TreeNode): Unit =
  val queue = scala.collection.mutable.Queue[TreeNode]()
  if root != null then queue.enqueue(root)
  while queue.nonEmpty do
    val node = queue.dequeue()
    visit(node)
    if node.left != null then queue.enqueue(node.left)
    if node.right != null then queue.enqueue(node.right)
void bfs(TreeNode* root) {
    std::queue<TreeNode*> queue;
    if (root != nullptr) queue.push(root);
    while (!queue.empty()) {
        TreeNode* node = queue.front();
        queue.pop();
        visit(node);
        if (node->left != nullptr) queue.push(node->left);
        if (node->right != nullptr) queue.push(node->right);
    }
}

    
  

  


  


  


  

boolean contains(TreeNode node, int target) {
    while (node != null) {
        if (node.value == target) return true;
        node = target < node.value ? node.left : node.right;
    }
    return false;
}
def contains(node, target: int) -> bool:
    while node:
        if node.value == target:
            return True
        node = node.left if target < node.value else node.right
    return False
def contains(node0: TreeNode, target: Int): Boolean =
  var node = node0
  while node != null do
    if node.value == target then return true
    node = if target < node.value then node.left else node.right
  false
bool contains(TreeNode* node, int target) {
    while (node != nullptr) {
        if (node->value == target) return true;
        node = target < node->value ? node->left : node->right;
    }
    return false;
}

    
  

  


  


  


  

void serialize(TreeNode node, List<String> out) {
    if (node == null) {
        out.add("#");
        return;
    }
    out.add(String.valueOf(node.value));
    serialize(node.left, out);
    serialize(node.right, out);
}
def serialize(node, out: list[str]) -> None:
    if not node:
        out.append("#")
        return
    out.append(str(node.value))
    serialize(node.left, out)
    serialize(node.right, out)
def serialize(node: TreeNode, out: scala.collection.mutable.Buffer[String]): Unit =
  if node == null then out += "#"
  else
    out += node.value.toString
    serialize(node.left, out)
    serialize(node.right, out)
void serialize(TreeNode* node, std::vector<std::string>& out) {
    if (node == nullptr) {
        out.push_back("#");
        return;
    }
    out.push_back(std::to_string(node->value));
    serialize(node->left, out);
    serialize(node->right, out);
}

    
  

  


  


  


  

void dfs(int node, List<List<Integer>> graph, boolean[] seen) {
    seen[node] = true;
    visit(node);
    for (int next : graph.get(node)) {
        if (!seen[next]) dfs(next, graph, seen);
    }
}
def dfs(node: int, graph: list[list[int]], seen: list[bool]) -> None:
    seen[node] = True
    visit(node)
    for nxt in graph[node]:
        if not seen[nxt]:
            dfs(nxt, graph, seen)
def dfs(node: Int, graph: Vector[Vector[Int]], seen: Array[Boolean]): Unit =
  seen(node) = true
  visit(node)
  for next <- graph(node) do
    if !seen(next) then dfs(next, graph, seen)
void dfs(int node, const std::vector<std::vector<int>>& graph, std::vector<bool>& seen) {
    seen[node] = true;
    visit(node);
    for (int next : graph[node]) {
        if (!seen[next]) dfs(next, graph, seen);
    }
}

    
  

  


  


  


  

int[] distances(List<List<Integer>> graph, int start) {
    int[] dist = new int[graph.size()];
    Arrays.fill(dist, -1);
    ArrayDeque<Integer> queue = new ArrayDeque<>();
    dist[start] = 0;
    queue.add(start);
    while (!queue.isEmpty()) {
        int node = queue.remove();
        for (int next : graph.get(node)) if (dist[next] == -1) {
            dist[next] = dist[node] + 1;
            queue.add(next);
        }
    }
    return dist;
}
def distances(graph: list[list[int]], start: int) -> list[int]:
    dist = [-1] * len(graph)
    dist[start] = 0
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if dist[nxt] == -1:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist
def distances(graph: Vector[Vector[Int]], start: Int): Array[Int] =
  val dist = Array.fill(graph.length)(-1)
  val queue = scala.collection.mutable.Queue(start)
  dist(start) = 0
  while queue.nonEmpty do
    val node = queue.dequeue()
    for next <- graph(node) do
      if dist(next) == -1 then
        dist(next) = dist(node) + 1
        queue.enqueue(next)
  dist
std::vector<int> distances(const std::vector<std::vector<int>>& graph, int start) {
    std::vector<int> dist(graph.size(), -1);
    std::queue<int> queue;
    dist[start] = 0;
    queue.push(start);
    while (!queue.empty()) {
        int node = queue.front();
        queue.pop();
        for (int next : graph[node]) if (dist[next] == -1) {
            dist[next] = dist[node] + 1;
            queue.push(next);
        }
    }
    return dist;
}

    
  

  


  


  


  

List<Integer> topologicalOrder(List<List<Integer>> graph) {
    int[] indegree = new int[graph.size()];
    for (List<Integer> edges : graph) for (int next : edges) indegree[next]++;
    ArrayDeque<Integer> queue = new ArrayDeque<>();
    for (int node = 0; node < graph.size(); node++) if (indegree[node] == 0) queue.add(node);
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.remove();
        order.add(node);
        for (int next : graph.get(node)) if (--indegree[next] == 0) queue.add(next);
    }
    return order;
}
def topological_order(graph: list[list[int]]) -> list[int]:
    indegree = [0] * len(graph)
    for edges in graph:
        for nxt in edges:
            indegree[nxt] += 1
    queue = deque(node for node, degree in enumerate(indegree) if degree == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order
def topologicalOrder(graph: Vector[Vector[Int]]): Vector[Int] =
  val indegree = Array.fill(graph.length)(0)
  for edges <- graph; next <- edges do indegree(next) += 1
  val queue = scala.collection.mutable.Queue[Int]()
  for node <- graph.indices do if indegree(node) == 0 then queue.enqueue(node)
  val order = scala.collection.mutable.Buffer[Int]()
  while queue.nonEmpty do
    val node = queue.dequeue()
    order += node
    for next <- graph(node) do
      indegree(next) -= 1
      if indegree(next) == 0 then queue.enqueue(next)
  order.toVector
std::vector<int> topologicalOrder(const std::vector<std::vector<int>>& graph) {
    std::vector<int> indegree(graph.size());
    for (const auto& edges : graph) for (int next : edges) indegree[next]++;
    std::queue<int> queue;
    for (int node = 0; node < graph.size(); node++) if (indegree[node] == 0) queue.push(node);
    std::vector<int> order;
    while (!queue.empty()) {
        int node = queue.front();
        queue.pop();
        order.push_back(node);
        for (int next : graph[node]) if (--indegree[next] == 0) queue.push(next);
    }
    return order;
}

    
  

  


  


  


  

class UnionFind {
    int[] parent;
    int[] size;

    UnionFind(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int node) {
        if (parent[node] != node) parent[node] = find(parent[node]);
        return parent[node];
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }
}
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, node: int) -> int:
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True
final class UnionFind(n: Int):
  private val parent = Array.tabulate(n)(identity)
  private val size = Array.fill(n)(1)

  def find(node: Int): Int =
    if parent(node) != node then parent(node) = find(parent(node))
    parent(node)

  def union(a: Int, b: Int): Boolean =
    var ra = find(a)
    var rb = find(b)
    if ra == rb then false
    else
      if size(ra) < size(rb) then
        val t = ra
        ra = rb
        rb = t
      parent(rb) = ra
      size(ra) += size(rb)
      true
class UnionFind {
    std::vector<int> parent;
    std::vector<int> size;

public:
    explicit UnionFind(int n) : parent(n), size(n, 1) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    int find(int node) {
        if (parent[node] != node) parent[node] = find(parent[node]);
        return parent[node];
    }

    bool unite(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) std::swap(ra, rb);
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }
};

    
  

  


  


  


  

int[] dijkstra(List<List<Edge>> graph, int source) {
    int[] dist = new int[graph.size()];
    Arrays.fill(dist, INF);
    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    dist[source] = 0;
    heap.add(new int[] {source, 0});
    while (!heap.isEmpty()) {
        int[] state = heap.remove();
        if (state[1] != dist[state[0]]) continue;
        for (Edge edge : graph.get(state[0])) if (state[1] + edge.weight < dist[edge.to]) {
            dist[edge.to] = state[1] + edge.weight;
            heap.add(new int[] {edge.to, dist[edge.to]});
        }
    }
    return dist;
}
def dijkstra(graph, source: int) -> list[int]:
    dist = [INF] * len(graph)
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        cost, node = heappop(heap)
        if cost != dist[node]:
            continue
        for nxt, weight in graph[node]:
            if cost + weight < dist[nxt]:
                dist[nxt] = cost + weight
                heappush(heap, (dist[nxt], nxt))
    return dist
def dijkstra(graph: Vector[Vector[Edge]], source: Int): Array[Int] =
  val dist = Array.fill(graph.length)(INF)
  val heap = scala.collection.mutable.PriorityQueue[(Int, Int)]()(Ordering.by(-_._1))
  dist(source) = 0
  heap.enqueue((0, source))
  while heap.nonEmpty do
    val (cost, node) = heap.dequeue()
    if cost == dist(node) then
      for edge <- graph(node) do
        if cost + edge.weight < dist(edge.to) then
          dist(edge.to) = cost + edge.weight
          heap.enqueue((dist(edge.to), edge.to))
  dist
std::vector<int> dijkstra(const std::vector<std::vector<Edge>>& graph, int source) {
    std::vector<int> dist(graph.size(), INF);
    std::priority_queue<State, std::vector<State>, std::greater<State>> heap;
    dist[source] = 0;
    heap.push({0, source});
    while (!heap.empty()) {
        auto [cost, node] = heap.top();
        heap.pop();
        if (cost != dist[node]) continue;
        for (const Edge& edge : graph[node]) if (cost + edge.weight < dist[edge.to]) {
            dist[edge.to] = cost + edge.weight;
            heap.push({dist[edge.to], edge.to});
        }
    }
    return dist;
}

    
  

  


  


  


  

int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, Comparator.comparingInt(edge -> edge[2]));
    UnionFind uf = new UnionFind(n);
    int cost = 0;
    for (int[] edge : edges) {
        if (uf.union(edge[0], edge[1])) cost += edge[2];
    }
    return cost;
}
def kruskal(n: int, edges: list[tuple[int, int, int]]) -> int:
    uf = UnionFind(n)
    cost = 0
    for a, b, weight in sorted(edges, key=lambda edge: edge[2]):
        if uf.union(a, b):
            cost += weight
    return cost
def kruskal(n: Int, edges: Array[Array[Int]]): Int =
  val uf = new UnionFind(n)
  var cost = 0
  for edge <- edges.sortBy(_(2)) do
    if uf.union(edge(0), edge(1)) then cost += edge(2)
  cost
int kruskal(int n, std::vector<Edge>& edges) {
    std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });
    UnionFind uf(n);
    int cost = 0;
    for (const Edge& edge : edges) {
        if (uf.unite(edge.a, edge.b)) cost += edge.weight;
    }
    return cost;
}

    
  

  


  


  


  

void bfs(int[][] grid, int row, int col) {
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    ArrayDeque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[] {row, col});
    mark(row, col);
    while (!queue.isEmpty()) {
        int[] cell = queue.remove();
        visit(cell[0], cell[1]);
        for (int[] dir : dirs) {
            int nr = cell[0] + dir[0], nc = cell[1] + dir[1];
            if (inside(grid, nr, nc) && unvisited(nr, nc)) {
                mark(nr, nc);
                queue.add(new int[] {nr, nc});
            }
        }
    }
}
def bfs(grid, row: int, col: int) -> None:
    queue = deque([(row, col)])
    mark(row, col)
    while queue:
        r, c = queue.popleft()
        visit(r, c)
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if inside(grid, nr, nc) and unvisited(nr, nc):
                mark(nr, nc)
                queue.append((nr, nc))
def bfs(grid: Array[Array[Int]], row: Int, col: Int): Unit =
  val dirs = Array((1, 0), (-1, 0), (0, 1), (0, -1))
  val queue = scala.collection.mutable.Queue((row, col))
  mark(row, col)
  while queue.nonEmpty do
    val (r, c) = queue.dequeue()
    visit(r, c)
    for (dr, dc) <- dirs do
      val nr = r + dr
      val nc = c + dc
      if inside(grid, nr, nc) && unvisited(nr, nc) then
        mark(nr, nc)
        queue.enqueue((nr, nc))
void bfs(const std::vector<std::vector<int>>& grid, int row, int col) {
    std::vector<std::pair<int, int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    std::queue<std::pair<int, int>> queue;
    queue.push({row, col});
    mark(row, col);
    while (!queue.empty()) {
        auto [r, c] = queue.front();
        queue.pop();
        visit(r, c);
        for (auto [dr, dc] : dirs) {
            int nr = r + dr, nc = c + dc;
            if (inside(grid, nr, nc) && unvisited(nr, nc)) {
                mark(nr, nc);
                queue.push({nr, nc});
            }
        }
    }
}

    
  

  


  


  


  

void dfs(int[][] grid, int row, int col) {
    if (!inside(grid, row, col) || seen(row, col)) return;
    mark(row, col);
    visit(row, col);
    dfs(grid, row + 1, col);
    dfs(grid, row - 1, col);
    dfs(grid, row, col + 1);
    dfs(grid, row, col - 1);
}
def dfs(grid, row: int, col: int) -> None:
    if not inside(grid, row, col) or seen(row, col):
        return
    mark(row, col)
    visit(row, col)
    dfs(grid, row + 1, col)
    dfs(grid, row - 1, col)
    dfs(grid, row, col + 1)
    dfs(grid, row, col - 1)
def dfs(grid: Array[Array[Int]], row: Int, col: Int): Unit =
  if inside(grid, row, col) && !seen(row, col) then
    mark(row, col)
    visit(row, col)
    dfs(grid, row + 1, col)
    dfs(grid, row - 1, col)
    dfs(grid, row, col + 1)
    dfs(grid, row, col - 1)
void dfs(const std::vector<std::vector<int>>& grid, int row, int col) {
    if (!inside(grid, row, col) || seen(row, col)) return;
    mark(row, col);
    visit(row, col);
    dfs(grid, row + 1, col);
    dfs(grid, row - 1, col);
    dfs(grid, row, col + 1);
    dfs(grid, row, col - 1);
}

    
  

  


  


  


  

void scanDirections(int[][] grid, int row, int col) {
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int[] dir : dirs) {
        int r = row + dir[0];
        int c = col + dir[1];
        while (inside(grid, r, c)) {
            visit(r, c);
            r += dir[0];
            c += dir[1];
        }
    }
}
def scan_directions(grid, row: int, col: int) -> None:
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        r, c = row + dr, col + dc
        while inside(grid, r, c):
            visit(r, c)
            r += dr
            c += dc
def scanDirections(grid: Array[Array[Int]], row: Int, col: Int): Unit =
  for (dr, dc) <- Array((1, 0), (-1, 0), (0, 1), (0, -1)) do
    var r = row + dr
    var c = col + dc
    while inside(grid, r, c) do
      visit(r, c)
      r += dr
      c += dc
void scanDirections(const std::vector<std::vector<int>>& grid, int row, int col) {
    std::vector<std::pair<int, int>> dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (auto [dr, dc] : dirs) {
        int r = row + dr, c = col + dc;
        while (inside(grid, r, c)) {
            visit(r, c);
            r += dr;
            c += dc;
        }
    }
}

    
  

  


  


  


  

void search(State state, List<Choice> path, List<List<Choice>> answer) {
    if (complete(state)) {
        answer.add(new ArrayList<>(path));
        return;
    }
    for (Choice choice : choices(state)) {
        if (!valid(state, choice)) continue;
        apply(state, choice);
        path.add(choice);
        search(state, path, answer);
        path.remove(path.size() - 1);
        undo(state, choice);
    }
}
def search(state, path, answer) -> None:
    if complete(state):
        answer.append(path.copy())
        return
    for choice in choices(state):
        if not valid(state, choice):
            continue
        apply(state, choice)
        path.append(choice)
        search(state, path, answer)
        path.pop()
        undo(state, choice)
def search(state: State, path: List[Choice], answer: scala.collection.mutable.Buffer[List[Choice]]): Unit =
  if complete(state) then answer += path
  else
    for choice <- choices(state) do
      if valid(state, choice) then
        applyChoice(state, choice)
        search(state, path :+ choice, answer)
        undoChoice(state, choice)
void search(State& state, std::vector<Choice>& path, std::vector<std::vector<Choice>>& answer) {
    if (complete(state)) {
        answer.push_back(path);
        return;
    }
    for (const Choice& choice : choices(state)) {
        if (!valid(state, choice)) continue;
        apply(state, choice);
        path.push_back(choice);
        search(state, path, answer);
        path.pop_back();
        undo(state, choice);
    }
}

    
  

  


  


  


  

int search(State state) {
    if (complete(state)) return value(state);
    int answer = identity();
    for (Choice choice : choices(state)) {
        if (!valid(state, choice)) continue;
        apply(state, choice);
        answer = combine(answer, search(state));
        undo(state, choice);
    }
    return answer;
}
def search(state) -> int:
    if complete(state):
        return value(state)
    answer = identity()
    for choice in choices(state):
        if not valid(state, choice):
            continue
        apply(state, choice)
        answer = combine(answer, search(state))
        undo(state, choice)
    return answer
def search(state: State): Int =
  if complete(state) then value(state)
  else
    var answer = identity()
    for choice <- choices(state) do
      if valid(state, choice) then
        applyChoice(state, choice)
        answer = combine(answer, search(state))
        undoChoice(state, choice)
    answer
int search(State& state) {
    if (complete(state)) return value(state);
    int answer = identity();
    for (const Choice& choice : choices(state)) {
        if (!valid(state, choice)) continue;
        apply(state, choice);
        answer = combine(answer, search(state));
        undo(state, choice);
    }
    return answer;
}

    
  

  


  


  


  

int linearDp(int n) {
    int[] dp = new int[n + 1];
    dp[0] = base();
    for (int i = 1; i <= n; i++) {
        dp[i] = transition(i, dp);
    }
    return dp[n];
}
def linear_dp(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = base()
    for i in range(1, n + 1):
        dp[i] = transition(i, dp)
    return dp[n]
def linearDp(n: Int): Int =
  val dp = Array.fill(n + 1)(0)
  dp(0) = base()
  for i <- 1 to n do dp(i) = transition(i, dp)
  dp(n)
int linearDp(int n) {
    std::vector<int> dp(n + 1);
    dp[0] = base();
    for (int i = 1; i <= n; i++) {
        dp[i] = transition(i, dp);
    }
    return dp[n];
}

    
  

  


  


  


  

int gridDp(int rows, int cols) {
    int[][] dp = new int[rows][cols];
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            dp[r][c] = transition(r, c, dp);
        }
    }
    return dp[rows - 1][cols - 1];
}
def grid_dp(rows: int, cols: int) -> int:
    dp = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            dp[r][c] = transition(r, c, dp)
    return dp[rows - 1][cols - 1]
def gridDp(rows: Int, cols: Int): Int =
  val dp = Array.fill(rows, cols)(0)
  for r <- 0 until rows do
    for c <- 0 until cols do
      dp(r)(c) = transition(r, c, dp)
  dp(rows - 1)(cols - 1)
int gridDp(int rows, int cols) {
    std::vector<std::vector<int>> dp(rows, std::vector<int>(cols));
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            dp[r][c] = transition(r, c, dp);
        }
    }
    return dp[rows - 1][cols - 1];
}

    
  

  


  


  


  

int twoSequenceDp(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            dp[i][j] = transition(a, b, i, j, dp);
        }
    }
    return dp[a.length()][b.length()];
}
def two_sequence_dp(a: str, b: str) -> int:
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            dp[i][j] = transition(a, b, i, j, dp)
    return dp[len(a)][len(b)]
def twoSequenceDp(a: String, b: String): Int =
  val dp = Array.fill(a.length + 1, b.length + 1)(0)
  for i <- 1 to a.length do
    for j <- 1 to b.length do
      dp(i)(j) = transition(a, b, i, j, dp)
  dp(a.length)(b.length)
int twoSequenceDp(const std::string& a, const std::string& b) {
    std::vector<std::vector<int>> dp(a.size() + 1, std::vector<int>(b.size() + 1));
    for (int i = 1; i <= a.size(); i++) {
        for (int j = 1; j <= b.size(); j++) {
            dp[i][j] = transition(a, b, i, j, dp);
        }
    }
    return dp[a.size()][b.size()];
}

    
  

  


  


  


  

int knapsackDp(int[] weight, int[] value, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int item = 0; item < weight.length; item++) {
        for (int cap = capacity; cap >= weight[item]; cap--) {
            dp[cap] = Math.max(dp[cap], dp[cap - weight[item]] + value[item]);
        }
    }
    return dp[capacity];
}
def knapsack_dp(weight: list[int], value: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for w, v in zip(weight, value):
        for cap in range(capacity, w - 1, -1):
            dp[cap] = max(dp[cap], dp[cap - w] + v)
    return dp[capacity]
def knapsackDp(weight: Array[Int], value: Array[Int], capacity: Int): Int =
  val dp = Array.fill(capacity + 1)(0)
  for item <- weight.indices do
    for cap <- capacity to weight(item) by -1 do
      dp(cap) = dp(cap).max(dp(cap - weight(item)) + value(item))
  dp(capacity)
int knapsackDp(const std::vector<int>& weight, const std::vector<int>& value, int capacity) {
    std::vector<int> dp(capacity + 1);
    for (int item = 0; item < weight.size(); item++) {
        for (int cap = capacity; cap >= weight[item]; cap--) {
            dp[cap] = std::max(dp[cap], dp[cap - weight[item]] + value[item]);
        }
    }
    return dp[capacity];
}

    
  

  


  


  


  

int intervalDp(int n) {
    int[][] dp = new int[n][n];
    for (int length = 1; length <= n; length++) {
        for (int left = 0; left + length <= n; left++) {
            int right = left + length - 1;
            dp[left][right] = solveInterval(left, right, dp);
        }
    }
    return dp[0][n - 1];
}
def interval_dp(n: int) -> int:
    dp = [[0] * n for _ in range(n)]
    for length in range(1, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            dp[left][right] = solve_interval(left, right, dp)
    return dp[0][n - 1]
def intervalDp(n: Int): Int =
  val dp = Array.fill(n, n)(0)
  for length <- 1 to n do
    for left <- 0 to n - length do
      val right = left + length - 1
      dp(left)(right) = solveInterval(left, right, dp)
  dp(0)(n - 1)
int intervalDp(int n) {
    std::vector<std::vector<int>> dp(n, std::vector<int>(n));
    for (int length = 1; length <= n; length++) {
        for (int left = 0; left + length <= n; left++) {
            int right = left + length - 1;
            dp[left][right] = solveInterval(left, right, dp);
        }
    }
    return dp[0][n - 1];
}

    
  

  


  


  


  

int bitmaskDp(int n) {
    int[][] dp = new int[1 << n][n];
    fill(dp, INF);
    for (int start = 0; start < n; start++) dp[1 << start][start] = base(start);
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int last = 0; last < n; last++) if (dp[mask][last] != INF) {
            for (int next = 0; next < n; next++) if ((mask & (1 << next)) == 0) {
                relax(dp, mask, last, next);
            }
        }
    }
    return answer(dp);
}
def bitmask_dp(n: int) -> int:
    dp = [[INF] * n for _ in range(1 << n)]
    for start in range(n):
        dp[1 << start][start] = base(start)
    for mask in range(1 << n):
        for last in range(n):
            if dp[mask][last] == INF:
                continue
            for nxt in range(n):
                if not mask & (1 << nxt):
                    relax(dp, mask, last, nxt)
    return answer(dp)
def bitmaskDp(n: Int): Int =
  val dp = Array.fill(1 << n, n)(INF)
  for start <- 0 until n do dp(1 << start)(start) = base(start)
  for mask <- 0 until (1 << n) do
    for last <- 0 until n do
      if dp(mask)(last) != INF then
        for next <- 0 until n do
          if (mask & (1 << next)) == 0 then relax(dp, mask, last, next)
  answer(dp)
int bitmaskDp(int n) {
    std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INF));
    for (int start = 0; start < n; start++) dp[1 << start][start] = base(start);
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int last = 0; last < n; last++) if (dp[mask][last] != INF) {
            for (int next = 0; next < n; next++) if ((mask & (1 << next)) == 0) {
                relax(dp, mask, last, next);
            }
        }
    }
    return answer(dp);
}

    
  

  


  


  


  

int increasingSubsequenceLength(int[] values) {
    int[] tails = new int[values.length];
    int size = 0;
    for (int value : values) {
        int i = lowerBound(tails, size, value);
        tails[i] = value;
        if (i == size) size++;
    }
    return size;
}
def increasing_subsequence_length(values: list[int]) -> int:
    tails = []
    for value in values:
        i = lower_bound(tails, value)
        if i == len(tails):
            tails.append(value)
        else:
            tails[i] = value
    return len(tails)
def increasingSubsequenceLength(values: Array[Int]): Int =
  val tails = Array.fill(values.length)(0)
  var size = 0
  for value <- values do
    val i = lowerBound(tails, size, value)
    tails(i) = value
    if i == size then size += 1
  size
int increasingSubsequenceLength(const std::vector<int>& values) {
    std::vector<int> tails;
    for (int value : values) {
        auto it = std::lower_bound(tails.begin(), tails.end(), value);
        if (it == tails.end()) tails.push_back(value);
        else *it = value;
    }
    return tails.size();
}

    
  

  


  


  


  

List<Item> topK(List<Item> items, int k) {
    PriorityQueue<Item> heap = new PriorityQueue<>(Comparator.comparingInt(this::score));
    for (Item item : items) {
        heap.add(item);
        if (heap.size() > k) heap.remove();
    }
    return new ArrayList<>(heap);
}
def top_k(items, k: int) -> list:
    heap = []
    for item in items:
        heappush(heap, (score(item), item))
        if len(heap) > k:
            heappop(heap)
    return [item for _, item in heap]
def topK(items: Iterable[Item], k: Int): Vector[Item] =
  val heap = scala.collection.mutable.PriorityQueue[Item]()(Ordering.by(-score(_)))
  for item <- items do
    heap.enqueue(item)
    if heap.size > k then heap.dequeue()
  heap.toVector
std::vector<Item> topK(const std::vector<Item>& items, int k) {
    auto worse = [](const Item& a, const Item& b) { return score(a) > score(b); };
    std::priority_queue<Item, std::vector<Item>, decltype(worse)> heap(worse);
    for (const Item& item : items) {
        heap.push(item);
        if (heap.size() > k) heap.pop();
    }
    return drain(heap);
}

    
  

  


  


  


  

void processWithBest(List<Event> events) {
    PriorityQueue<State> heap = new PriorityQueue<>(this::betterFirst);
    for (Event event : events) {
        addCandidates(heap, event);
        while (!heap.isEmpty() && stale(heap.peek(), event)) heap.remove();
        useBest(heap.peek(), event);
    }
}
def process_with_best(events) -> None:
    heap = []
    for event in events:
        add_candidates(heap, event)
        while heap and stale(heap[0], event):
            heappop(heap)
        use_best(heap[0], event)
def processWithBest(events: Iterable[Event]): Unit =
  val heap = scala.collection.mutable.PriorityQueue[State]()(betterFirst)
  for event <- events do
    addCandidates(heap, event)
    while heap.nonEmpty && stale(heap.head, event) do heap.dequeue()
    useBest(heap.head, event)
void processWithBest(const std::vector<Event>& events) {
    std::priority_queue<State, std::vector<State>, BetterFirst> heap;
    for (const Event& event : events) {
        addCandidates(heap, event);
        while (!heap.empty() && stale(heap.top(), event)) heap.pop();
        useBest(heap.top(), event);
    }
}

    
  

  


  


  


  

void add(int value) {
    if (low.isEmpty() || value <= low.peek()) low.add(value);
    else high.add(value);
    if (low.size() > high.size() + 1) high.add(low.remove());
    if (high.size() > low.size()) low.add(high.remove());
}
def add(value: int) -> None:
    if not low or value <= -low[0]:
        heappush(low, -value)
    else:
        heappush(high, value)
    if len(low) > len(high) + 1:
        heappush(high, -heappop(low))
    if len(high) > len(low):
        heappush(low, -heappop(high))
def add(value: Int): Unit =
  if low.isEmpty || value <= low.head then low.enqueue(value)
  else high.enqueue(value)
  if low.size > high.size + 1 then high.enqueue(low.dequeue())
  if high.size > low.size then low.enqueue(high.dequeue())
void add(int value) {
    if (low.empty() || value <= low.top()) low.push(value);
    else high.push(value);
    if (low.size() > high.size() + 1) {
        high.push(low.top());
        low.pop();
    }
    if (high.size() > low.size()) {
        low.push(high.top());
        high.pop();
    }
}

    
  

  


  


  


  

void parse(List<Token> tokens) {
    ArrayDeque<Token> stack = new ArrayDeque<>();
    for (Token token : tokens) {
        if (opens(token)) stack.push(token);
        else resolve(stack.pop(), token);
    }
}
def parse(tokens) -> None:
    stack = []
    for token in tokens:
        if opens(token):
            stack.append(token)
        else:
            resolve(stack.pop(), token)
def parse(tokens: Iterable[Token]): Unit =
  val stack = scala.collection.mutable.Stack[Token]()
  for token <- tokens do
    if opens(token) then stack.push(token)
    else resolve(stack.pop(), token)
void parse(const std::vector<Token>& tokens) {
    std::vector<Token> stack;
    for (const Token& token : tokens) {
        if (opens(token)) stack.push_back(token);
        else {
            resolve(stack.back(), token);
            stack.pop_back();
        }
    }
}

    
  

  


  


  


  

int[] nextGreater(int[] values) {
    int[] answer = new int[values.length];
    Arrays.fill(answer, -1);
    ArrayDeque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < values.length; i++) {
        while (!stack.isEmpty() && values[stack.peek()] < values[i]) answer[stack.pop()] = i;
        stack.push(i);
    }
    return answer;
}
def next_greater(values: list[int]) -> list[int]:
    answer = [-1] * len(values)
    stack = []
    for i, value in enumerate(values):
        while stack and values[stack[-1]] < value:
            answer[stack.pop()] = i
        stack.append(i)
    return answer
def nextGreater(values: Array[Int]): Array[Int] =
  val answer = Array.fill(values.length)(-1)
  val stack = scala.collection.mutable.Stack[Int]()
  for i <- values.indices do
    while stack.nonEmpty && values(stack.top) < values(i) do answer(stack.pop()) = i
    stack.push(i)
  answer
std::vector<int> nextGreater(const std::vector<int>& values) {
    std::vector<int> answer(values.size(), -1);
    std::vector<int> stack;
    for (int i = 0; i < values.size(); i++) {
        while (!stack.empty() && values[stack.back()] < values[i]) {
            answer[stack.back()] = i;
            stack.pop_back();
        }
        stack.push_back(i);
    }
    return answer;
}

    
  

  


  


  


  

void pushWindow(ArrayDeque<Integer> deque, int[] values, int index) {
    while (!deque.isEmpty() && values[deque.peekLast()] <= values[index]) deque.removeLast();
    deque.addLast(index);
}

void expireWindow(ArrayDeque<Integer> deque, int left) {
    while (!deque.isEmpty() && deque.peekFirst() < left) deque.removeFirst();
}
def push_window(deque, values: list[int], index: int) -> None:
    while deque and values[deque[-1]] <= values[index]:
        deque.pop()
    deque.append(index)

def expire_window(deque, left: int) -> None:
    while deque and deque[0] < left:
        deque.popleft()
def pushWindow(deque: scala.collection.mutable.ArrayDeque[Int], values: Array[Int], index: Int): Unit =
  while deque.nonEmpty && values(deque.last) <= values(index) do deque.removeLast()
  deque.append(index)

def expireWindow(deque: scala.collection.mutable.ArrayDeque[Int], left: Int): Unit =
  while deque.nonEmpty && deque.head < left do deque.removeHead()
void pushWindow(std::deque<int>& deque, const std::vector<int>& values, int index) {
    while (!deque.empty() && values[deque.back()] <= values[index]) deque.pop_back();
    deque.push_back(index);
}

void expireWindow(std::deque<int>& deque, int left) {
    while (!deque.empty() && deque.front() < left) deque.pop_front();
}

    
  

  


  


  


  

Value lookupOrBuild(List<Item> items) {
    Map<Key, Value> seen = new HashMap<>();
    for (Item item : items) {
        Key key = keyOf(item);
        if (seen.containsKey(key)) return merge(seen.get(key), item);
        seen.put(key, valueOf(item));
    }
    return emptyValue();
}
def lookup_or_build(items):
    seen = {}
    for item in items:
        key = key_of(item)
        if key in seen:
            return merge(seen[key], item)
        seen[key] = value_of(item)
    return empty_value()
def lookupOrBuild(items: Iterable[Item]): Value =
  val seen = scala.collection.mutable.Map[Key, Value]()
  for item <- items do
    val key = keyOf(item)
    if seen.contains(key) then return merge(seen(key), item)
    seen(key) = valueOf(item)
  emptyValue()
Value lookupOrBuild(const std::vector<Item>& items) {
    std::unordered_map<Key, Value> seen;
    for (const Item& item : items) {
        Key key = keyOf(item);
        if (seen.count(key)) return merge(seen[key], item);
        seen[key] = valueOf(item);
    }
    return emptyValue();
}

    
  

  


  


  


  

Map<Key, Integer> frequencies(List<Item> items) {
    Map<Key, Integer> counts = new HashMap<>();
    for (Item item : items) {
        Key key = keyOf(item);
        counts.put(key, counts.getOrDefault(key, 0) + 1);
    }
    return counts;
}
def frequencies(items) -> dict:
    counts = {}
    for item in items:
        key = key_of(item)
        counts[key] = counts.get(key, 0) + 1
    return counts
def frequencies(items: Iterable[Item]): Map[Key, Int] =
  val counts = scala.collection.mutable.Map[Key, Int]().withDefaultValue(0)
  for item <- items do
    val key = keyOf(item)
    counts(key) += 1
  counts.toMap
std::unordered_map<Key, int> frequencies(const std::vector<Item>& items) {
    std::unordered_map<Key, int> counts;
    for (const Item& item : items) {
        counts[keyOf(item)]++;
    }
    return counts;
}

    
  

  


  


  


  

boolean reachesRepeat(State start) {
    Set<State> seen = new HashSet<>();
    State state = start;
    while (seen.add(state)) {
        if (done(state)) return false;
        state = next(state);
    }
    return true;
}
def reaches_repeat(start) -> bool:
    seen = set()
    state = start
    while state not in seen:
        seen.add(state)
        if done(state):
            return False
        state = next_state(state)
    return True
def reachesRepeat(start: State): Boolean =
  val seen = scala.collection.mutable.Set[State]()
  var state = start
  while !seen.contains(state) do
    seen += state
    if done(state) then return false
    state = nextState(state)
  true
bool reachesRepeat(State start) {
    std::unordered_set<State> seen;
    State state = start;
    while (!seen.count(state)) {
        seen.insert(state);
        if (done(state)) return false;
        state = nextState(state);
    }
    return true;
}

    
  

  


  


  


  

int sortAndScan(List<Item> items) {
    items.sort(this::order);
    int answer = initial();
    for (Item item : items) {
        answer = consume(answer, item);
    }
    return answer;
}
def sort_and_scan(items) -> int:
    answer = initial()
    for item in sorted(items, key=order):
        answer = consume(answer, item)
    return answer
def sortAndScan(items: Vector[Item]): Int =
  var answer = initial()
  for item <- items.sortBy(order) do
    answer = consume(answer, item)
  answer
int sortAndScan(std::vector<Item>& items) {
    std::sort(items.begin(), items.end(), order);
    int answer = initial();
    for (const Item& item : items) {
        answer = consume(answer, item);
    }
    return answer;
}

    
  

  


  


  


  

int select(int[] values, int k) {
    int left = 0;
    int right = values.length - 1;
    while (left <= right) {
        int pivot = partition(values, left, right);
        if (pivot == k) return values[pivot];
        if (pivot < k) left = pivot + 1;
        else right = pivot - 1;
    }
    return -1;
}
def select(values: list[int], k: int) -> int:
    left, right = 0, len(values) - 1
    while left <= right:
        pivot = partition(values, left, right)
        if pivot == k:
            return values[pivot]
        if pivot < k:
            left = pivot + 1
        else:
            right = pivot - 1
    return -1
def select(values: Array[Int], k: Int): Int =
  var left = 0
  var right = values.length - 1
  while left <= right do
    val pivot = partition(values, left, right)
    if pivot == k then return values(pivot)
    if pivot < k then left = pivot + 1
    else right = pivot - 1
  -1
int select(std::vector<int>& values, int k) {
    int left = 0, right = static_cast<int>(values.size()) - 1;
    while (left <= right) {
        int pivot = partition(values, left, right);
        if (pivot == k) return values[pivot];
        if (pivot < k) left = pivot + 1;
        else right = pivot - 1;
    }
    return -1;
}

    
  

  


  


  


  

List<Interval> mergeIntervals(List<Interval> intervals) {
    intervals.sort(Comparator.comparingInt(a -> a.start));
    List<Interval> merged = new ArrayList<>();
    for (Interval current : intervals) {
        if (merged.isEmpty() || merged.get(merged.size() - 1).end < current.start) merged.add(current);
        else merged.get(merged.size() - 1).end = Math.max(merged.get(merged.size() - 1).end, current.end);
    }
    return merged;
}
def merge_intervals(intervals):
    merged = []
    for current in sorted(intervals, key=lambda x: x.start):
        if not merged or merged[-1].end < current.start:
            merged.append(current)
        else:
            merged[-1].end = max(merged[-1].end, current.end)
    return merged
def mergeIntervals(intervals: Vector[Interval]): Vector[Interval] =
  val merged = scala.collection.mutable.Buffer[Interval]()
  for current <- intervals.sortBy(_.start) do
    if merged.isEmpty || merged.last.end < current.start then merged += current
    else merged.last.end = merged.last.end.max(current.end)
  merged.toVector
std::vector<Interval> mergeIntervals(std::vector<Interval> intervals) {
    std::sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return a.start < b.start;
    });
    std::vector<Interval> merged;
    for (Interval current : intervals) {
        if (merged.empty() || merged.back().end < current.start) merged.push_back(current);
        else merged.back().end = std::max(merged.back().end, current.end);
    }
    return merged;
}

    
  

  


  


  


  

List<Interval> insertInterval(List<Interval> intervals, Interval next) {
    List<Interval> answer = new ArrayList<>();
    int i = 0;
    while (i < intervals.size() && intervals.get(i).end < next.start) answer.add(intervals.get(i++));
    while (i < intervals.size() && intervals.get(i).start <= next.end) next = merge(next, intervals.get(i++));
    answer.add(next);
    while (i < intervals.size()) answer.add(intervals.get(i++));
    return answer;
}
def insert_interval(intervals, next_interval):
    answer, i = [], 0
    while i < len(intervals) and intervals[i].end < next_interval.start:
        answer.append(intervals[i])
        i += 1
    while i < len(intervals) and intervals[i].start <= next_interval.end:
        next_interval = merge(next_interval, intervals[i])
        i += 1
    return answer + [next_interval] + intervals[i:]
def insertInterval(intervals: Vector[Interval], next0: Interval): Vector[Interval] =
  val answer = scala.collection.mutable.Buffer[Interval]()
  var next = next0
  var i = 0
  while i < intervals.length && intervals(i).end < next.start do
    answer += intervals(i)
    i += 1
  while i < intervals.length && intervals(i).start <= next.end do
    next = merge(next, intervals(i))
    i += 1
  (answer :+ next).toVector ++ intervals.drop(i)
std::vector<Interval> insertInterval(const std::vector<Interval>& intervals, Interval next) {
    std::vector<Interval> answer;
    int i = 0;
    while (i < intervals.size() && intervals[i].end < next.start) answer.push_back(intervals[i++]);
    while (i < intervals.size() && intervals[i].start <= next.end) next = merge(next, intervals[i++]);
    answer.push_back(next);
    while (i < intervals.size()) answer.push_back(intervals[i++]);
    return answer;
}

    
  

  


  


  


  

int maxConcurrent(List<Interval> intervals) {
    List<Event> events = eventsFrom(intervals);
    events.sort(this::byTimeThenEndBeforeStart);
    int active = 0;
    int best = 0;
    for (Event event : events) {
        active += event.delta;
        best = Math.max(best, active);
    }
    return best;
}
def max_concurrent(intervals) -> int:
    active = best = 0
    for event in sorted(events_from(intervals), key=by_time_then_end_before_start):
        active += event.delta
        best = max(best, active)
    return best
def maxConcurrent(intervals: Vector[Interval]): Int =
  var active = 0
  var best = 0
  for event <- eventsFrom(intervals).sortBy(byTimeThenEndBeforeStart) do
    active += event.delta
    best = best.max(active)
  best
int maxConcurrent(const std::vector<Interval>& intervals) {
    auto events = eventsFrom(intervals);
    std::sort(events.begin(), events.end(), byTimeThenEndBeforeStart);
    int active = 0, best = 0;
    for (const Event& event : events) {
        active += event.delta;
        best = std::max(best, active);
    }
    return best;
}

    
  

  


  


  


  

int sweep(List<Event> events) {
    events.sort(this::eventOrder);
    int active = 0;
    int answer = initial();
    for (Event event : events) {
        active += event.delta;
        answer = update(answer, event, active);
    }
    return answer;
}
def sweep(events) -> int:
    active = 0
    answer = initial()
    for event in sorted(events, key=event_order):
        active += event.delta
        answer = update(answer, event, active)
    return answer
def sweep(events: Vector[Event]): Int =
  var active = 0
  var answer = initial()
  for event <- events.sortBy(eventOrder) do
    active += event.delta
    answer = update(answer, event, active)
  answer
int sweep(std::vector<Event> events) {
    std::sort(events.begin(), events.end(), eventOrder);
    int active = 0, answer = initial();
    for (const Event& event : events) {
        active += event.delta;
        answer = update(answer, event, active);
    }
    return answer;
}

    
  

  


  


  


  

void sweepWithActiveSet(List<Event> events) {
    events.sort(this::eventOrder);
    TreeSet<Item> active = new TreeSet<>(this::itemOrder);
    for (Event event : events) {
        if (event.starts) active.add(event.item);
        else active.remove(event.item);
        use(active, event);
    }
}
def sweep_with_active_set(events) -> None:
    active = OrderedSet()
    for event in sorted(events, key=event_order):
        if event.starts:
            active.add(event.item)
        else:
            active.remove(event.item)
        use(active, event)
def sweepWithActiveSet(events: Vector[Event]): Unit =
  val active = scala.collection.mutable.TreeSet[Item]()(itemOrder)
  for event <- events.sortBy(eventOrder) do
    if event.starts then active += event.item
    else active -= event.item
    use(active, event)
void sweepWithActiveSet(std::vector<Event> events) {
    std::sort(events.begin(), events.end(), eventOrder);
    std::set<Item, ItemOrder> active;
    for (const Event& event : events) {
        if (event.starts) active.insert(event.item);
        else active.erase(event.item);
        use(active, event);
    }
}

    
  

  


  


  


  

class SegmentTree {
    int size;
    int[] tree;

    SegmentTree(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree = new int[2 * size];
    }

    void set(int index, int value) {
        index += size;
        tree[index] = value;
        for (index /= 2; index > 0; index /= 2) tree[index] = merge(tree[2 * index], tree[2 * index + 1]);
    }
}
class SegmentTree:
    def __init__(self, n: int):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.tree = [0] * (2 * self.size)

    def set(self, index: int, value: int) -> None:
        index += self.size
        self.tree[index] = value
        index //= 2
        while index:
            self.tree[index] = merge(self.tree[2 * index], self.tree[2 * index + 1])
            index //= 2
final class SegmentTree(n: Int):
  private var size = 1
  while size < n do size *= 2
  private val tree = Array.fill(2 * size)(0)

  def set(index0: Int, value: Int): Unit =
    var index = index0 + size
    tree(index) = value
    index /= 2
    while index > 0 do
      tree(index) = merge(tree(2 * index), tree(2 * index + 1))
      index /= 2
class SegmentTree {
    int size = 1;
    std::vector<int> tree;

public:
    explicit SegmentTree(int n) {
        while (size < n) size *= 2;
        tree.assign(2 * size, 0);
    }

    void set(int index, int value) {
        index += size;
        tree[index] = value;
        for (index /= 2; index > 0; index /= 2) tree[index] = merge(tree[2 * index], tree[2 * index + 1]);
    }
};

    
  

  


  


  


  

class FenwickTree {
    int[] tree;

    FenwickTree(int n) {
        tree = new int[n + 1];
    }

    void add(int index, int delta) {
        for (index++; index < tree.length; index += index & -index) tree[index] += delta;
    }

    int sum(int index) {
        int total = 0;
        for (index++; index > 0; index -= index & -index) total += tree[index];
        return total;
    }
}
class FenwickTree:
    def __init__(self, n: int):
        self.tree = [0] * (n + 1)

    def add(self, index: int, delta: int) -> None:
        index += 1
        while index < len(self.tree):
            self.tree[index] += delta
            index += index & -index

    def sum(self, index: int) -> int:
        total = 0
        index += 1
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total
final class FenwickTree(n: Int):
  private val tree = Array.fill(n + 1)(0)

  def add(index0: Int, delta: Int): Unit =
    var index = index0 + 1
    while index < tree.length do
      tree(index) += delta
      index += index & -index

  def sum(index0: Int): Int =
    var index = index0 + 1
    var total = 0
    while index > 0 do
      total += tree(index)
      index -= index & -index
    total
class FenwickTree {
    std::vector<int> tree;

public:
    explicit FenwickTree(int n) : tree(n + 1) {}

    void add(int index, int delta) {
        for (index++; index < tree.size(); index += index & -index) tree[index] += delta;
    }

    int sum(int index) const {
        int total = 0;
        for (index++; index > 0; index -= index & -index) total += tree[index];
        return total;
    }
};

    
  

  


  


  


  

class Trie {
    Map<Character, Trie> next = new HashMap<>();
    boolean word;

    void add(String text) {
        Trie node = this;
        for (char ch : text.toCharArray()) node = node.next.computeIfAbsent(ch, key -> new Trie());
        node.word = true;
    }
}
class Trie:
    def __init__(self):
        self.next = {}
        self.word = False

    def add(self, text: str) -> None:
        node = self
        for ch in text:
            node = node.next.setdefault(ch, Trie())
        node.word = True
final class Trie:
  val next = scala.collection.mutable.Map[Char, Trie]()
  var word = false

  def add(text: String): Unit =
    var node = this
    for ch <- text do node = node.next.getOrElseUpdate(ch, new Trie)
    node.word = true
class Trie {
    std::unordered_map<char, Trie*> next;
    bool word = false;

public:
    void add(const std::string& text) {
        Trie* node = this;
        for (char ch : text) {
            if (!node->next.count(ch)) node->next[ch] = new Trie();
            node = node->next[ch];
        }
        node->word = true;
    }
};

    
  

  


  


  


  

ListNode findMeetingPoint(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return slow;
    }
    return null;
}
def find_meeting_point(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return slow
    return None
def findMeetingPoint(head: ListNode): ListNode =
  var slow = head
  var fast = head
  while fast != null && fast.next != null do
    slow = slow.next
    fast = fast.next.next
    if slow == fast then return slow
  null
ListNode* findMeetingPoint(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return slow;
    }
    return nullptr;
}

    
  

  


  


  


  

ListNode reverse(ListNode head) {
    ListNode previous = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = previous;
        previous = head;
        head = next;
    }
    return previous;
}
def reverse(head):
    previous = None
    while head:
        nxt = head.next
        head.next = previous
        previous = head
        head = nxt
    return previous
def reverse(head0: ListNode): ListNode =
  var head = head0
  var previous: ListNode = null
  while head != null do
    val next = head.next
    head.next = previous
    previous = head
    head = next
  previous
ListNode* reverse(ListNode* head) {
    ListNode* previous = nullptr;
    while (head != nullptr) {
        ListNode* next = head->next;
        head->next = previous;
        previous = head;
        head = next;
    }
    return previous;
}

    
  

  


  


  


  

ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (a != null && b != null) {
        if (a.value <= b.value) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a != null ? a : b;
    return dummy.next;
}
def merge(a, b):
    dummy = tail = ListNode(0)
    while a and b:
        if a.value <= b.value:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next
def merge(a0: ListNode, b0: ListNode): ListNode =
  var a = a0
  var b = b0
  val dummy = ListNode(0)
  var tail = dummy
  while a != null && b != null do
    if a.value <= b.value then
      tail.next = a
      a = a.next
    else
      tail.next = b
      b = b.next
    tail = tail.next
  tail.next = if a != null then a else b
  dummy.next
ListNode* merge(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a != nullptr && b != nullptr) {
        if (a->value <= b->value) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a != nullptr ? a : b;
    return dummy.next;
}

    
  

  


  


  


  

int[] prefixTable(String pattern) {
    int[] prefix = new int[pattern.length()];
    for (int i = 1, j = 0; i < pattern.length(); i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) j = prefix[j - 1];
        if (pattern.charAt(i) == pattern.charAt(j)) j++;
        prefix[i] = j;
    }
    return prefix;
}
def prefix_table(pattern: str) -> list[int]:
    prefix = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j and pattern[i] != pattern[j]:
            j = prefix[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        prefix[i] = j
    return prefix
def prefixTable(pattern: String): Array[Int] =
  val prefix = Array.fill(pattern.length)(0)
  var j = 0
  for i <- 1 until pattern.length do
    while j > 0 && pattern(i) != pattern(j) do j = prefix(j - 1)
    if pattern(i) == pattern(j) then j += 1
    prefix(i) = j
  prefix
std::vector<int> prefixTable(const std::string& pattern) {
    std::vector<int> prefix(pattern.size());
    for (int i = 1, j = 0; i < pattern.size(); i++) {
        while (j > 0 && pattern[i] != pattern[j]) j = prefix[j - 1];
        if (pattern[i] == pattern[j]) j++;
        prefix[i] = j;
    }
    return prefix;
}

    
  

  


  


  


  

long[] rollingHash(String text, long base, long mod) {
    long[] hash = new long[text.length() + 1];
    for (int i = 0; i < text.length(); i++) {
        hash[i + 1] = (hash[i] * base + text.charAt(i)) % mod;
    }
    return hash;
}
def rolling_hash(text: str, base: int, mod: int) -> list[int]:
    hash_values = [0]
    for ch in text:
        hash_values.append((hash_values[-1] * base + ord(ch)) % mod)
    return hash_values
def rollingHash(text: String, base: Long, mod: Long): Array[Long] =
  val hash = Array.fill(text.length + 1)(0L)
  for i <- text.indices do
    hash(i + 1) = (hash(i) * base + text(i).toLong) % mod
  hash
std::vector<long long> rollingHash(const std::string& text, long long base, long long mod) {
    std::vector<long long> hash(text.size() + 1);
    for (int i = 0; i < text.size(); i++) {
        hash[i + 1] = (hash[i] * base + text[i]) % mod;
    }
    return hash;
}

    
  

  


  


  


  

int greedy(List<Item> items) {
    int answer = initial();
    for (Item item : items) {
        if (forced(item)) answer = take(answer, item);
    }
    return answer;
}
def greedy(items) -> int:
    answer = initial()
    for item in items:
        if forced(item):
            answer = take(answer, item)
    return answer
def greedy(items: Iterable[Item]): Int =
  var answer = initial()
  for item <- items do
    if forced(item) then answer = take(answer, item)
  answer
int greedy(const std::vector<Item>& items) {
    int answer = initial();
    for (const Item& item : items) {
        if (forced(item)) answer = take(answer, item);
    }
    return answer;
}

    
  

  


  


  


  

int greedyAfterSort(List<Item> items) {
    items.sort(this::priority);
    int answer = initial();
    for (Item item : items) {
        if (compatible(item)) answer = take(answer, item);
    }
    return answer;
}
def greedy_after_sort(items) -> int:
    answer = initial()
    for item in sorted(items, key=priority):
        if compatible(item):
            answer = take(answer, item)
    return answer
def greedyAfterSort(items: Vector[Item]): Int =
  var answer = initial()
  for item <- items.sortBy(priority) do
    if compatible(item) then answer = take(answer, item)
  answer
int greedyAfterSort(std::vector<Item>& items) {
    std::sort(items.begin(), items.end(), priority);
    int answer = initial();
    for (const Item& item : items) {
        if (compatible(item)) answer = take(answer, item);
    }
    return answer;
}

    
  

  


  


  


  

int greedyWithHeap(List<Item> items) {
    PriorityQueue<Item> heap = new PriorityQueue<>(this::priority);
    int answer = initial();
    for (Item item : items) {
        heap.add(item);
        while (!heap.isEmpty() && invalid(heap.peek())) heap.remove();
        answer = use(answer, heap.peek());
    }
    return answer;
}
def greedy_with_heap(items) -> int:
    heap = []
    answer = initial()
    for item in items:
        heappush(heap, ranked(item))
        while heap and invalid(heap[0]):
            heappop(heap)
        answer = use(answer, heap[0])
    return answer
def greedyWithHeap(items: Iterable[Item]): Int =
  val heap = scala.collection.mutable.PriorityQueue[Item]()(priority)
  var answer = initial()
  for item <- items do
    heap.enqueue(item)
    while heap.nonEmpty && invalid(heap.head) do heap.dequeue()
    answer = use(answer, heap.head)
  answer
int greedyWithHeap(const std::vector<Item>& items) {
    std::priority_queue<Item, std::vector<Item>, Priority> heap;
    int answer = initial();
    for (const Item& item : items) {
        heap.push(item);
        while (!heap.empty() && invalid(heap.top())) heap.pop();
        answer = use(answer, heap.top());
    }
    return answer;
}

    
  

  


  


  


  

int gcd(int a, int b) {
    while (b != 0) {
        int next = a % b;
        a = b;
        b = next;
    }
    return Math.abs(a);
}
def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return abs(a)
def gcd(a0: Int, b0: Int): Int =
  var a = a0
  var b = b0
  while b != 0 do
    val next = a % b
    a = b
    b = next
  a.abs
int gcd(int a, int b) {
    while (b != 0) {
        int next = a % b;
        a = b;
        b = next;
    }
    return std::abs(a);
}

    
  

  


  


  


  

boolean[] sieve(int n) {
    boolean[] prime = new boolean[n + 1];
    Arrays.fill(prime, true);
    if (n >= 0) prime[0] = false;
    if (n >= 1) prime[1] = false;
    for (int p = 2; p * p <= n; p++) if (prime[p]) {
        for (int x = p * p; x <= n; x += p) prime[x] = false;
    }
    return prime;
}
def sieve(n: int) -> list[bool]:
    prime = [True] * (n + 1)
    if n >= 0:
        prime[0] = False
    if n >= 1:
        prime[1] = False
    p = 2
    while p * p <= n:
        if prime[p]:
            for x in range(p * p, n + 1, p):
                prime[x] = False
        p += 1
    return prime
def sieve(n: Int): Array[Boolean] =
  val prime = Array.fill(n + 1)(true)
  if n >= 0 then prime(0) = false
  if n >= 1 then prime(1) = false
  var p = 2
  while p * p <= n do
    if prime(p) then
      for x <- p * p to n by p do prime(x) = false
    p += 1
  prime
std::vector<bool> sieve(int n) {
    std::vector<bool> prime(n + 1, true);
    if (n >= 0) prime[0] = false;
    if (n >= 1) prime[1] = false;
    for (int p = 2; p * p <= n; p++) if (prime[p]) {
        for (int x = p * p; x <= n; x += p) prime[x] = false;
    }
    return prime;
}

    
  

  


  


  


  

long[][] combinations(int n) {
    long[][] choose = new long[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
        choose[i][0] = choose[i][i] = 1;
        for (int j = 1; j < i; j++) choose[i][j] = choose[i - 1][j - 1] + choose[i - 1][j];
    }
    return choose;
}
def combinations(n: int) -> list[list[int]]:
    choose = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        choose[i][0] = choose[i][i] = 1
        for j in range(1, i):
            choose[i][j] = choose[i - 1][j - 1] + choose[i - 1][j]
    return choose
def combinations(n: Int): Array[Array[Long]] =
  val choose = Array.fill(n + 1, n + 1)(0L)
  for i <- 0 to n do
    choose(i)(0) = 1
    choose(i)(i) = 1
    for j <- 1 until i do choose(i)(j) = choose(i - 1)(j - 1) + choose(i - 1)(j)
  choose
std::vector<std::vector<long long>> combinations(int n) {
    std::vector<std::vector<long long>> choose(n + 1, std::vector<long long>(n + 1));
    for (int i = 0; i <= n; i++) {
        choose[i][0] = choose[i][i] = 1;
        for (int j = 1; j < i; j++) choose[i][j] = choose[i - 1][j - 1] + choose[i - 1][j];
    }
    return choose;
}

    
  

  


  


  


  

void enumerate(int n) {
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int bit = 0; bit < n; bit++) {
            if ((mask & (1 << bit)) != 0) use(bit);
        }
        finish(mask);
    }
}
def enumerate(n: int) -> None:
    for mask in range(1 << n):
        for bit in range(n):
            if mask & (1 << bit):
                use(bit)
        finish(mask)
def enumerate(n: Int): Unit =
  for mask <- 0 until (1 << n) do
    for bit <- 0 until n do
      if (mask & (1 << bit)) != 0 then use(bit)
    finish(mask)
void enumerate(int n) {
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int bit = 0; bit < n; bit++) {
            if (mask & (1 << bit)) use(bit);
        }
        finish(mask);
    }
}

GCDReduce arithmetic state with divisibility, remainders, or bit masks. SieveMark composite numbers from each prime. CombinatoricsBuild counting values from smaller counting values. Bitmask enumerationUse bits to represent which elements are selected.