summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-15 01:07:34 -0700
committerJack Sangdahl <[email protected]>2024-12-15 01:07:34 -0700
commit0ca91e0da2793b481c55bb2367e1549ec37f693d (patch)
tree613c7e7b1e379076e3310dd7cc6d6b0b4dacb5fa
parent37fded32814b534200f6c6c8c984ad0bed7253a2 (diff)
downloadaoc-0ca91e0da2793b481c55bb2367e1549ec37f693d.tar.gz
aoc-0ca91e0da2793b481c55bb2367e1549ec37f693d.zip
Day 15 2024
-rw-r--r--15_2024.py92
-rw-r--r--data/15_2024.txt72
2 files changed, 164 insertions, 0 deletions
diff --git a/15_2024.py b/15_2024.py
new file mode 100644
index 0000000..9952a8d
--- /dev/null
+++ b/15_2024.py
@@ -0,0 +1,92 @@
+from collections import deque
+
+input = "data/15_2024.txt"
+data = open(input).read().strip()
+lines, instrs = data.split("\n\n")
+lines = lines.split("\n")
+
+
+def solve(lines, part2):
+ rows = len(lines)
+ cols = len(lines[0])
+ lines = [[lines[r][c] for c in range(cols)] for r in range(rows)]
+ if part2:
+ big = []
+ for r in range(rows):
+ row = []
+ for c in range(cols):
+ if lines[r][c] == "#":
+ row.append("#")
+ row.append("#")
+ if lines[r][c] == "O":
+ row.append("[")
+ row.append("]")
+ if lines[r][c] == ".":
+ row.append(".")
+ row.append(".")
+ if lines[r][c] == "@":
+ row.append("@")
+ row.append(".")
+ big.append(row)
+ lines = big
+ cols *= 2
+ for r in range(rows):
+ for c in range(cols):
+ if lines[r][c] == "@":
+ sr, sc = r, c
+ lines[r][c] = "."
+ r, c = sr, sc
+ for inst in instrs:
+ if inst == "\n":
+ continue
+ dr, dc = {"^": (-1, 0), ">": (0, 1), "v": (1, 0), "<": (0, -1)}[inst]
+ rr, cc = r + dr, c + dc
+ if lines[rr][cc] == "#":
+ continue
+ elif lines[rr][cc] == ".":
+ r, c = rr, cc
+ elif lines[rr][cc] in ["[", "]", "O"]:
+ q = deque([(r, c)])
+ vis = set()
+ ok = True
+ while q:
+ rr, cc = q.popleft()
+ if (rr, cc) in vis:
+ continue
+ vis.add((rr, cc))
+ rrr, ccc = rr + dr, cc + dc
+ if lines[rrr][ccc] == "#":
+ ok = False
+ break
+ if lines[rrr][ccc] == "O":
+ q.append((rrr, ccc))
+ if lines[rrr][ccc] == "[":
+ q.append((rrr, ccc))
+ assert lines[rrr][ccc + 1] == "]"
+ q.append((rrr, ccc + 1))
+ if lines[rrr][ccc] == "]":
+ q.append((rrr, ccc))
+ assert lines[rrr][ccc - 1] == "["
+ q.append((rrr, ccc - 1))
+ if not ok:
+ continue
+ while len(vis) > 0:
+ for rr, cc in sorted(vis):
+ rrr, ccc = rr + dr, cc + dc
+ if (rrr, ccc) not in vis:
+ assert lines[rrr][ccc] == "."
+ lines[rrr][ccc] = lines[rr][cc]
+ lines[rr][cc] = "."
+ vis.remove((rr, cc))
+ r = r + dr
+ c = c + dc
+ res = 0
+ for r in range(rows):
+ for c in range(cols):
+ if lines[r][c] in ["[", "O"]:
+ res += 100 * r + c
+ return res
+
+
+print(solve(lines, False))
+print(solve(lines, True))
diff --git a/data/15_2024.txt b/data/15_2024.txt
new file mode 100644
index 0000000..8ec45c3
--- /dev/null
+++ b/data/15_2024.txt
@@ -0,0 +1,72 @@
+##################################################
+#OO..OO..O....O##O....O..#...O..O..............OO#
+#.OO.O.O.......O..O.....#O....#O#.......O.O...O.##
+#OO..O..O..O......OO.....O#..OOO..O.....#....O...#
+#...O......#O.O##.#..O.O#..O.O....O.#.#.OO#O.OO#O#
+#...#...O..OO.....O.........OO.OO.O........O...#.#
+#...#....O...O##O...O.....O....#.....O..O.O.O.OOO#
+#.O...O..#.#OO.O.##...#...##O....O...#...#....O..#
+##.###.O......#..O...O....#....O....#O.....O#..O.#
+#...#O.O...#O..O.O............OO.O..O..#.##..O.OO#
+#...OOO............#OO....O.O.O#.......O......O#.#
+##............#O.....O......O..O.O.#.OO.O.O......#
+#O...O..#...O....O..O...OO#.#OO#.........##.#O..##
+#O...O..O#O..O#.#.O.O...O.O..OOO.O....O....O.O...#
+#....#...#.O.O#O..O..OOO..O....O.....#...O...O.#.#
+#..O...#...OO.O.O.OOO.OO..#..O..OO...O......O#..O#
+#O.....O.O...O.O.#.O....O.....O...O....O...O.....#
+#.O..O..O.#O..O...O.O..O..OO.OO#...O.O....#.#.O..#
+#O..#O...O.O.....O#OO..O.......#.OO.OOOOOOO#..O..#
+#O#O...O..#...O#O.O......O..OO...O.....O...O.....#
+#O......O##....O#....O..#.OOOO.O.O..#OO........O.#
+#O..OO....#.#........O....O..O#.OO.....#.O.OO....#
+#.....O.....OO#OO....O.O...#.....OO.O...O.....O..#
+#.....O.O....#......O..O..O...O.....O....O.....O.#
+#.O.O#.......#O....O..OO@#...O#.O...OO...OO.#.O..#
+#OO...OO..#.#...OO.....#....O.....OO....O#..#....#
+#.O.#.O.......#.....O.O.......O...O....#...O.....#
+#.OOO.O..#...O...O..#O......O..O.O##..#.##.O.....#
+#O.O#..OO......OO..OO..O#..#O.O...#O#........#.OO#
+#..O.O.....#...OOO..OO.#.....OO#.......#OOO..O..O#
+#O.O..OO...O..O.O....OO...O.O...O..O......OO.....#
+##...O....#O..OOO.O.#.OO.#......O#..O.#O...#.....#
+#...O...O....O.#...O...........OO.OOO..O.O..#.#OO#
+#.O.#....#.O#..#O..O....#..OO.O..O..O.#........O.#
+#O#O...O.....O.O......#OOO.O#.......O....#O.#.#O##
+#O.O#..O...OO....O......O.O.....O......O.OOO....O#
+#....#OO...O.......#OO.O.O..#.O......#.....O..O..#
+#....O.....OO....OOO..O.OO..#OO..O.....OOO.#.....#
+##..OOO.#.O.........#..O..O..O..O.O.OOOO..#....O.#
+#...OO....OOO......O.......O.......#........O.O..#
+#O.O...#OOO....O.#...O...OO...O....OO.......#....#
+#.......O.O..#...OOO..#..O..OO..O..O.OOOO.O..OO..#
+#..O..O..O..O.##.OO...#..O#..O.#...OOO..O......O.#
+#.....OO..OO...O.#.O..OOO..OOO....OO.........#.O.#
+#..O.....O.O..O...O..##OO....O...O....#.O.O..#.OO#
+#..OO.......O..O#.OOO.....O....O...#..O.O.....#O##
+#...O..#...O..O........#...OO.O.O...#.O.....O....#
+#O....O.O#...OO......OO.OO..O.......#..#.#..OO...#
+#..#.#.....##.##O....O...O.......O..OO....O...OO.#
+##################################################
+
+^v^<>>vv<<<^v>v>>^<v<>vvv^<<>^><^^vv>^>>>>>>v^<v^>v^>>>^v>vv<^<<vv>^<^>v>v>>>v<^>^^^>^><v^<>v<<^^vv^>><>^v>><<>v<vvv^^^v^<^><<^^v>v^>v^^^^v>^^>^>v>>vv^^>>v^v<<^vvv<v<v<>v>v^^<^v<^v<<v^>>^>v^<v>^vvv><><<vv><<>^<>^v><>^>^^>v<>v^<>v^<^v^v><>>>^>vvv<^>^v<^<>vvvv><v><<^^>^><<>^vv>^>>^<<><v>><>^<^vv^<vvvv>^<<^^v<v<^^^<^>v>^><^>^<><<><vv^^<v^>^^<v<^>>><<^>v^>^v>^^<>v<>>v^<<<^v^<<^v>^<^^v^^^v>>^>^v^^v>>v>>vv<^^^<<^v<^^v<^^>^v<v<>>^^<<^<v<^>>>>^<>><<>^><^<vv>>>vv^>^><>v<^v><>><v>><v^<v^<<^^vv^>>>v^<>v<<^<^<^^<>^^>v^<^v^<>vv^^<>^v>^^<<v^>vv^>^<v<<vv>^<<>>v<<^^><>>>^<>^v><vvvvvv>>^v^^>v^^vvv^^v^<<v^><<^>>^^<vv>v><>>^<>^vv>v^vv<<v>^<^<^<<<<v<>v^>vvv^><v>^<>>v^<>^^<^vv^<>^v<>v^^v<v>^<>v<v>^><><v<>v<v<<v^><^<v>v>^>>^>^^<><<v^^vv<v^<v><>vv^^vv>><v<<^>v>><^v<^v>vv<v>>^vv>>^<^<>^v>v>^>v^<<v>vv<<^^<^<^<>>>>^^><<v>>^>^>v><v^<vvv^<v^v>vv^vv^vvvv<<<^v^vv><^<^>^^<v<<vv>^^vv<>>>^>^><>v>^<^<vv<<>v>vv<>>^vv<v<^<<^<<><v<v<<>>^<^>>>^>>^>v^<^^v<v^><vv><^>^v^>v>vv<^v<<v<<v^^<^vv^<vvv<<><>v>v^v>vv<^v<vv<^^>v^><<v>>
+v<>>^^vv<>^v^<<^>><><>^vvvv^^><<<<^>v<>v>>>^>^>>>v>>>^^<>><<^^^^v<>><>v^>>vv^><<v<^><^^v^<v>v^>>>v><v><v>v<<v<>>v^<^<^vv>^v>vvv<^><><<>^^>v^v>vvv<^>>>>^^^^vv<>^vv>^<v<>^v>v^<>v<v<>>><v><vvvv^vv^^<<v>>>>v^vvvv^^><^^^<v^>><<^>^^><>^<v^<<v^v<^<^<vvv<<>>v>>^v>><^v<v<<^^><>>vv<><^<^^^>^v^^>v<^<^><<^v<v<v>v^>^<<<<>v^^^><>vv>^>v^>^>vvv>>><^>^<<><><>v>^<v>><>^^>v>^><^^vvv^^^>>vv<vv>vv><^<>>vvv^^><<>>vvvv^^><<>><>vv^^>v^^vv<><^>^>^<<><>>v^^<^^>>^<v>>^<^^v>^^^<v^v<<><v<v>><vvv>>v<>v>v^<<^v>>><>v><v<<v^v>^v^<^<>>v^vv>^<v><<<^v^>><^^>^^v><>^>^<>^<<^>v<^<<^v<v<>>v^^>^^>v<v>^v<<>^>v<><^<v>>v><v><^>vv<<v^^^^^<<><>>><v>>v>vvv<>v>^>^vvv><>^^^>v^<<<v>>v>^>>>>v^^v>v>>v^<^v<^v><<^v^>>^>^<<><<<<>^<v>^^>^^v^>><<^<^v>v>v<v>>>>v><>v<<v^^v>^>><^<^^v^>><>v^v^vv^^^><<^<>^vv>v<<>^v^^<>><>^^<v^v>v<v^<^>vvv><^^><^^>v<v^>^<<>^v<<<>>v<^<>^v^<^>vvvv<v>v>>^^vv^<^v><<>^^v>^<<>v^vv^<>><^^v^^^v^^<<<>v>^<>>>>vv^^>^>^v><<^^<>^^<<<<<<^^<^v<>^v><v^^>>vv^^vvv^v^>^v<>v>v^<v^v<^>^^v>^^v^vv<>v^><<v<<^<^^v<>^>^v<^vvvv>><>v<vvv>>><
+>v<^<^<>v><^<<<<v>^^<<v<^>^>v<<^><v>v<<<^^<<v^v<^>^v<><>^^>^^<<v<<vvv^^^>^v<vv><v>>v>v>^<v^<^^><v>^v^<^v<v<v>^>^><><^<<^><v<>>^vv>^<>v><v^v<<^<v><v^<^>v^><<<><<<<>v^>>^>>>^<vvvv>v<>^v^<>>vv<^^v^v^^^>v>^>><<^>v^<^v^^v<<<<>v>v<>v>^vv><^^v>^^v^^<^v^<<^<><<vv>v<>>v^<<><>v<v>v<<><<^<<<<vvv><>vv^>^^v^^^>>vv>^v<<v^>^vv<^v<><v<vv<>v^^v<^^v>vv<>>^^>^><v<vvvv><^<<>vvvv<<>^vv<vv<>^^<^><>v^<><v>v<^>v^v<<^vv^>v^^<v^^<v<v^v<<^vv^vv^^v<vv>^<><<^>v^>><<<><^<><><^>>>><v><<><<vv>v^>v<<^vv^><v^^<v>v<>v<v>v^vv><v^><v>>^><<<<v>^<<vv^<>v><v<^>^^^><^^<><v^<^>^^<v><<^<^>v>v>^^^^^^v^^^vv>^>^><><<<vv<vvvv^><v>v^<>^^>^<^v^>vv^<<<^v<>^>v<^vv<vv<<>v>^^vv^v^^^vv><<<>>><^v^<<^<>v^v<^<^<^^>v<<>>^<v^^>><v<v^v^^>^><v<<><>vvv<<^^^>>>v<<<>^<^<v>v>><v<<<v<><v>>>>v<^v>><^<^^<>>vv><^^v>><>^<v^><v^^vv^>^^^<>v<^>^<<<^>v^<^^>^v>^<^v^vv^><^>vvv>><<<v>><^>^^<^^<v<><>v^vvv><^<<v^<>v^<v^v^>v^vv<^vv>>^v<^^^>v>vv>vvvvvvv<^<<vvv<vv<>^<v^>vv<vv^^^^^<>>^^<vvv^^^>vvv<v>^<v>^<^>v<>^v>^<<<^>v>^<<>vvvvv><<^v>>>^v>^^<>><>>v^<>^^^><<vv<v<<^^
+v>v>v<<^>v^^>>>v><v><v>vv<^^<^>vv>v>><v^<<<v<<vv<>vv^<>v^v^v<vv^><>v>>^^v><<^^<^^><^v^vv><<^v><<<<<<^><^^^<^>><^v>><<<>^vv<^^v>^v>^v<v<<^<^<v^^><v<vv>>^>^>vv>>^>^<^vv^vv><<<^>^<>^><<v>^<vv^<>^<^<<>^^><<>>>v><v<<<v^<<><^^><<v<>^^^^>v>>^>>^v>vvvvv^v^vv<v>^^^<v^><v^>^<v>><^><^vv^v><^^<<v^<v>^>>>><v<>v<>v^^^v><^^v^^^><<^^>^>>^^v<^>^<v^v>>>>vv^^v>v^^><>v^^^>^^^>>>^>^<^vv>v><v>^^>>>^<^>vv<<vvv^v>v><>^<>^<vv^><vv>v^^^^vv<^><^<<<<>v<^>vvv<v^^v<vv^<v<>>^<<>v<v>>>v<<v^<vv<^>>^v^>vv<><>vv>v^^v>>v>^<>^<v>>^<>><v>>^<<><^>^>><^^^v><v^<>^^^<^v<><^^>^<v^<^v>^vv<^^v^^<><^<^vv^vv<^^vv<v^<v^>v<>vv^>^>vv><vv<<><<<>><v>><^<<<<v<>v<v^vv^<>v<^^<<^>>vv>v><>vv^<^<v^>>^v>>vv>^^><<>^>vvv<^>^>^<v><^^>^>^<><v>^<<>>v>v>vvv>^^^>>>^><^<>>>>><vv<^<>v>v><vvv<vv>^><<v><^^<vv^<v^>vvv<<><>v<>><v^><v<<vv<>^^v<v<v^><^<vvv>vv^><>vv>>>>v<><<v>>v^^<<>>>>v^><<v>><^v^<v^v<v>^v^<^^>v><<<vv^<^^v<<vv<v<^>v^<>v^<v>v<<vv^>><>^^>^vv^><v^^<vvv^vv>><^^v<><>^<>>><^<>v<>>^^<^<v<<<><>v^^vv>>>v^<v<^^^<v>>v<v<<vv<>><vv^v^>>>vv^^<^^>><>^v<>^v
+>^><>^vvv<^vv<>v^>^>^<^v>><>^vv^<vvv>>v<v<v^<^v>^<vv^^<v^^^^^^v<v><v>^^^^<>v<>v<<><>>><>>v<^<>>v^vvv<<vv^^^^<>>^>v<<v<^>>>vvv>>^v<^v<<vv^<v^v^<v<vv>v>^^>v<>^>v>>^>vv><<>v<v>>>v<^>^v^v^><>^v^v>^^>vvvvv>^vv^v>>v>v^v>>>vvvvv>>v^>^>^vv<>vvvv>>^^<<v>^>>v>v>^v<v<<v<<^^>^vv><>^v^<^^^<vv>^<vv><^<<<v<v><<<^<^v^<^<<^<v>^v^^<><>>>^>>^vv>^>v><v^<v<<<>>v^vv^>v>>^vvv<<>>^^^>vvv>>^^><v>^>><<>v^<>^>^<^^^v>>><<^v>>^><>>vv<>v<><<<<vvv^^<<^^<^v<><v^^^>v>>^^<v<>^<^<<v>>>v<vv>>^<>^v<^^^><<^<<^<<>vv<><v^^v><<<<v>v<<vvvvv^v><v^^v^>v<^<>^>^<^v<>><<^^^^>>^^>^<><v<<v^vv>^>v>^^^>v^<<^v<v>vv^><><v<^^v^<><>v<v>^^<v>><<>><^^<^^<<v>v<v^<^>><<<v<<><v><><v>vv<^>v<<^<^^<<<v>><<v>^>><^><v><>v><>v<<>^v>>^<v>v<<v<^^>><<vvvv^<v<v^<^>v<<>vv>^<>^<>><vv<^<>><v>^<<<v>>>vv<>^v>v>^v^>>vv<vv>>v^<><>^<<^<><<vv^<<><>v>^<<>^^^>>v><v><>><^v><<vv<<v>^<^vv^v><>>v^^^^vv><>^>>>^^><v><v><^v^vv^v<>>^<vv^v><<<^^>v<v^<^>>><v<>vv>>^<v<^vv<>>>v>><^v>v<><><^<<v>vv<^<>>>v^><<>^vv^^><>v^>v<>vv<v>^>><<><^>^^>vvv><<vv<v^v^^^>v^<^v>^v>^<<<>^vv<<<v><
+<<^^>^v>v^v^vv><>^>><<>v>>><<<><>>vv^<<>>>^^v^vvv>v>v^^v^^vvv<>^<v^^vv<^v^>v>>vv>v>><^><<<<<<>>v<>>^^><<<>^^v<<<^<v^^>><<^v><<v><^vv<vv>v>^^<v^>v>>><v>^<^<v^^<><v<>>^^<>>v>^<<vv>^>v<>>v>^<v<<<<<>vv^v<>>^^vv<^<v^<^vv<^vv>><vv><^<<>v^v^^><v^vv<<<v^<v><><v><^>><>><<^^^v<><<>v^<^vv^>v^^<^<^^^<vvvv<^<^v^<>><><<<vvv><>^<^v>^>v^vvv<^^v<>><<^^^<v>vv>>vvv<v>^^v<v^^v^>>^^<<v>><>v<vv^<>v^>v>vvv<^^>^><^>^v<v^vv<><>v>>v<<v>>^v>>vv^>>^^<<<>v^^>^v>>>^<>v<><<^<v^>>>vv<^>vv>v><<^>^>>>>><v<><v>v<<>v<^^^<<vv^<<v^^>>^^>v><<<>>^<>v<vv^^vv^v^vv^^<<v>v><><^><^v>^<v^v>v^>^^>^^^<v<>>v<<^^><<<^>v>v>>^<><^>vv>^v^<>v^^^v>v^vv><<<><<><<v^^v^>>>^><>>>v><<<<^<>><v^^^<>><v>^v^vv^v>^v<^<<vv^<v^v<^<vv<v^<^^><^<<>>><><v^^^v>^^v<><<<^>^<^>v<^vv>>>><<v^^><>v<v<<v^<^>><>vv^>^vvv<^^<^vv>^vv^v<<<><>v<>v<^^^v^<^><^<^<><>>^<>v<>>>^v^>>v^v><^<v<v<v><^>>v>v^v>^<^><<<>^<<>v^v^<v^v^vv>^^<v^<<<<<<^<^v^v<<^<>vv<>^<^<^<^><^^<^><^v><^<vv>^v^>v<vv<>v^^<<<>^<^<v^<^<^>v<^><^<>>vv>>vv<><^<^>>^^v^^><>>><<<>v>v^<<<<v>>v^<v>v>>^v^<^vvvv^^v><
+v<^v>v>^v^^<^>v^<>v^>^>v<<vvv^^<v<v^^^vv^>v>>^^>><^v<<>v<>><^v<<^<^<vvvv<>v<<<<<v^v<<vvvvvvv<>v>><>^^^vvv^><^<v<>^>vv>v>>^<><>^v<^<^vvvv<v<<><>v>^><<v^v>^>vvvv<<>>v^v>><v<v>v>>>v<>>^>^v<<^><<^<<>^<^<v^<<>v<<vv<<v><v^v>^v<<<>vv>vv^^><vvv<^<>^<<^>^^<<^>^<>>v^^>vv^<<>v<v>>v^^vv<^><^<vv>>v><vv^>^<v^v^<^vv<<^<v<<v>^>^v>>v^v<<vv^<>vvv>^v<>^^<^<^<^<^<vv^>>v<^v>^v^<>^^<>>><<>><<<^>^^<v><<<v^v^<<>^<<v<v<^>>>^vv<<><^><^v<<^<^^^<>v>^v<>v<^<^<<v<v<v<^><<>><<^vvv<^<<^<^^>v^^^vv>><>^^>v>v<v<><^vv<v^^v>^<<><><^<v<^^>>><<<<v>^v><^>>^<<^^<^>^v^>>><^>^^>v<>v<><<^^>^>^<v><vvv>^>>^^>>>>^><^^>vv<>^^>>>v<<<vv<^<<v^vv<v<<^^v<^v<v><<v><><><v^>^v<vv>v><v^<>><<>^>^<v^>^v>vvv>^v><vv^v^v<v>^>^vv<v<^^<<<^v^v>^^>^^^<v^v<^v<vv><<>^v>^><v^>v^vvv<^>vv>^<^<^vv^<>>vv>v>>^<v<v<<>^>>v<>><>^<<^^^vv<<<^v^^v^<^><v^v<>><^><<^><<^<>v^v^><v^^>v^><>^>><v>><<^v>^<>vv>>v^<<<v^<<v^v^^^<^<v<><>v<^vv<>vv<v^<>^><^<>>>^v^^>>v<>^^v>>>vv^<<>vv^<^^<<^<v><^^>vv^vv^<>^v<<>^<>^>>vv^vv^^>>v^v><<<>>>^><vv^>v<>v^^><<v^>v<<>^>>^>v>^<^>v^v^><^^v>
+^>vv^<><^^<>vvvvv<^<v^^v^<vv<^^^<<<>><^v><<<><<v<<<^^<vv>^v^^>^v^<>v<^>v^<<<^v^^^<v<v<v^<<<^v<<<<^^<^v>^>v^v<^^v>>>v^<<^<<><>^<>^<v<^<v<^^<v><v<v^>vvvvv>><^>v^^<vv<^^^>>^<><>^^<>vv>v<vv^><>^v^^v<^v^<^^<^<vvv<v>v>v>>^<^>>vv^<^><><>^^v^v^>^<>><vv>>v^vvv>^>^v>v>v^^<^>>v^v><<>><^<v><<>^><^<vv<<v^><^v<<><><<^>><v^<^<v<><<^v>vv<v>^>v<vvvv>>^>v<^^<>vv^<>v>>><^v^>>vv>>^v^vv^>>>>^vv>v>><<>><v^<>v><v^><^^>>>><^<<<v^<v>><v^v^^<^<^>><^vv><><<<vv<v><v^>vv>v>>>v^<>^><v<<<^<v>vv^^>^<<v<<<^^<<>^v<><<>vv<^>v<^^v<v>v^<v^vv<^vv<^^v^>v><^vv<v<><v>>v>v>^>^<v^<v>v>^^<v><^^<v^v^>>^<^^^^<vv<v><v<<>v^^>^<^^<<>v>vv<<^^<>^v>>>^<<^<v>>v>>^v<<><^<<<>^>>^>>^>v>^>v<><vv<^^^^vv>^v><><<vvv>vvvv^v>^><v^<^<v^>v^>><<v<v<^^><vvv^>>>v<>v<v^<vvvv^>^v>>^<v<^^><vv<>v^^><v^>^>v>^><>>>^>^>><^<v>>vv<>vv>^vv<>><><>^v^<<<<vv^v<<^><<vv<v<^>>>v<v<>><vv><<v^^v^<vv<>>v<>^v^>^^<<v<v<^<^>v^>v>^><^v>^^v>^^^<v><^vv<v<v>>^>v>^>^<<>v<vv>^v^<<<>v>^^v^>^vvv<<vvv>><^v<v<><^^>><v^v<vv^<v>v<vv^v<<v^>^^>><<>><v<^>vvv><v^^><^>>^v>v^v>>>^<^<<<v^^^v
+v<<v^<>vv><<v<<v^^>>v>^><<v^><<><>>vv<>>^<<<v>^<v>>^><<>>^>^^<vv>v^>v^<>>>^<v<<<v^<<^v^<>^<v^<>v<<<<<<>v<>><<>vv^^<>vvv^>^v>^<v^v^<v<^<>v^v^^^><v>^^><>^^v^^<^v<v^vv<^v>>^<vv<<v><v><v<><^^>><^v<>v^>v^^>>^^<^>><^v>vv<<^v>v^^<v^vv^>>^>^<^>><v<<v<<><^>>v>>^<^>>^>>>^^^>v<>^>>v<>><<^vvv><v^>>^^vvvv<v<>vv>>>v><<^v^<<vvv^><<<<v>^<<><>v><v<v^v>>^^>>v>^<<<v^^<<v>>v><>v<><^vv>^^>>v^^><^^>>>^>vv>^<>^^<^^v<<<<<^^v^v<>>^^v>><>>v><^v><<<<^<><>><><vv<^<<^<>>^<><<^>v>v<>^<<^>^<^^^>^v<<vv^<>>>v^<<^^>v>^vv>^^<vv<v^^>v><vvvv^^^v<>vv<v<^v^<^<^vv>^<v<><<<>^><v>v^^v>><<^v<^^>vv<v^>^>v^^><v<vv^^vv<^v>^><^^vv^<^^^vvv^v<<><vvv^<v>><<>>>>v>^v^vv<v>^>v>v<>v>^>^<^>^><>v^^<^<^<vvv^>^v<>><<<<^><><>^v^v^vvvv<<<<v<^^><vv^<^<^<^^vvv^>v^v>>^>v>^^^<^v<<<><>v>>v><>vv>^v>^^<<>^<<<>^><>>v^v<v><^^<<^^<>>><vv>v>^<<^<>>^vv^^^>^vv>>>v^>^>^<v^v<<<^<<v>^vv>vv^^v><<<<v><<v^vv^<><^<>vv<<v>>>v<v<<^<^^^v^v<<^>^<^>vv>^^<><v^v^<<^^<<>>><><<v<<><vv^vv>^v<>>v^^<>>^>>>v<^<^><v^v^>v>>^>>^v^^vv^<v>^><v>vvv>v><>^><<v>v^><><v^v<^v>v<v>>v>v>>^
+vv<<^v><<v^<^v<>>v<v^<^v^>v^^vvv^>vv>>^^>^<^>^^^v^v><vv<v^<<v^^>v^>^<>><^^v<<vv>v^<v>v^<^v^<<^^><v<>v^>^^<<^>>>^<v^>>vv<^^^^^^^<^<v^^>v^<^vv<^>vv<^vv>^<^<><^<<>>v><<>^<<^v^><<v^v^^>v^^>^>><v>v>^^<>><^>^^>^v^v<v>>vvv^>>^v^>><>><<^vvv<^^>v^<<v><>><>>^v^>^<<^<<^v<v>v<^^v>><v^<v<<v^<^v^v>^>v^<>>>vv^v^^vv^^<^vv<><<>v>>>^>^^<<^<><>><^>>>^v^<><>^^>>>><v<<vv^v<<><^>v>v>^<<v<vv<v<>vv^^<v>^^<>^><v>v^>^><^><^^^^v^v<v^><v>vvvv<><<<><v^^^^^v<<v>>>vv<v<>>^<>><<<v<^>^>>^<<<<^>^<^^v>><^v>>v^v><<^<^<<v>>>>^v^v<v^v<vv^^v<<>v>^>v<<v>^^v><><>^<v^><<<<>^^^^<<vv^^v<^<v^<<v^>^vvv<>>v>>>>v><^>v>^v>v<>>><>v^<<<<>v>^vv<^<<<>^>><^>v>v<<>>><^v><<<>v^v<v^><>^^><<<v^^>^v^^<vvv<v<<>v<^v^^^^<^v<<v<<vv<^<^>vvv><><^v>><><vv^<^^^<<v>>^v>>^<vvvv^^^>>^v>^v^<v^>^<^^^^^^<>v<>v>^<>v^v>^<^v>^<v<<^>vvvvv>^vvv<<>^v>>v>v^v<<v<^^>v^v<vv>^>vv<^>>vv^^>v^>v><v<<>>>^<>vv<>^^^v^<v><>^v<<>>v>vv<vv^^<>vv<<<>v>>^^^^v>^^>>><<^^>v>>^v<v>^<v<v<>v>><v>v>><>^^>>^<<v>^<<<vvv>vvv<>^^v><<<<<>^<vv^vv^>v^v^<>>^^>vv<><<<<v^<^vv^^^^v<v<>>^<<<>>>>^v>
+v<v^v^><vv<^v<v<^<v^vvvv^^v>^^<><vv<>>^vvv^v>^v>^vvv>>^<v^>^^>^^<>v>^^v>v^^vv><>>v<<><<<>^<^v>>^^^v><>^<^<<<^<^<v<<>><<^v^<<<^>>><v<><>^>>v<>>v>v<v><<<<^>^<^v>^<>^<v>v>v^^^><^>>><<v^><^<<v<v^<v<^v<<^>>>>vv^<>>>v<v<>^<^>v^<v^>vv<^><><v^^v<><^<<<><^v^>>^<^v^<><^>v^>><<v^<><^v>^<<vv>v<><<^^<^<<v>^^><^v><<>^<<>^>v<>v>v^<<^v^v><>>>v^v<v><^^<>><^v^<vv^<vv^<<><>v>^<v<>^<>>v^^<^<<>v<^^<>^^^v>^^v^^^<><v^v>v>>>><>v<v>>v><<^<>v^vv>v^<v<vv<v^^^^<^v^>v><^><^>>v<>^>^^^^^<<><^^v>v<><<vvv<^>^<>vv>v<>><^^<><>><v<v^v^<^^v<vv<<v<<<vv<v><v>v^>v^^<vv^^v<vvv>><vvvv>>v<v<<<><<v^^v<>^>^v>^^^>>^v^^>><<<v^><>^<v<^^^>>vvvv^><<^^^<>>^<v^vvvv^v^v<><<v<^^^vvv><>^<vv<>v<v<^v>vv<vv>>>>>^^vv^<^<<<>^><vv<^vvv>^^>><<<^><^v<v>v><>v<v<v^^v>^^<<v<^^^v<v<^>>^<><v^v<><<<><vv^^^^v><>vvv<v>>vv><vvv^<<^>v>v>>v<>^v^>vv>^>>v>^>>><><<>>^^<>>^><^<<^>^>vvv>>^vvv<>v><v>^vv<<>v<<>>^v<<^>>v>><>^^>v^^<^>>v><>v^>v<^<>>vv<^^>><vv<<v<>^^>vv^>^<v<v>vv<v^^^<>^><^^^>^v>^v<v<><><^<^<^<^v>v>^^><v>^>>>^v^v<>vv<v<>^^^^v>>v^>>><^>>v<<<^^<^>><v^v^v
+<<v>><v^v^^<<><v^<v<<><>vv^^<^v>^v>v><>v<><<v>^^^^^>>><<vv^v^<>vvvv><v>v>v<>>v^>^v<^v>>v<^<vv^v<>^<^^^>v^v^>>^>^vv^^^vv>^v>><>^><><^>v^^>v<>>^v<v^v^^>>^^>>v>^>>v^>^^^>^v<><^v<v><<^>vv<<><vv<v^v<^v><v^^^<<<v^<<>^>^<v<vv<<>^>v<<vv><^>vv<<^vv<^<>>>^<>>v>v>>><^v^<v<<<^^v^v^>^^<v<^<>v^^>vv^v^<^^>><^v<<>><><v^^><^^<<>>>^><^>v^<v^^><<<^<<v>v<>>><^>><<>>v^<^vv<><v>v^v<^><<v>v>><<^><><^^>><<>^^>v<^<vvv<vvv^^<v^>>^v<>v^vv^^v^vv^vv>v<^>v^<v<vv<<vv<^^>v^><^v<^^><vv>^v<v>>>>v^>>vv><v<v<v<^v>v><^><<<<<vv>v<<<>v>v<v><>^<v<^>vvv<<v><>^^<^<^<<v^v^^v<><^><v>^<^<^v>^<>>><v><v>v>v^<v>><vv>^>><^v>v<^^<><v>><<><^<<<>^vv>><<<v<^v^<v^>^<v<>^<>^^<v><^vv>><<><>v>v>>>>^<>v<vvv>vv^^^v^>>v><<^>>><>^v^v<>><<<>v>>><<<<><v>><^v><><^v<^><<<^vv<^vvv^<<<vvvvvvv>>vvv^<<<v^>^<<^<>v^<><<>>^<v<<<^><v^<>>>>^>v>^>^><<<^vv><^<<<^^<>>v^v<v^v><v>^v<^><^vvv<<^^^^vv>><vv<<><^>vv<v<^<^v<<^<v<v^<><v>>vvvv<^^<<^v<>^>^^v^v>v^^<v>>><>vv<v^v<^><><>^^^^^v^>^vv<^<^<v>^^>^<v<v<><>vv^<v^v^vvv>v^^v<<<v^v<v^><v^v<<<>^>v^><<v>>>vv>v^>><>^v>>v^
+<>^>><v^>v>v<<>^v>^>><<>^>v>^<v>v>v>v<v^v><<<<v<>>^^v^>v><<^^v<^^>><^vv><<^<v^><v>>v^<v^v<^>v^>^v^>v^v^>>>^<><<<>^>>>v<vvvv<<>>vvv<v><^^<<><^vvvvvv<<^v>^^^v^^>vvv>>v>^v^vvv^><>><^<^v<<>^^>vv<<<^<><^^v<^><>v^v<><>v>vv<v^>v>^^>^v<>><>vvv<^<v><<^>><^v^vvv><^><<^<^<v^v<v<<^vv<>v^^><v>>>>v^v<<><^><v^<<>v^^>^^<>^<>^^v<^<>>v>v>^<<v^^^v^>^^<<<vv>^^>>vv^^<>>^^<>v>>^>^v>^>v>v>>vv<>v^v>v^v>><<vv><>^^<><>^><v<<<v>v^<<<v>>>>vv^vv><^^>>v<v^<vv<^<>>>vv^<^<>^vv>vv<>v<^>^>vv^v<<<<>^>vv<<^v^v><^>vv^<><>^><v<>v<vvv^>v^^v<v^^v^^<<v<<vv>><v>>>^vv>>^>vv^><v^^^<vv><vv^^<^><vv^^<>><<<<<v<<v<v^>^<v><^<^^>v<<>v<<vv^<>v><<<>^<vvv>><^<^>^v><>>>>>^<<^<>v>^<^<<v><v>v<>^v<<^><<<^^>>vv>^<v><<><>v^<^<><><vvv><^^^<vvv>v>^v><v^^v^v<<^<^>>v^^>vv<^><><><>^^>^v>v<v^^<>^v^<><^<>>^^<>v<^v^^>^v<<<v<<v>v<>^<v>>^>v^vv<^^<v^>>^>><^><^v<v>v<>^v>^v<v>^<<<>>v>v<<>v^<<vv<^><^^^vv>^<<vv<^<v><v><^^^v<v^<<v<^^<>>^<<v>^<><^<vv^v<<<><<v>v>v><v>v<^^v<<v<<v^v^<<vv^vv^v>^^<<<<<vv^vv<^^><^^v><>v<^^^>>vvv<><^>^v<v<<^v<<^>^>^v>^^v>>vv>>v^><>^>
+v^><v^v<<<v<v<<<<<<v>^>>^><<v><><>v<<v>>><>v>^>^^<><<^<^>^^^^<<^vv<^<vvvv>^^vv^><<>>>vvv<>>^v>vv>>^^<vvv>v<<^<^>v<v^><>^<>^^vv^v><v<^>^<v<vv^>^^><>>>v^v<<><vv<<^^><>v^<^>v^^><<vv>v><>>^v>v<v>^<v^v^^<^<v<^^^<^<>v^<v<<>v>v^>v>v^>>^^^^^>^<<vvv<>^>^^vv<^^>>v^v<^><>vvv^^>^<v<<<>^<^^>>>v>>v<<^>v>><>^<>^v>^<<^<<>>>v^<>^<^v<<v^^vv<v><^^v><^vvv<v^<>><v<v^v<vv^^<^v^<v<>>>>>vvv^^^<vv^<^^>><^<><>v^><^<<v^v>^^<>>v^>^v>^>v<vv^>v<>^v<>><vvv><>^><^v<v^v^^><^<>^^v^>>>v^^vv>v^^<^>>^^^<>v^><<>^^<v><v^<<><><^v>^vv<<^<^<v>^<vv<<^^<>^v<vvv<>><v<>^^>>>^^><v><^vv<^v<<<<^vvvv^v<^v<>^vv^<^<<^<>v<v^v^^>^v^>>^>^>v<<^^vvv><><vv^v>v<v<<v><>>v^<>v^<v>v<<^<<^^>^v^^v<^<^vv^v>v^v<v<^>v<>v^^<^<^vv^^<^<^><v>>><>^<<v>^v^>^>v<>^><v<>^^v<<^<^^><^v>vv^<^<v>>>v>><vv^^>^^^>>><>v<<<^<^<vv^<>^v<^>>^>v^<<<<v^v>^<v<v^<>^<^v^>^>><<<v^vv^^^v<^>^>^<^^<v<^^^vv<>>>^>vv^<>>^^<><^^vv<>><>^><>^vv><^v>v^>vv>v^>v<^v>v^v>>v^vvvvvvv^<><vvvv^>v^>^^>v>^vvv^>v>v<><<<>><v><<<v<^^<>v^<>>^<<^^v>v>^v>v^^>^>^^^^^>v^<>^vvv><>vvv<<>^>v>vv^vv^v^>>^v><v^
+>v>v>vv^><^<><v^<^^>v<>^><^>v^<v^<^^^<^vv<v<>>>><<v><vvvvv<>v^>vv<v^^vv^v<>v^<>><<^v<>vvv^v>^<v>^>v<^^>><>^<<>v<^><v<^><<v>^v^<<^v<<<><^<><<<v^v^<>^<v^<^^^v<vvvv^vv^>^<vv>^>v<<>>^<<v^^^v^<vvv^v^v<<>vvvv>v^><v^v<<^<vv^v<<<>v^vv>^><v^<v>^^><^^v<>^<>v^v>^v<>^>>^v<^vvvv^>>><><<<>vvv>vvv<>>>v<vv>v>v<<v^<<<<^^<^^v^<>^<v>>^>v>^^>^^^v^^v<^>>>v^<vvv<vv<>v>>><v^><>^vv><v<^vv<v^^^^^vv<vv<<<>^^vvv>>v<^v><<^v>v<^<>^<vv>vv<^^^^v<><><<<<^>>v>v^>>><>vvv>>><<<>^<v><^><v><v^<>v<>^>^vv<^<^vvv^>^>>^<^^vv>^v^<>v><v<^^>v^<<v<<>><v><>>^^^v<>^^^vv^>^<<>^>v><>vv>>^<<>>v<<^vvv<<>^^><<>>v<^v><<>v><><<<v^^^vvv<<<v^><>>vvv<^<^>^^<^<>><v<v><<v><vv<>v<<^>vvv>>v<v<^><v>v^><vv^^><<<^><<>v<<<^^v<<v<>^^<>>>^v>v>>>^>><<<^^^^>>v^<^^<<^>>v><<^>>>^^^^^<>^<^<vv^>^<<^v<v^v<^>>v>>v>^v^v<>^>^^>v<>v<<^v>^<<v><^<v>>>v<vvv^<<^<^>^v><>><<^^vvv^v>v>^<v<><<<v>v^<vv>^<<<>^><>^<v^>>vvv^>^>>^v>><^v>v<^>^^><^<v^vvv<<<>v^vv<^^<>v<>^<<>v>>^<^^vv<<<>^^^^<v>^<>>v^vv^v<>>><<>^^<^vvvv^>v<^<<><<^>^^v^<<^<v><^v^^v>><v^^v<v>><>>>vv^>>>^<>^^<<^^^>
+^^<v<>>>>vv^^<<>v>^^v><<<>^<<><<vv<v<<>v>vv^>^<<<<>><^^^v<^v><><^<>^^v><<<vv<<v^>^v^>>^<>^<<>>>>>^>v<<v^>^<v^^^><>>>^v<v<^^v>^>v><<^^<<v><><^vvvvv^<<v>^>>><^<<><^>^<^><<><<v^vv><<^^<v><^vv<>>^^>^v<><>vv^v<^<<><<><<><v^vvv^vv<^<<<v>>><<^><^vv<<^v>>><><v^^^v<>>^v<<>v>vvv<>^>^v<v>^v>v>v<>v>><><^<^v^<v<v^>>>^>v>>>^^>>>v^<<^v<<^^>v>v<^<v<<>^<><>vv>>>^^<^^<<>vv<<<v<><<^^^<vv<^>^>>>^v^^<>><<^v^<>v^^v<^^<v^>>v>>v>><>v<^^v<<<<>v^v><>>^>^>>^v><^><>^>^<<^v<v<^<<vv^^<>>><^><^^<<<^^>v>^>><<<vv^^v^<^<>^v^<>>>>^vvv><^v^v<v<^<v^><v^^><vvv<<>^>^vv<>v>v><<>>vv<^vv^v^<<<><^><vv>v^<^<v^v<vvvvv>vv^>><^>><>>>>^vv^^>><v>>>^<>^^^<><vv>vv<^<v>><<^<^v<>^<<<^vvv>>><<v^^<vv>>>v^v>^>^><v>^vv<><^v>^^>^<v>v<>>>v>v<<vv>^><v>><v^>v>^<^v^<^v<>>vvv>^^^<v^<<<^<><v^^>^<<vv^<^^^^>><^>^><>^^^>>>^^vv>^<v>v^<<>>v^^<<><^v^>>^<v>>v^>^<>><^><<>^<v>vv<vv>^>>vvv^<<vv>v<>>><>vvv>v<><^>>>v^^^^>>>>^v<^vvv<^vvvv>>^><v^>>^<^<>^<<^><v<v>^v^<^>v^^^v<v>><v<>^v^v<><v>>^^v^<^^^^><v<^^v>^<<^<>><^v><v^<<<>v<^^^vv<v>^<^v<>vv>^<^>v<<v^v^<>v^v<v
+^^<<<vv^>>^<v<<>v>>v^>>v><vvvv<v<><v^v^^<>v>>^^<^v<>v<>>>v<^v^<v>^^^<<<^>^^v^vv>^<<v><><>vv<^^^v^^vv>^vv^^>vvvv^vv<vv>v<>v^^v<<>^<>^v<<>vv^>><v<<^vv<>v^^>>><><^^<v<<vvv^>^<>^<>^<><^><<<v><>^v^^v>^<><^><<^>^v<<>^><>^>vv^^<<vvv<v^v<<<>><v>^v^^^>v>^<<^<v<v^<^<v>>v^<^^^>>^>v<^<><^v><^^v<v^<><<>>vv>v<<<v^vv>^^><>^<^>v^^<^^<<<<<^v^>v<>v^<>>>>v<>>v><<^^^>><>^v^^v^><^^v<^v>vv>v<^v<<v<vvvvv^<><v^<><<<^<<v<v^^<^v^>><>>><>^v^>>v<>>v^>^<^^<v^>v><^v^^vv>^<vv<>>vvv<>^^<<vv^v<v<<vv>><v^<vv^<v<<><v<vv<^v>>^^>>^>v^<v<vvvv<>^v>v^<^v<^><<^v<>>^^<>v><>v^>vvv>vv^^<v>^^^<^v^^v>v<v>>^v^v^v^<<v>>^><v<>^vv><^><>>>^<^>^^vv<v^^^^v>>>^^^><v^><v^^^v<>v>^>vv^^v^>v><<^>v><vv^v^>^v<<vv^^<^v>vv><<v<v><v^v^v><^>^^^^><>v<<v^^v>v><><>><>>^^>>><<<>v<^^vv^>vv^v^>^^>>^^<<>vvv<<<v><vv>><<vv^vv<>^^<^v^v>^^<^v>>>^<^<>^^<>^<<<<>><^<v><<^>^^v>^><<v^>>^^^v><<<vvvv^<v>^v<><^>>vv><^>>>^<>v^<<<>^^v^v><^><^^v<^vvvv<><<^>>>^<v^^<<vv>><<><<><<^>v<>>^><^^^vv^^v<^>v>><^^<^>^<v>^v^<^><<>^v><><^v^<^v^>><v>^v<vv<^v^^v^^vv>vv>>^>>><v<><>><v<
+>^<v<v<<<<^v^vv>><^>^^<^vv>^>v>^^<^^<v^>>^vvv><^v>^v>vvv>v>^<^^v^vv^v^v>><<vv>vv<vvv>>>^^>^><<^>^<vv^>v<^^v^>vv<^v<>>vvv^^<>>^v^>^^>^^><>^>v>><^<^><v<^<^v^><v><<<^v>^>^<^>v<vv<>^v^^>>>><v>>^>^><^>^>>^vv^<vv><v^^^>^^v>^v<>>v<><<vv><^^^^^<v^>v>^^<<<>^<><^>^v<<>^^>^^^v<>v><>^<<>^v^<<vv>^<v<^<v^><vvvv<<>><vv<<>v>vvv^^^^v<^^<^<>>^><>v<^^>^^^^v^<>><^>^^^<^vv>^>^^^>v^v>^v><>^^<>v^<>^^<>v^^v^<><^<v^>>^<<<<vv>v><<<vvv>^<^<^>^^<<v<><>^<v<^^>>^^>v^<<<vv>v>^>>^^>^>>>>v>>^<<>vv<^v^>^>>>>^<v><<<><v>><>v<><>>v^v>v^^<v^<vv<<<v>^^v>>>^<^vvv^vvv^>v>>^>v<>>v^<^v><><<vv^^<>v>^v>v>><v^<v^v>^<^v>vv^<<>>>^vv>><>^<v<<<<v^^>><<<^><^><^v>><<^^^v<<^vv^^><<<v^<><<^<>^><v>v^v^v>^<>vvvvvvv^>^>^^>v<><^><<>^vv<>^v<v^v<>v<<><v<><v^vv>v<^v^^<vv^>>vv<v<<>>^^>v>^^vv^>><^v^^^^<v<vv^v^<<<>v<<^^^vv>^^vv>>>^^<<^v<>>v<vv>>>vv<^^<>>^>vv^>>><<>^>v>vv<^<>vv>v^^<<^^^vv<>^^v^<^>^^>>>v>>^>^v<^><^<>v^v<v^<>>><^<^^<^^>^^>vv^>^><<<v^>^^^vv>><vvv^v>>^vv^<<v>vv>^<>^><v>vvv>^>>><v<^<<>vv>>>^<v^v<v<^^^<v^vvvv^^^^v<>><vv^vv<>vv<<<<<<v^^^^^
+<<^vv^^vv^><><<>>><<<^>^<^v>v>^><>>>^>vv>v^<<<vv>>^^^v<>v>vv<<<vv<<^v>v<^<v<^>^>v><^<>v><<><v<>>>v>v^v>v>v^^^v^v>vv^^>^><v^<<v^v>>^><v^^<<v^^^<^^^vvv<<^>^^<^^<^<<^^<v<<v<>v><v<>v^^^<vv^vvvvv>^v>vv^^>>vv><<^<v<^^>^<><v>><^^^^v>^>v^><v^>v>>><>^^v^<><>^><<<>^<^^>^>vv<>>^v<<^<>>>v>vv<vv><<vvv<<v<<<>^>>>v<<^^v^v<vv<v^^<>^^^<<^^v<^v^^><^^^>vvv<v<v>v^vv>><<><><vv><<><v>^<<>^^^>^^<^<^>^<><>v^^><^<^vvvv>v<v<>^^v<^>v><><^^^>>>>v^<<<<vvv>><>v<v<>^><^v>>v^>v^><v<v><^<>^^^<^<<>^<<<v<v^<>^^>v<^>^<^<^^vv>v<vv>><^<v^v^v<>vv^>v<^^^<v<v<>>>v<>>^^^<<^^v<<v><<>vvv^>^^<^>^vv>v><^<^<>>><<v<<>v>^>v<<>>^<^>v>^^<^><<<<v^v^<^>^^>>v<v><>>>^^>^>>vv>v^v^<v<<<><>>^^>v<^^>v<v<<<^v^^>v<v<v<>^<^v^vvv<<>^<>^v><vvv^^^v>v<<^v<>>vv^^^v^<vv^<<><^^^v^>>><<<v^<<^v<<v<><^>vv><<><v<v><<v><<>^v<>v^><v^v^<>v^>>^>><v<v<<<>v<^>^<v<^<v>v<><<<^^>^>^v<<v>^<<v>><^><^^<<^>>>>>^>^><^<^^^<v^^v<v<v^^v>vv^<^v<><>^><<>^<^^vv<><>>>^<v<^v>vvv<>^<<<>^^<^^^v<v<><<^>^>vv>>^vv^^>^^<^vv<<>>>vv<^<<^vvv^<^^v^<v>vv<v><><>^>^^<<<^<v<v^^>><v^^vv>><>>^>
+>vv^>v<<<>^>>>^^>><>vv<vv>^>^v^^^^v^v^>^><<v<v>>^<>v>vv>v^>^<<vv^<^v>vv^v><>>>>>^^<^><>v>vv>v<^>vvv><^^^>^^>><>>^^vv><v^v^<^<v^^v^><<^<v<<v^<>^^v^v^<>vvvvv<^vv><<vv<<<vv>^^^>vv<><><^v<><v<v<<v>>v>^^vvv<^^<<<><>^^><^v>^^<^>v<v><v<v^<^^>>>><<v><<>>^>vv>><vv<^>v>^<<v>><vv^>^v^<^>>><><v^<><^v>^^>vvv><vv^><v<vv^><<^v^^^vvv>>^>^v<vv<^<^^v>^<v^^v<<^v>^<<>>v^<^<^>>^^<v>v^^v^<>^v<v<>><^>>>>>>v<<<<>^^v><<>v^vv<<>^<^>>v>><^vv>^>vv^<v>^^<v^^>>^>>>v^^>^^><^v<><>^^>>>^v>^><<^<>^^^>^v>><v><>>v^>vv^^v<<><v^^^^^vv>^<^<v^<vv><>v><v^vv>v<<>v><<vv<^<v^<^>>^>^><^v^v>^v>><v^v>v<v<^v^vv>v<^vv<vvv<v^>^<^>vv<^^>^<^<v><^><<<>>^<<^^<^<v<vv<<^>v<v>>v^>^>^><<>^<>^^>v<<>><^v>>v>>>>>>>v^v<<^<^><^^<<v<vvv^>>v<<><><<v^^vvvv^<^<<>^<>><v>>^><^v<^>v<^><><<<>>><>v^^<<^<<<>^^<^^^^>^<>>v^^vv<vvv><>vv>>>>>>^v<>v^^<<>^<^><v^<^^><v>v^<<^<^>vv>^^>vv^>^v>vvv^>^>>>>><<<>vvvv<^>>>>v>^<v>v<v>^<^^v<<><^v<<>>v<v<v^^>vv>vvv<><>vv<<<^^>>>>v<>^>^v<v^vv^v^<^>vvv>v>^^v^v<>vv>>><^<>>v>vvv^>vv<<v>^^>>^^^>><><v^<^^v>vv<^^v^<v^v^v<<<^^v<v>^<>
+