class Solution {

	//First, count fresh oranges. Then, until fresh is non-zero, perform BFS to rot oranges, decreasing fresh. Count days (d) and return it in the end. If, after another day, fresh does not change, return -1.

	//For BFS, we can use the day counter (d + 2) to only process oranges that rotted yesterday.

    public int orangesRotting(int[][] grid) {
        int fresh = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        int day = 0;
        for (int old_fresh = fresh; fresh > 0; old_fresh = fresh, day++) {
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                	//only process rotted yesterday.
                    if (grid[i][j] == day + 2) {
                        fresh -= (rot(grid, i - 1, j, day) + rot(grid, i + 1, j, day) + rot(grid, i, j - 1, day) + rot(grid, i, j + 1, day));
                    }
                }
            }
            //when still have fresh one but not able to rot it.
            if (fresh == old_fresh) {
                return -1;
            }
        }
        return day;
    }

    private int rot(int[][] grid, int i, int j, int day) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] != 1) {
            return 0;
        }
        //use day+3 to mark rotted, and only process the one rotted yesterday.
        grid[i][j] = day + 3;
        return 1;
    }
}

public class Solution {
    int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }

    private int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        max = Math.max(max, left + right);

        return Math.max(left, right) + 1;
    }
}

class Solution {

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
    	//need to check, if it's the same, just return.
        if(image[sr][sc] == newColor) return image;
        fill(image,sr,sc,image[sr][sc],newColor);
        return image;
    }

    private void fill(int[][] image, int sr, int sc, int color, int newcolor) {
        if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[sr].length || image[sr][sc] != color) {
            return;
        }
        image[sr][sc] = newcolor;
        fill(image,sr+1,sc,color,newcolor);
        fill(image,sr-1,sc,color,newcolor);
        fill(image,sr,sc+1,color,newcolor);
        fill(image,sr,sc-1,color,newcolor);
    }
}

class Solution {
    public int minCost(int[][] costs) {
        if(costs==null || costs.length == 0){
            return 0;
        }
        int len = costs.length;
        for(int i = 1; i<len;i++){
            costs[i][0] += Math.min(costs[i-1][1],costs[i-1][2]);
            costs[i][1] += Math.min(costs[i-1][0],costs[i-1][2]);
            costs[i][2] += Math.min(costs[i-1][1],costs[i-1][0]);
        }
        return Math.min(costs[len-1][0],Math.min(costs[len-1][1],costs[len-1][2]));

    }
}

import java.util.List;

/**
 * Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
 */
class Solution {

    public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        int len = 0;
        ListNode temp_count = root;
        while (temp_count != null) {
            len++;
            temp_count = temp_count.next;
        }
        // n : minimum guaranteed part size;
        // r : extra nodes spread to the first r parts;
        int n = len / k;
        int r = len % k;
        ListNode node =root, prev = null;
        for(int i = 0;node!=null && i<k;i++,r--){
            res[i] = node;
            for(int j = 0;j<n+(r>0?1:0);j++){
                prev = node;
                node =node.next;
            }
            prev.next = null;
        }


        return res;
    }
}

/*
"Semaphore is a bowl of marbles" - Professor Stark

Semaphore is a bowl of marbles (or locks in this case). If you need a marble, and there are none, you wait. You wait until there is one marble and then you take it. If you release(), you will add one marble to the bowl (from thin air). If you release(100), you will add 100 marbles to the bowl (from thin air).
The thread calling third() will wait until the end of second() when it releases a '3' marble. The second() will wait until the end of first() when it releases a '2' marble. Since first() never acquires anything, it will never wait. There is a forced wait ordering.
With semaphores, you can start out with 1 marble or 0 marbles or 100 marbles. A thread can take marbles (up until it's empty) or put many marbles (out of thin air) at a time.
Upvote and check out my other concurrency solutions.

*/
import java.util.concurrent.Semaphore;

class Foo {

    Semaphore run2, run3;

