fork download

copy

#include <bits/stdc++.h>
using namespace std;
 
// =====================================================================
//                               DP CLASSIC
//                     All Functions and Tricks
//             Used in ECPC and ACPC competitions and advanced cases
// =====================================================================
 
// Global constant used in many DP functions (modulo for combinatorics, etc.)
// You must define MOD before using any function that relies on it.
const long long MOD = 1000000007LL;
 
// --------------------------------------------
// 1) Fibonacci (with memoization / bottom-up)
// --------------------------------------------
/*
 * This section provides functions to compute Fibonacci numbers.
 * - fib(n): top-down memoized recursion (requires resetting fibMemo to -1).
 * - buildFib(n): bottom-up iterative, returns vector of fib[0..n].
 * - fibOptimized(n): space-optimized O(1) iterative.
 * - fibMatrix(n): matrix exponentiation O(log n) for large n.
 * Use fibOptimized for small n, fibMatrix for n > 1e7.
 * Note: global fibMemo must be reset using resetMemo().
 */
 
const int MAXN = 1e6 + 5;
long long fibMemo[MAXN];
 
/*
 * Function: fib (recursive memoized)
 * Description: Computes the n-th Fibonacci number using top-down DP with memoization.
 * Parameters:
 *   n - non-negative integer (index of Fibonacci number)
 * Returns: long long - the n-th Fibonacci number (F(0)=0, F(1)=1)
 * Time Complexity: O(n)
 * Space Complexity: O(n) for the memo array
 * Constraints: n < MAXN (1e6+5)
 * Notes: The global array fibMemo must be initialized to -1 before calling.
 *        Use resetMemo(fibMemo, MAXN) to reset.
 */
long long fib(int n) {
    if (n <= 1) return n;
    if (fibMemo[n] != -1) return fibMemo[n];
    return fibMemo[n] = fib(n - 1) + fib(n - 2);
}
 
/*
 * Function: buildFib (iterative)
 * Description: Builds the Fibonacci sequence up to the n-th term using bottom-up DP.
 * Parameters:
 *   n - non-negative integer (maximum index)
 * Returns: vector<long long> - fib[0..n] where fib[i] = i-th Fibonacci number
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 * Constraints: n >= 0
 * Notes: None
 */
vector<long long> buildFib(int n) {
    vector<long long> fib(n + 1);
    fib[0] = 0;
    if (n >= 1) fib[1] = 1;
    for (int i = 2; i <= n; i++) fib[i] = fib[i - 1] + fib[i - 2];
    return fib;
}
 
// --------------------------------------------
// 2) Knapsack (0/1)
// --------------------------------------------
/*
 * This section solves the classic 0/1 knapsack problem.
 * - knapsack01: standard DP with O(n*W) time and O(W) space.
 * - knapsack01ByValue: alternative when capacity W is huge but total value is small.
 * Both assume each item is used at most once.
 */
 
/*
 * Function: knapsack01
 * Description: Solves the 0/1 knapsack problem: maximize total value with a weight capacity.
 * Parameters:
 *   weight - vector<int> of item weights (size n)
 *   value  - vector<int> of item values  (size n)
 *   W      - int capacity of knapsack
 * Returns: long long - maximum total value achievable
 * Time Complexity: O(n * W)
 * Space Complexity: O(W) (using 1D DP array)
 * Constraints: n and W can be up to ~10^4; weight[i] >= 0, W >= 0
 * Notes: Items are distinct (each used at most once).
 */
long long knapsack01(const vector<int>& weight, const vector<int>& value, int W) {
    int n = weight.size();
    vector<long long> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[W];
}
 
/*
 * Function: knapsack01ByValue
 * Description: Solves 0/1 knapsack when capacity W is very large but total value is small.
 *              It minimizes weight for each possible total value.
 * Parameters:
 *   weight - vector<int> of item weights (size n)
 *   value  - vector<int> of item values  (size n)
 *   W      - int capacity of knapsack
 * Returns: long long - maximum total value that fits in capacity W
 * Time Complexity: O(n * maxVal), where maxVal = sum of all values
 * Space Complexity: O(maxVal)
 * Constraints: sum of values should be manageable (e.g., <= 10^5) to avoid memory blow.
 * Notes: Use this when W is huge and values are small.
 */
long long knapsack01ByValue(const vector<int>& weight, const vector<int>& value, int W) {
    int n = weight.size();
    int maxVal = accumulate(value.begin(), value.end(), 0);
    const long long INF = 1e18;
    vector<long long> dp(maxVal + 1, INF);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int v = maxVal; v >= value[i]; v--) {
            dp[v] = min(dp[v], dp[v - value[i]] + weight[i]);
        }
    }
    long long ans = 0;
    for (int v = 0; v <= maxVal; v++) {
        if (dp[v] <= W) ans = v;
    }
    return ans;
}
 
// --------------------------------------------
// 3) Unbounded Knapsack (Complete)
// --------------------------------------------
/*
 * Solves the unbounded knapsack problem: each item can be taken any number of times.
 * - knapsackUnbounded: O(n*W) time, O(W) space.
 */
 
long long knapsackUnbounded(const vector<int>& weight, const vector<int>& value, int W) {
    int n = weight.size();
    vector<long long> dp(W + 1, 0);
    for (int w = 0; w <= W; w++) {
        for (int i = 0; i < n; i++) {
            if (w >= weight[i]) {
                dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
            }
        }
    }
    return dp[W];
}
 
// --------------------------------------------
// 4) LIS - Longest Increasing Subsequence
//    O(N log N) using binary search
// --------------------------------------------
/*
 * Functions for longest increasing subsequence and its variants.
 * - LIS: strict increasing, O(n log n).
 * - LNDS: non-decreasing (allows equal values), O(n log n).
 * - LISReconstruct: reconstructs one LIS using O(n^2) DP (for n ≤ 5000).
 * Use LIS for length only; use LISReconstruct for the actual sequence when n is small.
 */
 
int LIS(const vector<int>& arr) {
    vector<int> lis;
    for (int x : arr) {
        auto it = lower_bound(lis.begin(), lis.end(), x);
        if (it == lis.end()) lis.push_back(x);
        else *it = x;
    }
    return lis.size();
}
 
int LNDS(const vector<int>& arr) {
    vector<int> lis;
    for (int x : arr) {
        auto it = upper_bound(lis.begin(), lis.end(), x);
        if (it == lis.end()) lis.push_back(x);
        else *it = x;
    }
    return lis.size();
}
 
vector<int> LISReconstruct(const vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n, 1), parent(n, -1);
    int maxLen = 1, bestIdx = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            bestIdx = i;
        }
    }
    vector<int> seq;
    for (int i = bestIdx; i != -1; i = parent[i]) seq.push_back(arr[i]);
    reverse(seq.begin(), seq.end());
    return seq;
}
 
