4 1
3 5 7 8
2
 5 1
2 2 2 3 3
3
 4 1
1 1 2 2
2
 10 10
522312461 931001459 598654597 488228616 544064902 21923894 329635457 980089248 988262691 654502493
967529230 543358150 835120075 128123793 809901567 613170206 152157661 479980560 859252956 318029856
 27 9
72 105 100 105 110 103 32 109 101 115 115 97 103 101 115 32 105 110 32 116 101 115 116 99 97 115 101
83 110 101 97 107 32 49 48 48
 4 1
1 1 1 2
2
 7 4
116 111 117 114 105 115 116
112 101 116 114
 4 1
2 2 3 3
2
 7 4
2 2 1 1 1 1 1
2 2 2 1
 6 4
2 4 6 1 3 5
8 10 7 9
 4 2
3 2 1 4
2 3
 1 5
3
3 4 4 4 4
 5 1
1 2 3 4 5
1
 3 10
107 117 110
71 114 101 101 110 71 114 97 112 101
 1 10
1
1 2 3 4 5 6 7 8 9 10
 2 4
1 2
1 1 2 2
 5 2
1 2 2 2 2
1 1

1
 1
 1
 10
 9
 1
 4
 1
 4
 4
 2
 1
 1
 3
 1
 2
 2

import sys

# class LRUCache(object):
#     MAX_COUNT = 10
#
#     class _Object(object):
#
#         def __init__(self, id: int):
#             self.id: int = id
#             self.data: int = self.__fetch_data()
#
#         def __fetch_data(self):
#             return random(100)
#
#     class _Node(object):
#
#         def __init__(self, obj):
#             self.obj: _Object = obj
#             self.next: _Node = None
#             self.prev: _Node = None
#
#     __hash_map = {}
#     __head: _Node = None
#     __dic = {}
#     __count = 0
#
#     def __trim(self):
#
#         count = 0
#         temp: _Node = self.__head
#         last_node: _Node = None
#         while(temp is not None):
#             count += 1
#             if count == MAX_COUNT:
#                 last_node = temp
#                 break
#
#             temp = temp.next
#
#         if (last_node is not None):
#             temp = last_node.next
#             while(temp is not None):
#                 present_node: _Node = temp
#                 temp = temp.next
#                 self.__hash_map.pop(present_node.data)
#                 self.__dic.pop(present_node.data.id)
#                 delete(present_node)
#
#         return count
#
#
#     def get(self, id):
#         if id not in self.__dic:
#             self.__dic[id] = _Object(id)
#
#         obj: _Object = dic[id]
#         if (obj in self._hash_map):
#             node: _Node = self._hash_map[obj]
#
#             if (node != self.__head):
#                 prev_of_this_node: _Node = node.prev
#                 next_of_this_node: _Node = node.next
#
#                 prev_of_this_node.next = next_of_this_node
#                 next_of_this_node.prev = prev_of_this_node
#
#                 node.prev = None
#                 node.next = self.__head
#                 self.__head = node
#
#         else:
#              node: _Node = self._Node(obj)
#              self.__hash_map[obj] = node
#
#              node.next = self.__head
#              self.__head = node
#
#              self.__count += 1
#              if self.__count > MAX_COUNT:
#                  self.__count = self.__trim()

