Let's define the permutation of length n as an array p = [p1, p2, ..., pn] consisting of n distinct integers from range from 1 to n. We say that this permutation maps value 1 into the value p1, value 2 into the value p2 and so on.

Kyota Ootori has just learned about cyclic representation of a permutation. A cycle is a sequence of numbers such that each element of this sequence is being mapped into the next element of this sequence (and the last element of the cycle is being mapped into the first element of the cycle). The cyclic representation is a representation of p as a collection of cycles forming p. For example, permutation p = [4, 1, 6, 2, 5, 3] has a cyclic representation that looks like (142)(36)(5) because 1 is replaced by 4, 4 is replaced by 2, 2 is replaced by 1, 3 and 6 are swapped, and 5 remains in place. 

Permutation may have several cyclic representations, so Kyoya defines the standard cyclic representation of a permutation as follows. First, reorder the elements within each cycle so the largest element is first. Then, reorder all of the cycles so they are sorted by their first element. For our example above, the standard cyclic representation of [4, 1, 6, 2, 5, 3] is (421)(5)(63).

Now, Kyoya notices that if we drop the parenthesis in the standard cyclic representation, we get another permutation! For instance, [4, 1, 6, 2, 5, 3] will become [4, 2, 1, 5, 6, 3].

Kyoya notices that some permutations don't change after applying operation described above at all. He wrote all permutations of length n that do not change in a list in lexicographic order. Unfortunately, his friend Tamaki Suoh lost this list. Kyoya wishes to reproduce the list and he needs your help. Given the integers n and k, print the permutation that was k-th on Kyoya's list.

Input

