Integer Sequence Dividing

题意翻译

给你一个数n，求把1~n的整数分为两组，使得每组的和的差的绝对值最小。

题目描述

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

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

3

输出样例 #1

0

输入样例 #2

5

输出样例 #2

1

输入样例 #3

6

输出样例 #3

1

说明

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