text:
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
  <component name="Encoding" addBOMForNewFiles="with NO BOM" />
</project>

repo_language: Jupyter Notebook


text:
<component name="MarkdownNavigator.ProfileManager">
  <settings default="" pdf-export="" />
</component>


text:
<component name="InspectionProjectProfileManager">
  <profile version="1.0">
    <option name="myName" value="Project Default" />
    <inspection_tool class="PyPep8Inspection" enabled="true" level="WEAK WARNING" enabled_by_default="true">
      <option name="ignoredErrors">
        <list>
          <option value="W29" />
          <option value="E501" />
          <option value="W29" />
          <option value="E501" />
        </list>
      </option>
    </inspection_tool>
  </profile>
</component>


text:
class HashTable:

    def __init__(self, size):
        self._size = size
        self._table = [[] for _ in range(size)]

    def _hash(self, key):
        return #Complete it

    def insert(self, key, value):
        return #Complete it

    def get(self, key):
        return #Complete it


text:
from hash_table import HashTable

def answer(arr, k):
    return #Complete the function


text:
import random
from task import answer
from test_helper import failed

def solution(arr, k):
    sums = {}
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if k - arr[i] - arr[j] in sums:
                pair = sums[k - arr[i] - arr[j]]
                if i not in pair and j not in pair:
                    return (arr[i], arr[j]) + (arr[pair[0]], arr[pair[1]])
            sums[arr[i] + arr[j]] = (i, j)
    return None

def generate_test():
    return [random.randint(0, 10 ** 12) for i in range(random.randint(10, 1000))]

if __name__ == '__main__':
    if answer([0, 0, 0, 0], 100) is not None:
        failed("Wrong Answer!")
    if set(answer([10, 20, 20, 10, 40, 100], 160)) != {100, 10, 40, 10}:
        failed("Wrong Answer!")
    for i in range(5):
        arr = generate_test()
        values = random.sample(arr, 4)
        result = answer(arr, sum(values))
        if result is None or len(set(result)) < 4 or sum(result) != sum(values):
            failed("Wrong Answer!")
    for i in range(3):
        arr = generate_test()
        value = random.randint(0, 10 ** 12)
        result = answer(arr, value)
        ans = solution(arr, value)
        if ans is None and result is not None:
            failed("Wrong Answer!")
        elif ans is not None:
            if len(set(result)) < 4 or sum(result) != sum(ans):
                failed("Wrong Answer!")


text:
import string

def setup(dictionary):
    return #Complete the function

def suggestions(word):
    return #Complete the function


text:
import task
import random
import string
from test_helper import failed

def sol_setup(dictionary):
    global words
    words = set(dictionary)

def sol_suggestions(word):
    result = set()
    is_legit = word in words
    if not is_legit:
        # add char
        for i in range(len(word) + 1):
            for char in string.ascii_lowercase:
                possible = word[:i] + char + word[i:]
                if possible in words:
                    result.add(possible)
        # remove char
        for i in range(len(word)):
            possible = word[:i] + word[i + 1:]
            if possible in words:
                result.add(possible)
        # change char
        for i in range(len(word)):
            for char in string.ascii_lowercase:
                possible = word[:i] + char + word[i + 1:]
                if possible in words:
                    result.add(possible)
    return is_legit, result

if __name__ == '__main__':
    task.setup({"abc", "abcd", "g", "e", "ggh"})
    if task.suggestions("ggh") != (True, set()):
        failed("Wrong Answer!")
    if task.suggestions("abcz") != (False, {"abcd", "abc"}):
        failed("Wrong Answer!")
    if task.suggestions("gh") != (False, {"g", "ggh"}):
        failed("Wrong Answer!")
    if task.suggestions("a") != (False, {"g", "e"}):
        failed("Wrong Answer!")
    if task.suggestions("bbb") != (False, set()):
        failed("Wrong Answer!")
    if task.suggestions("bbc") != (False, {"abc"}):
        failed("Wrong Answer!")
    dic = {''.join(random.choice(string.ascii_lowercase) for _ in range(random.randint(1, 50))) for _ in range(10000)}
    test = {''.join(random.choice(string.ascii_lowercase) for _ in range(random.randint(1, 10))) for _ in range(10000)}
    task.setup(dic)
    sol_setup(dic)
    for word in test:
        if task.suggestions(word) != sol_suggestions(word):
            failed("Wrong Answer!")


text:
class HashTable:
    class _Cell:
        def __init__(self, key: int, value: object) -> None:
            self._key = key
            self._value = value
            self._isDeleted = False

        def get_key(self):
            return self._key

        def get_value(self):
            return self._value

        def is_deleted(self):
            return self._isDeleted

        def delete(self):
            self._isDeleted = True

    def __init__(self, size):
        self._size = size
        self._table = [None for _ in range(size)]

    def _hash(self, key, i):
        return (key + i) % self._size

    def insert(self, key, value):
        return #Complete it

    def delete(self, key):
        return #Complete it

    def get(self, key):
        return #Complete it


text:
from hash_table import HashTable

class LRUCache:
    def __init__(self, size):
        #Complete it

    def get(self, key):
        #Complete it

    def add(self, key, value):
        #Complete it


text:
from task import LRUCache
from test_helper import failed
import random

class LRUCacheSol:
    def __init__(self, size):
        self._time_queue = Queue(size)

    def get(self, key):
        return self._time_queue.get(key)

    def add(self, key, value):
        self._time_queue.push(key, value)

class Queue:
    class Node:
        def __init__(self, prev, key, value, next):
            self.prev = prev
            self.key = key
            self.value = value
            self.next = next

    def __init__(self, size):
        self._size = 0
        self._max = size
        self._front = None
        self._rear = None
        self._hashTable = {}

    def push(self, key, value):
        if self._rear is None:
            self._rear = Queue.Node(None, key, value, None)
            self._front = self._rear
        else:
            self._rear.prev = Queue.Node(None, key, value, self._rear)
            self._rear = self._rear.prev
        self._size += 1
        if self._size > self._max:
            self.pop()
        self._hashTable[key] = self._rear

    def delete(self, key):
        node = self._hashTable.get(key)
        if node.prev is not None:
            node.prev.next = node.next
        else:
            self._rear = node.next
        if node.next is not None:
            node.next.prev = node.prev
        else:
            self._front = node.prev
        self._hashTable.pop(key)
        self._size -= 1

    def pop(self):
        key = None
        if self._front is not None:
            key = self._front.key
            self._front = self._front.prev
            self._front.next = None
            self._hashTable.pop(key, None)
        self._size -= 1
        return key

    def get(self, key):
        if key not in self._hashTable:
            return None
        node = self._hashTable[key]
        self.delete(key)
        self.push(key, node.value)
        return node.value

if __name__ == '__main__':
    simple_cache = LRUCache(5)
    simple_cache.add(10 ** 9, 5)
    simple_cache.add(3, 20)
    simple_cache.add(4, 30)
    if simple_cache.get(10 ** 9) != 5 or simple_cache.get(3) != 20 or simple_cache.get(4) != 30:
        failed("Wrong Answer!")
    simple_cache.add(100, 1)
    simple_cache.add(101, 2)
    simple_cache.get(10 ** 9)
    simple_cache.add(102, 3)
    if simple_cache.get(3) is not None:
        failed("Wrong Answer!")
    if simple_cache.get(10 ** 9) != 5:
        failed("Wrong Answer!")
    simple_cache.get(4)
    simple_cache.get(100)
    simple_cache.add(0, 0)
    if simple_cache.get(101) is not None:
        failed("Wrong Answer!")

    cache = LRUCache(100)
    sol = LRUCacheSol(100)
    keys = random.sample(range(0, 10 ** 10), 100000)
    added = []
    if cache.get(1) is not None:
        failed("Wrong Answer!")
    for key in keys:
        if random.randint(0, 1) == 0:
            cache.add(key, key / 3)
            sol.add(key, key / 3)
            added.append(key)
        elif len(added) > 0:
            key = random.choice(added)
            if cache.get(key) != sol.get(key):
                failed("Wrong Answer!")


text:
def period(str):
    return "" #Complete the function


text:
import random
import string
import task
from test_helper import failed

def sol(str):
    p, q = 27, 10 ** 9 + 7
    hash_list = sol_hash(str, q, p)
    offset = p
    for T in range(1, len(str)):
        if sol_is_period(hash_list, T, offset, q):
            return T
        offset = (offset * p) % q
    return None

def sol_is_period(hash_list, T, offset, q):
    return (hash_list[len(hash_list) - T - 1] * offset) % q == (hash_list[len(hash_list) - 1] - hash_list[T - 1]) % q

def sol_hash(str, q, p):
    hash_list = [ord(str[0]) - ord('a') + 1]
    s = 1
    for i in range(1, len(str)):
        s = (s * p) % q
        hash_list.append((hash_list[i - 1] + (ord(str[i]) - ord('a') + 1) * s) % q)
    return hash_list

def generate_test():
    T = random.randint(0, 10 ** 4)
    return ''.join(random.choice(string.ascii_lowercase) for i in range(T)) * (10 ** 5 // T)

if __name__ == '__main__':
    # put_limit(10)
    # try:
    for i in range(5):
        str = generate_test()
        if sol(str) != task.period(str):
            failed("Wrong Answer!")
    # except Exception:
    #     failed("Timed Out!")


text:
class DisjointSet(object):
    def __init__(self, n):
        self.n = n
        # list of components of each set
        self.set_lists = [[i] for i in range(n)]
        # pointing to the set of each component
        self.set = [i for i in range(n)]

    def find(self, u):
        return self.set[u]

    def unite(self, u, v):
        u_set, v_set = self.find(u), self.find(v)
        if u_set == v_set:  # u and v are in the same component
            return False

        # set u to the smaller list
        if len(self.set_lists[u_set]) > len(self.set_lists[v_set]):
            u_set, v_set = v_set, u_set

        # merging the smaller list into the large list
        for i in self.set_lists[u_set]:
            self.set_lists[v_set].append(i)
            # updating set of each element
            self.set[i] = v_set

        return True

    def get_count(self):
        count = 0
        for i in range(self.n):
            if self.set[i] == i:
                count += 1
        return count

def solve(n, points):
    assert len(points) == n
    #Implement the function


text:
from test_helper import *
from task import solve

if __name__ == '__main__':
    manual_tests = [
        (14, [(25, 23), (499, 406), (193, 266), (823, 751), (219, 227), (101, 138), (978, 992), (43, 74), (997, 932),
              (237, 189), (634, 538), (774, 740), (842, 767), (742, 802)], 13),

        (6, [(535, 699), (217, 337), (508, 780), (180, 292), (393, 112), (732, 888)], 5),

        (7, [(948, 946), (130, 130), (761, 758), (941, 938), (971, 971), (387, 385), (509, 510)], 6),

        (9, [(811, 859), (656, 676), (76, 141), (945, 951), (497, 455), (18, 55), (335, 294), (267, 275), (656, 689)],
         7),

        (1, [(321, 88)], 0),
        (11,
         [(798, 845), (722, 911), (374, 270), (629, 537), (748, 856), (831, 885), (486, 641), (751, 829), (609, 492),
          (98, 27), (654, 663)], 10),
        (17,
         [(660, 646), (440, 442), (689, 618), (441, 415), (922, 865), (950, 972), (312, 366), (203, 229), (873, 860),
          (219, 199), (344, 308), (169, 176), (961, 992), (153, 84), (201, 230), (987, 938), (834, 815)], 16),
        (24, [(171, 35), (261, 20), (4, 206), (501, 446), (961, 912), (581, 748), (946, 978), (463, 514), (841, 889),
              (341, 466), (842, 967), (54, 102), (235, 261), (925, 889), (682, 672), (623, 636), (268, 94), (635, 710),
              (474, 510), (697, 794), (586, 663), (182, 184), (806, 663), (468, 459)], 21),
        (2, [(2, 1), (4, 1)], 0),
        (2, [(2, 1), (1, 2)], 1),
        (28,
         [(462, 483), (411, 401), (118, 94), (111, 127), (5, 6), (70, 52), (893, 910), (73, 63), (818, 818), (182, 201),
          (642, 633), (900, 886), (893, 886), (684, 700), (157, 173), (953, 953), (671, 660), (224, 225), (832, 801),
          (152, 157), (601, 585), (115, 101), (739, 722), (611, 606), (659, 642), (461, 469), (702, 689), (649, 653)],
         25),
    ]

    for test in manual_tests:
        n, points, ans1 = test
        ans2 = solve(n, points)
        if ans1 != ans2:
            failed("Wrong Answer! Input: {}, your output: {}, answer: {}".format((n, points), ans2, ans1))


text:
class Node(object):
    def __init__(self, label):
        self.label = label
        self.par = self
        self.rank = 0
        self.min = 0

class DisjointSet(object):
    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n)]

    def find(self, u):
        if u == u.par:
            return u
        return self.find(u.par)

    def union(self, u, v):
        u, v = self.find(u), self.find(v)
        if u == v:  # u and v are in the same component
            return False

        # making v the vertex with better rank
        if u.rank > v.rank:
            u, v = v, u

        # merging two components
        u.par = v

        # updating maximum depth as rank
        if u.rank == v.rank:
            v.rank += 1

        v.min = min(v.min, u.min)

        return True

    # Returns a list of components where each component is a list of values
    def get_all_components(self):
        comps = [[] for _ in range(self.n)]
        for node in self.nodes:
            comps[self.find(node).label].append(node.label)

        comps = [i for i in comps if i]  # Remove empty lists
        return comps

