DSA — Data Structures & Algorithms

// vector push_back: amortized O(1) despite occasional O(n) reallocation
std::vector<int> v;
for (int i = 0; i < n; ++i) {
    v.push_back(i); // amortized O(1); capacity roughly doubles when full
}
// Total work for n pushes: 1+2+4+8+...+n ~ 2n = O(n) => O(1) amortized/op

T(n) = a * T(n / b) + f(n)     where a >= 1, b > 1

// O(n log n): outer loop n times, inner loop halves each time
for (int i = 0; i < n; ++i) {
    for (int j = 1; j < n; j *= 2) {
        // O(1) work
    }
}

std::vector<int> v;
std::cout << v.capacity() << "\n"; // 0
for (int i = 0; i < 10; ++i) {
    v.push_back(i);
    std::cout << "size=" << v.size() << " cap=" << v.capacity() << "\n";
}
// Reserve up front to avoid reallocations when the final size is known:
std::vector<int> v2;
v2.reserve(1000); // capacity = 1000, size = 0, no reallocation for 1000 pushes
v2.shrink_to_fit(); // non-binding request to release unused capacity

std::pair<int, std::string> p = {1, "one"};
auto [id, name] = p; // structured binding (C++17)

std::tuple<int, double, char> t{1, 2.5, 'x'};
auto [a, b, c] = t;

for (auto& [key, value] : someMap) { // works on any std::pair-like element
    // key, value bound directly, no .first/.second
}

// pair/tuple compare lexicographically by default — handy for custom sort keys
std::vector<std::pair<int,int>> v = {{2,1},{1,5},{1,2}};
std::sort(v.begin(), v.end()); // sorts by .first, then .second

std::deque<int> dq;
dq.push_back(1);
dq.push_front(2); // O(1), unlike vector's O(n) insert-at-front
std::stack<int> st;         // LIFO, default backing = deque
std::queue<int> q;          // FIFO, default backing = deque
std::stack<int, std::vector<int>> stV; // can swap backing container

// Min-heap of ints
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

// Custom comparator via lambda (needs decltype since lambda types are unique)
auto cmp = [](const std::pair<int,int>& a, const std::pair<int,int>& b) {
    return a.second > b.second; // min-heap by .second
};
std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, decltype(cmp)> pq(cmp);

// Custom comparator via struct (reusable, often cleaner)
struct Cmp {
    bool operator()(int a, int b) const { return a > b; } // min-heap
};
std::priority_queue<int, std::vector<int>, Cmp> pq2;

std::set<int> s = {5, 1, 3};
s.insert(2);
auto it = s.lower_bound(3); // first element >= 3 -> iterator to 3
auto it2 = s.upper_bound(3); // first element > 3 -> iterator to 5
s.erase(1); // O(log n)
bool found = s.count(3) > 0; // O(log n); count is 0 or 1 for set

std::multiset<int> ms = {1, 1, 2, 2, 2};
ms.erase(ms.find(2)); // erase ONE instance (erase(2) would remove ALL of them!)

std::map<std::string, int> freq;
freq["apple"]++; // operator[] default-constructs 0 if missing, then increments; O(log n)

for (auto& [word, count] : freq) { /* sorted by key */ }

auto it = freq.find("apple"); // O(log n), returns end() if missing
if (it != freq.end()) { /* found */ }

// operator[] vs find: operator[] INSERTS a default value if key is missing —
// dangerous for a read-only lookup, use find() or count() to avoid pollution
if (freq.count("banana")) { /* safe check, no insertion */ }

std::unordered_map<std::string, int> m;
m.reserve(1000);  // pre-size bucket array to reduce rehashing
m["x"] = 1;       // average O(1)

// Custom hash for a struct/pair key (unordered_map has no default hash for pair)
struct PairHash {
    size_t operator()(const std::pair<int,int>& p) const {
        return std::hash<long long>()(((long long)p.first << 32) ^ (unsigned int)p.second);
    }
};
std::unordered_map<std::pair<int,int>, int, PairHash> grid;

// Combining hashes (boost-style hash_combine idiom)
size_t combined = std::hash<int>()(a);
combined ^= std::hash<int>()(b) + 0x9e3779b9 + (combined << 6) + (combined >> 2);

std::bitset<32> b(13); // 00000000000000000000000000001101
b.set(4);              // set bit 4
b.reset(0);            // clear bit 0
bool has = b.test(2);  // check bit 2
size_t ones = b.count();  // number of set bits
std::string s = b.to_string();
unsigned long v = b.to_ulong();
std::bitset<32> c = b & std::bitset<32>(0xFF); // bitwise AND

std::vector<int> v = {5, 3, 1, 4, 1, 5, 9, 2, 6};

std::sort(v.begin(), v.end());                 // O(n log n), not stable
std::stable_sort(v.begin(), v.end());          // O(n log n), stable (preserves equal-key order)
std::sort(v.begin(), v.end(), std::greater<>()); // descending

bool found = std::binary_search(v.begin(), v.end(), 4); // O(log n), needs sorted range
auto lo = std::lower_bound(v.begin(), v.end(), 4); // first element >= 4
auto hi = std::upper_bound(v.begin(), v.end(), 4); // first element > 4
// [lo, hi) is the range of elements equal to 4

do {
    // visits all n! permutations in lexicographic order
} while (std::next_permutation(v.begin(), v.end()));

int sum = std::accumulate(v.begin(), v.end(), 0); // fold with initial value
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());

// Bit tricks (GCC/Clang builtins, extremely useful and fast)
int x = 44; // 0b101100
int popcount = __builtin_popcount(x);     // number of set bits -> 3
int leadingZeros = __builtin_clz(x);      // count leading zeros (32-bit)
int trailingZeros = __builtin_ctz(x);     // count trailing zeros -> 2

// C++17
int g = std::gcd(12, 18); // 6
int l = std::lcm(4, 6);   // 12

std::reverse(v.begin(), v.end());
auto maxIt = std::max_element(v.begin(), v.end());
auto [minIt, maxIt2] = std::minmax_element(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end()); // dedupe ADJACENT equal elements (sort first!)

bool twoSumSorted(std::vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int sum = a[lo] + a[hi];
        if (sum == target) return true;
        else if (sum < target) ++lo;
        else --hi;
    }
    return false;
}
// O(n) time, O(1) space

// Fixed-size window: max sum of any subarray of size k
int maxSumFixedWindow(std::vector<int>& a, int k) {
    int sum = 0;
    for (int i = 0; i < k; ++i) sum += a[i];
    int best = sum;
    for (int i = k; i < (int)a.size(); ++i) {
        sum += a[i] - a[i - k]; // add new, remove leftmost
        best = std::max(best, sum);
    }
    return best;
}

