public class MovingAverage {
    private int [] window;
    private int n, insert;
    private long sum;
    
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        window = new int[size];
        insert = 0;
        sum = 0;
    }
    
    public double next(int val) {
        if (n < window.length)  n++;
        sum -= window[insert];
        sum += val;
        window[insert] = val;
        insert = (insert + 1) % window.length;
        
        return (double)sum / n;
    }
}

class MyHashMap {

    Node[] map;
    int size = 1 << 10;

    /**
     * Initialize your data structure here.
     */
    public MyHashMap() {
        map = new Node[size];
    }

    /**
     * value will always be non-negative.
     */
    public void put(int key, int value) {
        int idx = indexOf(key);
        if (map[idx] == null) {
            map[idx] = new Node(key, value);
        } else {
            Node temp = map[idx];
            Node pre = null;
            while (temp != null) {
                if(temp.key==key){
                    temp.val = value;
                    return;
                }
                pre = temp;
                temp = temp.next;
            }
            pre.next = new Node(key, value);
        }
    }

    /**
     * Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
     */
    public int get(int key) {
        int idx = indexOf(key);
        if (map[idx] == null) {
            return -1;
        } else {
            Node temp = map[idx];
            while (temp != null) {
                if (temp.key == key) {
                    return temp.val;
                }
                temp = temp.next;
            }
        }
        return -1;
    }

    /**
     * Removes the mapping of the specified value key if this map contains a mapping for the key
     */
    public void remove(int key) {
        int idx = indexOf(key);
        if (map[idx] == null) {
            return;
        } else{
            Node dummy = new Node(-1,-1);
            dummy.next = map[idx];
            Node pre = dummy;
            Node temp = map[idx];
            while(temp!=null){
                if(temp.key==key){
                    pre.next = temp.next;
                    break;
                }
                pre = temp;
                temp = temp.next;
            }
            map[idx] = dummy.next;
        }

    }

   
    private int indexOf(int key) {
        return Integer.hashCode(key) & (size - 1);
    }


    public class Node {

        int key;
        int val;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            next = null;
        }

    }
}

/**
 * Your MyHashMap object will be instantiated and called as such: MyHashMap obj = new MyHashMap(); obj.put(key,value); int param_2 = obj.get(key);
 * obj.remove(key);
 */

class Vector2D {

    int row;
    int col;
    int[][] data;

    public Vector2D(int[][] v) {
        data = v;
        row = 0;
        col = 0;
    }

    public int next() {
        hasNext();
        int ret = data[row][col];
        //move to next, may not be valid.
        //will have to ask hasNext() to find next valid position.
        col++;
        if(col>=data[row].length){
            col = 0;
            row++;
        }
        return ret;
    }

    //after calling hasNext, if return true, then col/row will always be valid and can be retrived.
    public boolean hasNext() {
    	//reached the end.
        if(row >= data.length){
            return false;
        }

        //col reached the tail of the current list, will go for next line.
        if(col>=data[row].length){
            col = 0;
            //to handle next is empty list. 
            while(row<data.length && data[row].length==0){
                row++;
            }

        }
        //after all the search and reached the end, no valid item.
        if(row >= data.length){
            return false;
        }

        return true;
    }
}

/**
 * Your Vector2D object will be instantiated and called as such: Vector2D obj = new Vector2D(v); int param_1 = obj.next(); boolean param_2 = obj.hasNext();
 */

//consider more find and less add or we only care time complexity in finding.
//
//For example, add operation can be pre-done.
public class TwoSum {
        Set<Integer> sum;
        Set<Integer> num;
        
        TwoSum(){
            sum = new HashSet<Integer>();
            num = new HashSet<Integer>();
        }
        // Add the number to an internal data structure.
        //O(n) since add() is less than find();
    	public void add(int number) {
    	    if(num.contains(number)){
    	        sum.add(number * 2);
    	    }else{
    	        Iterator<Integer> iter = num.iterator();
    	        while(iter.hasNext()){
    	            sum.add(iter.next() + number);
    	        }
    	        num.add(number);
    	    }
    	}
    
        // Find if there exists any pair of numbers which sum is equal to the value.
    	public boolean find(int value) {
    	    return sum.contains(value);
    	}
    }

//more add and less find
public class TwoSum {
    Map<Integer,Integer> hm;
    
    TwoSum(){
        hm = new HashMap<Integer,Integer>();
    }
    // Add the number to an internal data structure.
	public void add(int number) {
	    if(hm.containsKey(number)){
	        hm.put(number,2);
	    }else{
	        hm.put(number,1);
	    }
	}

