import java.io.*;
import java.util.*;

public class Tests {
    private static final int MAX_C = 100_000;
    private static final int MAX_P = 100_000;
    private static final int MAX_N = 100_000;

    int testNo = 0;
    PrintWriter out;
    static PrintWriter descriptions;
    Random random = new Random(3583289570238423583L);

    void beginTest(String description, Object... args) {
        ++testNo;
        descriptions.format("%03d: %s\n", testNo, String.format(description, args));
        descriptions.flush();
        System.out.format("%03d: %s\n", testNo, String.format(description, args));
        try {
            out = new PrintWriter(String.format("tests/%03d", testNo));
        } catch (FileNotFoundException e) {
            throw new AssertionError(e);
        }
    }

    class Profile implements Comparable<Profile> {
        int n;
        Max m;
        Answer a;
        int p;
        boolean ok = true;
        int cmax;
        int max;
        Item first, last;

        Profile(int n, Max m, Answer a, int p, Item first, Item last) {
            if (n > 10) {
                n = randomAlmost(n);
            }
            if (p > 10) {
                p = randomAlmost(p);
            }
            this.n = n;
            this.m = m;
            this.a = a;
            this.p = p;
            this.first = first;
            this.last = last;

            if (a == Answer.ONLY && m == Max.ONE) {
                ok = false;
                return;
            }

//        (max + p + delta) + cmax * max <= n + p
//        (cmax + 1) * m <= n - delta
//        max >= Math.max(delta, 1)

            // (cmax + 1) <= (n - delta) / delta - 1
            int min = m.base <= n / 2 - 2 ? 2 : Math.max(-a.delta, 1);
            int cmaxMax = n / min - 3;
            if (cmaxMax < m.base) {
                ok = false;
                return;
            }

            cmax = m == Max.MORE ? randomInt(m.base, cmaxMax + 1) : m.base;
            max = randomInt(min, (n - a.delta) / (cmax + 2) + 1);
            ok = max > 1 || max == 1 && (max + p + a.delta) + cmax * max == n + p;
            ok &= (max + p + a.delta) + cmax * max != n + p || first != Item.OTHER;
        }

        void write() {
            int left = max + p + a.delta;
            assert left + cmax * max <= n + p;
            assert a == answer(left, max, p);

            int[] colors = new int[n + p];
            int index = 0;
            for (int j = 0; j < left; j++) {
                colors[index++] = 0;
            }
            for (int k = 1; k <= cmax; k++) {
                for (int j = 0; j < max; j++) {
                    colors[index++] = k;
                }
            }
            for (int i = 0; i < max - 1 && index < n + p; i++) {
                colors[index++] = cmax + 1;
            }
            int c = cmax + 2;
            while (index != n + p) {
                colors[index++] = c++;
            }

            colors = permuteIndices(colors, permutation(n + p));
            biasColors(left, colors);

//            System.out.println(1 + ".." + cmax + " " + m);
            int firstColor = first == Item.OUR ? 0 : first == Item.MAX ? randomInt(1, cmax + 1) : randomInt(cmax + 1, c);
//            int firstColor = first == Item.OUR ? 0 : first == Item.MAX ? randomInt(1, cmax) : randomInt(cmax + 1, index);
            boolean firstFound = false;
            for (int i = 0; !firstFound && i < colors.length; i++){
                if (colors[i] == firstColor) {
                    firstFound = true;
                    int t = colors[i];
                    colors[i] = colors[n];
                    colors[n] = t;
                }
            }
            assert firstFound : first + " " + (cmax + 1) + " " + c + " " + firstColor + " " + Arrays.toString(colors);
            assert !(first == Item.MAX && m == Max.ONE && a == Answer.ONLY);

//            if (ourLast) {
//                for (int i = 0; i < colors.length; i++) {
//                    if (i != n && colors[i] == h) {
//                        int t = colors[i];
//                        colors[i] = colors[n + p - 1];
//                        colors[n + p - 1] = t;
//                        break;
//                    }
//                }
//            }

//            System.out.println(onBoard + " " + n + " " + left + " " + Arrays.toString(colors));

            int[] colorsPermutation = permutation(c);
            permuteValues(colors, colorsPermutation);
            int h = colorsPermutation[0];

            int[] board = Arrays.copyOfRange(colors, 0, n);
            int[] players = Arrays.copyOfRange(colors, n, n + p);
//            System.out.println(Arrays.toString(board) + " " + Arrays.toString(players));
//            System.out.println(firstColor);

//            System.out.println("--- " + (n + p) + " " + left + " " + (left - p) + " " + max + "*" + cmax + " " + Arrays.toString(colors) + " " + a + " " + answer(c, h, board, players));
            assert answer(c, h, board, players) == a : "Expected " + a + ", found " + answer(c, h, board, players);
            c = Math.max(c, players.length);
            c = Math.min(MAX_C, c + random.nextInt(1 + c / 10));
            rawTest(h, board, players, c);
        }