def solve(n, m, words, prices, groups, message):
    assert n == len(words)
    assert n == len(prices)
    assert m == len(message)

    #Implement the function


text:
from test_helper import *
from task import solve
import string, random

class Node(object):
    def __init__(self, label):
        self.label = label
        self.par = self
        self.rank = 0
        self.min = 0

class DisjointSet(object):
    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n)]

    def find(self, u):
        if u == u.par:
            return u
        return self.find(u.par)

    def union(self, u, v):
        u, v = self.find(u), self.find(v)
        if u == v:  # u and v are in the same component
            return False

        # making v the vertex with better rank
        if u.rank > v.rank:
            u, v = v, u

        # merging two components
        u.par = v

        # updating maximum depth as rank
        if u.rank == v.rank:
            v.rank += 1

        v.min = min(v.min, u.min)

        return True

    # Returns a list of components where each component is a list of values
    def get_all_components(self):
        comps = [[] for _ in range(self.n)]
        for node in self.nodes:
            comps[self.find(node).label].append(node.label)

        comps = [i for i in comps if i]  # Remove empty lists
        return comps

def solve2(n, m, words, prices, groups, message):
    dsu = DisjointSet(n)
    indices = {}
    for i in range(n):
        dsu.nodes[i].min = prices[i]
        indices[words[i]] = i

    for group in groups:
        for i in range(len(group)):
            dsu.union(dsu.nodes[group[0]], dsu.nodes[group[i]])

    price = 0
    for word in message:
        price += dsu.find(dsu.nodes[indices[word]]).min

    return price

def string_generator(size, chars=string.ascii_lowercase):
    return ''.join(random.choice(chars) for _ in range(size))

def partition(lst, n):
    random.shuffle(lst)
    division = len(lst) / float(n)
    return [lst[int(round(division * i)): int(round(division * (i + 1)))] for i in range(n)]

if __name__ == '__main__':
    manual_tests = [
        (5, 4, ['i', 'loser', 'am', 'the', 'second'], [100, 1, 1, 5, 10], [[0], [2], [1, 4], [3]],
         ['i', 'am', 'the', 'second'], 107),

        (5, 4, ['i', 'loser', 'am', 'the', 'second'], [100, 20, 1, 5, 10], [[0], [2], [1, 4], [3]],
         ['i', 'am', 'the', 'second'], 116),

        (1, 1, ['a'], [1000000000], [[0]], ['a'], 1000000000),

        (1, 10, ['a'], [1000000000], [[0]], ['a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'], 10000000000),
    ]

    for test in manual_tests:
        n, m, words, prices, groups, message, ans1 = test
        ans2 = solve(n, m, words, prices, groups, message)
        if ans1 != ans2:
            failed("Wrong Answer! Input: {}, your output: {}, answer: {}".format((words, prices, groups, message), ans2,
                                                                                ans1))

        random_tests = 10
        for i in range(random_tests):
            n = random.randint(1000, 10000)
            m = random.randint(1000, 10000)
            k = random.randint(1, min(10, n))
            words = [string_generator(random.randint(10, 20)) for _ in range(n)]
            prices = [random.randint(1, 10000) for _ in range(n)]
            lst = [i for i in range(n)]
            groups = partition(lst, k)
            message = [words[random.randint(0, n - 1)] for _ in range(m)]
            ans2 = solve(n, m, words, prices, groups, message)
            ans1 = solve2(n, m, words, prices, groups, message)
            if ans2 != ans1:
                failed("Wrong Answer! Input: {}, your output: {}, answer: {}".format((words, prices, groups, message),
                                                                                ans2,
                                                                                ans1))


text:
class Node(object):
    def __init__(self, label):
        self.label = label
        self.par = self
        self.size = 1
        self.sum = 0
        self.added = False

class DisjointSet(object):
    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n)]

    def find(self, u):
        if u != u.par:  # here we user path compression trick
            u.par = self.find(u.par)
        return u.par

    def unite(self, u, v):
        u, v = self.find(u), self.find(v)
        if u == v:  # u and v are in the same component
            return False

        # making v the vertex with bigger size
        if u.size > v.size:
            u, v = v, u

        # merging two components
        u.par = v

        # updating necessary variables
        v.size += u.size
        v.sum += u.sum

        return True

def solve(n, numbers, perm):
    # numbers is a list of n integers
    # perm is a list of the numbers 1 to n in some permutation
    # Return a list of answers
    #Implement the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from test_helper import *
from task import *
import random

def solve2(n, numbers, perm):
    # numbers is a list of n integers
    # perm is a list of the numbers 1 to n in some permutation
    # Return a list of answers

    perm2 = [i - 1 for i in perm]
    perm = perm2
    answers = []
    current_answer = 0
    dsu = DisjointSet(n)

    def add(i, current_answer):
        node = dsu.nodes[i]
        node.added = True
        node.sum = numbers[i]
        if i > 0 and dsu.nodes[i - 1].added:
            dsu.unite(node, dsu.nodes[i - 1])
        if i < n - 1 and dsu.nodes[i + 1].added:
            dsu.unite(node, dsu.nodes[i + 1])

        parent = dsu.find(node)
        current_answer = max(current_answer, parent.sum)
        return current_answer

    for i in range(n - 1, -1, -1):
        answers.append(current_answer)
        current_answer = add(perm[i], current_answer)

    answers.reverse()
    return answers

if __name__ == '__main__':
    manual_tests = [
        (4, [1, 3, 2, 5], [3, 4, 1, 2], [5, 4, 3, 0]),
        (5, [1, 2, 3, 4, 5], [4, 2, 3, 5, 1], [6, 5, 5, 1, 0]),
        (8, [5, 5, 4, 4, 6, 6, 5, 5], [5, 2, 8, 7, 1, 3, 4, 6], [18, 16, 11, 8, 8, 6, 6, 0]),
        (10, [3, 3, 3, 5, 6, 9, 3, 1, 7, 3], [3, 4, 6, 7, 5, 1, 10, 9, 2, 8], [34, 29, 14, 11, 11, 11, 8, 3, 1, 0]),
        (17, [12, 9, 17, 5, 0, 6, 5, 1, 3, 1, 17, 17, 2, 14, 5, 1, 17],
         [3, 7, 5, 8, 12, 9, 15, 13, 11, 14, 6, 16, 17, 1, 10, 2, 4],
         [94, 78, 78, 77, 39, 39, 21, 21, 21, 21, 21, 21, 21, 9, 9, 5, 0]),
        (17, [1, 6, 9, 2, 10, 5, 15, 16, 17, 14, 17, 3, 9, 8, 12, 0, 2],
         [9, 13, 15, 14, 16, 17, 11, 10, 12, 4, 6, 5, 7, 8, 2, 3, 1],
         [65, 64, 64, 64, 64, 64, 64, 64, 64, 46, 31, 31, 16, 16, 9, 1, 0]),
        (17, [10, 10, 3, 9, 8, 0, 10, 13, 11, 8, 11, 1, 6, 9, 2, 10, 5],
         [9, 4, 13, 2, 6, 15, 11, 5, 16, 10, 7, 3, 14, 1, 12, 8, 17],
         [63, 52, 31, 31, 26, 23, 23, 23, 23, 23, 13, 13, 13, 13, 13, 5, 0]),
        (10,
         [606976827, 581094359, 726836550, 554157795, 277900063, 389778978, 555756858, 259222039, 862348978, 749561490],
         [10, 8, 9, 5, 2, 1, 6, 3, 4, 7],
         [4814072447, 3692501430, 3692501430, 2469065531, 1280994345, 1280994345, 1280994345, 555756858, 555756858, 0]),
    ]

    for test in manual_tests:
        test_function(test[-1], solve, test[0], test[1], test[2])

    random_tests = 100
    for i in range(random_tests):
        n = random.randint(1000, 10000)
        nums = []
        for i in range(n):
            nums.append(random.randint(0, 1000000000))
        perm = list(range(1, n + 1))
        random.shuffle(perm)
        x = solve2(n, nums, perm)
        test_function(x, solve, n, nums, perm)


text:
class Node(object):
    def __init__(self, label):
        self.label = label
        self.par = self
        self.rank = 0

class DisjointSet(object):
    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n)]

    def find(self, u):
        if u == u.par:
            return u
        return self.find(u.par)

    def union(self, u, v):
        u, v = self.find(u), self.find(v)
        if u == v:  # u and v are in the same component
            return False

        # making v the vertex with better rank
        if u.rank > v.rank:
            u, v = v, u

        # merging two components
        u.par = v

        # updating maximum depth as rank
        if u.rank == v.rank:
            v.rank += 1

        return True

    # Returns a list of components where each component is a list of values
    def get_all_components(self):
        comps = [[] for _ in range(self.n)]
        for node in self.nodes:
            comps[self.find(node).label].append(node.label)

        comps = [i for i in comps if i]  # Remove empty lists
        return comps

def solve(n, a, b):
    #Implement the function


text:
from test_helper import *
from task import solve
import random
import string

class Node(object):
    def __init__(self, label):
        self.label = label
        self.par = self
        self.rank = 0

class DisjointSet(object):
    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n)]

    def find(self, u):
        if u == u.par:
            return u
        return self.find(u.par)

    def union(self, u, v):
        u, v = self.find(u), self.find(v)
        if u == v:  # u and v are in the same component
            return False

        # making v the vertex with better rank
        if u.rank > v.rank:
            u, v = v, u

        # merging two components
        u.par = v

        # updating maximum depth as rank
        if u.rank == v.rank:
            v.rank += 1

        return True

    # Returns a list of components where each component is a list of values
    def get_all_components(self):
        comps = [[] for _ in range(self.n)]
        for node in self.nodes:
            comps[self.find(node).label].append(node.label)

        comps = [i for i in comps if i]  # Remove empty lists
        return comps

