定義一棵根節點為 $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;
}