    public Foo() {
        run2 = new Semaphore(0);
        run3 = new Semaphore(0);
    }

    public void first(Runnable printFirst) throws InterruptedException {

        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        run2.release();
    }

    public void second(Runnable printSecond) throws InterruptedException {
        run2.acquire();
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
        run3.release();
    }

    public void third(Runnable printThird) throws InterruptedException {
        run3.acquire();
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}

import java.util.HashMap;
import java.util.Map;

class Solution {

/*
One pass on A,
For each different number a in A,
we need to count its frequency and it first occurrence index.

If a has the maximum frequency,
update the degree = count[a] and res = i - first[A[i]] + 1.

If a is one of the numbers that has the maximum frequency,
update the res = min(res, i - first[A[i]] + 1)

*/
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>(), firstIndex = new HashMap<>();
        int degree = 0, res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            //only store the first index of current number
            firstIndex.putIfAbsent(n,i);
            //count the current number.
            count.put(n,count.getOrDefault(n,0)+1);
            //if current number is larger, update degree
            if(count.get(n)>degree){
                degree = count.get(n);
                //after update degree, need to update length of min subarray.
                //the current number to the first index, it's may not be the final result
                //if encounter this number again, will update.
                //so will always calc the length from last to first index.
                res = i-firstIndex.get(n) + 1;
            }else if(count.get(n)==degree){
            	//encounter again, update.
                res = Math.min(res,i-firstIndex.get(n)+1);
            }
        }

        return res;
    }
}

class Solution {

    public int[] intersection(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums1);
        for(int n: nums2){
            //see Arrays doc.
            if(Arrays.binarySearch(nums1,n)>=0){
                set.add(n);
            }
        }

        int[] res = new int[set.size()];
        Iterator<Integer> iterator = set.iterator();
        for(int i = 0;i<res.length;i++){
            res[i] = iterator.next();
        }

        return res;
    }
}

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy, cur = head;
        while(cur != null){
            if(cur.val==val){
                pre.next = cur.next;
            }else{
                pre = pre.next;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }

        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.length, (o1,o2)->(o1.val - o2.val));

        for(ListNode listNode : lists){
            if(listNode != null){
                pq.offer(listNode);
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        while(!pq.isEmpty()){
            cur.next = pq.poll();
            cur = cur.next;

            if(cur.next != null){
                pq.offer(cur.next);
            }
        }

        return dummy.next;
    }
}

public class Trie {
private TrieNode root;

    /** Initialize your data structure here. */
    //like linked list.
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode ws = root;
        char[] letters = word.toCharArray();
        for(int i = 0;i<letters.length;i++){
            char cur = letters[i];
            if(ws.next[cur-'a'] == null){
                ws.next[cur-'a'] = new TrieNode();
            }
            ws = ws.next[cur-'a'];
        }

        ws.isWord = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode ws = root;
        char[] letters = word.toCharArray();
        for(int i = 0;i<letters.length;i++){
            char cur = letters[i];
            if(ws.next[cur-'a'] == null){
                return false;
            }
            ws = ws.next[cur-'a'];
        }

        return ws.isWord;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode ws = root;
        char[] letters = prefix.toCharArray();
        for(int i = 0;i<letters.length;i++){
            char cur = letters[i];
            if(ws.next[cur-'a'] == null){
                return false;
            }
            ws = ws.next[cur-'a'];
        }

        return true;
    }
}

class TrieNode{
    boolean isWord;
    TrieNode[] next;

    public TrieNode(char c){
        next = new TrieNode[26];
        isWord = false;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;
        int len = prices.length;
        int[] s0 = new int[len], s1 = new int[len],s2 = new int[len];
        s0[0] = 0;
        s1[0] = -prices[0];
        s2[0] = Integer.MIN_VALUE;
        for(int i = 1;i<len;i++){
            s0[i] = Math.max(s0[i-1],s2[i-1]);
            s1[i] = Math.max(s0[i-1]-prices[i],s1[i-1]);
            s2[i] = s1[i-1] + prices[i];
        }
        return Math.max(s0[len-1],s2[len-1]);
    }
}