// --------------------------------------------
// 5) LCS - Longest Common Subsequence
// --------------------------------------------
/*
 * Computes the longest common subsequence between two strings.
 * - LCS: returns length.
 * - LCSReconstruct: returns the actual LCS string.
 * - LCS_Optimized: uses O(min(n,m)) space.
 * Time complexity O(n*m) for all; space O(n*m) for reconstruction, O(min) for optimized.
 * Use LCS_Optimized when memory is tight.
 */
 
int LCS(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
}
 
string LCSReconstruct(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    string res;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            res.push_back(a[i - 1]);
            i--, j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) i--;
        else j--;
    }
    reverse(res.begin(), res.end());
    return res;
}
 
// --------------------------------------------
// 6) Coin Change (minimum coins & number of ways)
// --------------------------------------------
/*
 * Solves coin change problems with unlimited supply.
 * - coinChangeMin: minimum number of coins to make amount.
 * - coinChangeWays: number of combinations to make amount (order does not matter).
 * Both use O(amount * |coins|) time and O(amount) space.
 */
 
int coinChangeMin(const vector<int>& coins, int amount) {
    const int INF = 1e9;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int c : coins) {
            if (i >= c) dp[i] = min(dp[i], dp[i - c] + 1);
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}
 
long long coinChangeWays(const vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins) {
        for (int i = c; i <= amount; i++) {
            dp[i] += dp[i - c];
        }
    }
    return dp[amount];
}
 
// --------------------------------------------
// 7) Matrix Chain Multiplication
// --------------------------------------------
/*
 * Computes minimum scalar multiplications to multiply a chain of matrices.
 * - matrixChainOrder: classic interval DP, O(n^3) time, O(n^2) space.
 * n = dims.size() - 1 (number of matrices).
 */
 
int matrixChainOrder(const vector<int>& dims) {
    int n = dims.size() - 1;
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}
 
// --------------------------------------------
// 8) Edit Distance (Levenshtein)
// --------------------------------------------
/*
 * Computes minimum operations (insert, delete, replace) to transform one string into another.
 * - editDistance: standard DP, O(n*m) time and space.
 * Can be optimized to O(min(n,m)) space, but not implemented here.
 */
 
int editDistance(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
        }
    }
    return dp[n][m];
}
 
// --------------------------------------------
// 9) DP on Grid / Number of Paths
// --------------------------------------------
/*
 * Counting paths in a grid (right/down moves) and variants.
 * - countPaths: number of paths from (0,0) to (n-1,m-1).
 * - countPathsWithObstacles: with blocked cells.
 * - minPathSum: minimum sum path.
 * All use O(n*m) time and space (can be optimized to O(m)).
 */
 
long long countPaths(int n, int m) {
    vector<vector<long long>> dp(n, vector<long long>(m, 0));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i > 0) dp[i][j] += dp[i - 1][j];
            if (j > 0) dp[i][j] += dp[i][j - 1];
        }
    }
    return dp[n - 1][m - 1];
}
 
long long countPathsWithObstacles(const vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) return 0;
    vector<vector<long long>> dp(n, vector<long long>(m, 0));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) continue;
            if (i > 0) dp[i][j] += dp[i - 1][j];
            if (j > 0) dp[i][j] += dp[i][j - 1];
        }
    }
    return dp[n - 1][m - 1];
}
 
int minPathSum(const vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dp(n, vector<int>(m, INT_MAX));
    dp[0][0] = grid[0][0];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + grid[i][j]);
            if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + grid[i][j]);
        }
    }
    return dp[n - 1][m - 1];
}
 
// --------------------------------------------
// 10) Maximum Subarray Sum (Kadane) and variants
// --------------------------------------------
/*
 * Kadane's algorithm and its extensions.
 * - maxSubarraySumKadane: classic O(n) for max sum (allows negative).
 * - maxSubarraySumAtMostK: max sum with length at most K, O(n log n) using multiset.
 * - maxSubarraySumAtMostK2: same but O(n) using deque.
 * - maxProductSubarray: maximum product subarray, O(n).
 */
 
long long maxSubarraySumKadane(const vector<long long>& arr) {
    long long maxEnd = 0, maxSum = LLONG_MIN;
    for (long long x : arr) {
        maxEnd = max(x, maxEnd + x);
        maxSum = max(maxSum, maxEnd);
    }
    return maxSum;
}
 
long long maxSubarraySumAtMostK(const vector<long long>& arr, int K) {
    int n = arr.size();
    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
    multiset<long long> ms;
    long long ans = LLONG_MIN;
    for (int i = 0; i <= n; i++) {
        if (i - K - 1 >= 0) ms.erase(ms.find(pref[i - K - 1]));
        if (!ms.empty()) ans = max(ans, pref[i] - *ms.begin());
        ms.insert(pref[i]);
    }
    return ans;
}
 
long long maxSubarraySumAtMostK2(const vector<long long>& arr, int K) {
    int n = arr.size();
    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
    deque<int> dq;
    dq.push_back(0);
    long long ans = LLONG_MIN;
    for (int i = 1; i <= n; i++) {
        while (!dq.empty() && dq.front() < i - K) dq.pop_front();
        ans = max(ans, pref[i] - pref[dq.front()]);
        while (!dq.empty() && pref[dq.back()] >= pref[i]) dq.pop_back();
        dq.push_back(i);
    }
    return ans;
}
 
long long maxProductSubarray(const vector<int>& nums) {
    long long maxProd = nums[0], minProd = nums[0], ans = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        long long a = maxProd * nums[i];
        long long b = minProd * nums[i];
        maxProd = max({1LL * nums[i], a, b});
        minProd = min({1LL * nums[i], a, b});
        ans = max(ans, maxProd);
    }
    return ans;
}
 
// --------------------------------------------
// 11) DP with Bitmask (TSP, Hamiltonian Path)
// --------------------------------------------
/*
 * Bitmask DP for problems with small n (n ≤ 20).
 * - tsp: Traveling Salesman Problem (min cost Hamiltonian cycle).
 * - countHamiltonianPaths: count number of Hamiltonian paths (directed graph).
 * - countHamiltonianPaths(src, dst): with fixed start/end.
 * Time O(2^n * n^2) or O(2^n * n).
 */
 
int tsp(int n, const vector<vector<int>>& dist) {
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    dp[1][0] = 0; // start from city 0
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            if (dp[mask][u] == INT_MAX) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    int fullMask = (1 << n) - 1;
    int ans = INT_MAX;
    for (int u = 0; u < n; u++) {
        if (dp[fullMask][u] != INT_MAX)
            ans = min(ans, dp[fullMask][u] + dist[u][0]);
    }
    return ans;
}
 
long long countHamiltonianPaths(int n, const vector<vector<int>>& adj) {
    vector<vector<long long>> dp(1 << n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) dp[1 << i][i] = 1;
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            if (dp[mask][u] == 0) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                if (!adj[u][v]) continue;
                dp[mask | (1 << v)][v] += dp[mask][u];
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) ans += dp[(1 << n) - 1][i];
    return ans;
}
 
