Вам даны мультимножества A и B. Каждое мультимножество состоит из n целых чисел от 1 до n включительно. Мультимножества могут содержать несколько копий одного и того же числа.
Вы хотели бы найти непустое подмножество мультимножества A и непустое подмножество мультимножества B, такие, что суммы всех составляющих их чисел равны. Подмножества также могут быть мультимножествами, то есть могут содержать элементы с одинаковыми значениями.
Если решения не существует, выведите -1. В противном случае выведите индексы элементов любых таких подмножеств A и B.
Выходные данные
Если решения не существует, то выведите -1. В противном случае выведите своё решение на четырёх строках.
Первая строка должна содержать единственное целое число ka, определяющее размер соответствующего подмножества A. Вторая строка должна содержать ka различных чисел — индексы элементов подмножества A.
Третья строка должна содержать единственное целое число kb, определяющее размер соответствующего подмножества B. Четвёртая строка должна содержать kb различных чисел — индексы подмножества B.
Элементы обоих мультимножеств нумеруются от 1 до n. Если возможных решений несколько, то выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
10 10 10 10 10 10 10 10 10 10
10 9 8 7 6 5 4 3 2 1
|
1
2
3
5 8 10
|
|
2
|
5
4 4 3 3 3
2 2 2 2 5
|
2
2 3
2
3 5
|