You are given an undirected graph with n vertices numbered from 1 to n. Initially there are no edges.

You are asked to perform some queries on the graph. Let last be the answer to the latest query of the second type, it is set to 0 before the first such query. Then the queries are the following:

  * 1~x~y (1 ≤ x, y ≤ n, x ≠ y) — add an undirected edge between the vertices (x + last - 1)~mod~n + 1 and (y + last - 1)~mod~n + 1 if it doesn't exist yet, otherwise remove it; 
  * 2~x~y (1 ≤ x, y ≤ n, x ≠ y) — check if there exists a path between the vertices (x + last - 1)~mod~n + 1 and (y + last - 1)~mod~n + 1, which goes only through currently existing edges, and set last to 1 if so and 0 otherwise. 



Good luck!

Input

The first line contains two integer numbers n and m (2 ≤ n, m ≤ 2 ⋅ 10^5) — the number of vertices and the number of queries, respectively.

Each of the following m lines contains a query of one of two aforementioned types. It is guaranteed that there is at least one query of the second type.

Output

Print a string, consisting of characters '0' and '1'. The i-th character should be the answer to the i-th query of the second type. Therefore the length of the string should be equal to the number of queries of the second type.

Examples

Input


5 9
1 1 2
1 1 3
2 3 2
1 2 4
2 3 4
1 2 4
2 3 4
1 1 3
2 4 3


Output


1010


Input


3 9
1 1 2
1 2 3
1 3 1
2 1 3
1 3 2
2 2 3
1 1 2
2 1 2
2 1 2


Output


1101

Note

The converted queries in the first example are:

  * 1 1 2 
  * 1 1 3 
  * 2 3 2 
  * 1 3 5 
  * 2 4 5 
  * 1 2 4 
  * 2 3 4 
  * 1 2 4 
  * 2 5 4 