    // Find if there exists any pair of numbers which sum is equal to the value.
	public boolean find(int value) {
	    Iterator<Integer> iter = hm.keySet().iterator();
	    while(iter.hasNext()){
	        int num1 = iter.next();
	        int num2 = value - num1;
	        //handle special case where same number added twice.
	        if(hm.containsKey(num2)){
	            if(num1 != num2 || hm.get(num2) == 2){
	                return true;
	            }
	        }
	    }
	    return false;
	}
}

import java.util.*;

class PhoneDirectory {

    Set<Integer> used = new HashSet<Integer>();
    Queue<Integer> available = new LinkedList<Integer>();
    int max;
    
    public PhoneDirectory(int maxNumbers) {
        max = maxNumbers;
        for (int i = 0; i < maxNumbers; i++) {
            available.offer(i);
        }
    }

    public int get() {
        Integer ret = available.poll();
        if (ret == null) {
            return -1;
        }
        used.add(ret);
        return ret;
    }

    public boolean check(int number) {
        if (number >= max || number < 0) {
            return false;
        }
        return !used.contains(number);
    }

    public void release(int number) {
        if (used.remove(number)) {
            available.offer(number);
        }
    }
}

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * boolean param_2 = obj.check(number);
 * obj.release(number);
 */

//dp[i] -> max sum can get from A[0,i]
class Solution {
    public int maxSumAfterPartitioning(int[] A, int K) {
        int[] dp = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            int curMax = 0;
            for (int j = 1; j <= K && i - j + 1 >= 0; j++) {
                //keep track of the max backward.
                curMax = Math.max(curMax, A[i - j + 1]);
                //if go beyond the head, just add 0;
                dp[i] = Math.max(dp[i], curMax * j + ((i>=j)?dp[i - j]:0));
            }
        }
        
        return dp[A.length-1];
    }
}

class Solution {

    public double[] calcEquation(List<List<String>> equations, double[] values,
        List<List<String>> queries) {

        Map<String, Map<String, Double>> graph = buildGraph(equations, values);

        double[] result = new double[queries.size()];

        for (int i = 0; i < queries.size(); i++) {

            result[i] = getPathWeight(queries.get(i).get(0), queries.get(i).get(1), new HashSet<String>(), graph);
        }
        return result;
    }

    //DFS
    private double getPathWeight(String start, String end, Set<String> visited, Map<String, Map<String, Double>> graph) {
        //base case where node dose not exist.
        if (!graph.containsKey(start)) {
            return -1.0;
        }
        //end case where reached the end.
        if (graph.get(start).containsKey(end)) {
            return graph.get(start).get(end);
        }

        //mark as visited.
        visited.add(start);

        //travers the neighbors.
        for (Map.Entry<String, Double> neighbor : graph.get(start).entrySet()) {
            if (!visited.contains(neighbor.getKey())) {
                //get value from neighbor to end
                double weight = getPathWeight(neighbor.getKey(), end, visited, graph);
                //if the neighbor have path to end, just multiply the value with value[cur, neighbor].
                if (weight != -1.0) {
                    return weight * neighbor.getValue();
                }
            }
        }
        return -1.0;
    }

    //build weighted graph with bi-direction.
    private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        
        String u, v;

        for (int i = 0; i < equations.size(); i++) {
            u = equations.get(i).get(0);
            v = equations.get(i).get(1);

            graph.putIfAbsent(u, new HashMap<>());
            graph.putIfAbsent(v, new HashMap<>());

            graph.get(u).put(v, values[i]);
            graph.get(v).put(u, 1 / values[i]);
        }

        return graph;
    }
}

class Solution {
    List<String> res;
    Map<String, PriorityQueue<String>> flights;


    public List<String> findItinerary(List<List<String>> tickets) {
        res = new ArrayList<>();
        flights = new HashMap<>();
        
        //construct the map with priorityqueue.
        for(List<String> flight : tickets){
            String from = flight.get(0);
            String to = flight.get(1);
            flights.putIfAbsent(from,new PriorityQueue<>());
            flights.get(from).offer(to);
        }
        visit("JFK");
        return res;
        
    }
    

    public void visit(String from){
        //if there's flight from this city.
        if(flights.containsKey(from)){
            //keep flying until all tickets used.
            while(!flights.get(from).isEmpty()){
                visit(flights.get(from).poll());
            }
        }
        //add the city to head.
        res.add(0,from);
    }
}

