Problem: The only difference from the previous problem is the constraint on the number of requests. In this problem your program should guess the answer doing at most 7 requests.

This problem is a little bit unusual. Here you are to implement an interaction with a testing system. That means that you can make queries and get responses in the online mode. Please be sure to use the stream flushing operation after each query's output in order not to leave part of your output in some buffer. For example, in C++ you've got to use the fflush(stdout) function, in Java — call System.out.flush(), and in Pascal — flush(output).

Bulls and Cows (also known as Cows and Bulls or Pigs and Bulls or Bulls and Cleots) is an old code-breaking paper and pencil game for two players, predating the similar commercially marketed board game Mastermind.

On a sheet of paper, the first player thinks a secret string. This string consists only of digits and has the length 4. The digits in the string must be all different, no two or more equal digits are allowed.

Then the second player tries to guess his opponent's string. For every guess the first player gives the number of matches. If the matching digits are on their right positions, they are "bulls", if on different positions, they are "cows". Thus a response is a pair of numbers — the number of "bulls" and the number of "cows". A try can contain equal digits.

More formally, let's the secret string is s and the second player are trying to guess it with a string x. The number of "bulls" is a number of such positions i (1 ≤ i ≤ 4) where s[i] = x[i]. The number of "cows" is a number of such digits c that s contains c in the position i (i.e. s[i] = c), x contains c, but x[i] ≠ c.

For example, the secret string is "0427", the opponent's try is "0724", then the answer is 2 bulls and 2 cows (the bulls are "0" and "2", the cows are "4" and "7"). If the secret string is "0123", the opponent's try is "0330", then the answer is 1 bull and 1 cow.

In this problem you are to guess the string s that the system has chosen. You only know that the chosen string consists of 4 distinct digits.

You can make queries to the testing system, each query is the output of a single 4-digit string. The answer to the query is the number of bulls and number of cows. If the system's response equals "4 0", that means the interaction with your problem is over and the program must terminate. That is possible for two reasons — the program either guessed the number x or made an invalid action (for example, printed letters instead of digits).

Your program is allowed to do at most 7 queries.

You can hack solutions of other participants providing a 4-digit string containing distinct digits — the secret string.

Input

To read answers to the queries, the program must use the standard input.

The program will receive pairs of non-negative integers in the input, one pair per line. The first number in a pair is a number of bulls and the second one is a number of cows of the string s and the string xi printed by your program. If the system response equals "4 0", then your solution should terminate.

The testing system will let your program read the i-th pair of integers from the input only after your program displays the corresponding system query in the output: prints value xi in a single line and executes operation flush.

Output

The program must use the standard output to print queries.

Your program must output requests — 4-digit strings x1, x2, ..., one per line. After the output of each line the program must execute flush operation. The program should read the answer to the query from the standard input.

Your program is allowed to do at most 7 queries.

Examples

Input

0 1
2 0
1 1
0 4
2 1
4 0


Output

8000
0179
3159
3210
0112
0123

Note

The secret string s in the example is "0123".

Solution (in JAVA):

