class Solution(object):
    # https://leetcode.com/problems/convert-bst-to-greater-tree/solution/
    # def __init__(self):
    #     self.total = 0

    # def convertBST(self, root):
    #     if root is not None:
    #         self.convertBST(root.right)
    #         self.total += root.val
    #         root.val = self.total
    #         self.convertBST(root.left)
    #     return root

    def convertBST(self, root):
        total = 0
        
        node = root
        stack = []
        while stack or node is not None:
            # push all nodes up to (and including) this subtree's maximum on
            # the stack.
            while node is not None:
                stack.append(node)
                node = node.right

            node = stack.pop()
            total += node.val
            node.val = total

            # all nodes with values between the current and its parent lie in
            # the left subtree.
            node = node.left

        return root

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        totalsum = sum(nums)
        leftsum = 0
        for i, v in enumerate(nums):
            # leftsum == rightsum
            if leftsum == totalsum - leftsum - v:
                return i
            leftsum += v
        return -1

import java.util.List;

class Solution {
    public String[] reorderLogFiles(String[] logs) {
        Arrays.sort(logs, (log1, log2) -> {
            String[] split1 = log1.split(" ", 2);
            String[] split2 = log2.split(" ", 2);
            boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
            boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
            if (!isDigit1 && !isDigit2) {
                int cmp = split1[1].compareTo(split2[1]);
                if (cmp != 0) return cmp;
                return split1[0].compareTo(split2[0]);
            }
            return isDigit1 ? (isDigit2 ? 0 : 1) : -1;
        });
        return logs;
    }
}

class Solution(object):
    # def kClosest(self, points, K):
    #     """
    #     :type points: List[List[int]]
    #     :type K: int
    #     :rtype: List[List[int]]
    #     """
    #     # Sort
    #     return sorted(points, key=lambda x: x[0] ** 2 + x[1] ** 2)[:K]
    
    def kClosest(self, points, K):
        # K smallest heaq
        return heapq.nsmallest(K, points, key=lambda x: x[0] ** 2 + x[1] ** 2)

class Solution(object):
    def transpose(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        R, C = len(A), len(A[0])
        ans = [[None] * R for _ in xrange(C)]
        for r, row in enumerate(A):
            for c, val in enumerate(row):
                ans[c][r] = val
        return ans
        # Alternative Solution:
        # return zip(*A)

    # def transpose(self, A):
    #     res = []
    #     for i in range(len(A[0])):
    #         temp = []
    #         for j in range(len(A)):
    #             temp.append(A[j][i])
    #         res.append(temp)
    #     return res

class Solution {
    /*public int fib(int N) {
        // Recursively, O(n)
        if (N == 0) return 0;
        if (N == 1) return 1;
        return fib(N - 1) + fib(N - 2);
    }*/

    private List memo;

    public Solution() {
        memo = new ArrayList();
        memo.add(0);
        memo.add(1);
    }

    public int fib(int N) {
        // Dp with memo, O(n)
        if (N < memo.size()) return memo.get(N);
        for (int i = memo.size(); i <= N; i++) {
            memo.add(memo.get(i - 1) + memo.get(i - 2));
        }
        return memo.get(N);
    }
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


# https://leetcode.com/problems/path-sum-iii/discuss/91892/Python-solution-with-detailed-explanation
class Solution(object):
    # def find_paths(self, root, target):
    #     if root:
    #         return int(root.val == target)
    #         + self.find_paths(root.left, target - root.val)
    #         + self.find_paths(root.right, target - root.val)
    #     return 0

    # def pathSum(self, root, sum):
    #     """
    #     :type root: TreeNode
    #     :type sum: int
    #     :rtype: int
    #     """
    #     if root:
    #         return self.find_paths(root, sum)
    #         + self.pathSum(root.left, sum)
    #         + self.pathSum(root.right, sum)
    #     return 0

    def pathSumHelper(self, root, target, so_far, cache):
        if root:
            # complement == 1, root->curr path
            complement = so_far + root.val - target
            if complement in cache:
                # S->E path, sum(root->S)-sum(root->E) = target
                self.result += cache[complement]
            cache[so_far + root.val] = cache.get(so_far + root.val, 0) + 1
            self.pathSumHelper(root.left, target, so_far + root.val, cache)
            self.pathSumHelper(root.right, target, so_far + root.val, cache)
            cache[so_far + root.val] -= 1
        return

    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        self.result = 0
        self.pathSumHelper(root, sum, 0, {0: 1})
        return self.result

class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        count = [0] * 256
        i, numDistinct, maxLen = 0, 0, 0
        for j in range(len(s)):
            # udpate j
            if count[ord(s[j])] == 0:
                numDistinct += 1
            count[ord(s[j])] += 1
            # udpate i
            while numDistinct > k:
                count[ord(s[i])] -= 1
                if count[ord(s[i])] == 0:
                    numDistinct -= 1
                i += 1
            maxLen =  max(j - i + 1, maxLen)
        return maxLen

class Solution {
    // https://leetcode.com/problems/diameter-of-binary-tree/solution/
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) return 0;
        int L = depth(node.left);
        int R = depth(node.right);
        ans = Math.max(ans, L+R+1);
        return Math.max(L, R) + 1;
    }
}

