class Solution {
    Integer[] memo;
    int MOD = 1_000_000_007;
    public int countGoodStrings(int low, int high, int zero, int one) {
        memo = new Integer[high + 1];
        int res = 0;
        for(int i = low; i <= high; i ++){
            res += dp(i,zero,one);
            res %= MOD;
        }
        return res;
    }
    private int dp(int l, int zero, int one){
        // base case 
        if(l == 0) return 1; // we made to zero then we have 1 good string
        if(l < zero && l < one) return 0; //this case we are not allowed to append 
        // solved case 
        if(memo[l] != null) return memo[l]; // we have done this before 
        // solving the problem 
        int appendZeros = dp(l - zero,zero,one);
        int appendOnes = dp(l - one, zero, one);
        return memo[l] = (appendOnes + appendZeros) % MOD;
    }
}

class Solution {
    long[] memo;
    public long mostPoints(int[][] questions) {
        memo = new long[questions.length];
        Arrays.fill(memo,-1);
        return dp(questions,0);
    }
    private long dp(int[][] questions, int curr){
        // base case 
        if(curr >= questions.length) return 0; // no more questions
        if(memo[curr] != -1) return memo[curr];
        // two case 
        long skip = dp(questions,curr + 1);
        long take = questions[curr][0] + dp(questions,curr + questions[curr][1] + 1);
        return memo[curr] = Math.max(skip,take);
    }
}

class Solution {
    int[][] memo;
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // to be as fast as possible we would want nums1 to be smaller
        if(nums1.length > nums2.length){
            return maxUncrossedLines(nums2,nums1);
        }
        int n = nums1.length;
        int m = nums2.length;
        memo = new int[n][m];
        for(int[] row : memo){
            Arrays.fill(row,-1);
        }
        return dp(nums1,nums2,0,0);
    }
    private int dp(int[] nums1, int[] nums2,int p1, int p2){
        // base case 
        // we have reached the end of either number
        if(p1 == nums1.length || p2 == nums2.length) return 0;
        
        // solved case
        if(memo[p1][p2] != -1) return memo[p1][p2];
        
        int res = 0;
        
        if(nums1[p1] == nums2[p2]){
            // we can connect them 
            res = 1 + dp(nums1,nums2,p1 + 1, p2 + 1);
        }else{
            // we cant connect them, we have two option
            // 1. we can skip the nums1 and not try to connect it 
            // 2. we can find the match number and connect nums2
            // note there is no going back 
            int skip = dp(nums1,nums2,p1 + 1, p2);
            int connect = dp(nums1,nums2,p1,p2 + 1);
            res = Math.max(skip,connect);
        }
        return memo[p1][p2] = res;
    }
}

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        // define the boundry 
        int up = 0;
        int down = n - 1;
        int left = 0;
        int right = n - 1;
        int curr = 1; // we starting inserting one 
        while(curr <= n * n){
            // we have more stuff to insert
            // first we want to insert from left to right
            for(int i = left; i <= right; i ++){
                res[up][i] = curr ++;
            }
            // now we want to insert downwards 
            for(int j = up + 1; j <= down; j ++){
                res[j][right] = curr;
                curr ++;
            }
            // now if we are not on the same row we would wanna go cross left 
            if(up != down){
                for(int i = right - 1; i >= left; i --){
                    res[down][i] = curr++;
                }
            }
            // now finally we want to go down to up 
            if(left != right){
                for(int j = down - 1; j > up; j --){
                    res[j][left] = curr ++;
                }
            }
            // shrink the boundry 
            left ++;
            right --;
            up ++;
            down --;
        }
        return res;
    }
    
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        int up = 0;
        int down = m - 1;
        int left = 0;
        int right = n - 1;

        while(res.size() < m * n){
            // there is more item to traverse
            // first we add everthing from left to right
            for(int i = left; i <= right; i ++){
                res.add(matrix[up][i]);
            }
            // now we add from up to down 
            for(int j = up + 1; j <= down; j ++){
                res.add(matrix[j][right]);
            }
            // going from right to left but we got to make sure up != down that way we not adding duplicate row
            if(up != down){
                for(int i = right - 1; i >= left; i --){
                    res.add(matrix[down][i]);
                }
            }
            // from bot to top
            if(left != right){
                // note we dont want to add matrix[up][left] it is added from the left to right traversal!
                for(int j = down - 1; j > up; j --){
                    res.add(matrix[j][left]);
                }
            }

            // now we just have to shrink the boundry
            left ++;
            right --;
            up ++;
            down --;
        }
        return res;
    }
}

class Solution {
    public int diagonalSum(int[][] mat) {
        int res = 0;
        int n = mat.length, m = mat[0].length;
        int row = 0, col_primary = 0, col_secondary = m - 1;
        while(row < n){
            res += mat[row][col_primary];
            res += mat[row][col_secondary];
            if(col_primary == col_secondary){
                res -= mat[row][col_primary];
            }
            row ++;
            col_primary ++;
            col_secondary --;
        }
        return res;
        
    }
    
}