def solve2(n, a, b):
    dsu = DisjointSet(26)
    for i in range(n):
        n1 = dsu.nodes[ord(a[i]) - ord('a')]
        n2 = dsu.nodes[ord(b[i]) - ord('a')]
        dsu.union(n1, n2)
    comps = dsu.get_all_components()

    ans = 26 - len(comps)
    rules = []
    for i in comps:
        if len(i) > 1:
            for j in range(1, len(i)):
                rules.append((chr(ord('a') + i[0]), chr(ord('a') + i[j])))

    return ans, rules

def check_answer(n, a, b, ans, rules):
    dsu1 = DisjointSet(26)
    for i in range(n):
        n1 = dsu1.nodes[ord(a[i]) - ord('a')]
        n2 = dsu1.nodes[ord(b[i]) - ord('a')]
        dsu1.union(n1, n2)

    dsu2 = DisjointSet(26)
    for rule in rules:
        c1, c2 = rule
        c1 = dsu2.nodes[ord(c1) - ord('a')]
        c2 = dsu2.nodes[ord(c2) - ord('a')]
        dsu2.union(c1, c2)

    for i in range(26):
        dsu1.find(dsu1.nodes[i])
        dsu2.find(dsu1.nodes[i])
    for i in range(26):
        label2 = dsu2.find(dsu2.nodes[i]).label
        n1 = dsu1.find(dsu1.nodes[label2]).label
        n2 = dsu1.find(dsu1.nodes[i]).label
        if n1 != n2:
            failed("Wrong Answer! Input: {}, your output: {}, answer: {}".format((n, a, b), (ans, rules),
                                                                                solve2(n, a, b)))

def string_generator(size, chars=string.ascii_lowercase):
    return ''.join(random.choice(chars) for _ in range(size))

if __name__ == '__main__':
    manual_tests = [
        (3, 'abb', 'dad'),
        (8, 'drpepper', 'cocacola'),
        (1, 'h', 'p'),
        (2, 'cx', 'da'),
        (3, 'bab', 'aab'),
        (15, 'xrezbaoiksvhuww', 'dcgcjrkafntbpbl'),
        (10, 'daefcecfae', 'ccdaceefca'),
        (10, 'fdfbffedbc', 'cfcdddfbed'),
        (100, 'bltlukvrharrgytdxnbjailgafwdmeowqvwwsadryzquqzvfhjnpkwvgpwvohvjwzafcxqmisgyyuidvvjqljqshflzywmcccksk',
         'jmgilzxkrvntkvqpsemrmyrasfqrofkwjwfznctwrmegghlhbbomjlojyapmrpkowqhsvwmrccfbnictnntjevynqilptaoharqv'),

        (100, 'pfkskdknmbxxslokqdliigxyvntsmaziljamlflwllvbhqnzpyvvzirhhhglsskiuogfoytcxjmospipybckwmkjhnfjddweyqqi',
         'akvzmboxlcfwccaoknrzrhvqcdqkqnywstmxinqbkftnbjmahrvexoipikkqfjjmasnxofhklxappvufpsyujdtrpjeejhznoeai'),

        (3, 'whw', 'uuh'),
        (242,
         'rrrrrrrrrrrrrmmmmmmmmmmmmmgggggggggggggwwwwwwwwwwwwwyyyyyyyyyyyyyhhhhhhhhhhhhhoooooooooooooqqqqqqqqqqqqqjjjjjjjjjjjjjvvvvvvvvvvvvvlllllllllllllnnnnnnnnnnnnnfffffffffffffeeeeeeeeaaaaaaaaiiiiiiiiuuuuuuuuzzzzzzzzbbbbbbbbxxxxxxxxttttttttsscckppdd',
         'rmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfrmgwyhoqjvlnfeaiuzbxteaiuzbxteaiuzbxteaiuzbxteaiuzbxteaiuzbxteaiuzbxteaiuzbxtscsckpdpd')
    ]

    for test in manual_tests:
        n, a, b = test
        ans, rules = solve(n, a, b)
        check_answer(n, a, b, ans, rules)

    random_tests = 50
    for i in range(random_tests):
        n = random.randint(1000, 100000)
        a = string_generator(n)
        b = string_generator(n)
        ans, rules = solve(n, a, b)
        check_answer(n, a, b, ans, rules)


text:
class Node:
    def __init__(self):
        self.cnt = 0
        self.next = [None]*10

def main(dictionary, numpad, keyset):
    return #Complete the function


text:
from test_helper import *
from task import *

def test_answer_placeholders():
    placeholders = get_answer_placeholders()
    placeholder = placeholders[0]
    if placeholder == "":       # TODO: your condition here
        passed()
    else:
        failed()

if __name__ == '__main__':
    dic = ["am","axe","exam"
    ,"boy","colour","dam","dot","donkey",
    "fox","new","prim","prime","primeval","pry",
       "the","this","theory","van"]
    numpad = [['a','b','c'],['d','e','f'],['g','h'],['i','j','y'],
          ['l','m','n'],['o','p','q'],['r','s'],['t','u'],
          ['v','w','x'],['k','z']]
    keyset = [7,2,1,5,6,3,4,1,8,0,4]

    dic2 = ["am", "ant", "axe", "boy", "colour", "dam", "dot",
            "donkey", "exam", "exact", "fox", "new", "prim",
            "prime", "primeval", "pry", "the", "this", "theory", "van"]
    numpad2 = [['a','b','c'],['d','e','f'],['g','h'],['i','j','y'],
          ['l','m','n'],['o','p','q'],['r','s'],['t','u'],
          ['v','w','x'],['k','z']]
    keyset2 = [2,4,3,0,2]

    tests = [ (dic, numpad, keyset, 2),
          (dic2, numpad2, keyset2, -1)]
    for test in tests:
        test_function(test[-1], main, test[0], test[1], test[2])


text:
import random
class Node:
    def __init__(self, cnt):
        self.cnt = cnt
        self.zero = None
        self.one = None

def main(n, a):
    return #Complete the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from test_helper import *
from task import *

def test_answer_placeholders():
    placeholders = get_answer_placeholders()
    placeholder = placeholders[0]
    if placeholder == "7":       # TODO: your condition here
        passed()
    else:
        failed()

if __name__ == '__main__':
    tests = [
        (5, [3, 7, 7, 7, 0], 7),
        (5, [3, 8, 2, 6, 4], 15),
        (100, [760931312,
961953649,
429596411,
182330388,
16335298,
76880608,
346788756,
355556955,
334080582,
350409683,
937057391,
969259835,
174707619,
113291960,
360805778,
71938466,
438765547,
603511580,
10787845,
938312989,
359609538,
940176361,
210359121,
550234627,
742633517,
555718375,
734223942,
1442635,
981887833,
898263064,
619239874,
742819137,
860216705,
48836277,
777665890,
876552003,
978233257,
124454638,
84625316,
312313832,
327380686,
21682699,
134090025,
354604670,
987491032,
494895802,
279059501,
278772937,
950923748,
289847346,
69602285,
310533278,
82540065,
279961405,
860767904,
825173581,
688196145,
447508205,
679132582,
670083970,
345771261,
298372448,
265419465,
58504325,
199725090,
43085347,
787572693,
30474706,
20056350,
872198008,
342788537,
199953402,
746397073,
476878561,
554558071,
586404463,
824290729,
833617572,
865177399,
775214469,
975981283,
934779683,
938264112,
58521340,
67257446,
651548374,
736211286,
755453591,
99056571,
267860226,
278053919,
297344198,
566232673,
395989750,
355848522,
618474129,
291591462,
143421207,
648948834,
164164178], 1073354569)
    ]
    for test in tests:
        test_function(test[-1], main, test[0], test[1])


text:
def find_kth(array, k, subset_size=7):
    return #Complete the function


text:
import random

from test_helper import *
from task import *

if __name__ == '__main__':
    tests = [
        ([1, 2, 3, 4, 5, 6, 7, 8, 9], 4, 5),
        ([10, 11, 12, 4, 3, 4, 1], 2, 4),
        ([1, 1, 1, 1, 1, 1, 3, 4, 6, 1], 7, 3),
        ([1], 0, 1),
        (random.sample(list(range(1000)), 1000), 221, 221),
        ([2, 5, 1, 7, 2, 5, 9, 8, 2, 0, 1, 5, 0], 12, 9)
    ]
    for test in tests:
        test_function(test[-1], find_kth, test[0], test[1])


text:
import random

def find_kth(a, b, k):
    #Implement the function

#Implement the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    tests = [
        ([1, 2, 3, 4], [5, 6, 7, 8, 9], 4, 5),
        ([10, 11, 12], [4, 3, 4, 1], 2, 4),
        ([1, 1, 1, 1, 1, 1], [3, 4, 6, 1], 7, 3),
        ([1], [], 0, 1),
        (random.sample(list(range(1000)), 1000), random.sample(list(range(1000, 2000)), 1000), 1010, 1010),
        (random.sample(list(range(1000)), 1000), [], 30, 30),
        ([2, 5, 1, 7, 2, 5, 9], [8, 2, 0, 1, 5, 0], 12, 9)
    ]
    for test in tests:
        test_function(test[-1], find_kth, test[0], test[1], test[2])


text:
from collections import defaultdict

