






from __future__ import annotations

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

A__     :      Union[str, Any]             =      TypeVar('T')
A__     :      List[str]             =      TypeVar('U')
class 				_UpperCAmelCase (	Generic[T, U]     ):

				"""simple docstring"""




				def __init__(					self						:   Optional[int],  lowerCamelCase						:   T | None,  lowerCamelCase						:   U | None  ):

								'''simple docstring'''
								lowercase__       			=      key
								lowercase__       			=      val
								lowercase__       			=      0
								lowercase__       			=      None
								lowercase__       			=      None




				def __repr__(					self						:   List[Any]  ):

								'''simple docstring'''
								return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
								    self.key,  self.val,  self.freq,  self.next is not None,  self.prev is not None  )



class 				_UpperCAmelCase (	Generic[T, U]     ):

				"""simple docstring"""




				def __init__(					self						:   Tuple  ):

								'''simple docstring'''
								lowercase__       			=      DoubleLinkedListNode(lowerCamelCase,  lowerCamelCase  )
								lowercase__       			=      DoubleLinkedListNode(lowerCamelCase,  lowerCamelCase  )
								lowercase__			,						lowercase__       			=      self.rear, self.head




				def __repr__(					self						:   Optional[int]  ):

								'''simple docstring'''
								lowercase__       			=      ['''DoubleLinkedList''']
								lowercase__       			=      self.head
								while node.next is not None:
												rep.append(str(lowerCamelCase  )  )
												lowercase__       			=      node.next
								rep.append(str(self.rear  )  )
								return ",\n    ".join(lowerCamelCase  )




				def     lowercase__       (					self						:   str,  lowerCamelCase						:   DoubleLinkedListNode[T, U]  ):

								'''simple docstring'''
								lowercase__       			=      self.rear.prev

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

								lowercase__       			=      node
								lowercase__       			=      previous
								lowercase__       			=      node
								lowercase__       			=      self.rear
								node.freq += 1
								self._position_node(lowerCamelCase  )




				def     lowercase__       (					self						:   Optional[Any],  lowerCamelCase						:   DoubleLinkedListNode[T, U]  ):

								'''simple docstring'''

								while node.prev is not None and node.prev.freq > node.freq:
												# swap node with previous node
												lowercase__       			=      node.prev

												lowercase__       			=      previous_node.prev
												lowercase__       			=      node.prev
												lowercase__       			=      previous_node
												lowercase__       			=      node




				def     lowercase__       (					self						:   Union[str, Any],  lowerCamelCase						:   DoubleLinkedListNode[T, U]  ):

								'''simple docstring'''

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

								lowercase__       			=      node.next
								lowercase__       			=      node.prev
								lowercase__       			=      None
								lowercase__       			=      None
								return node



class 				_UpperCAmelCase (	Generic[T, U]     ):

				"""simple docstring"""




				lowercase__    							=	{}




				def __init__(					self						:   Optional[Any],  lowerCamelCase						:   int  ):

								'''simple docstring'''
								lowercase__       			=      DoubleLinkedList()
								lowercase__       			=      capacity
								lowercase__       			=      0
								lowercase__       			=      0
								lowercase__       			=      0
								lowercase__       			=      {}




				def __repr__(					self						:   str  ):

								'''simple docstring'''
								return (
								    F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
								    F"""capacity={self.capacity}, current_size={self.num_keys})"""
								)




				def __contains__(					self						:   str,  lowerCamelCase						:   T  ):

								'''simple docstring'''
								return key in self.cache




				def     lowercase__       (					self						:   Dict,  lowerCamelCase						:   T  ):

								'''simple docstring'''

								if key in self.cache:
												self.hits += 1
												lowercase__       			=      self.cache[key]
												lowercase__       			=      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(lowerCamelCase  )
												return node.val
								self.miss += 1
								return None




				def     lowercase__       (					self						:   Tuple,  lowerCamelCase						:   T,  lowerCamelCase						:   U  ):

								'''simple docstring'''

								if key not in self.cache:
												if self.num_keys >= self.capacity:
																# delete first node when over capacity
																lowercase__       			=      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(lowerCamelCase  ) is not None
																# first_node guaranteed to be in list

																del self.cache[first_node.key]
																self.num_keys -= 1
												lowercase__       			=      DoubleLinkedListNode(lowerCamelCase,  lowerCamelCase  )
												self.list.add(self.cache[key]  )
												self.num_keys += 1

								else:
												lowercase__       			=      self.list.remove(self.cache[key]  )
												assert node is not None  # node guaranteed to be in list
												lowercase__       			=      value
												self.list.add(lowerCamelCase  )




				@classmethod
				def     lowercase__       (					cls						:   type[LFUCache[T, U]],  lowerCamelCase						:   int = 128  ):

								'''simple docstring'''

								def cache_decorator_inner(lowerCamelCase						:   Callable[[T], U]  ) -> Callable[..., U]:
												def cache_decorator_wrapper(*lowerCamelCase						:   T  ) -> U:
																if func not in cls.decorator_function_to_instance_map:
																				lowercase__       			=      LFUCache(lowerCamelCase  )

																lowercase__       			=      cls.decorator_function_to_instance_map[func].get(args[0]  )
																if result is None:
																				lowercase__       			=      func(*lowerCamelCase  )
																				cls.decorator_function_to_instance_map[func].put(args[0],  lowerCamelCase  )
																return result

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

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

												return cache_decorator_wrapper

								return cache_decorator_inner