//use BFS, starting from all leaves, remove it layer by layer.
//until one or two nodes left.
class Solution {

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> ret = new ArrayList<>();
        if (n == 1) {
            ret.add(0);
            return ret;
        }


        List<HashSet<Integer>> adj = new ArrayList<HashSet<Integer>>();
        for (int i = 0; i < n; i++) {
            adj.add(new HashSet());
        }

        for(int[] edge:edges){
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        //noticable that leaves only have one adj.
        for(int i = 0;i<n;i++){
            if(adj.get(i).size() ==1){
                ret.add(i);
            }
        }

        while(n > 2){
        	//reduce the number of leaves.
            n -= ret.size();
            List<Integer> temp = new ArrayList<>();
            for(int i : ret){
            	//remove the leaves.
                int j = adj.get(i).iterator().next();
                adj.get(j).remove(i);
                //after removal, the cur node become new leaf.
                if(adj.get(j).size()==1){
                    temp.add(j);
                }
            }
            ret = temp;
        }
        
        return ret;

    }
}

//Greedy assign myself a color that has not been used by neighbor.
class Solution {

    public int[] gardenNoAdj(int N, int[][] paths) {
        //build graph first.
        Map<Integer, Set<Integer>> G = new HashMap<>();
        for (int i = 0; i < N; i++) {
            G.put(i, new HashSet<>());
        }
        for (int[] p : paths) {
            G.get(p[0] - 1).add(p[1] - 1);
            G.get(p[1] - 1).add(p[0] - 1);
        }
        int[] res = new int[N];

        for (int i = 0; i < N; i++) {
            //in order to find available color.
            int[] colors = new int[5];
            //iterate neighbor to mark used color.
            for (int j : G.get(i)) {
                colors[res[j]] = 1;
            }
            //try all color, there's always a valid color available.
            for (int c = 4; c > 0; --c) {
                if (colors[c] == 0) {
                    res[i] = c;
                }
            }
        }
        return res;
    }
}

class Solution {

    public int[] findRedundantConnection(int[][] edges) {
        int[] parent = new int[edges.length+1];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }

        for (int[] edge : edges) {
            int f = edge[0], t = edge[1];
            int p_f = find(parent,f);
            int p_t = find(parent,t);
            if (p_f == p_t) {
                return edge;
            } else {
                parent[p_f] = p_t;
            }
        }

        return new int[2];
    }

    private int find(int[] parent, int f) {
        if (f != parent[f]) {
            parent[f] = find(parent, parent[f]);
        }
        return parent[f];
    }
}

class Solution {

    HashMap<Integer, Integer> countMap;
    HashMap<Integer, Set<Integer>> sqrMap;
    int count;

    public int numSquarefulPerms(int[] A) {

        countMap = new HashMap<>();
        sqrMap = new HashMap<>();

        //count all numbers and init the sqrMap
        for (int num : A) {
            sqrMap.putIfAbsent(num, new HashSet<>());
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        //if sum of num1 and num2 are squarable, add to sqrMap.
        for (int num1 : countMap.keySet()) {
            for (int num2 : countMap.keySet()) {
                double c = Math.sqrt(num1 + num2);
                if (c == Math.floor(c)) {
                    sqrMap.get(num1).add(num2);
                    sqrMap.get(num2).add(num1);
                }
            }
        }

        //try all possibilities starting with different numbers.
        for (int num : countMap.keySet()) {
            dfs(num, A.length - 1);
        }

        return count;

    }

    public void dfs(int num, int left) {
    	//if reached the end, count as one possibility.
    	if(left==0){
    		count++;
    		return;
    	}

    	//remove/use the {num}.
        countMap.put(num, countMap.get(num) - 1);
        
        //for next possible solution, sum(num,next) is squarable.
        for (int next : sqrMap.get(num)) {
        	//if still remaining
            if (countMap.get(next) != 0) {
                dfs(next, left - 1);
            }
        }
        //revert the num for futher use.
        countMap.put(num, countMap.get(num) + 1);
    }
}

/**
take it this way:
We cannot build any well.
There is one and only one hidding well in my house (house 0).
The cost to lay pipe between house[i] and my house is wells[i].

In order to supply water to the whole village,
we need to make the village a coonected graph.

Merge all costs of pipes together and sort by key.
Greedily lay the pipes if it can connect two seperate union.
Appply union find to record which houses are connected.
 */
class Solution {

    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        //build own edge list
        List<int[]> edges = new ArrayList<>();
        int[] uf = new int[n + 1];

