class Solution {
TreeNode ans;

public void inorder(TreeNode c,TreeNode target) {
if (c != null) {
inorder(c.left, target);
if (c.val == target.val) {
ans = c;
}
inorder(c.right, target);
}
}

public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target)
{
inorder(cloned,target);
return ans;
}
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        MaxDepthInfo maxDepthInfo = new MaxDepthInfo(0 ,0);
        sumAtLevel(root, 0, maxDepthInfo);
        return maxDepthInfo.getSumAtMaxDepth();
    }

    public void sumAtLevel(TreeNode root, int currentDepth, MaxDepthInfo maxDepthInfo) {
        if (root == null) return;

        if (currentDepth > maxDepthInfo.getMaxDepth()) {
            maxDepthInfo.setMaxDepth(currentDepth);
            maxDepthInfo.setSumAtMaxDepth(root.val);
        }

        else if (currentDepth == maxDepthInfo.getMaxDepth())
            maxDepthInfo.setSumAtMaxDepth(maxDepthInfo.getSumAtMaxDepth() + root.val);

        sumAtLevel(root.left, currentDepth + 1, maxDepthInfo);
        sumAtLevel(root.right, currentDepth + 1, maxDepthInfo);
    }

    public static class MaxDepthInfo {
        private int maxDepth;
        private int sumAtMaxDepth;

        public MaxDepthInfo(int maxDepth, int sumAtMaxDepth) {
            this.maxDepth = maxDepth;
            this.sumAtMaxDepth = sumAtMaxDepth;
        }

        public int getMaxDepth() { return maxDepth;}

        public void setMaxDepth(int maxDepth) { this.maxDepth = maxDepth;}

        public int getSumAtMaxDepth() { return sumAtMaxDepth;}

        public void setSumAtMaxDepth(int sumAtMaxDepth) { this.sumAtMaxDepth = sumAtMaxDepth;}
    }
}

class Solution {
   private final Map<Integer, List<Node>> connected = new HashMap<>();

    public int networkDelayTime(int[][] times, int n, int k) {
        for (int[] time : times) {
            connected.putIfAbsent(time[0], new ArrayList<>());
            connected.get(time[0]).add(new Node(time[2], time[1]));
        }
        connected.forEach((source, nodes) -> nodes.sort(Comparator.comparing(Node::travelTime)));
        int[] receivedTime = new int[n + 1]; Arrays.fill(receivedTime, 1, receivedTime.length, Integer.MAX_VALUE);
        dfs(receivedTime, 0, k);
        
        int max = Arrays.stream(receivedTime).max().orElseThrow(RuntimeException::new);
        return max == Integer.MAX_VALUE ? -1 : max;
    }

    private void dfs(int[] receivedTime, int currentTime, int currentNode) {
        if (receivedTime[currentNode] <= currentTime) return;
        receivedTime[currentNode] = currentTime;
        if (connected.containsKey(currentNode))
            connected.get(currentNode).forEach(node -> dfs(receivedTime, currentTime + node.travelTime(), node.destination()));
    }

    public record Node(int travelTime, int destination) {}
}

class Solution {
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0){
            List<String> result = new ArrayList<>();
            return result;
        }
        List<String> res = combine(digits); 
        return res;
    }
    
    public List<String> combine(String digit){
        if(digit.length() == 0 ){
            List<String> result = new ArrayList<>();
            result.add("");
            return result;
        }
        
        String[] codes = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        
        char c = digit.charAt(0);
        
        String  digits_left = digit.substring(1);
        
        List<String> res = combine(digits_left);
        
        List<String> result = new ArrayList<>();
        
        String code_for_current_digit = codes[c-'0'];
        
        for(int i=0;i<code_for_current_digit.length();i++){
            char code_char = code_for_current_digit.charAt(i);
            
            if(!res.isEmpty()){
                for(String s : res){
                    result.add(code_char + s);
                }    
            }
            else{
                res.add(String.valueOf(code_char));
            }
            
        }
        
        
        return result;
    }
}