        private void biasColors(int left, int[] colors) {
            int onBoard = random.nextInt(10) == 0 ? Math.max(0, left - p)
                        : random.nextInt(9) == 0 ? Math.min(n, left)
                        : randomInt(Math.max(0, left - p), Math.min(n, left) + 1);
            int q = 0;
            int j = n;
            for (int i = 0; i < n; i++) {
                if (colors[i] == 0) {
                    q++;
                    if (q > onBoard) {
                        while (colors[j] == 0) {
                            j++;
                        }
                        colors[i] = colors[j];
                        colors[j] = 0;
                    }
                }
            }
            q = 0;
            j = 0;
            for (int i = n; i < n + p; i++) {
                if (colors[i] == 0) {
                    q++;
                    if (q > left - onBoard) {
                        while (colors[j] == 0) {
                            j++;
                        }
                        colors[i] = colors[j];
                        colors[j] = 0;
                    }
                }
            }
        }

        @Override
        public int compareTo(Profile that) {
            return Integer.compare(n + p, that.n + that.p);
        }
    }

    public void run() throws IOException {
        rawTest(1, a(1, 0, 1, 2, 1, 1), a(1, 0, 0), 4);
        testTwo();
        testOne();
        test(1, a(1, 1, 1, 2, 3), a(2, 3));
        test(1, a(1, 1, 2, 3, 4), a(4));
        rawTest(0, a(4, 0, 2, 0, 0, 1, 0), a(3, 3), 5);
		testThree();

        List<Profile> profiles = new ArrayList<>();
        for (int n : new int[]{10, 100, 1000, 10000}) {
            for (int p : new int[]{1, 2, 3, 10, 100, 1000, 10000}) {
                for (Max max : Max.values()) {
                    for (Answer answer : Answer.values()) {
                        for (Item first : Item.values()) {
                            for (Item last : Item.values()) {
                                Profile profile = new Profile(n, max, answer, p, first, last);
                                if (profile.ok) {
                                    profiles.add(profile);
                                }
                            }
                        }
                    }
                }
            }
        }

//        System.out.println(profiles.size());
        selectAndWrite(profiles, 70);
//        {
//            Profile p = new Profile(20, Max.TWO, Answer.ALL, 5, Item.MAX, randomItem(Item.values()));
//            System.out.println(p.ok);
//            p.write();
//        }
//        {
//            Profile p = new Profile(20, Max.TWO, Answer.NONE, 5, Item.MAX, randomItem(Item.values()));
//            System.out.println(p.ok);
//            p.write();
//        }
//        for (int i = 0; i < 10; i++) {
//            Profile p = new Profile(20, Max.TWO, Answer.ONLY, 5, Item.MAX, randomItem(Item.values()));
//            System.out.println(p.ok);
//            p.write();
//        }
        for (Max max : Max.values()) {
            for (Answer answer : Answer.values()) {
                for (Item first : Item.values()) {
                    Profile profile = new Profile(MAX_C, max, answer, MAX_C, first, randomItem(Item.values()));
                    if (profile.ok) {
                        profile.write();
                    }
                }
            }
        }
    }

    private Tests.Item randomItem(Tests.Item[] values) {
        return values[random.nextInt(values.length)];
    }

    private void selectAndWrite(List<Profile> profiles, int c) {
        Collections.shuffle(profiles, random);

        profiles = profiles.subList(0, c);
        Collections.sort(profiles);

        for (Tests.Profile profile : profiles) {
            profile.write();
        }
    }

    int randomInt(int from, int to) {
        return from + random.nextInt(to - from);
    }

