<jupyter_start><jupyter_text>Leetcode december> Solving a problem a day- toc: true - badges: true- comments: true- categories: [jupyter, leetcode, coding interview]- image: images/chart-preview.png  Setting up your environment for debugging![](https://miro.medium.com/max/700/1*NP0bYBdrhwgpJpKDhPLWrQ.gif)Setting up your debugger in jupyter is as easy as running two commandsThe debugger front-end can be installed as a JupyterLab extension.`jupyter labextension install @jupyterlab/debugger`The only kernel with debugging support, for now, is `xeus-python` a new Jupyter kernel for the Python programming language`conda install xeus-python -c conda-forge`more details on jupyter debugging: https://blog.jupyter.org/a-visual-debugger-for-jupyter-914e61716559  write some helper functions<jupyter_code>def testeq(want, meth, arg):
    """
    params:
        want - what we want
        meth - method of class instance, as Solution().meth
        arg  - arg to pass as Solution.meth(arg)
    
    """
    got = meth(arg)
    if got != want:
        raise ValueError(f"Got: {got}, want: {want}")<jupyter_output><empty_output><jupyter_text>Utils<jupyter_code># Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
    def __repr__v1(self):
        return self.val
    
    def __repr__(self):
        vl = 'none' if self.left is None else self.left.val
        vr = 'none' if self.right is None else self.right.val
        return f"{vl} <- {self.val} -> {vr}"
        
    def __repr__v2(self):
        vl = 'none' if self.left is None else self.left.val
        vr = 'none' if self.right is None else self.right.val
        return f"""
    {self.val}
  /   \      
{vl}    {vr}
"""



from typing import List, Union, Iterable

class TreeNodeBuilder:
    """Usage:
    t = TreeNodeBuilder()
    node = t([2,1,3])
    """
    def __init__(self, ):
        pass
    
        
    def better_next(self, iterable:Iterable):
        try:
            return next(iterable)
        except StopIteration:
            return None
        
    def build(self, node:TreeNode):
        vl = self.better_next(self.vals)
        vr = self.better_next(self.vals)
        
        if vl is not None: node.left = TreeNode(vl)
        if vr is not None: node.right = TreeNode(vr)
            
        if vl is not None: self.build(node.left)
        if vr is not None: self.build(node.right)
            
    def __call__(self, root:List[Union[int, None]]):
        self.vals = iter(root)
        node = TreeNode(val=next(self.vals))
        self.build(node)
        
        return node<jupyter_output><empty_output><jupyter_text>week 1 problem 1: two-sumhttps://leetcode.com/problems/two-sumGiven an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order. Example 1:```Input: nums = [2,7,11,15], target = 9Output: [0,1]Output: Because nums[0] + nums[1] == 9, we return [0, 1].```Example 2:```Input: nums = [3,2,4], target = 6Output: [1,2]```Example 3:```Input: nums = [3,3], target = 6Output: [0,1]``` Constraints:```2 <= nums.length <= 103-109 <= nums[i] <= 109-109 <= target <= 109Only one valid answer exists.``` There are two solutions: brute (loop over all candidates) and lookup.However, we use smart brute: after we checked candidate for **Left** (`idx_l`), we can be sure that all possible matching **right** are to the right. So instead of `for idx_r in range(0, len(nums))`, we can use `for idx_r in range(idx_l+1, len(nums))`> Note: Thanks to our smart trick, both solutions are nearly identical in python in terms of time/memory<jupyter_code>#collapse_show
from typing import List
class Solution:
    def twoSumBrute(self, nums: List[int], target: int) -> List[int]:
        for idx_l in range(len(nums)):
            for idx_r in range(idx_l+1, len(nums)):
                if nums[idx_l] + nums[idx_r] == target:
                    return idx_l, idx_r
                
    def twoSumLookupOnePass(self, nums: List[int], target: int) -> List[int]:
        lookup = {}
        for i, v in enumerate(nums):
            if target - v in lookup:
                return i, lookup[target - v]
            lookup[v] = i
        raise ValueError('Two sums target not in list.')<jupyter_output><empty_output><jupyter_text>2020-12-01 | problem 2 | add-two-numbershttps://leetcode.com/problems/add-two-numbers/Details:* Runtime: 72 ms, faster than 49.79% of Python3 online submissions for Add Two Numbers.* Memory Usage: 14.3 MB, less than 21.33% of Python3 online submissions for Add Two Numbers.<jupyter_code>from typing import List

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
    def tolist(self) -> List[int]:
        res = list()
        current = self
        while True:
            res.append(current.val)
            if current.next is None:
                return res
            else:
                current = current.next
        
    def __repr__(self):
        return str(self.tolist())
    
def ListNodeFromList(lst, vrb=False):
    ln = ListNode()
    
    current = ln
    for i,v in enumerate(lst, start=1):
        if vrb: print(v)
        current.val = v
        
        if i == len(lst):
            return ln
        current.next = ListNode()
        current = current.next
    
    raise Exception("Should not run")
def number_from_ListNode(list_node, vrb=False):
    number = 0
    current = list_node

    multiple = 1
    while True:
        number += current.val*multiple
        if current.next is None:
            return number
            
        if vrb: print(multiple, current.val, number)
        current = current.next
        multiple *= 10
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        int1 = number_from_ListNode(l1)
        int2 = number_from_ListNode(l2)
        new_num = int1+int2
        new_list = [int(x) for x in list(str(new_num))]
        #print(new_list[::-1])
        return ListNodeFromList(new_list[::-1])
    
    def run_example(self, input_1: List[int], input_2: List[int]):
        l1, l2 = ListNodeFromList(input_1), ListNodeFromList(input_2)
        return self.addTwoNumbers(l1, l2)
Solution().run_example([2,4,3], [5,6,4])
Solution().run_example([0], [0])
Solution().run_example([9,9,9,9,9,9,9], [9,9,9,9])<jupyter_output><empty_output><jupyter_text>Maximum Depth of Binary Treehttps://leetcode.com/explore/challenge/card/december-leetcoding-challenge/569/week-1-december-1st-december-7th/3551/Details:* Runtime: 72 ms, faster than 49.79% of Python3 online submissions for Add Two Numbers.* Memory Usage: 14.3 MB, less than 21.33% of Python3 online submissions for Add Two Numbers.<jupyter_code># Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
    def __repr__(self):
        vl = 'none' if self.left is None else self.left.val
        vr = 'none' if self.right is None else self.right.val
        return f"""
    {self.val}
  /   \      
{vl}    {vr}
"""
        
        
class Solution: 
    def maxDepthDeque(self, root: TreeNode) -> int:
            queue, count = deque([root]), 0
            if not root: return count

            while queue:
                cur_len = len(queue)
                while cur_len:
                    cur = queue.popleft()
                    if cur.left: queue.append(cur.left)
                    if cur.right: queue.append(cur.right)
                    cur_len -= 1
                count += 1
            return count
        
    def maxDepthRec(self, node): 
        if node is None: 
            return 0

        else : 

            # Compute the depth of each subtree 
            lDepth = self.maxDepthRec(node.left) 
            rDepth = self.maxDepthRec(node.right) 

            # Use the larger one 
            if (lDepth > rDepth): 
                return lDepth+1
            else: 
                return rDepth+1
null = None
root = [1,2,3,4,5,null,null,null,null,6,7,8,9]
root = [3,9,20,null,null,15,7]
vals = iter(root)
global node
node = TreeNode(val=next(vals))
def better_next(iterable):
    try:
        return next(iterable)
    except StopIteration:
        return None
def build(node:TreeNode):
    vl = better_next(vals)
    vr = better_next(vals)

    if vl: node.left = TreeNode(vl)
    if vr: node.right = TreeNode(vr)
        
    if vl: build(node.left)
    if vr: build(node.right)
build(node)
node<jupyter_output><empty_output><jupyter_text>Linked List Random Nodehttps://leetcode.com/explore/challenge/card/december-leetcoding-challenge/569/week-1-december-1st-december-7th/3552/**Performance**: Your runtime beats 47.34 % of python3 submissions.> Note: Faster solutions populate a list and the choose randomly from it. Below is the fastest implementation using a fixed amount of memory**Problem definition**:Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.**Follow up:**What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?**Example:**```// Init a singly linked list [1,2,3].ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);Solution solution = new Solution(head);// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.solution.getRandom();```<jupyter_code># Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
    def __repr__(self):
        return f"{self.val}, {type(self.next)}"
        
    def show_all(self):
        res = list()
        current = self
        
        while True:
            res.append(current.val)
            current = current.next
            if current is None:
                return res
import random
class Solution:

    def __init__(self, head: ListNode):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        """
        self.head = head
        
    def depth(self) -> int:
        """
        return linked list's depth
        """
        cntr = 0
        current = self.head

        while True:
            cntr += 1
            if current.next is None:
                return cntr
            current = current.next
        
    def get_val(self, idx:int) -> int:
        """
        @param idx The index of node to get value from
        """
        cntr = 0
        current = self.head

        while True:
            if cntr==idx:
                return idx, current.val

            cntr += 1
            if current.next is None:
                raise ValueError(f"idx={idx} is larger than linked list size of {cntr}")
            current = current.next

    def getRandom(self) -> int:
        """
        Returns a random node's value.
        """
        
        n = self.depth()
        idx_rand = random.randint(1, n)-1
        idx, val = self.get_val(idx_rand)
        assert idx_rand == idx
        return val
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = ListNode(6)
head.show_all()
obj = Solution(head)
# sample 50k times and make sure that it's random

import pandas as pd
pd.Series([obj.getRandom() for _ in range(50_000)]).value_counts(normalize=True).sort_index().round(2)<jupyter_output><empty_output><jupyter_text>The kth Factor of nhttps://leetcode.com/submissions/detail/427084666/?from=explore&item_id=3554** results**:Your runtime beats 87.17 % of python3 submissions.Your memory usage beats 34.67 % of python3 submissions.Not the best result for memory, but very readable** problem: **Given two positive integers n and k.A factor of an integer n is defined as an integer i where n % i == 0.Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors. Example 1:Input: n = 12, k = 3Output: 3Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.Example 2:Input: n = 7, k = 2Output: 7Explanation: Factors list is [1, 7], the 2nd factor is 7.Example 3:Input: n = 4, k = 4Output: -1Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.Example 4:Input: n = 1, k = 1Output: 1Explanation: Factors list is [1], the 1st factor is 1.Example 5:Input: n = 1000, k = 3Output: 4Explanation: Factors list is [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000]. Constraints:1 <= k <= n <= 1000<jupyter_code>def candidates_generator(n):
    # when we reach n//2, it should be multiplied by minimum of 2, so no point in
    # iterating past n//2
    for candidate in range(1, n//2+1):
        yield candidate
    
    # lastly, yield n itself as a candidate
    yield n

class Solution:
    def kthFactor(self, n: int, k: int, verb=False) -> int:
        # ToDo: ADD n istelf as a possible candidate
        idx_factor = 0
        for cnd in candidates_generator(n):
            if n%cnd == 0:
                idx_factor += 1
                if verb: print('\n', idx_factor, cnd, end='')
                if idx_factor == k:
                    if verb: print(" <-- ANSWER", end='') # return
                    return cnd

        if verb: print('\n-1, NO ANSWER')
        return -1

Solution().kthFactor(12, 3, True)
Solution().kthFactor(7, 2, True)
Solution().kthFactor(4, 4, True)
Solution().kthFactor(1, 1, True)
Solution().kthFactor(1000, 3, True)<jupyter_output><empty_output><jupyter_text>can place flowershttps://leetcode.com/explore/challenge/card/december-leetcoding-challenge/569/week-1-december-1st-december-7th/3555/** results**:tbd You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule. Example 1:Input: flowerbed = [1,0,0,0,1], n = 1Output: trueExample 2:Input: flowerbed = [1,0,0,0,1], n = 2Output: false Constraints:1 <= flowerbed.length <= 2 * 104flowerbed[i] is 0 or 1.There are no two adjacent flowers in flowerbed.0 <= n <= flowerbed.length<jupyter_code>from typing import List
class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        raise NotImplementedError
def walk(flowerbed, vrb=False):
    if flowerbed == [0]:
        return 1
    elif flowerbed == [1]:
        return 0
    
    if vrb: print("="*90)
    if vrb: print(flowerbed[0])
        
    new_flowers = 0
    
    # check first spot
    is_plantable = (flowerbed[0] + flowerbed[1]) == 0
    if is_plantable:
        flowerbed[0] = 9
        new_flowers += 1
        
        
    # check middle spots
    for i in range(1, len(flowerbed)-1):
        is_plantable = (flowerbed[i-1] + flowerbed[i] + flowerbed[i+1]) == 0
        if is_plantable:
            flowerbed[i] = 9
            new_flowers += 1
            
        if vrb: print(flowerbed[i], is_plantable)
            
    # check last spot
    is_plantable = (flowerbed[-2] + flowerbed[-1]) == 0
    if is_plantable:
        flowerbed[-1] = 9
        new_flowers += 1
        

    if vrb: print(flowerbed[-1])
    if vrb: print(f"Answer: {new_flowers}")
        
    return new_flowers

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        return n <= walk(flowerbed)
assert walk([0]) == 1
assert walk([1]) == 0
assert walk([0,1,0]) == 0
assert walk([0,0,0,0,0,1]) == 2
assert walk([0,0,0,1]) == 1
assert walk([0,0,0,1,0,0]) == 2
assert walk([0,0,0,1,0,0,1]) == 1
assert walk([1,0,0,1]) == 0
assert walk([1,0,0,0,0]) == 2

assert walk([1,0,0,0,0,1]) == 1
assert walk([1,0,0,0,0,0]) == 2

assert walk([1,0,1,0,0,1]) == 0

assert walk([1,0,1,0,0,0]) == 1

assert walk([1,0,0,0,1,0]) == 1<jupyter_output><empty_output><jupyter_text>week 2  Pairs of Songshttps://leetcode.com/explore/challenge/card/december-leetcoding-challenge/570/week-2-december-8th-december-14th/3559/<jupyter_code>big_time = [186,128,261,78,60,131,448,42,37,123,313,399,368,173,268,440,314,369,135,101,220,299,81,210,217,411,287,265,211,53,382,3,118,301,415,107,266,212,434,488,332,409,194,122,369,293,444,448,491,356,91,405,49,101,22,239,188,94,450,82,49,110,24,187,443,425,13,115,283,27,402,411,267,249,356,335,134,319,200,319,288,480,451,200,151,330,292,457,235,451,422,174,230,209,418,405,97,310,143,432,117,225,197,365,454,124,61,130,300,327,356,13,333,27,332,388,81,24,165,22,34,479,345,161,436,278,5,182,110,319,278,384,19,385,381,33,262,312,499,415,222,369,197,364,315,112,213,71,263,457,171,285,242,216,485,453,182,449,300,45,320,241,177,234,237,359,116,59,106,231,465,287,361,98,178,294,461,232,474,144,133,164,233,23,186,196,233,348,109,67,427,174,306,185,188,298,328,127,157,296,18,156,163,217,371,61,91,370,271,341,183,328,168,14,39,494,406,90,53,273,151,67,354,241,324,380,215,345,178,77,341,99,482,279,177,69,234,118,65,101,409,89,120,277,431,145,486,408,206,239,474,120,74,137,374,450,74,369,79,349,85,142,414,452,239,93,308,111,225,333,274,157,240,199,462,221,118,499,301,37,87,161,391,417,290,182,6,78,169,180,411,41,225,329,323,63,251,337,163,499,36,215,64,260,439,460,232,255,117,348,200,83,492,182,60,129,425,80,314,152,40,418,259,414,120,478,44,92,448,167,482,138,28,467,98,249,446,298,326,8,93,14,379,424,25,166,297,179,389,325,346,96,63,334,275,33,252,162,29,188,430,383,349,27,220,277,185,497,13,271,145,482,233,495,334,27,346,327,207,291,133,381,139,351,183,368,420,259,44,488,171,18,275,266,205,143,172,321,43,266,437,106,123,363,349,422,78,340,316,455,208,270,313,354,151,495,290,316,424,363,252,40,361,203,125,238,73,452,12,104,254,98,144,476,178,374,101,7,414,455,362,165,74,378,149,110,61,402,110,250,150,341,129,46,179,277,371,129,429,440,69,309,138,212,465,407,418,248,426,386,462,441,164,337,341,85,106,72,170,188,203,367,171,310,457,479,49,362,257,207,97,490,105,264,401,13,485,385,77,127,203,416,267,401,170,495,335,411,3,448,363,275,43,338,341,485,494,237,464,437,208,126,130,231,46,289,201,315,153,109,77,153,60,228,464,195,165,320,14,454,260,170,57,61,484,463,270,494,104,110,439,390,3,344,423,189,232,213,233,332,294,368,17,177,413,214,445,475,160,307,349,364,349,367,387,1,469,143,140,97,285,250,474,462,62,52,456,90,81,98,393,363,355,108,49,232,131,46,182,190,175,436,432,296,283,174,150,47,450,341,111,122,367,131,61,164,345,71,222,129,47,71,489,61,497,299,342,233,405,241,147,7,187,492,400,178,225,111,188,236,11,97,377,362,109,383,141,252,388,67,15,454,305,305,38,160,50,164,26,83,75,198,337,494,98,49,264,398,155,403,295,182,269,187,280,260,247,429,421,218,488,342,69,390,443,457,319,266,276,308,167,93,345,393,331,228,94,33,312,97,366,341,126,183,23,143,151,328,334,257,1,163,444,107,43,44,86,124,172,458,186,485,109,56,468,230,77,79,130,227,16,178,112,197,241,471,177,50,263,79,132,68,53,313,416,486,358,100,1,417,170,141,229,69,126,470,391,162,348,53,59,208,1,157,315,351,213,68,144,271,450,500,371,249,62,390,445,80,280,50,128,21,167,453,175,235,496,433,38,420,199,213,247,338,481,439,146,103,457,220,135,378,450,267,79,380,387,370,150,480,91,175,211,422,349,404,58,452,362,348,129,224,378,96,268,255,150,210,258,166,25,250,353,452,242,164,122,89,464,363,239,390,114,14,139,90,495,137,273,434,148,144,69,38,153,368,485,187,356,52,330,367,301,486,193,200,383,4,462,169,145,47,332,434,246,255,359,48,286,104,316,395,278,15,37,51,116,167,27,432,165,325,378,346,218,429,408,406,295,457,38,54,403,357,274,181,314,34,427,377,361,470,408,370,349,332,429,470,212,164,92,468,63,291,102,324,7,245,264,154,160,217,202,14,489,337,483,97,173,200,483,183,8,326,300,116,420,123,401,67,100,144,354,230,85,136,170,355,160,4,108,220,101,484,255,345,459,372,385,173,126,379,227,468,87,284,404,451,99,500,130,403,144,258,4,478,59,195,371,29,157,497,236,149,275,204,339,33,101,61,300,382,334,145,492,227,46,348,204,389,467,420,471,4,261,5,23,368,198,392,224,2,443,313,397,332,408,91,176,420,44,72,238,257,107,66,29,360,270,183,417,233,75,458,72,16,70,252,138,9,81,199,437,208,24,247,361,377,314,488,342,153,275,169,213,207,196,48,59,72,418,96,318,284,487,118,61,250,47,408,200,88,88,473,262,277,414,303,210,261,396,87,343,248,346,221,228,467,161,61,284,274,382,143,219,232,187,152,443,91,164,35,248,65,351,113,200,184,321,25,411,191,306,85,417,2,137,162,43,450,282,76,94,334,431,480,480,187,67,217,177,357,290,164,139,49,215,75,150,421,99,25,345,323,497,104,107,366,273,2,335,218,244,474,248,496,187,88,382,476,496,52,287,318,475,467,183,230,82,296,328,168,370,84,391,45,32,402,241,420,485,241,103,105,182,173,302,405,420,50,444,304,77,373,253,353,81,92,111,218,378,22,63,442,313,457,345,45,391,67,87,100,37,41,435,350,264,183,469,284,209,122,10,141,314,136,268,439,48,492,479,76,459,191,313,354,153,364,455,440,230,149,378,146,89,240,443,381,66,471,172,193,331,60,472,141,160,126,15,147,74,358,343,101,23,246,80,420,376,182,469,133,346,294,493,343,414,97,267,267,469,273,263,152,76,181,475,335,353,406,142,216,189,222,132,68,184,420,243,217,220,130,324,64,458,409,236,14,135,308,64,43,20,326,326,366,490,356,277,304,251,160,197,157,112,96,417,484,41,108,311,167,276,384,367,194,442,362,404,160,428,102,365,237,495,189,274,302,129,81,228,94,150,480,145,487,11,221,258,156,462,242,114,216,48,40,42,254,166,178,332,159,133,206,206,253,459,238,433,328,91,480,20,327,204,443,365,120,355,120,483,381,432,66,206,244,333,350,30,36,367,88,140,77,299,340,64,124,334,409,149,472,246,174,403,454,243,284,33,75,18,233,373,365,378,484,23,449,310,247,41,312,452,12,424,305,49,408,22,376,262,123,26,227,449,206,479,292,42,491,129,180,362,201,143,7,288,497,443,185,59,50,397,214,81,318,144,419,247,291,416,396,446,131,14,496,280,452,479,411,253,28,490,459,191,250,353,11,254,448,432,351,24,215,13,11,78,474,293,176,405,196,94,345,171,365,495,19,259,376,108,333,420,52,491,369,263,350,183,161,40,465,417,335,486,383,98,102,216,129,270,218,352,335,37,196,459,5,464,116,167,475,164,265,160,478,380,17,352,220,222,162,331,257,170,250,403,296,287,63,386,266,379,255,135,168,83,326,216,116,109,12,235,320,409,440,212,370,297,423,373,149,277,165,290,62,195,14,38,108,32,431,172,17,105,31,14,471,82,258,145,376,175,485,431,427,230,320,152,340,419,487,314,248,412,174,446,118,229,9,20,135,129,237,214,311,279,144,357,317,462,177,379,224,201,326,264,88,335,99,273,213,469,262,92,128,139,14,69,148,3,350,226,391,458,437,385,495,389,28,337,493,145,305,481,133,251,40,356,424,37,100,246,364,235,183,177,396,251,167,477,349,53,186,345,50,128,467,348,361,3,194,369,128,449,192,158,88,105,228,217,186,23,284,107,189,233,438,227,73,407,15,349,220,491,224,312,483,130,67,219,425,145,342,1,480,481,105,189,206,132,315,354,42,489,349,284,68,380,479,18,161,11,33,169,241,170,64,412,354,292,398,290,264,348,53,393,195,277,420,327,86,183,84,300,124,167,245,165,470,383,239,140,303,115,150,410,312,365,146,339,196,219,215,402,448,203,246,118,228,122,250,282,69,238,76,418,257,466,495,371,474,366,109,3,87,92,201,143,205,20,210,287,155,305,346,245,215,302,237,447,199,279,154,325,53,49,281,120,484,225,428,393,40,177,73,42,85,161,377,152,93,56,461,287,153,120,280,158,157,122,390,144,417,324,364,264,392,436,21,30,309,44,298,319,477,41,356,417,474,402,289,393,219,267,118,319,114,375,456,486,200,462,234,241,209,357,28,119,5,188,411,372,412,463,343,90,43,209,108,241,25,168,58,66,399,191,13,48,28,403,66,371,426,278,231,483,403,58,255,159,413,228,88,91,126,247,378,332,172,481,183,8,430,217,254,392,162,91,271,149,273,259,130,7,138,226,487,225,283,352,351,295,490,165,302,82,161,231,464,31,351,473,216,329,173,179,28,494,54,16,114,290,88,411,292,92,48,262,18,447,349,350,103,219,470,433,55,133,96,127,391,47,33,338,100,61,323,149,408,101,357,417,336,343,61,63,361,146,405,99,234,285,474,124,128,99,124,74,62,428,128,331,465,274,452,35,17,437,191,408,382,127,254,458,145,353,460,363,392,495,19,328,169,328,73,207,51,476,328,319,16,472,191,104,253,54,114,324,445,90,441,42,411,94,362,179,491,191,58,416,13,77,332,313,330,175,195,414,25,141,79,328,443,168,375,204,448,182,378,485,439,151,90,29,106,53,80,296,140,185,334,57,93,35,428,227,205,366,202,113,477,338,440,230,317,260,235,406,308,22,37,163,420,476,304,212,487,500,156,474,387,55,316,18,151,86,121,437,423,238,52,4,436,27,471,220,337,145,364,403,219,99,373,452,434,322,13,236,255,104,482,444,132,246,65,68,15,56,193,71,123,257,16,80,348,9,160,394,307,113,112,268,256,95,84,31,375,56,364,51,368,384,330,122,383,104,152,317,385,319,383,229,201,433,218,419,183,67,272,180,496,406,69,330,400,36,13,445,478,190,406,311,44,320,281,104,373,243,485,91,301,186,379,431,385,49,483,379,460,333,34,163,379,224,93,340,185,269,445,28,292,20,177,255,258,216,310,203,193,167,148,410,20,82,10,10,115,454,434,184,219,140,282,181,320,49,156,243,217,191,298,334,252,310,447,116,31,392,473,134,7,262,261,184,65,241,187,125,464,202,331,380,177,386,112,413,215,51,280,273,183,49,46,410,389,109,344,252,478,465,230,461,452,342,113,287,300,105,498,48,55,247,226,181,213,253,149,396,249,125,235,236,420,271,300,21,242,472,434,237,90,262,398,353,387,154,39,234,134,41,479,492,61,476,256,98,499,48,11,295,241,315,144,39,398,209,273,469,412,491,243,139,498,408,136,376,419,55,451,285,386,190,114,315,264,34,475,147,151,320,44,255,63,157,172,267,123,459,251,212,353,23,266,304,391,481,480,192,379,419,386,436,492,314,312,87,178,387,217,413,270,351,244,23,283,48,485,154,54,14,488,177,356,447,107,38,299,3,375,212,84,116,395,120,232,119,32,172,110,41,210,35,170,231,205,148,258,291,289,454,472,453,179,173,189,207,474,71,497,281,396,349,224,145,238,348,338,376,122,424,368,211,36,265,278,72,309,328,263,362,371,138,55,28,101,246,428,171,152,218,25,55,210,305,262,98,411,204,203,413,87,321,29,10,249,75,467,436,63,141,102,282,332,478,285,448,193,242,466,235,76,8,411,366,56,194,190,100,82,121,234,63,338,142,263,188,304,209,154,217,288,358,443,337,118,163,261,355,382,464,78,364,214,419,392,69,27,148,57,238,228,145,195,89,199,403,153,35,29,364,92,202,6,435,47,325,7,400,400,479,135,57,76,281,114,170,75,40,253,309,97,336,24,86,131,363,54,113,420,66,349,391,448,239,327,9,460,177,258,261,124,116,149,483,244,474,225,265,84,359,165,27,232,466,106,192,165,241,155,258,105,454,283,418,183,188,122,347,25,98,368,362,399,52,30,252,119,32,414,128,188,242,499,201,189,377,131,289,353,120,419,388,393,249,255,130,251,82,231,441,355,211,287,160,320,333,164,254,312,174,417,480,85,378,403,219,137,200,345,59,15,231,41,75,379,109,437,282,402,428,239,131,128,356,381,58,100,142,306,229,495,456,411,128,289,438,378,425,371,191,282,337,487,466,90,461,67,241,238,370,495,198,417,198,78,209,429,172,25,407,225,471,76,58,422,124,287,339,399,72,227,34,194,315,394,21,360,108,34,366,432,138,386,180,397,464,27,78,456,2,257,37,171,222,276,420,436,436,244,491,10,91,141,366,219,389,107,153,69,367,383,250,497,191,312,443,331,255,355,216,24,389,227,58,395,353,238,83,260,233,303,224,376,54,461,245,211,148,390,197,440,422,334,183,489,335,300,122,240,471,68,166,43,92,460,336,133,373,26,286,499,470,167,125,231,417,168,477,297,299,44,353,217,338,231,476,246,232,66,137,3,110,20,284,60,103,2,242,457,288,409,158,455,475,359,446,493,133,225,358,189,274,44,73,421,57,479,402,406,50,66,16,440,338,446,374,212,210,15,9,288,392,5,49,330,384,100,204,346,13,112,166,388,114,378,190,62,369,440,199,132,399,265,468,99,498,383,161,245,318,262,172,121,376,308,201,312,150,168,498,364,41,174,35,48,321,314,147,146,106,468,29,16,25,446,476,73,446,121,248,153,157,440,371,400,45,21,473,415,336,22,104,165,154,493,196,111,117,280,472,297,6,271,83,263,415,77,200,476,471,446,151,7,413,467,430,461,401,257,429,113,462,170,50,380,278,83,206,129,214,5,481,369,211,235,454,64,185,138,229,303,284,217,415,479,250,193,337,137,130,390,286,29,280,208,364,149,31,192,247,72,238,344,291,160,120,62,104,243,404,41,317,423,237,87,98,198,422,321,321,339,87,282,18,331,355,489,223,128,448,190,93,294,251,241,357,37,397,91,411,244,82,87,14,329,402,118,442,227,87,40,429,31,225,180,223,231,398,104,318,70,250,383,463,30,296,445,363,348,147,218,246,44,358,67,39,278,360,464,159,378,68,168,365,477,226,389,205,310,149,45,438,362,440,62,325,408,241,199,385,210,472,416,354,386,161,162,441,129,166,424,419,243,2,375,326,386,384,335,322,75,225,25,65,324,394,279,348,40,186,387,152,294,498,464,277,438,108,290,138,139,328,298,164,427,379,384,215,193,70,500,172,278,232,358,425,189,316,218,87,267,8,341,226,236,377,318,105,212,60,357,52,174,54,147,117,181,389,176,244,74,89,76,394,451,44,146,361,459,278,364,402,256,334,257,466,488,403,366,401,28,116,338,63,40,84,210,286,441,47,497,209,245,91,413,48,23,500,436,345,432,453,188,177,67,472,180,109,58,490,172,158,195,260,13,401,240,407,371,383,411,197,249,382,147,138,85,91,153,381,425,82,484,56,78,465,377,191,325,109,347,5,265,262,336,309,159,468,351,290,262,333,104,172,43,268,387,241,406,357,125,397,364,7,325,155,59,16,9,377,236,172,406,156,16,243,20,170,163,147,475,150,384,179,211,359,296,322,109,313,79,440,220,214,149,88,477,250,206,293,355,80,170,500,39,108,130,456,309,175,265,110,206,497,96,489,420,90,2,124,109,364,361,88,8,171,428,305,107,74,115,297,407,204,346,45,115,203,405,382,169,276,385,373,139,493,174,100,251,461,331,107,128,444,158,15,163,197,89,98,91,66,2,293,197,391,256,57,281,387,115,96,295,438,384,13,242,473,214,430,489,389,258,37,397,432,433,291,256,14,485,120,153,226,487,50,254,315,144,422,473,55,455,73,375,147,273,221,356,141,485,465,205,177,440,488,244,381,174,283,156,132,155,282,398,127,155,387,265,59,18,491,287,104,5,280,150,9,32,53,40,54,278,448,15,421,455,32,241,133,341,303,229,138,459,377,397,471,217,329,150,51,311,233,383,285,110,462,427,380,125,409,442,275,77,220,235,289,45,199,229,290,35,92,237,93,121,403,370,364,485,378,30,479,394,434,34,30,313,457,450,290,220,186,330,160,98,268,166,30,13,203,35,423,399,184,127,415,174,6,334,317,276,476,108,280,83,120,395,3,170,15,471,369,450,67,273,205,466,248,411,207,12,255,223,189,69,133,296,174,393,285,399,299,492,298,484,153,371,450,99,4,441,211,374,316,214,100,34,191,248,160,146,284,8,447,277,238,81,231,335,34,206,448,407,460,23,112,298,190,241,497,248,294,46,386,416,27,77,1,29,448,64,284,91,385,359,387,414,128,188,208,256,273,154,156,162,98,72,431,250,324,465,95,496,480,210,414,92,35,413,279,118,358,438,481,419,87,280,376,73,106,229,370,447,373,203,84,298,137,276,450,101,34,231,30,362,342,392,185,199,266,228,413,34,285,223,6,205,464,104,269,26,109,396,44,216,332,63,304,21,339,490,33,290,331,287,477,366,121,32,138,175,115,29,387,467,123,45,195,49,103,425,358,210,95,349,134,128,345,381,40,154,466,202,172,373,122,314,221,13,452,79,274,238,463,336,230,383,474,310,40,479,81,433,180,443,166,305,197,294,289,194,440,249,5,16,44,319,128,195,448,453,491,48,67,7,215,10,456,266,229,174,490,60,483,207,106,463,205,231,444,478,306,413,233,226,372,20,272,162,407,442,240,336,354,223,99,342,276,122,183,250,89,123,300,111,486,48,36,469,437,95,383,80,231,106,54,486,439,367,328,236,414,160,64,318,277,456,229,324,405,332,10,141,256,91,78,168,261,442,434,402,108,82,450,449,16,341,467,336,123,36,336,369,17,364,56,349,149,220,394,316,234,116,298,70,284,49,97,183,265,63,412,56,256,106,305,192,293,10,245,96,115,179,81,335,332,38,61,135,377,277,8,90,408,71,385,498,132,154,359,389,24,78,151,485,76,205,433,17,487,38,211,327,307,257,249,92,244,94,154,499,17,137,434,462,198,20,433,411,476,120,178,49,72,60,114,276,265,122,73,356,409,28,25,187,131,216,446,363,312,340,15,481,338,204,100,341,344,347,73,467,297,17,206,151,472,315,309,38,169,22,161,6,99,68,15,174,500,466,424,200,348,345,232,230,127,404,334,145,442,356,10,141,458,128,141,143,29,181,493,461,198,435,22,382,301,50,118,59,265,447,169,340,369,244,326,356,308,39,173,484,368,59,19,189,219,106,413,422,321,225,220,487,195,247,463,460,340,203,252,83,370,185,91,13,482,105,176,98,113,500,484,218,343,393,95,332,84,321,449,234,394,336,444,235,97,449,228,369,239,242,468,101,128,74,161,61,475,449,90,125,6,155,51,421,370,41,245,397,182,411,393,478,35,184,41,106,418,494,1,59,74,395,243,477,293,173,52,36,480,451,424,138,308,389,50,223,310,120,386,436,319,403,249,207,212,215,173,462,256,324,338,160,117,499,150,263,475,490,494,364,305,459,79,186,350,305,86,411,205,420,276,105,317,249,330,7,318,16,34,173,478,145,252,499,429,416,62,107,485,105,205,243,47,109,142,100,64,463,314,69,293,279,266,53,176,122,231,456,112,44,375,142,333,5,222,213,17,364,346,458,64,139,68,496,41,365,73,412,151,323,222,306,341,144,96,151,98,241,76,105,178,89,304,6,3,30,156,9,189,102,158,355,311,147,335,227,391,200,188,415,178,478,306,329,237,407,466,395,197,178,294,83,80,29,69,159,54,354,411,122,297,351,107,94,490,333,155,400,326,61,400,484,261,326,191,30,218,225,89,445,136,225,59,264,131,399,367,15,353,296,326,31,90,290,112,96,429,318,275,80,452,392,4,43,492,141,100,357,350,197,284,254,303,95,309,494,490,412,349,325,377,256,17,377,255,15,297,307,216,1,195,114,327,26,428,52,347,299,449,359,115,19,455,288,475,383,63,115,217,254,311,46,28,226,468,30,500,398,302,317,392,238,379,422,214,154,452,55,371,102,434,62,97,435,186,30,227,57,210,491,324,299,150,293,152,107,375,13,389,103,248,329,212,73,268,117,22,424,109,265,295,188,164,24,114,338,62,385,459,69,1,260,120,418,305,329,400,54,403,70,287,423,369,348,60,86,409,234,22,268,326,85,251,48,266,113,140,51,458,462,479,68,360,304,132,228,220,77,132,83,39,41,201,373,116,313,28,278,70,433,486,310,103,51,36,302,92,335,402,6,386,386,44,185,219,206,100,31,15,122,389,322,111,235,179,229,222,292,269,116,291,242,414,203,400,288,9,15,170,360,360,55,107,344,40,288,418,215,184,417,230,422,278,388,428,495,414,383,144,209,170,28,153,333,422,322,78,219,269,346,365,467,111,314,71,457,486,209,94,37,201,409,150,279,91,100,217,217,444,380,347,272,99,367,378,415,351,279,107,248,383,155,464,368,462,112,68,163,247,69,122,138,353,492,70,376,404,198,214,229,315,483,314,182,173,459,348,135,264,475,146,451,172,38,215,416,81,372,85,124,200,451,378,385,318,124,166,270,62,290,439,200,362,496,269,486,238,14,459,465,221,473,392,273,82,195,126,402,188,43,79,143,98,227,38,243,304,323,295,179,496,117,281,169,366,20,273,476,276,448,89,298,155,65,403,96,48,483,94,62,87,435,304,284,376,377,363,390,453,408,79,218,366,294,194,180,233,157,245,164,150,227,88,428,48,391,129,282,378,441,126,144,307,434,238,428,331,382,56,428,239,232,244,259,316,397,212,362,409,441,265,343,485,397,19,397,478,139,313,187,1,437,214,417,455,455,184,102,169,296,197,452,269,265,294,2,87,438,439,441,437,23,77,116,287,385,491,293,380,222,248,45,115,172,234,231,432,106,183,202,268,382,455,27,184,453,363,460,38,126,69,455,22,476,374,111,442,75,126,158,475,335,239,422,10,397,51,341,144,356,118,316,467,93,288,387,14,247,145,228,457,180,464,383,66,207,238,325,498,279,90,162,318,450,15,5,314,148,264,336,341,348,276,421,410,462,62,490,353,56,115,494,276,344,319,262,87,420,499,37,321,422,366,436,197,356,119,154,433,305,365,329,362,442,144,424,390,42,41,451,152,466,197,354,392,151,346,463,144,83,37,90,241,207,358,384,200,344,44,450,125,193,266,93,15,386,315,189,310,40,447,323,436,263,20,173,480,391,354,113,294,404,126,199,481,58,287,307,367,454,280,299,5,270,352,227,189,465,63,280,306,397,78,16,255,66,166,162,164,18,353,239,24,184,80,273,257,248,488,423,127,66,413,151,213,394,378,56,446,262,407,406,430,459,465,124,155,172,461,477,296,467,349,390,289,66,498,34,325,491,321,62,475,460,90,338,98,201,212,14,228,61,179,206,55,208,272,386,463,155,60,62,481,123,370,372,348,182,412,237,34,9,442,460,443,253,160,414,182,425,130,419,67,114,255,468,315,347,363,147,23,349,116,482,58,376,38,12,338,476,91,494,391,486,156,143,216,140,61,293,107,384,425,490,469,314,80,172,196,405,343,281,452,73,288,204,171,136,7,474,225,25,166,293,468,152,1,401,472,145,59,322,369,301,64,395,52,155,481,203,382,276,423,122,261,132,160,220,312,62,448,218,300,160,369,351,437,65,116,61,109,41,249,49,2,220,39,295,487,299,114,387,95,390,287,237,426,420,452,70,130,399,441,65,107,81,464,355,435,464,134,67,175,223,4,271,348,486,78,341,82,298,327,294,373,274,56,342,127,211,236,439,56,278,135,458,222,409,208,321,85,417,304,184,332,23,146,335,126,266,122,93,494,106,177,144,155,144,312,490,69,5,257,434,422,274,240,317,46,170,15,206,499,181,351,294,126,373,341,141,340,240,318,327,330,201,139,63,129,309,229,360,303,252,198,111,144,290,86,62,98,374,395,8,302,318,14,375,500,125,400,313,347,456,38,359,10,14,133,133,260,128,454,124,41,398,227,26,419,371,461,490,378,353,480,189,136,458,206,10,450,40,475,427,397,219,406,150,78,341,35,397,475,189,132,82,459,373,25,96,314,295,383,312,322,1,252,73,163,260,265,100,252,321,451,120,20,203,303,411,146,107,466,108,258,448,386,79,98,268,386,72,177,149,302,392,403,36,473,302,22,313,453,184,351,232,327,495,360,482,92,139,75,31,445,284,273,198,20,490,352,448,468,22,116,489,449,59,300,145,486,454,154,32,297,42,298,430,447,292,11,412,209,468,168,277,348,475,129,398,62,231,336,447,383,498,452,83,488,235,425,44,275,228,230,37,117,50,241,130,31,16,27,95,442,200,22,381,20,304,229,112,100,90,471,391,297,69,28,372,52,430,386,373,265,232,310,116,134,464,121,492,252,34,399,17,340,358,463,4,231,459,81,432,331,256,218,475,492,274,28,283,315,447,468,149,483,310,58,109,83,169,224,368,337,218,11,377,158,178,121,157,83,105,13,91,42,360,298,180,347,277,64,260,71,195,158,263,1,179,10,213,64,140,120,314,282,256,84,359,264,233,435,248,207,209,45,52,133,114,438,312,250,258,273,395,108,244,500,315,303,222,443,279,149,173,373,343,187,333,456,200,146,342,489,389,416,419,362,275,52,2,227,25,402,450,334,145,152,300,226,465,114,263,136,7,275,149,305,282,133,315,281,223,309,145,248,273,156,123,371,128,260,73,31,434,245,192,479,489,441,103,257,186,168,207,313,234,477,223,394,315,383,164,75,264,76,426,450,486,305,374,365,492,388,290,488,296,245,344,212,459,90,247,340,281,267,472,230,170,15,455,463,287,189,288,44,147,351,458,305,18,187,315,362,74,64,481,97,449,98,159,470,239,471,342,267,86,403,268,44,473,337,237,208,89,443,193,406,376,339,195,325,73,372,54,400,242,165,106,247,171,354,235,332,90,197,467,434,438,30,287,14,455,52,489,97,57,442,81,464,332,422,215,252,201,402,419,274,348,161,82,428,457,419,6,198,63,499,310,46,63,206,431,256,330,198,28,111,407,1,455,142,322,270,106,80,172,452,115,124,481,382,100,250,208,164,291,116,342,489,59,238,427,250,370,407,324,13,313,465,27,340,299,236,51,394,282,304,129,306,192,71,387,372,400,332,378,185,495,3,80,495,459,274,386,466,195,285,484,153,428,455,282,159,282,35,281,255,421,88,136,352,181,166,177,85,318,58,245,30,488,170,487,341,273,483,454,87,402,340,498,352,426,198,379,475,398,154,90,299,410,25,478,323,15,5,32,51,243,21,240,20,460,337,113,340,17,459,149,440,471,43,206,356,85,316,50,59,353,129,469,360,277,54,282,182,459,456,413,189,482,124,292,6,254,92,1,459,275,460,286,149,27,287,389,16,339,375,376,119,223,29,418,269,39,235,388,317,66,300,481,287,299,307,467,256,447,40,8,422,212,93,17,10,217,374,494,37,480,271,88,359,10,77,10,83,211,12,36,432,495,327,395,433,402,46,163,435,49,464,32,150,91,411,402,120,5,190,93,281,18,26,438,248,440,9,411,264,201,33,399,244,43,83,380,128,124,426,75,422,458,104,415,6,376,460,310,325,144,171,191,14,255,54,218,113,52,357,59,186,53,163,220,136,8,264,30,483,436,394,112,281,177,300,208,242,196,62,108,439,332,371,54,491,214,178,228,166,106,445,142,140,216,25,171,116,248,108,391,322,462,158,104,344,207,493,388,466,177,376,108,54,67,124,408,336,7,450,289,435,451,226,474,147,312,408,48,388,254,217,322,154,130,406,489,143,58,58,37,446,361,331,270,72,333,153,205,174,251,34,500,229,406,443,257,61,175,142,456,397,94,490,20,141,209,363,358,359,268,139,169,131,423,73,19,167,148,250,379,84,312,147,393,170,411,288,442,452,265,37,397,326,369,420,219,405,498,440,96,211,248,72,403,364,308,396,30,310,386,299,424,454,300,336,233,249,114,438,281,3,60,240,145,423,490,401,393,45,341,269,261,143,479,274,200,385,62,275,431,257,266,357,295,296,327,133,335,447,187,464,435,307,498,491,176,217,409,111,421,26,434,170,307,108,327,272,47,143,199,451,79,293,340,403,300,71,127,371,379,137,291,494,451,138,322,259,428,470,338,109,376,195,294,440,281,64,294,282,131,373,39,367,28,321,424,329,168,206,238,32,341,16,405,72,149,34,332,346,403,412,298,463,268,100,155,21,32,309,475,276,95,439,88,266,4,329,123,447,109,217,231,486,309,311,325,318,45,158,201,22,4,14,144,102,335,281,452,272,126,127,479,179,184,177,336,159,179,305,128,154,45,452,318,205,56,235,308,201,172,471,484,55,243,329,308,77,60,50,162,398,289,496,137,366,16,399,286,115,443,226,219,105,459,356,379,331,161,426,69,220,360,79,473,359,137,371,190,488,55,348,275,16,232,262,312,33,82,74,470,260,470,166,41,148,116,187,491,22,480,294,184,179,399,120,144,164,481,422,211,171,429,454,317,187,200,200,119,40,162,137,480,89,407,499,496,468,163,27,1,141,14,490,369,207,5,21,314,33,331,462,74,171,69,204,55,78,347,162,215,448,412,112,237,474,418,293,490,79,88,24,33,300,170,175,464,251,400,471,349,78,223,29,367,10,451,382,26,494,259,48,370,240,225,308,116,287,423,114,458,51,295,284,172,487,172,183,446,379,218,160,44,384,62,177,50,94,187,133,460,105,75,123,458,196,368,84,81,133,367,212,45,499,192,257,457,227,344,236,418,115,362,102,212,358,483,221,235,111,418,92,431,253,124,230,238,248,449,136,112,203,229,378,194,436,92,426,8,343,278,405,345,407,468,4,362,484,302,21,263,115,151,167,85,129,216,1,199,429,12,396,338,285,117,432,73,49,490,148,241,379,199,243,45,260,57,399,95,118,179,457,21,88,498,375,338,178,161,269,179,486,338,465,418,275,359,391,14,290,22,305,268,192,330,460,440,1,104,281,202,32,211,442,246,329,483,218,476,354,102,417,221,19,466,145,144,198,452,354,333,171,345,403,282,253,439,198,453,474,433,216,16,187,492,171,48,270,151,470,289,439,320,17,357,132,352,454,477,373,151,357,123,184,273,425,74,257,299,88,12,408,108,387,163,238,236,156,401,260,337,331,228,436,261,237,167,146,36,392,463,256,112,292,399,266,148,143,156,167,193,455,490,166,417,367,49,250,155,141,64,22,277,263,66,113,155,93,124,224,483,413,440,275,40,200,125,288,334,314,169,156,49,21,309,8,69,62,301,165,95,431,102,320,359,356,53,327,285,290,235,74,100,123,43,119,125,379,130,106,197,257,444,298,463,256,131,386,443,134,135,81,118,169,253,238,92,65,391,309,276,499,124,464,475,17,273,199,225,499,324,368,367,104,245,476,19,51,48,396,268,182,396,221,491,63,99,489,74,190,227,67,186,496,255,399,1,123,216,335,76,32,389,207,411,415,76,310,158,218,458,459,194,435,123,21,158,433,391,15,56,59,18,77,13,438,201,205,484,214,290,247,36,276,204,18,293,87,301,336,387,298,295,142,387,23,412,14,108,268,393,163,219,221,434,460,472,191,209,49,326,156,34,124,311,325,222,225,285,398,301,155,78,6,378,389,238,84,131,470,128,383,306,134,305,399,321,139,428,425,399,312,142,187,145,97,452,86,254,37,452,499,295,378,32,298,107,353,227,213,424,439,98,86,173,93,128,125,98,242,499,232,403,148,445,343,126,74,311,43,176,116,349,487,207,325,312,290,303,392,111,495,224,45,78,498,194,493,226,68,10,493,427,254,126,283,177,50,60,31,452,357,436,424,424,467,6,413,270,155,201,284,344,304,450,354,269,469,165,349,495,378,167,425,151,85,399,276,360,102,306,489,260,111,366,416,402,444,6,421,146,148,249,329,17,310,175,448,150,249,299,142,389,325,131,381,216,148,490,232,485,458,145,195,494,373,395,237,398,341,313,413,8,325,319,437,127,105,253,34,317,17,351,310,326,24,213,37,488,331,463,453,57,178,191,345,54,163,86,393,267,171,127,449,29,306,63,298,327,87,230,452,94,494,433,383,309,152,426,421,237,155,387,133,234,243,395,48,409,370,83,358,396,476,342,69,268,496,398,147,18,270,429,155,78,254,105,124,291,44,20,94,278,394,25,407,42,431,453,418,373,320,231,344,246,470,320,166,301,418,259,484,183,408,122,346,27,139,52,309,454,424,277,350,424,314,357,396,473,448,389,473,196,163,172,493,131,192,120,187,465,428,198,22,66,112,186,45,175,52,92,399,152,296,292,83,473,6,91,342,189,498,60,496,305,411,360,447,130,450,150,68,91,158,276,55,356,83,52,440,142,406,275,25,356,480,262,137,63,107,136,187,420,335,277,100,241,150,70,393,267,185,399,26,331,169,440,221,288,79,164,11,462,16,285,255,223,469,465,438,309,456,151,122,284,181,448,295,414,142,475,343,191,468,193,267,481,256,46,128,306,390,10,123,333,313,336,45,183,218,287,376,220,169,40,184,164,487,377,315,158,382,410,469,44,243,246,493,481,187,482,442,294,7,151,335,354,440,358,384,418,155,335,270,210,86,59,427,493,317,129,383,277,458,398,212,408,330,434,335,324,110,84,325,9,395,337,120,358,438,354,54,135,8,158,53,289,331,41,21,345,380,91,340,473,27,30,455,314,166,203,102,437,62,237,88,149,16,322,308,419,417,33,361,390,490,270,31,488,349,301,340,99,431,87,128,44,280,83,422,15,418,75,101,176,22,196,267,32,264,374,185,59,176,457,5,500,448,189,38,136,295,367,180,171,158,90,49,437,333,283,73,270,386,457,68,98,270,241,31,114,246,83,366,481,471,392,92,500,206,190,257,419,77,11,391,5,209,262,74,56,298,65,341,135,110,105,307,14,498,493,30,245,283,487,259,33,374,25,448,346,157,81,20,283,12,18,391,418,384,177,8,81,336,145,105,146,127,467,450,164,415,171,106,399,477,45,477,280,446,344,76,418,387,343,368,367,150,483,83,181,216,166,289,409,481,403,457,59,411,116,106,392,395,259,19,403,411,445,62,453,6,50,332,133,410,167,12,392,349,158,36,494,44,166,303,475,359,176,262,215,64,311,338,214,445,245,39,205,453,452,120,32,258,114,297,22,170,357,336,464,237,344,4,289,100,168,214,27,334,355,410,265,462,216,310,27,18,446,152,54,439,229,427,353,130,292,362,201,241,57,100,153,168,195,181,75,477,491,332,450,492,468,463,445,279,264,327,206,395,412,261,453,86,232,325,357,131,268,191,410,105,180,437,294,416,417,130,239,222,190,7,354,15,16,301,172,393,370,63,499,465,301,218,226,93,433,424,142,228,395,384,282,197,441,342,248,204,381,68,273,479,58,253,357,38,105,30,268,95,362,88,175,375,117,464,473,96,213,387,46,369,500,114,152,1,312,55,341,24,236,197,449,68,313,161,434,109,129,420,499,82,272,409,9,234,242,45,442,183,338,282,257,251,479,364,152,149,313,316,131,401,348,47,60,285,218,388,46,117,256,394,33,280,360,431,345,320,462,167,402,443,362,406,273,224,328,102,370,42,189,138,121,397,223,273,61,291,153,344,287,133,84,376,284,55,479,105,143,151,452,298,204,171,157,294,332,230,320,128,195,183,359,480,56,234,340,432,436,197,270,388,351,113,411,338,54,62,288,479,499,110,452,116,481,127,497,478,201,488,177,374,326,424,387,450,202,491,84,98,30,335,402,276,86,77,300,197,462,249,427,421,310,82,295,427,471,187,148,478,13,251,474,257,363,358,241,88,265,333,73,81,45,490,372,356,86,446,27,220,140,69,361,55,199,157,419,10,72,308,53,158,362,337,496,476,10,47,290,475,256,367,37,128,323,9,372,313,41,278,376,371,292,53,369,278,486,77,386,333,403,17,100,423,110,272,372,348,244,133,297,329,452,225,371,432,267,188,110,214,174,167,52,370,167,33,179,441,360,281,200,13,180,250,358,316,248,239,459,263,191,183,70,373,251,51,76,11,22,467,419,115,381,117,210,266,324,25,95,84,240,162,203,164,416,471,194,118,184,179,380,219,217,334,337,396,319,81,118,31,226,398,402,76,286,198,150,462,99,46,293,332,174,402,453,488,470,17,340,351,435,291,128,267,138,141,235,463,451,360,483,243,497,414,243,298,226,460,61,454,209,351,286,223,34,391,405,497,178,359,72,281,340,370,449,223,312,456,179,387,12,443,114,48,234,230,31,388,116,434,337,379,257,28,65,351,388,244,431,425,244,41,275,415,167,199,293,384,81,147,297,259,428,478,324,404,266,314,84,334,400,40,496,11,291,493,14,200,317,342,280,430,464,371,79,141,500,291,463,265,244,110,277,44,373,374,19,17,483,435,80,156,379,87,318,468,159,391,206,192,92,391,491,155,327,250,151,240,128,256,32,226,254,494,240,12,30,214,333,406,271,308,194,403,231,342,121,65,121,476,83,361,205,353,288,272,368,29,148,318,53,493,178,351,421,406,353,37,196,197,489,292,154,181,283,254,330,89,375,151,446,154,87,386,465,407,399,453,407,124,439,445,89,354,219,289,159,462,400,194,121,470,236,429,426,150,69,193,339,468,75,105,9,197,486,311,119,141,412,23,373,375,265,261,196,75,482,394,67,118,17,56,143,126,209,175,273,143,298,192,423,139,457,154,278,259,58,100,499,24,332,101,281,387,469,248,68,45,359,360,478,143,69,41,21,223,311,117,186,129,138,12,144,391,309,13,490,14,273,222,193,339,214,79,187,439,204,472,163,175,235,239,318,460,27,339,140,272,97,248,433,259,199,428,232,79,304,323,319,465,122,376,142,190,430,262,175,19,444,32,428,237,421,253,341,13,31,5,366,173,432,422,434,98,431,440,243,48,193,58,447,209,253,194,212,285,185,321,406,7,15,452,432,75,405,244,362,363,389,295,173,391,298,37,2,12,297,345,463,468,100,149,334,344,247,229,205,305,346,344,354,16,256,233,197,94,63,391,293,60,398,302,340,164,405,316,100,67,1,433,46,221,218,172,378,276,290,419,277,261,441,43,37,301,111,254,81,9,236,295,135,326,497,429,460,174,316,212,16,286,195,318,11,170,301,171,205,232,144,314,322,317,222,2,491,74,237,367,231,432,251,386,299,377,38,200,339,317,136,95,446,353,228,335,202,371,387,107,438,80,217,274,58,21,478,370,162,443,161,100,107,404,68,30,13,431,253,55,395,87,247,163,147,137,427,57,191,277,224,355,1,257,287,485,384,434,271,66,384,245,303,345,146,375,435,10,213,498,479,415,303,302,160,59,366,188,104,234,491,239,6,199,450,230,76,173,4,119,367,398,488,23,111,207,355,275,309,238,204,257,146,239,220,497,231,308,139,428,343,148,313,481,451,431,306,227,91,177,379,76,18,139,270,21,321,425,474,439,324,443,145,136,289,227,272,116,380,144,78,145,13,38,229,319,286,392,116,360,304,333,299,389,162,188,467,367,366,175,351,260,290,312,436,99,289,459,101,75,148,257,180,173,489,345,496,201,19,401,288,254,111,273,378,491,429,473,442,294,329,174,239,304,235,85,341,271,296,112,26,383,254,430,220,466,471,439,444,308,258,222,311,491,249,170,312,245,118,110,195,161,63,185,340,165,353,226,85,15,352,449,56,47,262,16,402,343,220,310,51,399,296,492,99,258,469,387,227,71,177,215,354,360,98,384,144,298,430,100,127,291,451,190,37,171,500,217,166,464,490,1,200,319,228,85,478,392,111,168,449,209,327,237,188,439,328,235,199,48,89,17,263,220,129,471,363,292,345,199,493,54,191,5,96,334,110,7,396,50,292,26,145,456,282,19,451,419,260,87,335,129,79,387,81,420,148,461,213,13,264,461,2,263,150,116,245,94,223,230,303,297,439,27,447,95,376,437,297,11,210,418,70,171,494,162,462,317,162,458,408,250,257,372,69,173,164,272,101,238,157,52,405,56,360,69,444,486,69,68,178,331,395,262,307,398,496,376,489,34,226,52,258,151,256,274,11,440,483,373,204,118,450,387,445,220,383,152,222,329,15,71,104,427,6,15,227,396,180,19,150,236,425,67,113,396,70,221,394,178,381,193,284,491,441,266,139,347,188,10,475,109,92,194,381,340,431,307,368,439,162,254,29,270,137,417,176,18,498,188,312,81,370,474,143,92,411,301,119,455,152,325,103,128,375,469,108,137,70,48,36,326,87,233,263,408,416,332,340,212,120,64,476,232,96,58,8,81,423,500,102,159,214,188,184,397,96,412,309,262,332,381,138,337,338,109,482,282,281,139,83,6,392,331,235,267,205,28,491,82,393,212,279,163,182,279,184,285,100,496,149,63,187,154,346,24,55,85,389,60,77,471,183,33,35,387,123,47,32,49,24,387,93,100,54,308,417,490,450,489,70,424,191,345,409,412,281,40,38,29,85,103,78,18,407,439,120,387,198,270,477,295,52,309,271,164,352,417,229,446,282,30,470,204,235,295,274,58,226,36,332,377,87,458,146,14,324,454,239,319,415,394,224,405,74,43,84,352,444,234,180,478,333,83,464,69,273,245,188,364,245,76,320,206,300,345,60,214,240,62,156,288,435,91,226,411,342,306,195,5,482,471,258,178,445,97,40,174,353,99,197,462,386,92,86,490,179,100,301,134,429,173,36,429,317,123,450,297,465,124,248,190,482,389,317,147,144,274,95,491,60,6,460,468,222,105,110,320,445,444,91,143,6,85,62,470,264,436,108,392,177,203,400,335,88,463,367,175,446,100,380,264,153,301,237,275,191,362,469,81,228,484,448,444,196,497,194,267,163,345,116,91,72,490,61,61,245,173,143,168,45,302,415,33,353,128,205,242,188,103,177,278,134,56,243,29,385,449,32,37,111,98,339,374,281,293,393,14,188,59,77,62,19,221,165,243,314,235,15,149,410,244,49,20,66,145,189,326,16,281,153,339,458,36,268,425,357,305,339,164,165,174,14,303,163,499,433,405,242,211,179,369,438,302,354,310,317,401,404,76,369,446,400,241,295,342,315,229,39,117,48,398,289,336,292,485,277,354,367,491,420,107,261,73,457,224,481,493,449,214,34,110,344,91,445,499,154,104,41,485,142,145,115,349,466,75,177,431,254,405,399,222,388,3,6,205,374,334,203,267,68,244,82,248,210,140,392,6,235,238,404,281,169,397,328,336,74,447,461,257,180,9,434,320,47,308,340,5,86,153,7,470,397,365,213,474,58,130,450,337,303,100,150,385,97,229,211,98,389,358,494,71,309,16,10,23,223,268,277,302,391,491,418,205,188,391,73,177,176,476,270,496,213,171,354,130,428,454,24,114,405,10,322,446,1,332,221,15,466,25,433,222,147,302,470,244,366,221,64,108,48,362,216,475,81,98,345,19,473,63,208,165,448,170,32,17,306,348,191,306,264,58,362,79,169,429,161,468,274,347,189,139,479,412,17,255,207,201,53,488,300,469,30,165,37,255,200,232,326,349,282,158,375,192,338,209,437,389,494,348,452,409,221,314,80,378,263,19,72,33,176,333,177,210,354,289,116,387,347,108,8,141,120,338,485,293,372,486,316,4,498,64,56,60,234,130,123,345,484,287,195,113,73,255,421,212,281,193,77,216,243,404,352,378,112,418,221,367,360,388,149,252,295,400,291,19,18,109,340,336,359,199,240,109,229,229,151,158,145,117,289,297,18,235,455,367,90,71,443,133,415,470,400,481,151,301,60,18,24,90,368,119,81,96,491,29,443,335,35,100,360,214,327,290,403,16,487,116,331,495,380,104,104,428,497,29,53,173,47,406,376,10,206,431,216,329,469,73,467,482,306,431,149,323,135,276,295,380,382,402,321,276,227,38,407,439,485,166,369,134,428,341,355,246,382,258,486,350,321,54,441,132,2,154,17,448,38,226,289,133,440,160,14,262,84,125,200,14,110,263,336,484,308,237,132,75,440,78,134,111,455,127,89,267,289,205,451,357,346,336,341,286,83,390,390,79,119,132,76,157,311,12,193,425,378,317,123,256,437,287,297,97,464,40,108,190,326,492,50,447,329,62,139,51,225,464,415,337,469,492,269,212,245,89,304,355,394,482,296,286,312,359,129,259,54,186,469,10,106,111,41,5,255,221,283,156,149,7,55,127,232,127,242,207,41,187,141,253,476,175,20,407,129,248,292,213,371,176,324,25,32,391,89,343,186,352,250,154,151,366,261,161,134,391,140,335,404,109,145,91,465,60,54,229,40,313,61,139,130,178,17,245,83,295,284,82,232,359,447,216,340,453,33,488,251,119,120,51,453,3,15,434,40,393,390,351,162,122,457,58,464,356,329,305,126,72,237,36,260,466,418,466,34,392,456,46,269,464,215,423,353,273,59,445,57,434,208,362,66,352,358,165,151,174,467,490,222,132,456,3,378,377,156,353,71,392,33,1,498,344,340,20,150,64,129,340,312,136,297,124,236,465,458,356,113,365,383,450,461,253,309,331,135,249,328,432,375,92,252,113,17,333,427,393,426,423,478,83,482,174,4,191,392,23,484,19,257,500,37,255,310,102,213,434,429,85,482,47,428,460,369,352,166,238,205,66,480,142,128,443,401,24,261,150,71,421,169,403,168,103,218,444,373,407,467,58,370,210,226,302,60,268,164,456,342,436,369,159,360,97,213,475,320,346,88,221,488,396,207,327,64,363,261,462,10,289,3,494,133,466,208,93,186,9,102,248,240,41,203,457,283,169,161,299,232,53,386,405,75,231,24,283,19,215,186,171,430,299,118,6,55,135,333,485,166,462,182,240,396,319,23,466,380,485,234,459,374,24,274,49,216,146,167,3,372,479,6,353,284,333,46,206,271,136,256,385,33,223,372,209,18,461,326,336,427,81,494,319,63,491,344,73,156,149,349,364,200,419,383,347,472,375,397,431,457,369,245,249,257,436,453,57,478,284,475,367,112,194,156,396,62,71,352,41,98,208,309,421,354,304,287,334,235,381,255,472,145,3,149,394,448,402,132,78,65,330,426,473,192,186,181,121,500,134,395,254,314,432,162,494,117,216,325,309,175,496,242,73,127,461,346,58,166,312,149,392,486,101,267,284,337,435,463,483,215,186,68,387,208,156,119,23,76,109,234,391,286,123,208,142,380,467,46,171,357,438,228,177,438,64,462,491,270,372,84,348,285,387,123,400,337,452,129,353,112,315,161,179,367,163,148,88,439,345,57,256,427,196,421,215,415,224,244,122,284,402,63,274,33,375,44,473,128,461,394,243,455,164,101,206,391,298,174,294,372,344,101,338,35,7,113,425,187,95,140,486,148,55,260,384,440,432,124,7,1,225,408,477,180,362,161,434,213,254,222,76,416,19,476,256,109,297,147,419,185,427,199,406,263,97,236,94,156,253,358,157,248,414,278,23,163,124,398,466,180,294,357,219,397,130,305,438,190,401,444,94,317,475,255,106,32,239,166,365,51,202,222,479,86,160,425,26,224,146,30,90,39,14,86,485,289,413,260,296,496,132,270,160,300,396,322,446,168,70,94,284,276,179,348,157,62,497,499,153,368,461,312,438,463,123,277,444,376,245,226,386,409,236,39,255,428,368,175,50,121,417,140,235,16,341,13,192,104,11,71,392,430,439,88,463,174,283,383,359,156,152,409,1,405,487,150,410,268,9,250,331,177,235,293,270,213,263,296,98,468,185,13,363,274,458,370,196,291,301,374,63,371,229,363,400,382,291,347,358,377,174,224,124,311,319,24,22,45,329,433,285,7,187,185,363,180,110,351,141,98,258,148,311,200,141,108,491,134,284,487,74,304,296,384,497,203,466,109,185,355,396,460,97,280,302,300,75,57,109,114,58,467,367,277,278,219,1,90,339,364,332,464,290,410,89,294,3,82,498,128,118,443,54,82,432,175,476,85,255,412,249,487,456,335,157,359,403,180,246,139,10,144,365,40,330,306,291,18,385,179,270,270,70,194,277,430,40,88,159,424,283,29,229,298,106,177,427,56,171,172,151,318,10,223,494,191,186,416,405,37,335,230,94,477,426,347,288,300,184,280,303,41,108,472,85,428,472,117,181,287,148,118,21,183,414,51,360,171,323,365,340,473,241,447,366,36,87,74,428,152,25,194,402,377,245,370,62,72,498,140,284,456,369,78,302,299,207,182,269,2,4,376,291,160,464,7,11,12,456,191,180,487,481,458,282,267,402,442,94,150,341,204,115,383,294,325,336,352,168,108,239,375,105,253,365,334,50,360,312,190,194,459,8,195,74,184,210,47,143,8,91,307,376,19,38,149,351,270,450,340,113,75,273,146,255,484,193,221,33,381,389,415,403,13,492,447,375,105,390,145,249,325,361,5,55,84,69,137,21,324,308,470,482,57,28,292,229,114,108,39,241,179,350,310,381,453,344,96,81,228,310,14,419,303,26,158,122,24,489,379,271,250,299,63,131,477,386,240,91,453,124,351,164,67,48,408,171,39,5,56,466,289,475,193,13,248,160,365,374,354,380,8,177,465,106,230,389,463,233,154,441,407,135,281,336,382,498,155,297,68,274,305,480,404,224,46,99,259,34,203,186,317,317,302,179,51,161,71,299,252,292,482,343,84,324,314,212,495,40,489,208,35,63,125,122,246,385,165,402,129,304,399,234,344,453,159,186,11,176,342,137,242,452,236,190,330,292,193,340,219,411,453,371,444,116,424,152,246,367,327,145,232,487,296,222,376,41,363,253,445,104,339,444,43,51,37,277,387,485,298,145,340,301,19,142,7,178,84,359,432,273,471,360,434,253,353,483,367,246,36,472,422,172,159,250,43,187,104,172,82,277,465,490,280,252,60,21,333,152,259,430,172,195,13,411,210,165,175,244,244,11,196,280,204,144,229,357,244,491,229,44,363,323,259,399,166,339,127,157,372,50,484,37,495,225,61,323,497,40,72,369,175,56,394,91,149,468,149,293,188,411,465,252,15,48,398,56,102,363,160,84,215,89,176,356,192,187,152,351,389,487,95,23,468,338,18,51,372,313,88,436,2,372,231,264,225,342,492,485,209,126,103,256,243,291,425,316,203,494,393,83,204,483,296,320,396,476,40,156,46,497,413,244,482,453,207,52,69,188,357,91,70,242,209,437,154,30,141,272,92,9,76,55,134,11,283,294,346,214,445,316,166,214,100,224,465,30,485,4,451,306,311,313,257,14,189,369,218,366,107,108,292,300,393,368,301,219,137,316,94,152,296,125,500,48,477,376,225,107,353,33,215,240,332,11,298,307,323,434,353,377,164,240,90,24,305,225,307,292,37,339,85,259,437,134,156,189,184,484,380,301,208,250,218,307,383,326,450,388,83,79,455,109,274,189,434,487,195,230,458,337,195,213,297,205,229,291,326,207,386,41,102,203,193,447,23,218,244,65,36,400,258,88,390,349,231,117,416,175,403,283,201,158,159,108,32,276,82,400,123,257,254,298,213,437,424,277,403,45,84,404,436,130,143,118,116,493,154,351,149,408,145,73,233,263,454,115,153,232,310,306,494,360,180,399,343,175,342,227,492,108,26,307,94,91,22,56,84,497,288,488,140,384,162,391,220,280,407,359,425,175,176,44,451,74,249,205,119,430,42,213,336,292,422,383,162,321,59,246,423,126,211,161,461,61,153,173,485,322,74,326,495,147,361,414,407,49,35,122,89,337,216,439,98,428,76,274,257,27,487,488,499,167,473,179,4,498,486,367,420,364,28,366,471,175,160,184,132,12,316,476,246,48,392,117,254,372,329,122,266,281,168,207,74,56,17,253,86,403,314,26,153,234,279,138,161,199,389,163,492,351,128,263,424,427,403,188,441,500,467,35,106,243,432,110,155,250,424,8,82,48,395,332,317,169,429,339,221,160,168,226,99,255,313,109,61,107,367,155,330,233,372,235,423,346,367,201,223,343,252,202,16,118,39,128,71,456,45,376,436,93,257,125,215,439,445,336,121,343,202,226,405,446,128,308,487,177,219,496,192,481,403,253,40,280,149,383,491,471,196,472,1,262,469,177,226,127,403,95,374,271,376,62,470,399,217,429,449,180,362,463,320,443,484,272,303,342,366,423,41,258,152,322,444,403,187,140,483,355,59,158,98,443,183,418,285,216,369,174,297,315,111,135,18,2,468,236,160,37,464,190,274,413,163,231,393,405,231,312,462,108,442,361,240,8,481,217,279,66,431,8,408,487,23,147,242,285,401,3,403,500,357,419,481,129,221,229,441,202,286,104,291,213,370,261,268,361,205,322,359,224,31,206,133,375,428,320,265,216,361,399,108,231,140,207,362,497,128,387,127,116,18,345,483,266,285,69,159,134,275,326,389,70,418,104,236,415,332,172,254,115,383,95,224,342,434,120,249,5,134,333,391,491,265,122,297,215,463,413,51,367,8,111,94,212,71,90,229,464,390,197,273,110,440,147,62,237,401,348,399,66,474,39,294,161,434,358,113,176,198,398,34,45,278,180,149,351,378,196,341,224,2,190,462,318,494,48,450,197,263,314,495,463,424,102,206,304,442,92,152,170,104,230,168,30,27,149,446,462,335,135,111,285,1,451,274,446,51,469,356,381,251,427,73,236,396,157,413,167,456,365,133,124,316,91,323,333,327,235,305,17,323,134,223,78,494,117,136,42,398,178,333,397,398,357,438,397,295,120,110,134,456,91,412,359,158,261,261,211,436,212,51,348,389,337,117,160,425,275,44,214,27,51,376,162,422,450,12,326,276,459,378,418,362,497,441,65,486,222,205,490,96,66,30,160,461,469,185,61,154,321,266,7,251,237,169,2,385,309,277,364,379,59,144,294,406,111,72,360,193,104,351,308,114,245,324,480,275,313,284,259,94,427,59,52,477,499,424,343,114,415,404,462,24,75,288,210,37,297,86,211,118,410,68,59,62,179,365,344,371,29,477,313,484,458,334,21,293,329,330,305,274,350,142,1,80,239,454,66,226,368,314,94,333,424,78,359,285,42,371,244,150,249,69,196,412,40,451,343,303,275,230,98,131,392,361,315,314,443,426,39,141,143,440,174,131,230,427,150,338,445,500,277,79,434,50,354,174,95,126,148,124,162,152,68,99,416,367,46,114,212,141,367,95,450,53,150,103,417,339,370,57,80,251,74,159,478,414,389,171,451,436,270,407,401,480,450,253,451,323,109,33,49,262,72,446,442,315,170,397,48,124,22,442,276,268,295,164,207,8,489,49,150,400,157,264,228,11,28,386,390,14,240,173,138,237,486,424,201,260,158,9,359,168,243,93,271,304,152,344,361,472,160,187,390,74,103,123,91,60,407,397,38,90,272,232,35,218,203,388,441,219,147,375,439,190,463,7,423,150,102,114,86,431,360,130,374,126,402,473,251,427,329,41,182,217,211,65,137,166,265,363,277,61,380,204,194,134,400,195,224,346,444,214,20,48,36,259,370,293,249,205,162,300,324,89,35,463,315,109,27,268,423,396,22,337,33,115,290,93,281,257,204,172,190,181,490,271,228,455,415,25,340,291,82,272,391,362,59,66,300,434,77,492,461,3,38,431,274,248,35,129,499,362,141,432,172,478,372,384,344,329,232,488,475,351,283,234,275,194,276,296,276,254,251,83,256,84,215,311,8,204,175,488,436,41,134,87,351,413,271,136,413,54,101,38,399,250,291,282,323,7,281,484,277,65,142,199,227,247,213,153,129,46,276,398,222,410,67,212,38,238,466,378,230,200,214,193,295,35,260,320,215,208,247,126,362,21,365,358,214,37,330,250,380,318,413,49,128,393,145,92,213,29,113,190,355,365,388,359,475,110,89,289,27,230,108,238,3,264,8,271,61,329,272,21,126,76,6,495,187,327,74,269,436,235,108,32,276,332,354,11,36,99,395,320,55,155,254,49,137,485,268,23,181,303,82,334,244,392,119,323,285,462,472,197,448,259,183,464,58,333,76,350,500,431,424,305,132,442,220,174,270,456,99,93,436,303,280,190,115,379,273,301,456,20,419,147,344,422,355,103,148,405,146,470,25,133,458,132,145,375,191,357,144,429,155,5,104,230,98,495,290,216,223,90,211,381,361,479,308,250,327,316,66,171,232,65,486,9,64,462,42,130,61,134,331,405,383,19,289,451,297,491,338,463,45,324,462,183,36,450,208,205,247,44,176,263,399,82,140,91,379,422,452,320,196,78,357,183,264,279,229,390,264,238,433,253,124,97,386,384,171,99,333,54,112,209,291,321,226,230,250,4,465,212,425,456,23,128,404,283,20,98,174,448,343,474,297,76,499,397,50,399,498,414,418,65,5,77,430,382,110,439,404,303,388,308,275,266,463,412,99,357,97,479,123,355,206,93,393,294,33,10,102,260,14,271,91,483,322,483,381,177,489,11,406,440,15,435,410,22,426,478,414,274,50,66,164,425,450,26,113,27,477,238,242,136,177,238,216,343,367,399,81,90,173,349,328,27,426,176,420,89,58,203,18,25,160,191,70,250,274,381,98,321,288,144,363,237,185,96,370,225,489,382,216,345,125,53,231,369,158,467,95,110,458,458,93,286,469,55,384,168,258,46,195,370,264,12,156,61,238,164,92,41,230,355,284,427,105,180,310,369,270,120,58,81,55,175,161,318,43,89,42,445,491,318,204,325,292,239,149,388,354,334,434,488,344,250,156,291,274,153,153,11,490,20,189,150,495,354,326,231,373,29,432,104,279,456,333,14,468,359,218,280,295,51,104,20,335,183,137,369,43,104,308,3,454,422,81,254,56,384,70,423,280,140,259,81,332,124,443,262,424,186,268,75,332,422,23,187,405,399,13,385,52,97,96,218,223,366,144,24,313,188,359,121,166,388,185,360,453,3,349,307,473,160,262,448,97,215,302,421,8,349,270,127,85,361,480,215,200,468,28,488,279,430,424,202,345,19,380,142,419,400,195,427,254,171,88,131,126,118,81,252,195,253,164,444,275,263,188,494,285,253,236,470,220,183,213,292,497,444,356,458,445,439,201,254,427,461,122,121,468,108,160,82,94,15,5,327,320,255,293,167,222,420,301,383,442,265,443,317,8,196,463,152,246,148,244,154,169,453,309,189,450,479,268,294,314,75,459,373,175,129,265,463,320,85,214,374,288,306,117,252,268,310,267,317,105,27,82,161,11,35,156,287,32,381,260,56,58,454,225,424,453,394,66,316,361,336,63,343,439,101,195,354,99,322,419,195,303,149,213,210,213,68,47,207,155,490,116,145,382,455,47,62,215,97,240,421,56,438,452,158,353,127,149,130,376,164,427,40,442,465,297,89,407,434,374,141,234,68,205,392,298,139,145,198,186,130,469,295,114,62,101,44,460,158,451,371,304,452,36,96,213,247,252,198,277,395,422,446,337,9,217,109,338,116,112,341,225,229,283,52,93,312,287,496,147,428,210,28,401,39,101,145,188,216,432,242,72,23,166,5,140,268,190,112,211,452,423,121,189,207,261,438,215,304,417,58,339,4,5,138,418,108,462,21,119,102,168,452,39,220,270,218,167,213,135,410,316,286,262,12,124,295,175,88,138,295,131,286,402,495,280,259,167,111,367,11,183,279,5,32,414,332,62,210,195,433,209,265,473,438,249,393,188,89,489,111,430,448,366,253,466,44,472,394,312,120,417,147,151,119,273,131,194,370,287,204,19,43,70,315,271,437,101,348,240,261,392,192,409,7,453,278,334,330,44,215,222,356,126,221,35,20,82,408,449,394,491,300,407,23,196,428,361,182,117,326,24,64,375,124,217,480,267,73,103,400,408,274,228,262,96,222,180,304,171,207,69,325,457,118,276,177,50,138,323,433,1,358,497,52,262,142,89,316,71,142,71,223,288,464,314,250,411,325,408,446,96,240,281,109,142,123,321,226,181,343,221,14,105,28,422,212,418,271,134,414,130,346,296,237,176,200,432,25,377,498,37,286,390,79,326,124,448,145,254,420,51,110,52,366,262,420,7,1,257,345,114,134,46,276,169,93,245,282,247,57,148,470,262,500,80,193,299,494,109,114,159,209,438,43,218,484,319,307,356,28,465,202,371,476,374,168,231,143,406,162,94,28,319,351,244,9,234,89,216,81,327,438,68,29,353,203,433,424,108,472,138,494,157,405,240,133,326,103,352,123,407,485,77,370,422,355,273,368,156,491,105,383,18,135,42,86,373,21,445,194,206,183,247,6,90,159,209,316,67,15,30,194,77,146,60,497,266,202,99,265,479,340,470,243,48,259,280,386,8,309,184,315,11,168,449,321,127,62,499,169,131,182,184,299,451,293,248,335,354,374,442,185,2,243,204,245,459,417,314,448,24,479,248,53,85,160,228,333,24,496,485,68,428,235,55,26,85,383,416,499,2,85,428,386,145,95,54,402,282,261,61,192,104,32,312,134,231,353,114,12,453,136,83,306,330,379,469,303,347,194,412,205,290,350,147,290,240,163,392,372,386,308,360,411,453,439,444,330,270,29,281,393,306,287,37,410,339,444,92,159,13,4,356,1,27,133,198,289,35,4,355,201,113,408,223,496,289,236,345,311,36,356,440,277,388,303,324,172,497,268,411,217,188,328,137,28,311,138,433,197,371,376,421,469,437,339,130,55,6,255,241,275,263,12,55,370,74,102,63,388,295,214,191,445,115,199,286,173,252,6,364,336,155,402,440,422,317,405,321,328,339,436,423,13,94,391,387,418,140,379,350,271,497,63,366,371,230,228,159,324,6,84,436,305,312,26,339,454,290,320,49,3,53,472,184,205,422,452,107,336,382,319,181,492,431,89,66,412,150,102,461,397,323,392,344,424,72,469,327,288,102,386,281,493,354,330,457,468,30,292,127,256,1,44,373,499,158,454,50,111,286,72,74,101,45,151,52,250,277,133,111,468,339,46,161,221,232,175,147,225,33,141,195,327,256,12,149,268,385,469,463,120,326,443,156,467,227,55,384,309,250,236,171,451,420,152,226,352,26,477,437,340,234,121,300,100,195,18,145,296,132,67,263,131,458,385,274,443,113,210,73,7,439,134,155,35,254,405,327,112,245,238,339,41,286,111,141,299,187,243,397,78,100,310,212,329,291,477,73,258,484,480,226,107,161,473,431,286,399,200,188,443,199,261,26,425,467,179,78,308,174,373,34,390,164,408,413,125,171,91,471,6,63,135,491,50,223,147,20,12,481,453,277,420,58,350,113,211,56,74,491,448,262,386,314,180,172,8,294,387,144,135,374,281,46,57,109,255,369,423,441,135,163,360,142,51,437,378,144,67,125,279,280,398,443,109,420,373,404,407,36,44,78,18,109,19,77,205,482,474,459,81,486,453,457,221,296,409,5,292,255,181,18,126,110,190,91,491,497,304,436,115,90,130,423,195,293,210,461,271,112,331,418,106,268,21,48,81,10,8,8,216,415,210,200,455,12,420,376,174,110,209,405,166,324,323,85,78,204,72,240,63,26,274,377,36,197,83,79,23,184,94,416,166,450,272,122,139,331,65,113,496,468,88,454,47,434,210,263,371,252,404,464,302,241,256,428,41,403,12,118,163,123,443,268,58,238,373,272,289,37,80,170,64,382,482,179,107,253,132,81,119,428,238,157,215,144,172,331,400,253,166,465,414,25,401,193,241,371,469,70,249,440,133,339,126,313,126,417,41,464,39,224,49,373,442,397,118,294,262,371,230,124,95,121,479,272,378,197,274,419,358,265,347,55,132,241,367,291,484,82,416,171,325,250,133,177,33,138,180,2,391,446,330,375,319,9,346,476,289,26,402,212,290,436,248,450,474,451,78,46,212,28,271,286,341,45,332,370,158,275,291,333,453,279,244,370,356,353,439,315,426,403,159,349,424,27,130,182,278,221,359,297,427,179,399,58,116,213,248,472,37,64,417,441,246,99,376,385,88,285,406,131,422,485,223,318,12,311,492,70,68,360,134,1,212,261,258,226,397,336,279,353,178,142,149,245,110,187,250,20,218,238,280,423,216,178,461,40,99,402,23,406,428,446,364,88,79,136,410,230,83,320,128,163,90,72,440,117,263,84,239,84,266,407,476,175,316,384,241,177,36,306,308,370,51,69,444,316,356,311,154,10,97,236,268,480,428,142,437,357,83,297,374,40,305,324,399,356,30,286,24,496,187,286,152,71,263,208,418,84,244,330,419,267,216,284,397,491,192,224,376,378,353,91,135,196,353,105,243,408,243,289,13,202,320,299,174,247,87,172,154,164,162,325,139,336,70,181,329,149,375,227,457,47,477,304,11,485,336,275,238,149,297,499,296,228,168,219,331,448,264,328,481,113,6,25,245,329,106,121,184,372,355,457,388,152,131,86,309,65,422,185,99,39,462,114,453,471,458,332,401,138,235,388,238,462,192,305,29,446,356,470,212,43,486,264,94,458,492,280,421,158,57,159,130,68,366,426,257,10,42,345,462,295,457,164,129,135,49,225,15,396,52,348,447,46,400,476,158,95,291,154,375,8,27,289,248,222,55,173,46,29,56,447,481,329,277,156,450,24,88,138,156,294,339,261,284,137,179,87,316,161,280,145,47,381,183,28,99,496,419,313,214,177,301,221,67,147,104,205,166,282,313,251,491,432,428,399,487,373,429,47,93,471,28,100,326,107,97,219,57,406,193,192,277,137,375,286,126,397,260,434,324,244,148,24,356,118,375,225,168,337,461,195,247,118,442,255,67,65,466,322,478,481,381,289,13,149,372,285,448,280,459,327,68,274,258,437,27,101,412,91,4,273,427,3,120,240,297,210,306,495,28,457,432,495,180,425,76,477,84,243,396,3,60,196,126,448,134,278,333,240,396,246,66,285,67,76,287,159,252,206,144,81,305,445,365,134,281,470,89,358,141,286,194,366,104,214,59,123,120,252,245,107,250,492,438,174,178,93,489,303,368,14,19,152,173,148,24,146,276,290,468,190,489,173,115,21,109,404,2,490]
len(big_time)
from typing import List
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        res = 0
        for i,vi in enumerate(time):
            for j,vj in enumerate(time[i+1:], start=i+1):
                if (vi + vj) % 60 == 0:
                    res += 1         
        return res
        
# 12 sec
# %time Solution().numPairsDivisibleBy60(big_time)
from typing import List
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        res = 0
        for i,vi in enumerate(time):
            for j,vj in enumerate(time[i+1:], start=i+1):
                if vi % 60 + vj % 60 == 60:
                    res += 1         
        return res
        
Solution().numPairsDivisibleBy60([30,20,150,100,40])
# 12 sec
# %time Solution().numPairsDivisibleBy60(big_time)
# readable var
def sum_of_integers(n):
    """returns 1+2+3+...+n 
    
    formula: https://www.onlinemathlearning.com/image-files/arithmetic-series.png
    """
    a1 = 1
    d = 1
    an = (n-1)*d
    sn = (n/2)*(2*a1+an)
    return int(sn)


from typing import List
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        from collections import Counter

        cnt = Counter()
        for t in time:
            r = t%60
            cnt[r] += 1

        numPairs = 0
        
        numPairs += sum_of_integers(cnt[0]-1) # corner case #1
        numPairs += sum_of_integers(cnt[30]-1) # corner case #2
        for a in range(1,30):
            b = 60 - a
            if cnt[a] and cnt[b]:
                numPairs += cnt[a] * cnt[b]
            
        return numPairs
# faster var Runtime: 232 ms

def sum_of_integers(n):
    """returns 1+2+3+...+n 
    
    formula: https://www.onlinemathlearning.com/image-files/arithmetic-series.png
    """
    return int((n+n*n) / 2)


from typing import List
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        from collections import Counter

        cnt = Counter()
        for t in time:
            r = t%60
            cnt[r] += 1

        numPairs = 0
        
        numPairs += sum_of_integers(cnt[0]-1) # corner case #1
        numPairs += sum_of_integers(cnt[30]-1) # corner case #2
        for a in range(1,30):
            b = 60 - a
            if cnt[a] and cnt[b]:
                numPairs += cnt[a] * cnt[b]
            
        return numPairs
# faster var Runtime: 236 ms

def sum_of_integers(n):
    """returns 1+2+3+...+n 
    
    formula: https://www.onlinemathlearning.com/image-files/arithmetic-series.png
    """
    return int((n+n*n) / 2)


from typing import List
from collections import Counter
import itertools
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:

        cnt = Counter()
        for t in time:
            r = t%60
            cnt[r] += 1

        numPairs = 0
        numPairs += sum_of_integers(cnt[0]-1) # corner case #1
        numPairs += sum_of_integers(cnt[30]-1) # corner case #2
        for p in itertools.product(sorted(cnt), repeat=2):
            a,b = p
            if 0 < a < b:
                if a + b == 60:
                    if a != b:
                        numPairs += cnt[a] * cnt[b]
            
        return numPairs
# faster var Runtime: 236 ms

def sum_of_integers(n):
    """returns 1+2+3+...+n 
    
    formula: https://www.onlinemathlearning.com/image-files/arithmetic-series.png
    """
    return 


from typing import List
from collections import Counter
import itertools
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:

        cnt = Counter()
        for t in time:
            r = t%60
            cnt[r] += 1

        numPairs = 0
        n = cnt[0]
        numPairs += int((n+n*n) / 2)
        numPairs += sum_of_integers(cnt[30]-1) # corner case #2
        numPairs += int((n+n*n) / 2)
        for p in itertools.product(sorted(cnt), repeat=2):
            a,b = p
            if 0 < a < b:
                if a + b == 60:
                    if a != b:
                        numPairs += cnt[a] * cnt[b]
            
        return numPairs
def testeq__(want, time):
    got = Solution().numPairsDivisibleBy60(time)
    if got != want:
        raise ValueError(f"Got: {got}, want: {want}")
# testeq__(1, [418,204,77,278,239,457,284,263,372,279,476,416,360,18])

# testeq__(3, [60,60,60])

# testeq__(0, [439,407,197,191,291,486,30,307,11])

# testeq__(3, [30,20,150,100,40])

# inp = [269,230,318,468,171,158,350,60,287,27,11,384,332,267,412,478,280,303,242,378,129,131,164,467,345,146,264,332,276,479,284,433,117,197,430,203,100,280,145,287,91,157,5,475,288,146,370,199,81,428,278,2,400,23,470,242,411,470,330,144,189,204,62,318,475,24,457,83,204,322,250,478,186,467,350,171,119,245,399,112,252,201,324,317,293,44,295,14,379,382,137,280,265,78,38,323,347,499,238,110,18,224,473,289,198,106,256,279,275,349,210,498,201,175,472,461,116,144,9,221,473]
# testeq(105, inp)<jupyter_output><empty_output><jupyter_text>Binary Search Tree Iterator<jupyter_code># Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
    def __repr__v1(self):
        return self.val
    
    def __repr__(self):
        vl = 'none' if self.left is None else self.left.val
        vr = 'none' if self.right is None else self.right.val
        return f"{vl} <- {self.val} -> {vr}"
        
    def __repr__v2(self):
        vl = 'none' if self.left is None else self.left.val
        vr = 'none' if self.right is None else self.right.val
        return f"""
    {self.val}
  /   \      
{vl}    {vr}
"""


from typing import List, Union, Iterable

class TreeBuilder:
    def __init__(self):
        pass
    
        
    def better_next(self, iterable:Iterable):
        try:
            return next(iterable)
        except StopIteration:
            return None
        
    def build(self, node:TreeNode):
        vl = self.better_next(self.vals)
        vr = self.better_next(self.vals)

        if vl: node.left = TreeNode(vl)
        if vr: node.right = TreeNode(vr)

        if vl: self.build(node.left)
        if vr: self.build(node.right)
            
    def __call__(self, root:List[Union[int, None]]):
        self.vals = iter(root)
        node = TreeNode(val=next(self.vals))
        self.build(node)
        
        return node
null = None
root_lst = [1,2,3,4,5,null,null,null,null,6,7,8,9]
root_lst = [3,9,20,null,null,15,7]
root_lst = [7, 3, 15, null, null, 9, 20]<jupyter_output><empty_output><jupyter_text>Let's build a wikipedia Tree to debug our algohttps://www.wikiwand.com/en/Tree_traversal![](https://upload.wikimedia.org/wikipedia/commons/thumb/d/dc/Sorted_binary_tree_ALL.svg/300px-Sorted_binary_tree_ALL.svg.png)Depth-first traversal of an example tree:pre-order (red): F, B, A, D, C, E, G, I, H;**in-order (yellow): A, B, C, D, E, F, G, H, I;**post-order (green): A, C, E, D, B, H, I, G, F.**In-order (LNR) algo:**1. Traverse the left subtree by recursively calling the in-order function.1. Access the data part of the current node.1. Traverse the right subtree by recursively calling the in-order function.<jupyter_code>root_lst = ["F", "B", "G", "A", "D", null, null, "C", "E", null, null, null, null, null, "I", "H"]

builder = TreeBuilder()

root = builder(root_lst)
# print(root)
# print(root.left)
# print(root.left.left)
# print(root.left.right)
# print(root.left.right.left)
# print(root.left.right.right)
# print(root.right)
# print(root.right.right)
class BSTIterator:
    def __init__(self, root: TreeNode):
        self.will_visit = {root.val:True}
        self.generator = self.inorder(root)

    def next(self) -> int:
        next_node = next(self.generator)
#         if next_node.val in ('H', 'I'):
#             print('pb')
        return next_node.val

    def hasNext(self) -> bool:
        keys_remaining = self.will_visit.keys()
        return bool(keys_remaining)
    
    def __repr__(self):
        return str(self.will_visit)
    
        
    def inorder(self, node:TreeNode):
        if node is None:
            return
        if node.val  : self.will_visit[node.val] = True
        if node.right: self.will_visit[node.right.val] = True
        if node.left : self.will_visit[node.left.val ] = True

        # continue DFS left
        yield from self.inorder(node.left)
        # NOW TIME TO YIELD
        self.will_visit.pop(node.val)
#         print(f"popped {node.val}, remaining: {self.will_visit.keys()}")
#         print(node.val)
        yield node
        # now go on to DFS rigth
        yield from self.inorder(node.right)<jupyter_output><empty_output><jupyter_text>**Faster solution from the internet**<jupyter_code>class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = []
        self.load_min(root)

    def load_min(self, root):
        while root:
            self.stack.append(root)
            root = root.left
            
    def next(self) -> int:
        node = self.stack.pop()
        if node.right:
            self.load_min(node.right)
        return node.val
            

    def hasNext(self) -> bool:
        return len(self.stack) > 0<jupyter_output><empty_output><jupyter_text>Valid Mountain Arrayhttps://leetcode.com/explore/challenge/card/december-leetcoding-challenge/570/week-2-december-8th-december-14th/3561/<jupyter_code># my solution
class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        # all corner cases in one
        if len(arr)<3 or arr[0]>=arr[1]:
            return False
        
        should_increase = True
        for i in range(1, len(arr)):
            diff = arr[i] - arr[i-1]
            if should_increase:
                if diff > 0:
                    continue
                elif diff < 0:
                    # we have reached an inflection, swap var
                    should_increase = False # swap variable
                    continue
                elif diff == 0:
                    return False
                    print("1 NOT A MOUNTAIN!!!")
                    break
            else:
                if diff < 0:
                    continue
                elif diff >= 0:
                    return False
                    print("2 NOT A MOUNTAIN!!!")
                    break

        # if you are here, you should have flipped the increase direction
        if should_increase:
            # if still at increasing, you never went through an inflection
            return False
        else:
            # if you are here, all is ok, arr is mountain
            return True
# cleaner code from the internet
class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        if len(arr)<3 or arr[0]>=arr[1]:
            return False
        
        uphill = True
        
        for i in range(1,len(arr)):
            if uphill:
                if arr[i-1]>=arr[i]:
                    uphill = False
            if not uphill:
                if arr[i-1]<=arr[i]:
                    return False
        return not uphill
def testeq_(want, arr):
    got = Solution().validMountainArray(arr)
    if got != want:
        raise ValueError(f"Got: {got}, want: {want}")
testeq_(True, [0, 1, 2, 3, 2, 1])
testeq_(True, [0, 1, 2, 3, 2, -1])
testeq_(False, [0, 1, 2, 3, 2, -1, 1])
testeq_(False, [0, 1, 2, 3, 2, -1, -1])
testeq_(False, [0, 1, 2, 3, 4])
testeq_(False, [0, 1, 2, 2, 4])
testeq_(False, [5, 4, 7])
testeq_(False, [2,1])<jupyter_output><empty_output><jupyter_text>Remove Duplicates from Sorted Array II:warning: Your runtime beats 97.91 % of python3 submissions.<jupyter_code>from typing import List

class Solution:
    def removeDuplicates(self, arr: List[int]) -> int:
        N = len(arr)
        for i in range(N-2):
            # popping from left to right poses index challenges
            # so let's pop from right to left!
            
            # first, for i'th element from the end, let's get it
            # and it's two left neigbours
            a,b,c = arr[N-3-i:N-i]
            
            # if all are equal, we can safely pop the candidate
            if a == b == c: 
                # triple duplicate!
                # time to pop rightmost element (arr[N-i-1])
                arr.pop(N-i-1)
        return arr
Solution().removeDuplicates([5])
Solution().removeDuplicates([5,5])
Solution().removeDuplicates([5,5,5])
m = Solution().removeDuplicates
testeq([0,0,1,1,2,3,3], m , [0,0,1,1,1,1,2,3,3])
testeq([0,0], m, [0,0])
testeq([0,0], m, [0,0,0,0])
testeq([0],   m, [0])<jupyter_output><empty_output><jupyter_text>Palindrome Partitioninghttps://leetcode.com/explore/challenge/card/december-leetcoding-challenge/570/week-2-december-8th-december-14th/3565/tbd  Week 3  Validate Binary Search Tree<jupyter_code>tnb = TreeNodeBuilder()
def nanmax(a,b):
    if a is None and b is None:
        return None
    elif a is None and b is not None:
        return b
    elif a is not None and b is None:
        return a
    else:
        return max(a,b)
assert nanmax(1,3)==3
assert nanmax(None,3)==3
assert nanmax(1,None)==1
assert nanmax(None, None) is None
def nanmin(a,b):
    if a is None and b is None:
        return None
    elif a is None and b is not None:
        return b
    elif a is not None and b is None:
        return a
    else:
        return min(a,b)
assert nanmin(1,3)==1
assert nanmin(None,3)==3
assert nanmin(1,None)==1
assert nanmin(None, None) is None
def validate(node, less_than=None, greater_than=None):
    # validate that node.val is between greater_than, less_than
    if node is None:
        return True
    
    if less_than is not None:
        if node.val >= less_than:
            return False
        
    if greater_than is not None:
        if node.val <= greater_than:
            return False
    
    L = validate(      node = node.left,
                 less_than = nanmin(node.val, less_than), # LEFT => change min value
                 greater_than = greater_than
                )
    
    R = validate(      node = node.right,
                 less_than = less_than,
                 greater_than = nanmax(node.val, greater_than), # RIGHT => change max value
                )
    
    return (L and R)
    
root = tnb([2,1,3])
assert validate(root)
root
root = tnb([5,1,4,None,None,3,6])
assert not validate(root)
root = tnb([5,4,6,None, None,3,7])
assert not validate(root)
root = tnb([1,1])
assert not validate(root)
tnb = TreeNodeBuilder()
root = tnb([3,1,5, 0, 2, None, None,None, None, 4, 6])
root
validate(root)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.21286455331412105, 'fraction_numerical': 0.4840115273775216, 'mean_word_length': 8.291099925029453, 'pattern_counts': {'":': 0, '<': 88, '<?xml version=': 0, '>': 100, 'https://': 17, 'lorem ipsum': 0, 'www.': 5, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '33256', 'license': 'Apache-2.0', 'n_tokens_mistral': 66553, 'n_tokens_neox': 39554, 'n_words': 2928, 'path': '_notebooks/2020-11-28-leetcode-december.ipynb', 'repo_name': 'ddobrinskiy/blog', 'size': '86750'}