Problem: <image>

William is hosting a party for n of his trader friends. They started a discussion on various currencies they trade, but there's an issue: not all of his trader friends like every currency. They like some currencies, but not others.

For each William's friend i it is known whether he likes currency j. There are m currencies in total. It is also known that a trader may not like more than p currencies.

Because friends need to have some common topic for discussions they need to find the largest by cardinality (possibly empty) subset of currencies, such that there are at least ⌈ n/2 ⌉ friends (rounded up) who like each currency in this subset.

Input

The first line contains three integers n, m and p (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ p ≤ m ≤ 60, 1 ≤ p ≤ 15), which is the number of trader friends, the number of currencies, the maximum number of currencies each friend can like.

Each of the next n lines contain m characters. The j-th character of i-th line is 1 if friend i likes the currency j and 0 otherwise. It is guaranteed that the number of ones in each line does not exceed p.

Output

Print a string of length m, which defines the subset of currencies of the maximum size, which are liked by at least half of all friends. Currencies belonging to this subset must be signified by the character 1.

If there are multiple answers, print any.

Examples

Input


3 4 3
1000
0110
1001


Output


1000


Input


5 5 4
11001
10101
10010
01110
11011


Output


10001

Note

In the first sample test case only the first currency is liked by at least ⌈ 3/2 ⌉ = 2 friends, therefore it's easy to demonstrate that a better answer cannot be found.

In the second sample test case the answer includes 2 currencies and will be liked by friends 1, 2, and 5. For this test case there are other currencies that are liked by at least half of the friends, but using them we cannot achieve a larger subset size.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.LinkedHashMap;
import java.util.Map;
import java.io.Writer;
import java.util.Map.Entry;
import java.io.OutputStreamWriter;
import java.util.BitSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        static int numFriends;
        static int numCurrencies;
        static int maxCoins = 0;
        static TaskD.LRUMap<BitSet, Integer> bestPossible = new TaskD.LRUMap<>(0, 7200);

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            maxCoins = 0;
            this.numFriends = in.nextInt();
            this.numCurrencies = in.nextInt();
            bestPossible = new TaskD.LRUMap<>(0, 7200);
            int maxCurrenciesPerFriend = in.nextInt();

            // only want currencies liked by more than half the people
            // can we just start intersecting currencies?
            // greedy search, a = 90000
            // b = 30000
            // we want a currency with the maximum number of intersections

            // identical currency problem?
            BitSet[] friends = new BitSet[numFriends];
            for (int i = 0; i < numFriends; i++) {
                String s = in.readLine();
                BitSet friendSet = new BitSet();
                for (int j = 0; j < s.length(); j++) {
                    friendSet.set(j, s.charAt(j) == '1');
                }

                friends[i] = friendSet;
            }

            BitSet[] currencies = new BitSet[numCurrencies];
            for (int i = 0; i < numCurrencies; i++) {
                currencies[i] = new BitSet(numFriends);
            }

            for (int i = 0; i < numFriends; i++) {
                for (int j = 0; j < numCurrencies; j++) {
                    currencies[j].set(i, friends[i].get(j));
                }
            }

            int minFriends = numFriends / 2 + numFriends % 2;

            HashMap<BitSet, Integer> SetToCard = new HashMap<>();
            BitSet includedFriends = new BitSet(numFriends);
            includedFriends.set(0, numFriends);
            BitSet includedCurrencies = new BitSet(numCurrencies);
            BitSet maxCurrencies = new BitSet();

            // sort currencies by cardinality.
            BitSetPair[] bitSetCardinalitySorted = new BitSetPair[numCurrencies];
            for (int i = 0; i < numCurrencies; i++) {
                BitSetPair b = new BitSetPair();
                b.idx = i;
                b.b = currencies[i];
                bitSetCardinalitySorted[i] = b;
            }
            Arrays.sort(bitSetCardinalitySorted);

            // best possible pruning
            for (int i = 0; i < numCurrencies; i++) {
                BitSet newSet = search(currencies, includedCurrencies, includedFriends, i, minFriends, bitSetCardinalitySorted);
                if (maxCurrencies.cardinality() < newSet.cardinality()) {
                    maxCurrencies = newSet;
                }
            }

            for (int i = 0; i < numCurrencies; i++) {
                if (maxCurrencies.get(i)) {
                    out.print(1);
                } else {
                    out.print(0);
                }
            }
            out.println();

        }

        private static BitSet search(BitSet[] currencies, BitSet currentCurrencies, BitSet prevPlayers, int idxAdded, int minFriends, BitSetPair[] sort) {
            // we want the biggest one we can get before the number of players goes to 0.
            // find number of players

            int added = sort[idxAdded].idx;

            BitSet myCurrency = (BitSet) currentCurrencies.clone();
            myCurrency.set(added);
            BitSet allPlayers = (BitSet) prevPlayers.clone();
            allPlayers.and(currencies[added]);
            if (allPlayers.cardinality() < minFriends) {
                return new BitSet(numCurrencies);
            }

            // what if there aren't enough currencies left to beat out the current maxCurrencies?
            int remainingCurrencies = numCurrencies - 1 - idxAdded;
            if (remainingCurrencies + myCurrency.cardinality() <= maxCoins) {
                return new BitSet(numCurrencies);
            }

            // this is important here, can we do some trick to determine how many are left?

            // lets use the memoization
            Integer memo = bestPossible.get(allPlayers);
            // bitSet representation of players, what happens if its sparse? what happens of its big?
            // given our current set of players, this is the a set we've seen before
            if (memo != null && myCurrency.cardinality() <= memo) {
                return new BitSet(numCurrencies);
            }
            bestPossible.put(allPlayers, myCurrency.cardinality());

            BitSet maxCurrencies = myCurrency;
            for (int i = idxAdded + 1; i < currencies.length; i++) {
                BitSet newSet = search(currencies, myCurrency, allPlayers, i, minFriends, sort);
                if (newSet.cardinality() > maxCurrencies.cardinality()) {
                    maxCurrencies = newSet;
                }
            }
            maxCoins = Math.max(maxCoins, maxCurrencies.cardinality());
            return maxCurrencies;
        }

        private class BitSetPair implements Comparable<BitSetPair> {
            int idx;
            BitSet b;

            public int compareTo(BitSetPair o) {
                return Integer.compare(b.cardinality(), o.b.cardinality());
            }

        }

        private static class LRUMap<K, V> extends LinkedHashMap<K, V> {
            protected final int _maxEntries;

            public LRUMap(int initialEntries, int maxEntries) {
                super(initialEntries, 0.8f, true);
                _maxEntries = maxEntries;
            }

            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > _maxEntries;
            }

        }

    }

    static interface NotNull {
    }

    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 println() {
            writer.println();
        }

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

        public void print(int i) {
            writer.print(i);
        }

    }

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

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

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

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

        }

    }
}