class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder ans = new StringBuilder();
        if ((numerator < 0) == (denominator > 0)) {
            ans.append("-");
        }
        long dividend = Math.abs(Long.valueOf(numerator));
        long divisor = Math.abs(Long.valueOf(denominator));
        long remainder = dividend % divisor;
        ans.append(dividend / divisor);
        if (remainder == 0) {
            return ans.toString();
        }

        ans.append(".");
        Map<Long, Integer> visited = new HashMap<>();
        while (remainder != 0 && !visited.containsKey(remainder)) {
            visited.put(remainder, ans.length());
            remainder *= 10;
            ans.append(remainder / divisor);
            remainder %= divisor;
        }
        if (remainder != 0) {
            ans = ans.insert(visited.get(remainder), "(").append(")");
        }
        return ans.toString();
    }
}

class Solution {
    public int minCost(String colors, int[] neededTime) {
        char[] colorArray = colors.toCharArray();
        int max = neededTime[0], count = 1, timeSum = neededTime[0], ans = 0;
        for (int i = 1; i < colorArray.length; i++) {
            char currColor = colorArray[i], lastColor = colorArray[i - 1];
            if (currColor == lastColor) {
                max = Math.max(max, neededTime[i]);
                timeSum += neededTime[i];
                count += 1;
            } else {
                if (count > 1) {
                    ans += timeSum - max;
                }
                max = neededTime[i];
                count = 1;
                timeSum = neededTime[i];
            }
        }
        if (count > 1) {
            ans += timeSum - max;
        }
        return ans;
    }
}

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorAns = 0;
        for (int num : nums) {
            xorAns ^= num;
        }
        int diff = xorAns & (-xorAns), ans1 = 0;
        for (int num : nums) {
            if ((num & diff) != 0) {
                ans1 ^= num;
            }
        }
        return new int[] { ans1, xorAns ^ ans1 };
    }
}

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        TreeMap<Integer, Integer> idxUpdate = new TreeMap<>();
        for (int[] update : updates) {
            idxUpdate.put(update[0], idxUpdate.getOrDefault(update[0], 0) + update[2]);
            idxUpdate.put(update[1] + 1, idxUpdate.getOrDefault(update[1] + 1, 0) - update[2]);
        }
        int[] ans = new int[length];
        int sum = 0;
        // updates是在给sum加成, 我们记录什么时候有加成, 什么时候停止加成, 不同的加成可以叠加.
        for (int i = 0; i < ans.length; i++) {
            sum += idxUpdate.getOrDefault(i, 0);
            ans[i] = sum;
        }
        return ans;
    }
}

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] revisions1 = version1.split("\\.");
        String[] revisions2 = version2.split("\\.");
        int ptr1 = 0, ptr2 = 0, ans = 0;
        while (ptr1 < revisions1.length || ptr2 < revisions2.length) {
            int revision1 = ptr1 >= revisions1.length ? 0 : Integer.parseInt(revisions1[ptr1]);
            int revision2 = ptr2 >= revisions2.length ? 0 : Integer.parseInt(revisions2[ptr2]);
            if (revision1 < revision2) {
                ans = -1;
                break;
            } else if (revision1 > revision2) {
                ans = 1;
                break;
            } else {
                ptr1 += 1;
                ptr2 += 1;
            }
        }
        return ans;
    }
}

class Solution {
    private TreeNode ans;

    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        helper(root, null);
        return ans;
    }

    private void helper(TreeNode node, TreeNode parent) {
        if (node.left != null) {
            helper(node.left, node);
        }
        ans = ans == null ? node : ans;
        if (parent != null) {
            node.right = parent;
            node.left = parent.right;
            parent.left = null;
            parent.right = null;
        }
    }
}

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0), ptr = head;
        while (ptr != null) {
            ListNode prev = dummy;
            while (prev.next != null && prev.next.val < ptr.val) {
                prev = prev.next;
            }
            ListNode nextNode = ptr.next;
            ptr.next = prev.next;
            prev.next = ptr;
            ptr = nextNode;
        }
        return dummy.next;
    }
}

