// Two indices, one array. r reads everything; w commits only keepers.
// The invariant w <= r is what makes writing in place safe: the slot w
// overwrites was already read by r, so no unread data can be destroyed.
int removeDuplicates(vector<int>& a) {
    if (a.empty()) return 0;
    int w = 1;                          // a[0] is a keeper by definition

    for (int r = 1; r < a.size(); r++)
        if (a[r] != a[w - 1])           // differs from the LAST KEPT value?
            a[w++] = a[r];              // commit it, then widen the answer

    return w;                           // w counted keepers, so it IS the length
}

// Two indices, one array. r reads everything; w commits only keepers.
// The invariant w <= r is what makes writing in place safe: the slot w
// overwrites was already read by r, so no unread data can be destroyed.
public int removeDuplicates(int[] a) {
    if (a.length == 0) return 0;
    int w = 1;                              // a[0] is always a keeper

    for (int r = 1; r < a.length; r++)
        if (a[r] != a[w - 1])               // new vs the last value KEPT
            a[w++] = a[r];

    return w;                               // w is a COUNT, so it IS the length
}

# Two indices, one list. r reads everything; w commits only keepers.
# The invariant w <= r is what makes writing in place safe: the slot w
# overwrites was already read by r, so no unread data can be destroyed.
def remove_duplicates(a):
    if not a: return 0
    w = 1                               # a[0] is a keeper by definition

    for r in range(1, len(a)):
        if a[r] != a[w - 1]:            # differs from the LAST KEPT value?
            a[w] = a[r]                 # commit it, then widen the answer
            w += 1

    return w                            # w counted keepers, so it IS the length

// Reversal rotation. The first reversal puts the right BLOCKS in the
// right places; the other two fix the order inside each block.
void rotate(vector<int>& a, int k) {
    int n = a.size();
    k %= n;                                 // k may exceed n - this is in the tests

    reverse(a.begin(), a.end());            // 1. blocks swap sides, both backwards
    reverse(a.begin(), a.begin() + k);      // 2. fix the block now at the front
    reverse(a.begin() + k, a.end());        // 3. fix the block now at the back
}

// Reversal rotation. The first reversal puts the right BLOCKS in the
// right places; the other two fix the order inside each block.
public void rotate(int[] a, int k) {
    int n = a.length;
    k %= n;                                 // k may exceed n - this is in the tests

    reverse(a, 0, n - 1);                   // 1. the whole array
    reverse(a, 0, k - 1);                   // 2. the first k
    reverse(a, k, n - 1);                   // 3. everything after
}
private void reverse(int[] a, int l, int r) {
    while (l < r) { int t = a[l]; a[l++] = a[r]; a[r--] = t; }
}

# Reversal rotation. The first reversal puts the right BLOCKS in the
# right places; the other two fix the order inside each block.
def rotate(a, k):
    n = len(a)
    k %= n                                  # k may exceed n - this is in the tests

    def rev(lo, hi):
        while lo < hi:
            a[lo], a[hi] = a[hi], a[lo]
            lo, hi = lo + 1, hi - 1

    rev(0, n - 1)                           # 1. blocks swap sides, both backwards
    rev(0, k - 1)                           # 2. fix the block now at the front
    rev(k, n - 1)                           # 3. fix the block now at the back

// The write pointer again, but SWAPPING because every element must
// survive: the zero displaced from w travels to r, which is already read.
void moveZeroes(vector<int>& a) {
    int w = 0;                              // oldest slot still owed a non-zero

    for (int r = 0; r < a.size(); r++)
        if (a[r] != 0)
            swap(a[w++], a[r]);             // order kept: written as they were read
}

// The write pointer again, but SWAPPING because every element must
// survive: the zero displaced from w travels to r, which is already read.
public void moveZeroes(int[] a) {
    int w = 0;                              // oldest slot still owed a non-zero

    for (int r = 0; r < a.length; r++)
        if (a[r] != 0) {
            int t = a[w]; a[w] = a[r]; a[r] = t;   // swap, never copy
            w++;
        }
}

