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:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = input().rstrip('\n')
    A = [int(a) for a in A]

    A = [abs(A[i+1] - A[i]) for i in range(N-1)]
    flg = 1
    if 1 not in A:
        flg = 2
        A = [a // 2 for a in A]
    else:
        A = [a % 2 for a in A]
    idx = []
    N -= 1
    for j in range(N.bit_length()):
        if N>>j&1:
            M = 2**j
            X = N%(M*2)
            if not idx:
                idx = list(range(M))
            else:
                idx_new = [X-1 - x for x in idx]
                idx.extend(idx_new)
    ans = 0
    #print(A)
    #print(idx)
    for i in idx:
        ans ^= A[i]
    print(ans * flg)


if __name__ == '__main__':
    main()