class Graph:

    def __init__(self,vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

def countPaths(g, s, d):
    return 0 #Implement the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from task import *

if __name__ == '__main__':
    run_common_tests()
    g = Graph(4)
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(0, 3)
    g.addEdge(2, 0)
    g.addEdge(2, 1)
    g.addEdge(1, 3)
    if countPaths(g, 2, 3) != 3:
        failed("Wrong Answer!")

    g = Graph(5)
    g.addEdge(0,1)
    g.addEdge(0,2)
    g.addEdge(0,4)
    g.addEdge(1,3)
    g.addEdge(1,4)
    g.addEdge(2,4)
    g.addEdge(3,2)

    if countPaths(g, 0, 4) != 4:
        failed("Wrong Answer!")

    if countPaths(g, 1, 0) != 0:
        failed("Wrong Answer!")


text:
from collections import defaultdict

class Graph:
    def __init__(self,vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def addEdge(self,v,w):
        self.graph[v].append(w)
        self.graph[w].append(v)

def hasCycle(g):
    #Implement the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from task import *

if __name__ == '__main__':
    run_common_tests()
    g = Graph(5)
    g.addEdge(1, 0)
    g.addEdge(0, 2)
    g.addEdge(2, 0)
    g.addEdge(0, 3)
    g.addEdge(3, 4)
    if not hasCycle(g):
        failed("Wrong Answer!")

    g = Graph(3)
    g.addEdge(0,1)
    g.addEdge(1,2)

    if hasCycle(g):
        failed("Wrong Answer!")

    g = Graph(5)
    g.addEdge(0, 1)
    g.addEdge(0, 4)
    g.addEdge(3, 4)
    g.addEdge(3, 2)
    g.addEdge(3, 1)

    if not hasCycle(g):
        failed("Wrong Answer!")


text:
from collections import defaultdict

class graph:
    def __init__(self,vertices):
        self.v = vertices
        self.graph = defaultdict(list)
        self.eSize = 0

    def addEdge(self,u,x):
        self.graph[u].append(x)
        self.graph[x].append(u)
        self.eSize += 1

def maxDistance(g):
return 0 #Implement the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from task import *

if __name__ == '__main__':
    run_common_tests()
    g = graph(7)
    g.addEdge(0,1)
    g.addEdge(1,2)
    g.addEdge(2,3)
    g.addEdge(3,4)
    g.addEdge(4,1)
    g.addEdge(2,6)
    g.addEdge(3,6)

    if maxDistance(g) != 4:
        failed("Wrong Answer")

    g = graph(4)
    g.addEdge(0,1)
    g.addEdge(1,2)
    g.addEdge(2,3)
    g.addEdge(3,0)
    if maxDistance(g) != 2:
        failed("Wrong Answer!")

    g.addEdge(0,2)
    g.addEdge(1,3)

    if maxDistance(g) != 1:
        failed("Wrong Answer!")


text:
import bisect

def func(n, array):
    return -1 #Complete the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    tests = [
        (3, [3, 1, 2], 2),
        (5, [4, 2, 1, 3, 5], 3),
        (10, [1, 9, 8, 10, 2, 3, 4, 6, 5, 7], 6),
        (10, [3, 1, 4, 6, 2, 8, 5, 9, 7, 10], 6),
        (20, [3, 1, 4, 6, 2, 5, 8, 7, 9, 11, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20], 15),
        (30, [2, 4, 1, 6, 3, 8, 5, 7, 9, 10, 11, 12, 13, 14, 16, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
              30], 25),
        (80 , [3, 1, 4, 6, 2, 8, 5, 9, 11, 7, 10, 12, 13, 14, 15, 16, 17, 18, 19, 21, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30,
          31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 40, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57,
          58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80] , 73)
    ]
    for test in tests:
        test_function(test[-1], func, test[0], test[1])


text:
def func(n, arr):
    return 0 #Complete the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    tests = [
        (3, [3, 1, 2], 1),
        (80, [3, 1, 4, 6, 2, 8, 5, 9, 11, 7, 10, 12, 13, 14, 15, 16, 17, 18, 19, 21, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30,
          31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 40, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57,
          58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80], 40),
        (5 , [4 ,1 , 2 , 5 , 3] , 2),
        (4 , [4 , 1 , 3, 2] , 2),
        (1 , [1] , 0),
        (2 , [2 , 1] , 1),
        (6 , [5 ,3 , 6 , 4, 1 ,2]  , 4),
        (7 , [1 , 2 , 3 , 6, 7 , 4 , 5] , 2),
        (8 , [6 , 2 , 1 , 8 , 5 ,7 , 3 , 4] , 5),
        (9 , [1 , 6 , 4 , 5 , 9 ,8 , 7, 3 , 2] , 7),
        (10 , [5 , 1 ,6 , 2, 8 , 3 , 4 , 10 , 9 , 7] , 6)

    ]
    for test in tests:
        test_function(test[-1], func, test[0], test[1])


text:
def func(n , m , arr):
    return 0 #Complete the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    tests = [
        (5, 6, [3, 3, 3, 3, 3], 10),
        (3, 5, [1, 2, 4], 3),
        (10, 17, [12, 16, 6, 9, 12, 6, 12, 1, 12, 13], 83),
        (24, 1, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 0),
        (21, 19, [19, 13, 2, 16, 8, 15, 14, 15, 7, 8, 3, 17, 11, 6, 1, 18, 16, 6, 2, 15, 5], 196),
        (6, 6, [2, 2, 4, 4, 6, 6], 18),
        (2, 1000, [1, 1000], 1)
    ]
    for test in tests:
        test_function(test[-1], func, test[0], test[1], test[2])


text:
def func(n, k):
    return -1 #Complete the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    tests = [
        (3, 3, [2, 1, 3]),
        (4, 1, [1, 2, 3, 4]),
        (5, 6, -1),
        (100, 100, -1),
        (10, 17, [3, 1, 4, 6, 2, 8, 5, 9, 7, 10]),
        (20, 15, [3, 1, 4, 6, 2, 5, 8, 7, 9, 11, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20]),
        (30, 17,
         [2, 4, 1, 6, 3, 8, 5, 7, 9, 10, 11, 12, 13, 14, 16, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
          30]),
        (80, 25,
         [3, 1, 4, 6, 2, 8, 5, 9, 11, 7, 10, 12, 13, 14, 15, 16, 17, 18, 19, 21, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30,
          31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 40, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57,
          58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80]),
        (120, 66, -1)

    ]
    for test in tests:
        test_function(test[-1], func, test[0], test[1])


text:
def shellSort(arr):
    return arr #Complete the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    tests = [
        ([3, 1, 2],[1, 2, 3]),
        ([3, 1, 4, 6, 2, 8, 5, 9, 11, 7, 10, 12, 13, 14, 15, 16, 17, 18, 19, 21, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30,
          31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 40, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57,
          58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80] ,[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80])
    ]
    for test in tests:
        test_function(test[-1], shellSort, test[0])


text:
import random
import timeit

def qSortRandomPivot(arr, fst, lst):
    return arr #Complete the function


text:
from task import qSortRandomPivot
from test_helper import *

if __name__ == '__main__':
    tests = [
        ([3, 1, 2], 0, 2, [1, 2, 3]),
        ([3, 1, 4, 6, 2, 8, 5, 9, 11, 7, 10, 12, 13, 14, 15, 16, 17, 18, 19, 21, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30,
          31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 40, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57,
          58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80] , 0 , 79 , [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80])
    ]
    for test in tests:
        test_function(test[-1], qSortRandomPivot, test[0], test[1], test[2])


text:
def func(n , b , arr):
    return 0 #Complete the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    tests = [
        (5, 6, [1, 2, 5, 10, 15, 20], 1),
        (4, 10, [1, 3, 2, 4], 0),
        (10, 100, [94, 65, 24, 47, 29, 98, 20, 65, 6, 17], 2)
    ]
    for test in tests:
        test_function(test[-1], func, test[0], test[1], test[2])


text:
def hasOnlyOneChild(pre, size):
    #Complete the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from task import*

if __name__ == "__main__":

    pre = [8, 3, 5, 7, 6]
    size = len(pre)

    if (hasOnlyOneChild(pre, size) == False):
        failed("please try again")

    pre = [11, 10, 6, 8, 3]
    size = len(pre)
    if (hasOnlyOneChild(pre, size) == True):
        failed("please try again")


text:
class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value

def insert(root,data):
    #Complete the function

#inorder is an array which we want to store the inorder traversal in it.
def inordertraversal(root, inorder):
    #Complete the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from task import *

def test_answer_placeholders():
    placeholders = get_answer_placeholders()
    placeholder = placeholders[0]
    if placeholder == "":       # TODO: your condition here
        passed()
    else:
        failed()

#intersection in O(m + n)
# m is size of arr1, n is size of array2
finalarray = []
def printIntersection(arr1, arr2, m, n):
    i, j = 0, 0
    while i < m and j < n:
        i, j = 0, 0
        while i < m and j < n:
            if arr1[i] < arr2[j]:
                i += 1
            elif arr2[j] < arr1[i]:
                j += 1
            else:
                # common element.
                finalarray.append(arr2[j])
                j += 1
                i += 1

if __name__ == '__main__':
    mainroot = Node(5)
    insert(mainroot,1)
    insert(mainroot,3)
    insert(mainroot,6)
    insert(mainroot,8)
    insert(mainroot,7)
    insert(mainroot, 4)

    mainroot2 = Node(10)
    insert(mainroot2, 11)
    insert(mainroot2, 4)
    insert(mainroot2, 6)
    insert(mainroot2, 7)
    insert(mainroot2, 14)
    insert(mainroot2, 9)

    inorder1 = []
    inorder2 = []
    inordertraversal(mainroot, inorder1)
    inordertraversal(mainroot2, inorder2)

    m = len(inorder1)
    n = len(inorder2)
    printIntersection(inorder1, inorder2, m, n)

    for i in [4,6,7]:
        if i not in finalarray:
            failed("try again")


text:
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def isbst(root):
    #Complete the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from task import *

if __name__ == '__main__':

    root = Node(10)
    root.left = Node(6)
    root.right = Node(14)
    root.left.left = Node(3)
    root.left.right = Node(8)
    root.right.left = Node(12)
    root.right.right = Node(1)

    if isbst(root):
        failed("please try again. 1")

    root = Node(10)
    root.left = Node(6)
    root.right = Node(14)
    root.left.left = Node(3)
    root.left.right = Node(8)
    root.right.left = Node(12)
    root.right.right = Node(16)
    if  isbst(root) is False:
        failed("please try again. 2")


text:
#Sample Input
# n = "0 0 1 0 1 0 1 1 1 0"
# q = 8
# inp = ["s 3 7", "g 4", ...]
def func(n, q, inp):
    #Implement the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from task import *

if __name__ == '__main__':
    run_common_tests()

    n = "0 0 1 0 1 0 1 1 1 0"
    q = 8
    inp = ["s 3 7", "g 4", "s 2 8", "s 5 10", "g 4", "s 0 6", "g 3", "g 5"]

    if func(n,q,inp) != [0, 1, 1, 0]:
        failed("Wrong Answer!")


text:
inf = 1000000000
#Sample Input
# n = 7
# arr = "7 2 3 13 5 17 11"
# q = 4
# inp = ["3 7", "2 5", ...]
def func(n, arr, q, inp):
    #Implement the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from task import *

if __name__ == '__main__':
    run_common_tests()

    n = 7
    arr = "7 2 3 13 5 17 11"
    q = 4
    inp = ["3 7", "2 5", "0 7", "5 6"]

    if func(n, arr, q, inp) != [5, 3, 2, 17]:
        failed("Wrong Answer!")


text:
class HeapNode:
    def __init__(self, data, row,):
        self.data = data
        self.row = row

def merge_k_sorted_arrays(matrix, k, n):
    #Implement the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from task import *

if __name__ == '__main__':
    mat = [ [1, 3, 5, 7],
            [2, 4, 6, 8],
            [0, 9, 10, 11] ]
    arr = merge_k_sorted_arrays(mat, 3, 4)
    if not all(arr[i] <= arr[i+1] for i in range(len(arr)-1)):
        failed("Wrong Answer!")

    mat = [ [-2, 3, 5, 10, 11, 100],
            [1, 3, 5, 6, 7, 8],
            [-3, -2, -1, 101, 102, 103],
            [0, 0, 0, 0, 0, 105]]
    arr = merge_k_sorted_arrays(mat, 4, 6)
    if not all(arr[i] <= arr[i+1] for i in range(len(arr)-1)):
        failed("Wrong Answer!")


text:
# Sample Input:
# n = 10
# arr1 = "0 0 0 0 1 0 1 0 1"  0 is for a course, 1 is for a prof.
# arr2 = "5 10 17 6 2 1 3 2 4" course units or h_index of the prof.

def maxVahed(n, arr1, arr2):
    #Implement the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from task import *

if __name__ == '__main__':
    n = 10
    arr1 = "0 0 0 0 1 0 1 0 1"
    arr2 = "5 10 17 6 2 1 3 2 4"
    if maxVahed(n,arr1,arr2) != 20:
        failed("Wrong Answer")

    n = 6
    arr1 = "0 0 1 0 1"
    arr2 = "10 12 2 1 3"

    if maxVahed(n,arr1,arr2) != 13:
        failed("Wrong Answer")


