class Solution {
    public int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<>();
        for(String t: tokens){
            if(!stack.isEmpty() && t.charAt(0)<48 && t.length()==1){
                int num2=Integer.parseInt(stack.pop());
                int num1=Integer.parseInt(stack.pop());
                stack.push(String.valueOf(calculate(num1, num2, t.charAt(0))));
            }else{
                stack.push(t);
            }
        }
        return Integer.parseInt(stack.peek());
    }
    public int calculate(int num1, int num2, char ch){
        switch(ch){
            case '+': return num1+num2;
            case '-': return num1-num2;
            case '*': return num1*num2;
            case '/': return num1/num2;
        }
        return 0;
    }
}

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> list = new ArrayList<>();
        int qarz=0, temp=0;
        for(int i=num.length-1; i>=0; i--){
            temp=num[i]+k%10+qarz;
            k/=10;
            System.out.println(temp);
            list.add(0, temp%10);
            qarz=temp/10;
        }
        k+=qarz;
        while(k!=0){
            list.add(0, k%10);
            k/=10;
        }
        return list;
    }
}

class Solution {
    public int lengthOfLastWord(String s) {
        int count=0;
        for(int i=s.length()-1; i>=0; i--){
            if(s.charAt(i)==' ' && count!=0) break;
            if(s.charAt(i)!=' ') count++;
        }
        
        return count;
    }
}

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, (a, b) -> a[0]*a[0]+a[1]*a[1]-b[0]*b[0]-b[1]*b[1]);
        
        return Arrays.copyOfRange(points, 0, k);
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode temp = head;
        int carry=0;
        while(l1!=null || l2!=null){
            temp.next=new ListNode();
            temp=temp.next;
            temp.val = (l1!=null?l1.val:0) + (l2!=null?l2.val:0)+carry;
            carry=temp.val/10;
            temp.val %= 10;
            if(l1!=null) l1=l1.next;
            if(l2!=null) l2=l2.next;
        }
        if(carry>0)
            temp.next = new ListNode(carry);
        return head.next;
    }
}

select id, 'Root' as type from tree where p_id is null
union
select id, 'Inner' as type from tree
where id in (select distinct p_id from tree where p_id is not null) and p_id is not null
union
select id, 'Leaf' as type from tree
where id not in(select distinct p_id from tree where p_id is not null) and p_id is not null

select distinct author_id as id from views where author_id=viewer_id order by author_id

select activity_date as day, count(distinct user_id) as active_users from activity
where datediff('2019-07-27', activity_date)<30
group by activity_date

select user_id, count(distinct follower_id) as followers_count
from followers group by user_id;

select actor_id, director_id 
from (select actor_id, director_id, count(*) as total from actordirector group by actor_id, director_id) as a where total>=3

class Solution {
    public int maxCoins(int[] piles) {
        int n=piles.length/3;
        int count=0;
        Arrays.sort(piles);
        for(int i=piles.length-2; n-- >0; i-=2){
            count+=piles[i];
        }
        return count;
    }
}

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        Deque<Integer> deque = new ArrayDeque<>();
        Arrays.sort(deck);
        for(int i=deck.length-1; i>=0; i--){
            if(deque.isEmpty()){
                deque.offer(deck[i]);
            }else{
                deque.offerFirst(deque.pollLast());
                deque.offerFirst(deck[i]);
            }
        }
        int ans[] = new int[deque.size()];
        for(int i=0; i<ans.length; i++){
            ans[i]=deque.poll();
        }
        return ans;
    }
}

class Solution {
    public boolean divideArray(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num: nums){
            map.put(num, map.getOrDefault(num, 0) +1);
        }
        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            if(entry.getValue()%2!=0) return false;
        }
        return true;
    }
}

class Solution {
    public int findTheWinner(int n, int k) {
        int cycle=n-1, curr=0, temp;
        int[] arr = new int[n];
        while(cycle-- >0){
            temp=0;
            while(temp<k){
                if(arr[curr%n]==0) temp++;
                if(temp<k) curr++;
            }
            arr[curr%n]++;
            curr++;
        }
        
        for(int i=0; i<arr.length; i++){
            if(arr[i]==0) return i+1;
        }
        return -1;
    }
}

class Solution {
    public String intToRoman(int num) {
        StringBuffer sb = new StringBuffer();
        String[] romans={"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int[] nums={1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        for(int i=romans.length-1; i>=0; i--){
            while(num>=nums[i]){
                sb.append(romans[i]);
                num = num-nums[i];
            }
        }
        return sb.toString();
    }
}

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i=1; i<nums.length-1; i+=3){
            if(nums[i-1]!=nums[i]) return nums[i-1];
        }
        return nums[nums.length-1];
    }
}

class Solution {
    public int[] singleNumber(int[] nums) {
        int single1=0, single2=0;
        boolean found=false;
        Map<Integer, Integer> map = new HashMap<>();
        for(int num: nums){
            map.put(num, map.getOrDefault(num, 0) +1);
        }
        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            if(entry.getValue()==1&&!found){
                single1=entry.getKey();
                found=true;
            }
            if(entry.getValue()==1&&found){
                single2=entry.getKey();
            }
        }
        return new int[]{single1, single2};
    }
}

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode head=list1;
        int diff=b-a;
        while(a-- > 1){
            list1=list1.next;
        }
        ListNode move=list1.next;
        list1.next=list2;
        while(diff-- >= 0){
            move=move.next;
        }
        while(list2.next!=null){
            list2=list2.next;
        }
        list2.next=move;
        
        return head;
    }
}

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int l=1, r=n, mid;
        while(l<=r){
            mid=l+(r-l)/2;
            if(guess(mid)==0) return mid;
            if(guess(mid)==1) l=mid+1;
            if(guess(mid)==-1) r=mid-1;
        }
        
        return l;
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        int i=nums.length-2, j=nums.length-1, temp;
        while(i>-1 && nums[i]>=nums[i+1])
            i--;
        if(i>=0){
            while(nums[i]>=nums[j])
            j--;
        
            temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
        int k=nums.length-1;
        i++;
        while(i<k){
            temp=nums[i];
            nums[i]=nums[k];
            nums[k]=temp;
            i++; k--;
        }
    }
}