# Background

My pet bridge-maker ants are marching across a terrain from left to right.

If they encounter a gap, the first one stops and then next one climbs over him, then the next, and the next, until a bridge is formed across the gap. 

What clever little things they are!

Now all the other ants can walk over the ant-bridge.

When the last ant is across, the ant-bridge dismantles itself similar to how it was constructed.

This process repeats as many times as necessary (there may be more than one gap to cross) until all the ants reach the right hand side.

# Kata Task

My little ants are marching across the terrain from left-to-right in the order ```A``` then ```B``` then ```C```...

What order do they exit on the right hand side?

# Notes

* ```-``` = solid ground
* ```.``` = a gap
* The number of ants may differ but there are always enough ants to bridge the gaps
* The terrain never starts or ends with a gap
* Ants cannot pass other ants except by going over ant-bridges
* If there is ever ambiguity which ant should move, then the ant at the **back** moves first

# Example

## Input
* ants = ````GFEDCBA````
* terrain = ```------------...-----------```

## Output
* result = ```EDCBAGF```

## Details


Ants moving left to right.
GFEDCBA
------------...-----------

The first one arrives at a gap.
GFEDCB     A
------------...-----------

They start to bridge over the gap...
GFED       ABC
------------...-----------

...until the ant-bridge is completed!
GF         ABCDE
------------...-----------

And then the remaining ants can walk across the bridge.
               F
G          ABCDE
------------...-----------

And when no more ants need to cross...
           ABCDE        GF
------------...-----------

... the bridge dismantles itself one ant at a time....                
             CDE      BAGF
------------...-----------

...until all ants get to the other side                
                   EDCBAGF
------------...-----------

```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 = 'from queue import deque\n\n\ndef ant_bridge(ants, terrain):\n    terrains = \'-\' + terrain + \'-\'\n    marching_ants = deque([ant, -len(ants)+count+1] for count, ant in enumerate(ants))\n    print(marching_ants)\n    bridge_ants = deque()\n    # 在地形上前进\n    for pos in range(1, len(terrains)-1):\n        if \'.\' in terrains[pos-1:pos+2]:\n            # 当前位置是坑，拿最前面的行进蚁填坑，其他的前移一步,并检查是否要拆掉最尾端的桥蚁\n            leading_ant = marching_ants.pop()\n            leading_ant[1] = pos\n            bridge_ants.append(leading_ant)\n            march_forward(marching_ants, bridge_ants)\n        else:\n            # 当前位置不是坑，所有行进蚁前移一步，并检查是否要拆掉最尾端的桥蚁\n            march_forward(marching_ants, bridge_ants)\n    # 到达最右端后，继续行进所有的蚂蚁，直到没有桥蚁为止\n    while len(bridge_ants) > 0:\n        march_forward(marching_ants, bridge_ants)\n    return \'\'.join(ant[0] for ant in marching_ants)\n\n\ndef march_forward(marching_ants, bridge_ants):\n    """\n    将整个行进蚁前移一格，并拆掉最尾端空闲的桥蚁\n    :param marching_ants: 行进蚁队列\n    :param bridge_ants: 桥蚁队列\n    """\n    print(marching_ants, bridge_ants)\n    for ant in marching_ants:\n        ant[1] += 1\n    if len(marching_ants) == 0 or (len(bridge_ants) > 0 and bridge_ants[0][1] < marching_ants[0][1]):\n        marching_ants.appendleft(bridge_ants.popleft())'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'ant_bridge'
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: 14423