Solution:
import sun.security.jca.JCAUtil;

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.security.SecureRandom;
import java.util.*;
import java.io.BufferedWriter;
import java.io.IOException;
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) {
        new TaskC().solve();
    }

    static class TaskC {
        public void solve() {

            long timeBeg = System.currentTimeMillis();

            InputReader in = new InputReader(System.in);

            String[] cand = new String[100500];
            int szCand = 0;
            for (int a = 0; a < 10; a++) {
                for (int b = 0; b < 10; b++) {
                    for (int c = 0; c < 10; c++) {
                        for (int d = 0; d < 10; d++) {
                            IntSplaySet abcd = new IntSplaySet();
                            abcd.add(a);
                            abcd.add(b);
                            abcd.add(c);
                            abcd.add(d);
                            if (abcd.size() == 4) {
                                cand[szCand++] = "" + a + b + c + d;
                            }
                        }
                    }
                }
            }

//            cmp(cand[0], cand[567]);
            int[][] cmp = new int[szCand][szCand];
            for (int i = 0; i < szCand; i++) {
                for (int j = i; j < szCand; j++) {
                    cmp[i][j] = cmp[j][i] = cmp(cand[i], cand[j]);
                }
            }
//            System.err.println("TIME:" + (System.currentTimeMillis() - timeBeg) / 1e3);
//            System.err.println(cmp[Arrays.binarySearch(cand, 0, szCand, "0123")][Arrays.binarySearch(cand, 0, szCand, "1230")]);
//            System.err.println(szCand * szCand * 1.);
//            System.err.println(4 * szCand * szCand / Math.pow(1024, 2));

            boolean[] isValid = new boolean[szCand];
            Arrays.fill(isValid, true);
            while (true) {
                int cntDelete = -1;
                int idBest = -1;

                long l = System.currentTimeMillis();
                for (int i = 0; i < szCand; i++) {
                    if (!isValid[i]) continue;
                    int[] cmp_i = cmp[i];
                    int val = (int) 1e9;
                    for (int b = 0; b < 4; b++) {
                        for (int c = 0; c + b <= 4; c++) {
                            int cntDel = 0;
                            for (int j = 0; j < szCand; j++) {
                                if (!isValid[j]) continue;
                                if (cmp_i[j] != ((b << 16) | c)) {
                                    ++cntDel;
                                }
                            }
                            val = Math.min(val, cntDel);
                        }
                    }
                    if (cntDelete < val) {
                        cntDelete = val;
                        idBest = i;
                    }
                }
//                System.err.println("TIME find:" + (System.currentTimeMillis() - l) / 1e3);

                System.out.println(cand[idBest]);

//                System.out.print("ALL: ");
//                for (int i = 0; i < szCand; i++)
//                    if (isValid[i])
//                        System.out.print(" " + cand[i]);
//                System.out.println();

                System.out.flush();

                int b = in.readInt();
                int c = in.readInt();
                if (b == 4 && c == 0) {
                    return;
                }


                for (int i = 0; i < szCand; i++) {
                    if (!isValid[i]) continue;
                    if (cmp[i][idBest] != ((b << 16) | c)) {
                        isValid[i] = false;
                    }
                }
            }
        }


        int timer = 0;
        int[] aa = new int['9' + 1];
        int[] bb = new int['9' + 1];

        private int cmp(String sa, String sb) {

            ++timer;

            int cntB = 0;
            for (int i = 0; i < 4; i++) {
                if (sa.charAt(i) == sb.charAt(i)) {
                    ++cntB;
                } else {
                    aa[sa.charAt(i)] = timer;
                    bb[sb.charAt(i)] = timer;
                }
            }
            int cntCow = 0;
            for (int i = '0'; i <= '9'; i++) {
                if (aa[i] == bb[i] && bb[i] == timer)
                    ++cntCow;
            }
            return (cntB << 16) | cntCow;
        }


    }

    static interface IntComparator {
        public int compare(int first, int second);

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

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

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

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

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

        public int readInt() {
            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 InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

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

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static interface IntCollection extends IntStream {
    }

    static class IntSplaySet implements IntSet {
        protected int[] value;
        protected int[] left;
        protected int[] right;
        protected int[] parent;
        private int[] size;
        private final IntComparator comparator;
        private int nextFree;
        protected int root = -1;

        public IntSplaySet() {
            this(null);
        }

        public IntSplaySet(IntComparator comparator) {
            this(comparator, 5);
        }

        public IntSplaySet(int capacity) {
            this(null, capacity);
        }

        public IntSplaySet(IntComparator comparator, int capacity) {
            this.comparator = comparator;
            value = new int[capacity];
            left = new int[capacity];
            right = new int[capacity];
            parent = new int[capacity];
            size = new int[capacity];
        }

        protected final int compare(int first, int second) {
            if (comparator == null) {
                return (first < second) ? -1 : ((first == second) ? 0 : 1);
            } else {
                return comparator.compare(first, second);
            }
        }


        public IntIterator intIterator() {
            return new IntIterator() {
                private boolean first = true;
                private boolean exhausted = root == -1;


                public int value() throws NoSuchElementException {
                    if (first) {
                        if (root == -1) {
                            throw new NoSuchElementException();
                        }
                        int leftmost = leftmost(root);
                        splay(leftmost);
                        first = false;
                    }
                    return value[root];
                }


                public boolean advance() throws NoSuchElementException {
                    if ((root == -1) || exhausted) {
                        throw new NoSuchElementException();
                    }
                    int next = leftmost(right[root]);
                    if (next == -1) {
                        exhausted = true;
                        return false;
                    }
                    splay(next);
                    return true;
                }


                public boolean isValid() {
                    return !exhausted;
                }


                public void remove() throws NoSuchElementException {
                    throw new UnsupportedOperationException();
                }
            };
        }

        private void splay(int node) {
            if (node == -1) {
                return;
            }
            while (parent[node] != -1) {
                if (parent[parent[node]] == -1) {
                    rotate(node);
                } else if ((left[parent[node]] == node) == (left[parent[parent[node]]] == parent[node])) {
                    rotate(parent[node]);
                    rotate(node);
                } else {
                    rotate(node);
                    rotate(node);
                }
            }
            this.root = node;
        }

        private void rotate(int node) {
            int cParent = parent[node];
            if (node == left[cParent]) {
                setLeft(cParent, right[node]);
                if (parent[cParent] != -1) {
                    if (cParent == left[parent[cParent]]) {
                        setLeft(parent[cParent], node);
                    } else {
                        setRight(parent[cParent], node);
                    }
                } else {
                    parent[node] = -1;
                }
                setRight(node, cParent);
            } else {
                setRight(cParent, left[node]);
                if (parent[cParent] != -1) {
                    if (cParent == left[parent[cParent]]) {
                        setLeft(parent[cParent], node);
                    } else {
                        setRight(parent[cParent], node);
                    }
                } else {
                    parent[node] = -1;
                }
                setLeft(node, cParent);
            }
            update(cParent);
            update(node);
        }

        protected void update(int node) {
            size[node] = size(left[node]) + size(right[node]) + 1;
        }

        protected int size(int node) {
            if (node != -1) {
                return size[node];
            }
            return 0;
        }

        protected int leftmost(int root) {
            if (root == -1) {
                return -1;
            }
            while (left[root] != -1) {
                root = left[root];
            }
            return root;
        }


        public int size() {
            return size(root);
        }


        public void add(int value) {
            if (contains(value)) {
                return;
            }
            ensureCapacity(nextFree + 1);
            IntSplaySet.Split roots = split(root, value);
            setLeft(nextFree, roots.left);
            setRight(nextFree, roots.right);
            parent[nextFree] = -1;
            this.value[nextFree] = value;
            update(nextFree);
            root = nextFree++;
        }

        private void setLeft(int node, int child) {
            left[node] = child;
            if (child != -1) {
                parent[child] = node;
            }
        }

        private void setRight(int node, int child) {
            right[node] = child;
            if (child != -1) {
                parent[child] = node;
            }
        }

        protected IntSplaySet.Split split(int root, int value) {
            if (root == -1) {
                return new IntSplaySet.Split();
            }
            int compare = compare(this.value[root], value);
            if (compare < 0) {
                IntSplaySet.Split result = split(right[root], value);
                setRight(root, result.left);
                result.left = root;
                update(root);
                behead(root);
                return result;
            } else if (compare > 0) {
                IntSplaySet.Split result = split(left[root], value);
                setLeft(root, result.right);
                result.right = root;
                update(root);
                behead(root);
                return result;
            } else {
                IntSplaySet.Split result = new IntSplaySet.Split();
                result.left = left[root];
                result.right = right[root];
                behead(left[root]);
                behead(right[root]);
                return result;
            }
        }

        protected int ensureCapacity(int capacity) {
            if (parent.length < capacity) {
                capacity = Math.max(2 * parent.length, capacity);
                left = Arrays.copyOf(left, capacity);
                right = Arrays.copyOf(right, capacity);
                parent = Arrays.copyOf(parent, capacity);
                size = Arrays.copyOf(size, capacity);
                value = Arrays.copyOf(value, capacity);
                return capacity;
            }
            return parent.length;
        }


        public boolean contains(int value) {
            int node = root;
            int lastNode = -1;
            while (node != -1) {
                lastNode = node;
                int compare = compare(value, this.value[node]);
                if (compare == 0) {
                    splay(node);
                    return true;
                }
                if (compare < 0) {
                    node = left[node];
                } else {
                    node = right[node];
                }
            }
            if (lastNode != -1) {
                splay(lastNode);
            }
            return false;
        }

        protected void behead(int node) {
            if (node != -1) {
                parent[node] = -1;
            }
        }

        protected static class Split {
            protected int left = -1;
            protected int right = -1;

        }

    }

    static interface IntIterator {
        public int value() throws NoSuchElementException;

        public boolean advance();

        public boolean isValid();

    }

    static interface IntSet extends IntCollection {
    }

    static interface IntStream extends Iterable<Integer>, Comparable<IntStream> {
        public IntIterator intIterator();

        default public Iterator<Integer> iterator() {
            return new Iterator<Integer>() {
                private IntIterator it = intIterator();

                public boolean hasNext() {
                    return it.isValid();
                }

                public Integer next() {
                    int result = it.value();
                    it.advance();
                    return result;
                }
            };
        }

        default public int compareTo(IntStream c) {
            IntIterator it = intIterator();
            IntIterator jt = c.intIterator();
            while (it.isValid() && jt.isValid()) {
                int i = it.value();
                int j = jt.value();
                if (i < j) {
                    return -1;
                } else if (i > j) {
                    return 1;
                }
                it.advance();
                jt.advance();
            }
            if (it.isValid()) {
                return 1;
            }
            if (jt.isValid()) {
                return -1;
            }
            return 0;
        }

    }
}