У вас на столе лежат две колоды карт, причем некоторые карты в этих колодах лежат рубашкой вверх, а некоторые — рубашкой вниз. Вы хотите получить из них одну колоду, в которой каждая карта лежит рубашкой вверх. Вы собираетесь сделать это в два этапа.
Первый этап заключается в слиянии обеих колод в одну так, что относительный порядок карт из одной и той же колоды не изменяется. То есть для любых двух различных карт i и j из одной колоды, если карта i лежала выше карты j, то после слияния карта i так же должна лежать выше карты j.
Второй этап заключается в выполнении над полученной после первого этапа колодой операций переворота. За одну операцию переворота вы можете взять несколько верхних карт, целиком перевернуть и положить обратно. Таким образом, переворачивается каждая из взятых карт, а порядок этих карт меняется на противоположный. То есть, самая нижняя карта из тех, что вы взяли, окажется сверху.
Ваша цель — добиться того, чтобы все карты стали лежать рубашкой вверх. Найдите такой такой порядок слияния карт на первом этапе и последовательность операций переворота на втором этапе, чтобы все карты лежали рубашкой вверх, а количество операций переворота было минимальным.
Выходные данные
В первую строку выведите n + m целых чисел, разделенных пробелом — номера карт в том порядке, в котором они будут находиться после первого этапа. Перечисляйте карты от самой верхней к самой нижней. Картам первой колоды должны соответствовать их номера от 1 до n в порядке от самой верхней карты к самой нижней, а картам второй колоды должны соответствовать их номера, увеличенные на n, то есть числа от n + 1 до n + m в порядке от самой верхней карты во второй колоде к самой нижней.
Во второй строке выведите одно целое число x — минимальное количество операций переворота, которое необходимо выполнить, чтобы все карты в колоде лежали рубашкой вверх. В третьей строке выведите x целых чисел: c1, c2, ..., cx (1 ≤ ci ≤ n + m), каждое из которых означает, сколько карт следует взять сверху колоды для выполнения очередной операции переворота. Операции выводите в том порядке, в котором их надо выполнять.
Если оптимальных решений несколько, выведите любой из них. Гарантируется, что минимальное количество операций не превышает 6·105.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 0 1
4
1 1 1 1
|
1 4 5 6 7 2 3
3
5 6 7
|
|
2
|
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
|