text:
class Graph:
    def __init__(self, row, col, g):
        self.ROW = row
        self.COL = col
        self.graph = g

    def count_islands(self):
        #Implement the function

# Don't change this function
def solve(graph):
    return graph.count_islands()


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    graph = [[1, 1, 0, 0, 0],
             [0, 1, 0, 0, 1],
             [1, 0, 0, 1, 1],
             [0, 0, 0, 0, 0],
             [1, 0, 1, 0, 1]]
    row = len(graph)
    col = len(graph[0])
    g = Graph(row, col, graph)

    graph = [[1, 1],
             [1, 1]]
    row = len(graph)
    col = len(graph[0])
    g2 = Graph(row, col, graph)

    graph = [[0 for i in range(1000)] for j in range(1000)]
    row = col = 1000
    g3 = Graph(row, col, graph)

    graph = [[0 for i in range(1000)] for j in range(1000)]
    graph[500] = [(1 if i % 2 == 0 else 0) for i in range(1000)]
    print(graph[500])
    row = col = 1000
    g4 = Graph(row, col, graph)

    tests = [
        (g, 5),
        (g2, 1),
        (g3, 0),
        (g4, 500),
    ]
    for test in tests:
        my_test_function(test[-1], solve, test[0])


text:
import copy

class Graph:
    def __init__(self, N):
        self.graph = [[] for _ in range(N)]
        self.Vertices_num = N
        self.result = []

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def all_topologicals(self):
        return -1 #Implement the function

# Don't change this function
def solve(graph):
    return graph.all_topologicals()


text:
# Sample Input:
# Input = [[4, 2], [1, 3], [2, 4]]

def solve(input):
    #Implement the fucntion


text:
from test_helper import *
from task import *

def intersect(l1, r1, l2, r2):
    if l1 <= l2 and r1 >= r2 or l2 <= l1 and r2 >= r1:
        return False
    if r2 <= r1 and l1 <= l2 and r2 <= l2:
        return False
    if l1 >= r2 and l1 >= l2 or r1 <= l2 and r1 <= r2:
        return False
    return True

def check_fallacy(l1, r1, l2, r2, ans1, ans2):
    if intersect(l1, r1, l2, r2):
        return ans1 == ans2
    return False

def dfs(v, clr, color, graph):
    if color[v] != -1 and color[v] != clr:
        return 'Impossible'
    if color[v] != -1:
        return
    color[v] = clr
    for u in graph[v]:
        if dfs(u, 1 - clr, color, graph) == 'Impossible':
            return 'Impossible'

def my_solve(input):
    n, m = input[0]
    graph = [[] for i in range(m)]
    vedge = []
    color = [-1] * m
    for i in range(m):
        a, b = map(int, input[i + 1])
        a, b = min(a, b), max(a, b)
        for j, v in enumerate(vedge):
            if intersect(a, b, v[0], v[1]):
                graph[i].append(j)
                graph[j].append(i)
        vedge.append((a, b))

    for i in range(m):
        if color[i] == -1:
            if dfs(i, 0, color, graph):
                return 'Impossible'
    return answer(color)

def answer(color):
    return str(['I' if i == 0 else 'O' for i in color])

if __name__ == '__main__':
    in1 = [[4, 2], [1, 3], [2, 4]]
    in2 = [[5, 2], [2, 4], [4, 1]]
    in3 = [[6, 6], [1, 4], [4, 6], [2, 6], [2, 4], [5, 3], [6, 3]]
    in4 = [[17, 10], [4, 11], [7, 16], [8, 5], [12, 15], [7, 4], [1, 12], [11, 1], [15, 1], [7, 14], [2, 9]]

    tests = [in1, in2, in3, in4]
    for test in tests:
        ans = solve(test)
        true_ans = my_solve(test)
        if true_ans == 'Impossible':
            if ans == 'Impossible':
                continue
            else:
                failed("Wrong Answer! Input: {}, your output: {}, answer: {}".format(test, ans, my_solve(test)))
        for i in range(1, len(test)):
            for j in range(i + 1, len(test)):
                if check_fallacy(test[i][0], test[i][1], test[j][0], test[j][1], list(ans)[i - 1], list(ans)[j - 1]):
                    failed("Wrong Answer! Input: {}, your output: {}, answer: {}".format(test, ans, my_solve(test)))
                passed()


text:
def solve(question):
    #Implement the function


text:
import random

from test_helper import *
from task import *

tests = [[57270, 70040],
 [84335, 98558],
 [29060, 43300],
 [39986, 95876],
 [89474, 91474],
 [98812, 99845],
 [60806, 70853],
 [5954, 43526],
 [14976, 47184],
 [5528, 12410],
 [61429, 93413],
 [79196, 93956],
 [87242, 96796],
 [40932, 42890],
 [25033, 87121],
 [59167, 81035],
 [9827, 93975],
 [54816, 79135],
 [36003, 45936],
 [57821, 86925],
 [82503, 86449],
 [79563, 93564],
 [80775, 83200],
 [35588, 94632],
 [72606, 75197],
 [66181, 93232],
 [4750, 69881],
 [24376, 54171],
 [30087, 45545],
 [33682, 74265],
 [57790, 90656],
 [87882, 89535],
 [34119, 83665],
 [6877, 30789],
 [55335, 73897],
 [89315, 98155],
 [87954, 98632],
 [17853, 53368],
 [30601, 84812],
 [32505, 96095],
 [1, 100000]
]

class Question:
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.asked_questions = 0

    def ask(self, x, y):
        if self.asked_questions == 40:
            return random.choice([True, False])

        self.asked_questions += 1
        return (x <= self.a <= y) or (x <= self.b <= y) or (self.a <= x <= self.b) or (self.a <= y <= self.b)

if __name__ == '__main__':
    for test in tests:
        test_function(test, solve, Question(test[0], test[1]))


text:
def solve(n, k, a):
    #Implement the function


text:
from test_helper import *
from task import *
from testcases import tests

if __name__ == '__main__':
    for test in tests:
        test_function(test[0], solve, test[1], test[2], test[3])


text:
def first_negatives(A, k):
    return #Complete the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    tests = [
        ([5, -4, -6, 3, -2, 4, 8, 12], 3, [-4, -4, -6, -2, -2, 0]),
        ([-1, -2, 4, -5, -1, -3], 6, [-1]),
        ([-1, -2, -3, -5, -1, -3], 1, [-1, -2, -3, -5, -1, -3]),
        ([2, -9, 8, 1, 0, 0, 1, -2, 5, 5, 4, -7, 10, -1, -2, -1, -7, -7, -3, 5, 5, 2, 2, 2, -8, 5, -7, -5, -1, 3, 8, 7,
          -7, 4, -9, 0, 9, 5, -2, 7, -9, 4, 6, 5, 9, 9, 1, 6, -2, -5, 4, 10, 4, 2, 2, 10, 8, 10, 6, -3, -4, -4, -4, -5,
          -2, -5, 2, -1, -7, 4, -4, 5, -10, 8, -7, 0, -4, 2, -7, 10, 7, 2, -3, 8, -1, 4, 1, 4, -9, 10, 8, 6, 5, 5, 3,
          -6, 5, 8, -6, 4], 4,
         [-9, -9, 0, 0, -2, -2, -2, -2, -7, -7, -7, -7, -1, -1, -2, -1, -7, -7, -3, 0, 0, -8, -8, -8, -8, -7, -7, -5,
          -1, -7, -7, -7, -7, -9, -9, -2, -2, -2, -2, -9, -9, 0, 0, 0, 0, -2, -2, -2, -2, -5, 0, 0, 0, 0, 0, 0, -3, -3,
          -3, -3, -4, -4, -4, -5, -2, -5, -1, -1, -7, -4, -4, -10, -10, -7, -7, -4, -4, -7, -7, -3, -3, -3, -3, -1, -1,
          -9, -9, -9, -9, 0, 0, 0, -6, -6, -6, -6, -6])

    ]
    for test in tests:
        test_function(test[-1], first_negatives, test[0], test[1])


text:
def can_sort_by_stack(input_queue):
    return False #Complete the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    tests = [
        ([1, 2, 3], True),
        ([3, 2, 1], True),
        ([2, 3, 1], False),
        ([3, 1, 2], True),
        ([1, 10, 5, 6, 4, 9, 8, 7, 3, 2], False),
        ([6, 5, 1, 2, 4, 3], True)
    ]
    for test in tests:
        test_function(test[-1], can_sort_by_stack, test[0])


text:
def linked_list_swap(node1, node2):
    return #Complete the function


text:
from test_helper import *
from task import *
import random

class Node:
    def __init__(self, data, next_node=None, prev_node=None):
        self.data = data
        self.next = next_node
        self.prev = prev_node

def check_swap(array_list, i, j):
    print(i, j)
    linked_list_swap(array_list[i], array_list[j])
    array_list[i], array_list[j] = array_list[j], array_list[i]
    error = False
    for k in range(0, len(array_list) - 1):
        if array_list[k].next != array_list[k + 1] or array_list[-k - 1].prev != array_list[-k - 2]:
            error = True
    if array_list[0].prev != None or array_list[-1].next != None or error:
        if abs(i - j) == 1:
            failed("Wrong linked list. Input is adjacent nodes.")
        elif i == 0 or j == 0 or i == len(array_list) - 1 or j == len(array_list) - 1:
            failed("Wrong linked list. Input contains head or tail nodes.")
        else:
            failed("Wrong linked list. Input isn't adjacent or head or tail nodes.")

if __name__ == '__main__':
    prev = Node(random.random())
    array_list = [prev]
    for i in range(1, 100):
        new = Node(random.random())
        new.prev = prev
        prev.next = new
        prev = new
        array_list.append(new)

    check_swap(array_list, 44, 88)
    check_swap(array_list, 0, 10)
    check_swap(array_list, 99, 5)
    check_swap(array_list, 0, 99)
    check_swap(array_list, 64, 65)
    check_swap(array_list, 9, 8)
    check_swap(array_list, 98, 99)
    check_swap(array_list, 1, 0)


text:
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def verticalOrder(root):
    #Implement the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    root1 = Node(1)
    root1.left = Node(2)
    root1.right = Node(3)
    root1.left.left = Node(4)
    root1.left.right = Node(5)
    root1.right.left = Node(6)
    root1.right.right = Node(7)
    root1.right.left.right = Node(8)
    root1.right.right.right = Node(9)

    root2 = Node(3)
    root2.left = Node(1)
    root2.right = Node(1)
    root2.left.left = Node(0)
    root2.left.right = Node(2)
    root2.right.left = Node(0)
    root2.right.right = Node(2)

    root3 = Node(1)
    root3.left = Node(2)
    root3.right = Node(2)
    root3.left.left = Node(3)
    root3.left.right = Node(4)
    root3.right.left = Node(4)
    root3.right.right = Node(3)
    root3.left.left.left = Node(5)
    root3.left.left.right = Node(6)
    root3.left.right.left = Node(7)
    root3.left.right.right = Node(8)
    root3.right.left.left = Node(8)
    root3.right.left.right = Node(7)
    root3.right.right.left = Node(6)
    root3.right.right.right = Node(5)

    root4 = Node(1)
    root4.left = Node(2)
    root4.right = Node(3)
    root4.left.left = Node(4)
    root4.right.right = Node(5)
    root4.left.left.left = Node(6)
    root4.right.right.right = Node(7)
    root4.right.right.right.left = Node(8)
    root4.right.right.right.left.left = Node(9)
    root4.right.right.right.left.left.left = Node(10)

    tests = [
        (root1, [[4], [2], [1, 5, 6], [3, 8], [7], [9]]),
        (root2, [[0], [1], [3, 2, 0], [1], [2]]),
        (root3, [[5], [3], [2, 6, 7, 8], [1, 4, 4], [8, 2, 7, 6], [3], [5]]),
        (root4, [[6], [4], [2], [1, 10], [3, 9], [5, 8], [7]])
    ]
    for test in tests:
        test_function(test[-1], verticalOrder, test[0])


