Determining whether a Turing machine halts is well known to be undecidable, but that's not necessarily true for simpler machines.

A *Foo machine* is a machine with a finite tape, where each cell on the tape has an integer or the halt symbol `h`, e.g.

`2 h 1 -1`

The instruction pointer starts by pointing to the first cell:

```
2 h 1 -1
^

```

At every step, the instruction pointer moves forward by the number it points to, then negates that number. So, after one step, it would move forward `2` cells, and turn the `2` into a `-2`:

```
-2 h 1 -1
     ^

```

The Foo machine keeps doing this until the instruction pointer is pointing to the halt symbol (`h`). So, here is the full execution of this program:

```
2 h 1 -1
^

-2 h 1 -1
     ^

-2 h -1 -1
         ^

-2 h -1 1
      ^

-2 h 1 1
   ^

```

The tape is also circular, so if the instruction pointer moves off of one side of the tape, it goes to the other side, e.g.:

```
3 h 1 3
^
-3 h 1 3
       ^
-3 h 1 -3
     ^
-3 h -1 -3
         ^
-3 h -1 3
 ^
3 h -1 3
  ^

```

One interesting thing about these Foo machines is that some do not halt, e.g.:

```
1 2 h 2
^
-1 2 h 2
   ^
-1 -2 h 2
        ^
-1 -2 h -2
    ^
-1 2 h -2
        ^
-1 2 h 2
   ^

```

This program will continue looping in those last four states forever.

So, write a program which determines if a Foo machine halts or not! You can use any (reasonable) input format you like for the Foo machines, and you can choose to use `0` as the halt symbol. You can use any two distinct outputs for the case where it does halt and the case where it doesn't. Your program must, of course, output an answer in a finite amount of time for all valid inputs.

This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so try to make your program as short as possible!

Test cases
----------

```
2 h 1 -1
Halts
3 h 1 3
Halts
h
Halts
1 1 1 1 h
Halts
2 1 3 2 1 2 h
Halts
3 2 1 1 4 h
Halts
1 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 h -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36
Halts

2 h
Does not halt
1 2 h 2
Does not halt
8 1 2 3 3 4 8 4 3 2 h
Does not halt
1 2 4 3 h 2 4 5 3
Does not halt
3 1 h 3 1 1
Does not halt
1 2 h 42
Does not halt

```