class Solution(object):
    def toHex(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num == 0:
            return '0'
        # letter map
        mp = '0123456789abcdef'
        ans = ''
        for _ in range(8):
            # get last 4 digits
            # num & 1111b
            n = num & 15
            # hex letter for current 1111
            c = mp[n]
            ans = c + ans
            # num = num / 16
            num = num >> 4
        #strip leading zeroes
        return ans.lstrip('0')
    
    # def toHex(self, num):
    #     def tohex(val, nbits):
    #         return hex((val + (1 << nbits)) % (1 << nbits))
    #     return tohex(num, 32)[2:]

    # def toHex(self, num, h=''):
    #     return (not num or h[7:]) and h or self.toHex(num / 16, '0123456789abcdef'[num % 16] + h)

class Solution(object):
    def numUniqueEmails(self, emails):
        """
        :type emails: List[str]
        :rtype: int
        """
        email_set = set()
        for email in emails:
            elements = email.split('@')
            email_set.add(elements[0].split('+')[0].replace('.', '') + elements[1])
        return len(email_set)

class Solution {
    public int repeatedNTimes(int[] A) {
        HashMap hash = new HashMap<>();
        int ans = A[0];
        for (int n: A) {
            int count = hash.getOrDefault(n, 0) + 1;
            hash.put(n, count);
            if (count >= hash.get(ans)) ans = n;
        }
        return ans;
    }
}

class Solution(object):
    # def addStrings(self, num1, num2):
    #     """
    #     :type num1: str
    #     :type num2: str
    #     :rtype: str
    #     """
    #     if num1 is None:
    #         num1 = '0'
    #     if num2 is None:
    #         num2 = '0'
    #     res = []
    #     carry = 0
    #     ls = min(len(num1), len(num2))
    #     pos = -1
    #     while pos + ls >= 0:
    #         curr = int(num1[pos]) + int(num2[pos]) + carry
    #         res.insert(0, str(curr % 10))
    #         carry = curr / 10
    #         pos -= 1
    #     while pos + len(num1) >= 0:
    #         curr = int(num1[pos]) + carry
    #         res.insert(0, str(curr % 10))
    #         carry = curr / 10
    #         pos -= 1
    #     while pos + len(num2) >= 0:
    #         curr = int(num2[pos]) + carry
    #         res.insert(0, str(curr % 10))
    #         carry = curr / 10
    #         pos -= 1
    #     if carry != 0:
    #         res.insert(0, str(carry))
    #     return ''.join(res)

    def addStrings(self, num1, num2):
        res = []
        pos1 = len(num1) - 1
        pos2 = len(num2) - 1
        carry = 0
        # This conditon is great
        # https://leetcode.com/problems/add-strings/discuss/90436/Straightforward-Java-8-main-lines-25ms
        while pos1 >= 0 or pos2 >= 0 or carry == 1:
            digit1 = digit2 = 0
            if pos1 >= 0:
                digit1 = ord(num1[pos1]) - ord('0')
            if pos2 >= 0:
                digit2 = ord(num2[pos2]) - ord('0')
            res.append(str((digit1 + digit2 + carry) % 10))
            carry = (digit1 + digit2 + carry) / 10
            pos1 -= 1
            pos2 -= 1
        # reverse res
        return ''.join(res[::-1])

class Solution(object):
    def findCircleNum(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        # because
        visited = [0] * len(M)
        count = 0
        for i in range(len(M)):
            if visited[i] == 0:
                self.dfs(M, visited, i)
                count += 1
        return count

    def dfs(self, M, visited, i):
        for j in range(len(M)):
            if M[i][j] == 1 and visited[j] == 0:
                visited[j] = 1
                self.dfs(M, visited, j)

    # def findCircleNum(self, M):
    #     # BFS
    #     visited = [0] * len(M)
    #     count = 0
    #     queue = []
    #     for i in range(len(M)):
    #         if visited[i] == 0:
    #             queue.append(i)
    #             while queue:
    #                 curr = queue.pop(0)
    #                 visited[curr] = 1
    #                 for j in range(len(M)):
    #                     if M[curr][j] == 1 and visited[j] == 0:
    #                         queue.append(j)
    #             count += 1
    #     return count

#     def findCircleNum(self, M):
#         # Union Find
#         union = Union()
#         for i in range(len(M)):
#             union.add(i)
#         for i in range(len(M)):
#             for j in range(i + 1, len(M)):
#                 if M[i][j] == 1:
#                     union.union(i, j)
#         return union.count

# class Union(object):
#     """
#     weighted quick union find
#     """
#     def __init__(self):
#         # both dic and list is fine
#         self.id = {}
#         self.sz = {}
#         self.count = 0

#     def count(self):
#         return self.count

#     def connected(self, p, q):
#         return self.find(p) == self.find(q)

#     def add(self, p):
#         # init
#         self.id[p] = p
#         self.sz[p] = 1
#         self.count += 1

#     def find(self, p):
#         """
#         find root of p, and compress path
#         """
#         while p != self.id[p]:
#             self.id[p] = self.id[self.id[p]]
#             p = self.id[p]
#         return p

#     def union(self, p, q):
#         """
#         connect p and q
#         """
#         i, j = self.find(p), self.find(q)
#         if i == j:
#             return
#         if self.sz[i] > self.sz[j]:
#             i, j = j, i
#         self.id[i] = j
#         self.sz[j] += self.sz[i]
#         self.count -= 1

class Solution(object):
    # def maximumProduct(self, nums):
    #     """
    #     :type nums: List[int]
    #     :rtype: int
    #     """
    #     nums.sort()
    #     # Check min1*min2*max1 and max1*max2*max3
    #     return max(reduce(lambda x, y: x * y, nums[:2]) * nums[-1],
    #                reduce(lambda x, y: x * y, nums[-3:]))

    def maximumProduct(self, nums):
        min1 = min2 = float('inf')
        max1 = max2 = max3 = float('-inf')
        for num in nums:
            if num <= min1:
                min2 = min1
                min1 = num
            elif num <= min2:
                min2 = num
            if num >= max1:
                max3 = max2
                max2 = max1
                max1 = num
            elif num >= max2:
                max3 = max2
                max2 = num
            elif num >= max3:
                max3 = num
        return max(min1 * min2 * max1, max1 * max2 * max3)

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        res = []
        if s is None or p is None or len(s) == 0 or len(p) == 0:
            return res
        char_map = [0] * 256
        for c in p:
            char_map[ord(c)] += 1
        left, right, count = 0, 0, len(p)
        while right < len(s):
            if char_map[ord(s[right])] >= 1:
                count -= 1
            char_map[ord(s[right])] -= 1
            right += 1
            if count == 0:
                res.append(left)
            if right - left == len(p):
                if char_map[ord(s[left])] >= 0:
                    count += 1
                char_map[ord(s[left])] += 1
                left += 1
        return res

    # def findAnagrams(self, s, p):
    #     if len(s) < len(p):
    #         return []
    #     res = []
    #     p_len = len(p)
    #     bit_map = []
    #     for _ in range(26):
    #         bit_map.append(0)
    #     for c in p:
    #         bit_map[ord(c) - ord('a')] += 1
    #     s_p = str(bit_map)
    #     for i in range(26):
    #         bit_map[i] = 0
    #     for i in range(p_len - 1):
    #         bit_map[ord(s[i]) - ord('a')] += 1
    #     for i in range(p_len - 1, len(s)):
    #         bit_map[ord(s[i]) - ord('a')] += 1
    #         if i - p_len >= 0:
    #             bit_map[ord(s[i - p_len]) - ord('a')] -= 1
    #         if str(bit_map) == s_p:
    #             res.append(i - p_len + 1)
    #     return res

    # def findAnagrams(self, s, p):
    #     """
    #     :type s: str
    #     :type p: str
    #     :rtype: List[int]
    #     """
    #     res = []
    #     pCounter = collections.Counter(p)
    #     sCounter = collections.Counter(s[:len(p)-1])
    #     for i in range(len(p)-1,len(s)):
    #         sCounter[s[i]] += 1   # include a new char in the char_map
    #         if sCounter == pCounter:    # This step is O(1), since there are at most 26 English letters 
    #             res.append(i-len(p)+1)   # append the starting index
    #         sCounter[s[i-len(p)+1]] -= 1   # decrease the count of oldest char in the window
    #         if sCounter[s[i-len(p)+1]] == 0:
    #             del sCounter[s[i-len(p)+1]]   # remove the count if it is 0
    #     return res

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        def longestConsecutive(self, num):
            # Pop adjacency O(n) and O(n)
            num = set(num)
            maxLen = 0
            while num:
                n = num.pop()
                i = n + 1
                l1 = 0
                l2 = 0
                while i in num:
                    num.remove(i)
                    i += 1
                    l1 += 1
                i = n - 1
                while i in num:
                    num.remove(i)
                    i -= 1
                    l2 += 1
                maxLen = max(maxLen, l1 + l2 + 1)
            return maxLen

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    # def sortedArrayToBST(self, nums):
    #     """
    #     :type nums: List[int]
    #     :rtype: TreeNode
    #     """
    #     # Recursion with slicing
    #     if not nums:
    #         return None
    #     mid = len(nums) / 2
    #     root = TreeNode(nums[mid])
    #     root.left = self.sortedArrayToBST(nums[:mid])
    #     root.right = self.sortedArrayToBST(nums[mid + 1:])
    #     return root

    def sortedArrayToBST(self, nums):
        # Recursion with index
        return self.getHelper(nums, 0, len(nums) - 1)

    def getHelper(self, nums, start, end):
        if start > end:
            return None
        mid = (start + end) / 2
        node = TreeNode(nums[mid])
        node.left = self.getHelper(nums, start, mid - 1)
        node.right = self.getHelper(nums, mid + 1, end)
        return node

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        # Two Points
        begin, end = 0, len(numbers) - 1
        while begin < end:
            curr = numbers[begin] + numbers[end]
            if curr == target:
                return [begin + 1, end + 1]
            elif curr < target:
                begin += 1
            else:
                end -= 1

public class Solution {
    public String reverseWords(String s) {
        String words[] = s.split(" ");
        StringBuilder ans = new StringBuilder();
        for (String word: words)
            ans.append(new StringBuffer(word).reverse().toString() + " ");
        return ans.toString().trim();
    }
}

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/discuss/92956/Java-accepted-simple-solution
        res = []
        if nums:
            n = len(nums)
            for i in range(n):
                val = abs(nums[i]) - 1
                if nums[val] > 0:
                    nums[val] = -nums[val]
            for i in range(n):
                if nums[i] > 0:
                    res.append(i + 1)
        return res

class Solution {
    /*public boolean backspaceCompare(String S, String T) {
        // https://leetcode.com/problems/backspace-string-compare/discuss/135603/C%2B%2BJavaPython-O(N)-time-and-O(1)-space
        int i = S.length() - 1, j = T.length() - 1;
        while (true) {
            for (int back = 0; i >= 0 && (back > 0 || S.charAt(i) == '#'); --i)
                back += S.charAt(i) == '#' ? 1 : -1;
            for (int back = 0; j >= 0 && (back > 0 || T.charAt(j) == '#'); --j)
                back += T.charAt(j) == '#' ? 1 : -1;
            if (i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)) {
                i--; j--;
            } else
                return i == -1 && j == -1;
        }
    }*/

    public boolean backspaceCompare(String S, String T) {
        return trans(S).equals(trans(T));
    }
    private String trans(String str) {
        StringBuilder sb = new StringBuilder();
        for (char c : str.toCharArray()) {
            if (c != '#') { sb.append(c); } // if not '#', append it at the end of sb.
            else if (sb.length() > 0) { sb.deleteCharAt(sb.length() - 1); } // remove last char in sb, if sb is not empty.
        }
        return sb.toString();
    }

}

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        # https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity
        isPrime = [True] * n
        for i in xrange(2, n):
            if i * i >= n:
                break
            if not isPrime[i]:
                continue
            for j in xrange(i * i, n, i):
                isPrime[j] = False
        count = 0
        for i in xrange(2, n):
            if isPrime[i]:
                count += 1
        return count

class Solution:
    # def searchInsert(self, nums, target):
    #     """
    #     :type nums: List[int]
    #     :type target: int
    #     :rtype: int
    #     """
    #     min, pos = 0, 0
    #     max = len(nums) - 1
    #     while min <= max:
    #         # binary search
    #         pos = (max + min) / 2
    #         if nums[pos] == target:
    #             return pos
    #         elif nums[pos] > target:
    #             max = pos - 1
    #         else:
    #             min = pos + 1
    #     if min > pos:
    #         # this means that target is great than pos, and target
    #         # is not in nums
    #         return pos + 1
    #     return pos

    def searchInsert(self, nums, target):
        l, r = int(0), len(nums) - 1
        while l < r:
            mid = int((l + r) / 2)
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        if nums[l] < target:
            return l + 1
        return l 

    
    
if __name__ == '__main__':
    # begin
    s = Solution()
    print (s.searchInsert([1,3,5,6],5))    
    

import com.sun.corba.se.spi.orbutil.fsm.Guard.Result;

class Solution {
    public String toHex(int num) {
        String hex_map = "0123456789abcdef";
        if (num == 0) return "0";
        String res = "";
        // To avoid infinite loop caused by negative num
        while (num != 0 && res.length() < 8) {
            res = hex_map.charAt(num & 15) + res;
            num = num >> 4;
        }
        return res;
    }

    /* public String toHex(int num) {
        String hex = Integer.toHexString(num);
        return hex;
    } */
}

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        alnum_s = [t.lower() for t in s if t.isalnum()]
        ls = len(alnum_s)
        if ls <= 1:
            return True
        mid = ls / 2
        for i in range(mid):
            if alnum_s[i] != alnum_s[ls - 1 - i]:
                return False
        return True

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int n = minutesToTest / minutesToDie + 1;
        int pigs = 0;
        while (Math.pow(n, pigs) < buckets) pigs++;
        return pigs; 
    }
}

