智乃的数组乘积

题号：NC288183
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

给定一个长度大小为 $N$ 的数组和一个质数 $P$ ，智乃定义数组子区间的权值 $Val(l,r) = \prod_{i=l}^{r}a_i$

现在给定一个整数 $x$ 智乃不希望出现 $\exists 1 \leq l \leq r \leq N,Val(l,r) \equiv x \pmod P$ ，因此她让你对其进行修改，每次操作可以将数组中任意位置的值改为任意小于 $P$ 的非负整数 $(0\leq a_i < P)$

请输出修改后的数组，要求最小化改动的次数

对于题目中出现的数学符号：

$\prod_a^b$ 表示从a到b的连续乘积

$\exists$ 表示“存在任意”

$...\pmod P$ 表示结果需要对 $P$ 取余数

$\equiv$ 为同余等号，表示左右两端的数字或表达式在同时除以 $P$ 后余数相同

输入描述:

第一行输入三个整数并且保证是一个质数

接下来在一行内输入个整数，表示一开始的数组

输出描述:

仅一行，输出修改后的数组，你可以将其修改为任意小于 $P$ 的非负整数 $(0\leq a_i <P)$

仅要求最小化改动的次数，可以证明总是存在这样的解

示例1

输入

复制

3 5 1
3 2 3

输出

复制

3 3 3