n,k = map(int, raw_input().split())
print (n/(k+1))*2 + min(2, n%(k+1))

Just do it. This is O(10! * |s|) ~ 3*10^8. This is fast enough in some languages.

#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define fore(i, b, e) for (int i = (int)(b); i <= (int)(e); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long i64;
typedef unsigned long long u64;
typedef long double ld;
typedef long long ll;

const int maxn = 105;

int n;
int a[maxn];
int p[maxn];

bool check() {
    int cur = 0;
    forn(i, n) {
        if (p[a[i]] == cur) ++cur;
    }
    return cur == 10;
}

int main() {
#ifdef LOCAL
    freopen("b.in", "r", stdin);
#endif

    char c;
    while (cin >> c) { a[n++] = c-'0'; }
    forn(i, 10) p[i] = i;
    int cnt = 0;
    do {
        cnt += check();
    } while (next_permutation(p, p+10));
    cout << cnt << endl;

#ifdef LOCAL
    cerr << "Time elapsed: " << clock() / 1000 << " ms" << endl;
#endif
    return 0;
}

We can do a bitmask dp. We need to be careful not to double count, so we advance our index to the first occurence of some character to take it. See the code for more details.

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int N = 105;
vector<int> pos[N];

char buf[N];

const int MSK = 1 << 10;
int D[MSK][N];

const int K = 10;

