class ParkingSystem {
    int big, medium, small;

    public ParkingSystem(int big, int medium, int small) {
        this.big=big;
        this.medium=medium;
        this.small=small;
    }
    
    public boolean addCar(int carType) {
        int type = carType%3;
        if(type==1)
            return --big>=0;
        else if(type == 2)
            return --medium >= 0;
        else
            return --small >= 0;
    }
}

public int countPoints(String rings) {
        int n = rings.length()/2;
        int arr1[] = new int[10];
        int arr2[] = new int[10];
        int arr3[] = new int[10];
        int count = 0;
        
        for(int i=0; i<n; i++){
            if(rings.charAt(2*i) == 'R')
                arr1[rings.charAt(2*i+1)-'0']++;
            if(rings.charAt(2*i) == 'G')
                arr2[rings.charAt(2*i+1)-'0']++;
            if(rings.charAt(2*i) == 'B')
                arr3[rings.charAt(2*i+1)-'0']++;
        }
        
        for(int i=0; i<10; i++){
            if(arr1[i]*arr2[i]*arr3[i] != 0)
                count++;
        }
        
        return count;
    }

class SubrectangleQueries {
    int height, width;
    int[][] rect;

    public SubrectangleQueries(int[][] rectangle) {
        this.rect = rectangle;
    }
    
    public void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
        for(int i=row1; i<=row2; i++){
            for(int j=col1; j<=col2; j++){
                rect[i][j] = newValue;
            }
        }
    }
    
    public int getValue(int row, int col) {
        return rect[row][col];
    }
}

class Solution {
    public int minimumSum(int num) {
        int[] arr = new int[4];
        
        for(int i=0; i<4; i++){
            arr[i] = num%10;
            num/=10;
        }
        
        Arrays.sort(arr);
        
        return 10*(arr[0]+arr[1])+arr[2]+arr[3];
    }
}

class Solution {
    public List<List<Integer>> groupThePeople(int[] gr) {
        Map<Integer, List<Integer>> map = new HashMap();
        List<List<Integer>> ans = new ArrayList();
        
        for(int i=0; i<gr.length; i++){
            int curr = gr[i];
            List<Integer> temp = new ArrayList();
            if(map.containsKey(curr)) temp = map.get(curr);
            temp.add(i);
            map.put(curr, temp);
            if(temp.size() == curr){
                ans.add(temp);
                map.remove(curr);
            }
        }
        
        return ans;
    }
}

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;
    }
}