Сізге ұзындығы $n$ болатын үш $a$, $b$ және $c$ орын алмастыруы берілген. $a$ массивіне $c$ орын алмастыруын қолдану барлық $i$ үшін $d[c[i]] = a[i]$ орындалатындай $d$ массивін береді.
$c$ орын алмастыруын $a$-ға қолданбас бұрын, сіз $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$ операция болады.