Вам даны мультимножества A и B. Каждое мультимножество состоит из n целых чисел от 1 до n включительно. Мультимножества могут содержать несколько копий одного и того же числа.
Вы хотели бы найти непустое подмножество мультимножества A и непустое подмножество мультимножества B, такие, что суммы всех составляющих их чисел равны. Подмножества также могут быть мультимножествами, то есть могут содержать элементы с одинаковыми значениями.
Если решения не существует, выведите -1. В противном случае выведите индексы элементов любых таких подмножеств A и B.
В первой строке входных данных будет записано единственное целое число n (1 ≤ n ≤ 1 000 000).
Во второй строке содержатся n целых чисел от 1 до n — элементы A. В третьей строке содержатся n целых чисел от 1 до n — элементы B.
Если решения не существует, то выведите -1. В противном случае выведите своё решение на четырёх строках.
Первая строка должна содержать единственное целое число ka, определяющее размер соответствующего подмножества A. Вторая строка должна содержать ka различных чисел — индексы элементов подмножества A.
Третья строка должна содержать единственное целое число kb, определяющее размер соответствующего подмножества B. Четвёртая строка должна содержать kb различных чисел — индексы подмножества B.
Элементы обоих мультимножеств нумеруются от 1 до n. Если возможных решений несколько, то выведите любое из них.
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
5
4 4 3 3 3
2 2 2 2 5
2
2 3
2
3 5
Название |
---|