text:
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Maybe want to write another function ?!

def isSymmetric(root):
    return False #Do the task


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    root1 = Node(1)
    root1.left = Node(2)
    root1.right = Node(2)
    root1.left.left = Node(3)
    root1.left.right = Node(4)
    root1.right.left = Node(4)
    root1.right.right = Node(3)

    root2 = Node(3)
    root2.left = Node(1)
    root2.right = Node(1)
    root2.left.left = Node(0)
    root2.left.right = Node(2)
    root2.right.left = Node(0)
    root2.right.right = Node(2)

    root3 = Node(1)
    root3.left = Node(2)
    root3.right = Node(2)
    root3.left.left = Node(3)
    root3.left.right = Node(4)
    root3.right.left = Node(4)
    root3.right.right = Node(3)
    root3.left.left.left = Node(5)
    root3.left.left.right = Node(6)
    root3.left.right.left = Node(7)
    root3.left.right.right = Node(8)
    root3.right.left.left = Node(8)
    root3.right.left.right = Node(7)
    root3.right.right.left = Node(6)
    root3.right.right.right = Node(5)

    root4 = Node(1)
    root4.left = Node(2)
    root4.right = Node(2)
    root4.left.left = Node(3)
    root4.left.right = Node(4)
    root4.right.left = Node(4)
    root4.right.right = Node(3)
    root4.left.left.left = Node(5)
    root4.left.left.right = Node(6)
    root4.left.right.left = Node(7)
    root4.left.right.right = Node(8)
    root4.right.left.left = Node(8)
    root4.right.left.right = Node(7)
    root4.right.right.left = Node(5)
    root4.right.right.right = Node(6)
    tests = [
        (root1, True),
        (root2, False),
        (root3, True),
        (root4, False)
    ]
    for test in tests:
        test_function(test[-1], isSymmetric, test[0])


text:
class Node:
    def __init__(self, name):
        self.city_name = name
        self.city1 = None
        self.city2 = None
        self.max_depth = 1
        self.answer = 0

def solve(root):
    return 0 #Complete the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':
    root1 = Node(1)
    root1.city1 = Node(2)
    root1.city2 = Node(3)
    root1.city1.city1 = Node(4)
    root1.city1.city2 = Node(5)
    root1.city2.city1 = Node(6)
    root1.city2.city2 = Node(7)
    root1.city2.city1.city2 = Node(8)
    root1.city2.city2.city2 = Node(9)

    root2 = Node(3)
    root2.city1 = Node(1)
    root2.city2 = Node(1)
    root2.city1.city1 = Node(0)
    root2.city1.city2 = Node(2)
    root2.city2.city1 = Node(0)
    root2.city2.city2 = Node(2)

    root3 = Node(1)
    root3.city1 = Node(2)
    root3.city2 = Node(2)
    root3.city1.city1 = Node(3)
    root3.city1.city2 = Node(4)
    root3.city2.city1 = Node(4)
    root3.city2.city2 = Node(3)
    root3.city1.city1.city1 = Node(5)
    root3.city1.city1.city2 = Node(6)
    root3.city1.city2.city1 = Node(7)
    root3.city1.city2.city2 = Node(8)
    root3.city2.city1.city1 = Node(8)
    root3.city2.city1.city2 = Node(7)
    root3.city2.city2.city1 = Node(6)
    root3.city2.city2.city2 = Node(5)

    root4 = Node(1)
    root4.city1 = Node(2)
    root4.city2 = Node(3)
    root4.city1.city1 = Node(4)
    root4.city2.city2 = Node(5)
    root4.city1.city1.city1 = Node(6)
    root4.city2.city2.city2 = Node(7)
    root4.city2.city2.city2.city1 = Node(8)
    root4.city2.city2.city2.city1.city1 = Node(9)
    root4.city2.city2.city2.city1.city1.city1 = Node(10)

    root5 = Node(1)
    root5.city1 = Node(2)
    root5.city2 = Node(3)
    root5.city1.city1 = Node(4)
    root5.city1.city2 = Node(5)
    root5.city1.city1.city1 = Node(6)
    root5.city1.city1.city1.city1 = Node(8)
    root5.city1.city2.city1 = Node(7)
    root5.city1.city2.city1.city1 = Node(9)

    tests = [
        (root1, 6),
        (root2, 5),
        (root3, 7),
        (root4, 10),
        (root5, 7)
    ]
    for test in tests:
        test_function(test[-1], solve, test[0])


text:
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def check(preorder, inorder, postorder):
    return False #Complete the function


text:
from test_helper import *
from task import *

if __name__ == '__main__':

    tests = [
        ([1, 2, 4, 5, 3], [4, 2, 5, 1, 3], [4, 5, 2, 3, 1], True),
        ([25,15,10,4,12,22,18,24,50,35,31,44,70,66,90], [4,10,12,15,18,22,24,25,31,35,44,50,66,70,90], [4,12,10,18,24,22,15,31,44,35,66,90,70,50,25], True),
        ([2,7,3,6,8,11,5,9,4], [3,7,8,6,11,2,5,4,9], [3,8,11,7,6,4,9,5,2], False),
        ([8,5,9,7,1,12,2,4,11,3], [9,5,1,7,2,12,8,4,3,11], [9,1,2,12,7,5,11,3,4,8], False)
    ]
    for test in tests:
        test_function(test[-1], check, test[0], test[1], test[2])


text:
# TODO: type solution here
class Node:
    def __init__(self, key=None, red=False, parent=None, children=None):
        self.key = key
        self.red = red
        self.parent = parent
        self.children = children
        self.num_nodes = 0
        self.sum_nodes = 0

    def refresh_features(self):
        self.num_nodes = 1 + sum([child.num_nodes for child in self.children])
        self.sum_nodes = self.key.value + sum([child.sum_nodes for child in self.children])

    def get_direction(self):
        return 0 if self == self.parent.children[0] else 1

    def get_brother(self):
        return self.parent.children[1 - self.get_direction()]

    def get_uncle(self):
        return self.parent.get_brother()

    def make_black(self):
        self.red = False

    def make_red(self):
        self.red = True

class Tree:
    def __init__(self):
        self.dummy_parent = Node(children=[None])
        self.dummy_parent.children[0] = Node(parent=self.dummy_parent)
        self.nil = self.root
        self.nil.num_nodes = 0
        self.nil.sum_nodes = 0

    def insert(self, key):
        node = self.root
        node_parent = node.parent
        direction = 0
        while node != self.nil:
            node_parent = node
            direction = 0 if key < node.key else 1
            node = node.children[direction]
        # create new node
        node_parent.children[direction] = Node(key, red=True, parent=node_parent, children=[self.nil] * 2)
        # refresh features
        node = node_parent.children[direction]
        while node != self.dummy_parent:
            node.refresh_features()
            node = node.parent

        self.cleanup_insert(node_parent.children[direction])

    def cleanup_insert(self, node):
        while node != self.root and node.parent.red:
            uncle = node.get_uncle()
            if uncle.red:
                uncle.make_black()
                node.parent.make_black()
                node.parent.parent.make_red()
                node = node.parent.parent
                continue
            # Save the value of grandparent because the rotation in the "if" staement below will mess up order of nodes
            grand_parent = node.parent.parent
            direction = node.get_direction()
            if direction != node.parent.get_direction():
                self.rotate(node.parent, 1 - direction)
                direction = 1 - direction
            self.rotate(grand_parent, 1 - direction)
            grand_parent.make_red()
            grand_parent.parent.make_black()
            # rotations should terminate loop
            break
        # Root should always be black
        self.root.make_black()

    def rotate(self, node, direction):
        child = node.children[1 - direction]
        mid_child = child.children[direction]
        parent = node.parent

        parent.children[node.get_direction()] = child
        child.parent = parent

        child.children[direction] = node
        node.parent = child

        node.children[1 - direction] = mid_child
        mid_child.parent = node

        node.refresh_features()
        child.refresh_features()

    def in_order(self, node=None):
        if node is None:
            node = self.root
        if node == self.nil:
            return []
        return self.in_order(node.children[0]) + [node] + self.in_order(node.children[1])

    def rank(self, key):
        node = self.root
        num_smaller_or_equal = 0
        while node != self.nil:
            if key < node.key:
                node = node.children[0]
                continue
            num_smaller_or_equal += node.children[0].num_nodes + 1
            if key > node.key:
                node = node.children[1]
            else:
                break
        return num_smaller_or_equal

    def increase_value(self, key, amount):
        node = self.root
        while node != self.nil:
            if key < node.key.key:
                node = node.children[0]
            elif key > node.key.key:
                node = node.children[1]
            else:
                break
        if node == self.nil:
            self.insert(My_pair(key, amount))
        else:
            node.key.value += amount
            while node != self.dummy_parent:
                node.refresh_features()
                node = node.parent

    def sum_range_zero(self, key):
        node = self.root
        sum_smaller_or_equal = 0
        while node != self.nil:
            if key < node.key:
                node = node.children[0]
                continue
            sum_smaller_or_equal += node.sum_nodes - node.children[1].sum_nodes
            if key > node.key:
                node = node.children[1]
            else:
                break
        return sum_smaller_or_equal

    @property
    def root(self):
        return self.dummy_parent.children[0]

class My_pair:
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def increment_value(self):
        self.value += 1

    def __lt__(self, other):
        return self.key < other.key

    def __le__(self, other):
        return self.key <= other.key

    def __gt__(self, other):
        return self.key > other.key

    def __ge__(self, other):
        return self.key >= other.key

    def __eq__(self, other):
        if self is None or other is None:
            return self is None and other is None
        return self.key == other.key

    def __ne__(self, other):
        return not self == other

def data_structure(li):
    x = Tree()
    output = []
    for cmd in li:
        if cmd[0] == 1:
            num = int(cmd[1])
            amount = int(cmd[2])
            x.increase_value(num, amount)
        else:
            num = int(cmd[1])
            output.append(x.sum_range_zero(My_pair(num, None)))
    return output


text:
class Node:
    def __init__(self, key=None, red=False, parent=None, children=None):
        self.key = key
        self.red = red
        self.parent = parent
        self.children = children
        self.num_nodes = 0
        self.sum_nodes = 0

    def refresh_features(self):
        self.num_nodes = 1 + sum([child.num_nodes for child in self.children])
        self.sum_nodes = self.key.value + sum([child.sum_nodes for child in self.children])

    def get_direction(self):
        return 0 if self == self.parent.children[0] else 1

    def get_brother(self):
        return self.parent.children[1 - self.get_direction()]

    def get_uncle(self):
        return self.parent.get_brother()

    def make_black(self):
        self.red = False

    def make_red(self):
        self.red = True