class Solution(object):
    # def uniquePathsWithObstacles(self, obstacleGrid):
    #     """
    #     :type obstacleGrid: List[List[int]]
    #     :rtype: int
    #     """
    #     m, n = len(obstacleGrid), len(obstacleGrid[0])
    #     dmap = [[0] * n for _ in range(m)]
    #     for i in range(m):
    #         if obstacleGrid[i][0] != 1:
    #             dmap[i][0] = 1
    #         else:
    #             break
    #     for j in range(n):
    #         if obstacleGrid[0][j] != 1:
    #             dmap[0][j] = 1
    #         else:
    #             break
    #     for i in range(1, m):
    #         for j in range(1, n):
    #             if obstacleGrid[i][j] == 1:
    #                 continue
    #             l = u = 0
    #             if i - 1 >= 0:
    #                 u = dmap[i - 1][j]
    #             if j - 1 >= 0:
    #                 l = dmap[i][j - 1]
    #             dmap[i][j] = l + u
    #     return dmap[m - 1][n - 1]

    def uniquePathsWithObstacles(self, obstacleGrid):
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        if m == 0:
            return 0
        dmap = [[0] * (n + 1) for _ in range(m + 1)]
        dmap[m - 1][n] = 1
        for i in range(m - 1, -1, -1):
            for j in  range(n - 1, -1, -1):
                if obstacleGrid[i][j] == 1:
                    dmap[i][j] = 0
                else:
                    dmap[i][j] = dmap[i][j + 1] + dmap[i + 1][j]
        return dmap[0][0]

