#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// ============================================================================
// SEGMENT TREE WITH WALK OPERATIONS (FIND FIRST / LAST, K‑TH, PREFIX WALK)
// ============================================================================
// This file provides a generic segment tree that supports:
//   • point assignment
//   • range query (sum, max, min, gcd, …)
//   • range add (lazy propagation – only for sum)
//   • "walk" functions:
//       - maxRight / minLeft  (AtCoder style, monotonic predicate)
//       - findKth             (k‑th element by prefix sum)
//       - walkToSum           (first position where prefix sum ≥ target)
//
// All functions are ready to be used as black boxes.
// Read the comments above each function to understand:
//   - what it solves
//   - what input it expects
//   - what it returns
//   - time complexity
//   - important constraints / assumptions
// ============================================================================

// ============================================================================
// Generic Segment Tree Class
// ============================================================================
// T        : type of the elements (int, long long, …)
// combine  : associative operation (e.g. sum, max, min, gcd)
// neutral  : identity element for combine (0 for sum, -INF for max, +INF for min, …)
// useLazy  : if true, enables range add (requires combine = sum and neutral = 0)
//            If you only need point updates / range queries, set useLazy = false.
//
// IMPORTANT:
//   • rangeAdd() works ONLY if combine is addition (sum) and neutral = 0.
//   • maxRight() and minLeft() require a predicate that is monotonic over the
//     monoid (see explanations inside).
//   • findKth() and walkToSum() also assume combine is sum.
//   • All indices are 0‑based and inclusive in queries, except where noted.
// ============================================================================

template <class T>
class SegTree {
private:
    int n;                      // number of elements
    vector<T> tree, lazy;       // segment tree and lazy values
    T neutral;                  // identity element
    function<T(T,T)> combine;   // associative operation
    bool useLazy;               // whether lazy range add is enabled