class Tree:
    def __init__(self):
        self.dummy_parent = Node(children=[None])
        self.dummy_parent.children[0] = Node(parent=self.dummy_parent)
        self.nil = self.root
        self.nil.num_nodes = 0
        self.nil.sum_nodes = 0

    def insert(self, key):
        node = self.root
        node_parent = node.parent
        direction = 0
        while node != self.nil:
            node_parent = node
            direction = 0 if key < node.key else 1
            node = node.children[direction]
        # create new node
        node_parent.children[direction] = Node(key, red=True, parent=node_parent, children=[self.nil] * 2)
        # refresh features
        node = node_parent.children[direction]
        while node != self.dummy_parent:
            node.refresh_features()
            node = node.parent

        self.cleanup_insert(node_parent.children[direction])

    def cleanup_insert(self, node):
        while node != self.root and node.parent.red:
            uncle = node.get_uncle()
            if uncle.red:
                uncle.make_black()
                node.parent.make_black()
                node.parent.parent.make_red()
                node = node.parent.parent
                continue
            # Save the value of grandparent because the rotation in the "if" staement below will mess up order of nodes
            grand_parent = node.parent.parent
            direction = node.get_direction()
            if direction != node.parent.get_direction():
                self.rotate(node.parent, 1 - direction)
                direction = 1 - direction
            self.rotate(grand_parent, 1 - direction)
            grand_parent.make_red()
            grand_parent.parent.make_black()
            # rotations should terminate loop
            break
        # Root should always be black
        self.root.make_black()

    def rotate(self, node, direction):
        child = node.children[1 - direction]
        mid_child = child.children[direction]
        parent = node.parent

        parent.children[node.get_direction()] = child
        child.parent = parent

        child.children[direction] = node
        node.parent = child

        node.children[1 - direction] = mid_child
        mid_child.parent = node

        node.refresh_features()
        child.refresh_features()

    def in_order(self, node=None):
        if node is None:
            node = self.root
        if node == self.nil:
            return []
        return self.in_order(node.children[0]) + [node] + self.in_order(node.children[1])

    def rank(self, key):
        node = self.root
        num_smaller_or_equal = 0
        while node != self.nil:
            if key < node.key:
                node = node.children[0]
                continue
            num_smaller_or_equal += node.children[0].num_nodes + 1
            if key > node.key:
                node = node.children[1]
            else:
                break
        return num_smaller_or_equal

    def increase_value(self, key, amount):
        node = self.root
        while node != self.nil:
            if key < node.key.key:
                node = node.children[0]
            elif key > node.key.key:
                node = node.children[1]
            else:
                break
        if node == self.nil:
            self.insert(My_pair(key, amount))
        else:
            node.key.value += amount
            while node != self.dummy_parent:
                node.refresh_features()
                node = node.parent

    def sum_range_zero(self, key):
        node = self.root
        sum_smaller_or_equal = 0
        while node != self.nil:
            if key < node.key:
                node = node.children[0]
                continue
            sum_smaller_or_equal += node.sum_nodes - node.children[1].sum_nodes
            if key > node.key:
                node = node.children[1]
            else:
                break
        return sum_smaller_or_equal

    @property
    def root(self):
        return self.dummy_parent.children[0]

class My_pair:
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def increment_value(self):
        self.value += 1

    def __lt__(self, other):
        return self.key < other.key

    def __le__(self, other):
        return self.key <= other.key

    def __gt__(self, other):
        return self.key > other.key

    def __ge__(self, other):
        return self.key >= other.key

    def __eq__(self, other):
        if self is None or other is None:
            return self is None and other is None
        return self.key == other.key

    def __ne__(self, other):
        return not self == other

def data_structure(li):
    #Complete the function


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from random import shuffle
from random import randint
from task import data_structure as func
from task_copy import data_structure as func_judge

def test_generator(n):
    li = []
    for i in range(n):
        kind = randint(1, 2)
        max_range = 10000
        if kind == 1:
            li.append((1, randint(1, max_range), randint(1, max_range)))
        else:
            li.append((2, randint(1, max_range)))
    return li
if __name__ == '__main__':
    test_nums = [10, 10, 100, 100, 10000]
    for test_num in test_nums:
        li = test_generator(test_num)
        user_li = func(li[0:len(li)])
        judge_li = func_judge(li[0:len(li)])
        if user_li != judge_li:
            failed("Wrong Answer! Input: " + str(li) +
                   " Your Answer: " + str(user_li) +
                   " Expected Answer: " + str(judge_li))
    print("PASS")


text:
"""
A classic (not left-leaning) Red-Black Tree implementation, supporting addition and deletion.
"""

# The possible Node colors
BLACK = 'BLACK'
RED = 'RED'
NIL = 'NIL'

class Node:
    def __init__(self, value, color, parent, left=None, right=None):
        self.value = value
        self.color = color
        self.parent = parent
        self.left = left
        self.right = right

    def __repr__(self):
        return '{color} {val} Node'.format(color=self.color, val=self.value)

    def __iter__(self):
        if self.left.color != NIL:
            yield from self.left.__iter__()

        yield self.value

        if self.right.color != NIL:
            yield from self.right.__iter__()

    def __eq__(self, other):
        if self.color == NIL and self.color == other.color:
            return True

        if self.parent is None or other.parent is None:
            parents_are_same = self.parent is None and other.parent is None
        else:
            parents_are_same = self.parent.value == other.parent.value and self.parent.color == other.parent.color
        return self.value == other.value and self.color == other.color and parents_are_same

    def has_children(self) -> bool:
        """ Returns a boolean indicating if the node has children """
        return bool(self.get_children_count())

    def get_children_count(self) -> int:
        """ Returns the number of NOT NIL children the node has """
        if self.color == NIL:
            return 0
        return sum([int(self.left.color != NIL), int(self.right.color != NIL)])

