← 返回题目列表

Codeforces · 325/B

B. 体育场和比赛

中文机器翻译题面 查看原题

丹尼尔正在组织一场足球锦标赛。他提出了以下比赛形式:

1. 在前几个(可能是零个)阶段,虽然队伍数量为偶数,但他们分成两对,每对进行一场比赛。在每个阶段,每对的失败者都会被淘汰(没有平局)。这种阶段是在队伍数量为偶数的情况下举行的。
2. 最终剩下的队伍数量将为奇数。如果还剩下一支球队,则该球队将被宣布为获胜者,比赛结束。否则,剩余队伍将在循环赛中与其他剩余队伍比赛一次(如果有 x 队,则将进行 $$\frac{x \cdot (x-1)}{2}$$ 场比赛),比赛结束。

例如,如果最初有 20 支球队,他们将首先进行 10 场比赛。这样,10支球队将被淘汰,剩下的10支球队将进行5场比赛。然后剩下的5支球队将进行10场循环赛。总共有10+5+10=25场比赛。

丹尼尔已经预订了n场比赛的球场。帮助他确定应该邀请多少支球队,以使锦标赛恰好需要 n 场比赛。您应该按升序打印所有可能产生 n 场比赛的球队数量,如果没有这样的数字,则打印 -1。

输入

第一行包含一个整数 n (1 ≤ n ≤ 1018),即应玩的游戏数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

按升序打印所有可能的受邀球队数量,每行一个。如果正好n场比赛无法进行,则输出一个数字:-1。

示例

输入 #1

3

输出 #1

3
4

输入 #2

25

输出 #2

20

输入 #3

2

输出 #3

-1