        // store pipe from HOUSE0 to house[i] with cost wells[i]
        for (int i = 1; i <= n; i++) {
            uf[i] = i;
            edges.add(new int[]{0, i, wells[i - 1]});
        }

        edges.addAll(Arrays.asList(pipes));

        //sorted by cost and use Greedy to pick less cost.
        edges.sort((a, b) -> (a[2] - b[2]));

        int res = 0;
        for (int[] e : edges) {
            int x = find(uf, e[0]);
            int y = find(uf, e[1]);
            //if(x == y means already connected, can skip.
            if (x != y) {
                //if not connected, add cost to res.
                res += e[2];
                //connect two house.
                uf[x] = y;
            }
        }
        return res;
    }

    private int find(int[] uf, int x) {
        if (uf[x] != x) {
            //find the most recent parent and store in uf[x] will save time finding.
            //like a short-cut.
            uf[x] = find(uf, uf[x]);
        }
        return uf[x];
    }
}

//main idea: use backtrace to find the min cost to make rest of the string valid, and swap the current one.
class Solution {

    public int kSimilarity(String A, String B) {
        HashMap<String, Integer> dist = new HashMap<>();
        return dfs(A.toCharArray(),B,dist,0);
    }

    private int dfs(char[] A, String B, HashMap<String, Integer> dist, int idx) {

        String sa = String.valueOf(A);

        //if already equal, dist is 0.
        if (sa.equals(B)) {
            return 0;
        }
        //already computed.
        if (dist.containsKey(sa)) {
            return dist.get(sa);
        }

        int min = Integer.MAX_VALUE;

        //search the first index that A[i] != B[i].
        while (idx < A.length && A[idx] == B.charAt(idx)) {
            idx++;
        }

        //try all possible solution that swap with idx
        for (int j = idx + 1; j < A.length; j++) {
            //if can make it valid, that is A[idx] = B[idx]
            if (A[j] == B.charAt(idx)) {
                //swap it to make it valid.
                swap(A, idx, j);
                //min dist to make A.substring(idx+1,end) valid.
                int next = dfs(A, B, dist, idx + 1);
                //next may be MAX due to unable to make the rest string valid.
                if (next != Integer.MAX_VALUE) {
                    min = Math.min(min, next);
                }
                //don't forget to swap back.
                swap(A, idx, j);
            }
        }


        dist.put(sa, min + 1);
        return min + 1;
    }