class RedBlackTree:
    # every node has null nodes as children initially, create one such object for easy management
    NIL_LEAF = Node(value=None, color=NIL, parent=None)

    def __init__(self):
        self.count = 0
        self.root = None
        self.ROTATIONS = {
            # Used for deletion and uses the sibling's relationship with his parent as a guide to the rotation
            'L': self._right_rotation,
            'R': self._left_rotation
        }

    def __iter__(self):
        if not self.root:
            return list()
        yield from self.root.__iter__()

    def add(self, value):
        if not self.root:
            self.root = Node(value, color=BLACK, parent=None, left=self.NIL_LEAF, right=self.NIL_LEAF)
            self.count += 1
            return
        parent, node_dir = self._find_parent(value)
        if node_dir is None:
            return  # value is in the tree
        new_node = Node(value=value, color=RED, parent=parent, left=self.NIL_LEAF, right=self.NIL_LEAF)
        if node_dir == 'L':
            parent.left = new_node
        else:
            parent.right = new_node

        self._try_rebalance(new_node)
        self.count += 1

    def remove(self, value):
        """
        Try to get a node with 0 or 1 children.
        Either the node we're given has 0 or 1 children or we get its successor.
        """
        node_to_remove = self.find_node(value)
        if node_to_remove is None:  # node is not in the tree
            return
        if node_to_remove.get_children_count() == 2:
            # find the in-order successor and replace its value.
            # then, remove the successor
            successor = self._find_in_order_successor(node_to_remove)
            node_to_remove.value = successor.value  # switch the value
            node_to_remove = successor

        # has 0 or 1 children!
        self._remove(node_to_remove)
        self.count -= 1

    def contains(self, value) -> bool:
        """ Returns a boolean indicating if the given value is present in the tree """
        return bool(self.find_node(value))

    def ceil(self, value) -> int or None:
        """
        Given a value, return the closest value that is equal or bigger than it,
        returning None when no such exists
        """
        if self.root is None: return None
        last_found_val = None if self.root.value < value else self.root.value

        def find_ceil(node):
            nonlocal last_found_val
            if node == self.NIL_LEAF:
                return None
            if node.value == value:
                last_found_val = node.value
                return node.value
            elif node.value < value:
                # go right
                return find_ceil(node.right)
            else:
                # this node is bigger, save its value and go left
                last_found_val = node.value

                return find_ceil(node.left)
        find_ceil(self.root)
        return last_found_val

    def floor(self, value) -> int or None:
        """
        Given a value, return the closest value that is equal or less than it,
        returning None when no such exists
        """
        if self.root is None: return None
        last_found_val = None if self.root.value > value else self.root.value

        def find_floor(node):
            nonlocal last_found_val
            if node == self.NIL_LEAF:
                return None
            if node.value == value:
                last_found_val = node.value
                return node.value
            elif node.value < value:
                # this node is smaller, save its value and go right, trying to find a cloer one
                last_found_val = node.value

                return find_floor(node.right)
            else:
                return find_floor(node.left)

        find_floor(self.root)
        return last_found_val

    def _remove(self, node):
        """
        Receives a node with 0 or 1 children (typically some sort of successor)
        and removes it according to its color/children
        :param node: Node with 0 or 1 children
        """
        left_child = node.left
        right_child = node.right
        not_nil_child = left_child if left_child != self.NIL_LEAF else right_child
        if node == self.root:
            if not_nil_child != self.NIL_LEAF:
                # if we're removing the root and it has one valid child, simply make that child the root
                self.root = not_nil_child
                self.root.parent = None
                self.root.color = BLACK
            else:
                self.root = None
        elif node.color == RED:
            if not node.has_children():
                # Red node with no children, the simplest remove
                self._remove_leaf(node)
            else:
                """
                Since the node is red he cannot have a child.
                If he had a child, it'd need to be black, but that would mean that
                the black height would be bigger on the one side and that would make our tree invalid
                """
                raise Exception('Unexpected behavior')
        else:  # node is black!
            if right_child.has_children() or left_child.has_children():  # sanity check
                raise Exception('The red child of a black node with 0 or 1 children'
                                ' cannot have children, otherwise the black height of the tree becomes invalid! ')
            if not_nil_child.color == RED:
                """
                Swap the values with the red child and remove it  (basically un-link it)
                Since we're a node with one child only, we can be sure that there are no nodes below the red child.
                """
                node.value = not_nil_child.value
                node.left = not_nil_child.left
                node.right = not_nil_child.right
            else:  # BLACK child
                # 6 cases :o
                self._remove_black_node(node)

    def _remove_leaf(self, leaf):
        """ Simply removes a leaf node by making it's parent point to a NIL LEAF"""
        if leaf.value >= leaf.parent.value:
            # in those weird cases where they're equal due to the successor swap
            leaf.parent.right = self.NIL_LEAF
        else:
            leaf.parent.left = self.NIL_LEAF

    def _remove_black_node(self, node):
        """
        Loop through each case recursively until we reach a terminating case.
        What we're left with is a leaf node which is ready to be deleted without consequences
        """
        self.__case_1(node)
        self._remove_leaf(node)

    def __case_1(self, node):
        """
        Case 1 is when there's a double black node on the root
        Because we're at the root, we can simply remove it
        and reduce the black height of the whole tree.

            __|10B|__                  __10B__
           /         \      ==>       /       \
          9B         20B            9B        20B
        """
        if self.root == node:
            node.color = BLACK
            return
        self.__case_2(node)

    def __case_2(self, node):
        """
        Case 2 applies when
            the parent is BLACK
            the sibling is RED
            the sibling's children are BLACK or NIL
        It takes the sibling and rotates it

                         40B                                              60B
                        /   \       --CASE 2 ROTATE-->                   /   \
                    |20B|   60R       LEFT ROTATE                      40R   80B
    DBL BLACK IS 20----^   /   \      SIBLING 60R                     /   \
                         50B    80B                                |20B|  50B
            (if the sibling's direction was left of it's parent, we would RIGHT ROTATE it)
        Now the original node's parent is RED
        and we can apply case 4 or case 6
        """
        parent = node.parent
        sibling, direction = self._get_sibling(node)
        if sibling.color == RED and parent.color == BLACK and sibling.left.color != RED and sibling.right.color != RED:
            self.ROTATIONS[direction](node=None, parent=sibling, grandfather=parent)
            parent.color = RED
            sibling.color = BLACK
            return self.__case_1(node)
        self.__case_3(node)

    def __case_3(self, node):
        """
        Case 3 deletion is when:
            the parent is BLACK
            the sibling is BLACK
            the sibling's children are BLACK
        Then, we make the sibling red and
        pass the double black node upwards

                            Parent is black
               ___50B___    Sibling is black                       ___50B___
              /         \   Sibling's children are black          /         \
           30B          80B        CASE 3                       30B        |80B|  Continue with other cases
          /   \        /   \        ==>                        /  \        /   \
        20B   35R    70B   |90B|<---REMOVE                   20B  35R     70R   X
              /  \                                               /   \
            34B   37B                                          34B   37B
        """
        parent = node.parent
        sibling, _ = self._get_sibling(node)
        if (sibling.color == BLACK and parent.color == BLACK
           and sibling.left.color != RED and sibling.right.color != RED):
            # color the sibling red and forward the double black node upwards
            # (call the cases again for the parent)
            sibling.color = RED
            return self.__case_1(parent)  # start again

        self.__case_4(node)

    def __case_4(self, node):
        """
        If the parent is red and the sibling is black with no red children,
        simply swap their colors
        DB-Double Black
                __10R__                   __10B__        The black height of the left subtree has been incremented
               /       \                 /       \       And the one below stays the same
             DB        15B      ===>    X        15R     No consequences, we're done!
                      /   \                     /   \
                    12B   17B                 12B   17B
        """
        parent = node.parent
        if parent.color == RED:
            sibling, direction = self._get_sibling(node)
            if sibling.color == BLACK and sibling.left.color != RED and sibling.right.color != RED:
                parent.color, sibling.color = sibling.color, parent.color  # switch colors
                return  # Terminating
        self.__case_5(node)

    def __case_5(self, node):
        """
        Case 5 is a rotation that changes the circumstances so that we can do a case 6
        If the closer node is red and the outer BLACK or NIL, we do a left/right rotation, depending on the orientation
        This will showcase when the CLOSER NODE's direction is RIGHT

              ___50B___                                                    __50B__
             /         \                                                  /       \
           30B        |80B|  <-- Double black                           35B      |80B|        Case 6 is now
          /  \        /   \      Closer node is red (35R)              /   \      /           applicable here,
        20B  35R     70R   X     Outer is black (20B)               30R    37B  70R           so we redirect the node
            /   \                So we do a LEFT ROTATION          /   \                      to it :)
          34B  37B               on 35R (closer node)           20B   34B
        """
        sibling, direction = self._get_sibling(node)
        closer_node = sibling.right if direction == 'L' else sibling.left
        outer_node = sibling.left if direction == 'L' else sibling.right
        if closer_node.color == RED and outer_node.color != RED and sibling.color == BLACK:
            if direction == 'L':
                self._left_rotation(node=None, parent=closer_node, grandfather=sibling)
            else:
                self._right_rotation(node=None, parent=closer_node, grandfather=sibling)
            closer_node.color = BLACK
            sibling.color = RED

        self.__case_6(node)

    def __case_6(self, node):
        """
        Case 6 requires
            SIBLING to be BLACK
            OUTER NODE to be RED
        Then, does a right/left rotation on the sibling
        This will showcase when the SIBLING's direction is LEFT

                            Double Black
                    __50B__       |                               __35B__
                   /       \      |                              /       \
      SIBLING--> 35B      |80B| <-                             30R       50R
                /   \      /                                  /   \     /   \
             30R    37B  70R   Outer node is RED            20B   34B 37B    80B
            /   \              Closer node doesn't                           /
         20B   34B                 matter                                   70R
                               Parent doesn't
                                   matter
                               So we do a right rotation on 35B!
        """
        sibling, direction = self._get_sibling(node)
        outer_node = sibling.left if direction == 'L' else sibling.right

        def __case_6_rotation(direction):
            parent_color = sibling.parent.color
            self.ROTATIONS[direction](node=None, parent=sibling, grandfather=sibling.parent)
            # new parent is sibling
            sibling.color = parent_color
            sibling.right.color = BLACK
            sibling.left.color = BLACK

        if sibling.color == BLACK and outer_node.color == RED:
            return __case_6_rotation(direction)  # terminating

        raise Exception('We should have ended here, something is wrong')

    def _try_rebalance(self, node):
        """
        Given a red child node, determine if there is a need to rebalance (if the parent is red)
        If there is, rebalance it
        """
        parent = node.parent
        value = node.value
        if (parent is None  # what the fuck? (should not happen)
           or parent.parent is None  # parent is the root
           or (node.color != RED or parent.color != RED)):  # no need to rebalance
            return
        grandfather = parent.parent
        node_dir = 'L' if parent.value > value else 'R'
        parent_dir = 'L' if grandfather.value > parent.value else 'R'
        uncle = grandfather.right if parent_dir == 'L' else grandfather.left
        general_direction = node_dir + parent_dir

        if uncle == self.NIL_LEAF or uncle.color == BLACK:
            # rotate
            if general_direction == 'LL':
                self._right_rotation(node, parent, grandfather, to_recolor=True)
            elif general_direction == 'RR':
                self._left_rotation(node, parent, grandfather, to_recolor=True)
            elif general_direction == 'LR':
                self._right_rotation(node=None, parent=node, grandfather=parent)
                # due to the prev rotation, our node is now the parent
                self._left_rotation(node=parent, parent=node, grandfather=grandfather, to_recolor=True)
            elif general_direction == 'RL':
                self._left_rotation(node=None, parent=node, grandfather=parent)
                # due to the prev rotation, our node is now the parent
                self._right_rotation(node=parent, parent=node, grandfather=grandfather, to_recolor=True)
            else:
                raise Exception("{} is not a valid direction!".format(general_direction))
        else:  # uncle is RED
            self._recolor(grandfather)

    def __update_parent(self, node, parent_old_child, new_parent):
        """
        Our node 'switches' places with the old child
        Assigns a new parent to the node.
        If the new_parent is None, this means that our node becomes the root of the tree
        """
        node.parent = new_parent
        if new_parent:
            # Determine the old child's position in order to put node there
            if new_parent.value > parent_old_child.value:
                new_parent.left = node
            else:
                new_parent.right = node
        else:
            self.root = node

    def _right_rotation(self, node, parent, grandfather, to_recolor=False):
        grand_grandfather = grandfather.parent
        self.__update_parent(node=parent, parent_old_child=grandfather, new_parent=grand_grandfather)

        old_right = parent.right
        parent.right = grandfather
        grandfather.parent = parent

        grandfather.left = old_right  # save the old right values
        old_right.parent = grandfather

        if to_recolor:
            parent.color = BLACK
            node.color = RED
            grandfather.color = RED

    def _left_rotation(self, node, parent, grandfather, to_recolor=False):
        grand_grandfather = grandfather.parent
        self.__update_parent(node=parent, parent_old_child=grandfather, new_parent=grand_grandfather)

        old_left = parent.left
        parent.left = grandfather
        grandfather.parent = parent

        grandfather.right = old_left  # save the old left values
        old_left.parent = grandfather

        if to_recolor:
            parent.color = BLACK
            node.color = RED
            grandfather.color = RED

    def _recolor(self, grandfather):
        grandfather.right.color = BLACK
        grandfather.left.color = BLACK
        if grandfather != self.root:
            grandfather.color = RED
        self._try_rebalance(grandfather)

    def _find_parent(self, value):
        """ Finds a place for the value in our binary tree"""
        def inner_find(parent):
            """
            Return the appropriate parent node for our new node as well as the side it should be on
            """
            if value == parent.value:
                return None, None
            elif parent.value < value:
                if parent.right.color == NIL:  # no more to go
                    return parent, 'R'
                return inner_find(parent.right)
            elif value < parent.value:
                if parent.left.color == NIL:  # no more to go
                    return parent, 'L'
                return inner_find(parent.left)

        return inner_find(self.root)

    def find_node(self, value):
        def inner_find(root):
            if root is None or root == self.NIL_LEAF:
                return None
            if value > root.value:
                return inner_find(root.right)
            elif value < root.value:
                return inner_find(root.left)
            else:
                return root

        found_node = inner_find(self.root)
        return found_node

    def _find_in_order_successor(self, node):
        right_node = node.right
        left_node = right_node.left
        if left_node == self.NIL_LEAF:
            return right_node
        while left_node.left != self.NIL_LEAF:
            left_node = left_node.left
        return left_node

    def _get_sibling(self, node):
        """
        Returns the sibling of the node, as well as the side it is on
        e.g

            20 (A)
           /     \
        15(B)    25(C)

        _get_sibling(25(C)) => 15(B), 'R'
        """
        parent = node.parent
        if node.value >= parent.value:
            sibling = parent.left
            direction = 'L'
        else:
            sibling = parent.right
            direction = 'R'
        return sibling, direction


text:
from rb_tree import RedBlackTree
from random import shuffle

class My_pair:
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def increment_value(self):
        self.value += 1

    def __lt__(self, other):
        return self.key < other.key

    def __le__(self, other):
        return self.key <= other.key

    def __gt__(self, other):
        return self.key > other.key

    def __ge__(self, other):
        return self.key >= other.key

    def __eq__(self, other):
        if self is None or other is None:
            return self is None and other is None
        return self.key == other.key

    def __ne__(self, other):
        return not self == other

def main():
    n = 10
    li = [i for i in range(n)]
    shuffle(li)
    print(li)
    print(func(li))

def func(li):
    tree = RedBlackTree()
    depths = []
    for num in li:
        next_node = tree.ceil(My_pair(num, None))
        prev_node = tree.floor(My_pair(num, None))
        parent_depth = -1
        for node in (next_node, prev_node):
            if node != None:
                parent_depth = max(parent_depth, node.value)
        tree.add(My_pair(num, parent_depth + 1))
        depths.append(parent_depth + 1)
    return depths

if __name__ == '__main__':
    main()


text:
from rb_tree import RedBlackTree
from random import shuffle

class My_pair:
    def __init__(self, key, value):
        self.key = key
        self.value = value

    def increment_value(self):
        self.value += 1

    def __lt__(self, other):
        return self.key < other.key

    def __le__(self, other):
        return self.key <= other.key

    def __gt__(self, other):
        return self.key > other.key

    def __ge__(self, other):
        return self.key >= other.key

    def __eq__(self, other):
        if self is None or other is None:
            return self is None and other is None
        return self.key == other.key

    def __ne__(self, other):
        return not self == other

def main():
    n = 10
    li = [i for i in range(n)]
    shuffle(li)
    print(li)
    print(func(li))

def func(li):
    #Implement the function

if __name__ == '__main__':
    main()


text:
from test_helper import run_common_tests, failed, passed, get_answer_placeholders
from random import shuffle
from random import randint
from task import func as func
from task_copy import func as func_judge

def test_generator(n):
    li = [i for i in range(n)]
    shuffle(li)
    return li

if __name__ == '__main__':
    test_nums = [10, 10, 100, 100, 10000]
    for test_num in test_nums:
        li = test_generator(test_num)
        user_li = func(li[0:len(li)])
        judge_li = func_judge(li[0:len(li)])
        if user_li != judge_li:
            failed("Wrong Answer! Input: " + str(li) +
                   " Your Answer: " + str(user_li) +
                   " Expected Answer: " + str(judge_li))
    print("PASS")