// Variable-size window: smallest subarray with sum >= target
int minSubarrayLen(int target, std::vector<int>& a) {
    int left = 0, sum = 0, best = INT_MAX;
    for (int right = 0; right < (int)a.size(); ++right) {
        sum += a[right];
        while (sum >= target) {
            best = std::min(best, right - left + 1);
            sum -= a[left++]; // shrink from left
        }
    }
    return best == INT_MAX ? 0 : best;
}
// Both O(n) time, O(1) space — each pointer moves forward at most n times total

// 1D: prefix[i] = sum of a[0..i-1]
std::vector<long long> buildPrefix(std::vector<int>& a) {
    std::vector<long long> prefix(a.size() + 1, 0);
    for (int i = 0; i < (int)a.size(); ++i) prefix[i + 1] = prefix[i] + a[i];
    return prefix;
}
long long rangeSum(std::vector<long long>& prefix, int l, int r) { // sum a[l..r] inclusive
    return prefix[r + 1] - prefix[l];
}

// 2D: prefix[i][j] = sum of rectangle (0,0) to (i-1,j-1)
std::vector<std::vector<long long>> build2D(std::vector<std::vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    std::vector<std::vector<long long>> pre(n + 1, std::vector<long long>(m + 1, 0));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            pre[i+1][j+1] = grid[i][j] + pre[i][j+1] + pre[i+1][j] - pre[i][j];
    return pre;
}
// Query sum of rectangle (r1,c1)-(r2,c2) inclusive, using inclusion-exclusion:
// pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]

int maxSubArray(std::vector<int>& a) {
    int best = a[0], curr = a[0];
    for (int i = 1; i < (int)a.size(); ++i) {
        curr = std::max(a[i], curr + a[i]); // extend or restart
        best = std::max(best, curr);
    }
    return best;
}
// O(n) time, O(1) space

void sortColors(std::vector<int>& a) { // values are 0, 1, 2
    int low = 0, mid = 0, high = (int)a.size() - 1;
    while (mid <= high) {
        if (a[mid] == 0) std::swap(a[low++], a[mid++]);
        else if (a[mid] == 1) ++mid;
        else std::swap(a[mid], a[high--]); // don't advance mid: re-check swapped-in value
    }
}
// O(n) time, O(1) space, single pass

const long long MOD = 1'000'000'007, BASE = 131;

struct StringHash {
    std::vector<long long> h, p; // h[i] = hash of prefix[0..i), p[i] = BASE^i mod MOD
    StringHash(const std::string& s) {
        int n = s.size();
        h.assign(n + 1, 0); p.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            h[i+1] = (h[i] * BASE + s[i]) % MOD;
            p[i+1] = (p[i] * BASE) % MOD;
        }
    }
    // hash of s[l..r) in O(1)
    long long get(int l, int r) {
        long long res = (h[r] - h[l] * p[r - l]) % MOD;
        return res < 0 ? res + MOD : res;
    }
};

std::vector<int> buildLPS(const std::string& pat) {
    int m = pat.size();
    std::vector<int> lps(m, 0);
    int len = 0, i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    return lps;
}

std::vector<int> kmpSearch(const std::string& text, const std::string& pat) {
    std::vector<int> lps = buildLPS(pat), matches;
    int n = text.size(), m = pat.size(), i = 0, j = 0;
    while (i < n) {
        if (text[i] == pat[j]) { ++i; ++j; }
        if (j == m) { matches.push_back(i - j); j = lps[j - 1]; }
        else if (i < n && text[i] != pat[j]) {
            if (j) j = lps[j - 1]; else ++i;
        }
    }
    return matches;
}
// O(n + m) time, O(m) space

std::vector<int> zFunction(const std::string& s) {
    int n = s.size();
    std::vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (i < r) z[i] = std::min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}
// O(n) time, O(n) space. z[0] is conventionally left as 0 or n by convention.

std::vector<int> rabinKarp(const std::string& text, const std::string& pat) {
    const long long MOD = 1'000'000'007, BASE = 131;
    int n = text.size(), m = pat.size();
    std::vector<int> matches;
    if (m > n) return matches;

    long long patHash = 0, curHash = 0, power = 1;
    for (int i = 0; i < m; ++i) {
        patHash = (patHash * BASE + pat[i]) % MOD;
        curHash = (curHash * BASE + text[i]) % MOD;
        if (i) power = (power * BASE) % MOD;
    }
    for (int i = 0; ; ++i) {
        if (curHash == patHash && text.substr(i, m) == pat) matches.push_back(i);
        if (i + m == n) break;
        curHash = ((curHash - (long long)text[i] * power % MOD + MOD) % MOD * BASE + text[i + m]) % MOD;
    }
    return matches;
}

std::string longestPalindrome(const std::string& s) {
    std::string t = "^#";
    for (char c : s) { t += c; t += '#'; }
    t += '$';
    int n = t.size();
    std::vector<int> p(n, 0);
    int center = 0, right = 0;
    for (int i = 1; i < n - 1; ++i) {
        if (i < right) p[i] = std::min(right - i, p[2 * center - i]);
        while (t[i + p[i] + 1] == t[i - p[i] - 1]) ++p[i];
        if (i + p[i] > right) { center = i; right = i + p[i]; }
    }
    int maxLen = 0, centerIdx = 0;
    for (int i = 1; i < n - 1; ++i)
        if (p[i] > maxLen) { maxLen = p[i]; centerIdx = i; }
    int start = (centerIdx - maxLen) / 2;
    return s.substr(start, maxLen);
}
// O(n) time, O(n) space

void backtrack(int idx, std::vector<int>& nums, std::vector<int>& path,
                std::vector<std::vector<int>>& result) {
    result.push_back(path); // every node in the recursion tree is a valid subset
    for (int i = idx; i < (int)nums.size(); ++i) {
        path.push_back(nums[i]);       // choose
        backtrack(i + 1, nums, path, result); // explore
        path.pop_back();               // un-choose (backtrack)
    }
}
// Generates all 2^n subsets. Time: O(2^n * n) (n to copy each subset)

void permute(std::vector<int>& nums, std::vector<bool>& used,
             std::vector<int>& path, std::vector<std::vector<int>>& result) {
    if (path.size() == nums.size()) { result.push_back(path); return; }
    for (int i = 0; i < (int)nums.size(); ++i) {
        if (used[i]) continue;
        used[i] = true; path.push_back(nums[i]);
        permute(nums, used, path, result);
        path.pop_back(); used[i] = false;
    }
}
// n! permutations, O(n! * n) time overall

int totalNQueens(int n) {
    std::vector<bool> cols(n), diag1(2 * n), diag2(2 * n); // diag1: r-c+n, diag2: r+c
    int count = 0;
    std::function<void(int)> solve = [&](int row) {
        if (row == n) { ++count; return; }
        for (int col = 0; col < n; ++col) {
            int d1 = row - col + n, d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) continue;
            cols[col] = diag1[d1] = diag2[d2] = true;
            solve(row + 1);
            cols[col] = diag1[d1] = diag2[d2] = false; // backtrack
        }
    };
    solve(0);
    return count;
}