long long countHamiltonianPaths(int n, int src, int dst, const vector<vector<int>>& adj) {
    vector<vector<long long>> dp(1 << n, vector<long long>(n, 0));
    dp[1 << src][src] = 1;
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u)) || dp[mask][u] == 0) continue;
            for (int v : adj[u]) {
                if (mask & (1 << v)) continue;
                dp[mask | (1 << v)][v] += dp[mask][u];
            }
        }
    }
    return dp[(1 << n) - 1][dst];
}
 
// --------------------------------------------
// 12) DP on Trees (Tree DP)
// --------------------------------------------
/*
 * Tree DP functions.
 * - dfsTreeDP: computes maximum independent set on a tree (global tree, dp0, dp1).
 * - dfsDiameter: computes tree diameter (longest path).
 * - dfsDown/dfsUp: rerooting DP to compute subtree contributions from all directions.
 * Use global adjacency list 'tree'.
 */
 
vector<vector<int>> tree;
vector<int> dp0, dp1; // dp0 = not taken, dp1 = taken
 
void dfsTreeDP(int u, int p) {
    dp1[u] = 1;
    for (int v : tree[u]) {
        if (v == p) continue;
        dfsTreeDP(v, u);
        dp0[u] += max(dp0[v], dp1[v]);
        dp1[u] += dp0[v];
    }
}
 
pair<int, int> dfsDiameter(int u, int p) {
    int max1 = 0, max2 = 0;
    for (int v : tree[u]) {
        if (v == p) continue;
        auto [d1, d2] = dfsDiameter(v, u);
        max1 = max(max1, d1 + 1);
        max2 = max(max2, d2);
    }
    return {max1, max(max2, max1 + max2)};
}
 
vector<long long> dpDown, dpUp, ansTree; // for rerooting
 
void dfsDown(int u, int p) {
    dpDown[u] = 1; // example: count nodes in subtree
    for (int v : tree[u]) {
        if (v == p) continue;
        dfsDown(v, u);
        dpDown[u] += dpDown[v];
    }
}
 
void dfsUp(int u, int p) {
    int deg = tree[u].size();
    vector<long long> pref(deg + 1, 0), suff(deg + 1, 0);
    for (int i = 0; i < deg; i++) {
        int v = tree[u][i];
        pref[i + 1] = pref[i] + (v == p ? dpUp[u] : dpDown[v]);
    }
    for (int i = deg - 1; i >= 0; i--) {
        int v = tree[u][i];
        suff[i] = suff[i + 1] + (v == p ? dpUp[u] : dpDown[v]);
    }
    for (int i = 0; i < deg; i++) {
        int v = tree[u][i];
        if (v == p) continue;
        dpUp[v] = 1 + pref[i] + suff[i + 1]; // combine all other branches
        dfsUp(v, u);
    }
}
// Usage: dfsDown(0, -1); dpUp[0] = 0; dfsUp(0, -1);
// answer for each node = dpDown[u] + dpUp[u] (or other definitions)
 
// --------------------------------------------
// 13) Digit DP
// --------------------------------------------
/*
 * Digit DP for counting numbers with certain digit sum or other properties.
 * - countDigitSum: counts numbers in [0, N] whose digit sum equals S.
 * - countDigitSumWithLeadingZero: counts numbers with exactly target occurrences of digit 1 (or any digit).
 * Uses memoization. Complexity O(len * sum * 2).
 * Note: N ≤ 1e18 (len ≤ 19).
 */
 
long long dpDigit[20][200][2];
string numStr;
 
long long solveDigitDP(int pos, int sum, int tight, int S) {
    if (pos == (int)numStr.size()) return sum == S;
    long long &ret = dpDigit[pos][sum][tight];
    if (ret != -1) return ret;
    ret = 0;
    int limit = tight ? numStr[pos] - '0' : 9;
    for (int d = 0; d <= limit; d++) {
        ret += solveDigitDP(pos + 1, sum + d, tight && (d == limit), S);
    }
    return ret;
}
 
long long countDigitSum(long long N, int S) {
    numStr = to_string(N);
    memset(dpDigit, -1, sizeof(dpDigit));
    return solveDigitDP(0, 0, 1, S);
}
 
// Variant with leading zeros and counting a specific digit (e.g., digit 1)
long long memoLead[20][20][2][2]; // [pos][cnt][tight][started]
 
long long solveDigitDPWithLeadingZero(int pos, int cnt, bool tight, bool started, int target, const string& num) {
    if (pos == (int)num.size()) return (started && cnt == target) ? 1 : 0;
    long long &ret = memoLead[pos][cnt][tight][started];
    if (ret != -1) return ret;
    ret = 0;
    int limit = tight ? num[pos] - '0' : 9;
    for (int d = 0; d <= limit; d++) {
        bool ntight = tight && (d == limit);
        bool nstarted = started || (d != 0);
        int add = (d == 1 && nstarted) ? 1 : 0;
        ret += solveDigitDPWithLeadingZero(pos + 1, cnt + add, ntight, nstarted, target, num);
    }
    return ret;
}
 
long long countDigitSumWithLeadingZero(long long N, int target) {
    string s = to_string(N);
    memset(memoLead, -1, sizeof(memoLead));
    return solveDigitDPWithLeadingZero(0, 0, true, false, target, s);
}
 
// --------------------------------------------
// 14) DP with Prefix Sum Optimization
// --------------------------------------------
/*
 * Optimizes DP transitions by using prefix sums to reduce time from O(K*n*limit) to O(K*n).
 * - dpPrefixOpt: counts ways to reach sum n using exactly K moves, each move adds 1..limit.
 * Complexity O(K*n), space O(n).
 */
 
long long dpPrefixOpt(int n, int K, int limit) {
    vector<long long> dp(n + 1, 0), pref(n + 1, 0);
    dp[0] = 1;
    for (int step = 0; step < K; step++) {
        for (int i = 1; i <= n; i++) pref[i] = (pref[i - 1] + dp[i]) % MOD;
        vector<long long> ndp(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            int l = max(0, i - limit);
            ndp[i] = (pref[i - 1] - (l > 0 ? pref[l - 1] : 0) + MOD) % MOD;
        }
        dp = ndp;
    }
    long long ans = 0;
    for (int i = 0; i <= n; i++) ans = (ans + dp[i]) % MOD;
    return ans;
}
 
// --------------------------------------------
// 15) DP + Sliding Window / Monotonic Queue
// --------------------------------------------
/*
 * Monotonic queue optimization for DP with sliding window maximum.
 * - maxSumWithWindow: example (may need verification; provided as template).
 * Usually used for problems like "max sum of subsequence with gap constraint".
 * Complexity O(n).
 */
 
long long maxSumWithWindow(const vector<long long>& arr, int K) {
    int n = arr.size();
    vector<long long> dp(n + 1, 0);
    deque<int> dq;
    for (int i = 1; i <= n; i++) {
        if (!dq.empty() && dq.front() < i - K) dq.pop_front();
        dp[i] = dp[i - 1] + arr[i - 1];
        if (!dq.empty()) dp[i] = max(dp[i], dp[dq.front()] + arr[i - 1]);
        while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
        dq.push_back(i);
    }
    return dp[n];
}
 