class Solution {
    public Node connect(Node root) {
        Node leftMost = root;
        while (leftMost != null) {
            Node cur = leftMost;
            leftMost = null;
            Node pre = null;
            while (cur != null) {
                if (leftMost == null) {
                    leftMost = cur.left == null ? cur.right: cur.left;
                }
                if (pre != null) {
                    pre.next = cur.left == null ? cur.right : cur.left;
                }
                if (cur.left != null && cur.right != null) {
                    cur.left.next = cur.right;
                }
                pre = cur.right == null ? (cur.left == null ? pre : cur.left) : cur.right;
                cur = cur.next;
            }
        }
        return root;
    }
}

class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> permutations = new ArrayList<>();
        Arrays.sort(nums);
        backtracking(permutations, new ArrayList<>(), nums, new boolean[nums.length]);
        return permutations;
    }

    private void backtracking(List<List<Integer>> permutations, List<Integer> current, int[] nums, boolean[] used) {
        if (current.size() == nums.length)
            permutations.add(new ArrayList<>(current));
        else {
            for (int i = 0; i < nums.length; i++) {
                if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
                current.add(nums[i]);
                used[i] = true;
                backtracking(permutations, current, nums, used);
                used[i] = false;
                current.remove(current.size() - 1);
            }
        }
    }
}

class Solution {
    public int countVowelStrings(int n) {
        int a,e,i,o,u;
        a = e = i = o = u = 1;
        
        for(int t = 1; t < n; t++){
            
            a = a + e + i + o + u;
            e = e + i + o + u;
            i = i + o + u;
            o = o + u;
            u = u;
        }
        return a + e + i + o + u;
    }
}

public class NestedIterator implements Iterator<Integer> {

    private List<Integer> integerList = new ArrayList<>();
    private int index = 0;
    public NestedIterator(List<NestedInteger> nestedList) {
        for (NestedInteger nestedInteger : nestedList) {
            flatten(nestedInteger);
        }
    }
    
    private void flatten(NestedInteger nested) {
        if (nested.isInteger()) 
            integerList.add(nested.getInteger());
        else 
            for (NestedInteger nestedFromList : nested.getList()) {
                flatten(nestedFromList);
        }
    }

    @Override
    public boolean hasNext() {
        return index < integerList.size();
    }

    @Override
    public Integer next() {
        return integerList.get(index++);
    }
}

class Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    public String build(String S) {
        Stack<Character> ans = new Stack();
        for (char c: S.toCharArray()) {
            if (c != '#')
                ans.push(c);
            else if (!ans.empty())
                ans.pop();
        }
        return String.valueOf(ans);
    }
}

class Solution {
    public String removeDuplicates(String s, int k) {
        Stack<int []> Master = new Stack<>();
        
        for(char ch : s.toCharArray()){
            if(!Master.isEmpty() && Master.peek()[0] == ch){
                Master.peek()[1]++;
            }
            else Master.push(new int[]{ch, 1});
            if(Master.peek()[1] == k) Master.pop();
        }
        StringBuilder sb = new StringBuilder();
        while(!Master.isEmpty()){
            int top[] = Master.pop();
            while(top[1] --> 0)
                sb.append((char)top[0]);
        }
        return sb.reverse().toString();
    }
}

class Solution {
    public long[] kthPalindrome(int[] queries, int intLength) {
        long[] res= new long[queries.length];
        for(int i=0;i<queries.length;i++){
            res[i]=nthPalindrome(queries[i],intLength);
        }
        return res;
    }
    public long nthPalindrome(int nth, int kdigit)
    {
    long temp = (kdigit & 1)!=0 ? (kdigit / 2) : (kdigit/2 - 1);
    long palindrome = (long)Math.pow(10, temp);
    palindrome += nth - 1;
    long res1=palindrome;
    if ((kdigit & 1)>0)
        palindrome /= 10;
    while (palindrome>0)
    {
        res1=res1*10+(palindrome % 10);
        palindrome /= 10;
    }
    String g="";
    g+=res1;
    if(g.length()!=kdigit)
        return -1;
    return res1;
}
}