    private void swap(char[] list, int i, int j) {
        char temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

/**
main idea is to use map to store all the relationships between chars.
e.g. a->c, b->d, and if we encounter some relationship that is conflict to the previous existing one
like a -> b , then return false.

1. transformation of link link ,like a -> b -> c:
we do the transformation from end to begin, that is b->c then a->b

2. transformation of cycle, like a -> b -> c -> a:
in this case we need a tmp
c->tmp, b->c a->b and tmp->a
Same as the process of swap two variable.

In both case, there should at least one character that is unused,
to use it as the tmp for transformation.
So we need to return if the size of set of unused characters < 26.
*/

class Solution {

    public boolean canConvert(String str1, String str2) {
        if (str1.equals(str2)) {
            return true;
        }
        Map<Character, Character> map = new HashMap<>();
        int len = str1.length();
        for (int i = 0; i < len; i++) {
            if (!map.containsKey(str1.charAt(i))) {
                map.put(str1.charAt(i), str2.charAt(i));
            } else {
                if (map.get(str1.charAt(i)) != str2.charAt(i)) {
                    return false;
                }
            }
        }

        //should exist at least one char that's unused as temp.
        return new HashSet<Character>(map.values()).size() < 26;
    }
}

class Solution {

    public void reorderList(ListNode head) {
        if(head==null||head.next==null) return;

        //Find the middle of the list
        ListNode p1=head;
        ListNode p2=head;
        while(p2.next!=null&&p2.next.next!=null){
            p1=p1.next;
            p2=p2.next.next;
        }

        //Reverse the half after middle  1->2->3->4->5->6 to 1->2->3->6->5->4
        ListNode preMiddle=p1;
        ListNode preCurrent=p1.next;
        while(preCurrent.next!=null){
            ListNode current=preCurrent.next;
            preCurrent.next=current.next;
            current.next=preMiddle.next;
            preMiddle.next=current;
        }

        //Start reorder one by one  1->2->3->6->5->4 to 1->6->2->5->3->4
        p1=head;
        p2=preMiddle.next;
        while(p1!=preMiddle){
            preMiddle.next=p2.next;
            p2.next=p1.next;
            p1.next=p2;
            p1=p2.next;
            p2=preMiddle.next;
        }
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        ListNode curA = headA;
        ListNode curB = headB;

        while(curA!=null){
            lenA++;
            curA = curA.next;
        }

        while(curB!=null){
            lenB++;
            curB = curB.next;
        }

        while(lenA > lenB){
            headA = headA.next;
            lenA--;
        }

        while(lenA < lenB){
            headB = headB.next;
            lenB--;
        }

        while(headA != headB)
        {
            headA = headA.next;
            headB = headB.next;
        }

        return headA;
    }
}

/**
use two iterations to do that. In the first iteration

we will reset the pointer of one linkedlist to the head of another linkedlist after it reaches the tail node.

In the second iteration, we will move two pointers until they points to the same node. 

Our operations in first iteration will help us counteract the difference. 

So if two linkedlist intersects, the meeting point in second iteration must be the intersection point. 

If the two linked lists have no intersection at all, then the meeting pointer in second iteration must be the tail node of both lists, which is null

*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //boundary check
    if(headA == null || headB == null) return null;
    
    ListNode a = headA;
    ListNode b = headB;
    
    //if a & b have different len, then we will stop the loop after second iteration
    while( a != b){
    	//for the end of first iteration, we just reset the pointer to the head of another linkedlist
        a = a == null? headB : a.next;
        b = b == null? headA : b.next;    
    }
    
    return a;
}

/**
main idea is to add the height to a pile/heap when encounter the left bond
and remove when right boarder.
so inside the heap, it will have all the height for current x position.
use pq or treemap to find the max height for current position.
add to res if it's different from the previous.
*/
class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res = new ArrayList<>();
        List<int[]> heights = new ArrayList<>();

        //add to height list, negative if right boundary.
        for(int[] building : buildings){
            heights.add(new int[]{building[0],building[2]});
            heights.add(new int[]{building[1],-building[2]});
        }

        //sort based on x coord.
        heights.sort((a,b)->(a[0]==b[0]?b[1]-a[1]:a[0]-b[0]));

        TreeMap<Integer,Integer> map = new TreeMap<>();

        //gound
        map.put(0,1);
        int prev = 0;

        for(int[] height : heights){
            if(height[1]<0){
            	//remove the height from heap if meet right boundary.
                if(map.get(-height[1])>1){
                    map.put(-height[1],map.get(-height[1])-1);
                }else{
                    map.remove(-height[1]);
                }
            }else{
            	//add to heap if left.
                map.put(height[1],map.getOrDefault(height[1],0)+1);
            }

            //find the max height for current position.
            int cur = map.lastKey();
            //if it's a curcial point.
            if(cur != prev){
                List<Integer> temp = new ArrayList<>();
                temp.add(height[0]);
                temp.add(cur);
                res.add(temp);
                prev = cur;
            }
        }

        return res;

    }
}

class Solution {

    public int nthSuperUglyNumber(int n, int[] primes) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[] primesIdx = new int[primes.length];

        int[] dp = new int[n];
        
        dp[0] = 1;
        
        for (int i = 1; i < n; i++) {
            int next = Integer.MAX_VALUE;
            for(int idx = 0;idx<primes.length;idx++){
                next = Math.min(next, dp[primesIdx[idx]] * primes[idx]);
            }
            for(int idx = 0;idx<primes.length;idx++){
                if(next == dp[primesIdx[idx]] * primes[idx]){
                    primesIdx[idx]++;
                }
            }
            dp[i] = next;
        }

        return dp[n-1];
    }
}

// The key to the solution is that Kth ratio (wage / quality) can only satisfy workers with a smaller ratio. 
    // Otherwise, it will break the minimum expectation constraint, since every worker will be sharing the same ratio. 
    // However, you cannot simply pick the first Kth workers. Since if the sum of the quality is super high, 
    // then we would rather have a higher ratio but smaller sum of quality. 
    // Therefore, we are looking for the minimum sum of quality * ratio. Following is how the algorithm works:
    
    // 1. Create an array that stores the ratio (worker[0]) and quality (worker[1]). 
    //     We don't care about the min wage expectation anymore, 
    //     since we are only looking at the workers with a ratio that is smaller than any current ratio, 
    //     and will always satisfy the minimum constraint.
    // 2. Sort the array and start from Kth smallest ratio. 
    //     Otherwise, there won't be enough workers that satisfy with the current ratio (minimum constraint breaks)
    // 3. Keep increase the current ratio with the next worker and find the smallest sum, since both the sum of quality and ratio impacts the result
    // 4. Keep removing the largest quality, since we want the smallest sum of quality and the smallest ratio possible
