Problem: This is an interactive problem.

Jury has hidden a permutation p of integers from 0 to n - 1. You know only the length n. Remind that in permutation all integers are distinct.

Let b be the inverse permutation for p, i.e. pbi = i for all i. The only thing you can do is to ask xor of elements pi and bj, printing two indices i and j (not necessarily distinct). As a result of the query with indices i and j you'll get the value <image>, where <image> denotes the xor operation. You can find the description of xor operation in notes.

Note that some permutations can remain indistinguishable from the hidden one, even if you make all possible n2 queries. You have to compute the number of permutations indistinguishable from the hidden one, and print one of such permutations, making no more than 2n queries.

The hidden permutation does not depend on your queries.

Input

The first line contains single integer n (1 ≤ n ≤ 5000) — the length of the hidden permutation. You should read this integer first.

Output

When your program is ready to print the answer, print three lines.

In the first line print "!".

In the second line print single integer answers_cnt — the number of permutations indistinguishable from the hidden one, including the hidden one. 

In the third line print n integers p0, p1, ..., pn - 1 (0 ≤ pi < n, all pi should be distinct) — one of the permutations indistinguishable from the hidden one.

Your program should terminate after printing the answer.

Interaction

To ask about xor of two elements, print a string "? i j", where i and j — are integers from 0 to n - 1 — the index of the permutation element and the index of the inverse permutation element you want to know the xor-sum for. After that print a line break and make flush operation.

After printing the query your program should read single integer — the value of <image>.

For a permutation of length n your program should make no more than 2n queries about xor-sum. Note that printing answer doesn't count as a query. Note that you can't ask more than 2n questions. If you ask more than 2n questions or at least one incorrect question, your solution will get "Wrong answer".

If at some moment your program reads -1 as an answer, it should immediately exit (for example, by calling exit(0)). You will get "Wrong answer" in this case, it means that you asked more than 2n questions, or asked an invalid question. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Your solution will get "Idleness Limit Exceeded", if you don't print anything or forget to flush the output, including for the final answer .

To flush you can use (just after printing line break): 

  * fflush(stdout) in C++; 
  * System.out.flush() in Java; 
  * stdout.flush() in Python; 
  * flush(output) in Pascal; 
  * For other languages see the documentation. 



Hacking

For hacking use the following format:

n

p0 p1 ... pn - 1

Contestant programs will not be able to see this input.

Examples

Input

3
0
0
3
2
3
2

Output

? 0 0
? 1 1
? 1 2
? 0 2
? 2 1
? 2 0
!
1
0 1 2

Input

4
2
3
2
0
2
3
2
0

Output

? 0 1
? 1 2
? 2 3
? 3 3
? 3 2
? 2 1
? 1 0
? 0 0
!
2
3 1 2 0

Note

xor operation, or bitwise exclusive OR, is an operation performed over two integers, in which the i-th digit in binary representation of the result is equal to 1 if and only if exactly one of the two integers has the i-th digit in binary representation equal to 1. For more information, see [here](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

In the first example p = [0, 1, 2], thus b = [0, 1, 2], the values <image> are correct for the given i, j. There are no other permutations that give the same answers for the given queries.

The answers for the queries are: 

  * <image>, 
  * <image>, 
  * <image>, 
  * <image>, 
  * <image>, 
  * <image>. 



In the second example p = [3, 1, 2, 0], and b = [3, 1, 2, 0], the values <image> match for all pairs i, j. But there is one more suitable permutation p = [0, 2, 1, 3], b = [0, 2, 1, 3] that matches all n2 possible queries as well. All other permutations do not match even the shown queries.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 27);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DSomethingWithXORQueries solver = new DSomethingWithXORQueries();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DSomethingWithXORQueries {
        Debug debug = new Debug(false);
        int[] p0b;
        int[] pb0;
        FastInput in;
        FastOutput out;

        public void solve(int testNumber, FastInput in, FastOutput out) {
            this.in = in;
            this.out = out;
            int n = in.readInt();

            p0b = new int[n];
            pb0 = new int[n];
            for (int i = 0; i < n; i++) {
                p0b[i] = ask(0, i);
                pb0[i] = ask(i, 0);
            }

            int[] p = new int[n];
            int[] b = new int[n];

            int[] ansP = null;
            int possible = 0;
            for (int i = 0; i < n; i++) {
                p[0] = i;
                for (int j = 1; j < n; j++) {
                    p[j] = xorPP(0, j) ^ p[0];
                }
                for (int j = 0; j < n; j++) {
                    b[j] = xorPB(0, j) ^ p[0];
                }

                boolean valid = true;
                for (int j = 0; j < n; j++) {
                    if (p[j] >= n || b[p[j]] != j) {
                        valid = false;
                        break;
                    }
                }

                if (!valid) {
                    continue;
                }
                debug.debug("i", i);
                possible++;
                if (ansP == null) {
                    ansP = p.clone();
                }
            }

            out.println("!");
            out.println(possible);
            out.flush();
            if (ansP == null) {
                return;
            }
            for (int x : ansP) {
                out.append(x);
                out.append(' ');
            }
            out.flush();
        }

        public int xorPB(int i, int j) {
            return p0b[j] ^ pb0[i] ^ p0b[0];
        }

        public int xorPP(int i, int j) {
            return pb0[i] ^ pb0[j];
        }

        public int ask(int a, int b) {
            out.printf("? %d %d\n", a, b);
            out.flush();
            return in.readInt();
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            return this;
        }

        public FastOutput printf(String format, Object... args) {
            cache.append(String.format(format, args));
            return this;
        }

        public FastOutput println(String c) {
            return append(c).println();
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class Debug {
        private boolean offline;
        private PrintStream out = System.err;

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager() == null;
        }

        public Debug debug(String name, int x) {
            if (offline) {
                debug(name, "" + x);
            }
            return this;
        }

        public Debug debug(String name, String x) {
            if (offline) {
                out.printf("%s=%s", name, x);
                out.println();
            }
            return this;
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }
}