if __name__ == "__main__":
							import doctest

							doctest.testmod()












import dataclasses
import enum
import functools
import math
import re

# The following script is adapted from the script of TaPas.
# Original: https://github.com/google-research/tapas/master/wikisql_utils.py
from typing import Any, List, Text


A__     :      Dict             =			'none'
A__     :      Optional[Any]             =			'none'






def   a      (						lowerCamelCase_		,       lowerCamelCase_    ):






				'''simple docstring'''
				lowercase__       			=      value.split(lowerCamelCase_    )
				return len(lowerCamelCase_    ) > 1 and any((len(lowerCamelCase_    ) == 3 for x in split)    )






def   a      (						lowerCamelCase_    ):






				'''simple docstring'''
				if isinstance(lowerCamelCase_		,       lowerCamelCase_    ):
								return value
				if isinstance(lowerCamelCase_		,       lowerCamelCase_    ):
								return float(lowerCamelCase_    )
				if not isinstance(lowerCamelCase_		,       lowerCamelCase_    ):
								raise ValueError('''Argument value is not a string. Can\'t parse it as float'''    )
				lowercase__       			=      value

				try:
								# Example: 1,000.7
								if "." in sanitized and "," in sanitized:
												return float(sanitized.replace(''','''		,       ''''''    )    )
								# 1,000
								if "," in sanitized and _split_thousands(''','''		,       lowerCamelCase_    ):
												return float(sanitized.replace(''','''		,       ''''''    )    )
								# 5,5556
								if "," in sanitized and sanitized.count(''','''    ) == 1 and not _split_thousands(''','''		,       lowerCamelCase_    ):
												return float(sanitized.replace(''','''		,       '''.'''    )    )
								# 0.0.0.1
								if sanitized.count('''.'''    ) > 1:
												return float(sanitized.replace('''.'''		,       ''''''    )    )
								# 0,0,0,1
								if sanitized.count(''','''    ) > 1:
												return float(sanitized.replace(''','''		,       ''''''    )    )
								return float(lowerCamelCase_    )
				except ValueError:
								# Avoid adding the sanitized value in the error message.
								raise ValueError('''Unable to convert value to float'''    )






def   a      (						lowerCamelCase_    ):






				'''simple docstring'''
				if answer is None:
								return None
				try:
								lowercase__       			=      convert_to_float(lowerCamelCase_    )
								if isinstance(lowerCamelCase_		,       lowerCamelCase_    ) and math.isnan(lowerCamelCase_    ):
												return None
								return value
				except ValueError:
								return answer.lower()


A__     :      Tuple             =			{
    'text': lambda x: x,
    'real': convert_to_float,
}
class 				_UpperCAmelCase (	enum.Enum     ):

				"""simple docstring"""




				lowercase__    							=	0
				lowercase__    							=	1
				lowercase__    							=	2
				lowercase__    							=	3
				lowercase__    							=	4
				lowercase__    							=	5



class 				_UpperCAmelCase (	enum.Enum     ):

				"""simple docstring"""




				lowercase__    							=	0
				lowercase__    							=	1
				lowercase__    							=	2



@dataclasses.dataclass
class 				_UpperCAmelCase :

				"""simple docstring"""




				lowercase__    							=	42
				lowercase__    							=	42
				lowercase__    							=	42



A__     :      str             =			re.compile(r'\w+|[^\w\s]+', re.UNICODE | re.MULTILINE | re.DOTALL)






def   a      (						lowerCamelCase_    ):






				'''simple docstring'''
				return list(_TOKENIZER.findall(x.lower()    )    )






def   a      (						lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_    ):






				'''simple docstring'''
				if operator == _Operator.EQUALS:
								return src == tgt
				elif operator == _Operator.GREATER:
								return src > tgt
				elif operator == _Operator.LESSER:
								return src < tgt
				raise ValueError(F"""Unknown operator: {operator}"""    )






def   a      (						lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_    ):






				'''simple docstring'''
				lowercase__       			=      table['''types''']
				return _TYPE_CONVERTER[types[column]](lowerCamelCase_    )