    // ---------------------- internal helpers ----------------------
    void build(int node, int l, int r, const vector<T>& data) {
        if (l == r) {
            tree[node] = data[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(node<<1, l, mid, data);
        build(node<<1|1, mid+1, r, data);
        tree[node] = combine(tree[node<<1], tree[node<<1|1]);
    }

    // apply an addition to a node – works ONLY for sum
    void applyAdd(int node, T val) {
        tree[node] += val;
        if (useLazy) lazy[node] += val;
    }

    void push(int node) {
        if (!useLazy) return;
        if (lazy[node] != neutral) {
            applyAdd(node<<1, lazy[node]);
            applyAdd(node<<1|1, lazy[node]);
            lazy[node] = neutral;
        }
    }

    // point set (no lazy push needed for point set? we push when going down)
    void pointSet(int node, int l, int r, int pos, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        push(node);
        int mid = (l + r) >> 1;
        if (pos <= mid) pointSet(node<<1, l, mid, pos, val);
        else pointSet(node<<1|1, mid+1, r, pos, val);
        tree[node] = combine(tree[node<<1], tree[node<<1|1]);
    }

    // range add (only for sum)
    void rangeAdd(int node, int l, int r, int ql, int qr, T val) {
        if (ql <= l && r <= qr) {
            applyAdd(node, val);
            return;
        }
        push(node);
        int mid = (l + r) >> 1;
        if (ql <= mid) rangeAdd(node<<1, l, mid, ql, qr, val);
        if (qr > mid)  rangeAdd(node<<1|1, mid+1, r, ql, qr, val);
        tree[node] = combine(tree[node<<1], tree[node<<1|1]);
    }

    // range query (works for any combine)
    T query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[node];
        push(node);
        int mid = (l + r) >> 1;
        if (qr <= mid) return query(node<<1, l, mid, ql, qr);
        if (ql > mid)  return query(node<<1|1, mid+1, r, ql, qr);
        return combine(
            query(node<<1, l, mid, ql, qr),
            query(node<<1|1, mid+1, r, ql, qr)
        );
    }

    // ---------- maxRight helper (inclusive tree) ----------
    // Finds the first index r in [ql, n] where the predicate becomes false.
    // sm accumulates the value of the prefix that has been proven to satisfy the predicate.
    // Returns n if the predicate stays true for the whole suffix.
    int maxRightRec(int node, int l, int r, int ql, T& sm, const function<bool(T)>& pred) {
        if (r < ql) return n;                     // segment completely before ql
        T combined = combine(sm, tree[node]);
        // If the whole segment is inside the query and adding it keeps pred true, take it.
        if (ql <= l && r <= n-1 && pred(combined)) {
            sm = combined;
            return n;
        }
        if (l == r) {
            // leaf: we must decide whether to include it
            T leafVal = tree[node];
            T newVal = combine(sm, leafVal);
            if (pred(newVal)) {
                sm = newVal;
                return n;
            } else {
                return l;   // this leaf is the first failure point
            }
        }
        push(node);
        int mid = (l + r) >> 1;
        int res = maxRightRec(node<<1, l, mid, ql, sm, pred);
        if (res != n) return res;
        return maxRightRec(node<<1|1, mid+1, r, ql, sm, pred);
    }

    // ---------- minLeft helper (inclusive tree) ----------
    // Finds the first index l (from the right) where the predicate fails,
    // while building the suffix from right to left.
    // Parameter rbound is the exclusive right bound of the query (0 <= rbound <= n).
    // sm accumulates the suffix that has been proven to satisfy pred.
    // Returns -1 if the predicate holds for the whole suffix down to index 0.
    // Otherwise returns the index of the element that cannot be included.
    int minLeftRec(int node, int l, int r, int rbound, T& sm, const function<bool(T)>& pred) {
        if (l >= rbound) return -1;               // segment completely after the query range
        T combined = combine(tree[node], sm);
        // If the whole segment is inside the query and adding it keeps pred true, take it.
        if (r <= rbound-1 && pred(combined)) {
            sm = combined;
            return -1;
        }
        if (l == r) {
            // leaf: test if we can include it
            T leafVal = tree[node];
            T newVal = combine(leafVal, sm);
            if (pred(newVal)) {
                sm = newVal;
                return -1;
            } else {
                return l;   // cannot include this leaf
            }
        }
        push(node);
        int mid = (l + r) >> 1;
        // go right first (since we are moving right‑to‑left)
        int res = minLeftRec(node<<1|1, mid+1, r, rbound, sm, pred);
        if (res != -1) return res;
        return minLeftRec(node<<1, l, mid, rbound, sm, pred);
    }

    // ---------- findKth helper (sum only) ----------
    // assumes tree[node] stores the sum of its segment.
    // k is 0‑based: we want the smallest index p such that prefix sum up to p > k.
    int findKthRec(int node, int l, int r, T k) {
        if (l == r) return l;
        push(node);
        int mid = (l + r) >> 1;
        if (tree[node<<1] > k) return findKthRec(node<<1, l, mid, k);
        else return findKthRec(node<<1|1, mid+1, r, k - tree[node<<1]);
    }

    // ---------- walkToSum helper (sum only) ----------
    // Finds the first position p (starting from ql) where the accumulated sum >= target.
    // acc holds the sum of the prefix that has already been taken.
    // Returns n if the total sum from ql to end is < target.
    int walkToSumRec(int node, int l, int r, int ql, T& acc, T target) {
        if (r < ql) return n;
        if (ql <= l) {
            T newAcc = combine(acc, tree[node]);
            if (newAcc < target) {
                acc = newAcc;
                return n;           // whole segment taken, still not enough
            }
            if (l == r) {
                return l;           // leaf makes sum reach target
            }
        }
        push(node);
        int mid = (l + r) >> 1;
        int res = walkToSumRec(node<<1, l, mid, ql, acc, target);
        if (res != n) return res;
        return walkToSumRec(node<<1|1, mid+1, r, ql, acc, target);
    }

public:
    // ---------- constructor ----------
    // data     : initial array (0‑indexed)
    // neutral  : identity element for combine
    // combine  : associative binary operation (e.g. [](T a, T b){ return a+b; })
    // useLazy  : enable range add (requires combine = addition)
    SegTree(const vector<T>& data, T neutral, function<T(T,T)> combine, bool useLazy = false)
        : neutral(neutral), combine(combine), useLazy(useLazy) {
        n = (int)data.size();
        tree.assign(4*n + 5, neutral);
        lazy.assign(4*n + 5, neutral);
        build(1, 0, n-1, data);
    }

    // ---------- point assignment ----------
    // Sets the value at position pos (0‑indexed) to val.
    // Time: O(log n)
    void pointSet(int pos, T val) {
        pointSet(1, 0, n-1, pos, val);
    }

    // ---------- range add (lazy) ----------
    // Adds val to every element in [l, r] (inclusive).
    // ONLY works if combine is sum (addition) and neutral = 0.
    // Time: O(log n)
    void rangeAdd(int l, int r, T val) {
        if (!useLazy) {
            cerr << "WARNING: rangeAdd called but lazy is disabled. This may give wrong results.\n";
        }
        rangeAdd(1, 0, n-1, l, r, val);
    }

    // ---------- range query ----------
    // Returns combine( data[l], data[l+1], …, data[r] ) (inclusive).
    // Works for any combine.
    // Time: O(log n)
    T query(int l, int r) {
        return query(1, 0, n-1, l, r);
    }

    // ---------- maxRight (AtCoder style) ----------
    // Finds the smallest index r (l <= r <= n) such that
    //   pred( combine( data[l], data[l+1], …, data[r-1] ) ) == false,
    // i.e. the first position where the predicate becomes false.
    // If the predicate is true for the whole array, returns n.
    // The empty prefix (r = l) is always considered true, so pred(neutral) must be true.
    //
    // The predicate pred must be monotonic:
    //   if pred(X) is true, then pred( combine(X, Y) ) may be true or false,
    //   but once it becomes false, it stays false when you extend the segment.
    //   (This holds for many natural predicates, e.g. sum < K).
    //
    // Time: O(log n)
    int maxRight(int l, const function<bool(T)>& pred) {
        T sm = neutral;
        int res = maxRightRec(1, 0, n-1, l, sm, pred);
        return res;   // res is either n or the first failure index
    }

    // ---------- minLeft (AtCoder style) ----------
    // Given r (0 <= r <= n), finds the minimum index l such that
    //   pred( combine( data[l], data[l+1], …, data[r-1] ) ) == true.
    // In other words, the largest prefix that can be excluded from the right
    // while keeping the predicate true on the remaining suffix.
    // The empty suffix (l = r) is always considered true, so pred(neutral) must be true.
    //
    // Predicate monotonic as for maxRight.
    //
    // Time: O(log n)
    int minLeft(int r, const function<bool(T)>& pred) {
        T sm = neutral;
        int res = minLeftRec(1, 0, n-1, r, sm, pred);
        return (res == -1 ? 0 : res + 1);
    }

    // ---------- findKth (sum only) ----------
    // Finds the smallest index p (0‑based) such that:
    //   sum( data[0] + data[1] + … + data[p] ) > k
    // (i.e. the position of the (k+1)‑th unit when elements represent frequencies).
    // This assumes all data elements are non‑negative and combine is addition.
    // k is 0‑based: k = 0 returns the position of the first element that makes prefix sum > 0.
    //
    // Returns p, or n if total sum <= k.
    // Time: O(log n)
    int findKth(T k) {
        if (tree[1] <= k) return n;
        return findKthRec(1, 0, n-1, k);
    }

    // ---------- walkToSum (sum only) ----------
    // Finds the smallest index p (0‑based) such that:
    //   sum( data[start] + data[start+1] + … + data[p] ) >= target
    // The search starts from position 'start' (default 0).
    // Returns p, or n if the total sum from start to n-1 is < target.
    // This is useful for prefix‑based queries.
    // Time: O(log n)
    int walkToSum(T target, int start = 0) {
        if (start >= n) return n;
        T acc = neutral;   // neutral = 0 for sum
        int res = walkToSumRec(1, 0, n-1, start, acc, target);
        return res;
    }

    // ---------- total aggregate ----------
    // Returns combine of all elements (tree[1]).
    // Time: O(1)
    T all() const {
        return tree[1];
    }
};

// ============================================================================
// ADDITIONAL HELPER FUNCTIONS (standalone)
// These are often used together with a segment tree that stores sums
// (like a Fenwick alternative) or for two‑pointer problems.
// ============================================================================

// ----------------------------------------------------------------------------
// 1) Maximum number of pairs from two sorted arrays with sum ≤ K
// ----------------------------------------------------------------------------
// PURPOSE:
//   Given two arrays A and B, find the maximum number of disjoint pairs
//   (one from A, one from B) such that A[i] + B[j] ≤ K.
// INPUT:
//   A, B : vectors of ints (will be sorted internally)
//   K    : upper bound
// OUTPUT:
//   Maximum number of pairs.
// TIME: O(n log n + m log m) due to sorting, then O(n+m) two pointers.
int maxPairsWithSumAtMostK(vector<int>& A, vector<int>& B, int K) {
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    int i = 0, j = (int)B.size() - 1;
    int ans = 0;
    while (i < (int)A.size() && j >= 0) {
        if (A[i] + B[j] <= K) {
            ans++;
            i++;
            j--;
        } else {
            j--;
        }
    }
    return ans;
}

// ----------------------------------------------------------------------------
// 2) Count subarrays with sum in [L, R] (non‑negative array only)
// ----------------------------------------------------------------------------
// PURPOSE:
//   Counts the number of contiguous subarrays whose sum lies in [L, R].
// INPUT:
//   nums : vector<int> with NON‑NEGATIVE elements.
//   L, R : long long bounds (L ≤ R).
// OUTPUT:
//   Number of subarrays.
// TIME: O(n log n)
// WARNING: Works only if all nums are non‑negative (otherwise prefix sums
//          are not monotonic and the sorting trick fails).
ll countSubarraysInRange(const vector<int>& nums, ll L, ll R) {
    int n = nums.size();
    vector<ll> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i+1] = pref[i] + nums[i];
    sort(pref.begin(), pref.end());
    auto countPairsLE = [&](ll X) -> ll {
        ll cnt = 0;
        int j = 0;
        for (int i = 0; i < (int)pref.size(); i++) {
            if (j < i) j = i;
            while (j + 1 < (int)pref.size() && pref[j+1] - pref[i] <= X) j++;
            cnt += (j - i);
        }
        return cnt;
    };
    return countPairsLE(R) - countPairsLE(L - 1);
}

