题目描述

在 Furina 的群聊中，一共发出了 $n$ 条消息 $a_1,a_2,\cdots,a_n$，其中每条消息可以用 $[1,m]$ 中的一个正整数来表示。

Furina 不喜欢复读，因此她设定了一个复读指数 $k$，如果存在某个 $1\le i\le n-2k+1$，使得从 $i$ 开始的连续 $k$ 条消息和 $i+k$ 开始的连续 $k$ 条消息对应相同，即 $a[i\cdots i+k-1]=a[i+k\cdots i+2k-1]$，那么 Furina 的 QQ bot 就会把复读的人全部禁言。

云浅不希望群聊中有人被禁言。她想让你帮她算出，有多少种可能的消息记录使得没有人被禁言。也就是说，你需要求出有多少个序列 $a$ 满足 $a_i$ 是 $[1,m]$ 中的正整数，且满足

• 不存在一个 $1\le i\le n-2k+1$ 使得对每个 $0\le j<k$，有 $a_{i+j}=a_{i+k+j}$。

由于 Furina 每天的心情好坏程度不一，因此 Furina 每天设置的复读指数 $k$ 可能也会不同。云浅明白，未雨绸缪，才能未雨绸缪；临危不乱，才能临危不乱。因此她提前得知了 Furina 的心情波动范围 $[L,R]$，你需要对每个 $k=L,L+1,\cdots,R$ 求出复读指数为 $k$ 时的答案。

答案对给定的质数 $P$ 取模。

输入格式

输入一行五个正整数 $n,m,L,R,P$，表示消息条数，消息种类数，Furina 的心情波动范围，以及模数。

输出格式

输出一行 $R-L+1$ 个正整数，依次表示 $k=L,L+1,\cdots,R$ 的答案。

样例 #1

样例输入 #1

5 2 1 5 998244353

样例输出 #1

2 20 32 32 32

样例 #2

样例输入 #2

6 2 2 4 1000000007

样例输出 #2

32 56 64

提示

样例 $1$ 解释

对于 $k=1$，仅有两种方案：$a=(1,2,1,2,1),a=(2,1,2,1,2)$。

对于 $k=2$，一种合法的方案是 $a=(1,1,2,1,1)$。

对于 $k\ge 3$，可以发现此时任意方案均不会出现复读，因此方案数为 $m^n=32$。

测试点约束

对于所有数据，$2\le n\le 5\times 10^5,1\le L\le R\le n,10^8\le P\le 10^9+7,2\le m<P$。