Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

A. Integer Sequence Dividing

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/26/2019 08:03:23 (e3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|