/* Interview Related Codes */

class LIS {
    public:
    vector<int> arr;
    vector<int> lis;
    LIS(vector<int> input){
        arr = input;
    }

    void computeLIS()
    {
        for(int i=0; i<arr.size(); i++){
            if(lis.empty()) lis.push_back(arr[i]);
            else {
                int maxElement = lis[(int)lis.size()-1];
                if(arr[i] > maxElement) lis.push_back(arr[i]);
                else {
                    int pos = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
                    lis[pos] = arr[i];
                }
            }
        }
    }

    vector<int> findLIS()
    {
        computeLIS();
        return lis;
    }

};

class maxHeap {
private:
    vector<int> heap;
    int findParent(int idx){
        return (idx-1)/2;
    }
    int findLeft(int idx){
        return 2*idx+1;
    }
    int findRight(int idx){
        return 2*idx+2;
    }
    void heapifyUp(int idx){
        if(idx && heap[findParent(idx)] < heap[idx]){
            swap(heap[findParent(idx)], heap[idx]);
            heapifyUp(findParent(idx));
        }
    }
    void heapifyDown(int idx){
        int left = findLeft(idx);
        int right = findRight(idx);

        int valid = idx;
        if(left < findSize() && heap[left] > heap[idx]) valid = left;
        if(right < findSize() && heap[right] > heap[idx]) valid = right;

        if(valid != idx){
            swap(heap[idx], heap[valid]);
            heapifyDown(valid);
        }
    }
public:
    unsigned int findSize(){
        return (unsigned int) heap.size();
    }
    bool isEmpty(){
        return (findSize() == 0);
    }
    void push(int val){
        heap.push_back(val);
        int idx = findSize() - 1;
        heapifyUp(idx);
    }
    void pop(){
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
    }
    int top(){
        return heap[0];
    }
    void prnt(){
        cout << "myHeap ";
        for(int i=0; i<heap.size(); i++) cout << heap[i] << " ";
        cout << endl;
    }
};

class rollingHash{
public:
    #define ll long long
    string text, pattern;
    ll base, MOD;
    rollingHash(string givenText, string givenPattern, ll givenBase, ll givenMod){
        text = givenText;
        pattern = givenPattern;
        base = givenBase;
        MOD = givenMod;
    }
    ll kLengthPrefixHash(string &str, int k)
    {
        ll power = 1;
        ll ans = 0;
        for(int i=k-1; i>=0; i--){
            ans = ans + (power*(str[i]-'a'))%MOD;
            ans = ans%MOD;
            power = (power*base)%MOD;
        }
        return ans;
    }
    ll powerFunction(ll x, ll y)
    {
        ll ans = 1;
        for(int i=1; i<=y; i++) ans = (ans*x)%MOD;
        return ans;
    }
    vector<int> findPositionMatch()
    {
        int len = (int) pattern.length();
        ll hashValue = kLengthPrefixHash(pattern, len);
        ll rollingHash = kLengthPrefixHash(text, len);
        vector<int> answer;
        answer.push_back(0);
        ll power = powerFunction(base, len-1);
        for(int i=len; i<text.length(); i++){
            int prev_char = text[i-len]-'a';
            int cur_char = text[i]-'a';
            rollingHash = (rollingHash - (prev_char * power)%MOD + MOD)%MOD;
            rollingHash = ((rollingHash*base)%MOD + cur_char)%MOD;
            if(hashValue == rollingHash) answer.push_back(i-len+1);
        }
        return answer;
    }
};

class quickSort{
public:
    int partitionIdx(vector<int> &arr, int l, int r)
    {
        int idx = l+1;
        int pivot = arr[l];
        for(int j=l+1; j<=r; j++){
            if(arr[j] < pivot){
                swap(arr[idx], arr[j]);
                idx++;
            }
        }
        swap(arr[l], arr[idx-1]);
        return idx-1;
    }

    void quick_sort(vector<int> &arr, int l, int r)
    {
        if(l < r){
            int idx = partitionIdx(arr, l, r);
            quick_sort(arr, l, idx-1);
            quick_sort(arr, idx+1, r);
        }
    }
};

class KMP{
public:
    vector<int> prefix_function(string str)
    {
        int n = (int) str.length();
        vector<int> pi(n);
        pi[0] = 0;
        for(int i=1; i<n; i++){
            int j = pi[i-1];
            while(j > 0 && str[i] != str[j]){
                j = pi[j-1];
            }
            if(str[i] == str[j]) ++j;
            pi[i] = j;
        }
        return pi;
    }
};

struct Point{
    int x, y;
};

class geometry{
public:
    // Given three colinear points p, q, r, the function checks
    // if point q lies on the segment 'pr'
    bool onSegment(Point p, Point q, Point r){
        if(q.x >= min(p.x, r.x) && q.x <= max(p.x, r.x) &&
           q.y >= min(p.y, r.y) && q.y <= max(p.y, r.y)){
            return true;
           }
        else return false;
    }
    // To find orientation of ordered triplet (p1, p2, p3)
    // The function returns the following values
    // 0 -> p, q, r are collinear
    // 1 -> clockwise
    // 2 -> counter clockwise
    int orientation(Point p1, Point p2, Point p3){
        int val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
        if(val == 0) return 0;
        return (val > 0) ? 1:2;
    }
    bool doIntersect(Point p1, Point q1, Point p2, Point q2)
    {
        int o1 = orientation(p1, q1, p2);
        int o2 = orientation(p1, q1, q2);
        int o3 = orientation(p2, q2, p1);
        int o4 = orientation(p2, q2, q1);

        if(o1 == 0 && onSegment(p1, p2, q1)) return true;
        if(o2 == 0 && onSegment(p1, q2, p1)) return true;
        if(o3 == 0 && onSegment(p2, p1, q2)) return true;
        if(o4 == 0 && onSegment(p2, q1, q2)) return true;
        return false;
    }
};

class priorityQueueComparator{
public:
    struct Person {
        int age, height;
    };

    struct customCompare{
        bool operator()(Person p, Person q){
            return p.age<q.age;
        }
    };
    priority_queue<Person, vector<Person>, customCompare> pq;
};

class operatorOverloading{
    struct Person{
        int age, height;
        Person(int _age, int _height){
            age = _age;
            height = _height;
        }
        bool operator < (const Person &other){
            return age < other.age;
        }
    };
};