int main() {
    scanf("%s", buf);
    int n = strlen(buf);
    for (int i = 0; i < n; i++) {
        pos[buf[i] - '0'].push_back(i);
    }
    D[0][0] = 1;
    for (int msk = 0; msk < MSK - 1; msk++) {
        for (int i = 0; i < K; i++) {
            if ((msk >> i) & 1) {
                continue;
            }
            for (int j = 0; j <= n + 1; j++) {
                if (j == n + 1) {
                    D[msk | (1 << i)][j] += D[msk][j];
                } else {
                    int p = lower_bound(pos[i].begin(), pos[i].end(), j) - pos[i].begin();
                    if (p == pos[i].size()) {
                        p = n + 1;
                    } else {
                        p = pos[i][p];
                    }
                    D[msk | (1 << i)][p + 1] += D[msk][j];
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans += D[MSK - 1][i];
    }
    printf("%d\n", ans);
}

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <vector>
using namespace std;

const int MOD = 1000 * 1000 * 1000 + 7;

inline int add(int a, int b) {
    if ((a += b) >= MOD) {
        a -= MOD;
    }
    return a;
}

typedef long long llong;

inline int mul(int a, int b) {
    return ((llong)a) * b % MOD;
}

inline int sub(int a, int b) {
    if ((a -= b) < 0) {
        a += MOD;
    }
    return a;
}

int powmod(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return powmod(x, MOD - 2);
}

const int N = 100500;

int V[N];

vector<int> history[N];

int AF[N];

void die() {
    puts("-1");
    exit(0);
}

int pw2[N];

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &V[i]);
    }
    for (int i = 0; i < k; i++) {
        int s;
        scanf("%d", &s);
        --s;
        history[s].push_back(i);
    }
    pw2[0] = 1;
    for (int i = 0; i < k; i++) {
        pw2[i + 1] = (pw2[i] % 2 == 0) ? pw2[i] / 2 : (pw2[i] + MOD) / 2;
    }

    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        if (history[a].size() > history[b].size()) {
            swap(a, b);
        }
        if (history[b].empty()) {
            continue;
        } else if (history[a].empty()) {
            if (V[a] == 0) {
                continue;
            } else {
                die();
            }
        } else {
            int prv = 0;
            for (int i = 0; i < (int)history[a].size(); i++) {
                int x = history[a][i];
                int p = lower_bound(history[b].begin(), history[b].end(), x) - history[b].begin();
                AF[b] = add(AF[b], pw2[p]);
                AF[a] = add(AF[a], mul(p - prv, pw2[i]));
                prv = p;
            }
            AF[a] = add(AF[a], mul((int)history[b].size() - prv, pw2[(int)history[a].size()]));
        }
    }

    int ans = 0;

    for (int i = 0; i < n; i++) {
        if (AF[i] != 0) {
            assert(!history[i].empty());
        }
        int k = pw2[(int)history[i].size()];
        int num = mul(AF[i], V[i]);
        int den = sub(1, k);
        ans = add(ans, mul(num, inv(den)));
    }
    printf("%d\n", ans);
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.stream.Stream;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Collections;
import java.util.ArrayList;
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);
        InfiniteGraphGame solver = new InfiniteGraphGame();
        solver.solve(1, in, out);
        out.close();
    }

    static class InfiniteGraphGame {
        public int mod = 1000000007;
        int[] cc;
        int[] sz;
        ArrayList<Integer>[] pos;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
            int[] v = in.readIntArray(n);
            int[] s = in.readIntArray(k);
            for (int i = 0; i < k; i++) s[i]--;
            pos = Stream.generate(ArrayList::new).limit(n).toArray(ArrayList[]::new);
            for (int i = 0; i < n; i++) pos[i].add(0);
            cc = new int[k + 1];
            sz = new int[n];
            for (int i = 1; i <= k; i++) {
                cc[i] = pos[s[i - 1]].size();
                pos[s[i - 1]].add(i);
                sz[s[i - 1]]++;
            }

            long[] div2 = new long[k + 1];
            div2[0] = 1;
            long mult = Utils.inv(2, mod);
            for (int i = 1; i < div2.length; i++) {
                div2[i] = div2[i - 1] * mult % mod;
            }

            long ans = 0;
            for (int i = 0; i < m; i++) {
                int a = in.nextInt() - 1, b = in.nextInt() - 1;
                if (sz[a] > sz[b]) {
                    int t = a;
                    a = b;
                    b = t;
                }
                if (sz[b] > 0 && sz[a] == 0 && v[a] > 0) {
                    out.println(-1);
                    return;
                }

                long sa = 0, sb = 0;
                int da = 0, db = 0;
                int lastw = 0;
                for (int q : pos[a]) {
                    if (q == 0) continue;
                    int curw = cc[pos[b].get(-Collections.binarySearch(pos[b], q) - 2)];
                    long w = curw - lastw;
                    lastw = curw;

                    sa = (sa + 1L * w * v[a] % mod * div2[da]) % mod;
                    db += w;
                    sb = (sb + v[b] * div2[db]) % mod;
                    da++;
                }
                {
                    long w = sz[b] - lastw;
                    sa = (sa + 1L * w * v[a] % mod * div2[da]) % mod;
                    db += w;
                }

                sa = sa * Utils.inv(1 - div2[da] + mod, mod) % mod;
                sb = sb * Utils.inv(1 - div2[db] + mod, mod) % mod;
                ans = (ans + sa + sb) % mod;
            }
            out.println(ans);
        }

    }

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

        public void println(long i) {
            writer.println(i);
        }

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

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar;
        private int numChars;

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

        public int[] readIntArray(int tokens) {
            int[] ret = new int[tokens];
            for (int i = 0; i < tokens; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    static class Utils {
        public static long inv(long N, long M) {
            long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M;
            while (b != 0) {
                q = a / b;
                t = a % b;
                a = b;
                b = t;
                t = x;
                x = lastx - q * x;
                lastx = t;
                t = y;
                y = lasty - q * y;
                lasty = t;
            }
            return (lastx + M) % M;
        }

    }
}

For an O(n⁴) solution, we can check all O(n^2) substrings. Now, we want to know if this string can stamp out the entire string. We can do this with dp. Let dp[i][j] be true if it is possible to stamp out the prefix 1, ..., i with (j + 1, ..., m) possibly left over the right edge. You can see the code below on how to update the dp table. This takes O(m^2) time per string so overall runtime is O(n^4) with a fairly low constant. We can get some more constant factor optimizations by doing some early breaks.

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define fore(i, b, e) for (int i = (int)(b); i <= (int)(e); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long i64;
typedef unsigned long long u64;
typedef long double ld;
typedef long long ll;

const int maxn = 500;

int n, m;
string s;
string t;
char d[maxn][maxn];

void scan() {
    cin >> s;
    n = s.size();
}

bool check() {
    memset(d, 0, sizeof d);
    m = t.size();
    if (s[0] != t[0]) return false;
    d[1][1] = 1;
    fore(i, 2, n) fore(j, 1, m) if (t[j-1] == s[i-1]) {
        if (d[i-1][j-1]) d[i][j] = 1;
        if (d[i-1][m]) d[i][j] = 1;
        if (j == 1) fore(k, 1, m-1) if (d[i-1][k]) { d[i][j] = 1; break; }
    }
    return d[n][m];
}

void solve() {
    set<string> res;
    set<string> seen;
    forn(i, n) forn(len, n-i+1) if (len) {
        t = s.substr(i, len);
        if (seen.count(t)) continue;
        seen.insert(t);
        if (check()) res.insert(t);
    }
    for (auto s: res) {
        cout << s << "\n";
    }
}

int main() {
#ifdef LOCAL
    freopen("e.in", "r", stdin);
#endif

    scan();
    solve();

#ifdef LOCAL
    cerr << "Time elapsed: " << clock() / 1000 << " ms" << endl;
#endif
    return 0;
}

For an O(n³·logn) solution, consider all occurences of t in s (these can be found in O(|s| + |t|) time). Then, consider extending a region as far as we can left by prepending a prefix of t, and extending a region as far as we can to the right by appending a suffix of t. This can be done with a stack or segment trees. Then, we have a set of intervals, and we want to check it covers 1, ..., n. This can also be done in time after sorting. Note, there is some tricky case in that if there can be gaps between the intervals, but these gaps need to consist of substrings of t. This can also be checked in linear time using suffix automaton.

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.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.io.InputStream;

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

    static class StampStampStamp {
        String s;
        SegmentTreeFast st;
        int[] r1;
        int[] r2;
        int[] left;
        int[] right;
        Pair<Integer, Integer>[] pp;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            s = in.next();
            int n = s.length();
            r1 = new int[n];
            r2 = new int[n];
            left = new int[n];
            right = new int[n];
            st = new SegmentTreeFast(n);
            pp = new Pair[n];
            HashSet<String> ss = new HashSet<>();
            HashSet<String> t = new HashSet<>();
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    String test = s.substring(i, j + 1);
                    if (t.add(test) && ok(test, s)) {
                        ss.add(test);
                    }
                }
            }
            ArrayList<String> ans = new ArrayList<>(ss);
            Collections.sort(ans);
            for (String x : ans) out.println(x);
        }

        boolean ok(String sub, String all) {
            if (sub.charAt(0) != all.charAt(0) || sub.charAt(sub.length() - 1) != all.charAt(all.length() - 1))
                return false;
            HashSet<Character> tt = new HashSet<>();
            for (char k : sub.toCharArray()) tt.add(k);
            for (char k : all.toCharArray()) if (!tt.contains(k)) return false;
            char[] c1 = (sub + "*" + all).toCharArray();
            int[] z1 = ZAlgorithm.zAlgorithm(c1);
            char[] c2 = (new StringBuffer(sub).reverse().toString() + "*" +
                    new StringBuffer(all).reverse().toString()).toCharArray();
            int[] z2 = ZAlgorithm.zAlgorithm(c2);

            int m = sub.length();
            int n = all.length();
            st.clear();
            for (int i = n - 1; i >= 0; i--) {
                int z = z1[i + m + 1];
                if (z == 0) {
                    r1[i] = -1;
                } else {
                    r1[i] = Math.max(i + z - 1, st.query(i + 1, i + z));
                }
                st.modify(i, i, r1[i]);
                pp[i] = new Pair(-r1[i], i);
            }
            Arrays.sort(pp);
            int idx = 0;
            int min = n;
            for (int i = n - 1; i >= 0; i--) {
                while (idx < n && -pp[idx].u >= i) {
                    min = Math.min(min, pp[idx].v);
                    idx++;
                }
                left[i] = Math.min(min, i + 1);
            }

            st.clear();
            int[] right = new int[n];
            for (int i = 0; i < n; i++) {
                int z = z2[n - i - 1 + m + 1];
                if (z == 0) {
                    r2[i] = n + 1;
                } else {
                    r2[i] = Math.min(i - z + 1, -st.query(i - z, i - 1));
                }
                st.modify(i, i, -r2[i]);
                pp[i] = new Pair(r2[i], i);
            }
            Arrays.sort(pp);
            idx = 0;
            int max = -1;
            for (int i = 0; i < n; i++) {
                while (idx < n && pp[idx].u <= i) {
                    max = Math.max(max, pp[idx].v);
                    idx++;
                }
                right[i] = Math.max(i - 1, max);
            }

            ArrayList<Integer> evts = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                if (z1[i + m + 1] == m) {
                    evts.add((i == 0 ? 0 : left[i - 1]) * 2 + 0);
                    evts.add(right[i] * 2 + 1);
                }
            }
            Collections.sort(evts);
            SuffixAutomaton.State[] automaton = SuffixAutomaton.buildSuffixAutomaton(sub);
            int psum = 0;
            for (int i = 0; i + 1 < evts.size(); i++) {
                int k = evts.get(i);
                if (k % 2 == 0) psum++;
                else psum--;
                if (psum == 0) {
                    int cur = k / 2 + 1;
                    int nxt = evts.get(i + 1) / 2;
                    int node = 0;
                    for (int j = cur; j < nxt; j++) {
                        int next = automaton[node].next[all.charAt(j)];
                        if (next == -1) return false;
                        node = next;
                    }
                }
            }
            return evts.get(0) / 2 == 0 && evts.get(evts.size() - 1) / 2 == n - 1;
        }

    }

    static class ZAlgorithm {
        public static int[] zAlgorithm(char[] let) {
            int N = let.length;
            int[] z = new int[N];
            int L = 0, R = 0;
            for (int i = 1; i < N; i++) {
                if (i > R) {
                    L = R = i;
                    while (R < N && let[R - L] == let[R])
                        R++;
                    z[i] = R - L;
                    R--;
                } else {
                    int k = i - L;
                    if (z[k] < R - i + 1)
                        z[i] = z[k];
                    else {
                        L = i;
                        while (R < N && let[R - L] == let[R])
                            R++;
                        z[i] = R - L;
                        R--;
                    }
                }
            }
            z[0] = N;
            return z;
        }

    }

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

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

    }

    static class SuffixAutomaton {
        public static SuffixAutomaton.State[] buildSuffixAutomaton(CharSequence s) {
            int n = s.length();
            SuffixAutomaton.State[] st = new SuffixAutomaton.State[Math.max(2, 2 * n - 1)];
            st[0] = new SuffixAutomaton.State();
            st[0].suffLink = -1;
            int last = 0;
            int size = 1;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                int cur = size++;
                st[cur] = new SuffixAutomaton.State();
                st[cur].length = i + 1;
                st[cur].firstPos = i;
                int p = last;
                for (; p != -1 && st[p].next[c] == -1; p = st[p].suffLink) {
                    st[p].next[c] = cur;
                }
                if (p == -1) {
                    st[cur].suffLink = 0;
                } else {
                    int q = st[p].next[c];
                    if (st[p].length + 1 == st[q].length) {
                        st[cur].suffLink = q;
                    } else {
                        int clone = size++;
                        st[clone] = new SuffixAutomaton.State();
                        st[clone].length = st[p].length + 1;
                        System.arraycopy(st[q].next, 0, st[clone].next, 0, st[q].next.length);
                        st[clone].suffLink = st[q].suffLink;
                        for (; p != -1 && st[p].next[c] == q; p = st[p].suffLink) {
                            st[p].next[c] = clone;
                        }
                        st[q].suffLink = clone;
                        st[cur].suffLink = clone;
                    }
                }
                last = cur;
            }
            for (int i = 1; i < size; i++) {
                st[st[i].suffLink].invSuffLinks.add(i);
            }
            return Arrays.copyOf(st, size);
        }

        public static class State {
            public int length;
            public int suffLink;
            public List<Integer> invSuffLinks = new ArrayList<>(0);
            public int firstPos = -1;
            public int[] next = new int[128];

            {
                Arrays.fill(next, -1);
            }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar;
        private int numChars;

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

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public String next() {
            int c;
            while (isSpaceChar(c = this.read())) {
                ;
            }

            StringBuilder result = new StringBuilder();
            result.appendCodePoint(c);

            while (!isSpaceChar(c = this.read())) {
                result.appendCodePoint(c);
            }

            return result.toString();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    static class SegmentTreeFast {
        int[] value;
        int[] delta;

        public SegmentTreeFast(int n) {
            value = new int[2 * n];
            for (int i = 0; i < n; i++) {
                value[i + n] = getInitValue();
            }
            for (int i = 2 * n - 1; i > 1; i -= 2) {
                value[i >> 1] = queryOperation(value[i], value[i ^ 1]);
            }
            delta = new int[2 * n];
            Arrays.fill(delta, getNeutralDelta());
        }

        public void clear() {
            int n = value.length / 2;
            for (int i = 0; i < n; i++) {
                value[i + n] = getInitValue();
            }
            for (int i = 2 * n - 1; i > 1; i -= 2) {
                value[i >> 1] = queryOperation(value[i], value[i ^ 1]);
            }
            Arrays.fill(delta, getNeutralDelta());
        }

        int modifyOperation(int x, int y) {
            return Math.max(x, y);
        }

        int queryOperation(int leftValue, int rightValue) {
            return Math.max(leftValue, rightValue);
        }

        int deltaEffectOnSegment(int delta, int segmentLength) {
            if (delta == getNeutralDelta()) return getNeutralDelta();
            // Here you must write a fast equivalent of following slow code:
            // int result = delta;
            // for (int i = 1; i < segmentLength; i++) result = queryOperation(result, delta);
            // return result;
            return delta;
//        return delta * segmentLength;
        }

        int getNeutralDelta() {
            return -(1 << 29);
        }

        int getInitValue() {
            return -(1 << 29);
        }

        int joinValueWithDelta(int value, int delta) {
            if (delta == getNeutralDelta()) return value;
            return modifyOperation(value, delta);
        }

        int joinDeltas(int delta1, int delta2) {
            if (delta1 == getNeutralDelta()) return delta2;
            if (delta2 == getNeutralDelta()) return delta1;
            return modifyOperation(delta1, delta2);
        }

        void pushDelta(int i) {
            int d = 0;
            for (; (i >> d) > 0; d++) {
            }
            for (d -= 2; d >= 0; d--) {
                int x = i >> d;
                value[x >> 1] = joinNodeValueWithDelta(x >> 1, 1 << (d + 1));
                delta[x] = joinDeltas(delta[x], delta[x >> 1]);
                delta[x ^ 1] = joinDeltas(delta[x ^ 1], delta[x >> 1]);
                delta[x >> 1] = getNeutralDelta();
            }
        }

        int joinNodeValueWithDelta(int i, int len) {
            return joinValueWithDelta(value[i], deltaEffectOnSegment(delta[i], len));
        }

        public int query(int from, int to) {
            to = Math.min(to, value.length / 2 - 1);
            from = Math.max(from, 0);
            if (to < from) return getInitValue();
            from += value.length >> 1;
            to += value.length >> 1;
            pushDelta(from);
            pushDelta(to);
            int res = 0;
            boolean found = false;
            for (int len = 1; from <= to; from = (from + 1) >> 1, to = (to - 1) >> 1, len <<= 1) {
                if ((from & 1) != 0) {
                    res = found ? queryOperation(res, joinNodeValueWithDelta(from, len)) : joinNodeValueWithDelta(from, len);
                    found = true;
                }
                if ((to & 1) == 0) {
                    res = found ? queryOperation(res, joinNodeValueWithDelta(to, len)) : joinNodeValueWithDelta(to, len);
                    found = true;
                }
            }
            if (!found) throw new RuntimeException();
            return res;
        }

        public void modify(int from, int to, int delta) {
            if (from > to) return;
            from += value.length >> 1;
            to += value.length >> 1;
            pushDelta(from);
            pushDelta(to);
            int a = from;
            int b = to;
            for (; from <= to; from = (from + 1) >> 1, to = (to - 1) >> 1) {
                if ((from & 1) != 0) {
                    this.delta[from] = joinDeltas(this.delta[from], delta);
                }
                if ((to & 1) == 0) {
                    this.delta[to] = joinDeltas(this.delta[to], delta);
                }
            }
            for (int i = a, len = 1; i > 1; i >>= 1, len <<= 1) {
                value[i >> 1] = queryOperation(joinNodeValueWithDelta(i, len), joinNodeValueWithDelta(i ^ 1, len));
            }
            for (int i = b, len = 1; i > 1; i >>= 1, len <<= 1) {
                value[i >> 1] = queryOperation(joinNodeValueWithDelta(i, len), joinNodeValueWithDelta(i ^ 1, len));
            }
        }

    }

    static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
        public final U u;
        public final V v;

        public Pair(U u, V v) {
            this.u = u;
            this.v = v;
        }

        public int hashCode() {
            return (u == null ? 0 : u.hashCode() * 31) + (v == null ? 0 : v.hashCode());
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair<U, V> p = (Pair<U, V>) o;
            return (u == null ? p.u == null : u.equals(p.u)) && (v == null ? p.v == null : v.equals(p.v));
        }

        public int compareTo(Pair<U, V> b) {
            int cmpU = u.compareTo(b.u);
            return cmpU != 0 ? cmpU : v.compareTo(b.v);
        }

        public String toString() {
            return String.format("[Pair = (%s, %s)", u.toString(), v.toString());
        }

    }
}

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <cassert>
using namespace std;

