class Solution {
    public int numberOfBeams(String[] bank) {
        int rows = bank.length, cols = bank[0].length();
        int total=0, counter = 0;
        List<Integer> nums = new ArrayList();
        for(int i = 0; i<rows; i++){
            int temp = 0;
            for(int j=0; j<cols; j++){
                if(bank[i].charAt(j) == '1') temp++;
            }
            
            if(temp != 0) nums.add(temp);
        }
        
        for(int i=1; i<nums.size(); i++){
            total += nums.get(i-1) * nums.get(i);
        }
        
        return total;
    }
}

class Solution {
    public char findTheDifference(String s, String t) {
        int n = s.length();
        char ch=t.charAt(n);
        for(int i=0; i<n; i++){
            ch ^= s.charAt(i);
            ch ^= t.charAt(i);
        }
        
        return ch;
    }
}

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int pos[] = new int[nums.length/2], neg[] = new int[nums.length/2], count1=0, count2=0;
        
        for(int n: nums){
            if(n>0) pos[count1++]=n;
            if(n<0) neg[count2++]=n;
        }
        
        for(int i=0; i<nums.length/2; i++){
            nums[i*2]=pos[i];
            nums[2*i+1]=neg[i];
        }
        
        return nums;
    }
}

class Solution {
    public String makeGood(String s) {
        Stack<Character> stack = new Stack();
        for(char ch: s.toCharArray()){
            if(!stack.isEmpty() && Math.abs(stack.peek()-ch) == 32)
                stack.pop();
            else
                stack.push(ch);
        }
        
        char temp[] = new char[stack.size()];
        int n = stack.size()-1;
        while(!stack.isEmpty()){
            temp[n--] = stack.pop();
        }
        
        return new String(temp);
    }
}

class MyQueue {
    Stack<Integer> stack = new Stack();
    Stack<Integer> temp = new Stack();
    
    public MyQueue() {}
    
    public void push(int x) {
        while(!stack.isEmpty())
            temp.push(stack.pop());
        
        stack.push(x);
        while(!temp.isEmpty())
            stack.push(temp.pop());
    }
    
    public int pop() {
        return stack.pop();
    }
    
    public int peek() {
        return stack.peek();
    }
    
    public boolean empty() {
        return stack.isEmpty();
    }
}

class MinStack {
    Stack<Integer> stack = new Stack();
    int min = Integer.MAX_VALUE;
    
    public MinStack() {}
    
    public void push(int val) {
        if(val<=min){
            stack.push(min);
            min=val;
        }
        stack.push(val);
    }
    
    public void pop() {
        if(stack.pop() == min) min = stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min;
    }
}

Stack<Character> stack1 = new Stack();
        Stack<Character> stack2 = new Stack();
        
        for(char ch: s.toCharArray()){
            if(!stack1.isEmpty() && ch == '#')
                stack1.pop();
            else if(ch != '#')
                stack1.push(ch);
        }
        
        for(char ch: t.toCharArray()){
            if(!stack2.isEmpty() && ch == '#')
                stack2.pop();
            else if(ch != '#')
                stack2.push(ch);
        }

        return String.valueOf(stack1).equals(String.valueOf(stack2));

        Stack<Character> stack = new Stack<Character>();
     for (char c : s.toCharArray()) {
      if (c == '(')
       stack.push(')');
      else if (c == '{')
       stack.push('}');
      else if (c == '[')
   stack.push(']');
      else if (stack.isEmpty() || stack.pop() != c)
       return false;
     }
     return stack.isEmpty();

class Solution {
    public int minAddToMakeValid(String s) {
        int res=0;
        Stack<Character> stack = new Stack();
        
        for(char ch: s.toCharArray()){
            if(ch == '(')
                stack.push(ch);
            else{
                if(!stack.isEmpty()) stack.pop();
                else res++;
            }
        }
        
        return res+stack.size();
    }
}

class CustomStack {
    int maxSize;
    int temp=0;
    int stack[];
    public CustomStack(int maxSize) {
        stack = new int[maxSize];
        this.maxSize=maxSize;
    }
    public void push(int x) {
        if(temp<maxSize)
            stack[temp++]=x;
    }
    public int pop() {
        if(temp>0)
            return stack[--temp];
        else
            return -1;
    }
    public void increment(int k, int val) {
        if(temp==0) return;
        for(int i=0; i<Math.min(k, temp); i++){
            stack[i]+=val;
        }
    }
}