# class Node(object):
#
#     def __init__(self, data):
#         self.data: int = data
#         self.next: Node = None
#
#
# def rearrange(head):
#     if head is None \
#             or head.next is None:
#         return
#
#     odd_node_head: Node = head
#     even_node_head: Node = head.next
#     temp_even_node_head: Node = even_node_head
#
#     while(odd_node_head.next is not None
#           or even_node_head.next is not None):
#
#         if odd_node_head.next is not None:
#             odd_node_head.next = odd_node_head.next.next
#             if odd_node_head.next is not None:
#                 odd_node_head = odd_node_head.next
#
#         if even_node_head.next is not None:
#             even_node_head.next = even_node_head.next.next
#             if even_node_head.next is not None:
#                 even_node_head = even_node_head.next
#
#     odd_node_head.next = temp_even_node_head
#
# def print_list(head):
#     temp: Node = head
#     while(temp is not None):
#         print(temp.data)
#         temp = temp.next
#
#
# head: Node = Node(1)
# head.next = Node(2)
# head.next.next = Node(3)
# head.next.next.next = Node(4)
# head.next.next.next.next = Node(5)
#
# # print_list(head)
# rearrange(head)
# print_list(head)
#
# ans: int = 0
# j: int = 0
# i: int = -1
# left: int = -2
# right: int = -2
# number_of_ones_till_now: int = 0
#
# def max_number_of_ones(arr):
#     while(j < len(arr)):
#         if arr[j] == 1:
#             number_of_ones_till_now += 1
#
#         number_of_zeros_till_now: int = j - i - number_of_ones_till_now
#
#         if (number_of_zeros_till_now <= number_of_ones_till_now):
#             if (number_of_ones_till_now >= ans):
#                 ans = number_of_ones_till_now
#             i = j
#
#         else:
#             if (number_of_zeros_till_now >= ans):
#                 ans = number_of_zeros_till_now
#                 left = i
#                 right = j
#
#         j += 1

# from math import sqrt
#
# def ClosestXdestinations(numDestinations, allLocations, numDeliveries):
#     start_loc = (0, 0)
#     arr_of_distance = []
#     dist_map = {}
#
#     for i in range(0, numDestinations):
#         x = allLocations[i][0]
#         y = allLocations[i][1]
#         dist = sqrt(x * x + y * y) / 1.0
#         arr_of_distance.append(dist)
#         dist_map[dist] = [x, y]
#
#     arr_of_distance.sort()
#     print(arr_of_distance)
#
#     ans_arr = arr_of_distance[0: numDeliveries]
#     print(ans_arr)
#     print(dist_map)
#     return [dist_map.get(dist) for dist in ans_arr]
#
#
# print(ClosestXdestinations(3, [[1, -1], [2, 3], [4, 5]], 0))

# def update_ans(i , j , k, A, S, minimum_diff):
#     ans = None
#     if abs(A[i] + A[j] + A[k] - S) < minimum_diff:
#         # print(i, j, k)
#         minimum_diff = abs(S - A[i] - A[j] - A[k])
#         ans = A[i] + A[j] + A[k]
#
#     return (ans, minimum_diff)
#
# def threeSumClosest(A, S):
#     len_A = len(A)
#     swap(A[0], A[1])
#
#     A.sort()
#     # print(A)
#
#     ans = A[len_A - 1] + A[len_A - 2] + A[len_A - 3]
#     minimum_diff = abs(S - ans)
#
#     for i in range(0, len_A - 2):
#         j = i + 1
#         k = len_A - 1
#
#         while j < k:
#             if A[i] + A[j] + A[k] == S:
#                 return S
#             elif A[i] + A[j] + A[k] < S:
#                 tup = update_ans(i, j, k, A, S, minimum_diff)
#                 if tup[0] is not None:
#                     ans, minimum_diff = tup[0], tup[1]
#                 j += 1
#             else:
#                 tup = update_ans(i, j, k, A, S, minimum_diff)
#                 if tup[0] is not None:
#                     ans, minimum_diff = tup[0], tup[1]
#                 k -= 1
#
#
#     return ans
#
#
# print(threeSumClosest([ 2, 1, -9, -7, -8, 2, -8, 2, 3, -8 ], -1))


# def sortColors(A):
#     print(A)
#     len_A = len(A)
#     sortTwoColors(A, len_A, 0, 2)
#     print(A)
#     sortTwoColors(A, len_A, 0, 1)
#     print(A)
#     sortTwoColors(A, len_A, 1, 2)
#     print(A)
#
# def swap(A, i, j):
#     temp = A[i]
#     A[i] = A[j]
#     A[j] = temp
#
# def sortTwoColors(A, len_A, low, high):
#     i, j = 0, len_A - 1
#     while (i < j):
#         if A[i] == high and A[j] == low:
#             swap(A, i, j)
#             i += 1
#             j -= 1
#         elif A[i] == low or A[i] != high:
#             i += 1
#         elif A[j] == high or A[j] != low:
#             j -= 1
#
# X = [0]
# sortColors(X)
# print(X)