// ----------------------------------------------------------------------------
// 3) Closest pair sum from two arrays
// ----------------------------------------------------------------------------
// PURPOSE:
//   Find a pair (a∈A, b∈B) whose sum is closest to a given target.
// INPUT:
//   A, B : vectors of ints (will be sorted internally)
//   target : int
// OUTPUT:
//   pair<int,int> with the chosen elements.
// TIME: O(n log n + m log m) sorting, then O(n+m) two pointers.
pair<int,int> closestPairFromTwoArrays(vector<int>& A, vector<int>& B, int target) {
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    int i = 0, j = (int)B.size() - 1;
    int bestDiff = INT_MAX;
    pair<int,int> best = {A[0], B[0]};
    while (i < (int)A.size() && j >= 0) {
        int sum = A[i] + B[j];
        int diff = abs(sum - target);
        if (diff < bestDiff) {
            bestDiff = diff;
            best = {A[i], B[j]};
        }
        if (sum < target) i++;
        else if (sum > target) j--;
        else break;
    }
    return best;
}

// ----------------------------------------------------------------------------
// 4) Median of two sorted arrays (merge to middle)
// ----------------------------------------------------------------------------
// PURPOSE:
//   Returns the median of the merged array from two sorted arrays.
// INPUT:
//   A, B : sorted vectors (non‑decreasing)
// OUTPUT:
//   double median.
// TIME: O(n+m)
double medianOfTwoSortedArrays(const vector<int>& A, const vector<int>& B) {
    int n = A.size(), m = B.size();
    int total = n + m;
    int i = 0, j = 0;
    int prev = 0, cur = 0;
    for (int k = 0; k <= total/2; k++) {
        prev = cur;
        if (i < n && (j >= m || A[i] < B[j]))
            cur = A[i++];
        else
            cur = B[j++];
    }
    if (total % 2 == 1) return cur;
    return (prev + cur) / 2.0;
}

