int diameter = 0;
int height(TreeNode node) {
    if (node == null) return 0;
    int l = height(node.left), r = height(node.right);
    diameter = Math.max(diameter, l + r);   // longest path THROUGH node
    return 1 + Math.max(l, r);              // height reported to parent
}

int diameter = 0;
int height(TreeNode* node) {
    if (node == nullptr) return 0;
    int l = height(node->left), r = height(node->right);
    diameter = std::max(diameter, l + r);   // longest path THROUGH node
    return 1 + std::max(l, r);              // height reported to parent
}

diameter = 0
def height(node):
    global diameter
    if node is None:
        return 0
    l, r = height(node.left), height(node.right)
    diameter = max(diameter, l + r)   # longest path THROUGH node
    return 1 + max(l, r)              # height reported to parent

let diameter = 0;
function height(node: TreeNode | null): number {
    if (node === null) return 0;
    const l = height(node.left), r = height(node.right);
    diameter = Math.max(diameter, l + r);   // longest path THROUGH node
    return 1 + Math.max(l, r);              // height reported to parent
}

int numIslands(char[][] g) {
    int m = g.length, n = g[0].length, count = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (g[i][j] == '1') { count++; sink(g, i, j); }
    return count;
}
void sink(char[][] g, int i, int j) {
    if (i<0 || i>=g.length || j<0 || j>=g[0].length || g[i][j] != '1') return;
    g[i][j] = '0';                          // mark visited in place
    sink(g,i+1,j); sink(g,i-1,j); sink(g,i,j+1); sink(g,i,j-1);
}

int numIslands(std::vector<std::vector<char>>& g) {
    int m = g.size(), n = g[0].size(), count = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (g[i][j] == '1') { count++; sink(g, i, j); }
    return count;
}
void sink(std::vector<std::vector<char>>& g, int i, int j) {
    if (i<0 || i>=(int)g.size() || j<0 || j>=(int)g[0].size() || g[i][j] != '1') return;
    g[i][j] = '0';                          // mark visited in place
    sink(g,i+1,j); sink(g,i-1,j); sink(g,i,j+1); sink(g,i,j-1);
}

def num_islands(g):
    m, n, count = len(g), len(g[0]), 0
    for i in range(m):
        for j in range(n):
            if g[i][j] == '1':
                count += 1
                sink(g, i, j)
    return count

def sink(g, i, j):
    if i < 0 or i >= len(g) or j < 0 or j >= len(g[0]) or g[i][j] != '1':
        return
    g[i][j] = '0'                          # mark visited in place
    sink(g, i+1, j); sink(g, i-1, j); sink(g, i, j+1); sink(g, i, j-1)

function numIslands(g: string[][]): number {
    const m = g.length, n = g[0].length; let count = 0;
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)
            if (g[i][j] === '1') { count++; sink(g, i, j); }
    return count;
}
function sink(g: string[][], i: number, j: number): void {
    if (i<0 || i>=g.length || j<0 || j>=g[0].length || g[i][j] !== '1') return;
    g[i][j] = '0';                          // mark visited in place
    sink(g,i+1,j); sink(g,i-1,j); sink(g,i,j+1); sink(g,i,j-1);
}

Deque<Integer> stack = new ArrayDeque<>();
stack.push(src); seen[src] = true;
while (!stack.isEmpty()) {
    int u = stack.pop();
    for (int v : adj[u]) if (!seen[v]) { seen[v] = true; stack.push(v); }
}

std::stack<int> stack;
stack.push(src); seen[src] = true;
while (!stack.empty()) {
    int u = stack.top(); stack.pop();
    for (int v : adj[u]) if (!seen[v]) { seen[v] = true; stack.push(v); }
}

stack = [src]
seen[src] = True
while stack:
    u = stack.pop()
    for v in adj[u]:
        if not seen[v]:
            seen[v] = True
            stack.append(v)

const stack: number[] = [src];
seen[src] = true;
while (stack.length > 0) {
    const u = stack.pop()!;
    for (const v of adj[u]) if (!seen[v]) { seen[v] = true; stack.push(v); }
}

void subsets(int[] nums, int i, List<Integer> cur, List<List<Integer>> out) {
    if (i == nums.length) { out.add(new ArrayList<>(cur)); return; }
    subsets(nums, i+1, cur, out);                 // skip nums[i]
    cur.add(nums[i]);
    subsets(nums, i+1, cur, out);                 // take nums[i]
    cur.remove(cur.size()-1);
}

void subsets(std::vector<int>& nums, int i, std::vector<int>& cur, std::vector<std::vector<int>>& out) {
    if (i == (int)nums.size()) { out.push_back(cur); return; }
    subsets(nums, i+1, cur, out);                 // skip nums[i]
    cur.push_back(nums[i]);
    subsets(nums, i+1, cur, out);                 // take nums[i]
    cur.pop_back();
}

def subsets(nums, i, cur, out):
    if i == len(nums):
        out.append(list(cur))
        return
    subsets(nums, i+1, cur, out)                 # skip nums[i]
    cur.append(nums[i])
    subsets(nums, i+1, cur, out)                 # take nums[i]
    cur.pop()

function subsets(nums: number[], i: number, cur: number[], out: number[][]): void {
    if (i === nums.length) { out.push([...cur]); return; }
    subsets(nums, i+1, cur, out);                 // skip nums[i]
    cur.push(nums[i]);
    subsets(nums, i+1, cur, out);                 // take nums[i]
    cur.pop();
}

void permute(int[] nums, List<Integer> cur, boolean[] used, List<List<Integer>> out){
    if (cur.size()==nums.length){ out.add(new ArrayList<>(cur)); return; }
    for (int i=0;i<nums.length;i++){
        if (used[i]) continue;
        used[i]=true; cur.add(nums[i]);
        permute(nums, cur, used, out);
        cur.remove(cur.size()-1); used[i]=false;
    }
}

void permute(std::vector<int>& nums, std::vector<int>& cur, std::vector<bool>& used, std::vector<std::vector<int>>& out){
    if (cur.size()==nums.size()){ out.push_back(cur); return; }
    for (int i=0;i<(int)nums.size();i++){
        if (used[i]) continue;
        used[i]=true; cur.push_back(nums[i]);
        permute(nums, cur, used, out);
        cur.pop_back(); used[i]=false;
    }
}

def permute(nums, cur, used, out):
    if len(cur) == len(nums):
        out.append(list(cur))
        return
    for i in range(len(nums)):
        if used[i]:
            continue
        used[i] = True
        cur.append(nums[i])
        permute(nums, cur, used, out)
        cur.pop()
        used[i] = False

function permute(nums: number[], cur: number[], used: boolean[], out: number[][]): void {
    if (cur.length === nums.length) { out.push([...cur]); return; }
    for (let i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true; cur.push(nums[i]);
        permute(nums, cur, used, out);
        cur.pop(); used[i] = false;
    }
}

int totalNQueens(int n){ return place(n,0,0,0,0); }
int place(int n,int row,int cols,int diag,int anti){
    if (row==n) return 1;
    int free = ((1<<n)-1) & ~(cols|diag|anti);      // columns still safe
    int count=0;
    while (free!=0){
        int bit = free & -free; free -= bit;         // pick lowest safe column
        count += place(n,row+1, cols|bit, (diag|bit)<<1, (anti|bit)>>1);
    }
    return count;
}

int totalNQueens(int n){ return place(n,0,0,0,0); }
int place(int n,int row,int cols,int diag,int anti){
    if (row==n) return 1;
    int free = ((1<<n)-1) & ~(cols|diag|anti);      // columns still safe
    int count=0;
    while (free!=0){
        int bit = free & -free; free -= bit;         // pick lowest safe column
        count += place(n,row+1, cols|bit, (diag|bit)<<1, (anti|bit)>>1);
    }
    return count;
}

def total_n_queens(n):
    return place(n, 0, 0, 0, 0)

def place(n, row, cols, diag, anti):
    if row == n:
        return 1
    free = ((1 << n) - 1) & ~(cols | diag | anti)      # columns still safe
    count = 0
    while free != 0:
        bit = free & -free
        free -= bit         # pick lowest safe column
        count += place(n, row+1, cols|bit, (diag|bit)<<1, (anti|bit)>>1)
    return count

