Problem: Given is a sequence of N digits a_1a_2\ldots a_N, where each element is 1, 2, or 3. Let x_{i,j} defined as follows:

* x_{1,j} := a_j \quad (1 \leq j \leq N)
* x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N and 1 \leq j \leq N+1-i)



Find x_{N,1}.

Constraints

* 2 \leq N \leq 10^6
* a_i = 1,2,3 (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:


N
a_1a_2\ldotsa_N


Output

Print x_{N,1}.

Examples

Input

4
1231


Output

1


Input

10
2311312312


Output

0

Solution (in PYTHON3):

Solution:
import sys

N = int(input())
S = input().strip()
ss = []
for c in S:
    ss.append(int(c))
if N == 2:
    print(abs(ss[0]-ss[1]))
    sys.exit()

X = []
X2 = []
fff = 0
for i in range(N-1):
    c = abs(ss[i] - ss[i+1])
    X.append(c%2)
    X2.append((c//2)%2)
    if c == 1:
        fff = 1


N=N-2

i = 0
Y = []
while N:
    if N%2:
        Y.append(i)
    i += 1
    N=N//2

C = [0]
for y in Y[::-1]:
    y = 2**y
#    print(y)
    tmp = []
    for c in C:
        tmp.append(c+y)
    for t in tmp:
        C.append(t)
r = 0
r2 = 0
for c in C:
    r = r^X[c]
    r2 = r2^X2[c]
if fff:
    print(r)
else:
    print(r2*2)