class Solution {
    public int[][] multiply(int[][] mat1, int[][] mat2) {
        int n = mat1.length;
        int k = mat1[0].length;
        int m = mat2[0].length;
        int[][] res = new int[n][m];

        for(int rowIndex = 0; rowIndex < n; rowIndex ++){
            for(int elementIndex = 0; elementIndex < k; elementIndex++){
                if(mat1[rowIndex][elementIndex] != 0){
                    // if just 0 we dont have to calculate it just gonna be 0 
                    for(int colIndex = 0; colIndex < m; colIndex++){
                        res[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                    } 
                }
            }
        }
        return res;

    }
}

class Solution {
    List<Integer> answer;
    // Find the rightmost insertion position. We use a fixed-length array and a changeable right boundary 
    // to represent an arraylist of dynamic size.
    private int bisectRight(int[] A, int target, int right) {
        if (right == 0)
            return 0;
        int left = 0;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] <= target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
    
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.length, lisLength = 0;
        
        // lis[i] records the lowest increasing sequence of length i + 1.
        int[] answer = new int[n], lis = new int[n];

        for (int i = 0; i < n; ++i) {
            int height = obstacles[i];
            
            // Find the rightmost insertion position idx.
            int idx = bisectRight(lis, height, lisLength);
            if (idx == lisLength)
                lisLength++;

            lis[idx] = height;
            answer[i] = idx + 1;
        }
        return answer;
    }
}

class Solution {
    public int numSubseq(int[] nums, int target) {
        // still two pointer problem 
        int n = nums.length;
        int MOD = 1000000007;
        Arrays.sort(nums);

        // compute the value of 2 to the power of each value
        int[] power = new int[n];
        power[0] = 1;
        for(int i = 1; i < n; i ++){
            power[i] = (power[i - 1] * 2) % MOD;
        }

        int res = 0;
        int left = 0, right = n - 1;
        while(left <= right){
            if(nums[left] + nums[right] <= target){
                // what this means is the min at left and max at right,
                // there are 2 ^ right - left subsequence that have nums[left] as the min and nums[right] as max, all theses subsequence is meeting our requirement.
                res += power[right - left];
                res %= MOD;
                left ++;
            }else{
                // max is too big, we shrink the window.
                right --;
            }
        }
        return res;
    }
}

class Solution {
    public int maxVowels(String s, int k) {
        // sliding window 
        int left = 0, right = 0;
        int res = 0;
        int curr = 0;
        while(right < s.length()){
            char c = s.charAt(right);
            if(c == 'a' || c == 'e' || c == 'i' || c =='o' || c == 'u'){
                // vowel 
                curr ++;
            }
            
            // shrink window
            while((right - left + 1) > k){
                // it is too big 
                
                char shrink = s.charAt(left);
                if(shrink == 'a' || shrink == 'e' || shrink == 'i' || shrink =='o' || shrink == 'u'){
                // vowel 
                    curr --;
                }
                left ++;
            }
            if((right - left + 1) <= k){
                res = Math.max(res,curr);
            }
            right ++;
        }
        return res;
    }
}

class Solution {
    public String predictPartyVictory(String senate) {
        // baning the new opposite party be the best 
        StringBuilder senates = new StringBuilder(senate); // for easy deletion
        // Count of Each Type of Senator to check for Winner
        int rCount = 0;
        int dCount = 0;
        for (int i = 0; i < senates.length(); i++) {
            if (senates.charAt(i) == 'R') {
                rCount++;
            } else {
                dCount++;
            }
        }

        int turn = 0;
        while(rCount > 0 && dCount > 0){
            // we have power still
            if(senates.charAt(turn) == 'R'){
                // we going to ban next D
                boolean banning_from_before = ban(senates,'D',(turn + 1) % senates.length());
                if(banning_from_before){
                    turn --; //there is one opponent banned before this index, next to go is just next in turn
                }
                dCount --;
            }else{
                boolean banning_from_before = ban(senates,'R',(turn + 1) % senates.length());
                if(banning_from_before){
                    turn --; //there is one opponent banned before this index, next to go is just next in turn
                }
                rCount --;
            }
            turn = (turn + 1) % senates.length();
        }
        if(rCount == 0){
            return "Dire";
        }else{
            return "Radiant";
        }
    }
    private boolean ban(StringBuilder sb, Character party, int start){
        boolean flag = false;
        for(int i = start; i < start + sb.length(); i ++){
            int curr = i % sb.length();
            if(curr == 0) flag = true;
            if(sb.charAt(curr) == party){
                sb.deleteCharAt(curr);
                break;
            }
        }
        return flag;
    }
    
}

class Solution {
    public String predictPartyVictory(String senate) {
        // we still know the running curr senate for each party
        int rCount = 0, dCount = 0;

        // Floating Ban Count
        int dFloatingBan = 0, rFloatingBan = 0;
        
        // Queue of senators
        Queue<Character> q = new LinkedList<>();
        for(char c : senate.toCharArray()){
            q.add(c);
            if(c == 'R') rCount ++;
            else dCount ++;
        }
        while(rCount > 0 && dCount > 0){
            char curr = q.poll();
            if(curr == 'D') {
                if(dFloatingBan > 0){
                    // we are banning this guy
                    dFloatingBan --;
                    dCount --;
                }else{
                    rFloatingBan ++; // banning next R
                    q.add('D'); // adds back
                }
            }else{
                // same thing for ther other party
                if(rFloatingBan > 0){
                    rFloatingBan --;
                    rCount --;
                }else{
                    dFloatingBan ++;
                    q.add('R');
                }
            }
        }
        return rCount == 0 ? "Dire" : "Radiant";
    }
}