function totalNQueens(n: number): number { return place(n,0,0,0,0); }
function place(n: number, row: number, cols: number, diag: number, anti: number): number {
    if (row === n) return 1;
    let free = ((1<<n)-1) & ~(cols|diag|anti);      // columns still safe
    let count = 0;
    while (free !== 0) {
        const bit = free & -free; free -= bit;         // pick lowest safe column
        count += place(n, row+1, cols|bit, (diag|bit)<<1, (anti|bit)>>1);
    }
    return count;
}

List<TreeNode> generateTrees(int n){ return build(1, n); }
List<TreeNode> build(int lo, int hi){
    List<TreeNode> res = new ArrayList<>();
    if (lo > hi){ res.add(null); return res; }          // one empty shape
    for (int root = lo; root <= hi; root++)
        for (TreeNode l : build(lo, root-1))            // all left subtrees
            for (TreeNode r : build(root+1, hi)){       // all right subtrees
                TreeNode node = new TreeNode(root);
                node.left = l; node.right = r;
                res.add(node);
            }
    return res;
}

std::vector<TreeNode*> generateTrees(int n){ return build(1, n); }
std::vector<TreeNode*> build(int lo, int hi){
    std::vector<TreeNode*> res;
    if (lo > hi){ res.push_back(nullptr); return res; }          // one empty shape
    for (int root = lo; root <= hi; root++)
        for (TreeNode* l : build(lo, root-1))            // all left subtrees
            for (TreeNode* r : build(root+1, hi)){       // all right subtrees
                TreeNode* node = new TreeNode(root);
                node->left = l; node->right = r;
                res.push_back(node);
            }
    return res;
}

def generate_trees(n):
    return build(1, n)

def build(lo, hi):
    res = []
    if lo > hi:
        res.append(None)          # one empty shape
        return res
    for root in range(lo, hi+1):
        for l in build(lo, root-1):            # all left subtrees
            for r in build(root+1, hi):       # all right subtrees
                node = TreeNode(root)
                node.left = l
                node.right = r
                res.append(node)
    return res

function generateTrees(n: number): (TreeNode | null)[] { return build(1, n); }
function build(lo: number, hi: number): (TreeNode | null)[] {
    const res: (TreeNode | null)[] = [];
    if (lo > hi) { res.push(null); return res; }          // one empty shape
    for (let root = lo; root <= hi; root++)
        for (const l of build(lo, root-1))            // all left subtrees
            for (const r of build(root+1, hi)) {       // all right subtrees
                const node = new TreeNode(root);
                node.left = l; node.right = r;
                res.push(node);
            }
    return res;
}

int numTrees(int n){
    int[] dp = new int[n+1];
    dp[0] = dp[1] = 1;
    for (int nodes=2; nodes<=n; nodes++)
        for (int root=1; root<=nodes; root++)
            dp[nodes] += dp[root-1] * dp[nodes-root];   // left size × right size
    return dp[n];
}

int numTrees(int n){
    std::vector<int> dp(n+1, 0);
    dp[0] = dp[1] = 1;
    for (int nodes=2; nodes<=n; nodes++)
        for (int root=1; root<=nodes; root++)
            dp[nodes] += dp[root-1] * dp[nodes-root];   // left size × right size
    return dp[n];
}

def num_trees(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for nodes in range(2, n + 1):
        for root in range(1, nodes + 1):
            dp[nodes] += dp[root-1] * dp[nodes-root]   # left size × right size
    return dp[n]

function numTrees(n: number): number {
    const dp = new Array<number>(n+1).fill(0);
    dp[0] = dp[1] = 1;
    for (let nodes = 2; nodes <= n; nodes++)
        for (let root = 1; root <= nodes; root++)
            dp[nodes] += dp[root-1] * dp[nodes-root];   // left size × right size
    return dp[n];
}

int[] topoSort(int n, int[][] edges){
    List<Integer>[] adj = new List[n];
    for (int i=0;i<n;i++) adj[i]=new ArrayList<>();
    int[] indeg = new int[n];
    for (int[] e : edges){ adj[e[0]].add(e[1]); indeg[e[1]]++; }

    Queue<Integer> q = new ArrayDeque<>();
    for (int i=0;i<n;i++) if (indeg[i]==0) q.offer(i);

    int[] order = new int[n]; int k=0;
    while (!q.isEmpty()){
        int u = q.poll(); order[k++] = u;
        for (int v : adj[u]) if (--indeg[v]==0) q.offer(v);
    }
    return k==n ? order : new int[0];        // empty ⇒ cycle
}

vector<int> topoSort(int n, vector<vector<int>>& edges){
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);
    for (auto& e : edges){ adj[e[0]].push_back(e[1]); indeg[e[1]]++; }

    queue<int> q;
    for (int i=0;i<n;i++) if (indeg[i]==0) q.push(i);

    vector<int> order(n); int k=0;
    while (!q.empty()){
        int u = q.front(); q.pop(); order[k++] = u;
        for (int v : adj[u]) if (--indeg[v]==0) q.push(v);
    }
    return k==n ? order : vector<int>();        // empty ⇒ cycle
}

def topo_sort(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for e in edges:
        adj[e[0]].append(e[1])
        indeg[e[1]] += 1

    q = deque()
    for i in range(n):
        if indeg[i] == 0:
            q.append(i)

    order = [0] * n
    k = 0
    while q:
        u = q.popleft()
        order[k] = u
        k += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if k == n else []        # empty ⇒ cycle

function topoSort(n: number, edges: number[][]): number[] {
    const adj: number[][] = Array.from({ length: n }, () => []);
    const indeg = new Array(n).fill(0);
    for (const e of edges) { adj[e[0]].push(e[1]); indeg[e[1]]++; }

    const q: number[] = [];
    for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);

    const order = new Array(n).fill(0);
    let k = 0;
    let head = 0;
    while (head < q.length) {
        const u = q[head++]; order[k++] = u;
        for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
    }
    return k === n ? order : [];        // empty ⇒ cycle
}

int[] dijkstra(List<int[]>[] adj, int src, int n){   // adj[u] = {v, w}
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);
    pq.offer(new int[]{src,0});
    while (!pq.isEmpty()){
        int[] top = pq.poll();
        int u = top[0], d = top[1];
        if (d > dist[u]) continue;                    // stale entry, skip
        for (int[] e : adj[u]){
            int v = e[0], w = e[1];
            if (dist[u]+w < dist[v]){
                dist[v] = dist[u]+w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

vector<int> dijkstra(vector<vector<pair<int,int>>>& adj, int src, int n){   // adj[u] = {v, w}
    vector<int> dist(n, INT_MAX);
    dist[src] = 0;
    auto cmp = [](const pair<int,int>& a, const pair<int,int>& b){ return a.second > b.second; };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
    pq.push({src, 0});
    while (!pq.empty()){
        auto top = pq.top(); pq.pop();
        int u = top.first, d = top.second;
        if (d > dist[u]) continue;                    // stale entry, skip
        for (auto& e : adj[u]){
            int v = e.first, w = e.second;
            if (dist[u]+w < dist[v]){
                dist[v] = dist[u]+w;
                pq.push({v, dist[v]});
            }
        }
    }
    return dist;
}

def dijkstra(adj, src, n):   # adj[u] = [(v, w), ...]
    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src)]            # (d, u)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                              # stale entry, skip
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

function dijkstra(adj: [number, number][][], src: number, n: number): number[] {   // adj[u] = [v, w]
    const dist = new Array(n).fill(Infinity);
    dist[src] = 0;
    const pq: [number, number][] = [[src, 0]];   // [u, d]; array used as a simple priority queue
    while (pq.length) {
        pq.sort((a, b) => a[1] - b[1]);
        const [u, d] = pq.shift()!;
        if (d > dist[u]) continue;                    // stale entry, skip
        for (const [v, w] of adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([v, dist[v]]);
            }
        }
    }
    return dist;
}

class DSU {
    int[] parent, rank; int count;
    DSU(int n){
        parent = new int[n]; rank = new int[n]; count = n;
        for (int i=0;i<n;i++) parent[i]=i;
    }
    int find(int x){
        while (parent[x]!=x){ parent[x]=parent[parent[x]]; x=parent[x]; } // compress
        return x;
    }
    boolean union(int a,int b){
        int ra=find(a), rb=find(b);
        if (ra==rb) return false;               // already same set (edge forms a cycle)
        if (rank[ra]<rank[rb]){ int t=ra; ra=rb; rb=t; }
        parent[rb]=ra;                          // smaller under larger
        if (rank[ra]==rank[rb]) rank[ra]++;
        count--;                                // one fewer component
        return true;
    }
}

