The Little Elephant has two permutations a and b of length n, consisting of numbers from 1 to n, inclusive. Let's denote the i-th (1 ≤ i ≤ n) element of the permutation a as ai, the j-th (1 ≤ j ≤ n) element of the permutation b — as bj.

The distance between permutations a and b is the minimum absolute value of the difference between the positions of the occurrences of some number in a and in b. More formally, it's such minimum |i - j|, that ai = bj.

A cyclic shift number i (1 ≤ i ≤ n) of permutation b consisting from n elements is a permutation bibi + 1... bnb1b2... bi - 1. Overall a permutation has n cyclic shifts.

The Little Elephant wonders, for all cyclic shifts of permutation b, what is the distance between the cyclic shift and permutation a?

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the size of the permutations. The second line contains permutation a as n distinct numbers from 1 to n, inclusive. The numbers are separated with single spaces. The third line contains permutation b in the same format.

Output

In n lines print n integers — the answers for cyclic shifts. Print the answers to the shifts in the order of the shifts' numeration in permutation b, that is, first for the 1-st cyclic shift, then for the 2-nd, and so on.

Examples

Input

2
1 2
2 1


Output

1
0


Input

4
2 1 3 4
3 4 2 1


Output

2
1
0
1
#include <bits/stdc++.h>
using namespace std;
int n;
multiset<int> R, L;
int a[100005], b[100005];
int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    int num;
    cin >> num;
    a[num] = i;
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    if (i - a[b[i]] >= 0)
      R.insert(i - a[b[i]]);
    else
      L.insert(i - a[b[i]]);
  }
  multiset<int>::iterator it;
  for (int i = 0; i < n; i++) {
    it = R.lower_bound(i);
    int res;
    if (it != R.end()) res = (*it) - i;
    if (it != R.begin()) res = res = min(res, -1 * (*(--it) - i));
    it = L.end();
    if (L.size() > 0) res = min(res, -1 * (*(--it) - i));
    cout << res << endl;
    if (i - a[b[i]] >= 0)
      R.erase(R.find(i - a[b[i]]));
    else
      L.erase(L.find(i - a[b[i]]));
    R.insert(i + n - a[b[i]]);
  }
  return 0;
}