// --------------------------------------------
// 16) DP + Bitmask Subsets (SOS DP)
// --------------------------------------------
/*
 * Sum Over Subsets DP (SOS DP) to compute f[mask] = sum_{sub ⊆ mask} a[sub].
 * - sosDP: in-place transform, O(n * 2^n) time, O(2^n) space.
 * Used for subset convolution and related problems.
 */
 
vector<int> sosDP(const vector<int>& a) {
    int n = a.size();
    int N = 1 << n;
    vector<int> f = a;
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < N; mask++) {
            if (mask & (1 << i)) f[mask] += f[mask ^ (1 << i)];
        }
    }
    return f;
}
 
// --------------------------------------------
// 17) DP with Monotonic Stack (for histograms etc.)
// --------------------------------------------
/*
 * Largest rectangle in histogram using monotonic stack.
 * - largestRectangleArea: O(n) time, O(n) space.
 */
 
long long largestRectangleArea(const vector<int>& heights) {
    int n = heights.size();
    vector<int> left(n), right(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && heights[st.top()] >= heights[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && heights[st.top()] >= heights[i]) st.pop();
        right[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, 1LL * heights[i] * (right[i] - left[i] - 1));
    }
    return ans;
}
 
// --------------------------------------------
// 18) DP + Combinatorics (NCR, precomputation)
// --------------------------------------------
/*
 * Precomputation of factorials and inverse factorials for nCr modulo MOD.
 * - initComb(): must be called once before using nCr.
 * - nCr(n,r): returns C(n,r) mod MOD in O(1).
 * MOD must be prime.
 */
 
const int MAXC = 1000005;
long long fact[MAXC], invFact[MAXC];
 
long long modPow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}
 
void initComb() {
    fact[0] = 1;
    for (int i = 1; i < MAXC; i++) fact[i] = fact[i - 1] * i % MOD;
    invFact[MAXC - 1] = modPow(fact[MAXC - 1], MOD - 2);
    for (int i = MAXC - 2; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % MOD;
}
 
long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}
 
// --------------------------------------------
// 19) DP for Longest Palindromic Subsequence
// --------------------------------------------
/*
 * Longest Palindromic Subsequence (LPS) length.
 * - LPS: interval DP, O(n^2) time and space.
 */
 
int LPS(const string& s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}
 
// --------------------------------------------
// 20) DP for Longest Common Substring (LCSubstr)
// --------------------------------------------
/*
 * Longest common substring (contiguous) between two strings.
 * - longestCommonSubstring: O(n*m) time and space.
 */
 
int longestCommonSubstring(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                ans = max(ans, dp[i][j]);
            }
        }
    }
    return ans;
}
 
// --------------------------------------------
// 21) DP with Rolling Array (Space Optimization)
// --------------------------------------------
/*
 * Space-optimized iterative Fibonacci.
 * - fibOptimized: O(1) space, O(n) time.
 */
 
long long fibOptimized(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}
 
// --------------------------------------------
// 22) DP for Partition Problems
// --------------------------------------------
/*
 * Partition into two subsets with equal sum.
 * - canPartition: O(n * target) time, O(target) space.
 */
 
bool canPartition(const vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum & 1) return false;
    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int x : nums) {
        for (int s = target; s >= x; s--) {
            if (dp[s - x]) dp[s] = true;
        }
    }
    return dp[target];
}
 
// --------------------------------------------
// 23) DP + Divide and Conquer Optimization
// --------------------------------------------
/*
 * Divide and Conquer DP optimization for DP of the form:
 * dp[i][j] = min_{k < j} (dp[i-1][k] + cost(k, j))
 * when the optimal split point is monotonic.
 * - compute: template function; adapt cost function accordingly.
 * Complexity O(m * n log n) for each row.
 */
 
void computeDC(int l, int r, int optL, int optR, int k, vector<vector<long long>>& dp, const vector<long long>& pref) {
    if (l > r) return;
    int mid = (l + r) / 2;
    int bestOpt = optL;
    long long bestVal = LLONG_MAX;
    for (int i = optL; i <= min(optR, mid - 1); i++) {
        long long cost = dp[k - 1][i] + (pref[mid] - pref[i]) * (pref[mid] - pref[i]); // example cost
        if (cost < bestVal) {
            bestVal = cost;
            bestOpt = i;
        }
    }
    dp[k][mid] = bestVal;
    computeDC(l, mid - 1, optL, bestOpt, k, dp, pref);
    computeDC(mid + 1, r, bestOpt, optR, k, dp, pref);
}
 
// --------------------------------------------
// 24) DP + Knuth Optimization (mentioned)
// --------------------------------------------
// Knuth optimization can be applied when quadrangle inequality holds.
// Not implemented as a separate function.
 
// --------------------------------------------
// 25) DP + Bitmask (Counting subsets with sum)
// --------------------------------------------
/*
 * Count subsets with a given sum (0/1 knapsack counting).
 * - countSubsetsWithSum: O(n * target), O(target).
 */
 
long long countSubsetsWithSum(const vector<int>& arr, int target) {
    int n = arr.size();
    vector<long long> dp(target + 1, 0);
    dp[0] = 1;
    for (int x : arr) {
        for (int s = target; s >= x; s--) {
            dp[s] += dp[s - x];
        }
    }
    return dp[target];
}
 
// --------------------------------------------
// 26) DP + Meet-in-the-Middle (for large N up to 40)
// --------------------------------------------
/*
 * Meet-in-the-Middle for subset sum problems when n ≤ 40.
 * - getSubsetSums: generates all subset sums of a half-array.
 * - countSubsetsWithSumMITM: counts subsets with exact target.
 * Complexity O(2^(n/2) log 2^(n/2)).
 */
 
vector<long long> getSubsetSums(const vector<int>& arr) {
    vector<long long> sums;
    int n = arr.size();
    for (int mask = 0; mask < (1 << n); mask++) {
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) sum += arr[i];
        }
        sums.push_back(sum);
    }
    return sums;
}
 
long long countSubsetsWithSumMITM(const vector<int>& arr, int target) {
    int n = arr.size();
    vector<int> left(arr.begin(), arr.begin() + n / 2);
    vector<int> right(arr.begin() + n / 2, arr.end());
    vector<long long> L = getSubsetSums(left), R = getSubsetSums(right);
    sort(R.begin(), R.end());
    long long ans = 0;
    for (long long s : L) {
        ans += upper_bound(R.begin(), R.end(), target - s) - lower_bound(R.begin(), R.end(), target - s);
    }
    return ans;
}
 
// --------------------------------------------
// 27) DP + Matrix Exponentiation (for linear recurrences)
// --------------------------------------------
/*
 * Matrix exponentiation for linear recurrences.
 * - Matrix struct for n x n matrices with multiplication modulo MOD.
 * - matPow: exponentiation.
 * - fibMatrix: Fibonacci using matrix exponentiation O(log n).
 * - linearRecurrence: computes n-th term of a 2nd order recurrence.
 */
 