class Solution {
    // dp[n][m] = sum(dp[n - 1][m - 1] + dp[n - 1][m - 2] + ... + dp[n - 1][m - k]);
    public int numRollsToTarget(int n, int k, int target) {
        int[][] dp = new int[n + 1][target + 1];
        int modulo = (int) 1e9 + 7;
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                for (int value = 1; value <= k && j - value > 0; value++) {
                    dp[i][j] = Math.floorMod(dp[i][j] + dp[i - 1][j - value], modulo);
                }
            }
        }
        return dp[n][target];
    }
}

class Solution {
    private String res;

    private static class Node {
        Map<Character, Node> children;
        boolean isWord;

        Node(Map<Character, Node> _children) {
            this.children = _children;
            isWord = false;
        }
    }

    private void addWord(Node root, String word) {
        Node ptr = root;
        for (char letter : word.toCharArray()) {
            ptr.children.putIfAbsent(letter, new Node(new HashMap<>()));
            ptr = ptr.children.get(letter);
        }
        ptr.isWord = true;
    }

    private void dfs(Node node, StringBuilder curr) {
        boolean hasLongerWord = false;
        for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
            if (entry.getValue().isWord) {
                curr.append(entry.getKey());
                dfs(entry.getValue(), curr);
                hasLongerWord = true;
                curr.setLength(curr.length() - 1);
            }
        }
        if (!hasLongerWord) {
            if (curr.length() > res.length() || (curr.length() == res.length() && curr.toString().compareTo(res) < 0)) {
                res = curr.toString();
            }
        }
    }

    public String longestWord(String[] words) {
        Node root = new Node(new HashMap<>());
        for (String word : words) {
            addWord(root, word);
        }
        res = "";
        dfs(root, new StringBuilder());
        return res;
    }
}

class FileSystem {
    private static class Node {
        Map<String, Node> children;
        StringBuilder content;

        Node(Map<String, Node> _children) {
            this.children = _children;
        }

        Node(StringBuilder _content) {
            this.content = _content;
        }
    }

    private Node root;

    public FileSystem() {
        root = new Node(new TreeMap<>());
    }

    public List<String> ls(String path) {
        String[] intermediate = path.split("/");
        Node ptr = root;
        for (int i = 1; i < intermediate.length; i++) {
            ptr = ptr.children.get(intermediate[i]);
        }
        List<String> ans = new ArrayList<>();
        if (ptr.content != null) {
            ans.add(intermediate[intermediate.length - 1]);
        } else {
            for (String child : ptr.children.keySet()) {
                ans.add(child);
            }
        }
        return ans;
    }

    public void mkdir(String path) {
        Node ptr = root;
        String[] files = path.split("/");
        for (int i = 1; i < files.length; i++) {
            String file = files[i];
            ptr.children.putIfAbsent(file, new Node(new TreeMap<>()));
            ptr = ptr.children.get(file);
        }
    }

    public void addContentToFile(String filePath, String content) {
        Node ptr = root;
        String[] files = filePath.split("/");
        for (int i = 1; i < files.length - 1; i++) {
            ptr = ptr.children.get(files[i]);
        }
        if (ptr.children.containsKey(files[files.length - 1])) {
            ptr.children.get(files[files.length - 1]).content.append(content);
        } else {
            Node newFile = new Node(new StringBuilder());
            newFile.content.append(content);
            ptr.children.put(files[files.length - 1], newFile);
        }
    }

    public String readContentFromFile(String filePath) {
        Node ptr = root;
        String[] files = filePath.split("/");
        for (int i = 1; i < files.length - 1; i++) {
            ptr = ptr.children.get(files[i]);
        }
        return ptr.children.get(files[files.length - 1]).content.toString();
    }
}
/**
 * Your FileSystem object will be instantiated and called as such:
 * FileSystem obj = new FileSystem();
 * List<String> param_1 = obj.ls(path);
 * obj.mkdir(path);
 * obj.addContentToFile(filePath,content);
 * String param_4 = obj.readContentFromFile(filePath);
 */