    Answer answer(int c, int h, int[] board, int[] players) {
        assert board.length > 0;

        int[] colors = new int[c + 1];
        for (int color : board) {
            colors[color]++;
        }

        for (int color : players) {
            colors[color]++;
        }

        int max1 = 0;
        int maxi1 = c;
        int max2 = 0;
        for (int i = 0; i < c; i++) {
            if (i != h) {
                int s = colors[i];
                if (max1 < s) {
                    max2 = max1;
                    max1 = s;
                    maxi1 = i;
                } else if (max2 < s) {
                    max2 = s;
                }
            }
        }

//        System.out.println("=== " + (board.length + players.length) + " " + colors[h] + " " + (colors[h] - players.length) + " " + colors[maxi1] + "*" + count(colors[maxi1], colors));
        return answer(colors[h], colors[maxi1], players.length);
    }

    int randomAlmost(int n) {
        return randomInt(n - (int) Math.log(n), n);
    }

    Answer answer(int myColor, int maxColor, int p) {
        int left = myColor - p;
        if (left > maxColor) {
            return Answer.ALL;
        } else if (left == maxColor) {
            return Answer.EXCEPT;
        } else if (left + 1 == maxColor) {
            return Answer.ONLY;
        } else {
            return Answer.NONE;
        }
    }

    enum Max {
        ONE(1),
        TWO(2),
        MORE(3);

        int base;

        Max(int base) {
            this.base = base;
        }
    }

    enum Item { MAX, OUR, OTHER }

    enum Answer {
        ALL(+1),
        EXCEPT(0),
        ONLY(-1),
        NONE(-2);

        final int delta;

        Answer(int delta) {
            this.delta = delta;
        }
    }

    enum Precision {
        EXACT,
        APPROX
    }

    private void test(int h, int[] board, int[] players) {
        int c = Math.max(h, Math.max(Collections.max(toList(board)), Collections.max(toList(players)))) + 1;
        c = Math.max(c, players.length);
        c = Math.min(MAX_C, c + random.nextInt(1 + c / 10));
        int[] colorPermutation = permutation(c);
        h = colorPermutation[h];
        permuteValues(board, colorPermutation);
        permuteValues(players, colorPermutation);

        int[] boardPermutation = permutation(board.length);
        int[] newBoard = permuteIndices(board, boardPermutation);

        rawTest(h, newBoard, players, c);
    }

