绿魔法师

题号：NC20812
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

“我不知道你在说什么，因为我只是个pupil。”--绿魔法师

一个空的可重集合S。
n次操作，每次操作给出x,k,p，执行以下操作：
1、在S中加入x。
2、输出 $\sum_{y \in S}{gcd(x,y)^k} (mod p)$ 。

所有输入的数都是小于1e5+1的正整数。

输出对应的结果

示例1

复制

复制

4
2
1