import java.util.ArrayList;
import java.util.List;

/* class MinStack {
    private Stack stack;
    private Stack minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int x) {
        stack.push(x);
        if (minStack.size() == 0 || x <= minStack.peek()) minStack.push(x);
    }
    
    public void pop() {
        if (stack.size() > 0) {
            int curr = stack.pop();
            if (minStack.size() > 0 && curr == minStack.peek()) minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        if (minStack.size() > 0) 
            return minStack.peek();
        else
            return stack.peek();
    }
} */

class MinStack {
    private Stack stack;
    private Stack minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int x) {
        stack.push(x);
        if (minStack.size() == 0 || x <= minStack.peek()) minStack.push(x);
        else minStack.push(minStack.peek());
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

# class MinStack(object):
#     def __init__(self):
#         """
#         initialize your data structure here.
#         """
#         self.stack = []
#         self.min_stack = []


#     def push(self, x):
#         """
#         :type x: int
#         :rtype: nothing
#         """
#         self.stack.append(x)
#         if len(self.min_stack) == 0 or x <= self.min_stack[-1]:
#             self.min_stack.append(x)


#     def pop(self):
#         """
#         :rtype: nothing
#         """
#         if len(self.stack) > 0:
#             last = self.stack[-1]
#             # Need to check whether pop minStack
#             if len(self.min_stack) > 0 and last == self.min_stack[-1]:
#                 self.min_stack.pop()
#             self.stack.pop()


#     def top(self):
#         """
#         :rtype: int
#         """
#         if len(self.stack) > 0:
#             return self.stack[-1]
#         return None


#     def getMin(self):
#         """
#         :rtype: int
#         """
#         if len(self.min_stack) > 0:
#             return self.min_stack[-1]
#         else:
#             if len(self.stack) > 0:
#                 return self.stack[-1]
#             return None

class MinStack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = []


    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.stack.append(x)
        if len(self.min_stack) == 0:
            self.min_stack.append(x)
            return
        if x <= self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            # Push top of min stack again
            self.min_stack.append(self.min_stack[-1])


    def pop(self):
        """
        :rtype: nothing
        """
        if len(self.stack) > 0:
            # Much simple than solution 1
            # But use more space
            self.min_stack.pop()
            self.stack.pop()


    def top(self):
        """
        :rtype: int
        """
        if len(self.stack) > 0:
            return self.stack[-1]
        return None


    def getMin(self):
        """
        :rtype: int
        """
        if len(self.min_stack) > 0:
            return self.min_stack[-1]
        return None

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    # def hasCycle(self, head):
    #     """
    #     :type head: ListNode
    #     :rtype: bool
    #     """
    #     # Add max and check if reach max
    #     if head is None:
    #         return False
    #     count = 0
    #     max = 100000
    #     pos = head
    #     while pos is not None:
    #         count += 1
    #         pos = pos.next
    #         if count > max:
    #             return True
    #     return False

    # def hasCycle(self, head):
    #     # Hash or set
    #     dic = {}
    #     pos = head
    #     while pos is not None:
    #         try:
    #             dic[pos]
    #             return True
    #         except KeyError:
    #             dic[pos] = pos
    #         pos = pos.next
    #     return False

    def hasCycle(self, head):
        # Two points
        try:
            fast = head.next.next
            slow = head.next

            while fast != slow:
                fast = fast.next.next
                slow = slow.next

            return True
        except:
            return False

class Solution:

    # def binaryGap(self, n: int) -> int:
    #     # Store index
    #     A = [i for i in xrange(32) if (N >> i) & 1]
    #     if len(A) < 2: return 0
    #     return max(A[i+1] - A[i] for i in xrange(len(A) - 1))


    def binaryGap(self, n: int) -> int:
        # one pass and store max
        current = 1
        last1 = -1
        out = 0
        while n > 0:
            if n % 2 == 1:
                if last1 >= 1:
                    out = max(out, current - last1)
                last1 = current
            current += 1
            n = n // 2
        return out
    
    # def binaryGap(self, n: int) -> int:
    #     # one pass and store max
    #     res = 0
    #     last = -1
    #     # Get binary encoding with bin
    #     for i, curr in enumerate(bin(n)[2:]):
    #         if curr == '1':
    #             if last >= 0:
    #                 res = max(res, i - last)
    #             last = i
    #     return res

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack = []
        for t in tokens:
            try:
                temp = int(t)
                stack.append(temp)
            except:
                b = stack.pop()
                a = stack.pop()
                if t == "+":
                    a += b
                elif t == "-":
                    a -= b
                elif t == "*":
                    a *= b
                else:
                    a = int(a * 1.0 / b)
                stack.append(a)
        return stack[-1]

class Solution {
    public int maximum69Number (int num) {
        // Replace first 6 with 9 if exists
        return Integer.valueOf(String.valueOf(num).replaceFirst("6", "9"));
    }

    /*
    public int maximum69Number (int num) {
        char[] chars = Integer.toString(num).toCharArray();
        // Replace first 6 with 9 if exists
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '6') {
                chars[i] = '9';
                break;
            }
        }
        return Integer.parseInt(new String(chars));
    }*/
}

class Solution(object):
#     def topKFrequent(self, words, k):
#         """
#         :type words: List[str]
#         :type k: int
#         :rtype: List[str]
#         """
#         counter = collections.Counter(words)
#         res = sorted(counter.items(), cmp=cmp_frequency, reverse=True)
#         return [k for k, _ in res[:k]]

# def cmp_frequency(x, y):
#     if x[1] != y[1]:
#         return cmp(x[1], y[1])
#     return cmp(y[0], x[0])

    # def topKFrequent(self, words, k):
    #     count = collections.Counter(words)
    #     candidates = count.keys()
    #     candidates.sort(key = lambda w: (-count[w], w))
    #     return candidates[:k]

    def topKFrequent(self, words, k):
        count = collections.Counter(words)
        # Note that python heapq only support min heap
        # So, we can make the value negative to create a max heap
        heap = [(-freq, word) for word, freq in count.items()]
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for _ in xrange(k)]