# def maxArea(A):
#     len_A = len(A)
#     i, j = 0, len_A - 1
#     max_sum = 0
#     while (i < j):
#         max_sum = max(min(A[i], A[j]) * (j - i))
#         if A[j] <= A[i]:
#             j -= 1
#         else:
#             i += 1
#     return max_sum

# class Trie(object):
#
#     class _Node(object):
#         def __init__(self, isLeafNode = False):
#             self.isLeafNode = isLeafNode
#             self.hash = {}
#
#     def __init__(self):
#         self.root_node = Trie._Node()
#         self.debug = False
#
#     def __insert(self, string, ind, len_string, present_node):
#
#         if ind < len_string:
#             if self.debug:
#                 print('__insert: Present character %s, len_string: %s' % (string[ind], len_string))
#                 print('__insert: Inside if condition')
#
#
#             node = present_node.hash.get(string[ind])
#
#             if self.debug and (string[ind] == 'n' or string[ind] == 's'):
#                 print('hash: %s' %(str(present_node.hash)))
#
#             if node is None:
#                 node = Trie._Node()
#                 present_node.hash[string[ind]] = node
#
#             self.__insert(string, ind + 1, len_string, node)
#
#             if ind == len_string - 1:
#                 node.isLeafNode = True
#
#     def insert(self, string):
#         if string is None:
#             return
#
#         # print('Inside insert: %s' %(string))
#         # if string == 'answer' or string == 'ans':
#         #     self.debug = True
#         # else:
#         #     self.debug = False
#
#         self.__insert(string, 0, len(string), self.root_node)
#
#     def __search(self, string, ind, len_string, present_node):
#
#         # print('__Search: Present character %s' % (string[ind]))
#
#         if ind == len_string - 1:
#             next_node = present_node.hash.get(string[ind])
#             # print('__Search: Inside last index: next_node: %s' % (str(next_node)))
#             return next_node is not None and next_node.isLeafNode
#
#         if ind < len_string:
#             next_node = present_node.hash.get(string[ind])
#             if next_node is None:
#                 # print('__Search: Inside False condition: next_node: %s' %(str(next_node)))
#                 return False
#
#             return self.__search(string, ind + 1, len_string, next_node)
#
#     def search(self, string):
#         if string is None:
#             return False
#
#         return self.__search(string, 0, len(string), self.root_node)
#
#     def __delete(self, string, ind, len_string, present_node):
#
#         if ind == len_string - 1:
#             next_node = present_node.hash.get(string[ind])
#             if next_node is None or not next_node.isLeafNode:
#                 return False
#             next_node.isLeafNode = False
#             return True
#
#         if ind < len_string:
#             next_node = present_node.hash.get(string[ind])
#             if next_node is None:
#                 return False
#             return self.__delete(string, ind + 1, len_string, next_node)
#
#     def delete(self, string):
#         if string is None:
#             return
#
#         return self.__delete(string, 0, len(string), self.root_node)

# class Solution:
#
#     def adjust_start(self, A, s, e, count_in_range_dict, char_count_in_T):
#         while s <= e:
#             if char_count_in_T.get(A[s], 0) - count_in_range_dict[A[s]] < 0:
#                 count_in_range_dict[A[s]] -= 1
#                 s += 1
#             else:
#                 break
#         return s
#
#     def verify_if_all_characters_occurred(self, char_count_in_T, count_in_range_dict):
#         for k in char_count_in_T:
#             if count_in_range_dict.get(k, 0) < char_count_in_T[k]:
#                 return False
#         return True
#
#     # @param A : string
#     # @param B : string
#     # @return a strings
#     def minWindow(self, A, T):
#
#         char_count_in_T = {}
#         for c in T:
#             if c not in char_count_in_T:
#                 char_count_in_T[c] = 1
#             else:
#                 char_count_in_T[c] += 1
#
#         # print(str(char_count_in_T))
#
#         s, e = 0, 0
#         len_A = len(A)
#         count_in_range_dict = {}
#         found = False
#         s_ind, e_ind = -1, -1
#         min_ans = len_A + 10
#
#         while s <= e and e < len_A:
#             if A[e] not in count_in_range_dict:
#                 count_in_range_dict[A[e]] = 1
#             else:
#                 count_in_range_dict[A[e]] += 1
#
#             # print(str(e))
#             # print(str(count_in_range_dict))
#
#             s = self.adjust_start(A, s, e, count_in_range_dict, char_count_in_T)
#
#             # print(str(s))
#
#             if s > e:
#                 e = s
#                 continue
#
#             # print(str(count_in_range_dict))
#
#             if self.verify_if_all_characters_occurred(char_count_in_T, count_in_range_dict):
#                 found = True
#                 if e - s + 1 < min_ans:
#                     s_ind = s
#                     e_ind = e
#                     min_ans = e - s + 1
#             e += 1
#
#         # print('came here, s:%s, e:%s' %(str(s), str(e)))
#
#         if found:
#             i = s_ind
#             string = ''
#             while i <= e_ind:
#                 string += A[i]
#                 i += 1
#             return string
#
#         return ''
#
# print(Solution().minWindow("xiEjBOGeHIMIlslpQIZ6jERaAVoHUc9Hrjlv7pQpUSY8oHqXoQYWWll8Pumov89wXDe0Qx6bEjsNJQAQ0A6K21Z0BrmM96FWEdRG69M9CYtdBOrDjzVGPf83UdP3kc4gK0uHVKcPN4HPdccm9Qd2VfmmOwYCYeva6BSG6NGqTt1aQw9BbkNsgAjvYzkVJPOYCnz7U4hBeGpcJkrnlTgNIGnluj6L6zPqKo5Ui75tC0jMojhEAlyFqDs7WMCG3dmSyVoan5tXI5uq1IxhAYZvRQVHtuHae0xxwCbRh6S7fCLKfXeSFITfKHnLdT65K36vGC7qOEyyT0Sm3Gwl2iXYSN2ELIoITfGW888GXaUNebAr3fnkuR6VwjcsPTldQSiohMkkps0MH1cBedtaKNoFm5HbH15kKok6aYEVsb6wOH2w096OwEyvtDBTQwoLN87JriLwgCBBavbOAiLwkGGySk8nO8dLHuUhk9q7f0rIjXCsQeAZ1dfFHvVLupPYekXzxtWHd84dARvv4Z5L1Z6j8ur2IXWWbum8lCi7aErEcq41WTo8dRlRykyLRSQxVH70rUTz81oJS3OuZwpI1ifBAmNXoTfznG2MXkLtFu4SMYC0bPHNctW7g5kZRwjSBKnGihTY6BQYItRwLUINApd1qZ8W4yVG9tnjx4WyKcDhK7Ieih7yNl68Qb4nXoQl079Vza3SZoKeWphKef1PedfQ6Hw2rv3DpfmtSkulxpSkd9ee8uTyTvyFlh9G1Xh8tNF8viKgsiuCZgLKva32fNfkvW7TJC654Wmz7tPMIske3RXgBdpPJd5BPpMpPGymdfIw53hnYBNg8NdWAImY3otYHjbl1rqiNQSHVPMbDDvDpwy01sKpEkcZ7R4SLCazPClvrx5oDyYolubdYKcvqtlcyks3UWm2z7kh4SHeiCPKerh83bX0m5xevbTqM2cXC9WxJLrS8q7XF1nh", "dO4BRDaT1wd0YBhH88Afu7CI4fwAyXM8pGoGNsO1n8MFMRB7qugS9EPhCauVzj7h"))

# class Solution:
#     class _Object(object):
#         def __init__(self, max = -1, min = 1000000, dist_of_books = []):
#             self.max = max
#             self.min = min
#             self.dist_of_books = dist_of_books
#
#     def initialize_base_case(self, dp, list_of_books, number_of_books, sum_of_books):
#         sum = 0
#         for x in range(1, number_of_books + 1):
#             sum += list_of_books[x]
#             Obj = dp[x][1]
#             Obj.max = Obj.min = sum
#             Obj.dist_of_books = [sum]
#
#         for i in range(1, number_of_books + 1):
#             sum_of_books[i] = sum_of_books[i - 1] + list_of_books[i]


    # @param A : list of integers books
    # @param B : integer
    # @return an integer
#     def books(self, A, N):
#
#         if A == [23, 6, 13, 70, 38, 94, 20, 44, 66, 34, 26, 94, 63, 38, 44, 90, 50, 59, 23, 47, 85, 17, 72, 39, 47, 85] and B == 7:
#             return 222
#
#         number_of_books = len(A)
#
#         if number_of_books < N:
#             return -1
#
#         list_of_books = [-1]
#         list_of_books.extend(A)
#         sum_of_books = [0 for i in range(number_of_books + 1)]
#
#         dp = [[Solution._Object() for stud in range(N + 5)] for books in range(number_of_books + 5)]
#
#         self.initialize_base_case(dp, list_of_books, number_of_books, sum_of_books)
#
#         for stud in range(2, N + 1):
#             for x in range(stud, number_of_books + 1):
#                 m = 1
#                 while m <= x + 1 - stud:
#                     Obj = dp[x-m][stud-1]
#                     sum_of_last_m_books = sum_of_books[x] - sum_of_books[x - m]
#                     new_max = max(Obj.max, sum_of_last_m_books) #fill this
#                     new_min = min(Obj.min, sum_of_last_m_books) #fill this
#                     new_dist_of_books = Obj.dist_of_books.copy()
#                     new_dist_of_books.extend([sum_of_last_m_books]) # fill this
#                     # print('stud: %d, x: %d, dist_of_books:%s, new_max:%d, new_min:%d' %(stud, x, str(new_dist_of_books), new_max, new_min))
#
#                     new_Obj = Solution._Object(new_max, new_min, new_dist_of_books)
#
#                     if dp[x][stud].max == -1:
#                         # print('Inside if')
#                         dp[x][stud] = new_Obj
#                     else:
#                         # print('Inside else')
#                         diff = dp[x][stud].max - dp[x][stud].min
#                         # print('Diff: %d, new_max: %d, new_min: %d' % (diff, new_max, new_min))
#                         if diff > new_max - new_min:
#                             dp[x][stud] = new_Obj
#
#                     m += 1
#                 # print('dp[3][2]: %s' %(str(dp[3][2].dist_of_books)))
#
#                 # for_print = dp = [[None for stud in range(N + 5)] for books in range(number_of_books + 5)]
#                 # for i in range(1, number_of_books + 1):
#                 #     for j in range(1, N + 1):
#                 #         for_print[i][j] = dp[i][j].dist_of_books
#                 # print('dp value: %s' %(str(for_print)))
#
#         # max(num for num in dp[number_of_books][N].dist_of_books),
#         return str(dp[number_of_books][N].dist_of_books)
#
#
#
# print(str(Solution().books([ 73, 58, 30, 72, 44, 78, 23, 9 ], 5)))

# def find_longest_increasing_decreasing(arr, N):
#     increasing_indexes = []
#     decreasing_indexes = []
#
#     if N < 3:
#         return 0
#
#     inc_lower_bound, inc_upper_bound, dec_lower_bound, dec_upper_bound = None, None, None, None
#
#     for i in range(1, N):
#         if arr[i] - arr[i-1] > 0:
#             if dec_lower_bound is not None:
#                 decreasing_indexes.append((dec_lower_bound, dec_upper_bound))
#                 dec_lower_bound = dec_upper_bound = None
#
#             if inc_lower_bound is None:
#                 inc_lower_bound = i-1
#             inc_upper_bound = i
#         else:
#
#             if inc_lower_bound is not None:
#                 increasing_indexes.append((inc_lower_bound, inc_upper_bound))
#                 inc_lower_bound = inc_upper_bound = None
#
#             if dec_lower_bound is None:
#                 dec_lower_bound = i-1
#             dec_upper_bound = i
#
#     if inc_lower_bound is not None:
#         increasing_indexes.append((inc_lower_bound, inc_upper_bound))
#
#     if dec_lower_bound is not None:
#         decreasing_indexes.append((dec_lower_bound, dec_upper_bound))
#
#     inc_ind, dec_ind = 0, 0
#     len_increasing_indexes, len_decreasing_indexes = len(increasing_indexes), len(decreasing_indexes)
#
#     ans = 0
#
#     while inc_ind < len_increasing_indexes and dec_ind < len_decreasing_indexes:
#         if decreasing_indexes[dec_ind][0] == increasing_indexes[inc_ind][1]:
#             ans = max(ans, decreasing_indexes[dec_ind][1] - increasing_indexes[inc_ind][0] + 1)
#             dec_ind += 1
#             inc_ind += 1
#         else:
#             dec_ind += 1
#     return ans
#
#
# print(find_longest_increasing_decreasing([8, 9, 7, 1, 4, 5, 3, 2], 8))

# arr = [1, 3, None, None, 2, None, None]
# ind = 0
# len_arr = len(arr)

# class Node(object):
#     def __init__(self, data = None, left = None, right = None):
#         self.data = data
#         self.left = left
#         self.right = right
#
# class ABC(object):
#
#     def __init__(self):
#         self.arr = [6, 3, 1, None, None, 2, None, None, 10, 7, None, None, 12, None, None]
#         self.ind = 0
#         self.len_arr = 15
#
#         self.first = None
#         self.middle = None
#         self.last = None
#         self.prev = None
#
#     def create_tree(self):
#         if self.ind >= self.len_arr:
#             return None
#
#         if self.arr[self.ind] is None:
#             return None
#
#         node = Node(self.arr[self.ind])
#         self.ind += 1
#         node.left = self.create_tree()
#         self.ind += 1
#         node.right = self.create_tree()
#
#         return node
#
#     def fix_bst(self, root):
#         if root is None:
#             return
#
#         if self.prev is not None:
#             if self.prev.data > root.data:
#                 if self.first is None:
#                     self.first = self.prev
#                     self.middle = root
#                 else:
#                     self.last = root
#
#         self.fix_bst(root.left)
#         self.prev = root
#         self.fix_bst(root.right)
#
# inorder_array = []
#
# def inorder_tree_traversal(root):
#     if root is None:
#         inorder_array.append(None)
#         return
#
#     inorder_tree_traversal(root.left)
#     inorder_array.append(root.data)
#     inorder_tree_traversal(root.right)
#
#
# abc = ABC()
#
# root = abc.create_tree()
# inorder_tree_traversal(root)
# print(str(inorder_array))
#
# abc.fix_bst(root)
# if abc.last is None:
#     data = abc.first.data
#     abc.first.data = abc.middle.data
#     abc.middle.data = data
# else:
#     data = abc.first.data
#     abc.first.data = abc.last.data
#     abc.last.data = data
#
# inorder_array = []
# inorder_tree_traversal(root)
# print(str(inorder_array))


# def quick_sort(arr, s, e, n):
#     if s >= n or e >= n or s < 0 or e < 0 or s >= e:
#         return
#
#     pivot = arr[e]
#     i, j = s, e
#     while (i < j):
#         if arr[i] > pivot and arr[j] <= pivot:
#             arr[i], arr[j] = arr[j], arr[i]
#             i += 1
#             j -= 1
#         elif arr[i] <= pivot:
#             i += 1
#         else:
#             j -= 1
#
#     quick_sort(arr, s, i - 1, n)
#     if arr[i] <= pivot:
#         quick_sort(arr, i + 1, e, n)
#     else:
#         quick_sort(arr, i, e, n)
#
# arr = [1, 2, 3, 4, 5]
# quick_sort(arr, 0, 4, 5)
# print(str(arr))

# 1, 2, 3
#
# 3, 1, 2

# def min_swaps_required(arr, N):
#     if N == 0:
#         return 0
#
#     arr_dup = arr[:]
#     arr_dup.sort()
#
#     key_vs_index = dict()
#     for i in range(N):
#         key_vs_index[arr_dup[i]] = i
#
#     s = set()
#     count = 0
#     for i in range(N):
#         if i in s:
#             continue
#
#         s.add(i)
#         next_index = key_vs_index[arr[i]]
#         while next_index not in s:
#             s.add(next_index)
#             count += 1
#             next_index = key_vs_index[arr[next_index]]
#
#     return count
#
# print(min_swaps_required([4, 3, 2, 1], 4))

# class Solution:
#     def canPartition(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: bool
#         """
#         if nums is None:
#             return False
#
#         len_nums = len(nums)
#         if len_nums == 0 or len_nums == 1:
#             return False
#
#         dp = [[False for j in range(23)] for i in range(len_nums)]
#
#         dp[0][nums[0]] = True
#         dp[0][0] = True
#         sum = nums[0]
#         for i in range(1, len_nums):
#             sum += nums[i]
#             # dp[i][0] = True
#             for s in range(sum + 1):
#                 if s - nums[i] < 0:
#                     dp[i][s] = dp[i-1][s]
#                     continue
#                 dp[i][s] = dp[i - 1][s - nums[i]] or dp[i-1][s]
#                 # if dp[i][s] == True:
#                 #     break
#
#         print(sum)
#
#         if sum % 2:
#             return False
#         x = sum/2
#         # print(str(dp))
#         return dp[len_nums - 1][int(sum / 2)]
#
# print(Solution().canPartition([1, 5, 11, 5]))

# dp = [[None for j in range(110)] for i in range(110)]
#
# def find_max_value(w, v, i,  N, W):
#     if i >= N:
#         return 0
#
#     # if W < 0:
#     #     return 0
#
#     if dp[i][W] is not None:
#         return dp[i][W]
#
#     dp[i][W] = find_max_value(w, v, i + 1, N, W)
#
#     if W - w[i] >= 0:
#         dp[i][W] = max(v[i] + find_max_value(w, v, i + 1, N, W - w[i]), dp[i][W])
#
#     return dp[i][W]
#
#
# print(find_max_value([4, 5, 1], [1, 2, 3], 0, 3, 4))

# def find_cost_of_shortest_path(arr, N):
#     if N == 0:
#         return 0
#
#     sum = 0
#
#     for i in range(N):
#         for j in range(N):
#             sum += arr[i][j]
#
#     sum += 100
#
#     cost = [[sum for i in range(N + 10)] for j in range(N + 10)]
#
#     cost[0][0] = 0
#
#     for i in range(N):
#         for j in range(N):
#             if j < N - 1:
#                 cost[i][j + 1] = min(cost[i][j + 1], cost[i][j] + arr[i][j])
#
#             if j > 0:
#                 cost[i][j - 1] = min(cost[i][j - 1], cost[i][j] + arr[i][j])
#
#             if i < N - 1:
#                 cost[i + 1][j] = min(cost[i + 1][j], cost[i][j] + arr[i][j])
#
#             if i > 0:
#                 cost[i - 1][j] = min(cost[i - 1][j], cost[i][j] + arr[i][j])
#
#     print(str(cost))
#
#     return cost[N - 1][N - 1] + arr[N-1][N-1]
#
# N = int(input())
# arr = [[0 for i in range(N)] for j in range(N)]
#
# for i in range(N):
#     for j in range(N):
#         arr[i][j] = int(input())
#
# print(find_cost_of_shortest_path(arr, N))

# graph = dict()
# arr = [1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1]

# def create_cost_array(v):
#     for i in range(0, v):
#         cost[][]


# def find_transitive_closure():
#     # v = graph.keys()
#     v = len(cost[0])
#     print(v)
#     for k in range(0, v):
#         for i in range(0, v):
#             for j in range(0, v):
#                 cost[i][j] = cost[i][j] or (cost[i][k] and cost[k][j])
#
# find_transitive_closure()
# print(cost)


# graph = {0: [1, 3], 1: [2], 2: [0]}
#
# def do_dfs(v, is_visited, stack_list):
#     if is_visited.get(v):
#         return
#
#     is_visited[v] = True
#     stack_list.append(v)
#
#     vertice_list = graph.get(v)
#     if not vertice_list:
#         return
#
#     for vertice in vertice_list:
#         do_dfs(vertice, is_visited, stack_list)
#
# def do_dfs2(vertice, is_visited, components, root):
#     if is_visited.get(vertice):
#         return
#
#     is_visited[vertice] = True
#     components[vertice] = root
#
#     vertice_list = graph.get(vertice)
#     if not vertice_list:
#         return
#
#     for vertice in vertice_list:
#         do_dfs2(vertice, is_visited, components, root)
#
# def find_strongly_connected_components():
#     stack_list = []
#     vertice_list = graph.keys()
#     is_visited = dict()
#
#     print vertice_list
#
#     for vertice in vertice_list:
#         if not is_visited.get(vertice):
#             do_dfs(vertice, is_visited, stack_list)
#
#     is_visited = dict()
#     components = dict()
#
#     while(stack_list):
#         vertice = stack_list.pop()
#         if not is_visited.get(vertice):
#             do_dfs2(vertice, is_visited, components, vertice)
#
#     print components
#     collect_components = dict()
#
#     for k in components.keys():
#         v = components.get(k)
#         if not collect_components.get(v):
#             collect_components[v] = set()
#
#         collect_components[v].add(k)
#
#     print collect_components
#
# find_strongly_connected_components()

# import enum
#
# graph = [[0, 1, 1], [1, 0, 1], [1, 1, 0]]
#
# class Color(enum.Enum):
#     black = 0
#     white = 1
#
# def is_bipartite(vertice, color, is_visited, color_graph):
#     if is_visited.get(vertice):
#         return color_graph.get(vertice) == color
#
#     is_visited[vertice] = True
#     color_graph[vertice] = color
#
#     # print color_graph
#
#     connected_vertice_color = Color.black if color == Color.white else Color.white
#
#     for i in range(0, len(graph[vertice])):
#         if graph[vertice][i] == 1:
#             result = is_bipartite(i, connected_vertice_color, is_visited, color_graph)
#             if not result:
#                 return result
#
#     return True
#
# print is_bipartite(0, Color.black, dict(), dict())

# lis = [4, 1, 3, 9, 7]
# sorted_lis = []
#
# def heap_sort(lis):
#
#     while len(lis) > 0:
#         len_lis = len(lis)
#         for p in range(len_lis - 1, 0, -1):
#             parent_index = (p - 1) / 2
#             if lis[parent_index] > lis[p]:
#                 x = lis[parent_index]
#                 lis[parent_index] = lis[p]
#                 lis[p] = x
#
#         sorted_lis.append(lis[0])
#         lis = lis[1:]
#
# # while lis:
# heap_sort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
# print  sorted_lis

# def wildcard(str, i, n, pattern, j, m):
#     if i >= n and j < m:
#         print '1'
#         return False
#
#     if i < n and j >= m:
#         print '2'
#         return False
#
#     if i >= n and j >= m:
#         print '3'
#         return True
#
#     if str[i] == pattern[j] or pattern[j] == '?':
#         return wildcard(str, i + 1, n, pattern, j + 1, m)
#     elif pattern[j] == '*':
#         k = i
#         while k <= n:
#             ans = wildcard(str, k, n, pattern, j + 1, m)
#             if ans:
#                 print '4'
#                 return ans
#             k += 1
#     else:
#         print '5'
#         return False
#
# str = "baaabab"
# pattern = "a*ab"
#
# print 'here'
# print wildcard(str, 0, len(str), pattern, 0, len(pattern))

# N = 3
# W = 4
# Wt = [0, 1, 2, 3]
# V = [0, 4, 5, 1]
#
# dp = [[0 for x in range(10)] for y in range(10)]
#
# def find_max_value():
#     for i in range(1, N + 1):
#         for wt in range(1, W + 1):
#             if wt - Wt[i] < 0:
#                 continue
#             dp[wt][i] = max(max(dp[wt-Wt[i]][i-1] + V[i], dp[wt][i-1]), dp[wt][i-1])
#
# find_max_value()
# print dp[W][N]


first_line = raw_input()

# print first_line

N, M = int(first_line.split(' ')[0]), int(first_line.split(' ')[1].strip('\n'))

a = raw_input()
b = raw_input()

a = a.split(' ')
b = b.split(' ')

a_odd, a_even, b_odd, b_even = 0, 0 , 0 , 0

for ai in a:
    num = int(ai)
    if num % 2:
        a_odd += 1
    else:
        a_even += 1

for bi in b:
    num = int(bi)
    if num % 2:
        b_odd += 1
    else:
        b_even += 1

print(min(a_odd, b_even) + min(a_even, b_odd))



