You are given an integer sequence $1, 2, \dots, n$. You have to divide it into two sets $A$ and $B$ in such a way that each element belongs to exactly one set and $|sum(A) - sum(B)|$ is minimum possible.

The value $|x|$ is the absolute value of $x$ and $sum(S)$ is the sum of elements of the set $S$.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^9$).


-----Output-----

Print one integer — the minimum possible value of $|sum(A) - sum(B)|$ if you divide the initial sequence $1, 2, \dots, n$ into two sets $A$ and $B$.


-----Examples-----
Input
3

Output
0

Input
5

Output
1

Input
6

Output
1



-----Note-----

Some (not all) possible answers to examples:

In the first example you can divide the initial sequence into sets $A = \{1, 2\}$ and $B = \{3\}$ so the answer is $0$.

In the second example you can divide the initial sequence into sets $A = \{1, 3, 4\}$ and $B = \{2, 5\}$ so the answer is $1$.

In the third example you can divide the initial sequence into sets $A = \{1, 4, 5\}$ and $B = \{2, 3, 6\}$ so the answer is $1$.

Difficulty: introductory

Starter code:

Solutions:
n = int(input())
if n * (n + 1) // 2 % 2 == 1:
    print(1)
else:
    print(0)

n = int(input())
s=n*(n+1)//2
print(s%2)

n = int(input())

print(1 if n % 4 in {1, 2} else 0)


n=int(input())

if n%4==1 or n%4==2:
	print(1)
else:
	print(0)

n = int(input())
s = n * (n + 1) // 2
print(s % 2)


n = int(input())

x = (1 + n) * n // 2
print(0 if x % 2 == 0 else 1)


n = int(input())

print((n * (n + 1) // 2) & 1)

n = int(input())
n = n % 4
if (n == 0):
    print(n)
if (n == 1):
    print(1)
if (n == 2):
    print(1)
if (n == 3):
    print(0)

n = int(input())
if(n%4==1 or n%4==2):
    print(1)
else:
    print(0)

N = int(input())

if (N * (N + 1) // 2) % 2 == 0:
    print(0)
    
else:
    print(1)

n = int(input())
print(min(1, (n*(n+1))%4))

n = int(input())
if (n % 4 == 0 or n % 4 == 3):
    print(0)
else:
    print(1)

n=int(input())
x=(n*(n+1))//2
print(x%2)

n=int(input())
print((n//2+n%2 )%2)


n=int(input())
xx=(n*(n+1))//2
if xx%2==0:
	print(0)
	return
else:
	print(1)

n = int(input())
print(1 if (n * (n + 1) // 2) % 2 != 0 else 0)


a=int(input())
b=(a+1)*a//2
print(b%2)


n = int(input())

ans = 0
if n % 4 == 0:
    ans = 0
elif n % 4 == 1:
    ans = 1
elif n % 4 == 2:
    ans = 1
elif n % 4 == 3:
    ans = 0

print(ans)



n=int(input())
if n*(n+1)//2%2==0:
    print(0)
else:
    print(1)


n = int(input())
w = n * (n + 1) // 2
print(w % 2)


n=int(input())
if n%4==0 or n%4==3:
    print(0)
else:
    print(1)


MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n, = I()

n %= 4
if n == 1:
    print(1)
elif n == 2:
    print(1)
elif n == 3:
    print(0)
else:
    print(0)

# n,m=map(int,input().split(" "))

t=int(input())


l=(t*(t+1))//2

print(l%2)

n = int(input())
if n % 4 == 0:
    print(0)
elif n % 4 == 1:
    print(1)
elif n % 4 == 2:
    print(1)
elif n % 4 == 3:
    print(0)

n = int(input())
x = n * (n + 1) // 2
if x % 2 == 0:
    print(0)
else:
    print(1)