    private int[] permuteIndices(int[] array, int[] permutation) {
        int[] newBoard = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            newBoard[permutation[i]] = array[i];
        }
        return newBoard;
    }

    void testOne() {
        test(1, a(1), a(1));
        test(1, a(1), a(0));
        test(1, a(1), a(0, 1));
        test(1, a(1), a(1, 0));

        test(1, a(0), a(1));
        test(1, a(0), a(0));
        test(1, a(0), a(0, 1));
        test(1, a(0), a(1, 0));
    }

    void testTwo() {
        test(1, a(1, 1), a(1));
        test(1, a(1, 0), a(1));
        test(1, a(0, 0), a(1));
        test(1, a(1, 1), a(1, 1, 1));
        test(1, a(0, 1), a(1, 1, 1));
        test(1, a(0, 0), a(1, 1, 1));
        test(1, a(1, 1), a(1, 0, 1));
        test(1, a(1, 1), a(0));
        test(1, a(1, 1), a(0, 1, 1));
    }

    void testThree() {
        test(1, a(1, 1, 1), a(1));
        test(1, a(1, 0, 1), a(1));
        test(1, a(0, 0, 1), a(1));
        test(1, a(0, 0, 0), a(1));

        test(1, a(1, 1, 1), a(1, 1, 1));
        test(1, a(1, 0, 1), a(1, 1, 1));
        test(1, a(0, 0, 1), a(1, 1, 1));
        test(1, a(0, 0, 0), a(1, 1, 1));

        test(1, a(1, 1, 1), a(1, 0));
        test(1, a(1, 0, 1), a(1, 0));
        test(1, a(0, 0, 1), a(1, 0));

        test(1, a(1, 1, 1), a(0, 1, 1));
        test(1, a(1, 0, 1), a(0, 1, 1));
        test(1, a(0, 0, 1), a(0, 1, 1));

        test(1, a(1, 1, 1), a(0, 0));
    }

    void testFour() {
        test(1, a(1, 1, 1, 1), a(1));

        test(1, a(1, 1, 1, 2), a(1));
        test(1, a(1, 2, 1, 2), a(1));
        test(1, a(2, 2, 1, 2), a(1));
        test(1, a(2, 3, 1, 4), a(1));
        test(1, a(2, 2, 1, 4), a(1));
        test(1, a(2, 2, 1, 2), a(1));

        test(1, a(1, 1, 1, 2), a(1, 0));
        test(1, a(1, 2, 1, 2), a(1, 2));
        test(1, a(2, 3, 1, 4), a(1, 1));
        test(1, a(2, 4, 1, 2), a(1, 1));
        test(1, a(2, 4, 1, 2), a(1, 0));
        test(1, a(1, 1, 2, 3), a(1, 0));
        test(1, a(1, 1, 2, 3), a(1, 2));
        test(1, a(1, 1, 2, 2), a(1, 2));

        test(1, a(1, 1, 1, 1), a(1, 0, 1));
        test(1, a(1, 1, 1, 1), a(1, 0, 2));
        test(1, a(1, 1, 1, 1), a(1, 0, 0));

        test(1, a(1, 1, 1, 2), a(1, 0, 1));
        test(1, a(1, 1, 1, 0), a(1, 0, 1));
        test(1, a(1, 1, 1, 2), a(1, 0, 3));
        test(1, a(1, 1, 1, 2), a(1, 0, 0));

        test(1, a(1, 1, 2, 3), a(1, 0, 1));
        test(1, a(1, 1, 2, 3), a(1, 2, 1));
        test(1, a(1, 1, 2, 2), a(1, 0, 1));
        test(1, a(1, 1, 2, 2), a(1, 2, 1));

        test(1, a(1, 2, 3, 4), a(1, 1, 1));
        test(1, a(1, 2, 3, 4), a(1, 0, 1));
        test(1, a(1, 2, 2, 4), a(1, 1, 1));
        test(1, a(1, 2, 2, 4), a(1, 1, 1));
        test(1, a(1, 2, 2, 4), a(1, 1, 3));
        test(1, a(1, 2, 2, 2), a(1, 1, 1));

        test(1, a(1, 2, 1, 1), a(0));
        test(1, a(1, 0, 1, 1), a(0));
        test(1, a(1, 0, 1, 1), a(0, 0));
        test(1, a(1, 0, 2, 1), a(0));
        test(1, a(1, 0, 2, 3), a(1));
        test(1, a(1, 0, 2, 3), a(4));
    }

    private void rawTest(int h, int[] board, int[] players, int c) {
        int[] colors = new int[c + 1];
        for (int color : board) {
            colors[color]++;
        }

        for (int color : players) {
            colors[color]++;
        }
        colors[h] = -1;
        int max = max(colors);
        int cmax = count(max, colors);
        beginTest(
                "%d stacks, %d of your color (%d stacks, %d chips), max other %d (%d times), %s",
                board.length,
                count(h, board) + count(h, players),
                count(h, board),
                count(h, players),
                max,
                cmax,
                answer(c, h, board, players)
//                h == players[0] ? "your color" : "color of " + count(players[0], board) + " other stacks",
//                players.length == 1 ? "you ourLast" : count(h, players) == players.length ? "all tail your color" : ""
        );
        assert 1 <= board.length && board.length <= MAX_N;
        assert 1 <= players.length && players.length <= MAX_P;
        assert players.length <= c && c <= MAX_C;
        assert 0 <= h && h < c;

        out.println(board.length + " " + players.length + " "+ c + " " + (h + 1));
        printArray(board);
        printArray(players);
        out.close();
    }

    private int max(int[] array) {
        int max = Integer.MIN_VALUE;
        for (int i : array) {
            max = Math.max(max, i);
        }
        return max;
    }

    private void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            if (i != 0) {
                out.print(" ");
            }
            out.print(array[i] + 1);
        }
        out.println();
    }

    private int count(int color, int[] board) {
        int yourColor = 0;
        for (int i : board) {
            if (i == color) {
                yourColor++;
            }
        }
        return yourColor;
    }

    List<Integer> toList(int[] values) {
        List<Integer> result = new ArrayList<>();
        for (int value : values) {
            result.add(value);
        }
        return result;
    }

    int[] a(int... values) {
        return values.clone();
    }
    private void permuteValues(int[] array, int[] permutation) {
        for (int i = 0; i < array.length; i++) {
            array[i] = permutation[array[i]];
        }
    }

    private int[] permutation(int n) {
        int[] permutation = new int[n];
        for (int i = 0; i < n; i++) {
            int j = random.nextInt(i + 1);
            permutation[i] = permutation[j];
            permutation[j] = i;
        }
        return permutation;
    }

    public static void main(String[] args) throws IOException {
        descriptions = new PrintWriter("tests/tests.lst");
        new Tests().run();
        descriptions.close();
    }
}
