#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
char s[1000010];
int a[1000010];
int main()
{
/*	for(int i=0;i<=20;++i)
	{
		C[i][0]=1;
		for(int j=1;j<=i;++j)C[i][j]=C[i-1][j]^C[i-1][j-1];
		for(int j=0;j<=i;++j)printf("%d",C[i][j]);printf("\n");
	}*/
	scanf("%d",&n);--n;
	scanf("%s",s);
	for(int i=0;i<=n-1;++i)
		if(s[i]<s[i+1])a[i]=s[i+1]-s[i];
		else a[i]=s[i]-s[i+1];
	--n;
	int ans=0;
	for(int i=0;i<=n;++i)if((i&n)==i)ans^=a[i]&1;
	if(ans&1)return printf("1"),0;
	for(int i=0;i<=n;++i)if(a[i]==1)return printf("0"),0;
	ans=0;
	for(int i=0;i<=n;++i)if((i&n)==i)ans^=a[i]==2;
	if(ans==0)printf("0");
	else printf("2");
	return 0;
}

### Prompt

Please create a solution in Cpp to the following 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

### Response

```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
char s[1000010];
int a[1000010];
int main()
{
/*	for(int i=0;i<=20;++i)
	{
		C[i][0]=1;
		for(int j=1;j<=i;++j)C[i][j]=C[i-1][j]^C[i-1][j-1];
		for(int j=0;j<=i;++j)printf("%d",C[i][j]);printf("\n");
	}*/
	scanf("%d",&n);--n;
	scanf("%s",s);
	for(int i=0;i<=n-1;++i)
		if(s[i]<s[i+1])a[i]=s[i+1]-s[i];
		else a[i]=s[i]-s[i+1];
	--n;
	int ans=0;
	for(int i=0;i<=n;++i)if((i&n)==i)ans^=a[i]&1;
	if(ans&1)return printf("1"),0;
	for(int i=0;i<=n;++i)if(a[i]==1)return printf("0"),0;
	ans=0;
	for(int i=0;i<=n;++i)if((i&n)==i)ans^=a[i]==2;
	if(ans==0)printf("0");
	else printf("2");
	return 0;
}

```