[Langton's ant](https://en.wikipedia.org/wiki/Langton%27s_ant) is a two-dimensional Turing machine invented in the late 1980s. The ant starts out on a grid of black and white cells and follows a simple set of rules that has complex emergent behavior.

## Task

Complete the function and return the `n`th iteration of Langton's ant with the given input.

### Parameters:

* `grid` - a two dimensional array of `1`s and `0`s (representing white and black cells respectively)
* `column` - horizontal position of ant
* `row` - ant's vertical position
* `n` - number of iterations
* `dir` - ant's current direction (0 - north, 1 - east, 2 - south, 3 - west), **should default to 0**

**Note:** parameters `column` and `row` will always be inside the `grid`, and number of generations `n` will never be negative.

## Output

The state of the `grid` after `n` iterations.

## Rules

The ant can travel in any of the four cardinal directions at each step it takes. The ant moves according to the rules below:

* At a white square (represented with `1`), turn 90° right, flip the color of the square, and move forward one unit.
* At a black square (`0`), turn 90° left, flip the color of the square, and move forward one unit.

The grid has no limits and therefore if the ant moves outside the borders, the grid should be expanded with `0`s, respectively maintaining the rectangle shape.

## Example

```python
ant([[1]], 0, 0, 1, 0)   # should return: [[0, 0]]
```

Initially facing north (`0`), at the first iteration the ant turns right (because it stands on a white square, `1`), flips the square and moves forward.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "def ant(gr, cl, ro, n, di = 0):\n    class ant_class():\n        def __init__(self, col, row, direction):\n            self.c = col\n            self.r = row\n            self.direction = ['N', 'E', 'S', 'W']\n        def __repr__(self):\n            return ('col: {}, row: {}, direction: {}'.format(self.c, self.r, self.direction[0]))\n        def turn_right(self):\n            self.direction.append(self.direction.pop(0))\n        def turn_left(self):\n            self.direction.insert(0, self.direction.pop(-1))\n        def move(self, grid):\n            if self.direction[0] == 'N':\n                 if ant.r == 0:\n                    grid.expand_north()\n                 else:\n                    ant.r -= 1\n            elif self.direction[0] == 'S':\n                if ant.r == len(grid.grid) - 1:\n                    grid.expand_south()\n                ant.r += 1\n            elif self.direction[0] == 'W':\n                if ant.c == 0:\n                    grid.expand_west()\n                else:\n                    ant.c -= 1\n            elif self.direction[0] == 'E':\n                if ant.c == len(grid.grid[0]) - 1:\n                    grid.expand_east()\n                ant.c += 1\n    \n    class grid():\n        def __init__(self, arr):\n            self.grid = arr\n        def expand_south(self):\n            self.grid.append([0 for i in range(len(self.grid[0]))])\n        def expand_north(self):\n            self.grid.insert(0, [0 for i in range(len(self.grid[0]))])\n        def expand_east(self):\n            self.grid = [i + [0] for i in self.grid]\n        def expand_west(self):\n            self.grid = [[0] + i for i in self.grid]\n        def invert(self, ant):\n            self.grid[ant.r][ant.c] = int(not(self.grid[ant.r][ant.c]))\n        \n    ant = ant_class(cl, ro, di)\n    field = grid(gr)\n    for i in range(di):\n        ant.turn_right()\n    \n    for i in range(n):\n        if field.grid[ant.r][ant.c] == 1:\n            ant.turn_right()\n            field.invert(ant)\n            ant.move(field)\n        elif field.grid[ant.r][ant.c] == 0:\n            ant.turn_left()\n            field.invert(ant)\n            ant.move(field)\n    \n    return field.grid\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'ant'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 15090