class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
        double[][] workers = new double[quality.length][2];
        for(int i = 0;i<workers.length;i++){
            workers[i] = new double[]{(double)(wage[i])/quality[i],(double)(quality[i])};
        }
        
        Arrays.sort(workers,(a,b)->(Double.compare(a[0],b[0])));
        double res = Double.MAX_VALUE, curSum = 0;
        PriorityQueue<Double> pq = new PriorityQueue<Double>((a,b)->Double.compare(b,a));
        for(double[] worker : workers){
            curSum += worker[1];
            pq.add(worker[1]);
            if(pq.size()>K){
                curSum -= pq.poll();
            }
            if(pq.size() == K){
            	//since the current ratio is larger than any of the item now
            	//it can guarantee that minimum wage are satisfied.
                res = Math.min(res, curSum * worker[0]);
            }
        }
        
        return res;
    }
}

//main idea is to act like a list of list, which start with nums1[i]
//nums1[0]->nums2[0]->nums2[1]-> ...
//nums1[i]->nums2[0]->nums2[1]-> ...
//so can use priorityqueue to store tumple, nums1, nums2 and index for nums2
//and always extract the min value.
class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums1.length == 0 || nums2.length == 0 || k==0){
            return res;
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->(a[0]+a[1]-b[0]-b[1]));
        for(int i = 0;i<nums1.length;i++){
            pq.offer(new int[]{nums1[i],nums2[0],0});
        }
        while(k>0 && !pq.isEmpty()){
            k--;
            int[] cur  = pq.poll();
            List<Integer> temp = new ArrayList<>();
            temp.add(cur[0]);
            temp.add(cur[1]);
            res.add(temp);
            
            if(cur[2] + 1 ==nums2.length){
                continue;
            }
            pq.offer(new int[]{cur[0], nums2[cur[2]+1], cur[2]+1});
        }
        
        return res;
    }
}

//bucket sort
class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> count = new HashMap<>();
        for (char ch : s.toCharArray()) {
            count.put(ch, count.getOrDefault(ch, 0) + 1);
        }
        List<Character>[] buckets = new List[s.length() + 1];
        for (char ch : count.keySet()) {
            int freq = count.get(ch);
            if (buckets[freq] == null) {
                buckets[freq] = new ArrayList<Character>();
            }
            buckets[freq].add(ch);
        }

        StringBuilder sb = new StringBuilder();
        for (int pos = buckets.length - 1; pos > 0; pos--) {
            if(buckets[pos]!=null){
                for(char c: buckets[pos]){
                    for(int i = 0;i<pos;i++){
                        sb.append(c);
                    }
                }
            }
        }
        
        return sb.toString();

    }
}

import java.util.*;

class Solution {

    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> tail = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            //need to skip when this been used.
            if(count.get(cur)==0)continue;
            if(tail.containsKey(cur-1) && tail.get(cur-1)>0){
                tail.put(cur-1,tail.get(cur-1)-1);
                tail.put(cur,tail.getOrDefault(cur,0)+1);
                count.put(cur,count.get(cur)-1);
            }else if(count.getOrDefault(cur,0)>0 && count.getOrDefault(cur+1,0)>0 && count.getOrDefault(cur+2,0)>0){
                tail.put(cur+2,tail.getOrDefault(cur+2,0)+1);
                count.put(cur,count.get(cur)-1);
                count.put(cur+1,count.get(cur+1)-1);
                count.put(cur+2,count.get(cur+2)-1);
            }else{
                return false;
            }
        }
        return true;
    }
}

class Solution {

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        Map<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
        for (int[] pair : flights) {
            HashMap<Integer,Integer> r = map.getOrDefault(pair[0],new HashMap<>());
            r.put(pair[1],pair[2]);
            map.put(pair[0],r);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->(a[1]-b[1]));
        //store stops in the tuple so can asset whether reach max stops.
        pq.offer(new int[]{src,0,K+1});
        while(!pq.isEmpty()){
            int[] cur =pq.poll();
            int city = cur[0];
            int price = cur[1];
            int stops = cur[2];
            if(city == dst) return price;
            if(stops>0){
                HashMap<Integer,Integer> adj = map.getOrDefault(city,new HashMap());
                for(Map.Entry<Integer,Integer> e:adj.entrySet()){
                    pq.offer(new int[]{e.getKey(),price+e.getValue(),stops-1});
                }
            }

        }
        return -1;

    }
}

