缪尔赛思又来到了你的面前（哈希）

定义一棵根节点为 $1$，$n(2\le n\le 10^3)$ 个节点的树的哈希值为：
$$H=\sum _{i=1}^n{X}^i{Y}^{fa(i)}mod998244353$$
$fa(i)$ 表示 $i$ 的父亲节点，$1$ 为根节点，$fa(1)=1$。

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

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

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

• 记数组 $fa(i)$ 表示第 $i$ 个节点的父亲，其中 $fa(1)=1$。
• 节点 $1$，$2$，$3\dots \dots n$ 对应的 $fa(1),fa(2),fa(3),\dots ,fa(n)$排成一排，得到了我们所要的$fa$数组。
• 对于两棵树 $u,v$，其数组 $f{a}_u,f{a}_v$，存在一个 $j$，使得 $f{a}_u(j)\ne f{a}_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

这里先说明一个有趣的事实，然后再说明解题思路

我们知道最多有365个人的生日是不同的，但是随着生日不同的人数增多，概率下降的很快：当要找出23个人的生日不同时，概率就下降到了0.5；当要找出100个人的生日不同时，概率就下降到了$10^{-7}$

所以哈希冲突的概率随着数量的增多上升的很快，本题就是利用这个性质

我们利用并查集+随机数进行树的构造，每次都能得到一个哈希值

当得到的哈希值出现重复时，我们就可以输出这两棵树的fa数组了

但是仅仅这样会TLE，需要优化

观察到只有20个节点的树就可以有很多种不同的结构，所以我们只对前20个节点进行随机排列，之后的所有节点全部连接到根节点上

AC代码如下

#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <random>
#include <map>
#define int unsigned long long
using namespace std;
const int max_n = 1e3;
const int max_try = 100050;
const int limit = 20;
const int p = 998244353;int n, x, y;
int fa2[max_try][limit + 1], tmpfa[limit + 1];
map<int, int>ans;int quick_pow(int x, int y) {int ret = 1;while (y) {if (y % 2) ret = (ret * x) % p;x = (x * x) % p;y /= 2;}return ret % p;
}void init(int n) {for (int i = 1; i <= n; i++) {tmpfa[i] = i;}
}int find(int x) {return x == tmpfa[x] ? x : (tmpfa[x] = find(tmpfa[x]));
}bool insame(int x, int y) {return find(x) == find(y);
}void merge(int x, int y) {x = find(x);y = find(y);tmpfa[x] = y;
}bool check(int id, int check, int tmpn, int tmphash) {init(tmpn);for (int i = 2; i <= tmpn; i++) {if (insame(i, fa2[id][i])) return false;else merge(i, fa2[id][i]);}for (int i = 2; i <= tmpn; i++) {if (!insame(1, i)) {return false;}}int hashcheck = tmphash;for (int i = 1; i <= n; i++) {hashcheck = ((hashcheck + (quick_pow(x, i) + quick_pow(y, fa2[id][i])) % p) % p) % p;}return check == hashcheck;
}signed main() {cin >> n >> x >> y;srand((unsigned)time(NULL));int cnt = 0;int tmpn = min(n, limit);int tmphash = 0;for (int i = tmpn + 1; i <= n; i++) {tmphash = (tmphash + (quick_pow(x, i) * quick_pow(y, 1)) % p) % p;}while (1) {int hash2 = (tmphash + (x * y) % p) % p;fa2[cnt][1] = 1;init(tmpn);int flag = 0;for (int i = 2; i <= tmpn; i++) {int rand_num = rand() % tmpn + 1;while (insame(i, rand_num)) rand_num = rand() % tmpn + 1;merge(i, rand_num);fa2[cnt][i] = rand_num;hash2 = (hash2 + (quick_pow(x, i) * quick_pow(y, fa2[cnt][i])) % p) % p;}if (ans.count(hash2)) {int tmpid = ans[hash2];for (int i = 1; i <= n; i++) {if (fa2[tmpid][i] != fa2[cnt][i]) {flag = 1;break;}}if (flag) {//if (check(tmpid, hash2, tmpn, tmphash) || //	check(cnt, hash2, tmpn, tmphash)) {//	printf("ERROR!");//	return -1;//}for (int i = 1; i <= n; i++) {if (i <= tmpn) printf("%lld", fa2[tmpid][i]);else printf("1");if (i != n) printf(" ");}printf("\n");for (int i = 1; i <= n; i++) {if (i <= tmpn) printf("%lld", fa2[cnt][i]);else printf("1");if (i != n) printf(" ");}return 0;}}else {ans[hash2] = cnt++;}}return 0;
}