길이가 $n$인 세 순열 $a$, $b$, $c$가 주어집니다. 배열 $a$에 순열 $c$를 적용하면 모든 $i$에 대해 $d[c[i]] = a[i]$를 만족하는 배열 $d$가 만들어집니다.
$a$에 $c$를 적용하기 전에, 순열 $c$에 연산을 원하는 만큼 수행할 수 있습니다. 한 번의 연산에서 두 인덱스 $i$와 $j$를 선택하여 $c[i]$와 $c[j]$를 교환할 수 있습니다.
$0$부터 $n$까지의 각 $k$에 대해, 수정된 순열 $c$를 $a$에 적용하여 얻은 배열이 $b$와 정확히 $k$개의 위치에서 다르게 되도록 하는 최소 연산 횟수를 구하거나, 그것이 불가능함을 판별하세요.
입력
첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t$ ($1 \le t \le 5 \cdot 10^4$)가 주어집니다.
각 테스트 케이스의 첫 번째 줄에는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.
다음 세 줄에는 길이가 $n$인 순열 $a$, $b$, $c$가 주어집니다. 각 순열은 $1$부터 $n$까지의 모든 정수를 정확히 한 번씩 포함합니다.
모든 테스트 케이스에 걸친 $n$의 합은 $10^6$을 초과하지 않습니다.
출력
각 테스트 케이스마다 $n + 1$개의 정수를 출력합니다. 그중 $k$번째 정수는 정확히 $k$개의 차이를 얻기 위해 필요한 최소 연산 횟수이며, 불가능한 경우 $-1$입니다.
예제
입력 1
2 3 1 2 3 3 1 2 2 3 1 2 2 1 1 2 1 2
출력 1
0 -1 1 2 1 -1 0
참고
첫 번째 테스트 케이스에서 배열은 $a = [1, 2, 3]$입니다. 순열 $c = [2, 3, 1]$을 적용한 후, $1$번째 위치의 원소는 $2$번째로, $2$번째 위치의 원소는 $3$번째로, $3$번째 위치의 원소는 $1$번째로 이동하여 결과 배열은 $d = [3, 1, 2]$가 됩니다. 이 경우 배열 $b$와 일치합니다. 따라서 $k = 0$개의 차이에 대한 답은 $0$번의 연산입니다.