幼儿园里有 $N$ 个孩子，每个孩子都认为有一个孩子是他最好的朋友。这些孩子非常奇特，因此没有两个孩子会认为同一个孩子是自己最好的朋友，但一个孩子有可能认为自己是他自己最好的朋友！此外，如果孩子 B 是孩子 A 最好的朋友，A 并不一定是 B 最好的朋友。

幼儿园老师有 $N$ 袋糖果，她希望将这些糖果分发给孩子们，使得每个孩子恰好得到一袋。然而，问题在于这些袋子里的糖果数量不一定相同，因此孩子们可能会感到不满。由于孩子们有着极强的正义感，孩子 A 的不满度等于孩子 A 获得的糖果数量与他最好的朋友获得的糖果数量之差的绝对值。

幼儿园老师决定分发这些糖果袋，使得所有孩子中最大的不满度尽可能小。请帮助她确定糖果袋的最优分配方案！

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 150$)。

第二行包含 $N$ 个互不相同的整数，其中第 $i$ 个数字表示第 $i$ 个孩子最好的朋友的编号。孩子们用 $1$ 到 $N$ 的数字进行编号。

第三行包含 $N$ 个整数，其中第 $i$ 个数字等于第 $i$ 袋糖果中的糖果数量。这些数字不会超过 $10^9$。

输出格式

输出的第一行必须包含所有孩子中最大不满度的最小可能值。

第二行必须包含 $N$ 个由空格隔开的数字，其中第 $i$ 个数字表示分给第 $i$ 个孩子的糖果数量。如果存在多种最优分配方案，输出其中任意一种即可。

子任务

在占总分 20% 的测试数据中，对于所有 $i < N$，第 $i$ 个孩子最好的朋友是第 $i+1$ 个孩子，且第 $N$ 个孩子最好的朋友是第 $1$ 个孩子。

在另外占总分 30% 的测试数据中，满足 $N \le 20$。

样例

输入样例 1

3
2 1 3
3 8 5

输出样例 1

2
5 3 8

输入样例 2

5
3 5 4 1 2
24 45 39 19 16

输出样例 2

8
16 39 24 19 45

输入样例 3

8
6 3 7 1 4 8 2 5
6 5 2 4 7 4 4 3

输出样例 3

2
3 4 4 4 6 5 2 7