class BrowserHistory {
    List<String> list;
    int size=-1, temp=-1;
    public BrowserHistory(String homepage) {
        list = new ArrayList();
        list.add(homepage);
        size++;
        temp++;
    }
    
    public void visit(String url) {
        list.add(++temp, url);
        size=temp;
    }
    
    public String back(int steps) {
        temp=Math.max(0, temp-steps);
        return list.get(temp);
    }
    
    public String forward(int steps) {
        temp=Math.min(size, temp+steps);
        return list.get(temp);
    }
}

        int[] res=new int[temp.length];
        for(int i=0; i<temp.length-1; i++){
            for(int j=i+1; j<temp.length; j++){
                if(temp[i]<temp[j]){
                    res[i]=j-i;
                    break;
                }       
            }
        }
        return res;

class Solution {
    public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        Set<Integer> set = new TreeSet<>();
        int l=nums.length;
        
        for(int i=0; i<l; i++){
            if(nums[i]==key){
                set.add(i);
                for(int j=i-k; j<=i+k; j++){
                    if(j>-1 && j<l)
                        set.add(j);
                }
            }
        }
        
        return new ArrayList<Integer>(set);
    }
}

class Solution {
    public List<String> cellsInRange(String s) {
        ArrayList<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        
        for(int i=(int)(s.charAt(0)); i<=(int)(s.charAt(3)); i++){
            for(int j=Integer.valueOf(s.charAt(1)-'0'); j<=Integer.valueOf(s.charAt(4)-'0'); j++){
                sb = new StringBuilder(""+(char)i);
                sb.append(j);
                list.add(sb.toString());
            }
        }
        
        return list;
    }
}

class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length;     //3
        int n = mat[0].length;   //4
        
        for(int k = 0; k < Math.min(m, n) ; k++){
            for(int i = 1; i < m; ++i){
                for(int j = 1; j < n; ++j){
                    if(mat[i][j] < mat[i-1][j-1]){
                        int temp = mat[i-1][j-1];
                        mat[i-1][j-1] = mat[i][j];
                        mat[i][j] = temp;
                    }
                }
            }
        }
        
        return mat;
    }
}

class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        int count=0, temp=0;
        for(int n: nums){
            if(n<pivot){
                list1.add(n);
            }else if(n>pivot){
                list2.add(n);
            }else
                count++;
        }
        temp=count;
        int res[] = new int[nums.length];
        for(int i=0; i<res.length; i++){
            if(i<list1.size()){
                res[i]=list1.get(i);
            }else if(i>=list1.size() &&i<list1.size()+count){
                while(count-- >0)
                    res[i++]=pivot;
                i--;
            }else
                res[i]=list2.get(i-list1.size()-temp);
        }
        return res;
    }
}

class Solution {
    public int countPairs(int[] nums, int k) {
        int count=0;
        for(int i=0; i<nums.length-1; i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[i]==nums[j] && i*j%k==0)
                    count++;
            }
        }
        
        return count;
    }
}

class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> list = new ArrayList<>();
        
        for(int i=0; i<l.length; i++){
            int temp[] = new int[r[i]-l[i]+1];
            for(int j=l[i]; j<=r[i]; j++){
                temp[j-l[i]]=nums[j];
            }
            Arrays.sort(temp);
            list.add(check(temp));
        }
        
        return list;
    }
    public boolean check(int[] arr){
        for(int i=1; i<arr.length-1; i++){
            if(arr[i]*2!=arr[i-1]+arr[i+1])
                return false;
        }
        
        return true;
    }
}

class Solution {
    public int prefixCount(String[] words, String pref) {
        int count=0;
        
        for(String word: words){
            if(word.startsWith(pref))
                count++;
        }
        
        return count;
    }
}

class Solution {
    public int countOperations(int num1, int num2) {
        int count=0;
        while(num1*num2!=0){
            if(num1<num2)
                num2-=num1;
            else
                num1-=num2;
            
            count++;
        }
        
        return count;
    }
}