Ideone.com

fork download

copy

#include <stdio.h>
void phi(long long int a,long long int b)
	{
		long long int i,result,n;
		for(n=a;n<=b;n++)
		{
		for(i=2;i*i<=n;i++)
			{	result=n;
				if(n%i==0)
				result=result-result/i;
				while(n%i==0)
				n=n/i;
			}
 
			if(n>1)
			result=result-result/n;
			printf("%lld\n",result);
		}
		return 0;
	}
int main(void) {
	long long int a,b;
	scanf("%lld%lld",&a,&b);
//	for(i=a;i<=b;i++)
//	printf("%lld\n",phi(n));
phi(a,b);
 
	return 0;
}

Runtime error #stdin #stdout 0s 2012KB

stdin

copy

1 5

stdout

copy

-5227371475607062784
-2613685737803531392
-1742457158535687595
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
2

https://ideone.com/TmlrPc

language:

C (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language