class DSU {
public:
    vector<int> parent, rank; int count;
    DSU(int n){
        parent.resize(n); rank.assign(n, 0); count = n;
        for (int i=0;i<n;i++) parent[i]=i;
    }
    int find(int x){
        while (parent[x]!=x){ parent[x]=parent[parent[x]]; x=parent[x]; } // compress
        return x;
    }
    bool unite(int a,int b){                // 'union' is a reserved keyword in C++
        int ra=find(a), rb=find(b);
        if (ra==rb) return false;               // already same set (edge forms a cycle)
        if (rank[ra]<rank[rb]){ int t=ra; ra=rb; rb=t; }
        parent[rb]=ra;                          // smaller under larger
        if (rank[ra]==rank[rb]) rank[ra]++;
        count--;                                // one fewer component
        return true;
    }
};

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]                  # compress
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                         # already same set (edge forms a cycle)
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                     # smaller under larger
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1                          # one fewer component
        return True

class DSU {
    parent: number[];
    rank: number[];
    count: number;

    constructor(n: number) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
        this.count = n;
    }

    find(x: number): number {
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];                  // compress
        }
        return x;
    }

    union(a: number, b: number): boolean {
        let ra = this.find(a), rb = this.find(b);
        if (ra === rb) return false;              // already same set (edge forms a cycle)
        if (this.rank[ra] < this.rank[rb]) { [ra, rb] = [rb, ra]; }
        this.parent[rb] = ra;                     // smaller under larger
        if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
        this.count--;                             // one fewer component
        return true;
    }
}

int lowerBound(int[] a, int target){       // first index with a[i] >= target
    int lo = 0, hi = a.length;              // [lo, hi) half-open
    while (lo < hi){
        int mid = lo + (hi - lo)/2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;                              // insertion point; == length if none
}

int lowerBound(vector<int>& a, int target){       // first index with a[i] >= target
    int lo = 0, hi = a.size();              // [lo, hi) half-open
    while (lo < hi){
        int mid = lo + (hi - lo)/2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;                              // insertion point; == length if none
}

def lower_bound(a, target):       # first index with a[i] >= target
    lo, hi = 0, len(a)            # [lo, hi) half-open
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo                     # insertion point; == length if none

function lowerBound(a: number[], target: number): number {       // first index with a[i] >= target
    let lo = 0, hi = a.length;              // [lo, hi) half-open
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;                              // insertion point; == length if none
}

// smallest speed so Koko finishes all piles within h hours
int minEatingSpeed(int[] piles, int h){
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);
    while (lo < hi){
        int mid = lo + (hi - lo)/2;
        if (feasible(piles, mid, h)) hi = mid;   // can do it ⇒ try slower
        else lo = mid + 1;                       // too slow ⇒ speed up
    }
    return lo;                                   // smallest feasible speed
}
boolean feasible(int[] piles, int speed, int h){
    long hours = 0;
    for (int p : piles) hours += (p + speed - 1) / speed;  // ceil
    return hours <= h;
}

// smallest speed so Koko finishes all piles within h hours
int minEatingSpeed(vector<int>& piles, int h){
    int lo = 1, hi = 0;
    for (int p : piles) hi = max(hi, p);
    while (lo < hi){
        int mid = lo + (hi - lo)/2;
        if (feasible(piles, mid, h)) hi = mid;   // can do it ⇒ try slower
        else lo = mid + 1;                       // too slow ⇒ speed up
    }
    return lo;                                   // smallest feasible speed
}
bool feasible(vector<int>& piles, int speed, int h){
    long long hours = 0;
    for (int p : piles) hours += (p + speed - 1) / speed;  // ceil
    return hours <= h;
}

def min_eating_speed(piles, h):
    # smallest speed so Koko finishes all piles within h hours
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(piles, mid, h):
            hi = mid                              # can do it ⇒ try slower
        else:
            lo = mid + 1                          # too slow ⇒ speed up
    return lo                                     # smallest feasible speed

def feasible(piles, speed, h):
    hours = 0
    for p in piles:
        hours += (p + speed - 1) // speed         # ceil
    return hours <= h

// smallest speed so Koko finishes all piles within h hours
function minEatingSpeed(piles: number[], h: number): number {
    let lo = 1, hi = 0;
    for (const p of piles) hi = Math.max(hi, p);
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (feasible(piles, mid, h)) hi = mid;   // can do it ⇒ try slower
        else lo = mid + 1;                       // too slow ⇒ speed up
    }
    return lo;                                   // smallest feasible speed
}
function feasible(piles: number[], speed: number, h: number): boolean {
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / speed);   // ceil
    return hours <= h;
}

int findKthLargest(int[] nums, int k){
    PriorityQueue<Integer> min = new PriorityQueue<>();  // keeps k largest
    for (int x : nums){
        min.offer(x);
        if (min.size() > k) min.poll();     // evict the smallest
    }
    return min.peek();                       // kth largest overall
}

int findKthLargest(vector<int>& nums, int k){
    priority_queue<int, vector<int>, greater<int>> minHeap;  // keeps k largest
    for (int x : nums){
        minHeap.push(x);
        if (minHeap.size() > (size_t)k) minHeap.pop();     // evict the smallest
    }
    return minHeap.top();                       // kth largest overall
}

def find_kth_largest(nums, k):
    heap = []                                # keeps k largest (min-heap)
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)              # evict the smallest
    return heap[0]                           # kth largest overall

function findKthLargest(nums: number[], k: number): number {
    const min: number[] = [];               // keeps k largest
    for (const x of nums) {
        min.push(x);
        min.sort((a, b) => a - b);
        if (min.length > k) min.shift();     // evict the smallest
    }
    return min[0];                           // kth largest overall
}

ListNode mergeKLists(ListNode[] lists){
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b)->a.val-b.val);
    for (ListNode l : lists) if (l!=null) pq.offer(l);
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!pq.isEmpty()){
        ListNode n = pq.poll();
        tail.next = n; tail = n;
        if (n.next != null) pq.offer(n.next);
    }
    return dummy.next;
}

ListNode* mergeKLists(vector<ListNode*>& lists){
    auto cmp = [](ListNode* a, ListNode* b){ return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    for (ListNode* l : lists) if (l != nullptr) pq.push(l);
    ListNode dummy(0), *tail = &dummy;
    while (!pq.empty()){
        ListNode* n = pq.top(); pq.pop();
        tail->next = n; tail = n;
        if (n->next != nullptr) pq.push(n->next);
    }
    return dummy.next;
}

def merge_k_lists(lists):
    heap = []
    for i, l in enumerate(lists):
        if l is not None:
            heapq.heappush(heap, (l.val, i, l))     # tie-break with index (nodes aren't comparable)
    dummy = ListNode(0)
    tail = dummy
    counter = len(heap)
    while heap:
        val, idx, n = heapq.heappop(heap)
        tail.next = n
        tail = n
        if n.next is not None:
            counter += 1
            heapq.heappush(heap, (n.next.val, counter, n.next))
    return dummy.next

function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
    const pq: ListNode[] = [];
    for (const l of lists) if (l !== null) pq.push(l);
    pq.sort((a, b) => a.val - b.val);
    const dummy = new ListNode(0);
    let tail = dummy;
    while (pq.length) {
        const n = pq.shift()!;
        tail.next = n; tail = n;
        if (n.next !== null) {
            pq.push(n.next);
            pq.sort((a, b) => a.val - b.val);
        }
    }
    return dummy.next;
}

PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // max-heap, lower half
PriorityQueue<Integer> hi = new PriorityQueue<>();                          // min-heap, upper half
void add(int x){
    lo.offer(x); hi.offer(lo.poll());              // funnel through to keep order
    if (hi.size() > lo.size()) lo.offer(hi.poll()); // rebalance sizes
}
double median(){ return lo.size()>hi.size() ? lo.peek() : (lo.peek()+hi.peek())/2.0; }

priority_queue<int> lo;                              // max-heap, lower half
priority_queue<int, vector<int>, greater<int>> hi;   // min-heap, upper half
void add(int x){
    lo.push(x); hi.push(lo.top()); lo.pop();          // funnel through to keep order
    if (hi.size() > lo.size()){ lo.push(hi.top()); hi.pop(); } // rebalance sizes
}
double median(){ return lo.size()>hi.size() ? lo.top() : (lo.top()+hi.top())/2.0; }