class Solution(object):
    # https://discuss.leetcode.com/topic/17639/20ms-detailed-explained-c-solutions-o-n-space/2
    # def minDistance(self, word1, word2):
    #     """
    #     :type word1: str
    #     :type word2: str
    #     :rtype: int
    #     """
    #     ls_1, ls_2 = len(word1), len(word2)
    #     dp = [[0] * (ls_2 + 1) for _ in range(ls_1 + 1)]
    #     for i in range(1, ls_1 + 1):
    #         dp[i][0] = i
    #     for j in range(1, ls_2 + 1):
    #         dp[0][j] = j
    #     for i in range(1, ls_1 + 1):
    #         for j in range(1, ls_2 + 1):
    #             if word1[i - 1] == word2[j - 1]:
    #                 dp[i][j] = dp[i - 1][j - 1]
    #             else:
    #                 dp[i][j] = min(dp[i - 1][j - 1] + 1,
    #                                dp[i][j - 1] + 1,
    #                                dp[i - 1][j] + 1)
    #     return dp[ls_1][ls_2]

    def minDistance(self, word1, word2):
        ls_1, ls_2 = len(word1), len(word2)
        dp = list(range(ls_1 + 1))
        for j in range(1, ls_2 + 1):
            pre = dp[0]
            dp[0] = j
            for i in range(1, ls_1 + 1):
                temp = dp[i]
                if word1[i - 1] == word2[j - 1]:
                    dp[i] = pre
                else:
                    dp[i] = min(pre + 1, dp[i] + 1, dp[i - 1] + 1)
                pre = temp
        return dp[ls_1]
    

    if __name__ == '__main__':
    # begin
    s = Solution()
    print (s.minDistance("horse","ros"))        
    print (s.minDistance("intention","execution"))        

# class Logger(object):

#     def __init__(self):
#         """
#         Initialize your data structure here.
#         """
#         self.timestamps = {}

#     def shouldPrintMessage(self, timestamp, message):
#         """
#         Returns true if the message should be printed in the given timestamp, otherwise returns false.
#         If this method returns false, the message will not be printed.
#         The timestamp is in seconds granularity.
#         :type timestamp: int
#         :type message: str
#         :rtype: bool
#         """
#         if timestamp < self.timestamps.get(message, 0):
#             return False
#         self.timestamps[message] = timestamp + 10
#         return True


import heapq


