Petya has n integers: 1, 2, 3, ..., n. He wants to split these integers in two non-empty groups in such a way that the absolute difference of sums of integers in each group is as small as possible. 

Help Petya to split the integers. Each of n integers should be exactly in one group.

Input

The first line contains a single integer n (2 ≤ n ≤ 60 000) — the number of integers Petya has.

Output

Print the smallest possible absolute difference in the first line.

In the second line print the size of the first group, followed by the integers in that group. You can print these integers in arbitrary order. If there are multiple answers, print any of them.

Examples

Input

4


Output

0
2 1 4 


Input

2


Output

1
1 1 

Note

In the first example you have to put integers 1 and 4 in the first group, and 2 and 3 in the second. This way the sum in each group is 5, and the absolute difference is 0.

In the second example there are only two integers, and since both groups should be non-empty, you have to put one integer in the first group and one in the second. This way the absolute difference of sums of integers in each group is 1.
import java.io.*;
import java.util.*;
import java.math.*;

 

public class Test
{

   
 
    
    public static void process()throws IOException
    {
          int n = ni();
          HashSet<Integer> a = new HashSet<Integer>();
          HashSet<Integer> b = new HashSet<Integer>();
          int i=0;
          boolean bool = false;
          int max1=0;
          int max2=0;
          if(n%2==0)
          {          
              while(i<n)
              {
                    if(!bool)
                    {
                         ++i;
                         a.add(i);
                         max1+=i;
                         if(i==n)break;
                         ++i;
                         b.add(i);
                         max2+=i;
                         bool = !bool;
                    }else{
                        ++i;
                        b.add(i);
                        max2+=i;
                        if(i==n)break;
                        ++i;
                        a.add(i);
                        max1+=i;
                        bool = !bool;
                    }
              }
          }else{
            while(i<n)
              {
                    if(!bool)
                    {
                         ++i;
                         a.add(i);
                         max1+=i;
                         if(i==n)break;
                         ++i;
                         a.add(i);
                         max1+=i;
                         bool = !bool;
                    }else{
                        ++i;
                        b.add(i);
                        max2+=i;
                        if(i==n)break;
                        ++i;
                        b.add(i);
                        max2+=i;
                        bool = !bool;
                    }
              }

          }
         
          pn(Math.abs(max1-max2));
          StringBuilder sb = new StringBuilder("");
          sb.append(a.size()).append(" ");
          for(Integer x : a)
          {
               sb.append(x).append(" ");
          }
          pn(sb.toString());

          

    }


    static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        out = new PrintWriter(System.out);
        sc=new AnotherReader();
        boolean oj = true;

        // oj = System.getProperty("ONLINE_JUDGE") != null;
        // if(!oj) sc=new AnotherReader(100);

        // long s = System.currentTimeMillis();
        int t=1;
        while(t-->0)
            process();
        out.flush();
        // if(!oj)
        //     System.out.println(System.currentTimeMillis()-s+"ms");
        System.out.close();  
    }

    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);System.out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
    static boolean multipleTC=false;



/////////////////////////////////////////////////////////////////////////////////////////////////////////

    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
    
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}