





def lowerCAmelCase__(__snake_case							)				->      Tuple:







	'''simple docstring'''







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





def lowerCAmelCase__(__snake_case							)				->      Optional[int]:







	'''simple docstring'''







	if not head or not head.next:
		return True

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

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

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

	return True





def lowerCAmelCase__(__snake_case							)				->      List[Any]:







	'''simple docstring'''







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










_a 						=      65_521





def lowerCAmelCase__(__snake_case							)				->      int:







	'''simple docstring'''







	lowerCamelCase__								=		1
	lowerCamelCase__								=		0
	for plain_chr in plain_text:
		lowerCamelCase__								=		(a + ord(__snake_case							)) % MOD_ADLER
		lowerCamelCase__								=		(b + a) % MOD_ADLER
	return (b << 16) | a