struct Matrix {
    vector<vector<long long>> mat;
    int n;
    Matrix(int n, bool identity = false) : n(n), mat(n, vector<long long>(n, 0)) {
        if (identity) for (int i = 0; i < n; i++) mat[i][i] = 1;
    }
    Matrix operator*(const Matrix& other) const {
        Matrix res(n);
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                if (mat[i][k] == 0) continue;
                for (int j = 0; j < n; j++) {
                    res.mat[i][j] = (res.mat[i][j] + mat[i][k] * other.mat[k][j]) % MOD;
                }
            }
        }
        return res;
    }
};
 
Matrix matPow(Matrix base, long long exp) {
    Matrix res(base.n, true);
    while (exp > 0) {
        if (exp & 1) res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}
 
long long fibMatrix(int n) {
    if (n <= 1) return n;
    Matrix base(2);
    base.mat = {{1, 1}, {1, 0}};
    Matrix res = matPow(base, n - 1);
    return res.mat[0][0];
}
 
long long linearRecurrence(long long n, long long a, long long b, long long f0, long long f1) {
    if (n == 0) return f0;
    if (n == 1) return f1;
    Matrix base(2);
    base.mat = {{a, b}, {1, 0}};
    Matrix res = matPow(base, n - 1);
    return (res.mat[0][0] * f1 + res.mat[0][1] * f0) % MOD;
}
 
// --------------------------------------------
// 28) DP for "Minimum Operations" (like min steps to reduce to 1)
// --------------------------------------------
/*
 * Minimum steps to reduce n to 1 using operations: subtract 1, divide by 2 (if even), divide by 3 (if divisible by 3).
 * - minStepsToOne: O(n) time and space.
 */
 
int minStepsToOne(int n) {
    vector<int> dp(n + 1, 1e9);
    dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 == 0) dp[i] = min(dp[i], dp[i / 2] + 1);
        if (i % 3 == 0) dp[i] = min(dp[i], dp[i / 3] + 1);
    }
    return dp[n];
}
 
// --------------------------------------------
// 29) DP for "Jump Game" / "Minimum Jumps to Reach End"
// --------------------------------------------
/*
 * Minimum number of jumps to reach the end.
 * - minJumps: O(n^2) DP (for small n).
 * - minJumpsGreedy: O(n) greedy for reachable arrays.
 */
 
int minJumps(const vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, INT_MAX);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] == INT_MAX) continue;
        for (int j = i + 1; j <= min(n - 1, i + nums[i]); j++) {
            dp[j] = min(dp[j], dp[i] + 1);
        }
    }
    return dp[n - 1];
}
 
int minJumpsGreedy(const vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return 0;
    int jumps = 0, currEnd = 0, farthest = 0;
    for (int i = 0; i < n - 1; i++) {
        farthest = max(farthest, i + nums[i]);
        if (i == currEnd) {
            jumps++;
            currEnd = farthest;
        }
    }
    return jumps;
}
 
// --------------------------------------------
// 30) DP for "Word Break" (Can be segmented)
// --------------------------------------------
/*
 * Determines if a string can be segmented into dictionary words.
 * - wordBreak: O(n^2) time with hash set.
 */
 
bool wordBreak(const string& s, const vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}
 
// --------------------------------------------
// 31) DP for "Number of Ways to Decode" (Leetcode 91)
// --------------------------------------------
/*
 * Counts ways to decode a digit string (A=1,...,Z=26).
 * - numDecodings: O(n) time and space.
 */
 
int numDecodings(const string& s) {
    int n = s.size();
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] != '0') dp[i] += dp[i - 1];
        if (i >= 2) {
            int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}
 
// --------------------------------------------
// 32) DP + KMP Automaton (for avoiding patterns)
// --------------------------------------------
/*
 * Count strings of length n over lowercase letters that do NOT contain a given pattern.
 * - buildKMPAutomaton: builds transition table.
 * - countStringsWithoutPattern: DP using automaton.
 * Complexity O(n * m * 26).
 */
 
vector<array<int, 26>> buildKMPAutomaton(const string& pat) {
    int m = pat.size();
    vector<array<int, 26>> aut(m + 1);
    vector<int> pi(m, 0);
    for (int i = 1; i < m; i++) {
        int j = pi[i - 1];
        while (j > 0 && pat[i] != pat[j]) j = pi[j - 1];
        if (pat[i] == pat[j]) j++;
        pi[i] = j;
    }
    for (int i = 0; i <= m; i++) {
        for (int c = 0; c < 26; c++) {
            if (i < m && pat[i] == 'a' + c) aut[i][c] = i + 1;
            else if (i == 0) aut[i][c] = 0;
            else aut[i][c] = aut[pi[i - 1]][c];
        }
    }
    return aut;
}
 
long long countStringsWithoutPattern(int n, const string& pat, long long MOD) {
    auto aut = buildKMPAutomaton(pat);
    int m = pat.size();
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int state = 0; state < m; state++) {
            for (int c = 0; c < 26; c++) {
                int nxt = aut[state][c];
                if (nxt == m) continue;
                dp[i + 1][nxt] = (dp[i + 1][nxt] + dp[i][state]) % MOD;
            }
        }
    }
    long long ans = 0;
    for (int state = 0; state < m; state++) ans = (ans + dp[n][state]) % MOD;
    return ans;
}
 
// --------------------------------------------
// 33) DP for "Distinct Subsequences"
// --------------------------------------------
/*
 * Count number of distinct subsequences (including empty) of a string.
 * - distinctSubsequences: O(n) time and space (using last occurrence).
 * Returns total distinct subsequences minus 1 (excluding empty).
 */
 
int distinctSubsequences(const string& s) {
    int n = s.size();
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    vector<int> last(26, -1);
    for (int i = 1; i <= n; i++) {
        dp[i] = (2 * dp[i - 1]) % MOD;
        int c = s[i - 1] - 'a';
        if (last[c] != -1) dp[i] = (dp[i] - dp[last[c] - 1] + MOD) % MOD;
        last[c] = i;
    }
    return dp[n] - 1; // exclude empty
}
 
// --------------------------------------------
// 34) DP for "Minimum Path Cover in DAG" (not implemented)
// --------------------------------------------
// (See bipartite matching for DAG path cover.)
 
// --------------------------------------------
// 35) DP + Topological Sort (DAG DP)
// --------------------------------------------
/*
 * Longest path in a weighted DAG.
 * - topologicalSort: computes topological order.
 * - dagLongestPath: returns maximum path sum (vertex weights).
 * Complexity O(V + E).
 */
 
vector<int> topo;
 
void topologicalSort(int n, vector<vector<int>>& adj) {
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++) for (int v : adj[u]) indeg[v]++;
    queue<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }
}
 
long long dagLongestPath(int n, vector<vector<int>>& adj, vector<int>& weight) {
    topologicalSort(n, adj);
    vector<long long> dp(n, 0);
    for (int u : topo) {
        for (int v : adj[u]) {
            dp[v] = max(dp[v], dp[u] + weight[v]);
        }
    }
    return *max_element(dp.begin(), dp.end());
}
 
