Bit’s request

Hello everyone. My name is Bit and I am the chief accountant of the Republic of Baitland! And recently I was assigned the following task.

There are $n$ ministers in Byteland. Each of the ministers considers one minister to be his best friend. Ministers are an extremely unusual people: no two ministers consider the same minister their best friend, but perhaps some minister considers himself his best friend!

Recently, a new order came: to assign new salaries to all ministers (a total of $n$ new salaries). However, there is a problem: salaries are not necessarily equal! Because of this, some ministers may break up. Namely: the frustration of the $i$-th minister will be equal to the absolute difference between his salary and the salary of his best friend.

And here is my task: to distribute the payments so that the maximum upset of any of the ministers turned out to be the minimum possible.

But this task turned out to be too difficult for me. Please help me solve it, otherwise Baitland will be mired in a terrible economic crisis.

Input

The first line contains one number $n(n\le 150)$ — the total number of ministers.

The second line contains $n$ different numbers. The $i$-th number is the number of the minister’s best friend under the number $i$.

The third line contains $n$ numbers, where the $i$-th number is the size of the next salary. The size of each salary does not exceed $10^9$.

Output

The first line should contain the minimum possible maximum disorder of any of the ministers.

The second line should contain $n$ numbers separated by a space, where the $i$-th number indicates the amount of salary that was assigned to the $i$-th minister. If there are several optimal salary distributions, output anyone.

Examples