← 返回题目列表

Codeforces · 317/D

D. 权力的游戏

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

Vasya 和 Petya 写下从 1 到 n 的所有整数来玩“幂”游戏(n 可以很大;但是,Vasya 和 Petya 并没有被这个事实混淆)。

玩家依次选择数字(Vasya 首先选择)。如果当前回合选择了某个数字x,则禁止在下一轮选择x或其所有其他正整数幂(即x2,x3,...)。例如,如果第一回合选择了数字9,则之后不能选择9或81,但仍可以选择3或27。不能走的人输。

如果 Vasya 和 Petya 都发挥最佳,谁会获胜?

输入

输入包含单个整数 n (1 ≤ n ≤ 109)。

输出

打印获胜者的名字 - “Vasya”或“Petya”(不带引号)。

示例

输入 #1

1

输出 #1

Vasya

输入 #2

2

输出 #2

Petya

输入 #3

8

输出 #3

Petya

注意

在第一个样本中,Vasya 将选择 1 并立即获胜。

在第二个样本中,无论 Vasya 在第一回合中选择哪个数字,Petya 都可以选择剩余的数字并获胜。