import java.util.*;

class Program {
    public static boolean interweavingStrings(String one, String two, String three) {
        StringBuilder currentString = new StringBuilder();
        return helper(currentString, one, two, three, 0, 0);
    }

    public static boolean helper(StringBuilder current, String one, String two, String three,
            int posOne, int posTwo) {
        if (posOne == one.length()) {
            String result = current.toString() + two.substring(posTwo, two.length());
            return result.equals(three);
        }
        if (posTwo == two.length()) {
            String result = current.toString() + one.substring(posOne, one.length());
            return result.equals(three);
        }
        current.append(one.charAt(posOne));
        boolean selectStringOne = helper(current, one, two, three, posOne + 1, posTwo);
        current.deleteCharAt(current.length() - 1);
        if (selectStringOne)
            return true;

        current.append(two.charAt(posTwo));
        boolean selectStringTwo = helper(current, one, two, three, posOne, posTwo + 1);
        current.deleteCharAt(current.length() - 1);
        return selectStringTwo;
    }
}

class Solution {
    // 记录左括号的个数. 如果左括号的个数是0, 那么就不能再往后加右括号.
    // 只能再加左括号.
    public List<String> generateDivTags(int numberOfTags) {
        List<String> result = new ArrayList<>();
        StringBuilder currentString = new StringBuilder();
        helper(currentString, result, 0, 0, numberOfTags);
        return result;
    }

    // currentLeft指的是currentString中有的left tag
    // remainingLeft指的是还有几个left tag没被抵消.
    public void helper(StringBuilder currentString, List<String> result,
            int currentLeftTagNum, int remainingLeftTag, int numberOfTags) {
        if (currentLeftTagNum == numberOfTags && remainingLeftTag == 0) {
            result.add(currentString.toString());
            return;
        }
        // 看是否可以添加左括号.
        if (currentLeftTagNum < numberOfTags) {
            currentString.append("<div>");
            helper(currentString, result, currentLeftTagNum + 1, remainingLeftTag + 1, numberOfTags);
            currentString.delete(currentString.length() - 5, currentString.length());
        }

        // 看是否可以添加右括号.
        if (remainingLeftTag > 0) {
            currentString.append("</div>");
            helper(currentString, result, currentLeftTagNum, remainingLeftTag - 1, numberOfTags);
            currentString.delete(currentString.length() - 6, currentString.length());
        }
    }
}

class Solution {
    public int getFood(char[][] grid) {
        Queue<int[]> q1 = new ArrayDeque<>();
        Queue<int[]> q2 = new ArrayDeque<>();
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int[] startPos = getPoint(grid, '*');
        int distance = 0;
        int result = -1;
        q1.offer(startPos);
        visited[startPos[0]][startPos[1]] = true;
        int[][] directions = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        while (!q1.isEmpty() || !q2.isEmpty()) {
            Queue<int[]> currentQueue = q1.isEmpty() ? q2 : q1;
            Queue<int[]> emptyQueue = q1.isEmpty() ? q1 : q2;
            while (!currentQueue.isEmpty()) {
                int[] currentPos = currentQueue.poll();
                char currentChar = grid[currentPos[0]][currentPos[1]];
                if (currentChar == '#') {
                    result = distance;
                    break;
                }
                for (int k = 0; k < 4; k++) {
                    int neighborRow = currentPos[0] + directions[k][0];
                    int neighborCol = currentPos[1] + directions[k][1];
                    if (!isOutOfBound(grid, neighborRow, neighborCol) && !visited[neighborRow][neighborCol]
                            && grid[neighborRow][neighborCol] != 'X') {
                        emptyQueue.offer(new int[] { neighborRow, neighborCol });
                        visited[neighborRow][neighborCol] = true;
                    }
                }
            }
            if (result != -1)
                break;
            distance += 1;
        }
        return result;
    }

    private int[] getPoint(char[][] grid, char target) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return null;
    }

    private boolean isOutOfBound(char[][] grid, int row, int col) {
        return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
    }
}

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> rotten = new LinkedList<>();
        int m = grid.length, n = grid[0].length;
        int unrotten = 0;
        // Add all rotten oranges positions into queue.
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2)
                    rotten.offer(new int[] { i, j });
                if (grid[i][j] == 1)
                    unrotten += 1;
            }
        }

        int ans = 0;
        int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
        while (!rotten.isEmpty()) {
            int length = rotten.size();
            boolean newRotten = false;
            for (int i = 0; i < length; i++) {
                int[] pos = rotten.poll();
                for (int[] direction : directions) {
                    int newRow = pos[0] + direction[0];
                    int newCol = pos[1] + direction[1];
                    if (!isOutOfBound(grid, newRow, newCol) && grid[newRow][newCol] == 1) {
                        newRotten = true;
                        grid[newRow][newCol] = 2;
                        unrotten -= 1;
                        rotten.offer(new int[] { newRow, newCol });
                    }
                }
            }
            if (newRotten == true)
                ans += 1;
        }
        return unrotten == 0 ? ans : -1;
    }

    private boolean isOutOfBound(int[][] grid, int row, int col) {
        return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
    }
}

class TimeMap {
    private Map<Integer, Map<String, String>> store;

    public TimeMap() {
        store = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        if (!store.containsKey(timestamp)) {
            store.put(timestamp, new HashMap<>());
        }
        store.get(timestamp).put(key, value);
    }

    public String get(String key, int timestamp) {
        if (store.containsKey(timestamp) && store.get(timestamp).containsKey(key)) {
            return store.get(timestamp).get(key);
        }

        for (int i = timestamp - 1; i > 0; i--) {
            if (store.containsKey(i) && store.get(i).containsKey(key)) {
                return store.get(i).get(key);
            }
        }
        return "";
    }
}

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
        return Arrays.copyOf(points, k);
    }

    public int squaredDistance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int[][] result = new int[mat.length][mat[0].length];
        initialize(result);
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                helper(mat, result, i, j);
            }
        }
        return result;
    }

    private void initialize(int[][] result) {
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[0].length; j++) {
                result[i][j] = -1;
            }
        }
    }

    private int helper(int[][] mat, int[][] result, int row, int col) {
        if (isOutOfBound(mat, row, col) || result[row][col] == -2) {
            return Integer.MAX_VALUE;
        }
        if (result[row][col] == -1 && mat[row][col] == 0) {
            result[row][col] = 0;
            return result[row][col];
        }
        if (result[row][col] != -1)
            return result[row][col];

        result[row][col] = -2;
        int up = helper(mat, result, row - 1, col);
        int down = helper(mat, result, row + 1, col);
        int left = helper(mat, result, row, col - 1);
        int right = helper(mat, result, row, col + 1);
        int minimum = Math.min(Math.min(left, right), Math.min(up, down)) + 1;
        result[row][col] = minimum;
        return result[row][col];
    }

    private boolean isOutOfBound(int[][] mat, int row, int col) {
        return row < 0 || row >= mat.length || col < 0 || col >= mat[0].length;
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        while (start < end) {
            int middle = start + (end - start) / 2;
            if (isBadVersion(middle)) {
                end = middle;
            } else {
                start = middle + 1;
            }
        }
        return start;
    }
}

class Solution {
    public int numWays(int n, int k) {
        return helper(0, 0, 0, n, k);
    }

    public int helper(int a, int b, int pos, int n, int k) {
        if (pos == n) {
            return 1;
        }
        int sum = 0;
        for (int i = 1; i <= k; i++) {
            if (a == b && a == i) {
                continue;
            } else {
                sum += helper(b, i, pos + 1, n, k);
            }
        }
        return sum;
    }
}