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;
const int MAXN = 100010;
int n, a[MAXN], b[MAXN], ia[MAXN], ans[MAXN];
priority_queue<pair<int, int> > pq1, pq2;
int main() {
  if (fopen("input.txt", "r")) {
    freopen("input.txt", "r", stdin);
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    a[i]--;
    ia[a[i]] = i;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &b[i]);
    b[i]--;
  }
  for (int i = 0; i < n; i++) ans[i] = 1e9;
  for (int i = 0; i < n; i++) {
    if (i <= ia[b[i]]) {
      pq1.push(pair<int, int>(-(ia[b[i]] - i), i));
    } else {
      pq2.push(pair<int, int>(-(i - ia[b[i]]), i));
    }
    ans[0] = min(ans[0], abs(i - ia[b[i]]));
  }
  for (int i = 1; i < n; i++) {
    pq2.push(pair<int, int>(-(n - ia[b[i - 1]] - 1 + i), n + i));
    while (!pq2.empty() && -pq2.top().first - i < 0) {
      pq1.push(pair<int, int>(-(1 - i), pq2.top().second));
      pq2.pop();
    }
    while (!pq1.empty() && pq1.top().second - i < 0) pq1.pop();
    if (!pq1.empty()) ans[i] = min(ans[i], -pq1.top().first + i);
    if (!pq2.empty()) ans[i] = min(ans[i], -pq2.top().first - i);
  }
  for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
}