const int N = 200500;

int B[N];

int W[N];

int bad = 0;

int getbad(int i) {
    return (W[2 * i] > 0 && W[2 * i + 1] > 0) ? 1 : 0;
}

void add(int i, int w) {
    bad -= getbad(i / 2);
    W[i] += w;
    bad += getbad(i / 2);
}

struct ev {
    int t;
    int i;
    int d;
    friend bool operator <(const ev& a, const ev& b) {
        return a.t < b.t;
    }
};

vector<ev> evts;

const int INF = 2e9 + 42;

void add(int l, int r, int i) {
    evts.emplace_back(ev{l, i, 1});
    evts.emplace_back(ev{r + 1, i, -1});
}

int A[N];

void die() {
    puts("-1");
    exit(0);
}

int T(int x) {
    return 2 * x + 1;
}

int F(int x) {
    return 2 * x;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }

    for (int i = 0; i < n; i++) {
        add(0, A[i] - 1, F(i));
    }
    bool f = false;
    for (int i = 0; i < n - 1; i++) {
        int a = A[i];
        int b = A[i + 1];
        int s = a + b;
        if (a == b) {
            add(0, s, F(i + 1));
            add(0, s, T(i));
            add(s, INF, F(i));
            add(s, INF, T(i + 1));
        } else if (a > b) {
            add(0, s, T(i));
            add(s, INF, T(i + 1));
        } else {
            add(0, s, F(i + 1));
            add(s, INF, F(i));
        }
    }

    add(0, -1, 0); // touch

    sort(evts.begin(), evts.end());

    int goodk = -1;

    for (int l = 0, r = 0; l < (int)evts.size(); l = r) {
        if (evts[l].t >= INF - 2) {
            break;
        }
        while (r < (int)evts.size() && evts[r].t == evts[l].t) {
            r++;
        }
        for (int i = l; i < r; i++) {
            add(evts[i].i, evts[i].d);
        }
        if (bad == 0) {
            goodk = evts[l].t;
            break;
        }
    }
    printf("%d\n", goodk);
    if (goodk != -1) {
        assert(W[2 * n] == 0 || W[2 * n + 1] == 0);
        for (int i = 0; i < n; i++) {
            assert(W[2 * i] == 0 || W[2 * i + 1] == 0);
            printf("%d ", (B[i] = ((W[2 * i] > 0) ? A[i] : goodk - A[i])));
        }
        printf("\n");
        for (int i = 0; i < n - 1; i++) {
            assert(B[i] < B[i + 1]);
        }
        for (int i = 0; i < n; i++) {
            assert(B[i] >= 0);
        }
    }
}

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.InputMismatchException;
import java.io.IOException;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Comparator;
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);
        YetAnotherBinaryMatrix solver = new YetAnotherBinaryMatrix();
        solver.solve(1, in, out);
        out.close();
    }

    static class YetAnotherBinaryMatrix {
        int n;
        int na;
        int nb;
        int[][] mat;
        int[] a;
        int[] b;
        long[] A;
        long[] nA;
        boolean[] ba;
        boolean[] bb;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            n = in.nextInt();
            na = in.nextInt();
            nb = in.nextInt();
            a = in.readIntArray(na);
            b = in.readIntArray(nb);
            ba = new boolean[n];
            for (int x : a) ba[x - 1] = true;
            bb = new boolean[n];
            for (int x : b) bb[x - 1] = true;
            mat = new int[n][n];
            for (int i = 0; i < n; i++) {
                char[] c = in.next().toCharArray();
                for (int j = 0; j < n; j++)
                    mat[i][j] = c[j] - '0';
            }
            A = new long[n];
            nA = new long[n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (ba[j]) A[i] = A[i] * 2 + mat[j][i];
                    else nA[i] = nA[i] * 2 + mat[j][i];
                }
            }
            Basis bs = new Basis();
            for (int i = 0; i < n; i++) bs.add(nA[i]);
            if (bs.size < n - na) {
                out.println(-1);
                return;
            }
            boolean[] ss = new boolean[n];
            while (true) {
                int[] x = findPath(ss);
                if (x == null) break;
                for (int j : x) {
                    ss[j] = !ss[j];
                }
            }
            int count = 0;
            for (boolean w : ss) if (w) count++;
            if (count != na) {
                out.println(-1);
                return;
            }
            count = 0;
            for (int i = 0; i < n; i++) {
                if (bb[i] && !ss[i]) {
                    out.println(-1);
                    return;
                } else if (ss[i] && !bb[i]) {
                    count++;
                }
            }

            out.println(count);
            int[] ret = new int[count];
            int idx = 0;
            for (int i = 0; i < n; i++) if (ss[i] && !bb[i]) ret[idx++] = i + 1;
            out.println(ret);
        }

        public boolean ok1(boolean[] ss) {
            Basis bs = new Basis();
            for (int j = 0; j < n; j++) {
                if (ss[j]) {
                    if (!bs.add(A[j]))
                        return false;
                }
            }
            return true;
        }

        public boolean ok2(boolean[] ss) {
            Basis bs = new Basis();
            for (int j = 0; j < n; j++) {
                if (!ss[j]) {
                    bs.add(nA[j]);
                }
            }
            return bs.size >= n - na;
        }

        public int[] findPath(boolean[] ss) {
            int nnodes = n + 2;
            List<Integer>[] graph = Stream.generate(ArrayList::new).limit(nnodes).toArray(List[]::new);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (!ss[i] && ss[j]) {
                        ss[i] = true;
                        ss[j] = false;
                        if (ok1(ss)) graph[i].add(j);
                        if (ok2(ss)) graph[j].add(i);
                        ss[i] = false;
                        ss[j] = true;
                    }
                }
            }

            for (int i = 0; i < n; i++) {
                if (!ss[i]) {
                    ss[i] = true;
                    if (ok2(ss)) graph[nnodes - 1].add(i);
                    if (ok1(ss)) graph[i].add(nnodes - 2);
                    ss[i] = false;
                }
            }


            int[] prev = new int[nnodes];
            int[] dist = new int[nnodes];
            Arrays.fill(prev, -1);
            Arrays.fill(dist, 1 << 25);
            TreeSet<Integer> ts = new TreeSet<>(Comparator.comparingInt(x -> dist[x] * (n + 10) + x));
            dist[nnodes - 1] = 0;
            ts.add(nnodes - 1);
            while (ts.size() > 0) {
                int f = ts.pollFirst();
                for (int nxt : graph[f]) {
                    int weight = (nxt < n ? 100 * (bb[nxt] ? -1 : 1) * (ss[nxt] ? -1 : 1) : 0) + 1;
                    if (dist[f] + weight < dist[nxt]) {
                        ts.remove(nxt);
                        dist[nxt] = dist[f] + weight;
                        prev[nxt] = f;
                        ts.add(nxt);
                    }
                }
            }
            if (prev[nnodes - 2] == -1) return null;
            int[] p = new int[nnodes];
            int cur = prev[nnodes - 2];
            int id = 0;
            do {
                p[id++] = cur;
                cur = prev[cur];
            } while (cur != nnodes - 1);

            return Arrays.copyOf(p, id);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar;
        private int numChars;

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

        public int[] readIntArray(int tokens) {
            int[] ret = new int[tokens];
            for (int i = 0; i < tokens; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public String next() {
            int c;
            while (isSpaceChar(c = this.read())) {
                ;
            }

            StringBuilder result = new StringBuilder();
            result.appendCodePoint(c);

            while (!isSpaceChar(c = this.read())) {
                result.appendCodePoint(c);
            }

            return result.toString();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    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(int[] array) {
            for (int i = 0; i < array.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(array[i]);
            }
        }

        public void println(int[] array) {
            print(array);
            writer.println();
        }

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

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

    }

    static class Basis {
        public int size;
        public long[] basis;

        public Basis() {
            basis = new long[100];
            size = 0;
        }

        public boolean add(long x) {
            for (int i = size - 1; i >= 0; i--) {
                x = Math.min(x, x ^ basis[i]);
            }
            if (x == 0) return false;
            basis[size++] = x;
            for (int i = size - 2; i >= 0; i--) {
                if (basis[i] > basis[i + 1]) {
                    long t = basis[i + 1];
                    basis[i + 1] = basis[i];
                    basis[i] = t;
                }
            }
            return true;
        }

    }
}

First solve: ksun48 at 00:01:01

Breakdown of results for submissions that passed pretests

OK 6427 (98.74%)
CHALLENGED 60 (0.92%)
WRONG_ANSWER 22 (0.34%)
TOTAL 6509

First solve: jonathanirvings, dotorya at 00:05:16

Breakdown of results for submissions that passed pretests

OK 4192 (83.72%)
WRONG_ANSWER 652 (13.02%)
CHALLENGED 126 (2.52%)
RUNTIME_ERROR 33 (0.66%)
TIME_LIMIT_EXCEEDED 4 (0.08%)
TOTAL 5007

First solve: ehnryx at 00:04:05

Breakdown of results for submissions that passed pretests

OK 2694 (63.81%)
WRONG_ANSWER 1064 (25.20%)
CHALLENGED 448 (10.61%)
RUNTIME_ERROR 11 (0.26%)
TIME_LIMIT_EXCEEDED 4 (0.09%)
MEMORY_LIMIT_EXCEEDED 1 (0.02%)
TOTAL 4222

First solve: dotorya at 00:16:46

Breakdown of results for submissions that passed pretests

OK 449 (99.78%)
WRONG_ANSWER 1 (0.22%)
TOTAL 450

First solve: Petr at 00:26:54

Breakdown of results for submissions that passed pretests

OK 166 (100.00%)
TOTAL 166

First solve: Petr at 00:38:32

Breakdown of results for submissions that passed pretests

OK 246 (90.44%)
WRONG_ANSWER 24 (8.82%)
RUNTIME_ERROR 2 (0.74%)
TOTAL 272

First solve: dotorya at 00:49:58

Breakdown of results for submissions that passed pretests

OK 46 (100.00%)
TOTAL 46

First solve: dotorya at 01:49:01

Breakdown of results for submissions that passed pretests

OK 10 (100.00%)
TOTAL 10

n,k = map(int, raw_input().split())

if n != 0:
	x = [n,0,n,2*n]
	if k == 0:
		print "Yes"
		print 0,0
	elif 1 <= k <= 3:
		print "Yes"
		print x[3-k], x[4-k]
	else:
		print "No"
else:
	if k == 0:
		print "Yes"
		print 1,1
	elif k == 1:
		print "Yes"
		print 0,1
	else:
		print "No"

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Collections;
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);
        RainbowRoad solver = new RainbowRoad();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class RainbowRoad {
        public List<RainbowRoad.Edge>[] edges;
        public int[] par;
        public int[] size;
        public int[] mn;
        public long[] ccolor;
        public int n;
        public int m;
        public int c;
        public boolean[] vis;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            n = in.nextInt();
            m = in.nextInt();
            c = in.nextInt();

            edges = new List[n];
            for (int i = 0; i < n; i++) edges[i] = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                int a = in.nextInt() - 1, b = in.nextInt() - 1;
                long c = in.nextLong();
                edges[a].add(new RainbowRoad.Edge(a, b, c));
                edges[b].add(new RainbowRoad.Edge(b, a, c));
            }

            int[] x = in.readIntArray(c);
            int[] y = in.readIntArray(c);
            for (int i = 0; i < c; i++) {
                x[i]--;
                y[i]--;
            }

            List<RainbowRoad.T> p = solve(x), q = solve(y);
            out.println(p.equals(q) ? "Possible" : "Impossible");
        }

        public List<RainbowRoad.T> solve(int[] arr) {
            par = new int[n];
            size = new int[n];
            mn = new int[n];
            ccolor = new long[n];

            for (int i = 0; i < n; i++) {
                par[i] = i;
                mn[i] = i;
                size[i] = 1;
                ccolor[i] = 0;
            }
            for (int j = 0; j < c; j++) {
                ccolor[arr[j]] |= 1L << j;
            }
            for (int xx = 0; xx < c; xx++) {
                vis = new boolean[n];
                for (int i = 0; i < n; i++) {
                    if (!vis[i] && ccolor[find(i)] != 0)
                        dfs(i);
                }
            }

            List<RainbowRoad.T> ret = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (find(i) == i && ccolor[i] != 0) {
                    ret.add(new RainbowRoad.T(mn[i], ccolor[i]));
                }
            }
            Collections.sort(ret);
            return ret;
        }

        public void dfs(int node) {
            if (vis[node]) return;
            vis[node] = true;
            for (RainbowRoad.Edge next : edges[node]) {
                if (join(next.a, next.b, next.c)) {
                    dfs(next.b);
                }
            }

        }

        public int find(int x) {
            return x == par[x] ? x : (par[x] = find(par[x]));
        }

        public boolean join(int a, int b, long c) {
            int x = find(a), y = find(b);
            if (x == y) return false;
            if ((ccolor[x] & c) != c && (ccolor[y] & c) != c) return false;

            if (size[x] < size[y]) {
                int t = x;
                x = y;
                y = t;
            }
            size[x] += size[y];
            mn[x] = Math.min(mn[x], mn[y]);
            par[y] = x;
            ccolor[x] |= ccolor[y];
            return true;
        }

        static class Edge {
            public int a;
            public int b;
            public long c;

            public Edge(int a, int b, long c) {
                this.a = a;
                this.b = b;
                this.c = c;
            }

        }

        static class T implements Comparable<RainbowRoad.T> {
            public long color;
            public int pos;

            public T(int pos, long color) {
                this.pos = pos;
                this.color = color;
            }


            public boolean equals(Object o) {
                if (!(o instanceof RainbowRoad.T)) return false;
                return ((RainbowRoad.T) o).pos == pos && ((RainbowRoad.T) o).color == color;
            }

            public int compareTo(RainbowRoad.T other) {
                return pos - other.pos;
            }

            public String toString() {
                return pos + " " + color;
            }

        }

    }

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

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

        public int[] readIntArray(int tokens) {
            int[] ret = new int[tokens];
            for (int i = 0; i < tokens; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public long nextLong() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            long res = 0L;

            while (c >= 48 && c <= 57) {
                res *= 10L;
                res += (long) (c - 48);
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * (long) sgn;
                }
            }

            throw new InputMismatchException();
        }

        public String next() {
            int c;
            while (isSpaceChar(c = this.read())) {
                ;
            }

            StringBuilder result = new StringBuilder();
            result.appendCodePoint(c);

            while (!isSpaceChar(c = this.read())) {
                result.appendCodePoint(c);
            }

            return result.toString();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

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

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

    }
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Collections;
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);
        WildcardWords solver = new WildcardWords();
        solver.solve(1, in, out);
        out.close();
    }

    static class WildcardWords {
        public HashMap<String, ArrayList<Integer>> mp;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            char[] s = in.next().toCharArray();
            mp = new HashMap<>();
            for (int i = 0; i < s.length; i++) {
                String cur = "";
                for (int j = i; j < i + 10 && j < s.length; j++) {
                    cur += s[j];

                    ArrayList<Integer> x = mp.get(cur);
                    if (x == null) {
                        mp.put(cur, x = new ArrayList<>());
                    }
                    x.add(i);
                }
            }

            int q = in.nextInt();
            while (q-- > 0) {
                int l = in.nextInt() - 1, r = in.nextInt();
                String w = in.next();
                if (!w.contains("*")) {
                    if (r - l != w.length()) {
                        out.println("No");
                        continue;
                    }
                    String ee = "";
                    for (int i = l; i < r; i++) ee += s[i];
                    out.println(ee.equals(w) ? "Yes" : "No");
                    continue;
                }
                String[] pat = w.split("\\*");
                int cur = l;
                if (w.charAt(0) != '*') {
                    // must start with pat[0]
                    int d = getPos(pat[0], cur);
                    if (d != cur) {
                        cur = 1 << 29;
                    } else {
                        cur = d + pat[0].length();
                    }
                }
                for (int i = 1; i < pat.length; i++) {
                    if (pat[i].equals("")) continue;
                    cur = next(pat[i], cur);
                }
                int c = pat.length - 1;
                out.println((w.charAt(w.length() - 1) == '*' ? cur <= r :
                        (cur <= r && getPos(pat[c], r - pat[c].length()) == r - pat[c].length())) ? "Yes" : "No");
            }
        }

        public int next(String s, int start) {
            if (start == 1 << 29) return 1 << 29;
            int k = getPos(s, start);
            if (k == 1 << 29) return k;
            return k + s.length();
        }

        public int getPos(String s, int start) {
            ArrayList<Integer> w = mp.get(s);
            if (w == null) {
                return 1 << 29;
            }
            int pos = Collections.binarySearch(w, start);
            if (pos < 0) pos = -pos - 1;
            if (pos == w.size()) {
                return 1 << 29;
            }
            return w.get(pos);
        }

    }

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

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

    }

    static class InputReader {
        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 (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public String next() {
            int c;
            while (isSpaceChar(c = this.read())) {
                ;
            }

            StringBuilder result = new StringBuilder();
            result.appendCodePoint(c);

            while (!isSpaceChar(c = this.read())) {
                result.appendCodePoint(c);
            }

            return result.toString();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }
}

n = int(raw_input())

D = dict()

def go(x, y):
    if not (x, y) in D:
        D[(x, y)] = 0
    D[(x, y)] = D[(x, y)] + 1
    if D[(x, y)] == 5:
        del D[(x, y)]
        go(x + 1, y)
        go(x, y + 1)
        go(x - 1, y)
        go(x, y - 1)

for i in range(n):
    x, y = map(int, raw_input().split())
    go(x, y)
    print len(D)

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
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);
        AvoidingAdjacent solver = new AvoidingAdjacent();
        solver.solve(1, in, out);
        out.close();
    }

    static class AvoidingAdjacent {
        public int mod = 1000000007;
        public int MAXN = 16 * 16 + 1;
        public int[][] w1;
        public long[] fact;
        public long[] ifact;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int c = in.nextInt();
            int[] arr = in.readIntArray(c);
            int s = AUtils.sum(arr);
            int[] x = in.readIntArray(s);
            for (int i = 0; i < s; i++) x[i]--;

            long[][] e = Factorials.getFIF(MAXN, mod);
            fact = e[0];
            ifact = e[1];
            w1 = new int[MAXN][MAXN];
            w1[0][0] = 1;
            for (int i = 1; i < MAXN; i++) {
                for (int j = 1; j < MAXN; j++) {
                    for (int k = 1; k <= i; k++) {
                        w1[i][j] += w1[i - k][j - 1];
                        if (w1[i][j] >= mod) w1[i][j] -= mod;
                    }
                }
            }

            int ans = 0;
            for (int i = 0; i < s; i++) {
                for (int j = 0; j < x[i]; j++) {
                    if (i > 0 && j == x[i - 1]) continue;
                    if (arr[j] > 0) {
                        arr[j]--;
                        int w = solve(arr, j);
                        ans += w;
                        if (ans >= mod) ans -= mod;
                        arr[j]++;
                    }
                }
                arr[x[i]]--;
            }

            out.println((ans + 1) % mod);
        }

        public int solve(int[] freq, int special) {
            int d = AUtils.sum(freq);
            int b = AUtils.max(freq);
            if (d == 0) return 1;
            if (d == freq[special]) return 0;
            if (b + b - 1 > d) return 0;
            int[] dp = new int[1];
            dp[0] = 1;
            for (int j = 0; j < freq.length; j++) {
                if (freq[j] == 0 || j == special) continue;
                int[] nxt = new int[dp.length + freq[j]];
                for (int pgr = 0; pgr < dp.length; pgr++) {
                    for (int cgr = 1; cgr <= freq[j]; cgr++) {
                        nxt[pgr + cgr] += 1L * dp[pgr] * w1[freq[j]][cgr] % mod * ifact[cgr] % mod;
                        if (nxt[pgr + cgr] >= mod) nxt[pgr + cgr] -= mod;
                    }
                }
                dp = nxt;
            }

            int res = 0;
            for (int i = 0; i < dp.length; i++) {
                if (freq[special] == 0) {
                    long x = 1L * dp[i] * fact[i] % mod;
                    if ((d - i) % 2 == 0) res += x;
                    else res -= x;
                    if (res >= mod) res -= mod;
                    if (res < 0) res += mod;
                } else {
                    for (int j = 1; j <= freq[special]; j++) {
                        long x = 1L * dp[i] * w1[freq[special]][j] % mod * ifact[j] % mod;
                        x = x * fact[i + j - 1] % mod * i % mod;

                        if ((d - i - j) % 2 == 0) res += x;
                        else res -= x;
                        if (res >= mod) res -= mod;
                        if (res < 0) res += mod;
                    }
                }
            }
            return res;
        }

    }

    static class AUtils {
        public static int max(int[] arr) {
            int res = arr[0];
            for (int x : arr) res = Math.max(res, x);
            return res;
        }

        public static int sum(int[] arr) {
            int sum = 0;
            for (int x : arr) {
                sum += x;
            }
            return sum;
        }

    }

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

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

    }

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

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

        public int[] readIntArray(int tokens) {
            int[] ret = new int[tokens];
            for (int i = 0; i < tokens; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        public int read() {
            if (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    static class Factorials {
        public static long[][] getFIF(int max, int mod) {
            long[] fact = new long[max];
            long[] ifact = new long[max];
            long[] inv = new long[max];
            inv[1] = 1;
            for (int i = 2; i < max; i++) {
                inv[i] = (mod - mod / i) * inv[mod % i] % mod;
            }
            fact[0] = 1;
            ifact[0] = 1;
            for (int i = 1; i < max; i++) {
                fact[i] = fact[i - 1] * i % mod;
                ifact[i] = ifact[i - 1] * inv[i] % mod;
            }
            return new long[][]{fact, ifact, inv};
        }

    }
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.List;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
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);
        TokenTree solver = new TokenTree();
        solver.solve(1, in, out);
        out.close();
    }

    static class TokenTree {
        int mod = 1000000007;
        int[] pow2;
        List<Integer>[] graph;
        int[] ans;
        int[] down;
        int[] up;
        int[] b1;
        int[] b2;
        int[] id;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            pow2 = new int[n + 1];
            pow2[0] = 1;
            for (int i = 1; i <= n; i++) {
                pow2[i] = (pow2[i - 1] << 1) % mod;
            }
            graph = new List[n];
            for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
            for (int i = 0; i < n - 1; i++) {
                int a = in.nextInt() - 1, b = in.nextInt() - 1;
                graph[a].add(b);
                graph[b].add(a);
            }
            ans = new int[n];
            b1 = new int[n];
            b2 = new int[n];
            id = new int[n];
            getFarthest();
            for (int i = 1; i < n; i++) {
                ans[0] += pow2[down[i]];
                if (ans[0] >= mod) ans[0] -= mod;
            }
            dfs3(0, -1);
            for (int i = 0; i < n; i++) {
                out.println(ans[i]);
            }
        }

        void dfs3(int node, int par) {
            for (int next : graph[node]) {
                if (next == par) continue;
                ans[next] = ans[node] - pow2[down[next]];
                if (ans[next] < 0) ans[next] += mod;
                int add = b1[node];
                if (id[node] == next) add = b2[node];
                ans[next] += pow2[add];
                if (ans[next] >= mod) ans[next] -= mod;
                dfs3(next, node);
            }
        }

        int[] getFarthest() {
            int n = graph.length;
            down = new int[n];
            up = new int[n];
            dfs(0, -1);
            dfs2(0, -1, 0);
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                ret[i] = Math.max(up[i], down[i]);
            }
            return ret;
        }

        void dfs(int node, int par) {
            for (int next : graph[node]) {
                if (next == par) continue;
                dfs(next, node);
                down[node] = Math.max(down[node], down[next] + 1);
            }
        }

        void dfs2(int node, int par, int frompar) {
            up[node] = frompar;
            b1[node] = up[node];
            id[node] = par;
            int mx1 = 0, id1 = -1, mx2 = 0;
            for (int next : graph[node]) {
                if (next == par) continue;
                if (down[next] + 1 > b1[node]) {
                    b2[node] = b1[node];
                    b1[node] = down[next] + 1;
                    id[node] = next;
                } else if (down[next] + 1 > b2[node]) {
                    b2[node] = down[next] + 1;
                }
                if (down[next] + 1 > mx1) {
                    mx2 = mx1;
                    mx1 = down[next] + 1;
                    id1 = next;
                } else if (down[next] + 1 > mx2) {
                    mx2 = down[next] + 1;
                }
            }

            for (int next : graph[node]) {
                if (next == par) continue;
                dfs2(next, node, Math.max(up[node], next == id1 ? mx2 : mx1) + 1);
            }
        }

    }

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

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

    }

    static class InputReader {
        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 (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }
}

