Little Petya loves playing with rectangles. Mom bought Petya a rectangle divided into cells *n* × *m* in size (containing *n* rows, *m* columns). Petya marked two different cells of the rectangle and now he is solving the following task:

Let's define a simple path between those two cells as a sequence of distinct cells *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*k*</sub>, where *a*<sub class="lower-index">1</sub> and *a*<sub class="lower-index">*k*</sub> are the two marked cells. Besides, *a*<sub class="lower-index">*i*</sub> and *a*<sub class="lower-index">*i* + 1</sub> are side-neighboring cells of the path (1 ≤ *i* &lt; *k*). Let's denote the path length as number *k* (the sequence length). 

Petya's task is to find the longest simple path's length and to print the path. Help him.
The first line contains space-separated integers *n* and *m* (4 ≤ *n*, *m* ≤ 1000) — the number of rows and the number of columns in the rectangle, correspondingly. The second line contains space-separated integers *x*<sub class="lower-index">1</sub> and *y*<sub class="lower-index">1</sub> — the coordinates of the first marked cell. The third line contains space-separated integers *x*<sub class="lower-index">2</sub> *y*<sub class="lower-index">2</sub> — the coordinates of the second marked cell (1 &lt; *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub> &lt; *n*, 1 &lt; *y*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">2</sub> &lt; *m*, *x*<sub class="lower-index">1</sub> ≠ *x*<sub class="lower-index">2</sub>, *y*<sub class="lower-index">1</sub> ≠ *y*<sub class="lower-index">2</sub>).

The coordinates of a marked cell are a pair of integers *x* *y*, where *x* represents the row's number and *y* represents the column's number. The rows are numbered from top to bottom with consecutive integers from 1 to *n*. The columns are numbered from the left to the right by consecutive integers from 1 to *m*.

It is guaranteed that the marked cells are not positioned in one row or column.
#!/usr/bin/env python3

import itertools

class Position:
  def __init__(self,x,y):
    self.x = x
    self.y = y
  
  def __add__(self, other):
    if isinstance(other, Position):
      return Position(self.x + other.x, self.y + other.y)
    else:
      (dx,dy) = other
      return Position(self.x + dx, self.y + dy)
  def __eq__(self, other):
    return (self.x == other.x) and (self.y == other.y)
  def __sub__(self, other):
    return Position(self.x - other.x, self.y - other.y)
  def __str__(self):
    return "(%d,%d)" % (self.x, self.y)

  def left(self):
    return Position(self.x-1, self.y)
  def right(self):
    return Position(self.x+1, self.y)
  def up(self):
    return Position(self.x, self.y-1)
  def down(self):
    return Position(self.x, self.y+1)
  def adjacent(self):
    return [self.up(), self.right(), self.down(), self.left()]


class Cell:
  def __init__(self, pos):
    self.pos = pos
    self.next = None
    self.group = None
    self.is_finish = False

  def __str__(self):
    if (self.is_finish):
      return "*"
    elif (self.next == None):
      return "."
    else:
      distance = self.next.pos - self.pos
      if (distance.x == 1):
        return ">"
      elif (distance.x == -1):
        return "<"
      elif (distance.y == 1):
        return "v"
      elif (distance.y == -1):
        return "^"
      else:
        raise("Wrong direction %s" % distance)

  def move_left(self):
    self.next = self.group.grid.cell(self.pos.left())
  def move_right(self):
    self.next = self.group.grid.cell(self.pos.right())
  def move_up(self):
    self.next = self.group.grid.cell(self.pos.up())
  def move_down(self):
    self.next = self.group.grid.cell(self.pos.down())

  def is_empty(self):
    # Returns whether the cell is already filled
    return (not self.is_finish) and (self.next == None)

  def adjacent(self):
    # Return cells adjacent to this cell
    neighbors = [self.group.grid.cell(pos) for pos in self.pos.adjacent()]
    neighbors = [cell for cell in neighbors if cell != None]
    return neighbors

  def prev(self):
    # Returns the previous cell on the route,
    # or None if there is none
    prev = [cell for cell in self.adjacent() if cell.next == self]
    return None if len(prev) == 0 else prev[0]

class Group:
  def __init__(self, grid, pos):
    self.grid = grid
    self.pos = pos
    self.cellsx = 2 if ((2*pos.x+3) != self.grid.m) else 3
    self.cellsy = 2 if ((2*pos.y+3) != self.grid.n) else 3
    self.cells = [[self.grid.cells[y][x] for x in range(pos.x*2, pos.x*2 + self.cellsx)] for y in range(pos.y*2, pos.y*2 + self.cellsy)]
    for row in self.cells:
      for cell in row:
        cell.group = self

  def __str__(self):
    result = []
    for row in self.cells:
      line = []
      for cell in row:
        line.append("%s" % cell)
      result.append("".join(line))
    return "\n".join(result)
  
  def fill_clock_wise(self):
    # Fill the group with a clock-wise ring
    for x in range(self.cellsx-1):
      self.cells[0][x].move_right()
    for y in range(self.cellsy-1):
      self.cells[y][-1].move_down()
    for x in range(self.cellsx-1, 0, -1):
      self.cells[-1][x].move_left()
    for y in range(self.cellsy-1, 0, -1):
      self.cells[y][0].move_up()

  def fill_counter_clock_wise(self):
    # Fill the group with a counter clock-wise ring
    for x in range(self.cellsx-1, 0, -1):
      self.cells[0][x].move_left()
    for y in range(self.cellsy-1):
      self.cells[y][0].move_down()
    for x in range(self.cellsx-1):
      self.cells[-1][x].move_right()
    for y in range(self.cellsy-1, 0, -1):
      self.cells[y][-1].move_up()

  def is_cell_adjacent(self, cell):
    # Checks if a certain cell is adjacent to this group
    neighbors = cell.adjacent()
    return any(c in neighbors for c in itertools.chain.from_iterable(self.cells))

  def solve_path(self, entry_cell, next_group):
    # Solve the current group; make a path from the entry_cell to one of the cells in the next group,
    # and use all cells in the group
    direction = next_group.pos-self.pos

    self.fill_clock_wise()
    exit_candidate = entry_cell.next
    if next_group.is_cell_adjacent(exit_candidate):
      self.fill_counter_clock_wise()
      exit_candidate.next = self.grid.cell(exit_candidate.pos+direction)
      return exit_candidate.next
    
    self.fill_counter_clock_wise()
    exit_candidate = entry_cell.next
    if next_group.is_cell_adjacent(exit_candidate):
      self.fill_clock_wise()
      exit_candidate.next = self.grid.cell(exit_candidate.pos+direction)
      return exit_candidate.next

    # FIXME: We can only get here for some of the 3x2/2x3/3x3 cases
    raise("Unhandled case")

  def nr_filled(self):
    return sum(1 for c in itertools.chain.from_iterable(self.cells) if (c.next != None) or (c.is_finish))

  def nr_unfilled(self):
    return (self.cellsx * self.cellsy) - self.nr_filled()

  def solve_end(self, entry_cell, destination_cell):
    # Solve the current group; make a path from the entry_cell to the destination cell.
    # This fuction will return the number of cells in the group that have not been used (ideally 0)
    if (entry_cell != destination_cell):
      self.fill_clock_wise()
      if (entry_cell.next == destination_cell):
        self.fill_counter_clock_wise()
        destination_cell.next = None
        return self.nr_unfilled()
      self.fill_counter_clock_wise()
      if (entry_cell.next == destination_cell):
        self.fill_clock_wise()
        destination_cell.next = None
        return self.nr_unfilled()
      if (self.cellsx == 2) and (self.cellsy == 2):
        # The destination cell is in the opposite corner of the entry cell
        self.fill_clock_wise() # TODO: Does it matter whether we go clock-wise or counter clock-wise? I don't think so... 
        assert(entry_cell.next.next == destination_cell)
        entry_cell.next.next.next.next = None # Clear the unused cell
        entry_cell.next.next.next = None # Clear the destination cell
        return self.nr_unfilled()
      # FIXME: We can only get here for some of the 3x2/2x3/3x3 cases
      raise("Unhandled case")
    else:
      # We enter at the location where we need to finish
      if (self.cellsx == 3) and (self.cellsy == 3) and (entry_cell == self.cells[0][0]):
        # We enter and at the top left corner of the 3x3 cell, leaving a nice L shape with an even number of empty cells
        # that will be filled automatically by the extend part of the algorithm
        # TODO: Is this true? We have a probelm if it possible that none of the adjoining 3x2/2x3 cells have an extension option 
        return 0
      # There might be a solution by slightly altering the previous group to exit that group a bit earlier:
      if (self.is_cell_adjacent(entry_cell.prev().prev())):
        redirect = entry_cell.prev().prev()
        direction = self.pos-redirect.group.pos
        entry_cell.prev().next = None
        redirect.next = self.grid.cell(redirect.pos+direction)
        # Now solve for the new problem
        return self.solve_end(redirect.next, destination_cell)+1
      else:
        # No local solution, perhaps a different route will help?
        return self.nr_unfilled()

class Grid:
  def __init__(self, n, m, x1, y1, x2, y2):
    self.n = n
    self.m = m
    self.cells = [[Cell(Position(x,y)) for x in range(m)] for y in range(n)]
    self.groups = [[Group(self, Position(x, y)) for x in range(m//2)] for y in range(n//2)]
    self.c1 = self.cell(Position(x1-1,y1-1))
    self.c2 = self.cell(Position(x2-1,y2-1))
    self.c2.is_finish = True
    self.g1 = self.group(Position((x1-1)//2,(y1-1)//2))
    self.g2 = self.group(Position((x2-1)//2,(y2-1)//2))

  def __str__(self):
    result = []
    for row in self.groups:
      divider = []
      lines = [[],[],[]]
      for group in row:
        group_lines = group.__str__().split("\n")
        divider.append("-" * group.cellsx)
        for (index, line) in enumerate(group_lines):
          lines[index].append(line)
      for line in lines:
        if len(line) > 0:
          result.append("|%s|" % ("|".join(line)))
      divider = "+%s+" % "+".join(divider)
      result.append(divider)
    result.insert(0, divider)
    return "\n".join(result)

  def cell(self, pos):
    if (0 <= pos.x) and (pos.x < self.m) and (0 <= pos.y) and (pos.y < self.n):
      return self.cells[pos.y][pos.x]
    else:
      return None

  def group(self, pos):
    return self.groups[pos.y][pos.x]

  def extend(self):
    # Given an available route from start to finish, fill in the rest of the groups
    cell = self.c1
    while (cell != self.c2):
      # Find any pair of empty adjacent cells that are also adjacent to the path
      adjacent_to_cell = [c for c in cell.adjacent() if (c != cell.next) and (c.is_empty())]
      adjacent_to_next = [c for c in cell.next.adjacent() if (c != cell) and (c.is_empty())]
      candidates = [(c1, c2) for (c1,c2) in itertools.product(adjacent_to_cell, adjacent_to_next) if (c1 in c2.adjacent())]
      if len(candidates) > 0:
        temp = cell.next
        (a1, a2) = candidates[0]
        cell.next = a1
        a1.next = a2
        a2.next = temp
      else:
        cell = cell.next

  def solve(self):
    # Find route from starting group to ending group
    current_group = self.g1
    route = []
    while (current_group != self.g2):
      distance = self.g2.pos - current_group.pos
      if (distance.x > 0):
        current_group = self.group(current_group.pos.right())
      elif (distance.x < 0):
        current_group = self.group(current_group.pos.left())
      elif (distance.y > 0):
        current_group = self.group(current_group.pos.down())
      else: #(distance.y < 0)
        current_group = self.group(current_group.pos.up())
      route.append(current_group)

    #print(",".join([group.pos.__str__() for group in route]))

    current_cell = self.c1
    for next_group in route:
      current_cell = current_cell.group.solve_path(current_cell, next_group)

    missed = current_cell.group.solve_end(current_cell, self.c2)
    #print(missed)
    # FIXME: Adjust route if missed > 1

    self.extend()

  def print_answer(self):
    cell = self.c1
    route = [cell]
    while (cell != self.c2):
      cell = cell.next
      route.append(cell)
    print(len(route))
    print("\n".join([cell.pos.__str__() for cell in route]))


(n,m) = map(int, input().split())
(x1,y1) = map(int, input().split())
(x2,y2) = map(int, input().split())

g = Grid(n,m,x1,y1,x2,y2)
g.solve()
g.print_answer()
#print(g)
