Multiply Pauli Matrices The Pauli matrices are a set of 2x2 matrices which appear very commonly in quantum physics (no, you don't need to know any quantum physics for this challenge). If we include the identity in the set, the four matrices are:

 σ0 =      σ1 =      σ2 =      σ3 = 
[1  0]    [0  1]    [0 -i]    [1  0]
[0  1]    [1  0]    [i  0]    [0 -1]


Multiplying two of these will always give another Pauli matrix, although it may be multiplied by one of the complex phases 1, i, -1, -i. For instance, σ1σ3 = -iσ2.

Your task is to multiply a number of Pauli matrices and return the resulting matrix and phase. Input will be given as a non-empty string of digits 0 to 3 representing the matrices σ0 to σ3. The output should be a string containing a single digit for the resulting matrix, optionally preceded by i, - or -i to indicate the phase (- is for -1).

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You must not use any built-in (or 3rd-party) features related to Pauli matrices.

This is code golf, the shortest answer (in bytes) wins.

Test Cases

1 =&gt; 1
13 =&gt; -i2
000 =&gt; 0
123 =&gt; i0
03022 =&gt; 3
02132230 =&gt; -i3
1320130100032 =&gt; i2
311220321030322113103 =&gt; -2
0223202330203313021301011023230323 =&gt; -i0
1323130203022111323321112122313213130330103202032222223 =&gt; -1
Python 2, 108 89 87 86 bytes

x=y=0
for m in map(int,raw_input()):x+=m*y and(m-y)%3*3/2;y^=m
print"--i"[~x%4::2]+`y`


(Thanks to @grc and @xnor for the help)

Explanation

Let's split up the coefficient and the base matrix. If we focus on the base matrix only, we get this multiplication table (e.g. 13 is -i2, so we put 2):

  0123

0 0123
1 1032
2 2301
3 3210


which just happens to be the same thing as doing bitwise xor.

Now let's focus on the coefficients. If we let 0123 denote 1,i,-1,-i respectively, we get:

  0123

0 0000
1 0031
2 0103
3 0310


For this we first check if either number is 0 by doing m*y, taking care of the left column and top row. Adding in (m-y)%3 then gives:

  0123

0 0000
1 0021
2 0102
3 0210


which is close, except that we have 2 instead of 3. We account for this by performing *3/2.

For indexing, we notice that if we take the string "--i" and select every second character starting from indices 0123 we get "-i","-","i","".