print (lambda s: max((s[:i] + x + s[i+1:]).count("VK") for x in "VK" for i in range(len(s))))(raw_input())

print (lambda s: s.count("VK") + int(any(x*3 in "K" + s + "V" for x in "VK")))(raw_input())

x,y = raw_input(), raw_input()
print all(a>=b for a,b in zip(x,y)) * y or "-1"

#include <stdio.h>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
// Adjust MAXN for bounds
const ll MAXN=1e5+4;
// MAXV is the max amount of time we can take
const ld MAXV=1e18;
ll a[MAXN],b[MAXN];
ld exhaust[MAXN];
int n;
ll P;
bool f(ld imid) {
	ld needsum=0;
	for (int i=0;i<n;i++) {
		ld need=max(0.0L, (imid-exhaust[i])*a[i]);
		needsum+=need;
	}
	ld supply=imid*P;
	return supply>=needsum;
}
int main() 
{
	scanf("%d%lld",&n,&P);
	for (int i=0;i<n;i++) {
		scanf("%lld%lld",&a[i],&b[i]);
	}
	ll suma=0;
	for (int i=0;i<n;i++) {
		suma+=a[i];
	}
	if (P>=suma) {
		printf("-1\n");
		return 0;
	}
	for (int i=0;i<n;i++) {
		exhaust[i]=((ld)b[i])/((ld)a[i]);
	}
	ld imin=0,imax=MAXV;
	for (ll iter=0;iter<220;iter++) {
		ld imid=(imin+imax)/2;
		if (f(imid)) imin=imid;
		else imax=imid;
	}
	if (imax>MAXV-100) printf("-1\n");
	else printf("%.9f\n",(double)imin);
}

