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

定义一棵根节点为 $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;
}