// --------------------------------------------
// 36) DP + Game Theory (optimal play)
// --------------------------------------------
/*
 * Predict the winner in a game where players pick from ends.
 * - predictTheWinner: returns true if first player can win.
 * O(n^2) time and space.
 */
 
bool predictTheWinner(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = nums[i];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
        }
    }
    return dp[0][n - 1] >= 0;
}
 
// --------------------------------------------
// 37) DP + "Maximum Sum Rectangle in 2D" (Kadane on rows)
// --------------------------------------------
/*
 * Maximum sum sub-rectangle in a 2D matrix.
 * - maxSumRectangle: O(n^2 * m) time, O(m) space.
 * Works for both int and long long matrices (overloaded).
 */
 
long long maxSumRectangle(const vector<vector<int>>& mat) {
    int n = mat.size(), m = mat[0].size();
    long long best = LLONG_MIN;
    for (int top = 0; top < n; top++) {
        vector<long long> col(m, 0);
        for (int bottom = top; bottom < n; bottom++) {
            for (int j = 0; j < m; j++) col[j] += mat[bottom][j];
            long long cur = 0, mx = LLONG_MIN;
            for (int j = 0; j < m; j++) {
                cur = max(col[j], cur + col[j]);
                mx = max(mx, cur);
            }
            best = max(best, mx);
        }
    }
    return best;
}
 
// Overload for long long matrix
long long maxSumRectangle(const vector<vector<long long>>& matrix) {
    int n = matrix.size(), m = matrix[0].size();
    long long ans = LLONG_MIN;
    for (int top = 0; top < n; top++) {
        vector<long long> colSum(m, 0);
        for (int bottom = top; bottom < n; bottom++) {
            for (int j = 0; j < m; j++) colSum[j] += matrix[bottom][j];
            long long maxEnd = 0, maxSum = LLONG_MIN;
            for (int j = 0; j < m; j++) {
                maxEnd = max(colSum[j], maxEnd + colSum[j]);
                maxSum = max(maxSum, maxEnd);
            }
            ans = max(ans, maxSum);
        }
    }
    return ans;
}
 
// --------------------------------------------
// 38) DP + Catalan Numbers
// --------------------------------------------
/*
 * Compute n-th Catalan number using DP.
 * - catalan: O(n^2) time, O(n) space.
 * Catalan numbers grow fast; use long long for n ≤ 30.
 */
 
long long catalan(int n) {
    vector<long long> cat(n + 1, 0);
    cat[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            cat[i] += cat[j] * cat[i - j - 1];
        }
    }
    return cat[n];
}
 
// --------------------------------------------
// 39) DP for "Partition into K subarrays with min/max sum"
// --------------------------------------------
/*
 * Split array into k subarrays to minimize the maximum subarray sum.
 * - canPartitionKSubarrays: greedy check for a given target.
 * - splitArrayMinLargestSum: binary search on answer.
 * Complexity O(n log sum).
 */
 
bool canPartitionKSubarrays(const vector<int>& nums, int k, long long target) {
    int cnt = 1;
    long long sum = 0;
    for (int x : nums) {
        if (sum + x > target) {
            cnt++;
            sum = x;
        } else sum += x;
    }
    return cnt <= k;
}
 
long long splitArrayMinLargestSum(const vector<int>& nums, int k) {
    long long lo = *max_element(nums.begin(), nums.end());
    long long hi = accumulate(nums.begin(), nums.end(), 0LL);
    long long ans = hi;
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        if (canPartitionKSubarrays(nums, k, mid)) {
            ans = mid;
            hi = mid - 1;
        } else lo = mid + 1;
    }
    return ans;
}
 
// --------------------------------------------
// 40) DP + BFS/Shortest Path (count ways)
// --------------------------------------------
/*
 * Counting ways in grid using BFS/DP (same as countPaths).
 * - countWaysInGridWithBFS: just an alias.
 */
 
long long countWaysInGridWithBFS(int n, int m) {
    vector<vector<long long>> dp(n, vector<long long>(m, 0));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i > 0) dp[i][j] += dp[i - 1][j];
            if (j > 0) dp[i][j] += dp[i][j - 1];
        }
    }
    return dp[n - 1][m - 1];
}
 
// --------------------------------------------
// 41) DP + Floyd-Warshall (all-pairs shortest paths)
// --------------------------------------------
/*
 * All-pairs shortest paths in a graph (negative weights allowed, no negative cycles).
 * - floydWarshall: O(n^3) time, O(n^2) space.
 * Modifies dist matrix in-place.
 */
 
void floydWarshall(vector<vector<long long>>& dist) {
    int n = dist.size();
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != LLONG_MAX && dist[k][j] != LLONG_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}
 
// --------------------------------------------
// 42) DP + Bellman-Ford (shortest path with negative weights)
// --------------------------------------------
/*
 * Bellman-Ford for single-source shortest paths with negative edges.
 * - bellmanFord: O(VE) time, O(V) space.
 * Returns distances or empty vector if negative cycle detected.
 */
 
vector<long long> bellmanFord(int n, vector<tuple<int,int,long long>>& edges, int src) {
    vector<long long> dist(n, LLONG_MAX);
    dist[src] = 0;
    for (int i = 0; i < n - 1; i++) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
        }
    }
    for (auto [u, v, w] : edges) {
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
            return {};
        }
    }
    return dist;
}
 
// --------------------------------------------
// 43) DP + Grundy Numbers (impartial games)
// --------------------------------------------
/*
 * Compute Grundy numbers for combinatorial games.
 * - mex: minimum excluded value.
 * - grundy: for a single pile with given moves.
 * - grundyNumber: XOR of Grundy numbers for multiple piles.
 */
 
int mex(const vector<int>& v) {
    vector<bool> vis(v.size() + 1, false);
    for (int x : v) if (x < (int)vis.size()) vis[x] = true;
    for (int i = 0; i < (int)vis.size(); i++) if (!vis[i]) return i;
    return v.size();
}
 
int grundy(int n, vector<int>& moves) {
    vector<int> g(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        vector<int> reachable;
        for (int m : moves) {
            if (i >= m) reachable.push_back(g[i - m]);
        }
        g[i] = mex(reachable);
    }
    return g[n];
}
 
int grundyNumber(int piles[], int n, int maxMove) {
    vector<int> g(maxMove + 1, 0);
    for (int i = 1; i <= maxMove; i++) {
        vector<int> reachable;
        for (int move = 1; move <= i; move++) {
            reachable.push_back(g[i - move]);
        }
        g[i] = mex(reachable);
    }
    int xr = 0;
    for (int i = 0; i < n; i++) xr ^= g[piles[i]];
    return xr; // zero means losing
}
 
// --------------------------------------------
// 44) DP + Convex Hull Trick (CHT)
// --------------------------------------------
/*
 * Convex Hull Trick for DP optimization with linear functions.
 * Slopes must be monotonic. Supports min queries.
 * - Line: y = m*x + c.
 * - CHT: add lines (monotonic slopes), query min at x.
 * Use when DP transition is dp[i] = min_j (dp[j] + m_j * x_i + c_j).
 */
 