#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

typedef long double ld;
typedef long double ll;

ld K(ld a) { return a * a; }

struct P {
	ll x, y;
	void read() { cin >> x >> y; }
	P operator + (P b) { return P{x + b.x, y + b.y}; }
	P operator - (P b) { return P{x - b.x, y - b.y}; }
	P operator * (ld/*ll*/ mul) { return P{x * mul, y * mul}; }
	ll operator * (P b) { return x * b.y - y * b.x; }
	ll dot(P b) { return x * b.x + y * b.y; }
	ld len() { return sqrt(K(x) + K(y)); }
	P lenTo(ld to) { return *this * (to / len()); }
	ld dist(P & b) { return (*this - b).len(); }
};

struct L2 {
	P one, two;
	ld dist(P he) {
		return abs((he - one) * (he - two)) / one.dist(two);
	}
};

int main() {
	int n;
	cin >> n;
	vector<P> points(n);
	for(P & p : points)
		p.read();
	ld answer = 1e15;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < 2 * n; ++j)
			if(abs(i - j) <= 2)
				for(int k = 0; k < 2 * n; ++k)
					if(abs(i - k) <= 2 && (int) set<int>{i % n, j % n, k % n}.size() == 3)
						answer = min(answer, L2{points[i%n], points[j%n]}.dist(points[k%n]));
	printf("%.10lf\n", (double) answer / 2);
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
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);
        NonConvexPolygon solver = new NonConvexPolygon();
        solver.solve(1, in, out);
        out.close();
    }

    static class NonConvexPolygon {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            long[][] p = new long[n][2];
            for (int i = 0; i < n; i++) {
                p[i][0] = in.nextInt();
                p[i][1] = in.nextInt();
            }
            double ans = 1L << 60;
            for (int i = 0; i < n; i++) {
                int prev = (i + n - 1) % n, next = (i + 1) % n;
                ans = Math.min(ans, PointToSegmentDistance.pointToLineThroughTwoPointsDistance(
                        p[i][0], p[i][1], p[prev][0], p[prev][1], p[next][0], p[next][1]
                ) / 2.0);
            }
            out.printf("%.10f\n", ans);
        }

    }

    static class Utils {
        public static double cross(Point a, Point b, Point c) {
            Point ab = new Point(b.x - a.x, b.y - a.y);
            Point ac = new Point(c.x - a.x, c.y - a.y);
            return ab.x * ac.y - ab.y * ac.x;
        }

    }

    static class PointToSegmentDistance {
        static double fastHypot(double x, double y) {
            return Math.sqrt(x * x + y * y);
        }

        public static double pointToLineThroughTwoPointsDistance(long x, long y, long ax, long ay, long bx, long by) {
            double t = Utils.cross(new Point(ax, ay), new Point(bx, by), new Point(x, y));
            return Math.abs(t / fastHypot(ax - bx, ay - by));
        }

    }

    static class Point implements Comparable<Point> {
        public double x;
        public double y;
        public double angle;
        public int idx;

        public Point(double x, double y) {
            this.x = x;
            this.y = y;
            angle = 0;
        }

        public Point(double x, double y, int idx) {
            this.x = x;
            this.y = y;
            this.idx = idx;
        }

        public int compareTo(Point other) {
            return x == other.x ? (int) Math.signum(y - other.y) : (int) Math.signum(x - other.x);
        }

    }

    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 printf(String format, Object... objects) {
            writer.printf(format, objects);
        }

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

    }

    static class InputReader {
        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 (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }
}

#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int nax = 2e5 + 5;
bool forbidden[nax];

int my_gcd(int a, int b) {
	if(a == 0 || b == 0) return max(a, b); // return m
	return __gcd(a, b);
}
#define __gcd use____my_gcd

vector<int> which[nax];
pair<int,int> dp[nax];