The converted queries in the second example are:

  * 1 1 2 
  * 1 2 3 
  * 1 3 1 
  * 2 1 3 
  * 1 1 3 
  * 2 3 1 
  * 1 2 3 
  * 2 2 3 
  * 2 1 2 
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
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 << 29);
        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);
            FForcedOnlineQueriesProblem solver = new FForcedOnlineQueriesProblem();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class FForcedOnlineQueriesProblem {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            int m = in.readInt();

            DynamicConnectiveChecker dcc = new DynamicConnectiveChecker(n + 1, m);
            int last = 0;
            for (int i = 0; i < m; i++) {
                int t = in.readInt();
                int x = (in.readInt() + last - 1) % n + 1;
                int y = (in.readInt() + last - 1) % n + 1;
                if (t == 1) {
                    if (dcc.containEdge(x, y)) {
                        dcc.deleteEdge(x, y);
                    } else {
                        dcc.addEdge(x, y);
                    }
                } else {
                    boolean ans = dcc.check(x, y);
                    if (ans) {
                        out.append('1');
                        last = 1;
                    } else {
                        out.append('0');
                        last = 0;
                    }
                }
            }
        }

    }

    static class DynamicConnectiveChecker {
        DynamicConnectiveChecker.EulerTourTree[] levels;
        int n;
        int log2;
        LongObjectHashMap<DynamicConnectiveChecker.EdgeInfo> map;

        public boolean containEdge(int i, int j) {
            return map.containKey(idOfEdge(i, j));
        }

        public DynamicConnectiveChecker(int n, int m) {
            this.n = n;
            this.log2 = 32 - Integer.numberOfLeadingZeros(n - 1);
            levels = new DynamicConnectiveChecker.EulerTourTree[log2 + 1];
            for (int i = 1; i <= log2; i++) {
                levels[i] = new DynamicConnectiveChecker.EulerTourTree(n, 0);
                levels[i].id = i;
            }
            map = new LongObjectHashMap<>(m, true);
        }

        public boolean check(int i, int j) {
            if (i == j) {
                return true;
            }
            int r1 = levels[log2].rootOf(i);
            int r2 = levels[log2].rootOf(j);
            return r1 == r2;
        }

        public void addEdge(int i, int j) {
            DynamicConnectiveChecker.EdgeInfo info = new DynamicConnectiveChecker.EdgeInfo();
            info.a = i;
            info.b = j;
            info.level = log2 + 1;
            map.put(idOfEdge(i, j), info);
            pushDownEdge(info, levels[log2].rootOf(info.a) != levels[log2].rootOf(info.b));
        }

        private void pushDownEdge(DynamicConnectiveChecker.EdgeInfo info, boolean link) {
            info.level--;
            if (info.level == 0) {
                return;
            }

            addEdgeChain(info);
            if (link) {
                levels[info.level].link(info);
            }
        }

        private void addEdgeChain(DynamicConnectiveChecker.EdgeInfo info) {
            DynamicConnectiveChecker.EdgeChain chain1 = new DynamicConnectiveChecker.EdgeChain(info);
            DynamicConnectiveChecker.EdgeChain chain2 = new DynamicConnectiveChecker.EdgeChain(info);
            DynamicConnectiveChecker.Splay.splay(levels[info.level].nodes[info.a]);
            levels[info.level].nodes[info.a].addEdge(chain1);
            levels[info.level].nodes[info.a].pushUp();
            DynamicConnectiveChecker.Splay.splay(levels[info.level].nodes[info.b]);
            levels[info.level].nodes[info.b].addEdge(chain2);
            levels[info.level].nodes[info.b].pushUp();
        }

        public void deleteEdge(int i, int j) {
            long idOfEdge = idOfEdge(i, j);
            DynamicConnectiveChecker.EdgeInfo info = map.remove(idOfEdge);
            if (info.level == 0) {
                return;
            }

            int curLevel = info.level;
            info.level = -1;
            if (!levels[log2].map.containKey(idOfEdge)) {
                return;
            }

            for (int k = curLevel; k <= log2; k++) {
                levels[k].cut(i, j);
            }

            for (int k = curLevel; k <= log2; k++) {
                DynamicConnectiveChecker.Splay ti = levels[k].nodes[i];
                DynamicConnectiveChecker.Splay tj = levels[k].nodes[j];
                DynamicConnectiveChecker.Splay.splay(ti);
                DynamicConnectiveChecker.Splay.splay(tj);

                if (ti.size > tj.size) {
                    DynamicConnectiveChecker.Splay tmp = ti;
                    ti = tj;
                    tj = tmp;
                }

                DynamicConnectiveChecker.Splay.splay(ti);
                while (ti.infoWithMaxLevel != null) {
                    ti = ti.infoWithMaxLevel;
                    DynamicConnectiveChecker.Splay.splay(ti);
                    if (ti.infoWithMaxLevel.info.level < k) {
                        break;
                    }
                    pushDownEdge(ti.info, true);
                    DynamicConnectiveChecker.Splay.splay(ti);
                }
                DynamicConnectiveChecker.Splay.splay(ti);
                while (ti.containEdge != null) {
                    ti = ti.containEdge;
                    DynamicConnectiveChecker.Splay.splay(ti);
                    DynamicConnectiveChecker.EdgeInfo e = ti.popEdge().info;
                    ti.pushUp();
                    if (e.level < k) {
                    } else if (levels[log2].rootOf(e.a) ==
                            levels[log2].rootOf(e.b)) {
                        if (e.level == k) {
                            pushDownEdge(e, false);
                        }
                    } else {
                        addEdgeChain(e);
                        for (int t = k; t <= log2; t++) {
                            levels[t].link(e);
                        }
                        return;
                    }
                    DynamicConnectiveChecker.Splay.splay(ti);
                }
            }
        }

        private static long idOfEdge(int i, int j) {
            if (i > j) {
                int tmp = i;
                i = j;
                j = tmp;
            }
            return (((long) i) << 32) | j;
        }

        private static class EdgeInfo {
            int a;
            int b;
            int level;

            public String toString() {
                return String.format("%d -> %d", a, b);
            }

        }

        private static class EdgeChain {
            final DynamicConnectiveChecker.EdgeInfo info;
            DynamicConnectiveChecker.EdgeChain next;

            private EdgeChain(DynamicConnectiveChecker.EdgeInfo info) {
                this.info = info;
            }

            public String toString() {
                if (next == null) {
                    return info.toString();
                }
                return info.toString() + ", " + next.toString();
            }

        }

        public static class EulerTourTree {
            DynamicConnectiveChecker.Splay[] nodes;
            int id;
            LongObjectHashMap<DynamicConnectiveChecker.EulerTourTree.Edge> map;

            private DynamicConnectiveChecker.Splay alloc(int id) {
                DynamicConnectiveChecker.Splay splay = new DynamicConnectiveChecker.Splay();//buffer.alloc();
                splay.id = id;
                return splay;
            }

            public EulerTourTree(int n, int m) {
                map = new LongObjectHashMap<>(m, true);
                nodes = new DynamicConnectiveChecker.Splay[n];
                for (int i = 0; i < n; i++) {
                    nodes[i] = alloc(i);
                    nodes[i].node = 1;
                    nodes[i].pushUp();
                }
            }

            private void destroy(DynamicConnectiveChecker.Splay s) {
//            s.info = null;
//            s.chain = null;
//            s.infoWithMaxLevel = null;
//            s.containEdge = null;
//            buffer.release(s);
            }

            public int rootOf(int i) {
                return rootOf(nodes[i]).id;
            }

            public void setRoot(int i) {
                if (rootOf(i) == i) {
                    return;
                }

                DynamicConnectiveChecker.Splay.splay(nodes[i]);
                DynamicConnectiveChecker.Splay l = DynamicConnectiveChecker.Splay.splitLeft(nodes[i]);
                if (l == DynamicConnectiveChecker.Splay.NIL) {
                    return;
                }
                DynamicConnectiveChecker.Splay a = DynamicConnectiveChecker.Splay.selectMinAsRoot(l);
                DynamicConnectiveChecker.Splay b = DynamicConnectiveChecker.Splay.selectMaxAsRoot(nodes[i]);

                if (nodes[a.id] == a) {
                    DynamicConnectiveChecker.Splay.splitLeft(b);
                    destroy(b);
                } else {
                    l = DynamicConnectiveChecker.Splay.splitRight(a);
                    destroy(a);
                }

                DynamicConnectiveChecker.Splay newNode = alloc(i);
                DynamicConnectiveChecker.Splay.splay(nodes[i]);
                DynamicConnectiveChecker.Splay.splay(l);
                DynamicConnectiveChecker.Splay.merge(nodes[i], DynamicConnectiveChecker.Splay.merge(l, newNode));
            }

            public void link(DynamicConnectiveChecker.EdgeInfo info) {
                int i = info.a;
                int j = info.b;
                setRoot(i);
                setRoot(j);

                DynamicConnectiveChecker.EulerTourTree.Edge e = new DynamicConnectiveChecker.EulerTourTree.Edge();

                long id = idOfEdge(i, j);
                e.a = alloc(-i * 10000 - j);
                e.b = alloc(-i * 10000 - j);
                e.a.info = info;
                e.a.pushUp();
                e.b.pushUp();
                map.put(id, e);

                DynamicConnectiveChecker.Splay.splay(nodes[i]);
                DynamicConnectiveChecker.Splay.splay(nodes[j]);
                DynamicConnectiveChecker.Splay.merge(nodes[i], e.a);
                DynamicConnectiveChecker.Splay.merge(nodes[j], e.b);
                DynamicConnectiveChecker.Splay.splay(nodes[i]);
                DynamicConnectiveChecker.Splay.splay(nodes[j]);
                DynamicConnectiveChecker.Splay.merge(nodes[i], nodes[j]);

                DynamicConnectiveChecker.Splay newNode = alloc(i);
                DynamicConnectiveChecker.Splay.splay(nodes[i]);
                DynamicConnectiveChecker.Splay.merge(nodes[i], newNode);
            }

            private DynamicConnectiveChecker.Splay rootOf(DynamicConnectiveChecker.Splay x) {
                DynamicConnectiveChecker.Splay.splay(x);
                return DynamicConnectiveChecker.Splay.selectMinAsRoot(x);
            }

            public void cut(int i, int j) {
                long id = idOfEdge(i, j);
                DynamicConnectiveChecker.EulerTourTree.Edge e = map.remove(id);

                DynamicConnectiveChecker.Splay.splay(e.a);
                DynamicConnectiveChecker.Splay al = DynamicConnectiveChecker.Splay.splitLeft(e.a);
                DynamicConnectiveChecker.Splay ar = DynamicConnectiveChecker.Splay.splitRight(e.a);


                DynamicConnectiveChecker.Splay l, r;
                if (rootOf(ar) == rootOf(e.b)) {
                    DynamicConnectiveChecker.Splay.splay(e.b);
                    DynamicConnectiveChecker.Splay bl = DynamicConnectiveChecker.Splay.splitLeft(e.b);
                    DynamicConnectiveChecker.Splay br = DynamicConnectiveChecker.Splay.splitRight(e.b);

                    l = al;
                    r = br;
                } else {
                    DynamicConnectiveChecker.Splay.splay(e.b);
                    DynamicConnectiveChecker.Splay bl = DynamicConnectiveChecker.Splay.splitLeft(e.b);
                    DynamicConnectiveChecker.Splay br = DynamicConnectiveChecker.Splay.splitRight(e.b);

                    l = bl;
                    r = ar;
                }

                DynamicConnectiveChecker.Splay.splay(l);
                DynamicConnectiveChecker.Splay.splay(r);
                l = DynamicConnectiveChecker.Splay.selectMaxAsRoot(l);
                r = DynamicConnectiveChecker.Splay.selectMinAsRoot(r);

                if (nodes[l.id] == l) {
                    DynamicConnectiveChecker.Splay rSnapshot = r;
                    r = DynamicConnectiveChecker.Splay.splitRight(r);
                    destroy(rSnapshot);
                } else {
                    DynamicConnectiveChecker.Splay lSnapshot = l;
                    l = DynamicConnectiveChecker.Splay.splitLeft(l);
                    destroy(lSnapshot);
                }

                DynamicConnectiveChecker.Splay.merge(l, r);
                destroy(e.a);
                destroy(e.b);
            }

            private static class Edge {
                DynamicConnectiveChecker.Splay a;
                DynamicConnectiveChecker.Splay b;

            }

        }

        public static class Splay implements Cloneable {
            public static final DynamicConnectiveChecker.Splay NIL = new DynamicConnectiveChecker.Splay();
            DynamicConnectiveChecker.Splay left = NIL;
            DynamicConnectiveChecker.Splay right = NIL;
            DynamicConnectiveChecker.Splay father = NIL;
            int size;
            byte node;
            int id;
            DynamicConnectiveChecker.EdgeChain chain;
            DynamicConnectiveChecker.EdgeInfo info;
            DynamicConnectiveChecker.Splay containEdge;
            DynamicConnectiveChecker.Splay infoWithMaxLevel;

            static {
                NIL.left = NIL;
                NIL.right = NIL;
                NIL.father = NIL;
                NIL.size = 0;
                NIL.id = -2;
            }

            public void addEdge(DynamicConnectiveChecker.EdgeChain newChain) {
                newChain.next = chain;
                chain = newChain;
                containEdge = this;
            }

            public DynamicConnectiveChecker.EdgeChain popEdge() {
                DynamicConnectiveChecker.EdgeChain head = chain;
                chain = head.next;
                head.next = null;
                return head;
            }

            public static void splay(DynamicConnectiveChecker.Splay x) {
                if (x == NIL) {
                    return;
                }
                DynamicConnectiveChecker.Splay y, z;
                while ((y = x.father) != NIL) {
                    if ((z = y.father) == NIL) {
                        y.pushDown();
                        x.pushDown();
                        if (x == y.left) {
                            zig(x);
                        } else {
                            zag(x);
                        }
                    } else {
                        z.pushDown();
                        y.pushDown();
                        x.pushDown();
                        if (x == y.left) {
                            if (y == z.left) {
                                zig(y);
                                zig(x);
                            } else {
                                zig(x);
                                zag(x);
                            }
                        } else {
                            if (y == z.left) {
                                zag(x);
                                zig(x);
                            } else {
                                zag(y);
                                zag(x);
                            }
                        }
                    }
                }

                x.pushDown();
                x.pushUp();
            }

            public static void zig(DynamicConnectiveChecker.Splay x) {
                DynamicConnectiveChecker.Splay y = x.father;
                DynamicConnectiveChecker.Splay z = y.father;
                DynamicConnectiveChecker.Splay b = x.right;

                y.setLeft(b);
                x.setRight(y);
                z.changeChild(y, x);

                y.pushUp();
            }

            public static void zag(DynamicConnectiveChecker.Splay x) {
                DynamicConnectiveChecker.Splay y = x.father;
                DynamicConnectiveChecker.Splay z = y.father;
                DynamicConnectiveChecker.Splay b = x.left;

                y.setRight(b);
                x.setLeft(y);
                z.changeChild(y, x);

                y.pushUp();
            }

            public void setLeft(DynamicConnectiveChecker.Splay x) {
                left = x;
                x.father = this;
            }

            public void setRight(DynamicConnectiveChecker.Splay x) {
                right = x;
                x.father = this;
            }

            public void changeChild(DynamicConnectiveChecker.Splay y, DynamicConnectiveChecker.Splay x) {
                if (left == y) {
                    setLeft(x);
                } else {
                    setRight(x);
                }
            }

            public void pushUp() {
                if (this == NIL) {
                    return;
                }
                size = left.size + right.size + node;

                containEdge = null;
                if (chain != null) {
                    containEdge = this;
                } else if (left.containEdge != null) {
                    containEdge = left.containEdge;
                } else {
                    containEdge = right.containEdge;
                }

                infoWithMaxLevel = null;
                if (info != null) {
                    infoWithMaxLevel = this;
                }
                if (left.infoWithMaxLevel != null &&
                        (infoWithMaxLevel == null || infoWithMaxLevel.info.level < left.infoWithMaxLevel.info.level)) {
                    infoWithMaxLevel = left.infoWithMaxLevel;
                }
                if (right.infoWithMaxLevel != null &&
                        (infoWithMaxLevel == null || infoWithMaxLevel.info.level < right.infoWithMaxLevel.info.level)) {
                    infoWithMaxLevel = right.infoWithMaxLevel;
                }
            }

            public void pushDown() {
            }

            public static void toString(DynamicConnectiveChecker.Splay root, StringBuilder builder) {
                if (root == NIL) {
                    return;
                }
                root.pushDown();
                toString(root.left, builder);
                builder.append(root.id).append(',');
                toString(root.right, builder);
            }

            public DynamicConnectiveChecker.Splay clone() {
                try {
                    return (DynamicConnectiveChecker.Splay) super.clone();
                } catch (CloneNotSupportedException e) {
                    throw new RuntimeException(e);
                }
            }

            public static DynamicConnectiveChecker.Splay cloneTree(DynamicConnectiveChecker.Splay splay) {
                if (splay == NIL) {
                    return NIL;
                }
                splay = splay.clone();
                splay.left = cloneTree(splay.left);
                splay.right = cloneTree(splay.right);
                return splay;
            }

            public static DynamicConnectiveChecker.Splay selectMinAsRoot(DynamicConnectiveChecker.Splay root) {
                if (root == NIL) {
                    return root;
                }
                root.pushDown();
                while (root.left != NIL) {
                    root = root.left;
                    root.pushDown();
                }
                splay(root);
                return root;
            }

            public static DynamicConnectiveChecker.Splay selectMaxAsRoot(DynamicConnectiveChecker.Splay root) {
                if (root == NIL) {
                    return root;
                }
                root.pushDown();
                while (root.right != NIL) {
                    root = root.right;
                    root.pushDown();
                }
                splay(root);
                return root;
            }

            public static DynamicConnectiveChecker.Splay splitLeft(DynamicConnectiveChecker.Splay root) {
                root.pushDown();
                DynamicConnectiveChecker.Splay left = root.left;
                left.father = NIL;
                root.setLeft(NIL);
                root.pushUp();
                return left;
            }

            public static DynamicConnectiveChecker.Splay splitRight(DynamicConnectiveChecker.Splay root) {
                root.pushDown();
                DynamicConnectiveChecker.Splay right = root.right;
                right.father = NIL;
                root.setRight(NIL);
                root.pushUp();
                return right;
            }

            public static DynamicConnectiveChecker.Splay merge(DynamicConnectiveChecker.Splay a, DynamicConnectiveChecker.Splay b) {
                if (a == NIL) {
                    return b;
                }
                if (b == NIL) {
                    return a;
                }
                a = selectMaxAsRoot(a);
                a.setRight(b);
                a.pushUp();
                return a;
            }

            public String toString() {
                StringBuilder builder = new StringBuilder().append(id).append(":");
                toString(cloneTree(this), builder);
                return builder.toString();
            }

        }

    }

    static class Hasher {
        private long time = System.nanoTime() + System.currentTimeMillis() * 31L;

        public int shuffle(long z) {
            z += time;
            z = (z ^ (z >>> 33)) * 0x62a9d9ed799705f5L;
            return (int) (((z ^ (z >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32);
        }

        public int hash(long x) {
            return shuffle(x);
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        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;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

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

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

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            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 LongObjectHashMap<V> {
        private int[] slot;
        private int[] next;
        private long[] keys;
        private Object[] values;
        private int alloc;
        private boolean[] removed;
        private int mask;
        private int size;
        private boolean rehash;
        private Hasher hasher = new Hasher();
        private int[] version;
        private int now;

        private void access(int i) {
            if (version[i] != now) {
                slot[i] = 0;
                version[i] = now;
            }
        }

        public LongObjectHashMap(int cap, boolean rehash) {
            this.mask = (1 << (32 - Integer.numberOfLeadingZeros(cap - 1))) - 1;
            slot = new int[mask + 1];
            version = new int[mask + 1];
            next = new int[cap + 1];
            keys = new long[cap + 1];
            values = new Object[cap + 1];
            removed = new boolean[cap + 1];
            this.rehash = rehash;
        }

        private void doubleCapacity() {
            int newSize = Math.max(next.length + 10, next.length * 2);
            next = Arrays.copyOf(next, newSize);
            keys = Arrays.copyOf(keys, newSize);
            values = Arrays.copyOf(values, newSize);
            removed = Arrays.copyOf(removed, newSize);
        }

        private void rehash() {
            int[] newSlots = new int[Math.max(16, slot.length * 2)];
            int[] newVersions = new int[newSlots.length];
            int newMask = newSlots.length - 1;
            for (int i = 0; i < slot.length; i++) {
                access(i);
                if (slot[i] == 0) {
                    continue;
                }
                int head = slot[i];
                while (head != 0) {
                    int n = next[head];
                    int s = hash(keys[head]) & newMask;
                    next[head] = newSlots[s];
                    newSlots[s] = head;
                    head = n;
                }
            }
            this.slot = newSlots;
            this.mask = newMask;
            this.version = newVersions;
            now = 0;
        }

        private void alloc() {
            alloc++;
            if (alloc >= next.length) {
                doubleCapacity();
            }
            next[alloc] = 0;
            removed[alloc] = false;
            values[alloc] = null;
            size++;
        }

        private int hash(long x) {
            return hasher.hash(x);
        }

        public void put(long x, V y) {
            int h = hash(x);
            int s = h & mask;
            access(s);
            if (slot[s] == 0) {
                alloc();
                slot[s] = alloc;
                keys[alloc] = x;
                values[alloc] = y;
            } else {
                int index = findIndexOrLastEntry(s, x);
                if (keys[index] != x) {
                    alloc();
                    next[index] = alloc;
                    keys[alloc] = x;
                    values[alloc] = y;
                } else {
                    values[index] = y;
                }
            }
            if (rehash && size >= slot.length) {
                rehash();
            }
        }

        public boolean containKey(long x) {
            int h = hash(x);
            int s = h & mask;
            access(s);
            if (slot[s] == 0) {
                return false;
            }
            return keys[findIndexOrLastEntry(s, x)] == x;
        }

        public V remove(long x) {
            int h = hash(x);
            int s = h & mask;
            access(s);
            if (slot[s] == 0) {
                return null;
            }
            int pre = 0;
            int index = slot[s];
            while (keys[index] != x) {
                pre = index;
                if (next[index] != 0) {
                    index = next[index];
                } else {
                    break;
                }
            }
            if (keys[index] != x) {
                return null;
            }
            if (slot[s] == index) {
                slot[s] = next[index];
            } else {
                next[pre] = next[index];
            }
            removed[index] = true;
            size--;
            return (V) values[index];
        }

        private int findIndexOrLastEntry(int s, long x) {
            int iter = slot[s];
            while (keys[iter] != x) {
                if (next[iter] != 0) {
                    iter = next[iter];
                } else {
                    return iter;
                }
            }
            return iter;
        }

        public LongObjectEntryIterator<V> iterator() {
            return new LongObjectEntryIterator() {
                int index = 1;
                int readIndex = -1;


                public boolean hasNext() {
                    while (index <= alloc && removed[index]) {
                        index++;
                    }
                    return index <= alloc;
                }


                public long getEntryKey() {
                    return keys[readIndex];
                }


                public Object getEntryValue() {
                    return values[readIndex];
                }


                public void next() {
                    if (!hasNext()) {
                        throw new IllegalStateException();
                    }
                    readIndex = index;
                    index++;
                }
            };
        }

        public String toString() {
            LongObjectEntryIterator<V> iterator = iterator();
            StringBuilder builder = new StringBuilder("{");
            while (iterator.hasNext()) {
                iterator.next();
                builder.append(iterator.getEntryKey()).append("->").append(iterator.getEntryValue()).append(',');
            }
            if (builder.charAt(builder.length() - 1) == ',') {
                builder.setLength(builder.length() - 1);
            }
            builder.append('}');
            return builder.toString();
        }

    }

    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;
        }

    }

    static interface LongObjectEntryIterator<V> {
        boolean hasNext();

        void next();

        long getEntryKey();

        V getEntryValue();

    }
}

