Боб — активный пользователь социальной сети Faithbug. В этой сети люди могут становиться взаимными друзьями. То есть, если \(a\) является другом \(b\), то \(b\) также является другом \(a\). Таким образом у каждого пользователя есть неотрицательное количество друзей.
Сегодня утром кто-то анонимно отправил Бобу следующую ссылку: задача о реализации графа. Боб хочет узнать, кто это был. Для этого ему сначала нужно узнать, как выглядит эта сеть. Он исследовал профиль каждого человека в сети и записал количество его друзей. Однако он забыл записать количество своих друзей. Помогите ему узнать, сколько у него друзей. Поскольку возможных ответов может быть много, выведите все возможные количества.
Выходные данные
Выведите все возможные значения \(a_{n+1}\) — количества людей, с которыми Боб может быть друзями, в порядке возрастания.
Если ни одного решения не существует, выведите \(-1\).
Примечание
В первом примере единственное решение заключается в том, чтобы каждый был другом каждому. Поэтому у Боба может быть только \(3\) друга.
Во втором примере есть три возможных решения (кроме симметричных):
- \(a\) — друг \(b\), \(c\) — друг \(d\), а у Боба нет друзей, или
- \(a\) — друг \(b\), а также и \(c\), и \(d\) — друзья Боба, или
- Боб — друг каждому.
Третий пример решить невозможно, так как второму человеку нужно быть другом каждому, но у первого нет друзей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 3 3
|
3
|
|
2
|
4
1 1 1 1
|
0 2 4
|
|
3
|
2
0 2
|
-1
|
|
4
|
35
21 26 18 4 28 2 15 13 16 25 6 32 11 5 31 17 9 3 24 33 14 27 29 1 20 4 12 7 10 30 34 8 19 23 22
|
13 15 17 19 21
|