// ----------------------------------------------------------------------------
// 5) Minimum operations to make all array elements equal (cost = sum |x - median|)
// ----------------------------------------------------------------------------
// PURPOSE:
//   Minimum total number of increment/decrement operations to make all elements equal.
// INPUT:
//   nums : vector<int>
// OUTPUT:
//   long long minimal cost.
// TIME: O(n log n) due to sorting, or O(n) with nth_element.
ll minOperationsToMakeEqual(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    sort(nums.begin(), nums.end());
    int median = nums[n/2];
    ll cost = 0;
    for (int x : nums) cost += llabs((ll)x - (ll)median);
    return cost;
}

// ============================================================================
// EXAMPLE USAGE (main)
// ============================================================================
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // ---------- Example 1: Segment Tree with sum ----------
    vector<int> data = {1, 3, 2, 5, 4};
    SegTree<int> st(data, 0, [](int a, int b){ return a + b; }, true); // with lazy

    cout << "Sum [0,4] = " << st.query(0, 4) << "\n";          // 15

    st.rangeAdd(1, 3, 2);   // add 2 to indices 1..3
    cout << "After add, sum [1,3] = " << st.query(1, 3) << "\n"; // (3+2)+(2+2)+(5+2)=16

    st.pointSet(2, 10);
    cout << "After set index 2 to 10, sum [0,4] = " << st.query(0, 4) << "\n";

    // ---------- Example 2: maxRight ----------
    vector<int> arr = {2, 3, 1, 4, 2};
    SegTree<int> st2(arr, 0, [](int a, int b){ return a + b; }, false);

    // pred(x) = x < 7  (monotonic: as we add more numbers, sum increases)
    auto pred = [](int x) { return x < 7; };
    int r = st2.maxRight(0, pred);
    cout << "maxRight: longest prefix from 0 with sum < 7 ends at index " << r << "\n";
    // prefix 0..2 sum = 2+3+1=6 <7, adding index 3 gives 10 >=7, so r=3.

    // ---------- Example 3: findKth ----------
    vector<int> weights = {0, 1, 0, 1, 0, 1};  // positions of ones
    SegTree<int> st3(weights, 0, [](int a, int b){ return a + b; }, false);
    int kth1 = st3.findKth(1); // k=1 (0‑based) -> second '1'
    cout << "Position of the 2nd '1' = " << kth1 << "\n"; // index 3 (since ones at 1,3,5)

    // ---------- Example 4: walkToSum ----------
    vector<int> vals = {5, 2, 8, 3, 6};
    SegTree<int> st4(vals, 0, [](int a, int b){ return a + b; }, false);
    int pos = st4.walkToSum(15, 0);  // need prefix sum >=15 from start
    cout << "First position where prefix sum >= 15 is " << pos << "\n"; // indices 0+1+2=15 -> pos=2

    pos = st4.walkToSum(10, 2);      // start at index 2: 8+3=11 -> pos=3
    cout << "From index 2, first pos with sum >=10 is " << pos << "\n"; // 3

    // ---------- Example 5: minLeft ----------
    // pred(x) = x >= 5 on suffix sums (monotonic when moving left)
    auto predMin = [](int x) { return x >= 5; };
    int l = st4.minLeft(5, predMin);   // r = 5 (exclusive, covers whole array)
    // Suffix from l to 4: we want smallest l such that sum(l..4) >= 5.
    // Suffixes: sum(4)=6>=5 -> l=4; sum(3..4)=9>=5 -> l=3; sum(2..4)=17>=5 -> l=2; sum(1..4)=19>=5 -> l=1; sum(0..4)=24>=5 -> l=0.
    // Smallest l that makes sum >=5 is actually 0? No, suffix sum from 4 is 6, so l=4 works. Smallest l is 4.
    cout << "minLeft: smallest l with sum(l..4) >= 5 is " << l << "\n"; // expected 4

    return 0;
}