lo = []   # max-heap, lower half (store negated values)
hi = []   # min-heap, upper half

def add(x):
    heapq.heappush(lo, -x)
    heapq.heappush(hi, -heapq.heappop(lo))            # funnel through to keep order
    if len(hi) > len(lo):
        heapq.heappush(lo, -heapq.heappop(hi))        # rebalance sizes

def median():
    if len(lo) > len(hi):
        return -lo[0]
    return (-lo[0] + hi[0]) / 2.0

const lo: number[] = [];   // max-heap, lower half
const hi: number[] = [];   // min-heap, upper half

function add(x: number): void {
    lo.push(x); lo.sort((a, b) => b - a);
    hi.push(lo.shift()!); hi.sort((a, b) => a - b);   // funnel through to keep order
    if (hi.length > lo.length) {
        lo.push(hi.shift()!);
        lo.sort((a, b) => b - a);                      // rebalance sizes
    }
}

function median(): number {
    return lo.length > hi.length ? lo[0] : (lo[0] + hi[0]) / 2.0;
}

int[] twoSum(int[] a, int target){        // a sorted ascending
    int lo = 0, hi = a.length - 1;
    while (lo < hi){
        int sum = a[lo] + a[hi];
        if (sum == target) return new int[]{lo, hi};
        else if (sum < target) lo++;      // need larger → move left pointer up
        else hi--;                        // need smaller → move right pointer down
    }
    return new int[]{-1,-1};
}

vector<int> twoSum(vector<int>& a, int target){        // a sorted ascending
    int lo = 0, hi = a.size() - 1;
    while (lo < hi){
        int sum = a[lo] + a[hi];
        if (sum == target) return {lo, hi};
        else if (sum < target) lo++;      // need larger → move left pointer up
        else hi--;                        // need smaller → move right pointer down
    }
    return {-1, -1};
}

def two_sum(a, target):        # a sorted ascending
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return [lo, hi]
        elif s < target:
            lo += 1             # need larger → move left pointer up
        else:
            hi -= 1             # need smaller → move right pointer down
    return [-1, -1]

function twoSum(a: number[], target: number): number[] {        // a sorted ascending
    let lo = 0, hi = a.length - 1;
    while (lo < hi) {
        const sum = a[lo] + a[hi];
        if (sum === target) return [lo, hi];
        else if (sum < target) lo++;      // need larger → move left pointer up
        else hi--;                        // need smaller → move right pointer down
    }
    return [-1, -1];
}

boolean hasCycle(ListNode head){
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null){
        slow = slow.next; fast = fast.next.next;   // 1x vs 2x speed
        if (slow == fast) return true;             // they meet inside a loop
    }
    return false;
}

bool hasCycle(ListNode* head){
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr){
        slow = slow->next; fast = fast->next->next;   // 1x vs 2x speed
        if (slow == fast) return true;                // they meet inside a loop
    }
    return false;
}

def has_cycle(head):
    slow, fast = head, head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next                # 1x vs 2x speed
        if slow == fast:
            return True                       # they meet inside a loop
    return False

function hasCycle(head: ListNode | null): boolean {
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow!.next; fast = fast.next.next;   // 1x vs 2x speed
        if (slow === fast) return true;              // they meet inside a loop
    }
    return false;
}

void sortColors(int[] a){
    int low = 0, mid = 0, high = a.length - 1;
    while (mid <= high){
        if (a[mid]==0) swap(a, low++, mid++);
        else if (a[mid]==1) mid++;
        else swap(a, mid, high--);         // 2 → send to the back
    }
}

void sortColors(vector<int>& a){
    int low = 0, mid = 0, high = a.size() - 1;
    while (mid <= high){
        if (a[mid]==0) swap(a[low++], a[mid++]);
        else if (a[mid]==1) mid++;
        else swap(a[mid], a[high--]);         // 2 → send to the back
    }
}

def sort_colors(a):
    low, mid, high = 0, 0, len(a) - 1
    while mid <= high:
        if a[mid] == 0:
            a[low], a[mid] = a[mid], a[low]
            low += 1
            mid += 1
        elif a[mid] == 1:
            mid += 1
        else:
            a[mid], a[high] = a[high], a[mid]        # 2 → send to the back
            high -= 1

function sortColors(a: number[]): void {
    let low = 0, mid = 0, high = a.length - 1;
    while (mid <= high) {
        if (a[mid] === 0) {
            [a[low], a[mid]] = [a[mid], a[low]];
            low++; mid++;
        } else if (a[mid] === 1) {
            mid++;
        } else {
            [a[mid], a[high]] = [a[high], a[mid]];    // 2 → send to the back
            high--;
        }
    }
}

long countPairs(int[] a, int[] b, int target){    // both sorted
    long count = 0; int j = b.length - 1;
    for (int i = 0; i < a.length; i++){
        while (j >= 0 && a[i] + b[j] > target) j--;
        count += (j + 1);                          // b[0..j] all pair with a[i]
    }
    return count;
}

long long countPairs(vector<int>& a, vector<int>& b, int target){    // both sorted
    long long count = 0; int j = b.size() - 1;
    for (int i = 0; i < (int)a.size(); i++){
        while (j >= 0 && a[i] + b[j] > target) j--;
        count += (j + 1);                          // b[0..j] all pair with a[i]
    }
    return count;
}

def count_pairs(a, b, target):    # both sorted
    count = 0
    j = len(b) - 1
    for i in range(len(a)):
        while j >= 0 and a[i] + b[j] > target:
            j -= 1
        count += (j + 1)                          # b[0..j] all pair with a[i]
    return count

function countPairs(a: number[], b: number[], target: number): number {    // both sorted
    let count = 0;
    let j = b.length - 1;
    for (let i = 0; i < a.length; i++) {
        while (j >= 0 && a[i] + b[j] > target) j--;
        count += (j + 1);                          // b[0..j] all pair with a[i]
    }
    return count;
}

int lengthOfLongestSubstring(String s){
    int[] last = new int[128]; Arrays.fill(last, -1);
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++){
        char c = s.charAt(right);
        if (last[c] >= left) left = last[c] + 1;   // jump past the earlier copy
        last[c] = right;
        best = Math.max(best, right - left + 1);
    }
    return best;
}

int lengthOfLongestSubstring(string s){
    vector<int> last(128, -1);
    int left = 0, best = 0;
    for (int right = 0; right < (int)s.length(); right++){
        char c = s[right];
        if (last[c] >= left) left = last[c] + 1;   // jump past the earlier copy
        last[c] = right;
        best = max(best, right - left + 1);
    }
    return best;
}

def length_of_longest_substring(s):
    last = [-1] * 128
    left = best = 0
    for right, c in enumerate(s):
        if last[ord(c)] >= left:
            left = last[ord(c)] + 1        # jump past the earlier copy
        last[ord(c)] = right
        best = max(best, right - left + 1)
    return best

function lengthOfLongestSubstring(s: string): number {
    const last = new Array(128).fill(-1);
    let left = 0, best = 0;
    for (let right = 0; right < s.length; right++) {
        const c = s.charCodeAt(right);
        if (last[c] >= left) left = last[c] + 1;   // jump past the earlier copy
        last[c] = right;
        best = Math.max(best, right - left + 1);
    }
    return best;
}

int maxSum(int[] a, int k){
    int sum = 0, best;
    for (int i = 0; i < k; i++) sum += a[i];
    best = sum;
    for (int i = k; i < a.length; i++){
        sum += a[i] - a[i-k];        // slide: add new, drop oldest
        best = Math.max(best, sum);
    }
    return best;
}

int maxSum(vector<int>& a, int k){
    int sum = 0, best;
    for (int i = 0; i < k; i++) sum += a[i];
    best = sum;
    for (int i = k; i < (int)a.size(); i++){
        sum += a[i] - a[i-k];        // slide: add new, drop oldest
        best = max(best, sum);
    }
    return best;
}

def max_sum(a, k):
    total = sum(a[:k])
    best = total
    for i in range(k, len(a)):
        total += a[i] - a[i - k]        # slide: add new, drop oldest
        best = max(best, total)
    return best

function maxSum(a: number[], k: number): number {
    let sum = 0;
    for (let i = 0; i < k; i++) sum += a[i];
    let best = sum;
    for (let i = k; i < a.length; i++) {
        sum += a[i] - a[i - k];        // slide: add new, drop oldest
        best = Math.max(best, sum);
    }
    return best;
}