bool isValid(std::vector<std::vector<char>>& b, int r, int c, char val) {
    for (int i = 0; i < 9; ++i) {
        if (b[r][i] == val || b[i][c] == val) return false;
        int br = 3 * (r / 3) + i / 3, bc = 3 * (c / 3) + i % 3;
        if (b[br][bc] == val) return false;
    }
    return true;
}

bool solveSudoku(std::vector<std::vector<char>>& b) {
    for (int r = 0; r < 9; ++r) {
        for (int c = 0; c < 9; ++c) {
            if (b[r][c] != '.') continue;
            for (char val = '1'; val <= '9'; ++val) {
                if (!isValid(b, r, c, val)) continue;
                b[r][c] = val;
                if (solveSudoku(b)) return true; // propagate success up the call stack
                b[r][c] = '.'; // backtrack
            }
            return false; // no digit worked here -> this whole branch fails
        }
    }
    return true; // filled every cell
}

void combSum(std::vector<int>& cand, int idx, int remain,
             std::vector<int>& path, std::vector<std::vector<int>>& result) {
    if (remain == 0) { result.push_back(path); return; }
    if (remain < 0 || idx == (int)cand.size()) return;
    path.push_back(cand[idx]);
    combSum(cand, idx, remain - cand[idx], path, result); // reuse cand[idx] -> don't advance idx
    path.pop_back();
    combSum(cand, idx + 1, remain, path, result); // skip cand[idx]
}
// Sort candidates first and prune (remain < 0) for efficiency

void merge(std::vector<int>& a, int l, int m, int r) {
    std::vector<int> tmp(r - l + 1);
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= keeps it stable
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int t = 0; t < k; ++t) a[l + t] = tmp[t];
}

void mergeSort(std::vector<int>& a, int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    merge(a, l, m, r);
}
// Time: O(n log n) always. Space: O(n) auxiliary + O(log n) recursion stack. Stable.

int partition(std::vector<int>& a, int lo, int hi) {
    int pivotIdx = lo + rand() % (hi - lo + 1); // randomized pivot avoids worst-case on sorted input
    std::swap(a[pivotIdx], a[hi]);
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; ++j) {
        if (a[j] < pivot) std::swap(a[i++], a[j]);
    }
    std::swap(a[i], a[hi]);
    return i;
}

void quickSort(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}
// Time: O(n log n) average, O(n²) worst case. Space: O(log n) stack average. Not stable.

void siftDown(std::vector<int>& a, int n, int i) {
    while (true) {
        int largest = i, l = 2*i+1, r = 2*i+2;
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) break;
        std::swap(a[i], a[largest]);
        i = largest;
    }
}

void heapSort(std::vector<int>& a) {
    int n = a.size();
    for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i); // build heap: O(n)
    for (int i = n - 1; i > 0; --i) {
        std::swap(a[0], a[i]);      // move max to the end
        siftDown(a, i, 0);          // restore heap on the shrunk range
    }
}
// Time: O(n log n) always. Space: O(1). Not stable.

std::vector<int> countingSort(std::vector<int>& a, int maxVal) {
    std::vector<int> count(maxVal + 1, 0);
    for (int x : a) count[x]++;
    for (int i = 1; i <= maxVal; ++i) count[i] += count[i - 1]; // prefix sum -> final positions
    std::vector<int> out(a.size());
    for (int i = (int)a.size() - 1; i >= 0; --i) // right-to-left keeps it stable
        out[--count[a[i]]] = a[i];
    return out;
}
// Time: O(n + k). Space: O(n + k). Stable.

void radixSort(std::vector<int>& a) {
    int maxVal = *std::max_element(a.begin(), a.end());
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        std::vector<int> out(a.size());
        int count[10] = {0};
        for (int x : a) count[(x / exp) % 10]++;
        for (int i = 1; i < 10; ++i) count[i] += count[i - 1];
        for (int i = (int)a.size() - 1; i >= 0; --i) {
            int digit = (a[i] / exp) % 10;
            out[--count[digit]] = a[i];
        }
        a = out; // stable per-digit sort composed d times -> overall stable & correct
    }
}
// Time: O(d * (n + 10)) ~ O(n) for fixed-width integers. Space: O(n).

std::vector<double> bucketSort(std::vector<double>& a) { // values in [0, 1)
    int n = a.size();
    std::vector<std::vector<double>> buckets(n);
    for (double x : a) buckets[(int)(x * n)].push_back(x);
    std::vector<double> result;
    for (auto& b : buckets) {
        std::sort(b.begin(), b.end());
        result.insert(result.end(), b.begin(), b.end());
    }
    return result;
}

int binarySearch(std::vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2; // avoids overflow vs (lo+hi)/2
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1; // not found
}

// "Find first index where predicate(x) is true" template (predicate is monotonic: F F F T T T)
int findFirstTrue(int lo, int hi, std::function<bool(int)> predicate) {
    // invariant: predicate(hi+1) would be true (or hi+1 is out of range)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (predicate(mid)) hi = mid;      // mid could be the answer, keep it in range
        else lo = mid + 1;                 // mid is definitely not the answer
    }
    return lo; // lo == hi: first index where predicate holds
}

// Split array into k subarrays minimizing the largest subarray sum
bool canSplit(std::vector<int>& a, int k, long long maxSum) {
    int parts = 1; long long curr = 0;
    for (int x : a) {
        if (curr + x > maxSum) { ++parts; curr = x; }
        else curr += x;
    }
    return parts <= k;
}

long long minimizeLargestSum(std::vector<int>& a, int k) {
    long long lo = *std::max_element(a.begin(), a.end());
    long long hi = std::accumulate(a.begin(), a.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canSplit(a, k, mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}
// O(n log(sum)) instead of exponential enumeration of all splits

double ternarySearchMax(double lo, double hi, std::function<double(double)> f) {
    for (int iter = 0; iter < 200; ++iter) { // fixed iterations for floating point
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1; else hi = m2;
    }
    return (lo + hi) / 2;
}
// O(log((hi-lo)/eps)) — each iteration shrinks the range by 1/3

struct ListNode { int val; ListNode* next; ListNode(int v): val(v), next(nullptr) {} };

// Iterative: O(n) time, O(1) space
ListNode* reverseIterative(ListNode* head) {
    ListNode* prev = nullptr;
    while (head) {
        ListNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

// Recursive: O(n) time, O(n) space (call stack)
ListNode* reverseRecursive(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

ListNode* findMiddle(ListNode* head) {
    ListNode* slow = head; ListNode* fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    return slow; // second middle node for even-length lists
}

ListNode* detectCycleStart(ListNode* head) {
    ListNode* slow = head; ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) { // cycle detected
            ListNode* ptr = head;
            while (ptr != slow) { ptr = ptr->next; slow = slow->next; }
            return ptr; // cycle entry point
        }
    }
    return nullptr; // no cycle
}
// O(n) time, O(1) space

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; }; // min-heap
    std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(cmp)> pq(cmp);
    for (auto* node : lists) if (node) pq.push(node);

    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node;
        tail = node;
        if (node->next) pq.push(node->next);
    }
    return dummy.next;
}
// O(N log k) time, O(k) space for the heap