def   a      (						lowerCamelCase_    ):






				'''simple docstring'''
				return isinstance(lowerCamelCase_		,       lowerCamelCase_    )






def   a      (						lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_    ):






				'''simple docstring'''
				for cond in conditions:
								lowercase__       			=      row[cond.column]

								lowercase__       			=      _parse_value(lowerCamelCase_		,       cond.column		,       cond.cmp_value    )

								if _is_string(lowerCamelCase_    ) and _is_string(lowerCamelCase_    ):
												lowercase__       			=      _normalize_for_match(lowerCamelCase_    )
												lowercase__       			=      _normalize_for_match(lowerCamelCase_    )

								if not isinstance(lowerCamelCase_		,       type(lowerCamelCase_    )    ):
												raise ValueError('''Type difference {} != {}'''.format(type(lowerCamelCase_    )		,       type(lowerCamelCase_    )    )    )

								if not _compare(cond.operator		,       lowerCamelCase_		,       lowerCamelCase_    ):
												return False
				return True






def   a      (						lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_    ):






				'''simple docstring'''
				if not answer_coordinates:
								if aggregation_op == _Aggregation.COUNT:
												return 0.0
								else:
												return EMPTY_ANSWER_AGG

    # Count can support non numeric answers.
				if aggregation_op == _Aggregation.COUNT:
								return float(len(lowerCamelCase_    )    )

				# If we have just one answer, if float returns it or try a conversion.
				lowercase__       			=      [table['''rows'''][i][j] for (i, j) in answer_coordinates]
				if len(lowerCamelCase_    ) == 1:
								try:
												return convert_to_float(values[0]    )
								except ValueError as e:
												if aggregation_op != _Aggregation.NONE:
																raise e

				if aggregation_op == _Aggregation.NONE:
								return None

				# Other aggregation only support numeric values. Bail out if we have strings.
				if not all((isinstance(lowerCamelCase_		,       (int, float)    ) for v in values)    ):
								return None

				if aggregation_op == _Aggregation.SUM:
								return float(sum(lowerCamelCase_    )    )
				elif aggregation_op == _Aggregation.AVERAGE:
								return sum(lowerCamelCase_    ) / len(lowerCamelCase_    )
				else:
								raise ValueError(F"""Unknown aggregation: {aggregation_op}"""    )






def   a      (						lowerCamelCase_		,       lowerCamelCase_    ):






				'''simple docstring'''
				lowercase__       			=      sql_query['''agg''']
				if aggregation_op_index >= 3:
								lowercase__       			=      _Aggregation(lowerCamelCase_    )
				else:
								lowercase__       			=      _Aggregation.NONE

				lowercase__       			=      sql_query['''sel''']
				lowercase__       			=      [
				    _Condition(lowerCamelCase_		,       _Operator(lowerCamelCase_    )		,       lowerCamelCase_    )
				    for column, operator, cmp_value in zip(
				        sql_query['''conds''']['''column_index''']		,       sql_query['''conds''']['''operator_index''']		,       sql_query['''conds''']['''condition''']    )
				]

				lowercase__       			=      []
				for row in range(len(table['''rows''']    )    ):
								if _respect_conditions(lowerCamelCase_		,       table['''rows'''][row]		,       lowerCamelCase_    ):
												indices.append((row, target_column)    )

				if not indices:
								return [], aggregation_op

				if len(lowerCamelCase_    ) == 1:
								return indices, aggregation_op

				# Parsing of MIN/MAX.
				if aggregation_op_index in (1, 2):
								lowercase__       			=      {2: min, 1: max}
								lowercase__       			=      [(table['''rows'''][i][j], index) for index, (i, j) in enumerate(lowerCamelCase_    )]
								lowercase__       			=      functools.reduce(operators[sql_query['''agg''']]		,       lowerCamelCase_    )

								lowercase__       			=      [indices[reduced[1]]]
								return ret, _Aggregation.NONE

				return indices, aggregation_op






def   a      (						lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_    ):






				'''simple docstring'''
				if float_answer is not None:
								return [str(lowerCamelCase_    )]
				return [str(table['''real_rows'''][r][c]    ) for r, c in answer_coordinates]






def   a      (						lowerCamelCase_		,       lowerCamelCase_    ):






				'''simple docstring'''
				lowercase__			,						lowercase__       			=      _get_answer_coordinates(lowerCamelCase_		,       lowerCamelCase_    )
				lowercase__       			=      _get_float_answer(lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_    )
				lowercase__       			=      _get_answer_text(lowerCamelCase_		,       lowerCamelCase_		,       lowerCamelCase_    )
				# keep the original data the same with TaPas
				if len(lowerCamelCase_    ) == 0:
								lowercase__       			=      [EMPTY_ANSWER]
				return answer_text