class Logger(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.heap = []
        self.cache = {}

    def shouldPrintMessage(self, timestamp, message):
        """
        Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity.
        :type timestamp: int
        :type message: str
        :rtype: bool
        """
        while len(self.heap):
            if self.heap[0][0] <= timestamp:
                temp = heapq.heappop(self.heap)
                self.cache.pop(temp[1])
            else:
                break
        if timestamp < self.cache.get(message, 0):
            return False
        self.cache[message] = timestamp + 10
        heapq.heappush(self.heap, (timestamp + 10, message))
        return True


# Your Logger object will be instantiated and called as such:
# obj = Logger()
# param_1 = obj.shouldPrintMessage(timestamp,message)

public class Solution {
    /*public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.length; start++) {
            int sum = 0;
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];
                if (sum == k)
                    count++;
            }
        }
        return count;
    }*/
    public int subarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        HashMap < Integer, Integer > map = new HashMap < > ();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            // check if sum - k in hash
            if (map.containsKey(sum - k))
                count += map.get(sum - k);
            // push sum into hash
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    # https://leetcode.com/problems/diameter-of-binary-tree/solution/
    def diameterOfBinaryTree(self, root):
        self.ans = 1
        def depth(node):
            if not node: return 0
            L = depth(node.left)
            R = depth(node.right)
            self.ans = max(self.ans, L+R+1)
            return max(L, R) + 1

        depth(root)
        # number of nodes - 1 = length
        return self.ans - 1

class TwoSum(object):

    def __init__(self):
        """
        initialize your data structure here
        """
        self.internal = []
        self.dic = {}

    def add(self, number):
        """
        Add the number to an internal data structure.
        :rtype: nothing
        """
        self.internal.append(number)
        if number in self.dic:
            # more than once
            self.dic[number] = True
            return
        # once
        self.dic[number] = False

    def find(self, value):
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        :type value: int
        :rtype: bool
        """
        for v in self.internal:
            if value - v in self.dic:
                if v << 1 == value and not self.dic[v]:
                    continue
                return True
        return False


# Your TwoSum object will be instantiated and called as such:
# twoSum = TwoSum()
# twoSum.add(number)
# twoSum.find(value)

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 1; i < n; i++) {
            // left part
            res[i] = res[i - 1] * nums[i - 1];
        }
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= right;
            // right part
            right *= nums[i];
        }
        return res;
    }
}

class Solution {
    /* public int missingNumber(int[] nums) {
        int n = nums.length;
        int total = n * (n + 1) / 2;
        for (int i = 0; i < nums.length; i++) {
            total -= nums[i];
        }
        return total;
    } */

    public int missingNumber(int[] nums) {
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            res ^= i;
            res ^= nums[i];
        }
        return res;
    }

    /* public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > mid) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    } */
}

class Solution(object):
    # def numWays(self, n, k):
    #     """
    #     :type n: int
    #     :type k: int
    #     :rtype: int
    #     """
    #     w = [0, k, k*k]
    #     while len(w) <= n:
    #         w += sum(w[-2:]) * (k-1),
    #     return w[n]
    def numWays(self, n, k):
        if n == 0:
            return 0
        elif n == 1:
            return k
        # two step dp
        # ways[1] = k
        # ways[2] = k * k
        # ways[i>2] = (ways[i-1] + ways[i-2]) * (k - 1)
        dp = [0] * 2
        dp[0] = k
        dp[1] = k * k
        for i in range(2, n):
            temp = dp[1]
            dp[1] = sum(dp) * (k - 1)
            dp[0] = temp
        return dp[1]

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        # BFS with queue
        direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        m = len(rooms)
        if m == 0:
            return
        n = len(rooms[0])
        q = []
        for row in range(m):
            for col in range(n):
                # gate
                if rooms[row][col] == 0:
                    q.append((row, col))

        while len(q) > 0:
            point = q.pop(0)
            row, col = point[0], point[1]
            for d in direction:
                r = row + d[0]
                c = col + d[1]
                # wall or out of rooms
                if r < 0 or c < 0 or r >= m or c >= n or rooms[r][c] != 2147483647:
                    continue
                rooms[r][c] = rooms[row][col] + 1
                q.append((r, c))

import itertools as it
 class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        return list(it.ifilter(lambda x: sum(x) == n, list(it.combinations(range(1, 10), k))))

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        curr = 0
        for n in nums:
            if n == 1:
                # Add 1 to curr when encounter 1
                curr += 1
                if curr > ans:
                    ans = curr
            else:
                # Add 1 to curr when encounter 1
                curr = 0
        return ans

class Solution(object):
    # def maxSubArray(self, nums):
    #     return self.maxSubArrayHelper(nums, 0, len(nums) - 1)
    #
    # def maxSubArrayHelper(self, nums, l, r):
    #     if l > r:
    #         return -2147483647
    #     mid = (l + r) / 2
    #     leftAns = self.maxSubArrayHelper(nums, l, mid - 1)
    #     rightAns = self.maxSubArrayHelper(nums, mid + 1, r)
    #     lMaxSum = res = 0
    #     for i in range(mid - 1, l -1, -1):
    #         res += nums[i]
    #         lMaxSum = max(res, lMaxSum)
    #     rMaxSum = res = 0
    #     for i in range(mid + 1, r + 1):
    #         res += nums[i]
    #         rMaxSum = max(res, rMaxSum)
    #     return max(lMaxSum + nums[mid] + rMaxSum, max(leftAns, rightAns))

    # def maxSubArray(self, nums):
    #     """
    #     :type nums: List[int]
    #     :rtype: int
    #     """
    #     ls = len(nums)
    #     start = [0] * ls
    #     all = [0] * ls
    #     start[-1], all[-1] = nums[-1], nums[-1]
    #     for i in reversed(range(ls - 1)):
    #         start[i] = max(nums[i], nums[i] + start[i + 1])
    #         all[i] = max(start[i], all[i + 1])
    #     return all[0]

    # def maxSubArray(self, nums):
    #     ls = len(nums)
    #     start, all = nums[-1], nums[-1]
    #     for i in reversed(range(ls - 1)):
    #         start = max(nums[i], nums[i] + start)
    #         all = max(start, all)
    #     return all

    def maxSubArray(self, nums):
        maxEndingHere = maxSofFar = nums[0]
        for i in range(1, len(nums)):
            maxEndingHere = max(maxEndingHere + nums[i], nums[i])
            maxSofFar = max(maxEndingHere, maxSofFar)
        return maxSofFar

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    # def copyRandomList(self, head):
    #     """
    #     :type head: RandomListNode
    #     :rtype: RandomListNode
    #     """
    #     # hash O(n) and O(n)
    #     dic = collections.defaultdict(lambda: RandomListNode(0))
    #     dic[None] = None
    #     n = head
    #     while n:
    #         dic[n].label = n.label
    #         dic[n].next = dic[n.next]
    #         dic[n].random = dic[n.random]
    #         n = n.next
    #     return dic[head]

    # def copyRandomList(self, head):
    #     # hash O(n) and O(n)
    #     dic = {}
    #     dic[None] = None
    #     dummyHead = RandomListNode(0)
    #     p, q = head, dummyHead
    #     while p is not None:
    #         q.next = RandomListNode(p.label)
    #         dic[p] = q.next
    #         p = p.next
    #         q = q.next
    #     p, q = head, dummyHead
    #     while p is not None:
    #         q.next.random = dic[p.random]
    #         p = p.next
    #         q = q.next
    #     return dummyHead.next

    def copyRandomList(self, head):
        # Modify original structure: Original->Copy->Original->Copy
        # node.next.random = node.random.next
        # O(n) and O(1)
        p = head
        while p is not None:
            next = p.next
            copy = RandomListNode(p.label)
            p.next = copy
            copy.next =  next
            p = next
        p = head
        while p is not None:
            if p.random is not None:
                p.next.random = p.random.next
            p = p.next.next
        p = head
        if p is not None:
            headCopy = p.next
        else:
            headCopy = None
        while p is not None:
            copy = p.next
            p.next = copy.next
            p = p.next
            if p is not None:
                copy.next = p.next
        return headCopy

class Solution(object):
    # def singleNumber(self, nums):
    #     """
    #     :type nums: List[int]
    #     :rtype: int
    #     """
    #     # hash
    #     dic = {}
    #     for num in nums:
    #         try:
    #             dic[num] += 1
    #         except KeyError:
    #             dic[num] = 1
    #     for num in nums:
    #         if dic[num] == 1:
    #             return num

    # def singleNumber(self, nums):
    #     # set
    #     s = set()
    #     for num in nums:
    #         if num in s:
    #             s.remove(num)
    #         else:
    #             s.add(num)
    #     return s.pop()

    def singleNumber(self, nums):
        # xor
        res = 0
        for num in nums:
            res ^= num
        return res

class Solution(object):
    # def findMin(self, nums):
    #     """
    #     :type nums: List[int]
    #     :rtype: int
    #     """
    #     return self.get_min(nums, 0, len(nums) - 1)

    # def get_min(self, nums, start, end):
    #     mid = (start + end) / 2
    #     if start == end:
    #         # one element
    #         return nums[start]
    #     if mid == start or mid == end:
    #         # two element
    #         return min(nums[start], nums[end])
    #     if nums[mid] < nums[end]:
    #         # right side sorted
    #         if nums[mid] > nums[start]:
    #             # not rotated
    #             return nums[start]
    #         return self.get_min(nums, start, mid)
    #     elif nums[mid] > nums[end]:
    #         # left side sorted
    #         return self.get_min(nums, mid, end)
    #     else:
    #         # cannot judge which direction is sorted
    #         return min(self.get_min(nums, start, mid), self.get_min(nums, mid, end))

    # def findMin(self, nums):
    #     start, end = 0, len(nums) - 1
    #     while start < end:
    #         mid = (start + end) / 2
    #         if nums[mid] > nums[end]:
    #             start = mid + 1
    #         elif nums[mid] < nums[end]:
    #             end = mid
    #         else:
    #             end -= 1
    #     return nums[start]


    def findMin(self, nums):
        l, r = 0, len(nums) - 1
        while l < r and nums[l] >= nums[r]:
            mid = (l + r) / 2
            if nums[mid] > nums[r]:
                l = mid + 1
            elif nums[mid] < nums[l]:
                r = mid
            else:
                # nums[l] = nums[r] = nums[mid]
                l += 1
        return nums[l]

class Solution(object):
    # def fizzBuzz(self, n):
    #     """
    #     :type n: int
    #     :rtype: List[str]
    #     """
    #     res = []
    #     for i in range(1, n + 1):
    #         if i % 3 == 0:
    #             if i % 5 == 0:
    #                 res.append('FizzBuzz')
    #             else:
    #                 res.append('Fizz')
    #         elif i % 5 == 0:
    #             res.append('Buzz')
    #         else:
    #             res.append(str(i))
    #     return res

    # def fizzBuzz(self, n):
    #     """
    #     :type n: int
    #     :rtype: List[str]
    #     """
    #     res = []
    #     for i in range(1, n + 1):
    #         curr = ''
    #         if i % 3 == 0:
    #             curr += 'Fizz'
    #         if i % 5 == 0:
    #             curr += 'Buzz'
    #         if not len(curr):
    #             curr += str(i)
    #         res.append(curr)
    #     return res

    def fizzBuzz(self, n):
        return [str(i) * (i % 3 != 0 and i % 5 != 0) + "Fizz" * (i % 3 == 0) + "Buzz" * (i % 5 == 0) 
                for i in range(1, n + 1)]
    
    # def fizzBuzz(self, n):
    #     return ['Fizz' * (not i % 3) + 'Buzz' * (not i % 5) or str(i) for i in range(1, n+1)]

class Solution {
    /* public int[] sortedSquares(int[] A) {
        int[] res = new int[A.length];
        for (int i = 0; i < A.length; ++i)
            res[i] = A[i] * A[i];

        Arrays.sort(res);
        return res;
    } */
    public int[] sortedSquares(int[] A) {
        int pos = 0;
        int[] res = new int[A.length];
        int curr = 0;
        while (pos < A.length && A[pos] < 0) pos++;
        int npos = pos - 1;
        while (pos < A.length && npos >= 0) {
            if (A[pos] * A[pos] < A[npos] * A[npos]) {
                res[curr++] = A[pos] * A[pos];
                pos++;
            } else {
                res[curr++] = A[npos] * A[npos];
                npos--;
            }
        }
        while (npos >= 0) {
            res[curr++] = A[npos] * A[npos];
            npos--;
        }
        while (pos < A.length) {
            res[curr++] = A[pos] * A[pos];
            pos++;
        }
        return res;
    }
}

// Source : https://leetcode.com/problems/count-primes/

/********************************************************************************** 
 * 
 * Description:
 * Count the number of prime numbers less than a non-negative number, n.
 * 
 * Credits:Special thanks to @mithmatt for adding this problem and creating all test cases.
 * 
 *   Let's start with a isPrime function. To determine if a number is prime, we need to check if 
 *   it is not divisible by any number less than n. The runtime complexity of isPrime function 
 *   would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?
 *   
 *   As we know the number must not be divisible by any number > n / 2, we can immediately cut the total 
 *   iterations half by dividing only up to n / 2. Could we still do better?
 *   
 *   Let's write down all of 12's factors:
 * 
 * 	2 × 6 = 12
 * 	3 × 4 = 12
 * 	4 × 3 = 12
 * 	6 × 2 = 12
 * 
 * As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider 
 * factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.
 * 
 * Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach?
 * 
 *	public int countPrimes(int n) {
 *	   int count = 0;
 *	   for (int i = 1; i < n; i++) {
 *	      if (isPrime(i)) count++;
 *	   }
 *	   return count;
 *	}
 *	
 *	private boolean isPrime(int num) {
 *	   if (num <= 1) return false;
 *	   // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
 *	   // to avoid repeatedly calling an expensive function sqrt().
 *	   for (int i = 2; i * i <= num; i++) {
 *	      if (num % i == 0) return false;
 *	   }
 *	   return true;
 *	}
 *   
 *   The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. 
 *   But don't let that name scare you, I promise that the concept is surprisingly simple.
 *
 *	[Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
 * 
 *	[https://leetcode.com/static/images/solutions/Sieve_of_Eratosthenes_animation.gif]
 *	[http://commons.wikimedia.org/wiki/File:Sieve_of_Eratosthenes_animation.gif]
 *
 *   Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation"() 
 *   by SKopp is licensed under CC BY 2.0.
 *
 *      * [Skoop](http://de.wikipedia.org/wiki/Benutzer:SKopp)
 *	* [CC BY 2.0](http://creativecommons.org/licenses/by/2.0/)
 * 
 * We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2 
 * must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, 
 * all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well. 
 * Now we look at the next number, 4, which was already marked off. What does this tell you? Should you 
 * mark off all multiples of 4 as well?
 *   
 * 4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible 
 * by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, 
 * all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off. 
 * There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?
 *   
 * In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off 
 * by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current 
 * number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, ... 
 * Now what should be the terminating loop condition?
 *   
 * It is easy to say that the terminating loop condition is p n, which is certainly correct but not efficient. 
 * Do you still remember Hint #3?
 *   
 * Yes, the terminating loop condition can be p n, as all non-primes ≥ √n must have already been marked off. 
 * When the loop terminates, all the numbers in the table that are non-marked are prime.
 * 
 * The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). 
 * For the more mathematically inclined readers, you can read more about its algorithm complexity on 
 * [Wikipedia](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity).
 * 
 *	public int countPrimes(int n) {
 *	   boolean[] isPrime = new boolean[n];
 *	   for (int i = 2; i < n; i++) {
 *	      isPrime[i] = true;
 *	   }
 *	   // Loop's ending condition is i * i < n instead of i < sqrt(n)
 *	   // to avoid repeatedly calling an expensive function sqrt().
 *	   for (int i = 2; i * i < n; i++) {
 *	      if (!isPrime[i]) continue;
 *	      for (int j = i * i; j < n; j += i) {
 *	         isPrime[j] = false;
 *	      }
 *	   }
 *	   int count = 0;
 *	   for (int i = 2; i < n; i++) {
 *	      if (isPrime[i]) count++;
 *	   }
 *	   return count;
 *	}
 *   
 *               
 **********************************************************************************/

#include 
#include 
#include 
using namespace std;

int countPrimes(int n)
{
    vector isPrimer(n, true);

    for (int i = 2; i * i < n; i++)
    {
        if (isPrimer[i])
        {
            for (int j = i * i; j < n; j += i)
            {
                isPrimer[j] = false;
            }
        }
    }

    int cnt = 0;
    for (int i = 2; i < n; i++)
    {
        if (isPrimer[i])
        {
            //cout << i << ", ";
            cnt++;
        }
    }
    return cnt;
}

int main(int argc, char **argv)
{
    int n = 100;
    if (argc > 1)
    {
        n = atoi(argv[1]);
    }

    cout << endl
         << n << " : " << countPrimes(n) << endl;

    return 0;
}

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        pref = [0]
        # Compute accumulated xor from head
        for e in arr:
            pref.append(e ^ pref[-1])
        ans = []
        # query result equal to xor[0, l] xor x[0, r]
        for [l, r] in queries:
            ans.append(pref[r+1] ^ pref[l])
        return ans

    # def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
    #     for i in range(len(arr) - 1):
    #         arr[i + 1] ^= arr[i]
    #     return [arr[j] ^ arr[i - 1] if i else arr[j] for i, j in queries]

public class Solution {
    /*public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        return Math.max(nums[0] * nums[1] * nums[nums.length - 1], nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3]);
    }*/
    
    public int maximumProduct(int[] nums) {
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for (int n: nums) {
            if (n <= min1) {
                min2 = min1;
                min1 = n;
            } else if (n <= min2) {     // n lies between min1 and min2
                min2 = n;
            }
            if (n >= max1) {            // n is greater than max1, max2 and max3
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (n >= max2) {     // n lies betweeen max1 and max2
                max3 = max2;
                max2 = n;
            } else if (n >= max3) {     // n lies betwen max2 and max3
                max3 = n;
            }
        }
        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}

class Solution(object):
    # def rob(self, nums):
    #     """
    #     :type nums: List[int]
    #     :rtype: int
    #     """
    #     if nums is None or len(nums) == 0:
    #         return 0
    #     ls = len(nums)
    #     dp = [0] * ls
    #     # dp from 0 ~ ls - 2
    #     dp[0] = nums[0]
    #     for i in range(1, ls - 1):
    #         if i < 2:
    #             dp[i] = max(nums[i], dp[i - 1])
    #         else:
    #             dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    #     res = dp[ls - 2]
    #     # dp from 1 ~ ls - 1
    #     dp[0] = 0
    #     for i in range(1, ls):
    #         if i < 2:
    #             dp[i] = max(nums[i], dp[i - 1])
    #         else:
    #             dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    #     return max(res, dp[ls - 1])

    def rob(self, nums):
        if len(nums) == 1:
            return nums[0]
        return max(self.rob_helper(nums, 0, len(nums) - 2),
                   self.rob_helper(nums, 1, len(nums) - 1))


    def rob_helper(self, nums, low, high):
        prevMax = currMax = 0
        for index in range(low, high + 1):
            temp = currMax
            currMax = max(prevMax + nums[index], currMax)
            prevMax = temp
        return currMax

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # use set to check duplicate
        return len(nums) != len(set(nums))

    # def containsDuplicate(self, nums):
    #     nums.sort()
    #     for i in range(len(nums) - 1):
    #         if nums[i] == nums[i + 1]:
    #             return True
    #     return False

class Solution(object):
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        dic = {}
        for c in s:
            dic[c] = dic.get(c, 0) + 1
        odd, even = 0, 0
        for c in dic:
            if dic[c] % 2 == 0:
                even += 1
            else:
                odd += 1
        if odd <= 1:
            return True
        return False