class LRUCache {
    int capacity;
    std::list<std::pair<int, int>> order; // {key, value}, front = most recently used
    std::unordered_map<int, std::list<std::pair<int,int>>::iterator> index;

public:
    LRUCache(int cap) : capacity(cap) {}

    int get(int key) {
        auto it = index.find(key);
        if (it == index.end()) return -1;
        order.splice(order.begin(), order, it->second); // move to front, O(1)
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = index.find(key);
        if (it != index.end()) {
            it->second->second = value;
            order.splice(order.begin(), order, it->second);
            return;
        }
        if ((int)order.size() == capacity) {
            auto last = order.back();
            index.erase(last.first);
            order.pop_back();
        }
        order.emplace_front(key, value);
        index[key] = order.begin();
    }
};
// get/put: O(1) average time (hashmap lookup + O(1) list splice), O(capacity) space

std::vector<int> nextGreaterElement(std::vector<int>& a) {
    int n = a.size();
    std::vector<int> result(n, -1);
    std::stack<int> st; // stores indices, values decreasing bottom-to-top
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && a[st.top()] < a[i]) {
            result[st.top()] = a[i]; // a[i] is the next greater element for st.top()
            st.pop();
        }
        st.push(i);
    }
    return result;
}
// O(n) time (amortized, each index pushed/popped once), O(n) space

std::vector<int> maxSlidingWindow(std::vector<int>& a, int k) {
    std::deque<int> dq; // stores indices, values decreasing front-to-back
    std::vector<int> result;
    for (int i = 0; i < (int)a.size(); ++i) {
        while (!dq.empty() && a[dq.back()] < a[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front(); // out of window
        if (i >= k - 1) result.push_back(a[dq.front()]);
    }
    return result;
}
// O(n) time — each index enters/leaves the deque at most once

class QueueUsingStacks {
    std::stack<int> inStack, outStack;
    void transfer() {
        if (outStack.empty())
            while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); }
    }
public:
    void push(int x) { inStack.push(x); }         // O(1)
    int pop() { transfer(); int v = outStack.top(); outStack.pop(); return v; } // amortized O(1)
    int peek() { transfer(); return outStack.top(); }                          // amortized O(1)
    bool empty() { return inStack.empty() && outStack.empty(); }
};
// Each element is moved between stacks at most once -> amortized O(1) per op

class StackUsingQueues {
    std::queue<int> q;
public:
    void push(int x) {
        q.push(x);
        for (int i = 0; i < (int)q.size() - 1; ++i) { q.push(q.front()); q.pop(); } // rotate
    } // O(n) push, O(1) pop/top -- makes the most recent element always the front
    int pop() { int v = q.front(); q.pop(); return v; }
    int top() { return q.front(); }
};

class MinStack {
    std::stack<int> st, minSt;
public:
    void push(int x) {
        st.push(x);
        minSt.push(minSt.empty() ? x : std::min(x, minSt.top()));
    }
    void pop() { st.pop(); minSt.pop(); }
    int top() { return st.top(); }
    int getMin() { return minSt.top(); } // O(1)
};
// Space-optimized variant: push only when x <= current min, store a counter for duplicates

struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v): val(v), left(nullptr), right(nullptr) {} };

// Recursive inorder: O(n) time, O(h) space (call stack, h = height)
void inorderRec(TreeNode* root, std::vector<int>& out) {
    if (!root) return;
    inorderRec(root->left, out);
    out.push_back(root->val);
    inorderRec(root->right, out);
}

// Iterative inorder with explicit stack: O(n) time, O(h) space
std::vector<int> inorderIterative(TreeNode* root) {
    std::vector<int> out;
    std::stack<TreeNode*> st;
    TreeNode* curr = root;
    while (curr || !st.empty()) {
        while (curr) { st.push(curr); curr = curr->left; }
        curr = st.top(); st.pop();
        out.push_back(curr->val);
        curr = curr->right;
    }
    return out;
}

std::vector<int> morrisInorder(TreeNode* root) {
    std::vector<int> out;
    TreeNode* curr = root;
    while (curr) {
        if (!curr->left) {
            out.push_back(curr->val);
            curr = curr->right;
        } else {
            TreeNode* pred = curr->left;
            while (pred->right && pred->right != curr) pred = pred->right;
            if (!pred->right) {
                pred->right = curr; // create the thread
                curr = curr->left;
            } else {
                pred->right = nullptr; // remove the thread (restore tree)
                out.push_back(curr->val);
                curr = curr->right;
            }
        }
    }
    return out;
}
// O(n) time (each edge traversed at most twice), O(1) extra space

TreeNode* search(TreeNode* root, int key) {
    while (root && root->val != key)
        root = key < root->val ? root->left : root->right;
    return root; // O(h): O(log n) balanced, O(n) worst case (degenerate/skewed)
}

TreeNode* insert(TreeNode* root, int key) {
    if (!root) return new TreeNode(key);
    if (key < root->val) root->left = insert(root->left, key);
    else if (key > root->val) root->right = insert(root->right, key);
    return root;
}

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) root->left = deleteNode(root->left, key);
    else if (key > root->val) root->right = deleteNode(root->right, key);
    else { // found the node to delete
        if (!root->left) return root->right;
        if (!root->right) return root->left;
        TreeNode* succ = root->right; // inorder successor = min of right subtree
        while (succ->left) succ = succ->left;
        root->val = succ->val;
        root->right = deleteNode(root->right, succ->val);
    }
    return root;
}

// Right rotation around node y (y is left-heavy)
//      y                x
//     / \              / \
//    x   T3    ->    T1   y
//   / \                  / \
//  T1  T2               T2  T3
Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;
    x->right = y;
    y->left = T2;
    updateHeight(y); updateHeight(x); // heights must be recomputed bottom-up
    return x; // new subtree root
}

class SegmentTree { // range sum with range-add lazy propagation
    int n;
    std::vector<long long> tree, lazy;

    void push_down(int node, int l, int r) {
        if (lazy[node] == 0) return;
        int mid = (l + r) / 2;
        apply(2*node, l, mid, lazy[node]);
        apply(2*node+1, mid+1, r, lazy[node]);
        lazy[node] = 0;
    }
    void apply(int node, int l, int r, long long val) {
        tree[node] += val * (r - l + 1);
        lazy[node] += val;
    }
public:
    SegmentTree(int size) : n(size), tree(4*size, 0), lazy(4*size, 0) {}

    void update(int node, int l, int r, int ql, int qr, long long val) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) { apply(node, l, r, val); return; }
        push_down(node, l, r);
        int mid = (l + r) / 2;
        update(2*node, l, mid, ql, qr, val);
        update(2*node+1, mid+1, r, ql, qr, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    long long query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        push_down(node, l, r);
        int mid = (l + r) / 2;
        return query(2*node, l, mid, ql, qr) + query(2*node+1, mid+1, r, ql, qr);
    }
};
// Build: O(n). Range update / range query: O(log n) each. Space: O(n)