//Union find, group all the stones together if they share the same col or row.
//total stone - number of island will be the max count can be removed.	
class Solution {

    HashMap<String, String> union;
    int count;

    public int removeStones(int[][] stones) {
        union = new HashMap<>();
        count = stones.length;

        for (int[] stone : stones) {
            String pos = stone[0] + " " + stone[1];
            union.put(pos, pos);
        }

        for (int[] s1 : stones) {
            String ss1 = s1[0] + " " + s1[1];
            for (int[] s2 : stones) {
                if (s1[0] == s2[0] || s1[1] == s2[1]) {
                    String ss2 = s2[0] + " " + s2[1];
                    union(ss1, ss2);
                }
            }
        }

        return stones.length - count;
    }

    private void union(String s1, String s2) {
        String r1 = find(s1), r2 = find(s2);
        if (r1.equals(r2)) {
            return;
        }
        union.put(r1, r2);
        count--;
    }

    private String find(String s) {
        if (!union.get(s).equals(s)) {
            union.put(s, find(union.get(s)));
        }
        return union.get(s);
    }

}

class Solution {

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        HashMap<String, String> parent = new HashMap<>();
        HashMap<String, String> accountName = new HashMap<>();
        HashMap<String, List<String>> unions = new HashMap<>();
        //put all email into map.
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                parent.put(account.get(i), account.get(1));
                accountName.put(account.get(i), name);
            }
        }

        //union all emails belong to the same person.
        //a<-b, a<-c,  d<-b(parent to a, so d<-a), d<-f,
        //d<-a<-b,c   d<-f
        for (List<String> account : accounts) {
            String parentEmail = find(parent, account.get(1));
            for (int i = 2; i < account.size(); i++) {
                parent.put(find(parent, account.get(i)), parentEmail);
            }
        }

        for (String email : parent.keySet()) {
            String parentEmail = find(parent, email);
            unions.putIfAbsent(parentEmail, new ArrayList<>());
            unions.get(parentEmail).add(email);
        }

        List<List<String>> res = new ArrayList<>();
        for (String parentEmail : unions.keySet()) {
            List<String> temp = new ArrayList<>(unions.get(parentEmail));
            temp.sort(String::compareTo);
            temp.add(0, accountName.get(parentEmail));
            res.add(temp);

        }

        return res;


    }

    private String find(Map<String, String> p, String s) {
        return p.get(s).equals(s) ? s : find(p,p.get(s));
    }

}

/**
Union found all nodes.
Count the union size of each union set.
Count the malware number of each union set.

Return the biggest union's malware if there is one and only one malware.
If no such union that has and has only one malware,
return the malware with minimum index.

Time Complexity:
O(N^2)

**/
class Solution {

    int[] parent;

    public int minMalwareSpread(int[][] graph, int[] initial) {
        int len = graph.length;
        parent = new int[len];
        for(int i = 0;i<len;i++){
            parent[i] = i;
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (graph[i][j] == 1) {
                    union(i, j);
                }
            }
        }

        int[] unionSize = new int[len];
        int[] malCount = new int[len];

        for(int i = 0;i<len;i++){
            unionSize[find(i)]++;
        }

        for(int init : initial){
            malCount[find(init)]++;
        }

        int res = -1;
        int maxSize = -1;
        Arrays.sort(initial);
        for(int init : initial){
            int idx = find(init);
            //if there's only one malware in the union
            //and this union is the largest, so can minimize the infested node.
            if(malCount[idx]==1 && unionSize[idx]>maxSize){
                res = init;
                maxSize = unionSize[idx];
            }
        }
        if(maxSize!=-1){
            return res;
        }
        return initial[0];
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int p_x = find(x);
        int p_y = find(y);

        if (p_x != p_y) {
            parent[p_x] = p_y;
        }
    }
}

/**
Union all the island together as one island and count the total number of unions.
*/
class Solution {

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res = new LinkedList<>();
        if (m <= 0 || n <= 0) {
            return res;
        }

        int count = 0;
        int[] roots = new int[m * n];   // 1D array of roots
        Arrays.fill(roots, -1);         // Every position is water initially.
        int[][] directions = new int[][][[-1, 0], [1, 0], [0, -1], [0, 1]];