# The write pointer again, but SWAPPING because every element must
# survive: the zero displaced from w travels to r, which is already read.
def move_zeroes(a):
    w = 0                                   # oldest slot still owed a non-zero

    for r in range(len(a)):
        if a[r] != 0:
            a[w], a[r] = a[r], a[w]         # order kept: written as they were read
            w += 1

// XOR the full range against what is actually present. Every value
// that IS there gets folded twice and cancels; the hole is folded once.
// Preferred over n(n+1)/2 because no intermediate can ever overflow.
int missingNumber(vector<int>& a) {
    int n = a.size(), x = 0;

    for (int i = 0; i < n; i++)
        x ^= i ^ a[i];                      // index and value, both folded
    return x ^ n;                           // index n has no element to pair with
}

// XOR the full range against what is actually present. Every value
// that IS there gets folded twice and cancels; the hole is folded once.
// Preferred over n(n+1)/2 because no intermediate can ever overflow.
public int missingNumber(int[] a) {
    int n = a.length, x = 0;

    for (int i = 0; i < n; i++) x ^= i ^ a[i];   // index against value
    return x ^ n;                                // and the index n itself
}

# XOR the full range against what is actually present. Every value
# that IS there gets folded twice and cancels; the hole is folded once.
# Python ints never overflow, so the sum version is safe here -- but the
# XOR version is the one that ports to C++ unchanged.
def missing_number(a):
    n, x = len(a), 0

    for i, v in enumerate(a):
        x ^= i ^ v                          # index and value, both folded
    return x ^ n                            # index n has no element to pair with

// The seed of Kadane: a running quantity and a best-so-far.
// best is updated on EVERY element, so a streak that runs to the end
// of the array is still recorded.
int findMaxConsecutiveOnes(vector<int>& a) {
    int run = 0, best = 0;

    for (int v : a) {
        run = (v == 1) ? run + 1 : 0;       // a 0 ends the streak entirely
        best = max(best, run);              // record here, not at the break
    }
    return best;
}

// The seed of Kadane: a running quantity and a best-so-far.
// best is updated on EVERY element, so a streak that runs to the end
// of the array is still recorded.
public int findMaxConsecutiveOnes(int[] a) {
    int run = 0, best = 0;

    for (int v : a) {
        run = (v == 1) ? run + 1 : 0;       // extend, or reset to nothing
        best = Math.max(best, run);         // record BEFORE moving on
    }
    return best;
}

# The seed of Kadane: a running quantity and a best-so-far.
# best is updated on EVERY element, so a streak that runs to the end
# of the array is still recorded.
def find_max_consecutive_ones(a):
    run = best = 0

    for v in a:
        run = run + 1 if v == 1 else 0      # a 0 ends the streak entirely
        best = max(best, run)               # record here, not at the break

    return best

// XOR is parity per bit column. A value appearing twice contributes
// an even number of 1s to every column, so it contributes nothing at all.
// Order is irrelevant: XOR is commutative AND associative.
int singleNumber(vector<int>& a) {
    int x = 0;                              // 0 is XOR's identity

    for (int v : a)
        x ^= v;                             // equal pairs cancel to 0
    return x;                               // only the loner survives
}

// XOR is parity per bit column. A value appearing twice contributes
// an even number of 1s to every column, so it contributes nothing at all.
// Order is irrelevant: XOR is commutative AND associative.
public int singleNumber(int[] a) {
    int x = 0;                              // 0 is XOR's identity
    for (int v : a) x ^= v;
    return x;
}

# XOR is parity per bit column. A value appearing twice contributes
# an even number of 1s to every column, so it contributes nothing at all.
# Order is irrelevant: XOR is commutative AND associative.
from functools import reduce
from operator import xor

def single_number(a):
    return reduce(xor, a, 0)                # 0 is XOR's identity