class Fenwick {
    std::vector<long long> tree;
    int n;
public:
    Fenwick(int size) : n(size), tree(size + 1, 0) {}

    void update(int i, long long delta) { // add delta at index i (1-indexed)
        for (; i <= n; i += i & (-i)) tree[i] += delta;
    }
    long long prefixSum(int i) { // sum of [1, i]
        long long sum = 0;
        for (; i > 0; i -= i & (-i)) sum += tree[i];
        return sum;
    }
    long long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); }
};
// update / prefixSum: O(log n) each. Space: O(n). Build from array: O(n log n) or O(n) with a trick.

struct TrieNode {
    TrieNode* children[26] = {};
    bool isEnd = false;
};

class Trie {
    TrieNode* root = new TrieNode();
public:
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        node->isEnd = true;
    }
    bool search(const std::string& word) {
        TrieNode* node = find(word);
        return node && node->isEnd;
    }
    bool startsWith(const std::string& prefix) { return find(prefix) != nullptr; }
private:
    TrieNode* find(const std::string& s) {
        TrieNode* node = root;
        for (char c : s) {
            int idx = c - 'a';
            if (!node->children[idx]) return nullptr;
            node = node->children[idx];
        }
        return node;
    }
};

// Word Break: can s be segmented into dictionary words? DP + trie/set, O(n^2)
bool wordBreak(const std::string& s, std::unordered_set<std::string>& dict) {
    int n = s.size();
    std::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];
}

const int LOG = 20;
std::vector<std::vector<int>> up; // up[k][v] = 2^k-th ancestor of v
std::vector<int> depth;

void dfs(int v, int parent, std::vector<std::vector<int>>& adj) {
    up[0][v] = parent;
    for (int k = 1; k < LOG; ++k)
        up[k][v] = (up[k-1][v] == -1) ? -1 : up[k-1][up[k-1][v]];
    for (int u : adj[v]) if (u != parent) { depth[u] = depth[v] + 1; dfs(u, v, adj); }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) std::swap(u, v);
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOG; ++k) if (diff & (1 << k)) u = up[k][u];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; --k)
        if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
    return up[0][u];
}
// Preprocess: O(n log n). Query: O(log n).

int diameter = 0;
int height(TreeNode* node) {
    if (!node) return 0;
    int lh = height(node->left);
    int rh = height(node->right);
    diameter = std::max(diameter, lh + rh); // path through this node
    return 1 + std::max(lh, rh);            // height to report upward
}
// O(n) time, O(h) space — a single post-order pass, not O(n^2) recomputation

std::string serialize(TreeNode* root) {
    if (!root) return "#,";
    return std::to_string(root->val) + "," + serialize(root->left) + serialize(root->right);
}

TreeNode* deserializeHelper(std::istringstream& iss) {
    std::string token;
    std::getline(iss, token, ',');
    if (token == "#") return nullptr;
    TreeNode* node = new TreeNode(std::stoi(token));
    node->left = deserializeHelper(iss);
    node->right = deserializeHelper(iss);
    return node;
}
TreeNode* deserialize(const std::string& data) {
    std::istringstream iss(data);
    return deserializeHelper(iss);
}
// Preorder + null markers uniquely determines the tree shape. O(n) time and space.

class MedianFinder {
    std::priority_queue<int> lower;                                  // max-heap, lower half
    std::priority_queue<int, std::vector<int>, std::greater<int>> upper; // min-heap, upper half
public:
    void addNum(int num) {
        if (lower.empty() || num <= lower.top()) lower.push(num);
        else upper.push(num);

        // rebalance so sizes differ by at most 1
        if (lower.size() > upper.size() + 1) { upper.push(lower.top()); lower.pop(); }
        else if (upper.size() > lower.size() + 1) { lower.push(upper.top()); upper.pop(); }
    }
    double findMedian() {
        if (lower.size() == upper.size()) return (lower.top() + upper.top()) / 2.0;
        return lower.size() > upper.size() ? lower.top() : upper.top();
    }
};
// addNum: O(log n). findMedian: O(1).

std::vector<int> topKLargest(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // size-k min-heap
    for (int x : nums) {
        minHeap.push(x);
        if ((int)minHeap.size() > k) minHeap.pop(); // discard the smallest
    }
    std::vector<int> result;
    while (!minHeap.empty()) { result.push_back(minHeap.top()); minHeap.pop(); }
    return result; // O(n log k) time, O(k) space
}
// Alternative: quickselect gives average O(n) if you only need the values, not sorted order

std::vector<std::vector<int>> adj; // adj[u] = list of neighbors

std::vector<int> bfs(int start, int n) {
    std::vector<int> dist(n, -1);
    std::queue<int> q;
    dist[start] = 0; q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
        }
    }
    return dist; // shortest distances in an UNWEIGHTED graph
}

std::vector<bool> visited;
void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u]) if (!visited[v]) dfs(v);
}
// Both: O(V + E) time, O(V) space

// Kahn's algorithm (BFS on in-degrees)
std::vector<int> topoSortKahn(int n, std::vector<std::vector<int>>& adj) {
    std::vector<int> indeg(n, 0);
    for (int u = 0; u < n; ++u) for (int v : adj[u]) indeg[v]++;
    std::queue<int> q;
    for (int u = 0; u < n; ++u) if (indeg[u] == 0) q.push(u);
    std::vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    if ((int)order.size() != n) return {}; // cycle detected -> no valid topo order
    return order;
}

// DFS-based (post-order, then reverse)
void dfsTopo(int u, std::vector<std::vector<int>>& adj, std::vector<bool>& visited, std::vector<int>& order) {
    visited[u] = true;
    for (int v : adj[u]) if (!visited[v]) dfsTopo(v, adj, visited, order);
    order.push_back(u); // post-order
}
std::vector<int> topoSortDFS(int n, std::vector<std::vector<int>>& adj) {
    std::vector<bool> visited(n, false);
    std::vector<int> order;
    for (int u = 0; u < n; ++u) if (!visited[u]) dfsTopo(u, adj, visited, order);
    std::reverse(order.begin(), order.end());
    return order;
}
// Both: O(V + E) time

class DSU {
    std::vector<int> parent, rank_;
public:
    DSU(int n) : parent(n), rank_(n, 0) {
        std::iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false; // already in the same set (would form a cycle)
        if (rank_[a] < rank_[b]) std::swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b]) rank_[a]++;
        return true;
    }
};
// find/unite: O(alpha(n)) amortized, effectively O(1). Space: O(n)

// Kruskal's: sort edges, greedily add if it connects two different components (via DSU)
long long kruskal(int n, std::vector<std::array<int,3>>& edges) { // {weight, u, v}
    std::sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long total = 0;
    for (auto& [w, u, v] : edges)
        if (dsu.unite(u, v)) total += w;
    return total;
}
// O(E log E) for sorting + O(E * alpha(n)) for DSU ops