        for (int[] p : positions) {

            int island = p[0] * n + p[1];
            //in case of duplicated position.
            if (roots[island] != -1) {
                res.add(count);
                continue;
            }

            roots[island] = island;     // Set it to be the root of itself.
            count++;

            // Check four directions
            for (int[] dir : directions) {
                int x = p[0] + dir[0], y = p[1] + dir[1];
                int neighbor = x * n + y;
                // Skip when x or y is invalid, or neighbor is water.
                if (x < 0 || x >= m || y < 0 || y >= n || roots[neighbor] == -1) {
                    continue;
                }
                int neighborRoot = find(neighbor, roots);
                int islandRoot = find(island, roots);
                if (islandRoot != neighborRoot) {
                    // Union by position, always append smaller one to the larger one
                    //so it can have the same root.
                    if (islandRoot >= neighborRoot) {
                        roots[neighborRoot] = islandRoot;
                    } else {
                        roots[islandRoot] = neighborRoot;
                    }
                    count--;
                }
            }
            res.add(count);
        }

        return res;
    }

    private int find(int id, int[] roots) {
        if (roots[id] == id) {
            return id;
        } else {
            roots[id] = find(roots[id], roots);    // path compression
            return roots[id];
        }
    }
}

/**

*/
class Solution {

    public int minMalwareSpread(int[][] graph, int[] initial) {
        HashSet<Integer> malware = new HashSet<>();
        int len = graph.length;
        for (int init : initial) {
            malware.add(init);
        }
        List<Integer>[] count = new List[len];

        for (int i = 0; i < len; i++) {
            count[i] = new ArrayList<Integer>();
        }

        for (int init : initial) {
            Queue<Integer> queue = new LinkedList<>();
            HashSet<Integer> visited = new HashSet<>();
            queue.offer(init);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                visited.add(cur);
                count[cur].add(init);

                for (int i = 0; i < len; i++) {
                    if (cur != i && graph[cur][i] == 1 && !malware.contains(i) && !visited.contains(i)) {
                        queue.offer(i);
                    }
                }
            }
        }

        int[] affectCount = new int[len];
        for (int i = 0; i < len; i++) {
            if (malware.contains(i) || count[i].size() != 1) {
                continue;
            }

            affectCount[count[i].get(0)]++;

        }

        int res = -1;
        int maxSize = 0;
        Arrays.sort(initial);

        for (int idx = 0; idx < len; idx++) {
            if (affectCount[idx] > maxSize) {
                maxSize = affectCount[idx];
                res = idx;
            }
        }

        if (maxSize == 0) {
            return initial[0];
        }
        return res;

    }
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        HashMap<Integer,Integer> preSum = new HashMap();
        preSum.put(0,1);
        int res = 0, sum =0;
        for(int i = 0;i<nums.length;i++){
            int cur = nums[i];
            sum+=cur;
            if(preSum.containsKey(sum-k)){
                res += preSum.get(sum-k);
            }
            preSum.put(sum,preSum.getOrDefault(sum,0)+1);
        }
        return res;
    }
}

class Solution {

    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        HashMap<Integer, Integer> counter = new HashMap<>();
        int res = 0;
        int m = matrix.length, n = matrix[0].length;
        //count the sum from matrix[i][0] to matrix[i][j]
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                matrix[i][j] += matrix[i][j - 1];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                counter.clear();
                counter.put(0, 1);
                int cur = 0;
                for (int[] ints : matrix) {
                    //sum from the top of matrix to current row
                    //where left = i and right  = j.
                    cur += ints[j] - (i > 0 ? ints[i - 1] : 0);
                    //cur is from the top
                    //cur-target, means how many sub can sum to cur-target
                    //so the sum of sub and sub-cur will be (cur-target) + target = cur;
                    res += counter.getOrDefault(cur - target, 0);
                    counter.put(cur, counter.getOrDefault(cur, 0) + 1);
                }
            }
        }

        return res;
    }
}

//count the number of char in the window
//if the total - maxCount is larger than K, means it's invalid
//that K moves will not make the window valid.
//so we keep moving left until the window is valid.
class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0, right = 0, maxLen = 0;
        int len = s.length();
        while (right < len) {
            char chRight = s.charAt(right);
            count[chRight - 'A']++;
            int num_max = findMax(count);
            while (right - left + 1 - num_max > k) {
                count[s.charAt(left++) - 'A']--;
                num_max = findMax(count);
            }

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

    public int findMax(int[] A) {
        return Arrays.stream(A).max().getAsInt();
    }
}