struct Line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
};
 
struct CHT {
    vector<Line> lines;
    int ptr = 0;
    bool bad(Line l1, Line l2, Line l3) {
        return (l3.c - l1.c) * (l1.m - l2.m) <= (l2.c - l1.c) * (l1.m - l3.m);
    }
    void addLine(Line l) {
        while (lines.size() >= 2 && bad(lines[lines.size()-2], lines.back(), l))
            lines.pop_back();
        lines.push_back(l);
    }
    long long query(long long x) {
        while (ptr + 1 < lines.size() && lines[ptr+1].eval(x) <= lines[ptr].eval(x))
            ptr++;
        return lines[ptr].eval(x);
    }
};
 
// --------------------------------------------
// 45) DP + Li Chao Tree (for min/max queries)
// --------------------------------------------
/*
 * Li Chao Tree for dynamic addition of lines and min/max queries over arbitrary x.
 * Supports discrete x-coordinates.
 * - LiChao: addLine, query.
 */
 
struct LiChao {
    struct Node {
        Line line;
        Node *left, *right;
        Node(Line l) : line(l), left(nullptr), right(nullptr) {}
    };
    Node* root;
    long long xL, xR;
    LiChao(long long l, long long r) : xL(l), xR(r), root(nullptr) {}
    void addLine(Line nw) { root = addLine(root, xL, xR, nw); }
    Node* addLine(Node* node, long long l, long long r, Line nw) {
        if (!node) return new Node(nw);
        long long mid = (l + r) / 2;
        Line lo = node->line, hi = nw;
        if (lo.eval(mid) > hi.eval(mid)) swap(node->line, nw);
        if (l == r) return node;
        if (nw.eval(l) < node->line.eval(l))
            node->left = addLine(node->left, l, mid, nw);
        else if (nw.eval(r) < node->line.eval(r))
            node->right = addLine(node->right, mid+1, r, nw);
        return node;
    }
    long long query(long long x) { return query(root, xL, xR, x); }
    long long query(Node* node, long long l, long long r, long long x) {
        if (!node) return LLONG_MAX;
        long long res = node->line.eval(x);
        if (l == r) return res;
        long long mid = (l + r) / 2;
        if (x <= mid) return min(res, query(node->left, l, mid, x));
        else return min(res, query(node->right, mid+1, r, x));
    }
};
 
// --------------------------------------------
// 46) DP + Alien Trick (Lagrangian relaxation)
// --------------------------------------------
/*
 * Alien trick to solve DP with exactly K items.
 * - solveWithPenalty: DP with penalty added per item.
 * - solveWithExactlyK: binary search on penalty.
 * Requires the DP to be convex.
 * Placeholder implementation; fill with actual DP.
 */
 
pair<long long, int> solveWithPenalty(int penalty) {
    // Placeholder: should return {max value, number of items}
    return {0, 0};
}
 
long long solveWithExactlyK(int k) {
    long long lo = -1e9, hi = 1e9, ans = 0;
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        auto [val, cnt] = solveWithPenalty(mid);
        if (cnt >= k) {
            ans = val + mid * k;
            lo = mid + 1;
        } else hi = mid - 1;
    }
    return ans;
}
 
// --------------------------------------------
// 47) DP + "Interval DP" (Burst Balloons, Palindrome cuts, etc.)
// --------------------------------------------
/*
 * Interval DP examples.
 * - maxCoinsBurstBalloons: Leetcode 312.
 * - minCutPalindrome: minimum cuts to partition into palindromes.
 * - longestValidParentheses: length of longest valid parentheses substring.
 */
 
int maxCoinsBurstBalloons(const vector<int>& nums) {
    int n = nums.size();
    vector<int> a(n + 2, 1);
    for (int i = 1; i <= n; i++) a[i] = nums[i - 1];
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
    for (int len = 1; len <= n; len++) {
        for (int l = 1; l <= n - len + 1; l++) {
            int r = l + len - 1;
            for (int k = l; k <= r; k++) {
                dp[l][r] = max(dp[l][r], dp[l][k - 1] + dp[k + 1][r] + a[l - 1] * a[k] * a[r + 1]);
            }
        }
    }
    return dp[1][n];
}
 
int minCutPalindrome(const string& s) {
    int n = s.size();
    vector<vector<bool>> isPal(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) isPal[i][i] = true;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && (len == 2 || isPal[i + 1][j - 1])) {
                isPal[i][j] = true;
            }
        }
    }
    vector<int> dp(n, INT_MAX);
    for (int i = 0; i < n; i++) {
        if (isPal[0][i]) dp[i] = 0;
        else {
            for (int j = 0; j < i; j++) {
                if (isPal[j + 1][i] && dp[j] + 1 < dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }
    return dp[n - 1];
}
 
int longestValidParentheses(const string& s) {
    int n = s.size();
    vector<int> dp(n, 0);
    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
            }
            ans = max(ans, dp[i]);
        }
    }
    return ans;
}
 
// --------------------------------------------
// 48) DP + "Ugly Numbers" (DP with prime factors)
// --------------------------------------------
/*
 * Find the n-th ugly number (factors only 2, 3, 5).
 * - nthUglyNumber: O(n) time, O(n) space.
 */
 
long long nthUglyNumber(int n) {
    vector<long long> ugly(n);
    ugly[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;
    for (int i = 1; i < n; i++) {
        long long next2 = ugly[p2] * 2;
        long long next3 = ugly[p3] * 3;
        long long next5 = ugly[p5] * 5;
        long long next = min({next2, next3, next5});
        ugly[i] = next;
        if (next == next2) p2++;
        if (next == next3) p3++;
        if (next == next5) p5++;
    }
    return ugly[n - 1];
}
 
// --------------------------------------------
// 49) DP + "Shortest Common Supersequence"
// --------------------------------------------
/*
 * Shortest string that contains both a and b as subsequences.
 * - shortestCommonSupersequence: O(n*m) time and space.
 */
 
string shortestCommonSupersequence(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
        }
    }
    string res;
    int i = n, j = m;
    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && a[i-1] == b[j-1]) {
            res.push_back(a[i-1]); i--; j--;
        } else if (i > 0 && (j == 0 || dp[i-1][j] <= dp[i][j-1])) {
            res.push_back(a[i-1]); i--;
        } else {
            res.push_back(b[j-1]); j--;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}
 
// --------------------------------------------
// 50) DP + Expected Steps in DAG
// --------------------------------------------
/*
 * Expected number of steps to reach goal in a probabilistic DAG.
 * - expectedSteps: assumes edges go forward, compute backwards.
 */
 
double expectedSteps(int n, vector<vector<double>>& trans) {
    vector<double> dp(n, 0);
    for (int u = n - 2; u >= 0; u--) {
        double sum = 0;
        for (int v = u + 1; v < n; v++) {
            sum += trans[u][v] * (1 + dp[v]);
        }
        dp[u] = sum;
    }
    return dp[0];
}
 