int my_pow(int a, int b, int m) {
	int r = 1;
	while(b) {
		if(b % 2) r = (long long) r * a % m;
		a = (long long) a * a % m;
		b /= 2;
	}
	return r;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	while(n--) {
		int x;
		scanf("%d", &x);
		forbidden[x] = true;
	}
	#define n use_____m
	for(int i = 0; i < m; ++i)
		if(!forbidden[i])
			which[my_gcd(i, m)].push_back(i);
	if(forbidden[0])
		which[m].push_back(0); // hack
	for(int i = 1; i <= m; ++i)
		if(!which[i].empty()) {
			dp[i] = {0, 0};
			for(int j = 1; j < i; ++j)
				if(i % j == 0 && dp[j].first > 0)
					dp[i] = max(dp[i], make_pair(dp[j].first, j));
			dp[i].first += which[i].size();
		}
	vector<int> ans;
	int x = m;
	while(!which[x].empty()) {
		for(int y : which[x])
			ans.push_back(y);
		x = dp[x].second;
	}
	reverse(ans.begin(), ans.end());
	if(forbidden[0]) {
		assert(!ans.empty());
		ans.pop_back();
	}
	debug() << imie(ans);
	int previous = 1;
	printf("%d\n", (int) ans.size());
	
	int cnt_coprime = 0;
	for(int i = 2; i < m; ++i)
		if(my_gcd(i, m) == 1)
			++cnt_coprime;
	
	for(int nxt : ans) {
		if(nxt == 0) {
			printf("0");
			continue;
		}
		int a = previous / my_gcd(m, previous);
		int b = nxt / my_gcd(m, nxt);
		
		int print = (long long) b * my_pow(a, cnt_coprime, m) % m;
		print = (long long) print * my_gcd(m, nxt) / my_gcd(m, previous) % m;
		printf("%d ", print);
		previous = nxt;
	}
	puts("");
}

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.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
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);
        PrefixProductSequence solver = new PrefixProductSequence();
        solver.solve(1, in, out);
        out.close();
    }

    static class PrefixProductSequence {
        public int[] div;
        public boolean[] forbidden;
        public ArrayList<Long> ans;
        public int n;
        public int m;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            n = in.nextInt();
            m = in.nextInt();
            forbidden = new boolean[m + 1];
            for (int i = 0; i < n; i++) {
                forbidden[in.nextInt()] = true;
            }
            int[] add = new int[m + 1];
            for (int i = 0; i < m; i++) {
                if (!forbidden[i]) {
                    int g = Utils.gcd(i, m);
                    add[m / g]++;
                }
            }
            int[] arr = new int[m + 1];
            div = new int[m + 1];
            Arrays.fill(arr, 1);
            Arrays.setAll(div, x -> x);
            for (int i = 2; i <= m; i++) {
                arr[i] += add[i];
                for (int j = i + i; j <= m; j += i) {
                    if (arr[i] > arr[j]) {
                        arr[j] = arr[i];
                        div[j] = j / i;
                    }
                }
            }

            ans = new ArrayList<>();
            solve(1, 1);
            out.println(ans.size());
            boolean first = true;
            for (long x : ans) {
                if (!first) out.print(" ");
                out.print(x);
                first = false;
            }
            out.println();
        }

        public void solve(int cmult, long mm) {
            if (cmult == m) {
                if (!forbidden[0]) {
                    ans.add(0L);
                }
                return;
            }
            int prev = 1;
            boolean has = false;
            for (int i = 1; i < m / cmult; i++) {
                if (!forbidden[i * cmult] && Utils.gcd(m / cmult, i) == 1) {
                    long x = Utils.inv(prev, m / cmult) * i % m;
                    if (!has) {
                        has = true;
                        x = x * mm % m;
                    }
                    ans.add(x);
                    prev = i;
                }
            }
            long nmm = Utils.inv(prev, m / cmult) * div[m / cmult] % m;
            if (!has) nmm = nmm * mm % m;
            solve(cmult * div[m / cmult], nmm);
        }

    }

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

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

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

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

    }

    static class InputReader {
        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 (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    static class Utils {
        public static long inv(long N, long M) {
            long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M;
            while (b != 0) {
                q = a / b;
                t = a % b;
                a = b;
                b = t;
                t = x;
                x = lastx - q * x;
                lastx = t;
                t = y;
                y = lasty - q * y;
                lasty = t;
            }
            return (lastx + M) % M;
        }

        public static int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }

    }
}

// vvvvvvvvvvvvvvvvv Library code start

#include <array>


#define NDEBUG
NDEBUG


#include <algorithm>

#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <queue>
#include <random>


#define forn(t, i, n) for (t i = 0; i < (n); ++i)

#define rforn(t, i, n) for (t i = (n) - 1; i >= 0; --i)

#define all(c) c.begin(), c.end()


using namespace std;

/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);


// Section with adoption of array and vector algorithms.


// 32 bit ints (sum LSB + MSB == 32)


// TODO: Section with some container algorithms


#define ENABLE_IF(e) typename enable_if<e>::type* = nullptr

namespace template_util {
    template<class T>
    constexpr T min(T a, T b) {
        return a < b ? a : b;
    }

    
    constexpr int bytecount(uint64_t x) {
        return x ? 1 + bytecount(x >> 8) : 0;
    }

    /// caide keep
    template<int N>
    struct bytetype {
        typedef uint64_t type;
    };

    /// caide keep
    template<>
    struct bytetype<4> {
        typedef uint32_t type;
    };

    /// caide keep
    template<>
    struct bytetype<3> {
        
    };

    /// caide keep
    template<>
    struct bytetype<2> {
        
    };

    /// caide keep
    template<>
    struct bytetype<1> {
        typedef uint8_t type;
    };

    /// caide keep
    template<>
    struct bytetype<0> {
        typedef uint8_t type;
    };

    /// caide keep
    template<uint64_t N>
    struct minimal_uint : bytetype<bytecount(N)> {
    };
}


template<class T>
T next(istream& in) {
    T ret;
    in >> ret;
    return ret;
}

template<class T>
vector<T> next_vector(istream& in, size_t n) {
    vector<T> ret(n);
    for (size_t i = 0; i < n; ++i) {
        ret[i] = next<T>(in);
    }
    return ret;
}


#define dbg(...) ;


/*
TODOs:
 cache invs
 primitive root
 discrete log

 tests!!!
*/

namespace mod_impl {
    /// caide keep
    template <class T>
    constexpr inline T mod(T MOD) {
        return MOD;
    }

    /// caide keep
    template <class T>
    constexpr inline T mod(T* MOD) {
        return *MOD;
    }

    /// caide keep
    template <class T>
    constexpr inline T max_mod(T MOD) {
        return MOD - 1;
    }

    /// caide keep
    template <class T>
    constexpr inline T max_mod(T*) {
        return numeric_limits<T>::max() - 1;
    }

    
    constexpr inline uint64_t combine_max_sum(uint64_t a, uint64_t b) {
        return a > ~b ? 0 : a + b;
    }

    constexpr inline uint64_t combine_max_mul(uint64_t a, uint64_t b) {
        return a > numeric_limits<uint64_t>::max() / b ? 0 : a * b;
    }

    /// caide keep
    template <class T>
    constexpr inline uint64_t next_divisible(T mod, uint64_t max) {
        return max % mod == 0 ? max : combine_max_sum(max, mod - max % mod);
    }

    /// caide keep
    template <class T>
    constexpr inline uint64_t next_divisible(T*, uint64_t) {
        return 0;
    }

    //caide keep
    constexpr int IF_THRESHOLD = 2;

    template <class T, T MOD_VALUE, uint64_t MAX,
            class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
            ENABLE_IF(MAX <= max_mod(MOD_VALUE) && !is_pointer<T>::value)>
    inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
        return value;
    }

    template <class T, T MOD_VALUE, uint64_t MAX,
            class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
            ENABLE_IF(max_mod(MOD_VALUE) < MAX && MAX <= IF_THRESHOLD * max_mod(MOD_VALUE) && !is_pointer<T>::value)>
    inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
        while (value >= mod(MOD_VALUE)) {
            value -= mod(MOD_VALUE);
        }
        return (RET)value;
    }

    template <class T, T MOD_VALUE, uint64_t MAX,
             class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
             ENABLE_IF(IF_THRESHOLD * max_mod(MOD_VALUE) < MAX || is_pointer<T>::value)>
    inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
        return (RET)(value % mod(MOD_VALUE));
    }
}

#define MOD mod_impl::mod(MOD_VALUE)
#define MAX_MOD mod_impl::max_mod(MOD_VALUE)

struct DenormTag {};

template <class T, T MOD_VALUE, uint64_t MAX = MAX_MOD, ENABLE_IF(MAX_MOD >= 2)>
struct ModVal {
    typedef typename template_util::minimal_uint<MAX>::type storage;
    storage value;

    /// caide keep
    inline ModVal(): value(0) {
        assert(MOD >= 2);
    }

    
    inline ModVal(storage v, DenormTag): value(v) {
        assert(MOD >= 2);
        assert(v <= MAX);
    };

    inline operator ModVal<T, MOD_VALUE>() {
        return {v(), DenormTag()};
    };

    explicit inline operator uint64_t() const {
        return v();
    }

    typename template_util::minimal_uint<mod_impl::max_mod(MOD_VALUE)>::type v() const {
        return mod_impl::smart_mod<T, MOD_VALUE, MAX>(value);
    }
};

template <class T, T MOD_VALUE, uint64_t MAX,
        uint64_t NEW_MAX = mod_impl::next_divisible(MOD_VALUE, MAX),
        ENABLE_IF(NEW_MAX != 0),
        class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
inline Ret operator-(const ModVal<T, MOD_VALUE, MAX>& o) {
    static_assert(NEW_MAX <= numeric_limits<typename Ret::storage>::max(), "bad unary minus template");
    assert(NEW_MAX % MOD == 0 && o.value <= NEW_MAX);
    return {typename Ret::storage(NEW_MAX - o.value), DenormTag()};
}


template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
        uint64_t NEW_MAX = mod_impl::combine_max_sum(MAX1, MAX2),
        ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
inline Ret operator+(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) {
    return {typename Ret::storage(typename Ret::storage() + o1.value + o2.value), DenormTag()};
}


template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
        uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
        ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
inline Ret operator*(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) {
    return {typename Ret::storage(typename Ret::storage(1) * o1.value * o2.value), DenormTag()};
}

template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
        uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
        uint64_t NEW_MAX1 = mod_impl::combine_max_mul(MAX_MOD, template_util::min(MAX1, MAX2)),
        ENABLE_IF(NEW_MAX == 0 && NEW_MAX1 != 0 && MAX1 <= MAX2),
        class Ret = ModVal<T, MOD_VALUE, mod_impl::combine_max_mul(MAX1, MAX_MOD)>>
inline Ret operator*(const ModVal<T, MOD_VALUE, MAX1>& o1, const ModVal<T, MOD_VALUE, MAX2>& o2) {
    return {typename Ret::storage(typename Ret::storage(1) * o1.value * o2.v()), DenormTag()};
}

