H. Слияние двух колод
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

У вас на столе лежат две колоды карт, причем некоторые карты в этих колодах лежат рубашкой вверх, а некоторые — рубашкой вниз. Вы хотите получить из них одну колоду, в которой каждая карта лежит рубашкой вверх. Вы собираетесь сделать это в два этапа.

Первый этап заключается в слиянии обеих колод в одну так, что относительный порядок карт из одной и той же колоды не изменяется. То есть для любых двух различных карт i и j из одной колоды, если карта i лежала выше карты j, то после слияния карта i так же должна лежать выше карты j.

Второй этап заключается в выполнении над полученной после первого этапа колодой операций переворота. За одну операцию переворота вы можете взять несколько верхних карт, целиком перевернуть и положить обратно. Таким образом, переворачивается каждая из взятых карт, а порядок этих карт меняется на противоположный. То есть, самая нижняя карта из тех, что вы взяли, окажется сверху.

Ваша цель — добиться того, чтобы все карты стали лежать рубашкой вверх. Найдите такой такой порядок слияния карт на первом этапе и последовательность операций переворота на втором этапе, чтобы все карты лежали рубашкой вверх, а количество операций переворота было минимальным.

Входные данные

В первой строке входных данных находится единственное целое число n — количество карт в первой колоде (1 ≤ n ≤ 105).

Во второй строке входных данных находится n целых чисел, разделенных одиночными пробелами a1, a2, ..., an (0 ≤ ai ≤ 1). Значение ai равно 0, если i-я карта лежит рубашкой вверх, и 1, если карта лежит рубашкой вниз. Карты заданы в порядке от самой верхней к самой нижней.

В третьей строке входных данных находится целое число m — количество карт во второй колоде (1 ≤ m ≤ 105).

В четвертой строке входных данных находится m целых чисел, разделенных одиночными пробелами b1, b2, ..., bm (0 ≤ bi ≤ 1). Значение bi равно 0, если i-я карта лежит рубашкой вверх, и 1, если карта лежит рубашкой вниз. Карты заданы в порядке от самой верхней к самой нижней.

Выходные данные

В первую строку выведите n + m целых чисел, разделенных пробелом — номера карт в том порядке, в котором они будут находиться после первого этапа. Перечисляйте карты от самой верхней к самой нижней. Картам первой колоды должны соответствовать их номера от 1 до n в порядке от самой верхней карты к самой нижней, а картам второй колоды должны соответствовать их номера, увеличенные на n, то есть числа от n + 1 до n + m в порядке от самой верхней карты во второй колоде к самой нижней.

Во второй строке выведите одно целое число x — минимальное количество операций переворота, которое необходимо выполнить, чтобы все карты в колоде лежали рубашкой вверх. В третьей строке выведите x целых чисел: c1, c2, ..., cx (1 ≤ ci ≤ n + m), каждое из которых означает, сколько карт следует взять сверху колоды для выполнения очередной операции переворота. Операции выводите в том порядке, в котором их надо выполнять.

Если оптимальных решений несколько, выведите любой из них. Гарантируется, что минимальное количество операций не превышает 6·105.

Примеры
Входные данные
3
1 0 1
4
1 1 1 1
Выходные данные
1 4 5 6 7 2 3
3
5 6 7
Входные данные
5
1 1 1 1 1
5
0 1 0 1 0
Выходные данные
6 1 2 3 4 5 7 8 9 10
4
1 7 8 9