print("Hello World!")

def two_sum(nums, target):
  left, right = 0, len(nums) - 1
  while left < right:
    current = nums[left] + nums[right]
    if current == target:
      return [left, right]

def is_palindrome(s):
  left, right = 0, len(s) - 1
  while left < right:
    if s[left] != s[right]:
      return False
    left += 1
    right -= 1
  return True

class TrieNode:
  def __init__(self):
    self.children = {}
    self.is_end = False

def binary_search(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
      return mid

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

def dfs(graph, node, visited):
  if node not in visited:
    print(node)
    visited.add(node)
    for neighbor in graph[node]:
      dfs(graph, neighbor, visited)

def reverse_list(head):
  prev = None
  current = head
  while current:
    next_node = current.next
    current.next = prev
    prev = current
    current = next_node
  return prev

class HashMap:
  def __init__(self, size):
    self.size = size
    self.map = [None] * size
  def _hash(self, key):
    return hash(key) % self.size

def bubble_sort(arr):
  n = len(arr)
  for i in range(n):
    for j in range(0, n-i-1):
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]

def kadane(arr):
  max_sum = arr[0]
  current_sum = arr[0]
  for num in arr[1:]:
    current_sum = max(num, current_sum + num)
    max_sum = max(max_sum, current_sum)
  return max_sum

def fibonacci(n):
  if n <= 1:
    return n
  return fibonacci(n-1) + fibonacci(n-2)

def max_sliding_window(nums, k):
  result = []
  window = []
  for i, num in enumerate(nums):
    while window and nums[window[-1]] < num:
      window.pop()

def coin_change(coins, amount):
  dp = [float('inf')] * (amount + 1)
  dp[0] = 0
  for coin in coins:
    for x in range(coin, amount + 1):
      dp[x] = min(dp[x], dp[x - coin] + 1)

class TreeNode:
  def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None

class Stack:
  def __init__(self):
    self.items = []
  def push(self, item):
    self.items.append(item)
  def pop(self):
    return self.items.pop()

def merge_sort(arr):
  if len(arr) <= 1:
    return arr
  mid = len(arr) // 2
  left = merge_sort(arr[:mid])
  right = merge_sort(arr[mid:])

def longest_substring(s):
  char_set = set()
  left = 0
  max_len = 0
  for right in range(len(s)):
    while s[right] in char_set:
      char_set.remove(s[left])
      left += 1

def bfs(graph, start):
  visited = set()
  queue = [start]
  while queue:
    node = queue.pop(0)
    if node not in visited:
      print(node)

def inorder(root):
  if root:
    inorder(root.left)
    print(root.val)
    inorder(root.right)

def partition(arr, low, high):
  pivot = arr[high]
  i = low - 1
  for j in range(low, high):
    if arr[j] < pivot:
      i += 1
      arr[i], arr[j] = arr[j], arr[i]

import heapq
def kth_largest(nums, k):
  heap = nums[:k]
  heapq.heapify(heap)
  for num in nums[k:]:
    if num > heap[0]:
      heapq.heapreplace(heap, num)

def has_cycle(head):
  slow = fast = head
  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
      return True
  return False

def dijkstra(graph, start):
  distances = {node: float('inf') for node in graph}
  distances[start] = 0
  pq = [(0, start)]
  while pq:
    curr_dist, curr_node = heapq.heappop(pq)

class UnionFind:
  def __init__(self, n):
    self.parent = list(range(n))
  def find(self, x):
    if self.parent[x] != x:
      self.parent[x] = self.find(self.parent[x])