The first line will contain two integers n, k (1 ≤ n ≤ 50, 1 ≤ k ≤ min{1018, l} where l is the length of the Kyoya's list).

Output

Print n space-separated integers, representing the permutation that is the answer for the question. 

Examples

Input

4 3


Output

1 3 2 4


Input

10 1


Output

1 2 3 4 5 6 7 8 9 10

Note

The standard cycle representation is (1)(32)(4), which after removing parenthesis gives us the original permutation. The first permutation on the list would be [1, 2, 3, 4], while the second permutation would be [1, 2, 4, 3].
import java.io.*;
import java.math.BigInteger;
import java.util.*;

/**
 * Created by shamir0xe on 1/5/2015 AD.
 */

/*
ID:     shamir0xe
PROG:   gift1
LANG:   JAVA
*/

public class Solution {

    public static void main(String[] args) {
        IOHandler IO = new IOHandler();
        IO.init("std", "std", "input.txt", "output.txt");
        boolean testCaseKnown = false;

        Solver solver = new Solver();
        if (testCaseKnown) {
            int testCase = IO.getInput().nextInt();
            for (int test = 0; test < testCase; test++) {
                solver.solve(IO.in, IO.out, test + 1);
                IO.flush();
            }
        }
        else {
            int test = 1;
            try {
                while (true) {
                    solver.solve(IO.in, IO.out, test++);
                    IO.flush();
                }
            } catch (UnknownError unknownError) {
                IO.close();
            }
        }

        IO.close();
    }
}

class Solver {
    public void solve (MyInput in, PrintWriter out, int testCase) {
        int n = in.nextInt();
        long m = in.nextLong();
        if (n == 1) {
            out.println(1);
            return ;
        }
        long f[] = new long[n];
        f[n - 1] = 1;
        f[n - 2] = 2;
        for (int i = n - 3; i >= 0; i--) {
            f[i] = f[i + 1] + f[i + 2];
        }


        int[] order = new int[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }

        int i = 0;
        while (m != 1) {
            if (m > f[i + 1]) {
                m -= f[i + 1];
                swap(i, i + 1, order);
                i++;
            }
            i++;
        }

        for (int j = 0; j < n; j++) {
            out.print((order[j] + 1) + " ");
        }
        out.println();
    }

    void swap(int i, int j, int[] order) {
        int temp = order[i];
        order[i] = order[j];
        order[j] = temp;
    }
}

class DJS{
    int[] jad;
    int[] child;
    int n;

    public void initialize(int n) {
        this.n = n;
        jad = new int[n];
        child = new int[n];
        for (int i = 0; i < n; i++) {
            jad[i] = i;
            child[i] = 1;
        }
    }

    public DJS(int n) {
        initialize(n);
    }

    public int find(int i){
        if(jad[i] != i){
            jad[i] = find(jad[i]);
        }
        return jad[i];
    }

    public int union(int u, int v){
        int jadU = find(u);
        int jadV = find(v);
        if(jadU == jadV)
            return child[jadU];
        if (jadU > jadV) {
            int temp = jadU;
            jadU = jadV;
            jadV = temp;
        }

        jad[jadV] = jadU;
        child[jadU] += child[jadV];
        return child[jadU];
    }

}

class MultiSet <K> extends TreeMap<K, Integer>{
    private int size;

    public MultiSet(){
        super();
        size = 0;
    }

    public void put(K key) {
        Integer temp = super.get(key);
        if (temp == null) {
            temp = 1;
        }
        else {
            temp ++;
        }
        size++;
        super.put(key, temp);
    }

    public int getNumber(K key) {
        Integer temp = super.get(key);
        if (temp == null) {
            return 0;
        }
        return temp;
    }

    public int size() {
        return size;
    }

    public boolean removeOne(K key) {
        Integer temp = super.get(key);
        if (temp == null) {
            return false;
        }
        size--;
        if (temp == 1) {
            super.remove(key);
            return true;
        }
        super.put(key, temp - 1);
        return true;
    }
}

/**
 * Created by shamir14 on 2/28/14.
 */
class DisjointSet {
    int n;
    PairInt[] father;

    public DisjointSet(int nn){
        n = nn;
        father = new PairInt[n];
        for(int i=0; i<n; i++)
            father[i] = new PairInt(i, 0);
    }

    public int find(int i){
        if(father[i].X !=i)
            father[i].X = find(father[i].X);
        return father[i].X;
    }


    public void union(int i, int j){
        int xroot = find(i);
        int yroot = find(j);
        if(xroot == yroot)
            return;
        if(father[xroot].Y < father[yroot].Y)
            father[xroot].X = yroot;
        else if(father[xroot].Y > father[yroot].Y)
            father[yroot].X = xroot;
        else{
            father[yroot].X = xroot;
            father[xroot].Y = father[xroot].Y + 1;
        }
    }
}


class SuffixArray {
    char str[];
    int N, m, SA[], LCP[];
    int[] x, y, w, c;

    boolean cmp(int a, int b, int l) {
        return (y[a] == y[b] && y[a + l] == y[b + l]);
    }

    void Sort() {
        for (int i = 0; i < m; ++i) w[i] = 0;
        for (int i = 0; i < N; ++i) ++w[x[y[i]]];
        for (int i = 0; i < m - 1; ++i) w[i + 1] += w[i];
        for (int i = N - 1; i >= 0; --i) SA[--w[x[y[i]]]] = y[i];
    }

    void DA() {
        ++N;
        for (int i = 0; i < N; ++i) {
            x[i] = str[i];
            y[i] = i;
        }
        Sort();
        for (int i, j = 1, p = 1; p < N; j <<= 1, m = p) {
            for (p = 0, i = N - j; i < N; i++) y[p++] = i;
            for (int k = 0; k < N; ++k) if (SA[k] >= j) y[p++] = SA[k] - j;
            Sort();
            {
                int[] temp = Arrays.copyOf(x, x.length);
                x = Arrays.copyOf(y, y.length);
                y = Arrays.copyOf(temp, temp.length);
            }
            for (p = 1, x[SA[0]] = 0, i = 1; i < N; ++i)
                x[SA[i]] = cmp(SA[i - 1], SA[i], j) ? p - 1 : p++;
        }
        for (int i = 1; i < N; ++i)
            SA[i - 1] = SA[i];
        --N;
    }

    void kasaiLCP() {
        for (int i = 0; i < N; ++i)
            c[SA[i]] = i;
        LCP[0] = 0;
        for (int i = 0, h = 0; i < N; ++i) {
            if (c[i] > 0) {
                int j = SA[c[i] - 1];
                while (i + h < N && j + h < N && str[i + h] == str[j + h]) ++h;
                LCP[c[i]] = h;
                if (h > 0) --h;
            }
        }
    }


    public SuffixArray(String string) {
        this.str = string.toCharArray();
        N = str.length;
        SA = new int[N];
        LCP = new int[N];
        x = new int[N];
        y = new int[N];
        w = new int[N];
        c = new int[N];
        m = 256;
        buildSuffixes();
    }

    public void buildSuffixes() {
        DA();
        kasaiLCP();
    }

}

/**
 * Created by shamir0xe on 6/16/2015 AD.
 */
class OSValidator {
    private String OS_Name;

    public OSValidator() {
        OS_Name = System.getProperty("os.name").toLowerCase();
    }

    public boolean isMac() {
        return OS_Name.contains("mac");
    }

    public boolean isWindows() {
        return OS_Name.indexOf("win") >= 0;
    }

    public boolean isLinux() {
        return OS_Name.indexOf("nix") >= 0 || OS_Name.indexOf("nux") >= 0 || OS_Name.indexOf("aix") > 0;
    }

    public String append(String ... names) {
        String ret = "";
        for (String str : names) {
            ret += str;
            if (isMac() || isLinux()) {
                ret += "/";
            }
            else {
                ret += "\\";
            }
        }
        return ret;
    }

    public String correctPath(String path) {
        if (isWindows()) {
            return path;
        }
        return "\"" + path + "\"";
    }
}


/**
 * Created by shamir14 on 5/7/14.
 */
class CtrlF5 {
    int test;
    public CtrlF5(int test) {
        this.test = test;
    }
    private OSValidator OS = new OSValidator();

    public long runTest(){
        long time = 0;
//        createCopyDir(test);

        StopWatch stopWatch = new StopWatch();
        final Process[] process = {null};
        Runnable runnable = new Runnable() {
            @Override
            public void run() {
                String cmd[] = new String[0];
                if (OS.isWindows()) {
                    cmd = new String[] {"j1.com"};
                }
                else {
                    // Linux
                }
                try {
                    process[0] = Runtime.getRuntime().exec(cmd);

//                    InputStream inFile = new FileInputStream(OS.append(problem.contestName, problem.name) + "in.txt");
//                    copyStream(inFile, process[0].getOutputStream());
                    PrintWriter out = new PrintWriter(process[0].getOutputStream());
                    out.println(test);
                    out.flush();
                    out.close();

                    try {
                        process[0].waitFor();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        };

        Thread thread = new Thread(runnable);
        thread.start();
        stopWatch.start();
        while(true) {
            time = stopWatch.getTimeMillis();
            if(!thread.isAlive()) {
                break;
            }
        }
        MyInput in = new MyInput(process[0].getInputStream());
        if (!in.nextLine().equals("You are not our student!You are not our student!")) {
            try {
                PrintWriter out = new PrintWriter(new FileOutputStream("ramz.txt"));
                out.println("yo bro, ans = " + test);
                out.flush();
                out.close();
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
        if(thread.isAlive()) {
            kill(process);
        }
        return (time);
    }

    public void kill(final Process[] process) {
//        if (OS.isWindows()) {
//            WinProcess winProcess = new WinProcess(process[0]);
//            winProcess.killRecursively();
//        }
        process[0].destroy();
    }

}

class StopWatch {
    long beginTime;

    public StopWatch() {
        beginTime = System.currentTimeMillis();
    }

    public void start() {
        beginTime = System.currentTimeMillis();
    }

    public long getTimeMillis() {
        return System.currentTimeMillis() - beginTime;
    }

    public double getTimeSecond() {
        return (double)getTimeMillis() / 1000.;
    }

}

class IOHandler {
    MyInput in;
    PrintWriter out;

    /**
     *
     * @param input_type        : "file" or "std"
     * @param output_type       : "file" or "std"
     * @param input_file_name   : name of the input file
     * @param output_file_name  : name of the output file
     */
    public void init(String input_type, String output_type, String input_file_name, String output_file_name) {
        if (input_type.toLowerCase().equals("std")) {
            in = new MyInput(System.in);
        }
        else {
            // file
            try {
                in = new MyInput(new FileInputStream(input_file_name));
            }
            catch (IOException e) {
                throw new UnknownError();
            }
        }
        if (output_type.toLowerCase().equals("std")) {
            out = new PrintWriter(System.out);
        }
        else {
            // file
            try {
                out = new PrintWriter(new FileOutputStream(output_file_name));
            }
            catch (IOException e) {
                throw new UnknownError();
            }
        }
    }

    public MyInput getInput() {
        return in;
    }

    public PrintWriter getOutput() {
        return out;
    }

    public void flush() {
        out.flush();
    }

    public void close() {
        out.flush();
        out.close();
    }

}

class MyInput {
    private BufferedReader br;
    private StringTokenizer st;

    MyInput (InputStream inputStream) {
        br = new BufferedReader(new InputStreamReader(inputStream));
        st = null;
    }

    public String next() {
        if (st == null || !st.hasMoreElements()) {
            try {
                String line = br.readLine();
                if (line == null) {
                    throw new UnknownError();
                }
                while (line.trim().equals("")) {
                    line = br.readLine();
                    if (line == null) {
                        throw new UnknownError();
                    }
                }
                st = new StringTokenizer(line);
            } catch (IOException e) {
                throw new UnknownError();
            }
        }
        return st.nextToken();
    }

    public String nextLine() {
        try {
            String line = br.readLine();
            if (line == null) {
                throw new UnknownError();
            }
            return line;
        }
        catch (IOException e) {
            throw new UnknownError();
        }
    }

    public void readEmptyLine() {
        try {
            br.readLine();
        }
        catch (IOException e) {
            throw new UnknownError();
        }
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public BigInteger nextBigInteger() {
        return new BigInteger(next());
    }

    public boolean hasNext() {
        try {
            return st != null && st.hasMoreElements() || br.ready();
        } catch (IOException e) {
            throw new UnknownError();
        }
    }
}

/**
 * Created by shamir0xe on 2/28/14.
 */
class MyMath {

    /**
     * Sieve Of Eratosthens[O(NloglogN)]
     * @param n
     * @return int[] with all primes within [0, n]
     */
    public static int[] sieve(int n){
        int[] pr = new int[n + 1];
        Arrays.fill(pr, 1);
        ArrayList <Integer> prime = new ArrayList<Integer>();
        pr[0] = pr[1] = 0;
        for(int i = 2; i <= n; i++) {
            if(pr[i] == 1) {
                prime.add(i);
                if((long)i * i <= n)
                    for(long j = (long)i * i; j <= n; j += i)
                        pr[(int)j] = 0;
            }
        }
        int [] ret = new int[prime.size()];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = prime.get(i);
        }
        return ret;
    }

    /**
     * GCD[O(logMAX(a, b))]
     * @param a
     * @param b
     * @return GCD(a, b)
     */
    public static int GCD(int a, int b){return b!=0 ? GCD(b, a % b) : a;}

    /**
     * Fast Power [O(logB)]
     * @param a
     * @param b
     * @param m
     * @return bth power of a modolu m
     */
    public static int fastPow(int a, int b, int m){
        int ans = 1;
        while(b != 0){
            if((b & 1) == 1)
                ans = mul(ans, a, m);
            a = mul(a, a, m);
            b >>= 1;
        }
        return ans%m;
    }

    public static void buildPascal(int[][] pas, int MOD) {
        int n = pas.length;
        for (int i = 0; i < n; i++) {
            pas[i][0] = 0;
        }
        for (int i = 0; i < n; i++) {
            pas[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                pas[i][j] = (pas[i][j-1] + pas[i-1][j-1]) % MOD;
            }
        }
    }

    // ext. Euclidean [O(log(Max(a, b))]
    // Assumes nonnegative input. Returns d such that d=a*X+b*Y
    public static long GCDex (long a, long b, long[] x, long[] y) {
        if (a == 0) {
            x[0] = 0; y[0] = 1;
            return b;
        }
        long[] x1 = new long[1];
        long[] y1 = new long[1];

        long d = GCDex(b % a, a, x1, y1);
        x[0] = y1[0] - (b / a) * x1[0];
        y[0] = x1[0];
        return d;
    }

    // Return X such that A * X == 1 (mod M)
    // Return -1 if it doesn't exist such an X
    public static long invMod(long a, long m){
        long[] x = new long[1];
        long[] q = new long[1];
        if(GCDex(a, m, x, q) == 1){
            x[0] = x[0] % m;
            if (x[0] < m) {
                x[0] = (x[0] + m) % m;
            }
            return x[0];
        }
        return -1;
    }

    /**
     *  this function gives the prime factors of n
     *  @param n an integer that wanna it primes
     *  @param primes the int[] of primes
     **/
    public static ArrayList<int[]> getFactors(int n, int[] primes) {
        ArrayList <int[]> factors = new ArrayList<int[]>();
        for (int prime: primes) {
            if (n % prime == 0) {
                int cnt = 0;
                while (n % prime == 0) {
                    n /= prime;
                    cnt++;
                }
                factors.add(new int[] {prime, cnt});
            }
        }
        if (n != 1) {
            factors.add(new int[] {n, 1});
        }
        return factors;
    }

    public static int add(int a, int b, int MOD) {
        return ((a + b) % MOD + MOD) % MOD;
    }

    public static int mul(int a, int b, int MOD) {
        return ((int)(((long) a * b) % MOD) + MOD) % MOD;
    }

}

class Pair <P extends Comparable <? super P>, Q extends Comparable <? super Q> >
        implements Comparable <Pair <P, Q> > {
    P a;
    Q b;
    public Pair (P a, Q b) {
        this.a = a;
        this.b = b;
    }

    public Pair() {
    }

    public void setX(P a) {
        this.a = a;
    }

    public void setY(Q b) {
        this.b = b;
    }

    public P getX() {
        return a;
    }

    public Q getY() {
        return b;
    }

    public String toString() {
        return "(" + a.toString() + ", " + b.toString() + ")";
    }

    @Override
    public int compareTo(Pair<P, Q> o) {
        int cmp = a.compareTo(o.a);
        if (cmp == 0) {
            return b.compareTo(o.b);
        }
        return cmp;
    }
}

class FenwickTree {
    private int[] tree;
    private int maxVal;

    public FenwickTree(int n) {
        maxVal = n;
        tree = new int[maxVal + 1];
    }

    /**
     *  update element val by adding the val to it
     *  O(LOG(N))
     */
    public void update(int idx, int val) {
        idx++;
        while (idx <= maxVal) {
            tree[idx] += val;
            idx += (idx & (-idx));
        }
    }

    /**
     *  return the sum of values of tree[] from idx to 0
     *  O(LOG(N))
     */
    public int read(int idx) {
        idx++;
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }

    public int getMaxVal() {
        return maxVal;
    }

    public int rangeSum(int left, int right) {
        if(left > right)
            return 0;
        int sumLeft = read(left - 1);
        int sumRight = read(right);
        return sumRight - sumLeft;
    }
}

class PairInt implements Comparable <PairInt> {
    public int X, Y;

    public PairInt(int X, int Y){
        this.X = X;
        this.Y = Y;
    }

    public PairInt add(PairInt b) {
        return new PairInt(X + b.X, Y + b.Y);
    }

    public PairInt sub(PairInt b) {
        return new PairInt(X - b.X, Y - b.Y);
    }

    @Override
    public int compareTo(PairInt o) {
        if(X != o.X)
            return X - o.X;
        return Y - o.Y;
    }
}

class IntArrays {

    public static void reverse(int[] cur){
        int[] temp = new int[cur.length];
        int cnt = 0;
        for(int i=cur.length-1; i>=0; i--){
            temp[cnt++] = cur[i];
        }
        for(int i=0;i<cnt; i++)
            cur[i] = temp[i];
    }

    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

//    public static void print(int[] arr, OutputWriter out){
//        boolean first = true;
//        for(int temp: arr){
//            if(first)
//                first = false;
//            else
//                out.print(" ");
//            out.print(temp);
//        }
//        out.printLine();
//    }

    public static Integer[] selfOrder(int n) {
        Integer[] self = new Integer[n];
        for (int i = 0; i < n; i++) {
            self[i] = i;
        }
        return self;
    }

    public static int[] convertBoxToPrimitive(Integer[] box) {
        int[] primitive = new int[box.length];
        for (int i = 0; i < box.length; i++) {
            primitive[i] = box[i];
        }
        return primitive;
    }

    public static int[] getOrder(final int[] arr) {
        Integer[] order = selfOrder(arr.length);
        Arrays.sort(order, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return arr[o1] - arr[o2];
            }
        });
        return convertBoxToPrimitive(order);
    }

    public static boolean next_permutation(int[] c){
        // 1. finds the largest k, that c[k] < c[k+1]
        int first = getFirst( c );
        if ( first == -1 ) return false; // no greater permutation
        // 2. find last index toSwap, that c[k] < c[toSwap]
        int toSwap = c.length - 1;
        while ( c[ first ] >= c[ toSwap ] )
            --toSwap;
        // 3. swap elements with indexes first and last
        swap( c, first++, toSwap );
        // 4. reverse sequence from k+1 to n (inclusive)
        toSwap = c.length - 1;
        while ( first < toSwap )
            swap( c, first++, toSwap-- );
        return true;
    }

    // finds the largest k, that c[k] < c[k+1]
    // if no such k exists (there is not greater permutation), return -1
    private static int getFirst( final int[] c ) {
        for ( int i = c.length - 2; i >= 0; --i )
            if ( c[ i ] <  c[ i + 1 ] )
                return i;
        return -1;
    }

    /**
     * return the minimum index i such that val[ order[ i ] ] >= need
     */
    public static int lowerBound(int[] order, int[] val, int need) {
        int s = 0;
        int e = order.length;
        while(e - s > 1) {
            int mid = (e + s) / 2;
            if(val[order[mid]] < need)
                s = mid;
            else
                e = mid;
        }
        if(val[order[s]] >= need)
            return s;
        return e;
    }

    public static int lowerBound(int[] val, int need) {
        int s = 0;
        int e = val.length;
        while(e - s > 1) {
            int mid = (e + s) / 2;
            if(val[mid] < need)
                s = mid;
            else
                e = mid;
        }
        if(val[s] >= need)
            return s;
        return e;
    }


}

/**
 * Created by shamir14 on 2/27/14.
 */
class InputReader {
    // this IO reading is provided by Egor Kulikov
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new UnknownError();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new UnknownError();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }


    public boolean hasNext(){
        return peek()!=-1;
    }

    public int peek() {
        if (numChars == -1)
            return -1;
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                return -1;
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new UnknownError();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long nextLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new UnknownError();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0() {
        StringBuffer buf = new StringBuffer();
        int c = read();
        while (c != '\n' && c != -1) {
            if (c != '\r')
                buf.appendCodePoint(c);
            c = read();
        }
        return buf.toString();
    }

    public String nextLine() {
        String s = readLine0();
        while (s.trim().length() == 0)
            s = readLine0();
        return s;
    }

    public String readLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines)
            return nextLine();
        else
            return readLine0();
    }

    public BigInteger nextBigInteger() {
        try {
            return new BigInteger(nextString());
        } catch (NumberFormatException e) {
            throw new UnknownError();
        }
    }

    public char nextCharacter() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public double nextDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, nextInt());
            if (c < '0' || c > '9')
                throw new UnknownError();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new UnknownError();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public boolean isExhausted() {
        int value;
        while (isSpaceChar(value = peek()) && value != -1)
            read();
        return value == -1;
    }

    public String next() {
        return nextString();
    }
}
