Equal Sums
Лятна Информатическа Школа, 2014
Time Limit: 5s, Memory Limit: 512MiB
Ели има множество от N цели положителни числа. Сега тя се чуди дали съществуват две различни непразни подмножества, чиито суми да са равни. Момичето счита две подмножества за различни, ако едното от тях съдържа поне един елемент от началното подмножество, който не се съдържа в другото.

Вие решавате да помогнете на Ели, като напишете програма, която проверява дали съществуват две такива подмножества, и ако да – да изведете един такъв пример. Ако съществуват повече от една двойка такива подмножества, изведете която и да е от тях.
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N – броят елементи на входното множество. Следва ред с N на брой различни цели числа Ai – всеки от елементите на множеството.
Изход
Ако съществуват две различни непразни подмножества, сумата на чиито елементи е равна, на първия ред на стандартния изход изведете елементите на едното множество, а на втория – елементите на второто. В противен случай на единствен ред на стандартния изход изведете "Impossible".
Ограничения
  • N = 20 или N = 500
  • 1 ≤ Ai != Aj ≤ 1012
Примерен Вход Примерен Изход
20 42 266 6170 858 9512 1243 1657 1771 2328 2490 2665 2894 3117 4210 4943 5690 7048 120 7125 9600 4943 4210 3117 2894 7048 2328
20 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 Impossible
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 3 1 2 17 3
Мрън!