AtCoder Grand Contest 043 - 123 Triangle

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

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
N = int(input())
a = input()

def myc(n):
	ret = 0
	while n % 2 == 0:
		ret += 1
		n //= 2
	return ret

def func(c):
	odd = 0
	count = 0
	if a[0] == c:
		count += 1
	if a[-1] == c:
		count += 1
	for i in range(1, N // 2):
		odd += myc(N - i) - myc(i)
		if a[i] == c and odd == 0:
			count += 1
		if a[-i - 1] == c and odd == 0:
			count += 1
	if N % 2 == 1:
		if a[N // 2] == c and odd + myc(N // 2 + 1) - myc(N // 2) == 0:
			count += 1
	return count % 2 == 0
if '2' in a:
	if func('2'):
		print(0)
	else:
		print(1)
elif func('3'):
	print(0)
else:
	print(2)


N = int(input())
S = input()
a = [int(s) - 1 for s in S]
from collections import defaultdict
r = 1
d = defaultdict(int)
while 2 ** r <= N:
	for i in range(1, N):
		if i * 2 ** r <= N:
			d[i * 2 ** r] += 1
		else:
			break
	r += 1

def calc(list_of_int):
	length = len(list_of_int)
	res = list_of_int[0]
	keisu = 0
	for (i, r) in zip(list_of_int[1:], range(N - 1)):
		keisu += d[N - r - 1] - d[r + 1]
		res = (res + (2 if keisu > 0 else 1) * i) % 2
	return res
if 1 in a:
	print(calc(a))
else:
	print(calc(list(map(lambda x: x // 2, a))) * 2)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, list(input().rstrip())))

def contains(n):
	t = n & -n
	return t.bit_length()

def solve1(A, D):
	is1 = False
	cmb_e = 0
	for (i, a) in enumerate(A):
		if a and cmb_e == 0:
			is1 = not is1
		cmb_e += contains(D - 1 - i) - contains(i + 1)
	return is1
B = [abs(A[i] - A[i + 1]) for i in range(N - 1)]
if 1 in set(B):
	C = [b % 2 for b in B]
	is1 = solve1(C, N - 1)
	print(1 if is1 else 0)
else:
	C = [b // 2 for b in B]
	is2 = solve1(C, N - 1)
	print(2 if is2 else 0)


n = int(input())
s = input()
a = [int(s[i]) - 1 for i in range(n)]
div = [0] * (n + 1)
for i in range(1, n + 1):
	div[i] += div[i - 1]
	x = i
	while not x & 1:
		x >>= 1
		div[i] += 1
XOR = 0
one = False
for i in range(n):
	one |= a[i] == 1
	if div[n - 1] <= div[i] + div[n - 1 - i]:
		XOR ^= a[i]
if XOR & 1:
	print(1)
elif one:
	print(0)
elif XOR & 2:
	print(2)
else:
	print(0)


import sys
input = sys.stdin.readline
import math
from collections import deque
from fractions import gcd
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')

def inputI():
	return int(input().strip())

def inputS():
	return input().strip()

def inputIL():
	return list(map(int, input().split()))

def inputSL():
	return list(map(str, input().split()))

def inputILs(n):
	return list((int(input()) for _ in range(n)))

def inputSLs(n):
	return list((input().strip() for _ in range(n)))

def inputILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def inputSLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def lcm(a, b):
	return a * b // gcd(a, b)
N = inputI()
s_ = list(inputS())
s = []
for i in range(len(s_) - 1):
	s.append(abs(int(s_[i]) - int(s_[i + 1])))
N = N - 1

def decode(s):
	N = len(s)
	news = []
	if set(s) != {0, 2}:
		for n in range(20):
			if N - 1 >> n & 1:
				d = pow(2, n)
				for i in range(N - d):
					news.append(abs(s[i] % 2 - s[i + d] % 2))
				break
	else:
		for n in range(20):
			if N - 1 >> n & 1:
				d = pow(2, n)
				for i in range(N - d):
					news.append(abs(s[i] - s[i + d]))
				break
	return news
while len(s) > 1:
	s = decode(s)
print(s[0])


import sys
N = int(input())
a = list(map(lambda x: int(x) - 1, list(input())))
all_odd = 0
kai = [0] * N
if 0 not in a and 1 not in a:
	print(0)
	sys.exit()
if 1 not in a and 2 not in a:
	print(0)
	sys.exit()
if 0 not in a and 2 not in a:
	print(0)
	sys.exit()
for k in range(1, N):
	count = 0
	p = k
	for _ in range(N):
		if p % 2 == 1:
			kai[k] = kai[k - 1] + count
			break
		p = p / 2
		count += 1
all_num = 0
for k in range(N):
	if kai[-1] == kai[k] + kai[N - 1 - k] and a[k] == 1:
		all_num += 1
if all_num % 2 == 1:
	print(1)
elif 1 in a:
	print(0)
else:
	for i in range(N):
		a[i] = a[i] / 2
	for k in range(N):
		if kai[-1] <= kai[k] + kai[N - 1 - k] and a[k] == 1:
			all_num += 1
	if all_num % 2 == 1:
		print(2)
	else:
		print(0)


import math
N = int(input())
a = list(map(int, list(input())))
x = []
while len(x) != 1:
	inx = 1 << math.floor(math.log2(N)) - 1
	N -= inx
	x = [0] * N
	for i in range(N):
		x[i] = abs(a[i] - a[i + inx])
	a = x
print(x[0])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left, bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil, pi, cos, radians, sqrt
from operator import itemgetter

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def LI2():
	return [int(input()) for i in range(n)]

def MXI():
	return [[LI()] for i in range(n)]

def SI():
	return input().rstrip()

def printns(x):
	print('\n'.join(x))

def printni(x):
	print('\n'.join(list(map(str, x))))
inf = 10 ** 17
mod = 10 ** 9 + 7
n = I()
s = list(map(int, SI()))
if n == 1:
	print(s[0])
	sys.exit()

def divi2(x):
	if x % 2 == 1:
		return 0
	else:
		count = 0
		while x % 2 == 0:
			x //= 2
			count += 1
		return count
pw2 = [0 for i in range(n - 1)]
for i in range(n - 1):
	if i % 2 == 1:
		pw2[i] = divi2(i + 1)
cmbnk2 = [0 for i in range(n)]
for i in range(n - 1):
	cmbnk2[i + 1] = cmbnk2[i] + pw2[n - 2 - i] - pw2[i]
ans = 0
if not 2 in s:
	for i in range(n):
		s[i] = (s[i] - 1) // 2
	for i in range(n):
		if cmbnk2[i] == 0:
			ans += s[i] % 2
	if ans % 2 == 0:
		print(0)
	else:
		print(2)
	sys.exit()
else:
	for i in range(n):
		if cmbnk2[i] == 0:
			ans += s[i] % 2
print(ans % 2)


def popcount_parity(x, a):
	x ^= x >> 2
	x ^= x >> 4
	x ^= x >> 8
	x ^= x >> 16
	x ^= x >> 32
	x ^= x >> 64
	x ^= x >> 128
	x ^= x >> 256
	x ^= x >> 512
	x ^= x >> 1024
	x ^= x >> 2048
	x ^= x >> 4096
	x ^= x >> 8192
	x ^= x >> 16384
	x ^= x >> 32768
	x ^= x >> 65536
	x ^= x >> 131072
	x ^= x >> 262144
	x ^= x >> 524288
	x ^= x >> 1048576
	return x & a

def include_2(a):
	x = ~a & a >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	x |= x >> 32
	x |= x >> 64
	x |= x >> 128
	x |= x >> 256
	x |= x >> 512
	x |= x >> 1024
	x |= x >> 2048
	x |= x >> 4096
	x |= x >> 8192
	x |= x >> 16384
	x |= x >> 32768
	x |= x >> 65536
	x |= x >> 131072
	x |= x >> 262144
	x |= x >> 524288
	x |= x >> 1048576
	return x & 1
N = int(input()) - 1 << 1
s = 1
while N:
	l = N & -N
	s |= s << l
	N ^= l
a = int(input(), 4)
if include_2(a):
	print(popcount_parity(~a & s, 1))
else:
	print(popcount_parity(a & s << 1, 2))


N = int(input())
A = list(map(lambda a: int(a) - 1, input()))
prd = 1
if all((a % 2 == 0 for a in A)):
	prd = 2
	A = [a // 2 for a in A]
ans = 0
for i in range(N):
	if N - 1 & i == i:
		ans ^= A[i] % 2
print(prd * ans)


N = int(input())
a = list(map(int, list(input())))
t = [0 for i in range(N + 1)]
i = 2
while i < N:
	for j in range(i, N + 1, i):
		t[j] += 1
	i *= 2
sum_t = [0]
for i in range(1, N + 1):
	sum_t.append(sum_t[-1] + t[i])
x = [max(a[i], a[i + 1]) - min(a[i], a[i + 1]) for i in range(N - 1)]

def isCombOdd(n, k):
	bunshi = sum_t[n] - sum_t[n - k]
	bunbo = sum_t[k]
	return bunshi == bunbo
f1 = False
for n in x:
	if n == 1:
		f1 = True
		break
if f1:
	x = [n if n != 2 else 0 for n in x]
candidate = 1 if f1 else 2
ans = 0
for i in range(N - 1):
	if x[i] > 0 and isCombOdd(N - 2, i):
		ans = 1 - ans
print(0 if ans == 0 else candidate)


N = int(input())
A = [int(a) - 1 for a in input()]
print(sum([A[i] for i in range(N) if N - 1 & i == i]) % (4 >> int(1 in A)))


N = int(input())
A = [int(a) - 1 for a in input()]
r = 1 if 1 in A else 2
print(sum([1 if A[i] & r and N - 1 & i == i else 0 for i in range(N)]) % 2 * r)


def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	N = I()
	a2 = input()
	a = []
	for i in range(len(a2)):
		a.append(int(a2[i]))

	def calc(L):
		L1 = list(L)
		nL = len(L)
		if nL % 2 == 1 or nL <= 5000:
			for i in range(nL - 1):
				L1[i] = abs(L[i] - L[i + 1])
			L1.pop()
			return L1
		else:
			L2 = []
			for i in range(0, nL, 2):
				L2.append(abs(L[i] - L[i + 1]))
			return L2
	while len(a) != 1:
		a = calc(a)
	print(a[0])
main()


n = int(input())
a = input()
fac2 = [0] * (n + 1)
i = 2
while i <= n:
	for j in range(i, n + 1, i):
		fac2[j] += 1
	i *= 2
for i in range(1, n + 1):
	fac2[i] += fac2[i - 1]

def calc(x):
	len_x = len(x)
	res = 0
	for (i, xi) in enumerate(x):
		if fac2[len_x - 1] - fac2[len_x - 1 - i] - fac2[i] > 0:
			continue
		res = res ^ xi
	return res
if a.count('2') == 0:
	x = []
	for ai in a:
		x.append(int(ai) // 2)
	res = calc(x)
	if res == 0:
		print(0)
	else:
		print(2)
else:
	x = []
	for ai in a:
		x.append((int(ai) - 1) % 2)
	res = calc(x)
	print(res)


import sys
n = int(input())
s = input()
frac = [0] * (n + 1)
for i in range(1, n + 1):
	k = i
	frac[i] = frac[i - 1]
	while k % 2 == 0:
		k //= 2
		frac[i] += 1
ans = 0
for i in range(n):
	if int(s[i]) == 2 and frac[n - 1] - frac[i] - frac[n - 1 - i] == 0:
		ans ^= 1
if ans == 1:
	print(1)
elif '2' in s:
	print(0)
else:
	ans = 0
	for i in range(n):
		if int(s[i]) == 3 and frac[n - 1] - frac[i] - frac[n - 1 - i] == 0:
			ans ^= 1
	print(ans * 2)


import sys
input = sys.stdin.readline

def pr2(x):
	ret = 0
	while x % 2 == 0:
		ret += 1
		x //= 2
	return ret
n = int(input())
s = input()
x = []
flg = 0
if s.count('2') >= 1:
	for i in range(n - 1):
		t = abs(int(s[i + 1]) - int(s[i]))
		x.append(t % 2)
else:
	flg = 1
	for i in range(n - 1):
		t = abs(int(s[i + 1]) - int(s[i]))
		x.append(t // 2)
n -= 1
num2 = 0
ans = 0
for i in range(n):
	if i == 0:
		ans += x[i]
		continue
	num2 += pr2(n - i) - pr2(i)
	if num2 > 0:
		continue
	else:
		ans += x[i]
if ans % 2:
	print(flg + 1)
else:
	print(0)


import math
n = int(input())
alist = input()
blist = []
swit = 0
for i in range(n - 1):
	now = abs(int(alist[i + 1]) - int(alist[i]))
	if now == 1:
		swit = 1
	blist.append(now)
if swit == 1:
	for i in range(n - 1):
		if blist[i] == 2:
			blist[i] = 0
else:
	for i in range(n - 1):
		if blist[i] == 2:
			blist[i] = 1
dekai = 100
while len(blist) > 1:
	clist = []
	dekai = math.floor(math.log(len(blist), 2))
	katamari = 2 ** dekai
	kosu = len(blist) - katamari + 1
	nanko = 0
	for i in range(katamari):
		if blist[i] == 1:
			nanko += 1
	clist.append(nanko % 2)
	for i in range(kosu - 1):
		nanko += blist[katamari + i] - blist[i]
		clist.append(nanko % 2)
	blist = clist
if swit == 1:
	print(blist[0])
else:
	print(blist[0] * 2)


def solve_base(n, a_list):
	factorial_count_2 = [0] * n
	for i in range(1, n):
		p = i
		cnt = 0
		while p % 2 == 0:
			p = p // 2
			cnt += 1
		factorial_count_2[i] = factorial_count_2[i - 1] + cnt
	mod_2 = 0
	for i in range(n):
		if factorial_count_2[n - 1] == factorial_count_2[i] + factorial_count_2[n - 1 - i]:
			mod_2 += a_list[i] % 2
			mod_2 %= 2
	return mod_2

def solve(n, a_list):
	if 2 in a_list:
		return solve_base(n, a_list)
	else:
		return 2 * solve_base(n - 1, [abs(a_list[i] - a_list[i + 1]) // 2 for i in range(n - 1)])

def main():
	n = int(input())
	a_list = list(map(int, list(input())))
	res = solve(n, a_list)
	print(res)

def test():
	assert solve(4, [1, 2, 3, 1]) == 1
	assert solve(10, [2, 3, 1, 1, 3, 1, 2, 3, 1, 2]) == 0
test()
main()


n = int(input())
al = list(input())
al = [int(a) - 1 for a in al]
flag = False
if 1 not in al:
	flag = True
	al = [a // 2 for a in al]
else:
	al = [a if a != 2 else 0 for a in al]
countl = [0]
a = 0
for i in range(1, n + 1):
	while i % 2 == 0:
		a += 1
		i //= 2
	countl.append(a)

def comb(a, b):
	if countl[a] - countl[a - b] - countl[b] > 0:
		return 0
	else:
		return 1
ans = 0
for (idx, a) in enumerate(al):
	if a == 1:
		ans += comb(n - 1, idx)
if ans % 2 == 0:
	print(0)
elif flag:
	print(2)
else:
	print(1)


import sys
N = int(input()) - 1
two = False
S = 0
for i in range(N + 1):
	a = int(sys.stdin.read(1))
	if not two:
		two = a == 2
	if i & N == i:
		S ^= a - 1
if two:
	S &= ~2
print(S)


n = int(input())
string = input()
a = []
a_01 = []
a_02 = []
bit_1 = 0
for i in range(n):
	a.append(int(string[i]) - 1)
	a_01.append((int(string[i]) - 1) % 2)
	a_02.append((int(string[i]) - 1) // 2)
	if int(string[i]) - 1 == 1:
		bit_1 = 1
num_lst = [0 for i in range(n)]
for i in range(1, n):
	p = i
	cnt = 0
	while p % 2 == 0:
		p = p / 2
		cnt += 1
	num_lst[i] = cnt
n_1Ci = [0 for i in range(n)]
for i in range(1, n):
	n_1Ci[i] = n_1Ci[i - 1] + num_lst[n - i] - num_lst[i]
cnt_01 = [0, 0]
for i in range(n):
	cnt_01[a_01[i]] += 1 if n_1Ci[i] == 0 else 0
if cnt_01[1] % 2 == 1:
	print(1)
	exit()
if bit_1 == 1:
	print(0)
	exit()
cnt_02 = [0, 0]
for i in range(n):
	cnt_02[a_02[i]] += 1 if n_1Ci[i] == 0 else 0
if cnt_02[1] % 2 == 1:
	print(2)
else:
	print(0)


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

def LI():
	return list(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, input().split()))

def II():
	return int(input())

def IF():
	return float(input())

def LS():
	return list(map(list, input().split()))

def S():
	return list(input().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = 10000000000.0

def solve():
	n = II()
	a = list(map(lambda x: int(x) - 1, S()))
	ans = 1
	if not 1 in a:
		ans *= 2
		for i in range(n):
			a[i] >>= 1
	res = 0
	for i in range(n):
		if n - 1 & i == i:
			res ^= a[i] & 1
	print(res * ans)
	return
solve()


import sys
n = int(input())
a = list(input())
A = []
for i in range(n):
	a[i] = int(a[i]) - 1
	A.append(a[i] % 2)
xorct = 0
for i in range(n):
	if n - 1 == i | n - 1 - i:
		xorct ^= A[i]
if xorct == 1:
	print(1)
	sys.exit()
if 1 in a:
	print(0)
	sys.exit()
for i in range(n):
	a[i] = a[i] // 2
xorct = 0
for i in range(n):
	if n - 1 == i | n - 1 - i:
		xorct ^= a[i]
if xorct == 1:
	print(2)
	sys.exit()
print(0)


n = int(input())
s = input()
a = [int(s[i]) - 1 for i in range(n)]
div = [0] * (n + 1)
for i in range(1, n + 1):
	div[i] += div[i - 1]
	x = i
	while not x & 1:
		x >>= 1
		div[i] += 1
XOR = 0
for i in range(n):
	if div[n - 1] <= div[i] + div[n - 1 - i]:
		XOR ^= a[i]
if XOR & 1:
	print(1)
	exit(0)
for i in a:
	if i == 1:
		print(0)
		exit(0)
XOR = 0
for i in range(n):
	if div[n - 1] <= div[i] + div[n - 1 - i]:
		XOR ^= a[i] >> 1
if XOR & 1:
	print(2)
	exit(0)
print(0)


def even_or_odd(a):
	ans = a[0] % 2
	for i in range(1, N):
		ans ^= int(N - 1 & i == i) & a[i]
	return ans
N = int(input())
a = [x - 1 for x in list(map(int, list(input())))]
if even_or_odd([x % 2 for x in a]) == 1:
	print(1)
elif 1 in a:
	print(0)
elif even_or_odd([x // 2 for x in a]) == 1:
	print(2)
else:
	print(0)


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
n = I()
a = input()
a = list(map(lambda x: int(x) - 1, list(a)))
b = [0 if i % 2 == 0 else i for i in a]
cnt = 0
for i in range(n):
	if b[i] % 2:
		if n - 1 & i == i:
			cnt += 1
if cnt % 2:
	print(1)
elif 1 in b:
	print(0)
else:
	c = [i // 2 if i % 2 == 0 else i for i in a]
	cnt = 0
	for i in range(n):
		if c[i] % 2:
			if n - 1 & i == i:
				cnt += 1
	if cnt % 2:
		print(2)
	else:
		print(0)


N = int(input())
div2_num = [0]
for i in range(1, N + 1):
	cnt = 0
	while i % 2 == 0:
		cnt += 1
		i //= 2
	div2_num.append(div2_num[-1] + cnt)

def EO_nCr(n, r):
	if div2_num[n] - (div2_num[n - r] + div2_num[r]) > 0:
		return 0
	else:
		return 1
A = list(map(int, list(input())))
a = []
for i in range(N - 1):
	a.append(abs(A[i] - A[i + 1]))
if 1 not in a:
	for i in range(N - 1):
		a[i] = a[i] // 2
	lastk = 2
else:
	lastk = 1
ans = 0
for i in range(N - 1):
	ans ^= a[i] % 2 * EO_nCr(N - 2, i)
print(ans * lastk)


N = int(input())
A = [int(a) - 1 for a in input()]
r = 2 - (1 in A)
print(sum([A[i] & r and N - 1 & i == i for i in range(N)]) % 2 * r)


import sys
input = sys.stdin.readline
N = int(input())
A = list(input().rstrip())

def two_num(x):
	res = 0
	while x % 2 == 0:
		x //= 2
		res += 1
	return res
C_twos = [0] * N
for i in range(1, N):
	res = C_twos[i - 1] + two_num(N - i) - two_num(i)
	C_twos[i] = res
if '2' in A:
	ans = 0
	for i in range(N):
		ans ^= int(A[i]) - 1 & 1 * (C_twos[i] == 0)
	print(ans)
else:
	ans = 0
	for i in range(N):
		ans ^= (int(A[i]) - 1) // 2 * (C_twos[i] == 0)
	print(ans * 2)


N = int(input())
a = list(map(int, input()))
if N == 2:
	print(abs(a[0] - a[1]))
	exit()
a1 = [abs(a[i] - a[i + 1]) for i in range(N - 1)]
if 1 in a1:
	s = 0
	for i in range(len(a1)):
		if len(a1) - 1 | i == len(a1) - 1:
			s += a1[i] % 2
	print(s % 2)
else:
	s = 0
	for i in range(len(a1)):
		if len(a1) - 1 | i == len(a1) - 1:
			s += a1[i] // 2
	print(s % 2 * 2)


N = int(input())
A = [int(a) - 1 for a in input()]
b = 1 if 1 in A else 2
ans = 0
for (i, a) in enumerate(A):
	if N - 1 & i == i and a ^ b == 0:
		ans ^= b
print(ans)


n = int(input())
a = input()
a2 = [int(a[i]) for i in range(n)]
n2 = bin(n)
b = [0] * n
c = [1] * 2 ** (len(n2) - 3)
for i in range(len(c)):
	b[i] += c[i]
temp = len(n2) - 4
count = len(c)
while temp >= 0:
	if n2[-1 - temp] == '1':
		c = [b[i] for i in range(count)]
		for i in range(count):
			b[i + 2 ** temp] += c[i]
		count += 2 ** temp
	temp -= 1
e = [b[i] % 2 for i in range(len(b))]
d = 0
for i in range(n):
	if e[i] % 2 == 1:
		d += a2[i]
if d % 2 == 1:
	print(1)
else:
	a3 = [abs(a2[i] - a2[i + 1]) for i in range(n - 1)]
	if 1 in a3:
		print(0)
	else:
		n3 = bin(n - 1)
		b = [0] * (n - 1)
		c = [1] * 2 ** (len(n3) - 3)
		for i in range(len(c)):
			b[i] += c[i]
		temp = len(n3) - 4
		count = len(c)
		while temp >= 0:
			if n3[-1 - temp] == '1':
				c = [b[i] for i in range(count)]
				for i in range(count):
					b[i + 2 ** temp] += c[i]
				count += 2 ** temp
			temp -= 1
		e = [b[i] % 2 for i in range(len(b))]
		d = 0
		for i in range(n - 1):
			if e[i] % 2 == 1:
				d += a3[i]
		if d % 4 == 0:
			print(0)
		else:
			print(2)


n = int(input())
arr = list(input())
arr = [int(arr[i]) for i in range(n)]
if n == 1:
	print(arr[0])
if n == 2:
	print(abs(arr[0] - arr[1]))
else:
	tmp = []
	for i in range(n - 2):
		tmp.append(abs(abs(arr[i] - arr[i + 1]) - abs(arr[i + 1] - arr[i + 2])))
	arr = tmp
	while len(arr) > 3:
		tmp = []
		if len(arr) % 2 == 0:
			for i in range(len(arr) // 2):
				tmp.append(abs(arr[2 * i] - arr[2 * i + 1]))
		else:
			for i in range(len(arr) - 1):
				tmp.append(abs(arr[i] - arr[i + 1]))
		arr = tmp
	if len(arr) == 1:
		print(arr[0])
	elif len(arr) == 2:
		print(abs(arr[0] - arr[1]))
	elif len(arr) == 3:
		print(abs(abs(arr[0] - arr[1]) - abs(arr[1] - arr[2])))


def main():
	n = int(input())
	a = list(map(lambda x: int(x) - 1, list(input())))
	b = [i % 2 for i in a]

	def all_a(x):
		ans = 0
		for (j, i) in enumerate(x):
			ans ^= (n - 1 | j == n - 1) * i
		return ans
	all_b = all_a(b)
	if all_b == 1:
		print(1)
		return
	if 1 in a:
		print(0)
		return
	b = [i // 2 for i in a]
	print(all_a(b) * 2)
main()


def pascal_parity(N):
	if N & -N == N:
		return [1] * N
	else:
		n = N - (1 << N.bit_length() - 1)
		p = pascal_parity(n)
		return p + [0] * (N - 2 * n) + p
N = int(input())
A = list(map(lambda x: int(x) - 1, input()))
P = pascal_parity(N)
if 1 in A:
	if sum((a * p for (a, p) in zip(A, P))) % 2 == 1:
		print(1)
	else:
		print(0)
else:
	pa = 0
	for (p, a) in zip(P, A):
		if p == 1 and a == 2:
			pa += 1
	if pa % 2 == 1:
		print(2)
	else:
		print(0)


import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
fact2 = [0] * 1000011

def cnt2(n):
	if n % 2 == 1:
		return 0
	else:
		fact2[n] = 1 + fact2[n // 2]
		return fact2[n]
factorial = [0, 0]
for i in range(2, 1000010):
	factorial.append(factorial[-1] + cnt2(i))

def nck(n, k):
	return factorial[n] - factorial[k] - factorial[n - k]

def nxor(x, n):
	if n > 0:
		return 0
	else:
		return x

def main():
	n = int(input())
	a = [int(i) - 1 for i in list(input())]
	cumxor = 0
	amod = [i % 2 for i in a]
	for i in range(n):
		cumxor ^= nxor(amod[i], nck(n - 1, i))
	if cumxor == 1:
		ans = 1
	elif 1 in a:
		ans = 0
	else:
		cumxor = 0
		adiv = [i // 2 for i in a]
		for i in range(n):
			cumxor ^= nxor(adiv[i], nck(n - 1, i))
		if cumxor == 0:
			ans = 0
		else:
			ans = 2
	print(ans)
main()


N = int(input())
A = [int(a) for a in input()]

def pascal_parity(n):

	def cnt2(m):
		a = m & -m
		return a.bit_length() - 1
	S = [0] * (n + 1)
	for i in range(1, n):
		S[i] = S[i - 1] + cnt2(n + 1 - i) - cnt2(i)
	return [1 if s == 0 else 0 for s in S]

def calc(L):
	return [abs(L[i] - L[i - 1]) for i in range(1, len(L))]

def calc_all(L):
	for i in range(len(L) - 1):
		L = calc(L)
	return L[0]
if N <= 5:
	print(calc_all(A))
else:
	A = calc(A)
	pp = pascal_parity(N - 2)
	s = sum([a * pp[i] for (i, a) in enumerate(A)])
	if 1 in A:
		print(s % 2)
	else:
		print(s % 4)


def is_odd_binomial(n, m):
	return ~n & m == 0
N = int(input())
a = list(map(lambda x: int(x) - 1, input()))
parity = sum((a[i] for i in range(N) if is_odd_binomial(N - 1, i)))
if parity % 2 == 1:
	ans = 1
elif 1 in a:
	ans = 0
elif parity % 4 == 2:
	ans = 2
else:
	ans = 0
print(ans)


import sys
import random
input = sys.stdin.readline

def solve(n, s):
	sub = [int(s[i]) - 1 for i in range(n)]
	table = [0] * (n + 1)
	p = 2
	for i in range(len(bin(n)) - 1):
		for j in range(p, n + 1, p):
			table[j] += 1
		p *= 2
	for i in range(n):
		table[i + 1] += table[i]
	ans = 0
	for i in range(n):
		if sub[i] % 2:
			judge = table[n - 1] - table[n - 1 - i] - table[i]
			if not judge:
				ans += 1
	if ans % 2:
		res = 1
	elif 1 in sub:
		res = 0
	else:
		res = 0
		for i in range(n):
			if sub[i]:
				judge = table[n - 1] - table[n - 1 - i] - table[i]
				if not judge:
					res += 1
		return res % 2 * 2
	return res

def main():
	n = int(input())
	s = input()
	ans = solve(n, s)
	print(ans)
main()


import sys

def main():
	N = int(input())
	a = input()
	nl = []
	for num in a:
		num = int(num)
		nl.append(num - 1)
	if 1 in nl:
		cnt = 0
		for (i, num) in enumerate(nl):
			cnt += num * (N - 1 == i | N - 1 - i)
		print(cnt % 2)
	else:
		for i in range(N):
			nl[i] //= 2
		cnt = 0
		for (i, num) in enumerate(nl):
			cnt += num * (N - 1 == i | N - 1 - i)
		print(cnt % 2 * 2)
main()


def Lucas(n, k):
	if n & k == k:
		return 1
	else:
		return 0
n = int(input())
a = list(map(int, list(input())))
odd = 0
cnt = 0
for i in range(n):
	a[i] -= 1
	if a[i] == 1:
		odd += Lucas(n - 1, i)
		cnt = 1
if odd % 2 == 1:
	print(1)
elif cnt == 1:
	print(0)
else:
	for i in range(n):
		a[i] //= 2
		if a[i] == 1:
			odd += Lucas(n - 1, i)
	print(odd % 2 * 2)


import math
import fractions

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def ValueToBits(x, digit):
	res = [0 for i in range(digit)]
	now = x
	for i in range(digit):
		res[i] = now % 2
		now = now >> 1
	return res

def BitsToValue(arr):
	n = len(arr)
	ans = 0
	for i in range(n):
		ans += arr[i] * 2 ** i
	return ans

def ValueToArray10(x, digit):
	ans = [0 for i in range(digit)]
	now = x
	for i in range(digit):
		ans[digit - i - 1] = now % 10
		now = now // 10
	return ans

def cmb(n, r, p):
	if r < 0 or n < r:
		return 0
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % p
p = 2
N = 10 ** 5 + 2
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
	fact.append(fact[-1] * i % p)
	inv.append(-inv[p % i] * (p // i) % p)
	factinv.append(factinv[-1] * inv[-1] % p)
n = int(input())
s = input()
a = []

def is2(n, r):
	if n == r | n - r:
		return 1
	else:
		return 0
non1 = 1
for i in range(n):
	a.append(int(s[i]) - 1)
	if a[i] == 1:
		non1 = 0
total = 0
if non1 == 0:
	for i in range(n):
		total += is2(n - 1, i) * (a[i] % 2)
	print(total % 2)
else:
	for i in range(n):
		total += is2(n - 1, i) * (a[i] // 2)
	print(total % 2 * 2)


n = int(input())
a = list(map(lambda x: int(x) - 1, input()))
ans = 0
for i in range(n):
	if n - 1 & i == i:
		ans += a[i]
if ans % 2 == 1:
	print(1)
elif a.count(1) != 0:
	print(0)
else:
	ans = 0
	b = list(map(lambda x: x // 2, a))
	for i in range(n):
		if n - 1 & i == i:
			ans += b[i]
	if ans % 2 == 1:
		print(2)
	else:
		print(0)


N = int(input()) - 1
a = input()
l = [None] * N
for i in range(N):
	l[i] = abs(int(a[i + 1]) - int(a[i]))
for i in range(19, 0, -1):
	if N > 2 ** i:
		t = 2 ** i
		N -= t
		lb = [None] * N
		for i in range(N):
			if l[i + t // 2] == 1 and l[i] + l[i + t] == 2:
				lb[i] = 0
			else:
				lb[i] = abs(l[i] - l[i + t])
		l = lb
if len(l) == 1:
	print(l[0])
else:
	print(abs(l[0] - l[1]))


n = int(input())
a = input()
b = []
att = 1
for i in range(n):
	b.append(int(a[i]) - 1)
for i in range(n):
	if b[i] % 2 == 1:
		break
else:
	att = 2
	for i in range(n):
		b[i] //= 2
for i in range(n):
	if b[i] == 2:
		b[i] = 0
pre = [0 for _ in range(10 ** 6)]
now = 2
while now < 10 ** 6 + 5:
	for k in range(10 ** 6):
		try:
			pre[k * now] += 1
		except:
			now *= 2
			break
nm = [0]
for i in range(1, n):
	nm.append(nm[-1] - pre[i] + pre[n - i])
for i in range(n):
	if nm[i]:
		nm[i] = 0
	else:
		nm[i] = 1
ans = 0
for i in range(n):
	ans ^= b[i] * nm[i]
print(ans * att)


def comb(n, r):
	return n == r | n - r
N = int(input())
S = input()
x = 0
b = 1
for i in range(N):
	s = int(S[i]) % 2
	x = (x + s * comb(N - 1, i)) % 2
	b *= s % 2
if x % 2 or b == 0:
	print(x % 2)
	exit()
x = 0
for i in range(N):
	s = int(S[i]) // 2 % 2
	x = (x + s * comb(N - 1, i)) % 2
print(x % 2 * 2)


import sys

def main():
	input = sys.stdin.readline
	N = int(input())
	iS = input().rstrip()
	S = []
	for i in range(N - 1):
		S.append(abs(int(iS[i]) - int(iS[i + 1])))
	N -= 1
	f = FactorialUtils(N)
	n1 = n2 = 0
	for i in range(N):
		t = f.choose(N - 1, i)
		if S[i] == 1:
			n1 += t
		elif S[i] == 2:
			n2 += t
	if n1 & 1 and n2 & 1:
		print(1)
	elif n1 & 1:
		print(1)
	elif n2 & 1 and n1 == 0:
		print(2)
	else:
		print(0)

class FactorialUtils:

	def __init__(self, n):
		self.fac = [1] * (n + 1)
		for i in range(2, n + 1):
			self.fac[i] = self.fac[i - 1] + (i & -i).bit_length()

	def choose(self, n, r):
		if r < 0 or r > n:
			return 0
		return 2 if self.fac[n] - self.fac[n - r] - self.fac[r] > 0 else 1
main()


import sys

def solve(N: int, a: str):
	a = [int(a[i]) - 1 for i in range(N)]
	zeroone = [a[i] % 2 for i in range(N)]
	SUM = 0
	comb = [0] * N
	comb[0] = 1
	for i in range(1, N):
		comb[i] = 1 if N - 1 & i == i else 0
	for i in range(N):
		SUM += zeroone[i] * comb[i]
	SUM %= 2
	if SUM == 1:
		print(1)
		return
	if 1 in a:
		print(0)
		return
	zerotwo = [a[i] // 2 for i in range(N)]
	SUM = 0
	for i in range(N):
		SUM += zerotwo[i] * comb[i]
	SUM %= 2
	if SUM == 1:
		print(2)
		return
	print(0)
	return

def main():
	N = int(input())
	a = input()
	solve(N, a)
main()


N = int(input())
S = ''.join([str(int(d) - 1) for d in input()])

def solve01(s):
	ans = 0
	for (k, d) in enumerate(s):
		if k & N - 1 == k:
			ans ^= int(d)
	return ans
if '1' in S:
	print(solve01(S.replace('2', '0')))
else:
	print(solve01(S.replace('2', '1')) * 2)


n = int(input())
a = [int(x) - 1 for x in input()]
am = [a[i] % 2 for i in range(n)]
tmp = 0
ans = am[0] % 2
for i in range(1, n):
	ind = 0
	k = n - i & -(n - i)
	while k > 1:
		k = k // 2
		ind += 1
	kk = i & -i
	while kk > 1:
		kk = kk // 2
		ind -= 1
	tmp += ind
	if tmp == 0:
		ans += am[i]
		ans %= 2
if ans == 1:
	print(1)
	exit()
if 1 in a:
	print(0)
else:
	b = [1 if a[i] == 2 else 0 for i in range(n)]
	tmp = 0
	ans = b[0] % 2
	for i in range(1, n):
		ind = 0
		k = n - i & -(n - i)
		while k > 1:
			k = k // 2
			ind += 1
		kk = i & -i
		while kk > 1:
			kk = kk // 2
			ind -= 1
		tmp += ind
		if tmp == 0:
			ans += b[i]
			ans %= 2
	if ans == 1:
		print(2)
	else:
		print(0)


N = int(input())
A = list(map(int, input()))
num = 0
for i in range(N):
	num += (N - 1 == i | N - 1 - i) * (-1) ** i * A[i]
if num % 2 == 1:
	print(1)
else:
	for i in range(N - 1):
		if abs(A[i] - A[i + 1]) == 1:
			print(0)
			break
	else:
		B = []
		for i in range(N - 1):
			if A[i] == A[i + 1]:
				B.append(0)
			else:
				B.append(1)
		for i in range(N - 1):
			num += (N - 2 == i | N - 2 - i) * (-1) ** i * B[i]
		if num % 2 == 1:
			print(2)
		else:
			print(0)


n = int(input())

def f(n, r):
	return n == r | n - r
s = list(map(int, list(input())))
b = []
for i in range(n - 1):
	b.append(abs(s[i] - s[i + 1]))
if 0 in b and len(set(b)) == 2 or len(set(b)) == 1:
	ans = 0
	anss = 0
	for i in range(n - 1):
		if b[i]:
			anss = b[i]
			ans += f(n - 2, i)
	if ans % 2 == 0:
		print(0)
	else:
		print(anss)
	quit()
ans = 0
for i in range(n - 1):
	if b[i] % 2 == 1:
		anss = b[i]
		ans += f(n - 2, i)
if ans % 2 == 0:
	print(0)
else:
	print(1)


N = int(input())
a = [int(i) - 1 for i in list(input())]

def solve(seq):
	if {0} == set(seq):
		return 0
	res = 0
	for k in range(N):
		tmp = 0
		if N - 1 & k == k:
			tmp = 1
		res += tmp * seq[k]
		res %= 2
	if res % 2 == 1:
		return 1
	if 1 in set(seq):
		return 0
	seq2 = [seq[i] // 2 for i in range(N)]
	return solve(seq2) * 2
print(solve(a))


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
	for i in idx:
		ans ^= A[i]
	print(ans * flg)
main()


n = int(input())
s = list(input())
ans = 0
if s.count('2') == 0:
	for i in range(n):
		if s[i] == '3':
			if n - 1 & i == i:
				ans += 1
	print(2 * (ans % 2))
else:
	for i in range(n):
		if s[i] == '2':
			if n - 1 & i == i:
				ans += 1
	print(ans % 2)


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
A = list(map(int, input()))
X = 2 in A
while len(A) > 1:
	if len(A) % 2 == 1:
		for i in range(len(A) - 1):
			A[i] = abs(A[i] - A[i + 1])
		A.pop()
	B = []
	for i in range(len(A) // 2):
		B.append(abs(A[i * 2] - A[i * 2 + 1]))
	A = B[:]
if X:
	A[0] %= 2
print(A[0])


def kezl(xlist):
	lenx = len(xlist)
	news = []
	for i in range(lenx - 1):
		news.append(abs(xlist[i + 1] - xlist[i]))
	return news
flist = []
import math
n = int(input())
alist = input()
blist = []
swit = 0
for i in range(n - 1):
	now = abs(int(alist[i + 1]) - int(alist[i]))
	if now == 1:
		swit = 1
	blist.append(now)
if swit == 1:
	for i in range(n - 1):
		if blist[i] == 2:
			blist[i] = 0
	dekai = 100
	while len(blist) > 1:
		clist = []
		dekai = math.floor(math.log(len(blist), 2))
		katamari = 2 ** dekai
		kosu = len(blist) - katamari + 1
		nanko = 0
		for i in range(katamari):
			if blist[i] == 1:
				nanko += 1
		clist.append(nanko % 2)
		for i in range(kosu - 1):
			nanko += blist[katamari + i] - blist[i]
			clist.append(nanko % 2)
		blist = clist
	print(blist[0])
else:
	for i in range(n - 1):
		if blist[i] == 2:
			blist[i] = 1
	dekai = 100
	while len(blist) > 1:
		clist = []
		dekai = math.floor(math.log(len(blist), 2))
		katamari = 2 ** dekai
		kosu = len(blist) - katamari + 1
		nanko = 0
		for i in range(katamari):
			if blist[i] == 1:
				nanko += 1
		clist.append(nanko % 2)
		for i in range(kosu - 1):
			nanko += blist[katamari + i] - blist[i]
			clist.append(nanko % 2)
		blist = clist
	print(blist[0] * 2)


def solve_for_01(nums):
	N = len(nums)
	ans = 0
	for (i, x) in enumerate(nums):
		if N - 1 & i == i:
			ans ^= x
	return ans

def main():
	N = int(input())
	A = list(map(lambda x: int(x) - 1, input()))
	if 1 in A:
		print(solve_for_01([a % 2 for a in A]))
	else:
		print(solve_for_01([a // 2 for a in A]) * 2)
main()


n = int(input())
l = [int(s) - 1 for s in input()]
if 1 in l:
	s = 0
	for (i, a) in enumerate(l):
		s += a * (n - 1 == i | n - 1 - i)
	print(s % 2)
else:
	l = [i // 2 for i in l]
	s = 0
	for (i, a) in enumerate(l):
		s += a * (n - 1 == i | n - 1 - i)
	print(s % 2 * 2)


N = int(input())
slist = input()

def fact_mod2(n, r):
	if n == r | n - r:
		return 1
	else:
		return 0
alist = []
for s in slist:
	alist.append(int(s) - 1)
parity = 0
for i in range(N):
	parity += fact_mod2(N - 1, i) * alist[i]
if parity % 2 == 1:
	print(1)
elif 1 in alist:
	print(0)
else:
	for i in range(N):
		alist[i] //= 2
	parity = 0
	for i in range(N):
		parity += fact_mod2(N - 1, i) * alist[i]
	if parity % 2 == 1:
		print(2)
	else:
		print(0)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, list(input().strip())))

def next(A):
	B = []
	for i in range(1, len(A)):
		B.append(abs(A[i] - A[i - 1]))
	return B
A = next(A)
if len(A) <= 3:
	while len(A) > 1:
		A = next(A)
	print(A[0])
	sys.exit()

def in2(x):
	if x == 0:
		return 0
	ANS = 0
	while x % 2 == 0:
		ANS += 1
		x //= 2
	return ANS
if not 1 in A:
	LEN = len(A)
	SUM = 0
	COMBI = 0
	for i in range(LEN):
		if COMBI == 0:
			SUM += A[i] // 2
		COMBI = COMBI + in2(LEN - 1 - i) - in2(i + 1)
	if SUM % 2 == 1:
		print(2)
	else:
		print(0)
else:
	LEN = len(A)
	SUM = 0
	COMBI = 0
	for i in range(LEN):
		if COMBI == 0:
			SUM += A[i]
		COMBI = COMBI + in2(LEN - 1 - i) - in2(i + 1)
	if SUM % 2 == 1:
		print(1)
	else:
		print(0)


n = int(input())
a = list(map(lambda x: int(x) - 1, list(input())))
memo = [-1] * (n + 1)

def log(x):
	if memo[x] != -1:
		return memo[x]
	ret = 0
	xx = x
	while x and x % 2 == 0:
		x //= 2
		ret += 1
	memo[xx] = ret
	return ret

def slv(n, a):
	v = a[0]
	if all((v == x for x in a)):
		return 0
	chk = 0
	tmppl = 0
	tmpmi = 0
	for i in range(n):
		x = a[i] % 2
		if tmppl > tmpmi:
			pass
		else:
			chk += a[i]
			chk %= 2
		tmppl += log(n - i - 1)
		tmpmi += log(i + 1)
	if chk:
		return 1
	if 1 in a:
		return 0
	a = [x // 2 for x in a]
	return slv(n, a) * 2
print(slv(n, a))


import math
N = int(input())
A = list(map(int, input()))
B = []
for i in range(N):
	if N - 1 == i | N - 1 - i:
		B.append(1)
	else:
		B.append(0)
b = 0
for i in range(N):
	b += B[i] * A[i]
if b % 2 == 1:
	print(1)
else:
	for i in range(N):
		if A[i] == 2:
			print(0)
			break
	else:
		c = 0
		for i in range(N):
			A[i] = (A[i] - 1) // 2
			c += B[i] * A[i]
		if c % 2 == 1:
			print(2)
		else:
			print(0)


N = int(input())
a = input()

def is_combination_odd(n, r):
	_n = n
	_r = r
	is_odd = True
	while _n > 0 and _r > 0:
		if _n % 2 < _r % 2:
			is_odd = False
			break
		_n >>= 1
		_r >>= 1
	return is_odd

def is_ans_odd(num_str: str) -> bool:
	is_odd = False
	for (i, c) in enumerate(num_str):
		is_c_odd = int(c) % 2
		is_odd ^= is_combination_odd(len(num_str) - 1, i) & is_c_odd
	return is_odd

def main():
	ans = -1
	table = str.maketrans({'1': '0', '2': '1', '3': '2'})
	a012 = a.translate(table)
	if is_ans_odd(a012):
		ans = 1
	elif '1' in a012:
		ans = 0
	else:
		table = str.maketrans({'2': '1'})
		a01 = a012.translate(table)
		if is_ans_odd(a01):
			ans = 2
		else:
			ans = 0
	print(ans)
main()


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
	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)


def popcount_parity(x):
	x ^= x >> 1
	x ^= x >> 2
	x ^= x >> 4
	x ^= x >> 8
	x ^= x >> 16
	x ^= x >> 32
	x ^= x >> 64
	x ^= x >> 128
	x ^= x >> 256
	x ^= x >> 512
	x ^= x >> 1024
	x ^= x >> 2048
	x ^= x >> 4096
	x ^= x >> 8192
	x ^= x >> 16384
	x ^= x >> 32768
	x ^= x >> 65536
	x ^= x >> 131072
	x ^= x >> 262144
	x ^= x >> 524288
	return x & 1
N = int(input()) - 1
s = 1
while N:
	l = N & -N
	s |= s << l
	N ^= l
A = input()
if '2' in A:
	a = int(A.replace('1', '0').replace('3', '0').replace('2', '1'), 2)
	print(popcount_parity(a & s))
else:
	a = int(A.replace('1', '0').replace('3', '1'), 2)
	print(popcount_parity(a & s) * 2)


def test(a):
	print(*a)
	for i in range(len(a) - 1):
		a = [abs(a1 - a0) for (a0, a1) in zip(a, a[1:])]
		print(*a)

def solve(n, aaa):
	if '2' not in aaa:
		factor = '3'
		effect = 2
	else:
		factor = '2'
		effect = 1
	try_list = []
	m = n - 1
	while m:
		l = 1 << m.bit_length() - 1
		m ^= l
		try_list.append((l, m))
	ans = 0
	for (i, a) in enumerate(aaa):
		if a == factor:
			for (l, m) in try_list:
				if i >= l:
					i -= l
				if i == 0:
					ans ^= effect
					break
				elif i > m:
					break
	return ans
n = int(input())
aaa = input()
print(solve(n, aaa))


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
read = sys.stdin.read
n = int(input())
a = [int(i) for i in input()]
n -= 1
d = [abs(i - j) for (i, j) in zip(a, a[1:])]
p2 = [0]
for i in range(1, n + 2):
	r = p2[-1]
	while i & 1 == 0:
		r += 1
		i >>= 1
	p2.append(r)

def choose(n, k):
	if p2[n] > p2[k] + p2[n - k]:
		return 0
	else:
		return 1
par = sum((choose(n - 1, i) * di for (i, di) in enumerate(d))) % 2
if par == 1:
	print(1)
elif 1 in d:
	print(0)
else:
	d = [di >> 1 for di in d]
	par = sum((choose(n - 1, i) * di for (i, di) in enumerate(d))) % 2
	if par == 0:
		print(0)
	else:
		print(2)


n = int(input())
a = input()
x = []
x.extend([int(i) for i in a])
if 2 in x:
	flag = True
	x = [1 if i == 2 else 0 for i in x]
else:
	flag = False
	x = [1 if i == 3 else 0 for i in x]
c = 0
n = len(x)
n_b = bin(n - 1)
if x[0] == 1:
	c += 1
for i in range(1, n - 1):
	tmp_nck = int(n - 1 == i | n - 1 - i)
	if x[i] == 1:
		c += tmp_nck
if x[n - 1] == 1:
	c += 1
if flag:
	print(c % 2)
elif c % 2 == 1:
	print(2)
else:
	print(0)


n = int(input())
a = list(map(lambda x: int(x) - 1, input()))
cnt = [0]
for i in range(1, n + 1):
	x = 0
	while i % 2 == 0:
		x += 1
		i //= 2
	cnt.append(cnt[-1] + x)

def comb(k):
	left = cnt[n - 1]
	right = cnt[k] + cnt[n - 1 - k]
	return left - right == 0
f = 1 in a
if f:
	a = [int(i == 1) for i in a]
else:
	a = [int(i == 2) for i in a]
ans = 0
for i in range(n):
	if comb(i):
		ans += a[i]
ans %= 2
if not f:
	ans *= 2
print(ans)


N = int(input())
a = list(map(int, list(input())))
while N != 0:
	digit = 1
	while digit < N // 2:
		digit *= 2
	x = []
	for i in range(digit, N):
		x.append(abs(a[i - digit] - a[i]))
	a = x
	N -= digit
	if len(x) == 1:
		break
print(a[0])


(n, a) = (int(input()) - 1, list(map(lambda x: int(x) - 1, list(input()))))
b = [i % 2 for i in a]

def c(x):
	a = 0
	for (j, i) in enumerate(x):
		a ^= (n | j == n) * i
	return a
if c(b):
	k = 1
elif 1 in a:
	k = 0
else:
	k = c([i // 2 for i in a]) * 2
print(k)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint
from copy import deepcopy
sys.setrecursionlimit(2147483647)
INF = 10 ** 20

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 2
n = I()
s = S()
l = len(s)
L = []
one_cnt = 0
for i in range(l - 1):
	ret = abs(int(s[i]) - int(s[i + 1]))
	L += [ret]
	if ret == 1:
		one_cnt += 1
m = 0
for j in range(l - 1):
	m += int(l - 2 & j == j) * L[j]
	m %= 2
if m % 2:
	print(1)
	exit()
elif one_cnt:
	print(0)
else:
	L = [k // 2 for k in L]
	ret2 = 0
	for jj in range(l - 1):
		ret2 += int(l - 2 & jj == jj) * L[jj]
		ret2 %= 2
	if ret2:
		print(2)
	else:
		print(0)


N = int(input())
A = [int(c) - 1 for c in input()]
x = 0
b = 1 if any((a == 1 for a in A)) else 2
for (k, a) in enumerate(A):
	p = int(N - 1 & k == k)
	if p and a ^ b == 0:
		x ^= b
print(x)


n = int(input())
a = list(map(int, input()))
if n <= 1:
	print(a[0])
	exit()
for i in range(n - 1):
	a[i] = abs(a[i + 1] - a[i])
a.pop()
n -= 1

def bc(u, v):
	return u & v == v

def solve(t):
	ans = 0
	for i in range(n):
		if a[i] == 1:
			ans ^= bc(n - 1, i)
	print(ans * t)
if 1 in a:
	solve(1)
else:
	for i in range(n):
		a[i] >>= 1
	solve(2)


import sys
import random
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
a = [int(ch) for ch in s]

def naive(a):
	c = a[:]
	while len(c) > 1:
		b = []
		for (c1, c2) in zip(c, c[1:]):
			b.append(abs(c1 - c2))
		c = b[:]
	return c[0]

def solve(a):
	c = a[:]
	while len(c) > 1:
		b = []
		if len(c) % 2 == 0:
			for (c1, c2) in zip(c[::2], c[1::2]):
				b.append(abs(c1 - c2))
		else:
			for (c1, c2) in zip(c, c[1:]):
				b.append(abs(c1 - c2))
		c = b[:]
	return c[0]
b = []
for (a1, a2) in zip(a, a[1:]):
	b.append(abs(a1 - a2))
if 1 not in b:
	tmp = []
	for item in b:
		if item == 2:
			tmp.append(1)
		else:
			tmp.append(0)
	ret = solve(tmp)
	if ret == 1:
		print(2)
	else:
		print(0)
else:
	tmp = []
	for item in b:
		if item == 2:
			tmp.append(0)
		else:
			tmp.append(item)
	ret = solve(tmp)
	print(ret)


N = int(input())
a = list(map(int, list(input())))
a = list(map(lambda x: x - 1, a))
x = 0
for (i, n) in enumerate(a):
	if n % 2 == 0:
		continue
	elif (N - 1 ^ i) & i == 0:
		x += 1
if x % 2 != 0:
	print(1)
elif 1 in a:
	print(0)
else:
	a = [x // 2 for x in a]
	x = 0
	for (i, n) in enumerate(a):
		if n % 2 == 0:
			continue
		elif N - 1 & i == i:
			x += 1
	if x % 2 != 0:
		print(2)
	else:
		print(0)


N = int(input())
a = list(map(int, list(input())))

def mod2_pascal(n):
	res = []
	for r in range(n + 1):
		res.append(1 if n == r | n - r else 0)
	return res
b = []
if N >= 3:
	for i in range(N - 1):
		b.append(abs(a[i] - a[i + 1]))
	mod2_line = mod2_pascal(N - 2)
	ans = 0
	for i in range(N - 1):
		if mod2_line[i] == 1:
			ans += b[i]
	if b.count(0) == N - 1 - b.count(2):
		b_divided_by_2 = list(map(lambda x: x // 2, b))
		for i in range(N - 1):
			if mod2_line[i] == 1:
				ans += b_divided_by_2[i]
		if ans % 2 == 1:
			print(2)
		else:
			print(0)
	else:
		print(ans % 2)
else:
	print(abs(a[1] - a[0]))


f2 = [0] * 10 ** 6
p2 = 2
while p2 < 10 ** 6:
	for i in range(p2, 10 ** 6, p2):
		f2[i] += 1
	p2 *= 2
for i in range(1, 10 ** 6):
	f2[i] += f2[i - 1]
n = int(input())
s = input()
p = '2' if '2' in s else '3'
ans = 0
for (i, c) in enumerate(s):
	if c == p:
		ans += 0 if f2[n - 1] - f2[i] - f2[n - 1 - i] else 1
print(int(p) - 1 if ans % 2 == 1 else 0)


def solve(*args: str) -> str:
	n = int(args[0])
	A = [ord(a) - 48 for a in args[1]]
	A = [abs(A[i] - A[i + 1]) for i in range(n - 1)]
	r = 2 if A.count(1) == 0 else 1
	ret = 0
	for i in range(n - 1):
		ret += A[i] // r * (n - 2 == i | n - 2 - i)
	return str(ret % 2 * r)
print(solve(*open(0).read().splitlines()))


N = int(input())
A = input()
S = [int(A[i]) - 1 for i in range(N)]
Lucas = [0 for i in range(N)]
D = {0: 1}
(base, m) = (1, N - 1)
while m != 0:
	if m % 2 == 1:
		L = [i for i in D]
		for i in L:
			D[i + base] = 1
	m //= 2
	base *= 2
for i in D:
	Lucas[i] = 1
oddness = 0
for i in range(N):
	if S[i] % 2 != 0:
		oddness += Lucas[i]
		oddness %= 2
if oddness == 1:
	print(1)
elif 1 in S:
	print(0)
else:
	S = [S[i] // 2 for i in range(N)]
	oddness = 0
	for i in range(N):
		if S[i] % 2 != 0:
			oddness += Lucas[i]
			oddness %= 2
	if oddness == 1:
		print(2)
	else:
		print(0)


N = int(input())
a = [int(s) - 1 for s in input()]
twos = {}
twos[0] = 0
for r in range(1, N):
	count = 0
	tmp = r
	while tmp % 2 == 0:
		tmp //= 2
		count += 1
	twos[r] = twos[r - 1] + count
ncr = {}
for r in range(N):
	if twos[N - 1] - twos[N - 1 - r] - twos[r] > 0:
		ncr[r] = 0
	else:
		ncr[r] = 1
oe = 0
for (r, ai) in enumerate(a):
	oe = (oe + ncr[r] * ai) % 2
if oe == 1:
	print(1)
elif 1 in a:
	print(0)
else:
	oe2 = 0
	for (r, ai) in enumerate(a):
		oe2 = (oe2 + ncr[r] * ai // 2) % 2
	if oe2 == 1:
		print(2)
	else:
		print(0)


n = int(input())
a = [int(t) - 1 for t in input()]
f = 1
if 1 not in a:
	a = [x // 2 for x in a]
	f = 2
s = sum([x for (i, x) in enumerate(a) if n - 1 & i == i])
print(s % 2 * f)


def ord(N, n):
	if n % N != 0:
		return 0
	else:
		return 1 + ord(N, n // N)
N = int(input())
A = input()
A = [int(A[i]) for i in range(0, N)]
X = [abs(A[i] - A[i + 1]) for i in range(0, N - 1)]
cmb = [0 for i in range(0, N - 1)]
cmb[0] = 0
for i in range(1, N - 1):
	cmb[i] = cmb[i - 1] + ord(2, N - 2 - (i - 1)) - ord(2, i)
data = [0 for i in range(0, N - 1)]
for i in range(0, N - 1):
	if cmb[i] > 0:
		data[i] = 0
	else:
		data[i] = 1
s = 0
for i in range(0, N - 1):
	s = (s + X[i] * data[i]) % 2
if s == 1:
	print(1)
elif 1 in X:
	print(0)
else:
	X = [X[i] // 2 for i in range(0, N - 1)]
	s = 0
	for i in range(0, N - 1):
		s = (s + X[i] * data[i]) % 2
	if s == 1:
		print(2)
	else:
		print(0)


import sys

def input():
	return sys.stdin.readline().rstrip()
N = int(input())
a = input()

def bit_count(i):
	res = 0
	while i > 0 and i & 1 == False:
		i >>= 1
		res += 1
	return res
f = [0]
for i in range(N // 2):
	f.append(f[-1] + bit_count(N - 1 - i) - bit_count(i + 1))

def nCr(n, r):
	if r > n - r:
		r = n - r
	if f[r] == 0:
		return 1
	else:
		return 0

def main():
	ans = 0
	for i in range(N):
		now = int(a[i]) - 1
		if now % 2:
			ans += now * (nCr(N - 1, i) % 2)
			ans %= 2
	if ans:
		return ans
	if '2' in a:
		return 0
	ans = 0
	for i in range(N):
		now = (int(a[i]) - 1) // 2
		if now % 2:
			ans += now * (nCr(N - 1, i) % 2)
			ans %= 2
	return ans * 2
print(main())


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().decode().rstrip()))

def pp(A, offset=0):
	s = ' ' * offset + ' '.join(map(str, A))
	print(s)

def test(A):
	i = 0
	while len(A) > 1:
		pp(A, i)
		A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
		i += 1
	pp(A, i)
	return A

def convert(counts):
	ret = []
	if counts[0][1] > 1:
		ret.append((0, counts[0][1] - 1))
	for ((n1, cnt1), (n2, cnt2)) in zip(counts, counts[1:]):
		ret.append((abs(n1 - n2), 1))
		if cnt2 > 1:
			ret.append((0, cnt2 - 1))
	n = None
	count = 0
	filtered = []
	for (a, cnt) in ret:
		if a != n:
			n = a
			count = 0
			filtered.append((n, 0))
		count += cnt
		filtered[-1] = (n, count)
	return filtered
cnt2 = []
cnt = 0
for n in range(N + 10):
	while n >= 2 and n % 2 == 0:
		n //= 2
		cnt += 1
	cnt2.append(cnt)
A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
if 1 in A:
	for i in range(len(A)):
		if A[i] == 2:
			A[i] = 0
mod = 2 if 1 in A else 4
ans = 0
n = len(A) - 1
for r in range(len(A)):
	cnt = cnt2[len(A) - 1] - cnt2[r] - cnt2[n - r]
	if cnt == 0:
		ans += A[r]
		ans %= mod
print(ans)


def main():
	n = int(input())
	A = list(map(lambda x: int(x) - 1, list(input().strip())))
	ans = 1
	if not 1 in A:
		ans *= 2
		for i in range(n):
			A[i] >>= 1
	parity = 0
	for i in range(n):
		if n - 1 & i == i:
			parity ^= A[i] & 1
	ans *= parity
	print(ans)
main()


import sys
stdin = sys.stdin
ns = lambda : stdin.readline().rstrip()
ni = lambda : int(stdin.readline().rstrip())
nm = lambda : map(int, stdin.readline().split())
nl = lambda : list(map(int, stdin.readline().split()))
n = ni()
l = list(map(lambda x: int(x) - 1, list(ns())))
f = 1
if 1 not in l:
	l = [x // 2 for x in l]
	f += 1

def Cmod2(n, r):
	return n & r == r
s = sum((Cmod2(n - 1, i) * l[i] for i in range(n))) % 2
print(f * s)


import sys
from itertools import product
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().strip()))
A1 = [a % 2 for a in A]
for i in range(31, -1, -1):
	if 1 << i & len(A1):
		k = 1 << i
		B = []
		B.append(sum(A1[:k]) % 2)
		for j in range(k, len(A1)):
			B.append((B[-1] + A1[j] - A1[j - k]) % 2)
		A1 = B[:]
	if 1 << i & len(A1):
		k = 1 << i
		B = []
		B.append(sum(A1[:k]) % 2)
		for j in range(k, len(A1)):
			B.append((B[-1] + A1[j] - A1[j - k]) % 2)
		A1 = B[:]
pari = A1[0]
if pari == 1:
	ans = 1
elif 2 in A:
	ans = 0
else:
	A2 = [abs(a2 - a1) // 2 for (a1, a2) in zip(A, A[1:])]
	N2 = len(A2)
	for i in range(31, -1, -1):
		if 1 << i & len(A2):
			k = 1 << i
			B = []
			B.append(sum(A2[:k]) % 2)
			for j in range(k, len(A2)):
				B.append((B[-1] + A2[j] - A2[j - k]) % 2)
			A2 = B[:]
		if 1 << i & len(A2):
			k = 1 << i
			B = []
			B.append(sum(A2[:k]) % 2)
			for j in range(k, len(A2)):
				B.append((B[-1] + A2[j] - A2[j - k]) % 2)
			A2 = B[:]
	if A2[0] == 0:
		ans = 0
	else:
		ans = 2
print(ans)


N = int(input())
A = input()
b = []
for i in range(N - 1):
	b.append(abs(int(A[i]) - int(A[i + 1])))
S = 0
p = 0
for i in range(N - 1):
	if p == 0:
		S += b[i]
	n = N - 2 - i
	k = i + 1
	if n == 0:
		break
	else:
		while n % 2 == 0:
			p += 1
			n //= 2
		while k % 2 == 0:
			p -= 1
			k //= 2
if S % 2:
	print(1)
else:
	for i in range(N - 1):
		if b[i] == 1:
			print(0)
			exit()
	if S // 2 % 2:
		print(2)
	else:
		print(0)


n = int(input())
s = input()
a = []
for i in range(n - 1):
	a.append(abs(int(s[i]) - int(s[i + 1])))
ans = []
for r in range(n - 1):
	if n - 2 ^ r ^ n - 2 - r == 0:
		ans.append(int(a[r]))
res = 0
for i in ans:
	res = abs(res - i)
if 1 in a:
	print(res % 2)
else:
	print(res)


from collections import Counter, defaultdict
(N,) = list(map(int, input().split()))
A = list(map(int, input()))
A = [abs(x - y) for (x, y) in zip(A, A[1:])]
N -= 1

def solve(A):
	N = len(A)

	def fact(n):
		if n == 0:
			return 1
		return n * fact(n - 1)

	def nCr(n, r):
		return fact(n) // (fact(n - r) * fact(r))

	def nCrMod2(n, r):
		return 0 if (n ^ r) & r else 1
		while r:
			if r % 2 and (not n % 2):
				return 0
			n //= 2
			r //= 2
		return 1
	onlyZeroesAndTwos = Counter(A)[1] == 0
	ans = None
	if onlyZeroesAndTwos:
		ans = 2 * (sum((nCrMod2(N - 1, i) * (A[i] // 2) for i in range(N))) % 2)
	else:
		ans = sum((nCrMod2(N - 1, i) * A[i] for i in range(N))) % 2
	if False:
		import numpy as np
		mat = np.zeros((N, N), dtype=np.int64)
		for i in range(N - 1):
			mat[i][i] = 1
			mat[i][i + 1] = 1
		vec = np.array(A, dtype=np.int64)
		for t in range(N):
			M = np.linalg.matrix_power(mat, t)
			print('t', t)
			print('M^t', M)
			print('v_t', np.matmul(M, vec)[:N - t] % 4)
			print()
		for i in range(N):
			assert np.linalg.matrix_power(mat, N - 1)[0][i] == nCr(N - 1, i)
		mod4 = sum((nCr(N - 1, i) * A[i] for i in range(N))) % 4
		ans2 = mod4
		if not onlyZeroesAndTwos:
			ans2 = mod4 % 2
		assert ans == ans2
	return ans
print(solve(A))
if False:
	from itertools import product
	for N in range(2, 7):
		print('N', N)
		groups = defaultdict(list)
		for A in product([0, 1, 2], repeat=N):
			temp = list(A)
			for i in range(N - 1):
				temp = [abs(x - y) for (x, y) in zip(temp, temp[1:])]
			assert len(temp) == 1
			groups[temp[0]].append(A)
		for (k, v) in groups.items():
			print('ans', k)
			for A in v:
				assert k == solve(A)
				print('\t', A)
		print()


N = int(input())
a = list(map(int, list(input())))
a = list(map(lambda x: x - 1, a))
x = 0
num_mod = [0] * N
for i in range(1, N):
	tmp = 0
	t = i
	while t % 2 == 0:
		t //= 2
		tmp += 1
	num_mod[i] = num_mod[i - 1] + tmp
for (i, n) in enumerate(a):
	if n % 2 == 0:
		continue
	elif num_mod[N - 1] == num_mod[i] + num_mod[N - 1 - i]:
		x += 1
if x % 2 != 0:
	print(1)
elif 1 in a:
	print(0)
else:
	a = [x // 2 for x in a]
	x = 0
	for (i, n) in enumerate(a):
		if n % 2 == 0:
			continue
		elif num_mod[N - 1] == num_mod[i] + num_mod[N - 1 - i]:
			x += 1
	if x % 2 != 0:
		print(2)
	else:
		print(0)


import sys
import math
import heapq
mod = 10 ** 9 + 7
inf = float('inf')
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP, Decimal
from functools import lru_cache
n = int(input())
s = input()
A = [int(i) - 1 for i in s]
RUI2 = [pow(2, i) for i in range(21)]
import bisect as bi

@lru_cache(maxsize=10 ** 10)
def tan(n):
	if n == 0:
		return [1]
	if n == 1:
		return [1, 1]
	if n == 2:
		return [1, 0, 1]
	i = bi.bisect_right(RUI2, n) - 1
	return tan(n - pow(2, i)) + [0] * (pow(2, i + 1) - n - 1) + tan(n - pow(2, i))
if A.count(1) != 0:
	A = [i % 2 != 1 for i in A]
	a = [i & j for (i, j) in zip(A, tan(n - 1))]
	print(1 if sum(a) % 2 == 1 else 0)
else:
	a = [i // 2 & j for (i, j) in zip(A, tan(n - 1))]
	print(2 if sum(a) % 2 == 1 else 0)


import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

def nxor(x, n, k):
	if n & k == k:
		return x
	else:
		return 0

def main():
	n = int(input())
	a = [int(i) - 1 for i in list(input())]
	cumxor = 0
	amod = [i % 2 for i in a]
	for i in range(n):
		cumxor ^= nxor(amod[i], n - 1, i)
	if cumxor == 1:
		ans = 1
	elif 1 in a:
		ans = 0
	else:
		cumxor = 0
		adiv = [i // 2 for i in a]
		for i in range(n):
			cumxor ^= nxor(adiv[i], n - 1, i)
		if cumxor == 0:
			ans = 0
		else:
			ans = 2
	print(ans)
main()


def twos_in_factorial(n):
	return n - bin(n).count('1')

def parity_of_nCr(n, i):
	f = twos_in_factorial
	return f(n) - f(n - i) - f(i) > 0
n = int(input())
nums = list(map(lambda x: int(x) - 1, input().strip()))
no_one = False
if 1 not in nums:
	nums = [num // 2 for num in nums]
	no_one = True
is_odd = False
for (i, num) in enumerate(nums):
	if not parity_of_nCr(n - 1, i) and num & 1:
		is_odd ^= 1
if not is_odd:
	print(0)
else:
	print(1 << no_one)


n = int(input())
aa = list(map(lambda x: int(x) - 1, list(input())))

def parity(n, r):
	if n <= 1:
		return 1
	if r == 1:
		return n % 2
	if r == 0:
		return 1
	if n % 2 == 0 and r % 2 != 0:
		return 0
	return parity(n // 2, r // 2)

def ab(x):
	if x < 0:
		return -x
	return x
ans = 0
for (i, a) in enumerate([a % 2 for a in aa]):
	p = parity(n - 1, i)
	if p == 1:
		ans = ab(ans - a)
if ans == 1:
	print(1)
	exit(0)
if 1 in aa:
	print(0)
	exit(0)
ans = 0
for (i, a) in enumerate([a // 2 for a in aa]):
	p = parity(n - 1, i)
	if p == 1:
		ans = ab(ans - a)
print(ans * 2)


import sys
input = sys.stdin.readline
from functools import reduce
from itertools import starmap
from operator import xor, mul
N = int(input())
A = list(map(int, input().strip()))
A = [abs(x - y) for (x, y) in zip(A, A[1:])]
n = len(A)
coef = [n - 1 & k == k for k in range(n)]
if 1 in A:
	B = [x % 2 for x in A]
	ans = reduce(xor, starmap(mul, zip(B, coef)))
else:
	B = [x // 2 for x in A]
	ans = reduce(xor, starmap(mul, zip(B, coef))) * 2
print(ans)


N = int(input())
A = [int(a) - 1 for a in input()]
s = sum([a for (i, a) in enumerate(A) if N - 1 & i == i])
print(s % (2 if 1 in A else 4))


n = int(input())
a = list(map(int, input()))
l = [0] * (n - 1)
for i in range(n - 1):
	l[i] = abs(a[i + 1] - a[i])
n -= 1
if 1 in l:
	for i in range(n):
		if l[i] == 2:
			l[i] = 0
ans = 0
for (i, x) in enumerate(l):
	if not (i ^ n - 1) & i:
		ans ^= x
print(ans)


n = int(input())
a = list(map(int, input()))
a = [e - 1 for e in a]

def cnt_div2(x):
	ret = 0
	while x % 2 == 0 and x != 0:
		x //= 2
		ret += 1
	return ret
now = 0
cnt = [0]
for i in range(1, n):
	now += cnt_div2(n - i)
	now -= cnt_div2(i)
	cnt.append(now)
div2 = [e == 0 for e in cnt]

def f(li):
	ret = 0
	for (e1, e2) in zip(li, div2):
		e1 %= 2
		ret ^= e1 * e2
	return ret
if f(a):
	ans = 1
elif 1 in a:
	ans = 0
else:
	a = [e // 2 for e in a]
	if f(a):
		ans = 2
	else:
		ans = 0
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1

def main():
	N = int(input())
	a = list(map(int1, input()))
	X = 0
	c = 0
	f = False
	if not 1 in a:
		for i in range(N):
			a[i] //= 2
		f = True
	for i in range(N):
		if c == 0:
			X ^= a[i] % 2
		K = N - 1 - i
		while K > 0 and K % 2 == 0:
			c += 1
			K //= 2
		K = i + 1
		while K > 0 and K % 2 == 0:
			c -= 1
			K //= 2
	if X == 1:
		print(1 * (f + 1))
	else:
		print(0)
main()


N = int(input())
A = [int(a) - 1 for a in input()]
r = 1 if 1 in A else 2

def parity_of_nCk(n, k):
	return n & k == k
ans = 0
for (i, a) in enumerate(A):
	if a & r:
		if parity_of_nCk(N - 1, i):
			ans ^= 1
print(ans * r)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int, read().decode().rstrip()))
U = N + 10
fact_ord = [0] * U
for n in range(1, U):
	fact_ord[n] = fact_ord[n // 2] + n // 2

def solve_01(A):
	ret = 0
	N = len(A) - 1
	comb_ord = [fact_ord[N] - fact_ord[i] - fact_ord[N - i] for i in range(N + 1)]
	return sum((x * (y == 0) for (x, y) in zip(A, comb_ord))) % 2

def solve(A):
	if len(A) == 1:
		return A[0]
	A = [abs(x - y) for (x, y) in zip(A, A[1:])]
	if all((x != 1 for x in A)):
		B = [x // 2 for x in A]
		return 2 * solve_01(B)
	A = [x % 2 for x in A]
	return solve_01(A)
print(solve(A))


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def lucas(n, k):
	return n & k == k
N = INT()
A = [a - 1 for a in list(map(int, input()))]

def check(A):
	mod2 = 0
	for (i, a) in enumerate(A):
		if a == 1:
			mod2 += lucas(N - 1, i)
			mod2 %= 2
	return mod2
res = check(A)
if res == 1:
	print(1)
	exit()
if A.count(1):
	print(0)
	exit()
A = [a // 2 for a in A]
res = check(A)
if res == 1:
	print(2)
else:
	print(0)


n = int(input())
a = input()
if '2' in a:
	ans = 0
	for i in range(n):
		if a[i] == '2':
			ans ^= n - 1 == i | n - 1 - i
	if ans:
		print(1)
	else:
		print(0)
else:
	ans = 0
	for i in range(n):
		if a[i] == '3':
			ans ^= n - 1 == i | n - 1 - i
	if ans:
		print(2)
	else:
		print(0)