template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
        uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
        uint64_t NEW_MAX1 = mod_impl::combine_max_mul(MAX_MOD, template_util::min(MAX1, MAX2)),
        ENABLE_IF(NEW_MAX == 0 && NEW_MAX1 != 0 && MAX2 < MAX1),
        class Ret = ModVal<T, MOD_VALUE, mod_impl::combine_max_mul(MAX_MOD, MAX2)>>
inline Ret operator*(const ModVal<T, MOD_VALUE, MAX1>& o1, const ModVal<T, MOD_VALUE, MAX2>& o2) {
    return {typename Ret::storage(typename Ret::storage(1) * o1.v() * o2.value), DenormTag()};
}


template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2>
inline auto operator-(const ModVal<T, MOD_VALUE, MAX1>& lhs, const ModVal<T, MOD_VALUE, MAX2>& rhs) -> decltype(lhs + (-rhs)) {
    return lhs + (-rhs);
}

template <class T, T MOD_VALUE, uint64_t MAX>
inline ModVal<T, MOD_VALUE>& operator+=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) {
    lhs = lhs + rhs;
    return lhs;
}

template <class T, T MOD_VALUE, uint64_t MAX>
inline ModVal<T, MOD_VALUE>& operator-=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) {
    lhs = lhs - rhs;
    return lhs;
}


template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2>
inline bool operator!=(const ModVal<T, MOD_VALUE, MAX1>& lhs, const ModVal<T, MOD_VALUE, MAX2>& rhs) {
    return lhs.v() != rhs.v();
}


template <class T, T MOD_VALUE, class MOD_TYPE>
struct ModCompanion {
    typedef MOD_TYPE mod_type;
    typedef ModVal<mod_type, MOD_VALUE> type;
    

    template <uint64_t C>
    inline static constexpr ModVal<mod_type, MOD_VALUE, C> c() {
        return {C, DenormTag()};
    };

    template <uint64_t MAX = numeric_limits<uint64_t>::max()>
    inline static ModVal<mod_type, MOD_VALUE, MAX> wrap(uint64_t x) {
        assert(x <= MAX);
        return {typename ModVal<mod_type, MOD_VALUE, MAX>::storage(x), DenormTag()};
    };

    template <uint64_t MAX, ENABLE_IF(!is_pointer<T>::value && MAX <= MAX_MOD)>
    inline static ModVal<mod_type, MOD_VALUE> inv(const ModVal<mod_type, MOD_VALUE, MAX>& x) {
        if (x.value == 1) {
            return c<1>();
        }
        return -(wrap<MAX_MOD / 2>(MOD / x.value) * inv(wrap<MAX>(MOD % x.value)));
    };

    
};


#undef MOD
#undef MAX_MOD

template <uint64_t MOD_VALUE>
struct Mod : ModCompanion<uint64_t, MOD_VALUE, typename template_util::minimal_uint<MOD_VALUE>::type> {
    template<uint64_t VAL>
    static constexpr uint64_t literal_builder() {
        return VAL;
    }

    template<uint64_t VAL, char DIGIT, char... REST>
    static constexpr uint64_t literal_builder() {
        return literal_builder<(10 * VAL + DIGIT - '0') % MOD_VALUE, REST...>();
    }
};


#define REGISTER_MOD_LITERAL(mod, suffix) \
template <char... DIGITS> mod::type operator "" _##suffix() { \
    return mod::c<mod::literal_builder<0, DIGITS...>()>(); \
}


// ^^^^^^^^^^^^^^^^^ Library code end

using md = Mod<1000000007>;
using mt = md::type;
REGISTER_MOD_LITERAL(md, mod)

using Val = tuple<int, mt, mt>;

mt pow2s[1000001], powInv2s[1000001];

mt pow2(int p) {
    return p < 0 ? powInv2s[-p] : pow2s[p];
}

Val mul(Val a, Val b) {
    const mt p2a = pow2(get<0>(a));
    const mt p2b = pow2(get<0>(b));
    return Val{get<0>(a) + get<0>(b), p2a * get<1>(b) + get<1>(a) * p2b, p2a * get<2>(b) + 2_mod * get<1>(a) * get<1>(b) + get<2>(a) * p2b};
}

Val inv(Val a) {
    Val b;
    get<0>(b) = -get<0>(a);
    const mt p2b = pow2(get<0>(b));
    get<1>(b) = -p2b * (get<1>(a) * p2b);
    get<2>(b) = -p2b * (2_mod * get<1>(a) * get<1>(b) + get<2>(a) * p2b);
    return b;
}

Val d[1000000][7];
mt dSum[1000000][7];

void solve(istream& in, ostream& out) {
    pow2s[0] = powInv2s[0] = 1_mod;
    mt inv2 = md::inv(2_mod);
    forn (int, i, 1000000) {
        pow2s[i + 1] = pow2s[i] * 2_mod;
        powInv2s[i + 1] = powInv2s[i] * inv2;
    }

    int n = next<int>(in);
    auto as = next_vector<int>(in, n);
    sort(all(as));
    uint64_t ans = 0;
    int add[1 << 6];
    forn (int, mask, 1 << 6) {
        add[mask] = 0;
        int mask1 = mask;
        forn (int, it, 6) {
            add[mask] = add[mask] * 10 + (mask1 & 1);
            mask1 /= 2;
        }
    }
    int asIt = n - 1;
    rforn (int, x, 1000000) {
        int badMask = 0;
        int x1 = x;
        forn (int, it, 6) {
            badMask = 2 * badMask + (x1 % 10 == 9 ? 1 : 0);
            x1 /= 10;
        }
        d[x][0] = Val{0, 0_mod, 0_mod};
        dSum[x][0] = 0_mod;
        forn (int, bit, 6) {
            d[x][bit + 1] = d[x][bit];
            dSum[x][bit + 1] = dSum[x][bit];
            if (!(badMask & (1 << bit))) {
                d[x][bit + 1] = mul(d[x][bit + 1], inv(d[x + add[1 << bit]][bit]));
                dSum[x][bit + 1] -=  dSum[x + add[1 << bit]][bit];
            }
        }
        auto val = inv(d[x][6]);
        while (asIt >= 0 && as[asIt] == x) {
            --asIt;
            val = mul(val, Val{1, md::wrap(x), md::wrap(1ULL * x * x)});
        }
        auto sum = get<2>(val) + dSum[x][6];
        forn (int, bit, 6) {
            d[x][bit] = mul(d[x][bit], val);
            dSum[x][bit] += get<2>(val);
        }
        if (sum != 0_mod) {
            dbg(x, sum, x * uint64_t(sum));
            ans ^= x * uint64_t(sum);
        }
    }
    out << ans << endl;
}


int main() {
    solve(cin, cout);
    return 0;
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
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);
        MinAddition solver = new MinAddition();
        solver.solve(1, in, out);
        out.close();
    }

    static class MinAddition {
        public int[] pow10 = {1, 10, 100, 1000, 10000, 100000, 1000000};
        public int MAXN = 1000000;
        public int LOG = 6;
        public int mod = 1000000007;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            int[] freq = new int[MAXN];
            int[] sum = new int[MAXN];
            int[] sum2 = new int[MAXN];
            int[] pow2 = new int[n + 1];
            pow2[0] = 1;
            for (int i = 1; i <= n; i++) pow2[i] = (pow2[i - 1] << 1) % mod;
            for (int i = 0; i < n; i++) {
                int a = in.nextInt();
                freq[a]++;
                sum[a] += a;
                if (sum[a] >= mod) sum[a] -= mod;
                int x = (int) (1L * a * a % mod);
                sum2[a] += x;
                if (sum2[a] >= mod) sum2[a] -= mod;
            }

            int[] mod10 = new int[MAXN];
            for (int i = 0; i < 10; i++) mod10[i] = i;
            for (int i = 10; i < MAXN; i++) mod10[i] = mod10[i - 10];

            for (int level = LOG - 1; level >= 0; level--) {
                for (int i = MAXN - 1; i >= 0; i--) {
                    int d = mod10[i / pow10[level]];
                    if (d > 0) {
                        int p = i - pow10[level];
                        freq[p] += freq[i];
                        sum[p] += sum[i];
                        if (sum[p] >= mod) sum[p] -= mod;
                        sum2[p] += sum2[i];
                        if (sum2[p] >= mod) sum2[p] -= mod;
                    }
                }
            }
            for (int i = 0; i < MAXN; i++) {
                int sdiff = (int) ((1L * sum[i] * sum[i] + mod - sum2[i]) % mod);
                int ssame = sum2[i];
                int g = 0;
                if (freq[i] >= 1)
                    g += (int) (1L * ssame * pow2[freq[i] - 1] % mod);
                if (freq[i] >= 2)
                    g += (int) (1L * sdiff * pow2[freq[i] - 2] % mod);
                while (g >= mod) g -= mod;
                freq[i] = g;
            }

            for (int level = 0; level < LOG; level++) {
                for (int i = 0; i < MAXN; i++) {
                    int d = mod10[i / pow10[level]];
                    if (d + 1 < 10) {
                        int p = i + pow10[level];
                        freq[i] -= freq[p];
                        if (freq[i] < 0) freq[i] += mod;
                    }
                }
            }

            long s = 0;
            for (int i = 0; i < MAXN; i++) {
                s ^= 1L * i * freq[i];
            }
            out.println(s);
        }

    }

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

        public void println(long i) {
            writer.println(i);
        }

    }

    static class InputReader {
        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 (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }
}

// vvvvvvvvvvvvvvvvv Library code start


#define NDEBUG
NDEBUG


#include <algorithm>
#include <array>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <queue>
#include <random>


#define forn(t, i, n) for (t i = 0; i < (n); ++i)
#define foran(t, i, a, n) for (t i = (a); i < (n); ++i)


using namespace std;

/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);

template<class T>
inline T mn(T arg) {
    return arg;
}


template<class T, class... Args>
inline bool rmx(T &to, Args... args) {
    auto v = mn(args...);
    if (to < v) {
        to = v;
        return true;
    }
    return false;
}


// Section with adoption of array and vector algorithms.


// 32 bit ints (sum LSB + MSB == 32)


// TODO: Section with some container algorithms


namespace template_util {
    

    constexpr int bytecount(uint64_t x) {
        return x ? 1 + bytecount(x >> 8) : 0;
    }

    /// caide keep
    template<int N>
    struct bytetype {
        
    };