// # subarrays with exactly K distinct = atMost(K) - atMost(K-1)
int atMost(int[] a, int k){
    Map<Integer,Integer> freq = new HashMap<>();
    int left = 0, count = 0;
    for (int right = 0; right < a.length; right++){
        freq.merge(a[right], 1, Integer::sum);
        while (freq.size() > k){
            int v = a[left++];
            if (freq.merge(v, -1, Integer::sum) == 0) freq.remove(v);
        }
        count += right - left + 1;   // # valid windows ending at right
    }
    return count;
}

// # subarrays with exactly K distinct = atMost(K) - atMost(K-1)
int atMost(vector<int>& a, int k){
    unordered_map<int,int> freq;
    int left = 0, count = 0;
    for (int right = 0; right < (int)a.size(); right++){
        freq[a[right]]++;
        while ((int)freq.size() > k){
            int v = a[left++];
            if (--freq[v] == 0) freq.erase(v);
        }
        count += right - left + 1;   // # valid windows ending at right
    }
    return count;
}

# # subarrays with exactly K distinct = at_most(K) - at_most(K-1)
def at_most(a, k):
    freq = {}
    left = count = 0
    for right in range(len(a)):
        freq[a[right]] = freq.get(a[right], 0) + 1
        while len(freq) > k:
            v = a[left]
            left += 1
            freq[v] -= 1
            if freq[v] == 0:
                del freq[v]
        count += right - left + 1   # # valid windows ending at right
    return count

// # subarrays with exactly K distinct = atMost(K) - atMost(K-1)
function atMost(a: number[], k: number): number {
    const freq = new Map<number, number>();
    let left = 0, count = 0;
    for (let right = 0; right < a.length; right++) {
        freq.set(a[right], (freq.get(a[right]) ?? 0) + 1);
        while (freq.size > k) {
            const v = a[left++];
            const c = freq.get(v)! - 1;
            if (c === 0) freq.delete(v); else freq.set(v, c);
        }
        count += right - left + 1;   // # valid windows ending at right
    }
    return count;
}

int[] dailyTemperatures(int[] t){
    int n = t.length; int[] res = new int[n];
    Deque<Integer> st = new ArrayDeque<>();   // indices, temps decreasing down the stack
    for (int i = 0; i < n; i++){
        while (!st.isEmpty() && t[i] > t[st.peek()]){
            int j = st.pop();
            res[j] = i - j;                   // i is j's next-warmer day
        }
        st.push(i);
    }
    return res;                               // unresolved stay 0
}

vector<int> dailyTemperatures(vector<int>& t){
    int n = t.size(); vector<int> res(n, 0);
    deque<int> st;   // indices, temps decreasing down the stack
    for (int i = 0; i < n; i++){
        while (!st.empty() && t[i] > t[st.back()]){
            int j = st.back(); st.pop_back();
            res[j] = i - j;                   // i is j's next-warmer day
        }
        st.push_back(i);
    }
    return res;                               // unresolved stay 0
}

def daily_temperatures(t):
    n = len(t)
    res = [0] * n
    st = []                                    # indices, temps decreasing down the stack
    for i in range(n):
        while st and t[i] > t[st[-1]]:
            j = st.pop()
            res[j] = i - j                     # i is j's next-warmer day
        st.append(i)
    return res                                 # unresolved stay 0

function dailyTemperatures(t: number[]): number[] {
    const n = t.length;
    const res = new Array(n).fill(0);
    const st: number[] = [];   // indices, temps decreasing down the stack
    for (let i = 0; i < n; i++) {
        while (st.length && t[i] > t[st[st.length - 1]]) {
            const j = st.pop()!;
            res[j] = i - j;                   // i is j's next-warmer day
        }
        st.push(i);
    }
    return res;                               // unresolved stay 0
}

int largestRectangleArea(int[] h){
    int n = h.length, best = 0;
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i <= n; i++){
        int cur = (i == n) ? 0 : h[i];          // sentinel flushes the stack
        while (!st.isEmpty() && h[st.peek()] >= cur){
            int height = h[st.pop()];
            int width  = st.isEmpty() ? i : i - st.peek() - 1;
            best = Math.max(best, height * width);
        }
        st.push(i);
    }
    return best;
}

int largestRectangleArea(vector<int>& h){
    int n = h.size(), best = 0;
    deque<int> st;
    for (int i = 0; i <= n; i++){
        int cur = (i == n) ? 0 : h[i];          // sentinel flushes the stack
        while (!st.empty() && h[st.back()] >= cur){
            int height = h[st.back()]; st.pop_back();
            int width  = st.empty() ? i : i - st.back() - 1;
            best = max(best, height * width);
        }
        st.push_back(i);
    }
    return best;
}

def largest_rectangle_area(h):
    n = len(h)
    best = 0
    st = []
    for i in range(n + 1):
        cur = 0 if i == n else h[i]             # sentinel flushes the stack
        while st and h[st[-1]] >= cur:
            height = h[st.pop()]
            width = i if not st else i - st[-1] - 1
            best = max(best, height * width)
        st.append(i)
    return best

function largestRectangleArea(h: number[]): number {
    const n = h.length;
    let best = 0;
    const st: number[] = [];
    for (let i = 0; i <= n; i++) {
        const cur = (i === n) ? 0 : h[i];          // sentinel flushes the stack
        while (st.length && h[st[st.length - 1]] >= cur) {
            const height = h[st.pop()!];
            const width = st.length === 0 ? i : i - st[st.length - 1] - 1;
            best = Math.max(best, height * width);
        }
        st.push(i);
    }
    return best;
}

int subarraySum(int[] nums, int k){
    Map<Integer,Integer> seen = new HashMap<>();
    seen.put(0, 1);                       // empty prefix
    int sum = 0, count = 0;
    for (int x : nums){
        sum += x;
        count += seen.getOrDefault(sum - k, 0);  // a prior prefix closes a k-sum here
        seen.merge(sum, 1, Integer::sum);
    }
    return count;
}

int subarraySum(vector<int>& nums, int k){
    unordered_map<int,int> seen;
    seen[0] = 1;                       // empty prefix
    int sum = 0, count = 0;
    for (int x : nums){
        sum += x;
        count += seen.count(sum - k) ? seen[sum - k] : 0;  // a prior prefix closes a k-sum here
        seen[sum]++;
    }
    return count;
}

def subarray_sum(nums, k):
    seen = {0: 1}                       # empty prefix
    total = count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)  # a prior prefix closes a k-sum here
        seen[total] = seen.get(total, 0) + 1
    return count

function subarraySum(nums: number[], k: number): number {
    const seen = new Map<number, number>();
    seen.set(0, 1);                       // empty prefix
    let sum = 0, count = 0;
    for (const x of nums) {
        sum += x;
        count += seen.get(sum - k) ?? 0;  // a prior prefix closes a k-sum here
        seen.set(sum, (seen.get(sum) ?? 0) + 1);
    }
    return count;
}

// P[i+1][j+1] = sum of the rectangle from (0,0) to (i,j)
int[][] P = new int[m+1][n+1];
for (int i=0;i<m;i++)
    for (int j=0;j<n;j++)
        P[i+1][j+1] = a[i][j] + P[i][j+1] + P[i+1][j] - P[i][j];
// sum of rows [r1,r2], cols [c1,c2]:
int sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1];

// P[i+1][j+1] = sum of the rectangle from (0,0) to (i,j)
vector<vector<int>> P(m+1, vector<int>(n+1, 0));
for (int i=0;i<m;i++)
    for (int j=0;j<n;j++)
        P[i+1][j+1] = a[i][j] + P[i][j+1] + P[i+1][j] - P[i][j];
// sum of rows [r1,r2], cols [c1,c2]:
int sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1];

# P[i+1][j+1] = sum of the rectangle from (0,0) to (i,j)
P = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
    for j in range(n):
        P[i+1][j+1] = a[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]
# sum of rows [r1,r2], cols [c1,c2]:
total = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

// P[i+1][j+1] = sum of the rectangle from (0,0) to (i,j)
const P: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
        P[i+1][j+1] = a[i][j] + P[i][j+1] + P[i+1][j] - P[i][j];
// sum of rows [r1,r2], cols [c1,c2]:
const sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1];

int[] diff = new int[n+1];
void addRange(int l, int r, int val){ diff[l] += val; diff[r+1] -= val; }
int[] build(){ int[] a=new int[n]; int run=0;
    for (int i=0;i<n;i++){ run += diff[i]; a[i]=run; } return a; }

