5726. 缪尔赛思又来到了你的面前

单点时限: 2.0 sec

内存限制: 512 MB

定义一棵根节点为 $1$,$n(2 \leq n \leq 10^3)$ 个节点的树的哈希值为:
$$
H = \sum_{i=1}^{n} X^iY^{fa(i)} \bmod 998244353
$$
$fa(i)$ 表示 $i$ 的父亲节点,$1$ 为根节点,$fa(1) = 1$。

$X, Y(1 \leq X,Y < 998244353)$ 为给定的两个随机值。

请构造两棵大小为 $n$ 的树,他们有相同的哈希值,但两棵树要求不一样。

我们认为两棵大小为 $n$ 的树不一样:

  • 记数组 $fa(i)$ 表示第 $i$ 个节点的父亲,其中 $fa(1) = 1$。
  • 节点 $1$,$2$,$3$……$n$ 对应的 $fa(1), fa(2), fa(3), … , fa(n)$排成一排,得到了我们所要的$fa$数组。
  • 对于两棵树 $u,v$,其数组 $fa_u, fa_v$,存在一个 $j$,使得 $fa_u(j)\neq fa_v(j)$,此时认为两棵树不一样。

你需要输出两棵树的 $fa$ 数组。

你需要保证输出的 fa 数组可以构成一棵树。

保证输入数据必然有解。

输入格式

一行三个数 $n, X, Y$ 。

输出格式

输出共两行。

每行 $n$ 个数,分别表示两棵树的 $fa$ 数组。

若有多组解,请输出任意一组满足题意的解即可。

样例

Input
8 1 1
Output
1 1 1 6 1 1 1 1
1 1 1 1 1 1 1 1

4 人解决,24 人已尝试。

5 份提交通过,共有 92 份提交。

9.2 EMB 奖励。

创建: 4 月,3 周前.

修改: 4 月,3 周前.

最后提交: 2 月,3 周前.

来源: N/A

题目标签