// The reframe: "do two values sum to t" is a question about PAIRS.
// "Have I seen t - a[i]" is a question about ONE value, and a map answers
// that in O(1). Check BEFORE storing, or a[i] pairs with itself.
vector<int> twoSum(vector<int>& a, int t) {
    unordered_map<int, int> seen;           // value -> index it was seen at

    for (int i = 0; i < a.size(); i++) {
        int need = t - a[i];                // the ONE partner that works
        if (seen.count(need))               // has it already gone past?
            return {seen[need], i};
        seen[a[i]] = i;                     // store AFTER checking
    }
    return {};
}

// The reframe: "do two values sum to t" is a question about PAIRS.
// "Have I seen t - a[i]" is a question about ONE value, and a map answers
// that in O(1). Check BEFORE storing, or a[i] pairs with itself.
public int[] twoSum(int[] a, int t) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> its index

    for (int i = 0; i < a.length; i++) {
        Integer j = seen.get(t - a[i]);     // CHECK first
        if (j != null) return new int[]{j, i};
        seen.put(a[i], i);                  // then store
    }
    return new int[]{-1, -1};
}

# The reframe: "do two values sum to t" is a question about PAIRS.
# "Have I seen t - a[i]" is a question about ONE value, and a dict answers
# that in O(1). Check BEFORE storing, or a[i] pairs with itself.
def two_sum(a, t):
    seen = {}                               # value -> index it was seen at

    for i, v in enumerate(a):
        need = t - v                        # the ONE partner that works
        if need in seen:                    # has it already gone past?
            return [seen[need], i]
        seen[v] = i                         # store AFTER checking

    return []

// Three regions and one unclassified gap [mid, high]. The invariant
// is a claim about RANGES, and every line below protects it.
void sortColors(vector<int>& a) {
    int low = 0, mid = 0, high = a.size() - 1;

    while (mid <= high) {                   // <= : [mid, high] is INCLUSIVE
        if (a[mid] == 0) swap(a[low++], a[mid++]);      // both advance
        else if (a[mid] == 1) mid++;                    // already home
        else swap(a[mid], a[high--]);                   // mid does NOT move
    }
}

// Three regions and one unclassified gap [mid, high]. The invariant
// is a claim about RANGES, and every line below protects it.
public void sortColors(int[] a) {
    int low = 0, mid = 0, high = a.length - 1;

    while (mid <= high) {                   // <= : [mid, high] is INCLUSIVE
        if (a[mid] == 0) {
            int t = a[low]; a[low++] = a[mid]; a[mid++] = t;   // both advance
        } else if (a[mid] == 1) {
            mid++;                          // already where it belongs
        } else {
            int t = a[mid]; a[mid] = a[high]; a[high--] = t;   // mid STAYS
        }
    }
}

# Three regions and one unclassified gap [mid, high]. The invariant
# is a claim about RANGES, and every line below protects it.
def sort_colors(a):
    low, mid, high = 0, 0, len(a) - 1

    while mid <= high:                      # <= : [mid, high] is INCLUSIVE
        if a[mid] == 0:
            a[low], a[mid] = a[mid], a[low]                 # both advance
            low, mid = low + 1, mid + 1
        elif a[mid] == 1:
            mid += 1                                        # already home
        else:
            a[mid], a[high] = a[high], a[mid]               # mid does NOT move
            high -= 1

// Unequal elements annihilate in pairs. A value holding more than half
// cannot be fully cancelled, so it is the ONLY POSSIBLE survivor -- which
// is not the same as proof that it IS the majority. Hence pass two.
int majorityElement(vector<int>& a) {
    int cand = 0, cnt = 0;

    for (int v : a) {
        if (cnt == 0) cand = v;             // prefix cancelled: restart here
        cnt += (v == cand) ? 1 : -1;        // agree, or annihilate
    }
    int c = 0;
    for (int v : a) c += (v == cand);       // VERIFY -- this IS the algorithm
    return c > a.size() / 2 ? cand : -1;
}