std::vector<int> diff(n+1, 0);
void addRange(int l, int r, int val){ diff[l] += val; diff[r+1] -= val; }
std::vector<int> build(){ std::vector<int> a(n); int run=0;
    for (int i=0;i<n;i++){ run += diff[i]; a[i]=run; } return a; }

diff = [0] * (n + 1)

def add_range(l, r, val):
    diff[l] += val
    diff[r + 1] -= val

def build():
    a = [0] * n
    run = 0
    for i in range(n):
        run += diff[i]
        a[i] = run
    return a

const diff: number[] = new Array(n + 1).fill(0);
function addRange(l: number, r: number, val: number): void { diff[l] += val; diff[r + 1] -= val; }
function build(): number[] {
    const a: number[] = new Array(n).fill(0);
    let run = 0;
    for (let i = 0; i < n; i++) { run += diff[i]; a[i] = run; }
    return a;
}

int coinChange(int[] coins, int amount){
    int[] dp = new int[amount+1];
    Arrays.fill(dp, amount+1);           // "infinity"
    dp[0] = 0;                           // base: 0 coins make 0
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = Math.min(dp[a], dp[a-c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

int coinChange(std::vector<int>& coins, int amount){
    std::vector<int> dp(amount+1, amount+1);   // "infinity"
    dp[0] = 0;                                 // base: 0 coins make 0
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = std::min(dp[a], dp[a-c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

def coin_change(coins, amount):
    dp = [amount + 1] * (amount + 1)   # "infinity"
    dp[0] = 0                          # base: 0 coins make 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] > amount else dp[amount]

function coinChange(coins: number[], amount: number): number {
    const dp: number[] = new Array(amount + 1).fill(amount + 1);   // "infinity"
    dp[0] = 0;                                                     // base: 0 coins make 0
    for (let a = 1; a <= amount; a++)
        for (const c of coins)
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

int change(int amount, int[] coins){
    int[] dp = new int[amount+1]; dp[0] = 1;
    for (int c : coins)                   // coin outer ⇒ order-independent combos
        for (int a = c; a <= amount; a++)
            dp[a] += dp[a-c];
    return dp[amount];
}

int change(int amount, std::vector<int>& coins){
    std::vector<int> dp(amount+1, 0); dp[0] = 1;
    for (int c : coins)                   // coin outer ⇒ order-independent combos
        for (int a = c; a <= amount; a++)
            dp[a] += dp[a-c];
    return dp[amount];
}

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:                       # coin outer ⇒ order-independent combos
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

function change(amount: number, coins: number[]): number {
    const dp: number[] = new Array(amount + 1).fill(0);
    dp[0] = 1;
    for (const c of coins)                // coin outer ⇒ order-independent combos
        for (let a = c; a <= amount; a++)
            dp[a] += dp[a - c];
    return dp[amount];
}

int knapsack(int[] w, int[] v, int W){
    int[] dp = new int[W+1];
    for (int i = 0; i < w.length; i++)
        for (int c = W; c >= w[i]; c--)          // DOWNWARD ⇒ item used at most once
            dp[c] = Math.max(dp[c], dp[c-w[i]] + v[i]);
    return dp[W];
}

int knapsack(std::vector<int>& w, std::vector<int>& v, int W){
    std::vector<int> dp(W+1, 0);
    for (size_t i = 0; i < w.size(); i++)
        for (int c = W; c >= w[i]; c--)          // DOWNWARD ⇒ item used at most once
            dp[c] = std::max(dp[c], dp[c-w[i]] + v[i]);
    return dp[W];
}

def knapsack(w, v, W):
    dp = [0] * (W + 1)
    for i in range(len(w)):
        for c in range(W, w[i] - 1, -1):    # DOWNWARD ⇒ item used at most once
            dp[c] = max(dp[c], dp[c - w[i]] + v[i])
    return dp[W]

function knapsack(w: number[], v: number[], W: number): number {
    const dp: number[] = new Array(W + 1).fill(0);
    for (let i = 0; i < w.length; i++)
        for (let c = W; c >= w[i]; c--)          // DOWNWARD ⇒ item used at most once
            dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
    return dp[W];
}

int maxSubArray(int[] a){
    int best = a[0], cur = a[0];
    for (int i = 1; i < a.length; i++){
        cur = Math.max(a[i], cur + a[i]);   // extend previous or restart at a[i]
        best = Math.max(best, cur);
    }
    return best;
}

int maxSubArray(std::vector<int>& a){
    int best = a[0], cur = a[0];
    for (size_t i = 1; i < a.size(); i++){
        cur = std::max(a[i], cur + a[i]);   // extend previous or restart at a[i]
        best = std::max(best, cur);
    }
    return best;
}

def max_sub_array(a):
    best = cur = a[0]
    for i in range(1, len(a)):
        cur = max(a[i], cur + a[i])     # extend previous or restart at a[i]
        best = max(best, cur)
    return best

function maxSubArray(a: number[]): number {
    let best = a[0], cur = a[0];
    for (let i = 1; i < a.length; i++) {
        cur = Math.max(a[i], cur + a[i]);   // extend previous or restart at a[i]
        best = Math.max(best, cur);
    }
    return best;
}

int numDecodings(String s){
    if (s.charAt(0)=='0') return 0;
    int prev2 = 1, prev1 = 1;
    for (int i = 1; i < s.length(); i++){
        int cur = 0;
        if (s.charAt(i) != '0') cur += prev1;                     // take 1 digit
        int two = (s.charAt(i-1)-'0')*10 + (s.charAt(i)-'0');
        if (two >= 10 && two <= 26) cur += prev2;                  // take 2 digits
        prev2 = prev1; prev1 = cur;
    }
    return prev1;
}

int numDecodings(std::string s){
    if (s[0]=='0') return 0;
    int prev2 = 1, prev1 = 1;
    for (size_t i = 1; i < s.size(); i++){
        int cur = 0;
        if (s[i] != '0') cur += prev1;                            // take 1 digit
        int two = (s[i-1]-'0')*10 + (s[i]-'0');
        if (two >= 10 && two <= 26) cur += prev2;                 // take 2 digits
        prev2 = prev1; prev1 = cur;
    }
    return prev1;
}

def num_decodings(s):
    if s[0] == '0':
        return 0
    prev2, prev1 = 1, 1
    for i in range(1, len(s)):
        cur = 0
        if s[i] != '0':
            cur += prev1                                   # take 1 digit
        two = int(s[i-1]) * 10 + int(s[i])
        if 10 <= two <= 26:
            cur += prev2                                   # take 2 digits
        prev2, prev1 = prev1, cur
    return prev1

function numDecodings(s: string): number {
    if (s[0] === '0') return 0;
    let prev2 = 1, prev1 = 1;
    for (let i = 1; i < s.length; i++) {
        let cur = 0;
        if (s[i] !== '0') cur += prev1;                          // take 1 digit
        const two = (s.charCodeAt(i - 1) - 48) * 10 + (s.charCodeAt(i) - 48);
        if (two >= 10 && two <= 26) cur += prev2;                // take 2 digits
        prev2 = prev1; prev1 = cur;
    }
    return prev1;
}

int lcs(String a, String b){
    int m = a.length(), n = b.length();
    int[][] dp = new int[m+1][n+1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (a.charAt(i-1)==b.charAt(j-1))
                     ? dp[i-1][j-1] + 1                       // chars match
                     : Math.max(dp[i-1][j], dp[i][j-1]);      // drop one side
    return dp[m][n];
}

int lcs(const std::string& a, const std::string& b){
    int m = a.size(), n = b.size();
    std::vector<std::vector<int>> dp(m+1, std::vector<int>(n+1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = (a[i-1]==b[j-1])
                     ? dp[i-1][j-1] + 1                       // chars match
                     : std::max(dp[i-1][j], dp[i][j-1]);      // drop one side
    return dp[m][n];
}

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i-1][j-1] + 1 if a[i-1] == b[j-1]      # chars match
                        else max(dp[i-1][j], dp[i][j-1]))         # drop one side
    return dp[m][n]

function lcs(a: string, b: string): number {
    const m = a.length, n = b.length;
    const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++)
        for (let j = 1; j <= n; j++)
            dp[i][j] = (a[i - 1] === b[j - 1])
                     ? dp[i - 1][j - 1] + 1                        // chars match
                     : Math.max(dp[i - 1][j], dp[i][j - 1]);       // drop one side
    return dp[m][n];
}

int editDistance(String a, String b){
    int m=a.length(), n=b.length();
    int[][] dp = new int[m+1][n+1];
    for (int i=0;i<=m;i++) dp[i][0]=i;      // delete all
    for (int j=0;j<=n;j++) dp[0][j]=j;      // insert all
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            dp[i][j] = (a.charAt(i-1)==b.charAt(j-1))
                     ? dp[i-1][j-1]
                     : 1 + Math.min(dp[i-1][j-1],             // replace
                              Math.min(dp[i-1][j], dp[i][j-1]));// delete / insert
    return dp[m][n];
}

int editDistance(const std::string& a, const std::string& b){
    int m=a.size(), n=b.size();
    std::vector<std::vector<int>> dp(m+1, std::vector<int>(n+1, 0));
    for (int i=0;i<=m;i++) dp[i][0]=i;      // delete all
    for (int j=0;j<=n;j++) dp[0][j]=j;      // insert all
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            dp[i][j] = (a[i-1]==b[j-1])
                     ? dp[i-1][j-1]
                     : 1 + std::min(dp[i-1][j-1],              // replace
                              std::min(dp[i-1][j], dp[i][j-1]));// delete / insert
    return dp[m][n];
}

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                       # delete all
    for j in range(n + 1):
        dp[0][j] = j                       # insert all
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = (dp[i-1][j-1] if a[i-1] == b[j-1]
                        else 1 + min(dp[i-1][j-1],             # replace
                                     dp[i-1][j], dp[i][j-1]))   # delete / insert
    return dp[m][n]

function editDistance(a: string, b: string): number {
    const m = a.length, n = b.length;
    const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
    for (let i = 0; i <= m; i++) dp[i][0] = i;      // delete all
    for (let j = 0; j <= n; j++) dp[0][j] = j;      // insert all
    for (let i = 1; i <= m; i++)
        for (let j = 1; j <= n; j++)
            dp[i][j] = (a[i - 1] === b[j - 1])
                     ? dp[i - 1][j - 1]
                     : 1 + Math.min(dp[i - 1][j - 1],               // replace
                              Math.min(dp[i - 1][j], dp[i][j - 1])); // delete / insert
    return dp[m][n];
}

int numDistinct(String s, String t){
    int n = t.length();
    long[] dp = new long[n+1]; dp[0] = 1;
    for (int i = 1; i <= s.length(); i++)
        for (int j = n; j >= 1; j--)                  // reverse ⇒ 1D safe
            if (s.charAt(i-1) == t.charAt(j-1)) dp[j] += dp[j-1];
    return (int) dp[n];
}

int numDistinct(const std::string& s, const std::string& t){
    int n = t.size();
    std::vector<long long> dp(n+1, 0); dp[0] = 1;
    for (int i = 1; i <= (int)s.size(); i++)
        for (int j = n; j >= 1; j--)                  // reverse ⇒ 1D safe
            if (s[i-1] == t[j-1]) dp[j] += dp[j-1];
    return (int) dp[n];
}

def num_distinct(s, t):
    n = len(t)
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, len(s) + 1):
        for j in range(n, 0, -1):                      # reverse ⇒ 1D safe
            if s[i-1] == t[j-1]:
                dp[j] += dp[j-1]
    return dp[n]

function numDistinct(s: string, t: string): number {
    const n = t.length;
    const dp: number[] = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i <= s.length; i++)
        for (let j = n; j >= 1; j--)                  // reverse ⇒ 1D safe
            if (s[i - 1] === t[j - 1]) dp[j] += dp[j - 1];
    return dp[n];
}

boolean wordBreak(String s, List<String> dict){
    Set<String> words = new HashSet<>(dict);
    boolean[] dp = new boolean[s.length()+1]; dp[0] = true;
    for (int i = 1; i <= s.length(); i++)
        for (int j = 0; j < i; j++)
            if (dp[j] && words.contains(s.substring(j, i))){ dp[i] = true; break; }
    return dp[s.length()];
}

bool wordBreak(const std::string& s, std::vector<std::string>& dict){
    std::unordered_set<std::string> words(dict.begin(), dict.end());
    std::vector<bool> dp(s.size()+1, false); dp[0] = true;
    for (size_t i = 1; i <= s.size(); i++)
        for (size_t j = 0; j < i; j++)
            if (dp[j] && words.count(s.substr(j, i-j))){ dp[i] = true; break; }
    return dp[s.size()];
}

def word_break(s, dict_):
    words = set(dict_)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[len(s)]

function wordBreak(s: string, dict: string[]): boolean {
    const words = new Set(dict);
    const dp: boolean[] = new Array(s.length + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= s.length; i++)
        for (let j = 0; j < i; j++)
            if (dp[j] && words.has(s.substring(j, i))) { dp[i] = true; break; }
    return dp[s.length];
}

int lengthOfLIS(int[] nums){
    int[] tails = new int[nums.length]; int size = 0;
    for (int x : nums){
        int lo = 0, hi = size;
        while (lo < hi){ int mid=(lo+hi)/2; if (tails[mid]<x) lo=mid+1; else hi=mid; }
        tails[lo] = x;                          // patience sorting
        if (lo == size) size++;
    }
    return size;
}

int lengthOfLIS(std::vector<int>& nums){
    std::vector<int> tails(nums.size()); int size = 0;
    for (int x : nums){
        int lo = 0, hi = size;
        while (lo < hi){ int mid=(lo+hi)/2; if (tails[mid]<x) lo=mid+1; else hi=mid; }
        tails[lo] = x;                          // patience sorting
        if (lo == size) size++;
    }
    return size;
}

def length_of_lis(nums):
    tails = [0] * len(nums)
    size = 0
    for x in nums:
        lo, hi = 0, size
        while lo < hi:
            mid = (lo + hi) // 2
            if tails[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        tails[lo] = x                          # patience sorting
        if lo == size:
            size += 1
    return size

function lengthOfLIS(nums: number[]): number {
    const tails: number[] = new Array(nums.length).fill(0);
    let size = 0;
    for (const x of nums) {
        let lo = 0, hi = size;
        while (lo < hi) { const mid = (lo + hi) >> 1; if (tails[mid] < x) lo = mid + 1; else hi = mid; }
        tails[lo] = x;                          // patience sorting
        if (lo === size) size++;
    }
    return size;
}

int tsp(int[][] dist){
    int n = dist.length, FULL = (1 << n) - 1;
    int[][] dp = new int[1 << n][n];
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
    for (int i = 0; i < n; i++) dp[1 << i][i] = 0;      // start at each node
    for (int mask = 1; mask <= FULL; mask++)
        for (int i = 0; i < n; i++){
            if ((mask & (1 << i)) == 0) continue;         // i must be in mask
            for (int j = 0; j < n; j++){
                if ((mask & (1 << j)) != 0) continue;     // j not yet visited
                int nm = mask | (1 << j);
                dp[nm][j] = Math.min(dp[nm][j], dp[mask][i] + dist[i][j]);
            }
        }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) ans = Math.min(ans, dp[FULL][i]);
    return ans;
}

int tsp(std::vector<std::vector<int>>& dist){
    int n = dist.size(), FULL = (1 << n) - 1;
    std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INT_MAX / 2));
    for (int i = 0; i < n; i++) dp[1 << i][i] = 0;      // start at each node
    for (int mask = 1; mask <= FULL; mask++)
        for (int i = 0; i < n; i++){
            if ((mask & (1 << i)) == 0) continue;         // i must be in mask
            for (int j = 0; j < n; j++){
                if ((mask & (1 << j)) != 0) continue;     // j not yet visited
                int nm = mask | (1 << j);
                dp[nm][j] = std::min(dp[nm][j], dp[mask][i] + dist[i][j]);
            }
        }
    int ans = INT_MAX;
    for (int i = 0; i < n; i++) ans = std::min(ans, dp[FULL][i]);
    return ans;
}

def tsp(dist):
    n = len(dist)
    FULL = (1 << n) - 1
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    for i in range(n):
        dp[1 << i][i] = 0                              # start at each node
    for mask in range(1, FULL + 1):
        for i in range(n):
            if not (mask & (1 << i)):
                continue                                # i must be in mask
            for j in range(n):
                if mask & (1 << j):
                    continue                            # j not yet visited
                nm = mask | (1 << j)
                dp[nm][j] = min(dp[nm][j], dp[mask][i] + dist[i][j])
    return min(dp[FULL][i] for i in range(n))

function tsp(dist: number[][]): number {
    const n = dist.length, FULL = (1 << n) - 1;
    const dp: number[][] = Array.from({ length: 1 << n }, () => new Array(n).fill(Infinity));
    for (let i = 0; i < n; i++) dp[1 << i][i] = 0;      // start at each node
    for (let mask = 1; mask <= FULL; mask++)
        for (let i = 0; i < n; i++) {
            if ((mask & (1 << i)) === 0) continue;         // i must be in mask
            for (let j = 0; j < n; j++) {
                if ((mask & (1 << j)) !== 0) continue;     // j not yet visited
                const nm = mask | (1 << j);
                dp[nm][j] = Math.min(dp[nm][j], dp[mask][i] + dist[i][j]);
            }
        }
    let ans = Infinity;
    for (let i = 0; i < n; i++) ans = Math.min(ans, dp[FULL][i]);
    return ans;
}

int maxMeetings(int[][] iv){
    Arrays.sort(iv, (a,b) -> a[1] - b[1]);      // earliest finish first
    int count = 0, end = Integer.MIN_VALUE;
    for (int[] m : iv)
        if (m[0] >= end){ count++; end = m[1]; } // take it if it starts after last end
    return count;
}

int maxMeetings(std::vector<std::vector<int>>& iv){
    std::sort(iv.begin(), iv.end(), [](const std::vector<int>& a, const std::vector<int>& b){
        return a[1] < b[1];                     // earliest finish first
    });
    int count = 0, end = INT_MIN;
    for (auto& m : iv)
        if (m[0] >= end){ count++; end = m[1]; } // take it if it starts after last end
    return count;
}

def max_meetings(iv):
    iv.sort(key=lambda m: m[1])            # earliest finish first
    count, end = 0, float('-inf')
    for m in iv:
        if m[0] >= end:                    # take it if it starts after last end
            count += 1
            end = m[1]
    return count

function maxMeetings(iv: number[][]): number {
    iv.sort((a, b) => a[1] - b[1]);        // earliest finish first
    let count = 0, end = -Infinity;
    for (const m of iv)
        if (m[0] >= end) { count++; end = m[1]; }  // take it if it starts after last end
    return count;
}

int jump(int[] a){
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < a.length - 1; i++){
        farthest = Math.max(farthest, i + a[i]);   // best reach from this layer
        if (i == curEnd){ jumps++; curEnd = farthest; }  // must jump; extend layer
    }
    return jumps;
}

int jump(std::vector<int>& a){
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i < (int)a.size() - 1; i++){
        farthest = std::max(farthest, i + a[i]);   // best reach from this layer
        if (i == curEnd){ jumps++; curEnd = farthest; }  // must jump; extend layer
    }
    return jumps;
}

def jump(a):
    jumps = cur_end = farthest = 0
    for i in range(len(a) - 1):
        farthest = max(farthest, i + a[i])     # best reach from this layer
        if i == cur_end:                        # must jump; extend layer
            jumps += 1
            cur_end = farthest
    return jumps

function jump(a: number[]): number {
    let jumps = 0, curEnd = 0, farthest = 0;
    for (let i = 0; i < a.length - 1; i++) {
        farthest = Math.max(farthest, i + a[i]);   // best reach from this layer
        if (i === curEnd) { jumps++; curEnd = farthest; }  // must jump; extend layer
    }
    return jumps;
}

class Trie {
    private final Trie[] next = new Trie[26];
    private boolean end;
    void insert(String w){
        Trie node = this;
        for (char c : w.toCharArray()){
            int i = c - 'a';
            if (node.next[i] == null) node.next[i] = new Trie();
            node = node.next[i];
        }
        node.end = true;
    }
    boolean search(String w){ Trie n = walk(w); return n != null && n.end; }
    boolean startsWith(String p){ return walk(p) != null; }
    private Trie walk(String s){
        Trie node = this;
        for (char c : s.toCharArray()){
            node = node.next[c - 'a'];
            if (node == null) return null;
        }
        return node;
    }
}

class Trie {
private:
    Trie* next[26] = {nullptr};
    bool end = false;

    Trie* walk(const std::string& s){
        Trie* node = this;
        for (char c : s){
            node = node->next[c - 'a'];
            if (node == nullptr) return nullptr;
        }
        return node;
    }

public:
    void insert(const std::string& w){
        Trie* node = this;
        for (char c : w){
            int i = c - 'a';
            if (node->next[i] == nullptr) node->next[i] = new Trie();
            node = node->next[i];
        }
        node->end = true;
    }
    bool search(const std::string& w){ Trie* n = walk(w); return n != nullptr && n->end; }
    bool startsWith(const std::string& p){ return walk(p) != nullptr; }
};

class Trie:
    def __init__(self):
        self.next = [None] * 26
        self.end = False

    def insert(self, w):
        node = self
        for c in w:
            i = ord(c) - ord('a')
            if node.next[i] is None:
                node.next[i] = Trie()
            node = node.next[i]
        node.end = True

    def search(self, w):
        n = self._walk(w)
        return n is not None and n.end

    def starts_with(self, p):
        return self._walk(p) is not None

    def _walk(self, s):
        node = self
        for c in s:
            node = node.next[ord(c) - ord('a')]
            if node is None:
                return None
        return node

class Trie {
    private next: (Trie | null)[] = new Array(26).fill(null);
    private end = false;

    insert(w: string): void {
        let node: Trie = this;
        for (const c of w) {
            const i = c.charCodeAt(0) - 'a'.charCodeAt(0);
            if (node.next[i] === null) node.next[i] = new Trie();
            node = node.next[i]!;
        }
        node.end = true;
    }
    search(w: string): boolean { const n = this.walk(w); return n !== null && n.end; }
    startsWith(p: string): boolean { return this.walk(p) !== null; }
    private walk(s: string): Trie | null {
        let node: Trie | null = this;
        for (const c of s) {
            node = node.next[c.charCodeAt(0) - 'a'.charCodeAt(0)];
            if (node === null) return null;
        }
        return node;
    }
}

int strStr(String text, String pat){
    int m = pat.length(); int[] lps = new int[m];  // longest proper prefix=suffix
    for (int i=1,len=0; i<m; ){
        if (pat.charAt(i)==pat.charAt(len)) lps[i++] = ++len;
        else if (len>0) len = lps[len-1];
        else lps[i++] = 0;
    }
    for (int i=0,j=0; i<text.length(); ){
        if (text.charAt(i)==pat.charAt(j)){ i++; j++; if (j==m) return i-m; }
        else if (j>0) j = lps[j-1];                 // reuse matched prefix, no re-scan
        else i++;
    }
    return -1;
}

int strStr(const std::string& text, const std::string& pat){
    int m = pat.size(); std::vector<int> lps(m, 0);  // longest proper prefix=suffix
    for (int i=1,len=0; i<m; ){
        if (pat[i]==pat[len]) lps[i++] = ++len;
        else if (len>0) len = lps[len-1];
        else lps[i++] = 0;
    }
    for (int i=0,j=0; i<(int)text.size(); ){
        if (text[i]==pat[j]){ i++; j++; if (j==m) return i-m; }
        else if (j>0) j = lps[j-1];                  // reuse matched prefix, no re-scan
        else i++;
    }
    return -1;
}

def str_str(text, pat):
    m = len(pat)
    lps = [0] * m                          # longest proper prefix=suffix
    i, length = 1, 0
    while i < m:
        if pat[i] == pat[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    i = j = 0
    while i < len(text):
        if text[i] == pat[j]:
            i += 1
            j += 1
            if j == m:
                return i - m
        elif j > 0:
            j = lps[j - 1]                 # reuse matched prefix, no re-scan
        else:
            i += 1
    return -1

function strStr(text: string, pat: string): number {
    const m = pat.length; const lps: number[] = new Array(m).fill(0);  // longest proper prefix=suffix
    for (let i = 1, len = 0; i < m; ) {
        if (pat[i] === pat[len]) lps[i++] = ++len;
        else if (len > 0) len = lps[len - 1];
        else lps[i++] = 0;
    }
    for (let i = 0, j = 0; i < text.length; ) {
        if (text[i] === pat[j]) { i++; j++; if (j === m) return i - m; }
        else if (j > 0) j = lps[j - 1];                 // reuse matched prefix, no re-scan
        else i++;
    }
    return -1;
}