// Prim's: grow the tree one cheapest crossing edge at a time, via a min-heap
long long prim(int n, std::vector<std::vector<std::pair<int,int>>>& adj) { // adj[u] = {v, weight}
    std::vector<bool> inMST(n, false);
    std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, std::greater<>> pq; // {weight, node}
    pq.push({0, 0});
    long long total = 0;
    int count = 0;
    while (!pq.empty() && count < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true; total += w; ++count;
        for (auto& [v, wt] : adj[u]) if (!inMST[v]) pq.push({wt, v});
    }
    return total;
}
// O(E log V) with a binary heap

std::vector<long long> dijkstra(int start, int n, std::vector<std::vector<std::pair<int,int>>>& adj) {
    std::vector<long long> dist(n, LLONG_MAX);
    std::priority_queue<std::pair<long long,int>, std::vector<std::pair<long long,int>>, std::greater<>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue; // stale entry, skip (lazy deletion)
        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}
// O((V + E) log V) with a binary heap and lazy deletion

struct Edge { int u, v, w; };

std::pair<std::vector<long long>, bool> bellmanFord(int start, int n, std::vector<Edge>& edges) {
    std::vector<long long> dist(n, LLONG_MAX);
    dist[start] = 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;

    bool hasNegCycle = false;
    for (auto& [u, v, w] : edges) // one extra pass to detect negative cycles
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) { hasNegCycle = true; break; }

    return {dist, hasNegCycle};
}
// O(V * E) time, O(V) space

void floydWarshall(std::vector<std::vector<long long>>& dist, int n) {
    // dist[i][j] pre-initialized to edge weight or INF (0 if i==j)
    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] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
}
// O(V^3) time, O(V^2) space -- only practical for V up to a few hundred

void dfs1(int u, std::vector<std::vector<int>>& adj, std::vector<bool>& vis, std::vector<int>& order) {
    vis[u] = true;
    for (int v : adj[u]) if (!vis[v]) dfs1(v, adj, vis, order);
    order.push_back(u);
}
void dfs2(int u, std::vector<std::vector<int>>& radj, std::vector<bool>& vis, std::vector<int>& comp) {
    vis[u] = true; comp.push_back(u);
    for (int v : radj[u]) if (!vis[v]) dfs2(v, radj, vis, comp);
}
std::vector<std::vector<int>> kosaraju(int n, std::vector<std::vector<int>>& adj, std::vector<std::vector<int>>& radj) {
    std::vector<bool> vis(n, false);
    std::vector<int> order;
    for (int i = 0; i < n; ++i) if (!vis[i]) dfs1(i, adj, vis, order);
    std::fill(vis.begin(), vis.end(), false);
    std::vector<std::vector<int>> sccs;
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        if (!vis[u]) { std::vector<int> comp; dfs2(u, radj, vis, comp); sccs.push_back(comp); }
    }
    return sccs;
}
// O(V + E) time, two DFS passes plus building the reverse graph

int timer = 0;
std::vector<int> disc, low;
std::vector<bool> visited;
std::vector<std::pair<int,int>> bridges;

void dfsBridge(int u, int parent, std::vector<std::vector<int>>& adj) {
    visited[u] = true;
    disc[u] = low[u] = timer++;
    for (int v : adj[u]) {
        if (v == parent) continue; // skip the edge back to immediate parent (not a "back edge")
        if (visited[v]) { low[u] = std::min(low[u], disc[v]); continue; } // back edge
        dfsBridge(v, u, adj);
        low[u] = std::min(low[u], low[v]);
        if (low[v] > disc[u]) bridges.push_back({u, v}); // bridge found
    }
}
// O(V + E) time

bool isBipartite(int n, std::vector<std::vector<int>>& adj) {
    std::vector<int> color(n, -1);
    for (int start = 0; start < n; ++start) {
        if (color[start] != -1) continue;
        color[start] = 0;
        std::queue<int> q; q.push(start);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) { color[v] = 1 - color[u]; q.push(v); }
                else if (color[v] == color[u]) return false;
            }
        }
    }
    return true;
}
// O(V + E) time

// Directed graph: track nodes currently "in the recursion stack" (color: white/gray/black)
bool hasCycleDirected(int u, std::vector<std::vector<int>>& adj, std::vector<int>& state) {
    state[u] = 1; // gray = in progress
    for (int v : adj[u]) {
        if (state[v] == 1) return true;         // back edge to a gray node -> cycle
        if (state[v] == 0 && hasCycleDirected(v, adj, state)) return true;
    }
    state[u] = 2; // black = fully explored
    return false;
}

// Undirected graph: a visited neighbor that isn't the immediate parent means a cycle
bool hasCycleUndirected(int u, int parent, std::vector<std::vector<int>>& adj, std::vector<bool>& visited) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) { if (hasCycleUndirected(v, u, adj, visited)) return true; }
        else if (v != parent) return true;
    }
    return false;
}
// Both O(V + E) time. Alternative for undirected: DSU -- a cycle exists the moment
// union(u, v) is attempted but find(u) == find(v) already.

// Fibonacci: memoization
std::vector<long long> memo;
long long fibMemo(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
}

// Fibonacci: tabulation, space-optimized to O(1)
long long fibTab(int n) {
    if (n <= 1) return n;
    long long prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; ++i) { long long curr = prev1 + prev2; prev2 = prev1; prev1 = curr; }
    return prev1;
}

int knapsack01(std::vector<int>& wt, std::vector<int>& val, int W) {
    int n = wt.size();
    std::vector<int> dp(W + 1, 0); // space-optimized: 1D array
    for (int i = 0; i < n; ++i)
        for (int w = W; w >= wt[i]; --w) // iterate DOWN to avoid reusing item i twice
            dp[w] = std::max(dp[w], dp[w - wt[i]] + val[i]);
    return dp[W];
}
// O(n * W) time, O(W) space

int unboundedKnapsack(std::vector<int>& wt, std::vector<int>& val, int W) {
    std::vector<int> dp(W + 1, 0);
    for (int w = 1; w <= W; ++w)
        for (int i = 0; i < (int)wt.size(); ++i)
            if (wt[i] <= w) dp[w] = std::max(dp[w], dp[w - wt[i]] + val[i]);
    return dp[W];
}
// O(n * W) time, O(W) space

int lcs(const std::string& a, const std::string& b) {
    int n = a.size(), m = b.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dp[i][j] = (a[i-1] == b[j-1]) ? dp[i-1][j-1] + 1 : std::max(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}
// O(n * m) time, O(n * m) space (reducible to O(min(n,m)) if only the length is needed)

int lengthOfLIS(std::vector<int>& nums) {
    std::vector<int> tails; // tails[k] = smallest tail of any increasing subsequence of length k+1
    for (int x : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}
// O(n log n) time, O(n) space. NOTE: tails does NOT hold an actual valid subsequence,
// only correct lengths -- reconstruct the actual LIS via parent pointers if needed.

int matrixChainOrder(std::vector<int>& p) { // p[i-1] x p[i] is the dimension of matrix i
    int n = p.size() - 1;
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0));
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i <= n - len + 1; ++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] + p[i-1] * p[k] * p[j];
                dp[i][j] = std::min(dp[i][j], cost);
            }
        }
    }
    return dp[1][n];
}
// O(n^3) time, O(n^2) space