// Unequal elements annihilate in pairs. A value holding more than half
// cannot be fully cancelled, so it is the ONLY POSSIBLE survivor -- which
// is not the same as proof that it IS the majority. Hence pass two.
public int majorityElement(int[] a) {
    int cand = 0, cnt = 0;

    for (int v : a) {
        if (cnt == 0) cand = v;             // prefix cancelled: restart here
        cnt += (v == cand) ? 1 : -1;        // agree, or annihilate
    }
    int c = 0;
    for (int v : a) if (v == cand) c++;     // VERIFY -- this IS the algorithm
    return c > a.length / 2 ? cand : -1;
}

# Unequal elements annihilate in pairs. A value holding more than half
# cannot be fully cancelled, so it is the ONLY POSSIBLE survivor -- which
# is not the same as proof that it IS the majority. Hence pass two.
def majority_element(a):
    cand, cnt = None, 0

    for v in a:
        if cnt == 0: cand = v               # prefix cancelled: restart here
        cnt += 1 if v == cand else -1       # agree, or annihilate

    return cand if a.count(cand) > len(a) // 2 else -1   # VERIFY

// One decision per element: extend the run, or start over here.
// cur  = best run ENDING AT i.   best = best run ANYWHERE so far.
// Collapsing those two into one variable is how this usually breaks.
int maxSubArray(vector<int>& a) {
    int cur = a[0], best = a[0];            // NOT 0 - handles all-negative input

    for (int i = 1; i < a.size(); i++) {
        cur  = max(a[i], cur + a[i]);       // a prefix that hurts is dropped
        best = max(best, cur);              // record on EVERY element
    }
    return best;
}