    /// caide keep
    template<>
    struct bytetype<4> {
        
    };

    /// caide keep
    template<>
    struct bytetype<3> {
        
    };

    /// caide keep
    template<>
    struct bytetype<2> {
        
    };

    /// caide keep
    template<>
    struct bytetype<1> {
        
    };

    /// caide keep
    template<>
    struct bytetype<0> {
        
    };

    /// caide keep
    template<uint64_t N>
    struct minimal_uint : bytetype<bytecount(N)> {
    };
}


template<class T>
T next(istream& in) {
    T ret;
    in >> ret;
    return ret;
}


// ^^^^^^^^^^^^^^^^^ Library code end

int tr[1000][3];
int l[1000], r[1000];
bool col[1000];
int ans[2000];

tuple<int, int, int> chooseDfs(int total, int i, int p = -1) {
    int size = 1, best = -1, bestSize = 1000000000, maxSize = 0;
    forn (int, e, 3) {
        int j = tr[i][e];
        if (j != p && j >= 0 && !col[j]) {
            auto r1 = chooseDfs(total, j, i);
            if (get<1>(r1) < bestSize) {
                best = get<0>(r1);
                bestSize = get<1>(r1);
            }
            size += get<2>(r1);
            rmx(maxSize, get<2>(r1));
        }
    }
    rmx(maxSize, total - size);
    if (maxSize < bestSize) {
        best = i;
        bestSize = maxSize;
    }
    return tuple<int, int, int>{best, bestSize, size};
}

int sizeDfs(int i, int p = -1) {
    auto r = 1;
    forn (int, e, 3) {
        int j = tr[i][e];
        if (j != p && j >= 0 && !col[j]) {
            r += sizeDfs(j, i);
        }
    }
    return r;
}

void ansDfs(int n, int i) {
    forn (int, e, 2) {
        if (tr[i][e] >= 0) {
            ansDfs(n, tr[i][e]);
        }
        ans[tr[i][e] < 0 ? -2 - tr[i][e] : n + tr[i][e]] = n + i + 1;
    }
}

void solve(istream& in, ostream& out) {
    auto q = [&](int a, int b, int c) {
        out << a + 1 << " " << b + 1 << " " << c + 1 << endl;
        string s = next<string>(in);
        if (s == "X") {
            return 2;
        } else if (s == "Y") {
            return 1;
        } else if (s == "Z") {
            return 0;
        } else {
            throw 42;
        }
    };
    int n = next<int>(in);
    memset(tr, -1, sizeof(tr));
    tr[0][0] = -2;
    tr[0][1] = -3;
    l[0] = 0;
    r[0] = 1;
    foran (int, i, 2, n) {
        memset(col, 0, sizeof(col));
        int x = 0;
        while (true) {
            x = get<0>(chooseDfs(sizeDfs(x), x));
            int e = q(l[x], r[x], i);
            if (tr[x][e] < 0 || col[tr[x][e]]) {
                if (tr[x][e] >= 0) {
                    forn (int, e1, 3) {
                        if (tr[tr[x][e]][e1] == x) {
                            tr[tr[x][e]][e1] = i - 1;
                        }
                    }
                }
                tr[i - 1][e] = tr[x][e];
                tr[x][e] = i - 1;
                tr[i - 1][e == 0 ? 1 : 0] = -2 - i;
                tr[i - 1][e == 2 ? 1 : 2] = x;
                l[i - 1] = tr[i - 1][0] < 0 ? -2 - tr[i - 1][0] : l[tr[i - 1][0]];
                r[i - 1] = tr[i - 1][1] < 0 ? -2 - tr[i - 1][1] : r[tr[i - 1][1]];
                break;
            }
            col[x] = true;
            x = tr[x][e];
        }
    }
    int r = 0;
    while (tr[r][2] != -1) {
        r = tr[r][2];
    }
    ans[n + r] = -1;
    ansDfs(n, r);
    out << "-1\n";
    forn (int, i, 2 * n - 1) {
        out << ans[i] << " ";
    }
    out << "\n";
}


int main() {
    solve(cin, cout);
    return 0;
}

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
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);
        ForgottenTree solver = new ForgottenTree();
        solver.solve(1, in, out);
        out.close();
    }

    static class ForgottenTree {
        public InputReader in;
        public OutputWriter out;
        public int nidx;
        public int n;
        public int[] par;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            this.in = in;
            this.out = out;

            n = in.nextInt();
            nidx = n;
            ForgottenTree.Node root = new ForgottenTree.Node(0);
            ForgottenTree.Node.cgen = 0;
            for (int i = 1; i < n; i++) {
                ForgottenTree.Node.cgen++;
                root.getLeaves();
                root = insert(root, i);
            }
            out.println(-1);
            par = new int[2 * n - 1];
            dfs(root, -2);
            out.println(par);
        }

        public String ask(int a, int b, int c) {
            out.println((a + 1) + " " + (b + 1) + " " + (c + 1));
            out.flush();
            String ret = in.next();
            if (ret.equals("-1")) System.exit(0);
            return ret;
        }

        public void dfs(ForgottenTree.Node root, int p) {
            par[root.label] = p + 1;
            if (root.lchild != null) {
                dfs(root.lchild, root.label);
                dfs(root.rchild, root.label);
            }
        }

        public ForgottenTree.Node insert(ForgottenTree.Node root, int label) {
            if (!root.active()) {
                return add(root, label);
            }
            root.dfs();

            if (root.lchild == null) {
                return add(root, label);
            }

            int curleaves = root.nleaves;
            if (curleaves <= 1) {
                int nnodes = 0;
                ForgottenTree.Node cur = root;
                while (!cur.isLeaf()) {
                    nnodes++;
                    if (cur.lchild.active()) cur = cur.lchild;
                    else cur = cur.rchild;
                }
                cur = root;
                int depth = 0;
                while (2 * (depth + 1) < nnodes) {
                    if (cur.lchild.active()) cur = cur.lchild;
                    else cur = cur.rchild;
                    depth++;
                }

                return process(root, cur, label);
            }

            ForgottenTree.Node cur = root;
            while (true) {
                if (cur.lchild == null) {
                    if (cur.par == null) {
                        return add(cur, label);
                    }
                    if (cur.which == 0) {
                        cur.par.setChild(0, add(cur, label));
                        return root;
                    } else {
                        cur.par.setChild(1, add(cur, label));
                        return root;
                    }
                }
                int x1 = cur.lchild.active() ? cur.lchild.nleaves : 0;
                int x2 = cur.rchild.active() ? cur.rchild.nleaves : 0;

                if (x1 * 2 > curleaves) {
                    cur = cur.lchild;
                    continue;
                }
                if (x2 * 2 > curleaves) {
                    cur = cur.rchild;
                    continue;
                }

                return process(root, cur, label);
            }
        }

        public ForgottenTree.Node process(ForgottenTree.Node root, ForgottenTree.Node cur, int label) {
            String s = ask(cur.x, cur.y, label);
            switch (s) {
                case "X":
                    if (cur.par == null) {
                        return add(cur, label);
                    }
                    cur.disable();
                    return insert(root, label);
                case "Y":
                    cur.setChild(1, insert(cur.rchild, label));
                    return root;
                case "Z":
                    cur.setChild(0, insert(cur.lchild, label));
                    return root;
                default:
                    throw new RuntimeException();
            }
        }

        public ForgottenTree.Node add(ForgottenTree.Node cnode, int label) {
            ForgottenTree.Node add = new ForgottenTree.Node(nidx++);
            add.setChild(0, cnode);
            add.setChild(1, new ForgottenTree.Node(label));
            return add;
        }

        static class Node {
            public static int cgen;
            public int x;
            public int y;
            public int label;
            public int gen;
            public int nleaves;
            public int which;
            public ForgottenTree.Node lchild;
            public ForgottenTree.Node rchild;
            public ForgottenTree.Node par;

            public Node(int label) {
                this.lchild = null;
                this.rchild = null;
                this.par = null;
                this.which = 0;
                this.label = label;
                this.gen = 0;
                this.nleaves = 1;
            }

            public boolean active() {
                return gen < cgen;
            }

            public void disable() {
                this.gen = cgen;
            }

            public boolean isLeaf() {
                return lchild == null || (!lchild.active() && !rchild.active());
            }

            public void setChild(int which, ForgottenTree.Node x) {
                if (which == 0) {
                    this.lchild = x;
                } else {
                    this.rchild = x;
                }
                x.par = this;
                x.which = which;
            }

            public void dfs() {
                if (isLeaf()) {
                    this.nleaves = 1;
                    return;
                }

                this.nleaves = 0;
                if (lchild.active()) {
                    lchild.dfs();
                    this.nleaves += lchild.nleaves;
                }
                if (rchild.active()) {
                    rchild.dfs();
                    this.nleaves += rchild.nleaves;
                }
            }

            public void getLeaves() {
                if (lchild == null) {
                    this.x = this.y = label;
                    return;
                }
                lchild.getLeaves();
                rchild.getLeaves();
                this.x = lchild.x;
                this.y = rchild.x;
            }

        }

    }

    static class InputReader {
        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 (this.numChars == -1) {
                throw new InputMismatchException();
            } else {
                if (this.curChar >= this.numChars) {
                    this.curChar = 0;

                    try {
                        this.numChars = this.stream.read(this.buf);
                    } catch (IOException var2) {
                        throw new InputMismatchException();
                    }

                    if (this.numChars <= 0) {
                        return -1;
                    }
                }

                return this.buf[this.curChar++];
            }
        }

        public int nextInt() {
            int c;
            for (c = this.read(); isSpaceChar(c); c = this.read()) {
                ;
            }

            byte sgn = 1;
            if (c == 45) {
                sgn = -1;
                c = this.read();
            }

            int res = 0;

            while (c >= 48 && c <= 57) {
                res *= 10;
                res += c - 48;
                c = this.read();
                if (isSpaceChar(c)) {
                    return res * sgn;
                }
            }

            throw new InputMismatchException();
        }

        public String next() {
            int c;
            while (isSpaceChar(c = this.read())) {
                ;
            }

            StringBuilder result = new StringBuilder();
            result.appendCodePoint(c);

            while (!isSpaceChar(c = this.read())) {
                result.appendCodePoint(c);
            }

            return result.toString();
        }

        public static boolean isSpaceChar(int c) {
            return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
        }

    }

    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 print(int[] array) {
            for (int i = 0; i < array.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(array[i]);
            }
        }

        public void println(int[] array) {
            print(array);
            writer.println();
        }

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

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

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

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

    }
}