int editDistance(const std::string& a, const std::string& b) {
    int n = a.size(), m = b.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
    for (int i = 0; i <= n; ++i) dp[i][0] = i; // delete all of a[0..i)
    for (int j = 0; j <= m; ++j) dp[0][j] = j; // insert all of b[0..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 + std::min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}); // del, insert, replace
        }
    }
    return dp[n][m];
}
// O(n * m) time and space

int coinChangeMinCoins(std::vector<int>& coins, int amount) { // unbounded knapsack shape
    std::vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int a = 1; a <= amount; ++a)
        for (int c : coins)
            if (c <= a && dp[a - c] != INT_MAX) dp[a] = std::min(dp[a], dp[a - c] + 1);
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

long long coinChangeCountWays(std::vector<int>& coins, int amount) { // order doesn't matter -> combinations
    std::vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins)               // coin in OUTER loop avoids counting permutations as distinct
        for (int a = c; a <= amount; ++a)
            dp[a] += dp[a - c];
    return dp[amount];
}
// Both O(amount * coins.size()) time, O(amount) space

// Count numbers in [0, N] whose digit sum equals targetSum
std::string numStr;
int memo_dp[20][200][2]; bool computed[20][200][2];

int solve(int pos, int sumSoFar, int tight) {
    if (pos == (int)numStr.size()) return sumSoFar == 0 ? 1 : 0;
    if (computed[pos][sumSoFar][tight]) return memo_dp[pos][sumSoFar][tight];
    computed[pos][sumSoFar][tight] = true;

    int limit = tight ? (numStr[pos] - '0') : 9;
    int result = 0;
    for (int d = 0; d <= limit; ++d) {
        if (d > sumSoFar) break; // pruning for this specific "remaining sum" style problem
        int newTight = (tight && d == limit) ? 1 : 0;
        result += solve(pos + 1, sumSoFar - d, newTight);
    }
    return memo_dp[pos][sumSoFar][tight] = result;
}
// Complexity: O(digits * targetSum * 2) states, each O(10) transition -> very fast
// even when N is astronomically large (up to 10^18), because we never enumerate numbers directly

int tsp(std::vector<std::vector<int>>& dist, int n) {
    std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INT_MAX));
    dp[1][0] = 0; // start at city 0, only city 0 visited
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int u = 0; u < n; ++u) {
            if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX) continue;
            for (int v = 0; v < n; ++v) {
                if (mask & (1 << v)) continue; // already visited
                int newMask = mask | (1 << v);
                dp[newMask][v] = std::min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    int best = INT_MAX;
    int fullMask = (1 << n) - 1;
    for (int u = 1; u < n; ++u)
        if (dp[fullMask][u] != INT_MAX) best = std::min(best, dp[fullMask][u] + dist[u][0]);
    return best;
}
// O(2^n * n^2) time, O(2^n * n) space -- feasible up to n ~ 18-20

// Returns {best sum WITHOUT robbing this node, best sum robbing this node}
std::pair<int,int> robTree(TreeNode* node) {
    if (!node) return {0, 0};
    auto [lWithout, lWith] = robTree(node->left);
    auto [rWithout, rWith] = robTree(node->right);
    int without = std::max(lWithout, lWith) + std::max(rWithout, rWith); // children free to be robbed or not
    int with = node->val + lWithout + rWithout; // children can't be robbed if this node is
    return {without, with};
}
int rob(TreeNode* root) { auto [w, r] = robTree(root); return std::max(w, r); }
// O(n) time, O(h) space

// Palindrome partitioning: min cuts to partition s into palindromic substrings
int minCut(const std::string& s) {
    int n = s.size();
    std::vector<std::vector<bool>> isPal(n, std::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 + len - 1 < n; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j] && (len == 2 || isPal[i+1][j-1])) isPal[i][j] = true;
        }
    std::vector<int> dp(n, INT_MAX);
    for (int j = 0; j < n; ++j) {
        if (isPal[0][j]) { dp[j] = 0; continue; }
        for (int i = 1; i <= j; ++i)
            if (isPal[i][j] && dp[i-1] != INT_MAX) dp[j] = std::min(dp[j], dp[i-1] + 1);
    }
    return dp[n-1];
}
// O(n^2) time and space

int activitySelection(std::vector<std::pair<int,int>>& activities) { // {start, end}
    std::sort(activities.begin(), activities.end(),
              [](auto& a, auto& b) { return a.second < b.second; }); // sort by end time
    int count = 0, lastEnd = INT_MIN;
    for (auto& [start, end] : activities) {
        if (start >= lastEnd) { ++count; lastEnd = end; }
    }
    return count;
}
// O(n log n) time (dominated by the sort)

std::vector<std::pair<int,int>> mergeIntervals(std::vector<std::pair<int,int>>& intervals) {
    std::sort(intervals.begin(), intervals.end());
    std::vector<std::pair<int,int>> merged;
    for (auto& [s, e] : intervals) {
        if (!merged.empty() && s <= merged.back().second)
            merged.back().second = std::max(merged.back().second, e); // overlap -> extend
        else
            merged.push_back({s, e});
    }
    return merged;
}
// O(n log n) time

struct HuffNode {
    int freq; char ch; HuffNode *left = nullptr, *right = nullptr;
};
struct Cmp { bool operator()(HuffNode* a, HuffNode* b) { return a->freq > b->freq; } };

HuffNode* buildHuffmanTree(std::vector<std::pair<char,int>>& freqs) {
    std::priority_queue<HuffNode*, std::vector<HuffNode*>, Cmp> pq;
    for (auto& [ch, f] : freqs) pq.push(new HuffNode{f, ch});
    while (pq.size() > 1) {
        HuffNode* a = pq.top(); pq.pop();
        HuffNode* b = pq.top(); pq.pop();
        HuffNode* merged = new HuffNode{a->freq + b->freq, '\0', a, b};
        pq.push(merged);
    }
    return pq.top(); // root; walk left=0/right=1 to get each character's code
}
// O(n log n) time — why it's optimal: merging the two smallest first guarantees
// the least-frequent symbols end up deepest (longest codes), which minimizes
// sum(freq * depth) -- provable via an exchange argument.

// Swap without a temp variable (rarely used in practice, but a classic trick)
a ^= b; b ^= a; a ^= b;

// Find the single number that appears once while all others appear twice
int singleNumber(std::vector<int>& nums) {
    int result = 0;
    for (int x : nums) result ^= x; // pairs cancel out to 0, leaving the unique one
    return result;
}