// One decision per element: extend the run, or start over here.
// cur  = best run ENDING AT i.   best = best run ANYWHERE so far.
// Collapsing those two into one variable is how this usually breaks.
public int maxSubArray(int[] a) {
    int cur = a[0], best = a[0];            // NOT 0 - handles all-negative

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

# One decision per element: extend the run, or start over here.
# cur  = best run ENDING AT i.   best = best run ANYWHERE so far.
# Collapsing those two into one variable is how this usually breaks.
def max_sub_array(a):
    cur = best = a[0]                       # NOT 0 - handles all-negative input

    for v in a[1:]:
        cur = max(v, cur + v)               # a prefix that hurts is dropped
        best = max(best, cur)               # record on EVERY element

    return best

// Two destination cursors, each stepping by TWO. One visits only even
// indices and the other only odd ones, so they are disjoint by construction
// and no bounds check between them is ever needed.
vector<int> rearrangeArray(vector<int>& a) {
    vector<int> out(a.size());
    int pos = 0, neg = 1;                   // first even slot, first odd slot

    for (int v : a) {
        if (v > 0) { out[pos] = v; pos += 2; }
        else       { out[neg] = v; neg += 2; }
    }
    return out;                             // order kept within each sign
}

// Two destination cursors, each stepping by TWO. One visits only even
// indices and the other only odd ones, so they are disjoint by construction
// and no bounds check between them is ever needed.
public int[] rearrangeArray(int[] a) {
    int[] out = new int[a.length];
    int pos = 0, neg = 1;                   // even slots / odd slots

    for (int v : a) {
        if (v > 0) { out[pos] = v; pos += 2; }
        else       { out[neg] = v; neg += 2; }
    }
    return out;
}

# Two destination cursors, each stepping by TWO. One visits only even
# indices and the other only odd ones, so they are disjoint by construction
# and no bounds check between them is ever needed.
def rearrange_array(a):
    out = [0] * len(a)
    pos, neg = 0, 1                         # first even slot, first odd slot

    for v in a:
        if v > 0:
            out[pos] = v; pos += 2
        else:
            out[neg] = v; neg += 2

    return out                              # order kept within each sign

// A descending suffix is ALREADY the largest arrangement of its values,
// so the change must happen at the last position with room to grow.
void nextPermutation(vector<int>& a) {
    int n = a.size(), i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;         // find the pivot

    if (i >= 0) {
        int j = n - 1;
        while (a[j] <= a[i]) j--;                   // RIGHTMOST value above it
        swap(a[i], a[j]);                           // smallest possible increase
    }
    reverse(a.begin() + i + 1, a.end());            // descending -> ascending
}

// A descending suffix is ALREADY the largest arrangement of its values,
// so the change must happen at the last position with room to grow.
public void nextPermutation(int[] a) {
    int n = a.length, i = n - 2;
    while (i >= 0 && a[i] >= a[i + 1]) i--;         // find the pivot

    if (i >= 0) {
        int j = n - 1;
        while (a[j] <= a[i]) j--;                   // smallest value ABOVE it
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
    for (int l = i + 1, r = n - 1; l < r; l++, r--) {   // reverse, not sort:
        int t = a[l]; a[l] = a[r]; a[r] = t;           // the suffix descends
    }
}

# A descending suffix is ALREADY the largest arrangement of its values,
# so the change must happen at the last position with room to grow.
def next_permutation(a):
    n = len(a)
    i = n - 2
    while i >= 0 and a[i] >= a[i + 1]: i -= 1       # find the pivot

    if i >= 0:
        j = n - 1
        while a[j] <= a[i]: j -= 1                  # RIGHTMOST value above it
        a[i], a[j] = a[j], a[i]                     # smallest possible increase

    a[i + 1:] = reversed(a[i + 1:])                 # descending -> ascending

// A while inside a for, and still O(n) -- because of ONE guard.
// Only a value with no left neighbour starts a walk, so every run is
// traversed exactly once across the whole execution. Drop the guard and
// the identical code becomes O(n^2).
int longestConsecutive(vector<int>& a) {
    unordered_set<int> s(a.begin(), a.end());       // dedupes for free
    int best = 0;

    for (int v : s) {
        if (s.count(v - 1)) continue;               // not a head - skip
        int x = v, len = 1;
        while (s.count(x + 1)) { x++; len++; }      // walk the run once
        best = max(best, len);
    }
    return best;
}

// A while inside a for, and still O(n) -- because of ONE guard.
// Only a value with no left neighbour starts a walk, so every run is
// traversed exactly once across the whole execution. Drop the guard and
// the identical code becomes O(n^2).
public int longestConsecutive(int[] a) {
    Set<Integer> s = new HashSet<>();
    for (int v : a) s.add(v);

    int best = 0;
    for (int v : s) {
        if (s.contains(v - 1)) continue;    // THE guard: only run starts
        int len = 1;
        while (s.contains(v + len)) len++;
        best = Math.max(best, len);
    }
    return best;
}

# A while inside a for, and still O(n) -- because of ONE guard.
# Only a value with no left neighbour starts a walk, so every run is
# traversed exactly once across the whole execution. Drop the guard and
# the identical code becomes O(n^2).
def longest_consecutive(a):
    s = set(a)                                      # dedupes for free
    best = 0

    for v in s:
        if v - 1 in s: continue                     # not a head - skip
        x, length = v, 1
        while x + 1 in s:                           # walk the run once
            x, length = x + 1, length + 1
        best = max(best, length)

    return best

// The matrix stores its own bookkeeping: row 0 and column 0 become the
// marker strips. a[0][0] is the ONE collision -- it cannot mark both, so
// column 0's fate lives in a single boolean.
void setZeroes(vector<vector<int>>& a) {
    int m = a.size(), n = a[0].size();
    bool col0 = false;

    for (int r = 0; r < m; r++) {
        if (a[r][0] == 0) col0 = true;
        for (int c = 1; c < n; c++)
            if (a[r][c] == 0) a[r][0] = a[0][c] = 0;    // leave notes, do not clear
    }
    for (int r = m - 1; r >= 0; r--) {                  // bottom-up: read before overwrite
        for (int c = n - 1; c >= 1; c--)
            if (a[r][0] == 0 || a[0][c] == 0) a[r][c] = 0;
        if (col0) a[r][0] = 0;                          // column 0 handled last
    }
}

// The matrix stores its own bookkeeping: row 0 and column 0 become the
// marker strips. a[0][0] is the ONE collision -- it cannot mark both, so
// column 0's fate lives in a single boolean.
public void setZeroes(int[][] a) {
    int m = a.length, n = a[0].length;
    boolean col0 = false;

    for (int r = 0; r < m; r++) {
        if (a[r][0] == 0) col0 = true;      // column 0 marked separately
        for (int c = 1; c < n; c++)
            if (a[r][c] == 0) { a[r][0] = 0; a[0][c] = 0; }
    }
    for (int r = m - 1; r >= 0; r--) {      // BACKWARDS: markers read last
        for (int c = n - 1; c >= 1; c--)
            if (a[r][0] == 0 || a[0][c] == 0) a[r][c] = 0;
        if (col0) a[r][0] = 0;
    }
}

# The matrix stores its own bookkeeping: row 0 and column 0 become the
# marker strips. a[0][0] is the ONE collision -- it cannot mark both, so
# column 0's fate lives in a single boolean.
def set_zeroes(a):
    m, n = len(a), len(a[0])
    col0 = False

    for r in range(m):
        if a[r][0] == 0: col0 = True
        for c in range(1, n):
            if a[r][c] == 0: a[r][0] = a[0][c] = 0       # leave notes, do not clear

    for r in range(m - 1, -1, -1):                       # bottom-up: read before overwrite
        for c in range(n - 1, 0, -1):
            if a[r][0] == 0 or a[0][c] == 0: a[r][c] = 0
        if col0: a[r][0] = 0                             # column 0 handled last

// 90 clockwise = transpose, then reverse each row. Both are reflections,
// and their composition is the rotation. The inner loop starts at r+1 so
// each pair swaps ONCE -- running the full square would undo the transpose.
void rotate(vector<vector<int>>& a) {
    int n = a.size();

    for (int r = 0; r < n; r++)
        for (int c = r + 1; c < n; c++)
            swap(a[r][c], a[c][r]);         // reflect across the main diagonal
    for (auto& row : a)
        reverse(row.begin(), row.end());    // flip left-to-right
}

// 90 clockwise = transpose, then reverse each row. Both are reflections,
// and their composition is the rotation. The inner loop starts at r+1 so
// each pair swaps ONCE -- running the full square would undo the transpose.
public void rotate(int[][] a) {
    int n = a.length;

    for (int r = 0; r < n; r++)
        for (int c = r + 1; c < n; c++) {       // r+1, not 0
            int t = a[r][c]; a[r][c] = a[c][r]; a[c][r] = t;
        }
    for (int[] row : a)
        for (int l = 0, rr = n - 1; l < rr; l++, rr--) {
            int t = row[l]; row[l] = row[rr]; row[rr] = t;
        }
}

# 90 clockwise = transpose, then reverse each row. Both are reflections,
# and their composition is the rotation. The inner loop starts at r+1 so
# each pair swaps ONCE -- running the full square would undo the transpose.
def rotate(a):
    n = len(a)

    for r in range(n):
        for c in range(r + 1, n):
            a[r][c], a[c][r] = a[c][r], a[r][c]     # reflect across the diagonal
    for row in a:
        row.reverse()                               # flip left-to-right

// Four bounds that only shrink. The two inner guards are the whole
// problem: without them a lone final row or column is emitted twice.
vector<int> spiralOrder(vector<vector<int>>& a) {
    int top = 0, bot = a.size() - 1, left = 0, right = a[0].size() - 1;
    vector<int> out;

    while (top <= bot && left <= right) {
        for (int c = left; c <= right; c++) out.push_back(a[top][c]);
        top++;
        for (int r = top; r <= bot; r++) out.push_back(a[r][right]);
        right--;
        if (top <= bot) {                            // guard: still a row left?
            for (int c = right; c >= left; c--) out.push_back(a[bot][c]);
            bot--;
        }
        if (left <= right) {                         // guard: still a column left?
            for (int r = bot; r >= top; r--) out.push_back(a[r][left]);
            left++;
        }
    }
    return out;
}

// Four bounds that only shrink. The two inner guards are the whole
// problem: without them a lone final row or column is emitted twice.
public List<Integer> spiralOrder(int[][] a) {
    int top = 0, bot = a.length - 1, left = 0, right = a[0].length - 1;
    List<Integer> out = new ArrayList<>();

    while (top <= bot && left <= right) {
        for (int c = left; c <= right; c++) out.add(a[top][c]);
        top++;
        for (int r = top; r <= bot; r++)   out.add(a[r][right]);
        right--;
        if (top <= bot) {                                  // GUARD
            for (int c = right; c >= left; c--) out.add(a[bot][c]);
            bot--;
        }
        if (left <= right) {                               // GUARD
            for (int r = bot; r >= top; r--) out.add(a[r][left]);
            left++;
        }
    }
    return out;
}

# Four bounds that only shrink. The two inner guards are the whole
# problem: without them a lone final row or column is emitted twice.
def spiral_order(a):
    top, bot, left, right = 0, len(a) - 1, 0, len(a[0]) - 1
    out = []

    while top <= bot and left <= right:
        for c in range(left, right + 1): out.append(a[top][c])
        top += 1
        for r in range(top, bot + 1): out.append(a[r][right])
        right -= 1
        if top <= bot:                               # guard: still a row left?
            for c in range(right, left - 1, -1): out.append(a[bot][c])
            bot -= 1
        if left <= right:                            # guard: still a column left?
            for r in range(bot, top - 1, -1): out.append(a[r][left])
            left += 1

    return out

// Two Sum on prefix sums: a[j+1..i] sums to k iff P(j) = P(i) - k.
// The map counts prefix OCCURRENCES because we are counting subarrays,
// and it is seeded with {0:1} for the empty prefix. Negatives are handled
// for free -- which is exactly why a sliding window will not do.
int subarraySum(vector<int>& a, int k) {
    unordered_map<int, int> cnt{{0, 1}};    // the empty prefix counts
    int sum = 0, total = 0;

    for (int v : a) {
        sum += v;
        total += cnt[sum - k];              // every earlier P(j)=sum-k closes one
        cnt[sum]++;                         // record AFTER checking
    }
    return total;
}

// Two Sum on prefix sums: a[j+1..i] sums to k iff P(j) = P(i) - k.
// The map counts prefix OCCURRENCES because we are counting subarrays,
// and it is seeded with {0:1} for the empty prefix. Negatives are handled
// for free -- which is exactly why a sliding window will not do.
public int subarraySum(int[] a, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);                        // the empty prefix
    int prefix = 0, total = 0;

    for (int v : a) {
        prefix += v;
        total += count.getOrDefault(prefix - k, 0);   // how many starts qualify
        count.merge(prefix, 1, Integer::sum);
    }
    return total;
}

# Two Sum on prefix sums: a[j+1..i] sums to k iff P(j) = P(i) - k.
# The map counts prefix OCCURRENCES because we are counting subarrays,
# and it is seeded with {0:1} for the empty prefix. Negatives are handled
# for free -- which is exactly why a sliding window will not do.
from collections import defaultdict

def subarray_sum(a, k):
    cnt = defaultdict(int); cnt[0] = 1      # the empty prefix counts
    running = total = 0

    for v in a:
        running += v
        total += cnt[running - k]           # every earlier P(j)=running-k closes one
        cnt[running] += 1                   # record AFTER checking

    return total