



def 							A			(  _UpperCAmelCase       :     Optional[int]					)       ->				Union[str, Any]:







			'''simple docstring'''
			if not head:
						return True
			# split the list to two parts
			_UpperCAmelCase ,  _UpperCAmelCase	 =     head.next, head
			while fast and fast.next:
						_UpperCAmelCase	 =     fast.next.next
						_UpperCAmelCase	 =     slow.next
			_UpperCAmelCase	 =     slow.next
			_UpperCAmelCase	 =     None  # Don't forget here! But forget still works!
			# reverse the second part
			_UpperCAmelCase	 =     None
			while second:
						_UpperCAmelCase	 =     second.next
						_UpperCAmelCase	 =     node
						_UpperCAmelCase	 =     second
						_UpperCAmelCase	 =     nxt
			# compare two parts
			# second part has the same or one less node
			while node:
						if node.val != head.val:
									return False
						_UpperCAmelCase	 =     node.next
						_UpperCAmelCase	 =     head.next
			return True





def 							A			(  _UpperCAmelCase       :     int					)       ->				Optional[int]:







			'''simple docstring'''
			if not head or not head.next:
						return True

			# 1. Get the midpoint (slow)
			_UpperCAmelCase	 =     _UpperCAmelCase	 =     _UpperCAmelCase	 =     head
			while fast and fast.next:
						_UpperCAmelCase ,  _UpperCAmelCase	 =     fast.next.next, slow.next

			# 2. Push the second half into the stack
			_UpperCAmelCase	 =     [slow.val]
			while slow.next:
						_UpperCAmelCase	 =     slow.next
						stack.append(slow.val					)

			# 3. Comparison
			while stack:
						if stack.pop() != cur.val:
									return False
						_UpperCAmelCase	 =     cur.next

			return True





def 							A			(  _UpperCAmelCase       :     Any					)       ->				Any:







			'''simple docstring'''
			if not head or not head.next:
						return True
			_UpperCAmelCase	 =     {}
			_UpperCAmelCase	 =     0
			while head:
						if head.val in d:
									d[head.val].append(_UpperCAmelCase					)
						else:
									_UpperCAmelCase	 =     [pos]
						_UpperCAmelCase	 =     head.next
						pos += 1
			_UpperCAmelCase	 =     pos - 1
			_UpperCAmelCase	 =     0
			for v in d.values():
						if len(_UpperCAmelCase					) % 2 != 0:
									middle += 1
						else:
									_UpperCAmelCase	 =     0
									for i in range(0							,     len(_UpperCAmelCase					)					):
												if v[i] + v[len(_UpperCAmelCase					) - 1 - step] != checksum:
															return False
												step += 1
						if middle > 1:
									return False
			return True





import unittest

from knapsack import knapsack as k







class     __lowerCAmelCase					(    unittest.TestCase		):



			def 					_lowerCamelCase (		self     :						Optional[Any])     ->					Any:



						"""simple docstring"""






						_UpperCAmelCase	 =     0
						_UpperCAmelCase	 =     [0]
						_UpperCAmelCase	 =     [0]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	0)

						_UpperCAmelCase	 =     [60]
						_UpperCAmelCase	 =     [10]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	0)



			def 					_lowerCamelCase (		self     :						str)     ->					List[str]:



						"""simple docstring"""






						_UpperCAmelCase	 =     3
						_UpperCAmelCase	 =     [1, 2, 3]
						_UpperCAmelCase	 =     [3, 2, 1]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	5)



			def 					_lowerCamelCase (		self     :						Tuple)     ->					Tuple:



						"""simple docstring"""






						_UpperCAmelCase	 =     50
						_UpperCAmelCase	 =     [60, 1_00, 1_20]
						_UpperCAmelCase	 =     [10, 20, 30]
						_UpperCAmelCase	 =     len(A)
						self.assertEqual(k.knapsack(A				,	A				,	A				,	A)				,	2_20)


if __name__ == "__main__":
							unittest.main()