bool isSet   = (x >> i) & 1;         // check bit i
int  setBit  = x | (1 << i);         // set bit i
int  clrBit  = x & ~(1 << i);        // clear bit i
int  togBit  = x ^ (1 << i);         // toggle bit i
int  lowBit  = x & (-x);             // isolate lowest set bit
int  clrLow  = x & (x - 1);          // clear lowest set bit
bool isPow2  = x > 0 && (x & (x - 1)) == 0; // power-of-two check

int popcountBuiltin(int x) { return __builtin_popcount(x); } // fastest, use this in practice

int popcountManual(int x) { // Brian Kernighan's algorithm: O(number of set bits)
    int count = 0;
    while (x) { x &= (x - 1); ++count; } // clears lowest set bit each iteration
    return count;
}

// Precompute popcount for all numbers 0..n via DP: O(n)
std::vector<int> popcountDP(int n) {
    std::vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) dp[i] = dp[i >> 1] + (i & 1);
    return dp;
}

void enumerateSubsets(std::vector<int>& a) {
    int n = a.size();
    for (int mask = 0; mask < (1 << n); ++mask) {
        std::vector<int> subset;
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i)) subset.push_back(a[i]);
        // process subset
    }
}
// O(2^n * n) time -- fine for n <= ~20

// Iterate all submasks of a given mask (useful in SOS DP / subset-sum-over-subsets)
void iterateSubmasks(int mask) {
    for (int sub = mask; ; sub = (sub - 1) & mask) {
        // process sub
        if (sub == 0) break;
    }
}
// Total submask-iteration work across ALL masks of n bits is O(3^n), not O(4^n) --
// each element is independently "not in mask" / "in mask, not in submask" / "in submask"

// Every element appears 3 times except one that appears once: track bits appearing
// a multiple-of-3 count via two accumulator variables (ones/twos state machine)
int singleNumberII(std::vector<int>& nums) {
    int ones = 0, twos = 0;
    for (int x : nums) {
        ones = (ones ^ x) & ~twos;
        twos = (twos ^ x) & ~ones;
    }
    return ones;
}

// Exactly two elements appear once, rest appear twice: XOR all -> get a^b,
// then split by any set bit in (a^b) to separate the two groups
std::pair<int,int> singleNumberIII(std::vector<int>& nums) {
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;
    int diffBit = xorAll & (-xorAll); // any bit where a and b differ
    int a = 0;
    for (int x : nums) if (x & diffBit) a ^= x;
    return {a, xorAll ^ a};
}
// Both O(n) time, O(1) space

class SqrtDecomp {
    std::vector<long long> a, blockSum;
    int blockSize;
public:
    SqrtDecomp(std::vector<long long>& arr) : a(arr) {
        blockSize = std::max(1, (int)sqrt(a.size()));
        blockSum.assign((a.size() + blockSize - 1) / blockSize, 0);
        for (int i = 0; i < (int)a.size(); ++i) blockSum[i / blockSize] += a[i];
    }
    void update(int i, long long val) {
        blockSum[i / blockSize] += val - a[i];
        a[i] = val;
    }
    long long query(int l, int r) { // sum a[l..r], O(sqrt n)
        long long sum = 0;
        while (l <= r) {
            if (l % blockSize == 0 && l + blockSize - 1 <= r) {
                sum += blockSum[l / blockSize]; l += blockSize;
            } else { sum += a[l]; ++l; }
        }
        return sum;
    }
};

class SparseTable {
    std::vector<std::vector<int>> table;
    std::vector<int> logTable;
public:
    SparseTable(std::vector<int>& a) {
        int n = a.size();
        int LOG = std::__lg(n) + 1;
        table.assign(LOG, std::vector<int>(n));
        table[0] = a;
        for (int k = 1; k < LOG; ++k)
            for (int i = 0; i + (1 << k) <= n; ++i)
                table[k][i] = std::min(table[k-1][i], table[k-1][i + (1 << (k-1))]);
        logTable.assign(n + 1, 0);
        for (int i = 2; i <= n; ++i) logTable[i] = logTable[i/2] + 1;
    }
    int queryMin(int l, int r) { // inclusive, O(1)
        int k = logTable[r - l + 1];
        return std::min(table[k][l], table[k][r - (1 << k) + 1]);
    }
};
// Build: O(n log n) time and space. Query: O(1). No updates supported.

struct Query { int l, r, idx; };
int blockSize;

bool moCompare(const Query& a, const Query& b) {
    int blockA = a.l / blockSize, blockB = b.l / blockSize;
    if (blockA != blockB) return blockA < blockB;
    return (blockA & 1) ? a.r > b.r : a.r < b.r; // alternate direction per block
}
// After sorting queries with moCompare, maintain [curL, curR] with add(x)/remove(x)
// callbacks, moving one boundary at a time between consecutive queries -- total
// pointer movement across all queries is bounded by O((n + q) * sqrt(n)).

using Matrix = std::array<std::array<long long,2>,2>;
const long long MOD = 1'000'000'007;

Matrix multiply(const Matrix& a, const Matrix& b) {
    Matrix c{};
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
    return c;
}
Matrix matPow(Matrix base, long long exp) {
    Matrix result = {{{1,0},{0,1}}}; // identity
    while (exp) {
        if (exp & 1) result = multiply(result, base);
        base = multiply(base, base);
        exp >>= 1;
    }
    return result;
}
long long fibFast(long long n) {
    if (n == 0) return 0;
    Matrix base = {{{1,1},{1,0}}};
    Matrix result = matPow(base, n - 1);
    return result[0][0];
}
// O(log n) time (each of the ~log n squarings does O(1) 2x2 matrix multiplies)

const long long MOD = 1'000'000'007;

long long power(long long base, long long exp, long long mod) { // fast exponentiation
    long long result = 1; base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}
// O(log exp) time

// Modular inverse via Fermat's Little Theorem (requires mod to be PRIME):
// a^(mod-1) === 1 (mod p)  =>  a^(mod-2) is the modular inverse of a
long long modInverse(long long a, long long mod) {
    return power(a, mod - 2, mod);
}

// Sieve of Eratosthenes: all primes up to n in O(n log log n)
std::vector<bool> sieve(int n) {
    std::vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; (long long)i * i <= n; ++i)
        if (isPrime[i])
            for (int j = i * i; j <= n; j += i) isPrime[j] = false;
    return isPrime;
}

// Euler's Totient Function: count of integers in [1, n] coprime to n
long long eulerTotient(long long n) {
    long long result = n;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}
// O(sqrt(n)) time

const int MAXN = 1'000'001;
std::vector<long long> fact(MAXN), invFact(MAXN);

void precomputeFactorials() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) fact[i] = fact[i-1] * i % MOD;
    invFact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2, MOD); // Fermat's little theorem
    for (int i = MAXN - 2; i >= 0; --i) invFact[i] = invFact[i+1] * (i+1) % MOD; // O(1) per step
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n-r] % MOD;
}
// Precompute: O(n). Each query: O(1).