// --------------------------------------------
// 51) DP + "Count Subsets with Sum ≤ Target" (MITM)
// --------------------------------------------
/*
 * Count subsets with sum ≤ target using meet-in-the-middle.
 * - countSubsetsWithSumLE: O(2^(n/2) log 2^(n/2)).
 */
 
long long countSubsetsWithSumLE(const vector<int>& arr, int target) {
    int n = arr.size();
    int n1 = n / 2, n2 = n - n1;
    vector<int> L, R;
    for (int mask = 0; mask < (1 << n1); mask++) {
        int sum = 0;
        for (int i = 0; i < n1; i++) if (mask & (1 << i)) sum += arr[i];
        L.push_back(sum);
    }
    for (int mask = 0; mask < (1 << n2); mask++) {
        int sum = 0;
        for (int i = 0; i < n2; i++) if (mask & (1 << i)) sum += arr[n1 + i];
        R.push_back(sum);
    }
    sort(R.begin(), R.end());
    long long ans = 0;
    for (int x : L) {
        ans += upper_bound(R.begin(), R.end(), target - x) - R.begin();
    }
    return ans;
}
 
// --------------------------------------------
// 52) DP + "Zeta Transform" (SOS DP)
// --------------------------------------------
/*
 * Zeta transform (subset sum) - same as SOS DP.
 * - zetaTransform: in-place transform.
 */
 
vector<int> zetaTransform(vector<int> f) {
    int n = f.size();
    int bits = 0; while ((1 << bits) < n) bits++;
    for (int i = 0; i < bits; i++) {
        for (int mask = 0; mask < n; mask++) {
            if (mask & (1 << i))
                f[mask] += f[mask ^ (1 << i)];
        }
    }
    return f;
}
 
// --------------------------------------------
// 53) DP + "LCS Optimized Space"
// --------------------------------------------
/*
 * LCS with O(min(n,m)) space.
 * - LCS_Optimized: swaps to make second string shorter.
 */
 
int LCS_Optimized(const string& a, const string& b) {
    if (a.size() < b.size()) return LCS_Optimized(b, a);
    int n = a.size(), m = b.size();
    vector<int> dp(m + 1, 0), ndp(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        ndp[0] = 0;
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1]) ndp[j] = dp[j-1] + 1;
            else ndp[j] = max(dp[j], ndp[j-1]);
        }
        swap(dp, ndp);
    }
    return dp[m];
}
 
// --------------------------------------------
// 54) Utility Functions
// --------------------------------------------
/*
 * Common utility functions for DP:
 * - buildPrefix: 1D prefix sum.
 * - rangeSum: sum in [l,r].
 * - buildPrefix2D: 2D prefix sum.
 * - rectSum: rectangle sum.
 * - printDP: print 2D DP table (debugging).
 * - resetMemo: reset memo array to -1.
 */
 
vector<long long> buildPrefix(const vector<long long>& arr) {
    int n = arr.size();
    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
    return pref;
}
 
long long rangeSum(const vector<long long>& pref, int l, int r) {
    return pref[r + 1] - pref[l];
}
 
vector<vector<long long>> buildPrefix2D(const vector<vector<long long>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<long long>> pref(n + 1, vector<long long>(m + 1, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            pref[i + 1][j + 1] = grid[i][j] + pref[i][j + 1] + pref[i + 1][j] - pref[i][j];
        }
    }
    return pref;
}
 
long long rectSum(const vector<vector<long long>>& pref, int x1, int y1, int x2, int y2) {
    return pref[x2 + 1][y2 + 1] - pref[x1][y2 + 1] - pref[x2 + 1][y1] + pref[x1][y1];
}
 
template<typename T>
void printDP(const vector<vector<T>>& dp) {
    for (auto &row : dp) {
        for (auto &val : row) cout << val << ' ';
        cout << '\n';
    }
}
 
void resetMemo(long long memo[], int size) {
    for (int i = 0; i < size; i++) memo[i] = -1;
}
 
// --------------------------------------------
// 55) Additional: DP for "Can Partition K Subsets"
// --------------------------------------------
/*
 * Check if array can be partitioned into k subsets with equal sum.
 * - canPartitionKSubsets: bitmask DP, O(k * 2^n) or O(n * 2^n).
 */
 
bool canPartitionKSubsets(const vector<int>& nums, int k) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k != 0) return false;
    int target = sum / k;
    int n = nums.size();
    vector<int> dp(1 << n, -1);
    dp[0] = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == -1) continue;
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i)) && dp[mask] + nums[i] <= target) {
                int newMask = mask | (1 << i);
                int newSum = (dp[mask] + nums[i]) % target;
                if (dp[newMask] == -1) dp[newMask] = newSum;
            }
        }
    }
    return dp[(1 << n) - 1] == 0;
}
 
// --------------------------------------------
// 56) DP + "Max Sum of Non-Adjacent Elements" (House Robber)
// --------------------------------------------
/*
 * House Robber problems.
 * - houseRobber: linear array.
 * - houseRobberCircular: circular array (first and last adjacent).
 */
 
long long houseRobber(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    vector<long long> dp(n, 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[n - 1];
}
 
long long houseRobberCircular(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    vector<int> a(nums.begin(), nums.end() - 1);
    vector<int> b(nums.begin() + 1, nums.end());
    return max(houseRobber(a), houseRobber(b));
}
 
// --------------------------------------------
// 57) DP + "Distinct Subsequences" (count of t as subsequence of s)
// --------------------------------------------
/*
 * Count distinct subsequences of s that equal t.
 * - numDistinct: O(n*m) time and space.
 */
 
int numDistinct(const string& s, const string& t) {
    int n = s.size(), m = t.size();
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    for (int i = 0; i <= n; i++) dp[i][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            if (s[i - 1] == t[j - 1]) dp[i][j] += dp[i - 1][j - 1];
        }
    }
    return dp[n][m];
}
 
// =====================================================================
//                         EXAMPLE MAIN
// =====================================================================
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    // Example usage of some functions:
    vector<int> arr = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "LIS length = " << LIS(arr) << '\n';
 
    vector<int> weight = {2, 3, 4, 5};
    vector<int> value  = {3, 4, 5, 6};
    int W = 5;
    cout << "Knapsack max value = " << knapsack01(weight, value, W) << '\n';
 
    initComb(); // if using nCr
    cout << "Fib(10) = " << fibOptimized(10) << '\n';
 
    string s = "leetcode";
    vector<string> dict = {"leet", "code"};
    cout << "Word Break: " << wordBreak(s, dict) << '\n';
 
    vector<int> houses = {2, 7, 9, 3, 1};
    cout << "House Robber: " << houseRobber(houses) << '\n';
 
    vector<int> dims = {40, 20, 30, 10, 30};
    cout << "Matrix Chain Min Cost: " << matrixChainOrder(dims) << '\n';
 
    string pal = "aab";
    cout << "Min cuts for palindrome: " << minCutPalindrome(pal) << '\n';
 
    cout << "10th ugly number: " << nthUglyNumber(10) << '\n';
 
    return 0;
}