class MedianFinder {
    PriorityQueue<Long> large, small;

    /** initialize your data structure here. */
    public MedianFinder() {
        large = new PriorityQueue();
        small = new PriorityQueue();
    }

    public void addNum(int num) {
        large.add((long)num);
        small.add(-large.poll());
        if(large.size()<small.size()){
            large.add(-small.poll());
        }
    }

    public double findMedian() {
        return large.size()>small.size()?large.peek():(large.peek()-small.peek())/2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList();
        TrieNode root = buildTrie(words);
        for(int i = 0; i< board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                dfs(board, i, j, root, res);
            }
        }
        return res;
    }



    public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res){
        if(i <0 || j<0 || i>=board.length || j >= board[0].length || board[i][j] == '#' || p.next[board[i][j]-'a']==null) return;
        char c = board[i][j];
        p = p.next[board[i][j]-'a'];
        if(p.word != null){
            res.add(p.word);
            p.word = null;
        }

        board[i][j] = '#';
        dfs(board, i-1, j, p, res);
        dfs(board, i+1, j, p, res);
        dfs(board, i, j-1, p, res);
        dfs(board, i, j+1, p, res);
        board[i][j] = c;
    }


    public TrieNode buildTrie(String[] words){
        TrieNode root = new TrieNode();
        for(String s: words){
            TrieNode p = root;
            for(char c: s.toCharArray()){
                if(p.next[c-'a']==null) p.next[c-'a'] = new TrieNode();
                p = p.next[c-'a'];
            }
            p.word = s;
        }
        return root;
    }


    class TrieNode{
        TrieNode[] next = new TrieNode[26];
        String word;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if(s == null || t == null) return false;
        if(isSame(s,t)) return true;
        return isSubtree(s.left,t) || isSubtree(s.right, t);

    }

    public boolean isSame(TreeNode s, TreeNode t){
        if(s == null && t == null) return true;
        if(s == null || t == null) return false;

        if(s.val != t.val) return false;
        return isSame(s.left, t.left) && isSame(s.right, t.right);
    }
}

class Solution {

    HashMap<String, List<String>> map;
    HashSet<String> wordSet;

    public List<String> wordBreak(String s, List<String> wordDict) {
        map = new HashMap();
        wordSet = new HashSet(wordDict);
        return helper(s);

    }

    public List<String> helper(String s){
        List<String> res = new ArrayList();
        if(s == null || s.isEmpty()) return res;
        //if already searched, just return result.
        if(map.containsKey(s)) return map.get(s);
        //the left string is itself a word.
        if(wordSet.contains(s)) {
            res.add(s);
        }
        for(int i = 1;i<s.length();i++){
            //cut the first i char as a word.
            String t = s.substring(0, i);
            if(wordSet.contains(t)){
                //get all possible result of the left string.
                List<String> temp = helper(s.substring(i));
                if(temp!=null && temp.size()!=0){
                    //combine each of the result with t(word)
                    for(int j = 0;j<temp.size();j++){
                        res.add(t+" "+temp.get(j));
                    }
                }
            }
        }
        //store it to prevent duplication.
        map.put(s,res);
        return res;
    }
}

class TicTacToe {
    private int[] rows;
    private int[] cols;
    private int diag;
    private int antidiag;
    private int size;
    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        rows = new int[n];
        cols = new int[n];
        size = n;
    }

    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        int toAdd = player==1?1:-1;
        rows[row] += toAdd;
        cols[col] += toAdd;

        if(row==col){
            diag += toAdd;
        }

        if(row+col == size - 1){
            antidiag += toAdd;
        }

        if(Math.abs(rows[row])==size ||
           Math.abs(cols[col])==size ||
           Math.abs(diag)==size ||
           Math.abs(antidiag)==size
          ) return player;
        return 0;

    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */