





from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

_UpperCAmelCase       : List[str]			     =       TypeVar("""T""")
_UpperCAmelCase       : Union[str, Any]			     =       TypeVar("""U""")

class      lowerCAmelCase							(      Generic[T, U]    ):
 def __init__(   self						:   int    ,  UpperCAmelCase						:   T | None    ,  UpperCAmelCase						:   U | None			)    ->			Dict:
     lowerCamelCase__					:   Optional[int]      				=	key
     lowerCamelCase__					:   int      				=	val
     lowerCamelCase__					:   DoubleLinkedListNode[T, U] | None      				=	None
     lowerCamelCase__					:   DoubleLinkedListNode[T, U] | None      				=	None







 def __repr__(   self						:   Dict			)    ->			str:
     return (
         F"""Node: key: {self.key}, val: {self.val}, """
         F"""has next: {bool(self.next			)}, has prev: {bool(self.prev			)}"""
     )


class      lowerCAmelCase							(      Generic[T, U]    ):
 def __init__(   self						:   Any			)    ->			None:
     lowerCamelCase__					:   DoubleLinkedListNode[T, U]      				=	DoubleLinkedListNode(UpperCAmelCase    ,  UpperCAmelCase			)
     lowerCamelCase__					:   DoubleLinkedListNode[T, U]      				=	DoubleLinkedListNode(UpperCAmelCase    ,  UpperCAmelCase			)
     lowerCamelCase__				,							lowerCamelCase__					:   Tuple      				=	self.rear, self.head
 def __repr__(   self						:   List[Any]			)    ->			str:
     lowerCamelCase__					:   str      				=	['DoubleLinkedList']
     lowerCamelCase__					:   Dict      				=	self.head
     while node.next is not None:
         rep.append(str(UpperCAmelCase			)			)
         lowerCamelCase__					:   List[str]      				=	node.next
     rep.append(str(self.rear			)			)
     return ",\n    ".join(UpperCAmelCase			)
 def   A_			(   self						:   List[str]    ,  UpperCAmelCase						:   DoubleLinkedListNode[T, U]			)    ->			None:
     lowerCamelCase__					:   Tuple      				=	self.rear.prev

     # All nodes other than self.head are guaranteed to have non-None previous
     assert previous is not None

     lowerCamelCase__					:   Optional[Any]      				=	node
     lowerCamelCase__					:   Any      				=	previous
     lowerCamelCase__					:   List[str]      				=	node
     lowerCamelCase__					:   List[Any]      				=	self.rear







 def   A_			(   self						:   Optional[Any]    ,  UpperCAmelCase						:   DoubleLinkedListNode[T, U]			)    ->			DoubleLinkedListNode[T, U] | None:

     if node.prev is None or node.next is None:
         return None

     lowerCamelCase__					:   List[Any]      				=	node.next
     lowerCamelCase__					:   Any      				=	node.prev
     lowerCamelCase__					:   int      				=	None
     lowerCamelCase__					:   Optional[int]      				=	None
     return node


class      lowerCAmelCase							(      Generic[T, U]    ):
 UpperCAmelCase__									=	{}
 def __init__(   self						:   Union[str, Any]    ,  UpperCAmelCase						:   int			)    ->			Optional[Any]:
     lowerCamelCase__					:   DoubleLinkedList[T, U]      				=	DoubleLinkedList()
     lowerCamelCase__					:   List[str]      				=	capacity
     lowerCamelCase__					:   str      				=	0
     lowerCamelCase__					:   Union[str, Any]      				=	0
     lowerCamelCase__					:   Optional[Any]      				=	0
     lowerCamelCase__					:   dict[T, DoubleLinkedListNode[T, U]]      				=	{}
 def __repr__(   self						:   List[Any]			)    ->			str:
     return (
         F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
         F"""capacity={self.capacity}, current size={self.num_keys})"""
     )
 def __contains__(   self						:   List[Any]    ,  UpperCAmelCase						:   T			)    ->			bool:
     return key in self.cache
 def   A_			(   self						:   str    ,  UpperCAmelCase						:   T			)    ->			U | None:
     # Note: pythonic interface would throw KeyError rather than return None

     if key in self.cache:
         self.hits += 1
         lowerCamelCase__					:   DoubleLinkedListNode[T, U]      				=	self.cache[key]
         lowerCamelCase__					:   Optional[Any]      				=	self.list.remove(self.cache[key]			)
         assert node == value_node

         # node is guaranteed not None because it is in self.cache
         assert node is not None
         self.list.add(UpperCAmelCase			)
         return node.val
     self.miss += 1
     return None
 def   A_			(   self						:   List[str]    ,  UpperCAmelCase						:   T    ,  UpperCAmelCase						:   U			)    ->			None:

     if key not in self.cache:
         if self.num_keys >= self.capacity:
             # delete first node (oldest) when over capacity
             lowerCamelCase__					:   int      				=	self.list.head.next

             # guaranteed to have a non-None first node when num_keys > 0
             # explain to type checker via assertions
             assert first_node is not None
             assert first_node.key is not None
             assert (
                 self.list.remove(UpperCAmelCase			) is not None
             )  # node guaranteed to be in list assert node.key is not None

             del self.cache[first_node.key]
             self.num_keys -= 1
         lowerCamelCase__					:   Optional[Any]      				=	DoubleLinkedListNode(UpperCAmelCase    ,  UpperCAmelCase			)
         self.list.add(self.cache[key]			)
         self.num_keys += 1

     else:
         # bump node to the end of the list, update value
         lowerCamelCase__					:   Union[str, Any]      				=	self.list.remove(self.cache[key]			)
         assert node is not None  # node guaranteed to be in list
         lowerCamelCase__					:   Optional[int]      				=	value
         self.list.add(UpperCAmelCase			)







 @classmethod
 def   A_			(   cls						:   Dict    ,  UpperCAmelCase						:   int = 128			)    ->			Callable[[Callable[[T], U]], Callable[..., U]]:

     def cache_decorator_inner(UpperCAmelCase						:   Callable[[T], U]			) -> Callable[..., U]:
         def cache_decorator_wrapper(*UpperCAmelCase						:   T			) -> U:
             if func not in cls.decorator_function_to_instance_map:
                 lowerCamelCase__					:   List[Any]      				=	LRUCache(UpperCAmelCase			)

             lowerCamelCase__					:   Optional[int]      				=	cls.decorator_function_to_instance_map[func].get(args[0]			)
             if result is None:
                 lowerCamelCase__					:   List[Any]      				=	func(*UpperCAmelCase			)
                 cls.decorator_function_to_instance_map[func].put(args[0]    ,  UpperCAmelCase			)
             return result

         def cache_info() -> LRUCache[T, U]:
             return cls.decorator_function_to_instance_map[func]

         setattr(UpperCAmelCase    ,  'cache_info'    ,  UpperCAmelCase			)  # noqa: B010

         return cache_decorator_wrapper

     return cache_decorator_inner


if __name__ == "__main__":
    import doctest

    doctest.testmod()












from __future__ import annotations

from collections.abc import Iterable, Iterator
from dataclasses import dataclass

_UpperCAmelCase       : Union[str, Any]			     =       (3, 9, -11, 0, 7, 5, 1, -1)
_UpperCAmelCase       : Union[str, Any]			     =       (4, 6, 2, 0, 8, 10, 3, -2)

@dataclass
class      lowerCAmelCase							:
 UpperCAmelCase__									=	42
 UpperCAmelCase__									=	42


class      lowerCAmelCase							:
 def __init__(   self						:   Any    ,  UpperCAmelCase						:   Iterable[int]			)    ->			None:
     lowerCamelCase__					:   Node | None      				=	None
     for i in sorted(UpperCAmelCase    ,  reverse=UpperCAmelCase			):
         lowerCamelCase__					:   Tuple      				=	Node(UpperCAmelCase    ,  self.head			)
 def __iter__(   self						:   Optional[int]			)    ->			Iterator[int]:
     lowerCamelCase__					:   str      				=	self.head
     while node:
         yield node.data
         lowerCamelCase__					:   List[str]      				=	node.next_node
 def __len__(   self						:   List[str]			)    ->			int:
     return sum(1 for _ in self			)







 def __str__(   self						:   Any			)    ->			str:
     return " -> ".join([str(UpperCAmelCase			) for node in self]			)


def  SCREAMING_SNAKE_CASE   ( _UpperCAmelCase		,			_UpperCAmelCase				)    ->  SortedLinkedList:
    return SortedLinkedList(list(_UpperCAmelCase				) + list(_UpperCAmelCase				)				)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    _UpperCAmelCase       : Optional[Any]			     =       SortedLinkedList
    print(merge_lists(SSL(test_data_odd), SSL(test_data_even)))





