Problem:
 Score : 1000 points    Problem Statement For two permutations p and q of the integers from 1 through N , let f(p,q) be the permutation that satisfies the following:   The p_i -th element ( 1 \leq i \leq N ) in f(p,q) is q_i .
Here, p_i and q_i respectively denote the i -th element in p and q .   You are given two permutations p and q of the integers from 1 through N .
We will now define a sequence { a_n } of permutations of the integers from 1 through N , as follows:   a_1=p , a_2=q  a_{n+2}=f(a_n,a_{n+1}) ( n \geq 1 )   Given a positive integer K , find a_K .      Constraints  1 \leq N \leq 10^5  1 \leq K \leq 10^9  p and q are permutations of the integers from 1 through N .         Input Input is given from Standard Input in the following format:  N  K  p_1  ...  p_N  q_1  ...  q_N       Output Print N integers, with spaces in between.
The i -th integer ( 1 \leq i \leq N ) should be the i -th element in a_K .        Sample Input 1 3 3
1 2 3
3 2 1      Sample Output 1 3 2 1  Since a_3=f(p,q) , we just need to find f(p,q) .
We have p_i=i here, so f(p,q)=q .       Sample Input 2 5 5
4 5 1 2 3
3 2 1 5 4      Sample Output 2 4 3 2 1 5       Sample Input 3 10 1000000000
7 10 6 5 4 2 9 1 3 8
4 1 9 2 3 7 8 10 6 5      Sample Output 3 7 9 4 8 2 5 1 6 10 3

Solution (Python):
def perpro(q,p):
    res=[-1]*len(p)
    for i in range(len(p)):
        res[i]=q[p[i]]
    return res

def inverse(p):
    res=[-1]*len(p)
    for i in range(len(p)):
        res[p[i]]=i
    return res

N,K=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))

ide_ele=[i for i in range(N)]

for i in range(N):
    p[i]-=1
    q[i]-=1

invp=[-1]*N
for i in range(N):
    invp[p[i]]=i

invq=[-1]*N
for i in range(N):
    invq[q[i]]=i

A=perpro(q,perpro(invp,perpro(invq,p)))

kthA=[A]
for i in range(30):
    kthA.append(perpro(kthA[-1],kthA[-1]))

def _nthA(n):
    res=ide_ele
    for i in range(30):
        if n>>i&1==1:
            res=perpro(res,kthA[i])
    return res

def ntha(n):
    qqq=n//4
    r=n%4
    if r==0:
        return _nthA(qqq)
    elif r==1:
        return perpro(_nthA(qqq),q)
    elif r==2:
        return perpro(_nthA(qqq),perpro(q,invp))
    else:
        return perpro(_nthA(qqq),perpro(q,perpro(invp,invq)))

Q=(K-1)//3
r=(K-1)%3
ans=[]
if Q==0:
    if K==1:
        ans=p
    elif K==2:
        ans=q
    else:
        ans=perpro(q,invp)
else:
    if Q%2==0:
        if r==0:
            mid=p
            a=ntha(2*Q-1)
            ans=perpro(a,perpro(mid,inverse(a)))
        elif r==1:
            mid=q
            a=ntha(2*Q)
            ans=perpro(a,perpro(mid,inverse(a)))
        else:
            mid=perpro(q,invp)
            a=ntha(2*Q)
            ans=perpro(a,perpro(mid,inverse(a)))
    else:
        if r==0:
            mid=invp
            a=ntha(2*Q-1)
            ans=perpro(a,perpro(mid,inverse(a)))
        elif r==1:
            mid=invq
            a=ntha(2*Q)
            ans=perpro(a,perpro(mid,inverse(a)))
        else:
            mid=perpro(invq,p)
            a=ntha(2*Q)
            ans=perpro(a,perpro(mid,inverse(a)))

for i in range(N):
    ans[i]+=1

print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline

import numpy as np



N,K = map(int,input().split())

P,Q = [np.array(input().split(), dtype=np.int32) for _ in range(2)]

P -= 1
Q -= 1

def inv(a):
    x = np.empty_like(a)
    x[a] = np.arange(len(x))
    return x

def mult_inv(a,b):
    
    c = np.empty_like(a)
    c[b] = a
    return c

def mult(a,b):
    return mult_inv(a,inv(b))

def power(a,n):
    if n == 0:
        return np.arange(len(a))
    x = power(a,n//2)
    x = mult(x,x)
    return mult(a,x) if n&1 else x

A = [P,Q]
for _ in range(4):
    A.append(mult_inv(A[-1],A[-2]))

q,r = divmod(K-1,6)
QP_Q_P = mult(mult_inv(mult_inv(Q,P),Q),P)
left = power(QP_Q_P,q)
right = inv(left)
answer = mult(mult(left, A[r]), right) + 1

print(' '.join(answer.astype(str)))

Solution (Python):
N,K=map(int,input().split());p=[int(i)-1for i in input().split()];q=[int(i)-1for i in input().split()];T=lambda s,t:[s[t[i]]for i in range(N)];m=[[0for i in[0]*N]for i in[0]*6];m[0]=p;m[1]=q
def I(s):
 r=[0]*N
 for i in range(N):r[s[i]]=i
 return r
for i in range(4):m[i+2]=T(m[i+1],I(m[i]))
E=lambda s,k:T(E(T(s,s),k//2),s)if k%2 else (E(T(s,s),k//2)if k else list(range(N)));t=E(T(T(T(q,I(p)),I(q)),p),~-K//6);print(*[str(i+1)for i in T(T(t,m[~-K%6]),I(t))])

Solution (Python):
N,K=map(int,input().split());p=[int(i)-1for i in input().split()];q=[int(i)-1for i in input().split()];T=lambda s,t:[s[t[i]]for i in range(N)];m=[[0for i in[0]*N]for i in[0]*6];m[0]=p;m[1]=q
def I(s):
 r=[0]*N
 for i in range(N):r[s[i]]=i
 return r
for i in range(4):m[i+2]=T(m[i+1],I(m[i]))
E=lambda s,k:T(E(T(s,s),k//2),s)if k%2 else (E(T(s,s),k//2)if k else list(range(N)));t=E(T(T(T(q,I(p)),I(q)),p),~-K//6);print(" ".join([str(i+1)for i in T(T(t,m[~-K%6]),I(t))]))

Solution (Python):
N,K=map(int,input().split())
p=[int(i)-1for i in input().split()]
q=[int(i)-1for i in input().split()]
T=lambda s,t:[s[t[i]]for i in range(N)]
m=[[0for i in[0]*N]for i in[0]*6];m[0]=p;m[1]=q
def I(s):
 r=[0]*N
 for i in range(N):r[s[i]]=i
 return r
for i in range(4):m[i+2]=T(m[i+1],I(m[i]))
E=lambda s,k:T(E(T(s,s),k//2),s)if k%2 else (E(T(s,s),k//2)if k else list(range(N)))
t=E(T(T(T(q,I(p)),I(q)),p),~-K//6);print(" ".join([str(i+1)for i in T(T(t,m[~-K%6]),I(t))]))

Solution (Python):
N,K=map(int,input().split());p=[int(i)-1 for i in input().split()];q=[int(i)-1 for i in input().split()];T=lambda s,t:[s[t[i]] for i in range(N)];m=[[0 for i in [0]*N] for i in [0]*6];m[0]=p;m[1]=q
def I(s):
 r=[0]*N
 for i in range(N):r[s[i]]=i
 return r
for i in range(4):m[i+2]=T(m[i+1],I(m[i]))
E=lambda s,k:(E(T(s,s),k//2) if k!=0 else list(range(N)))if k%2==0 else T(E(T(s,s),k//2),s);t=E(T(T(T(q,I(p)),I(q)),p),~-K//6);print(" ".join([str(i+1) for i in T(T(t,m[~-K%6]),I(t))]))

Solution (Python):
N,K=map(int,input().split());p=[int(i)-1 for i in input().split()];q=[int(i)-1 for i in input().split()]
def I(s):
 r=[0]*N
 for i in range(N):r[s[i]]=i
 return r
def T(s,t):return [s[t[i]] for i in range(N)]
m=[[0 for i in [0]*N] for i in [0]*6]
for i in range(N):m[0][i]=p[i];m[1][i]=q[i]
for i in range(4):m[i+2]=T(m[i+1],I(m[i]))
def E(s,k):
 if k%2==0:
  return E(T(s,s),k//2) if k!=0 else list(range(N))
 else:
  return T(E(T(s,s),k//2),s)
t=E(T(T(T(q,I(p)),I(q)),p),~-K//6);print(" ".join([str(i+1) for i in T(T(t,m[~-K%6]),I(t))]))

Solution (Python):
N,K=map(int,input().split());p=[int(i)-1 for i in input().split()];q=[int(i)-1 for i in input().split()]
def I(s):
 r=[0 for i in range(N)]
 for i in range(N):r[s[i]]=i
 return r
def T(s,t):
 r=[0 for i in range(N)]
 for i in range(N):r[i]=s[t[i]]
 return r
m=[[0 for i in range(N)] for i in range(6)];A=T(T(T(q,I(p)),I(q)),p);X=(K-1)//6
for i in range(N):m[0][i]=p[i];m[1][i]=q[i]
for i in range(2,6):m[i]=T(m[i-1],I(m[i-2]))
def E(s,k):
 if k==0:
  return [i for i in range(N)]
 elif k==1:
  return s
 elif k%2==0:
  return E(T(s,s),k//2)
 else:
  return T(E(T(s,s),k//2),s)
t=E(A,X);a=T(T(t,m[(K-1)%6]),I(t));print(" ".join([str(i+1) for i in a]))

Solution (Python):
n,k = map(int,input().split())

p = list(map(int,input().split()))
q = list(map(int,input().split()))

def perprod(x,y): 
    nn = len(x)
    ret = [0 for i in range(nn)]

    for i in range(nn):
        ret[i] = x[y[i]-1]

    return ret

def perinv(x): 
    nn = len(x)
    ret = [0 for i in range(nn)]
    for i in range(nn):
        ret[x[i]-1] =i+1

    return ret 

amari = (k-1) % 6
e = (k-1) //6

a =[[] for i in range(6)]

a[0] = p
a[1] = q
a[2] = perprod(a[1],perinv(a[0]))
a[3] = perprod(a[2],perinv(a[1]))
a[4] = perprod(a[3],perinv(a[2]))
a[5] = perprod(a[4],perinv(a[3]))

pp = perprod(perprod(a[1],perinv(a[0])),perprod(perinv(a[1]),a[0]))


ans1 = [i+1 for i in range(n)]

while e>0:
    if(e & 1): ans1 = perprod(ans1,pp)
    pp = perprod(pp,pp)
    e >>= 1

ans2 = perinv(ans1)

ans = perprod(ans1,a[amari])
ans = perprod(ans,ans2)

print(*ans)

Solution (Python):
N,K=map(int,input().split())
p=[int(i)-1 for i in input().split()]
q=[int(i)-1 for i in input().split()]
e=[i for i in range(N)]
def cir(x,y):
    z=[0]*N
    for i in range(N):
        z[i]=x[y[i]]
    return z
def inv(x):
    z=[0]*N
    for i in range(N):
        z[x[i]]=i
    return z
def f(x,y):
    return cir(y,inv(x))

def double(x,k):
    a=k
    t=x
    num=e
    while a!=0:
        if a%2==1:
            num=cir(num,t)
        a=a//2
        t=cir(t,t)
    return num
P=inv(p)
Q=inv(q)

quo=(K-1)//6
r=K-quo*6-1
X=cir(q,cir(P,cir(Q,p)))


Z=double(X,quo)
A=cir(Z,cir(p,inv(Z)))
B=cir(Z,cir(q,inv(Z)))

def g(n):
    if n==0:
        return A
    if n==1:
        return B
    return f(g(n-2),g(n-1))
L=g(r)
for i in range(N):
    L[i]+=1
print(' '.join(map(str,L)))

Solution (Python):
from operator import itemgetter


def get_identity():
    return list(range(1, n + 1))


def composition(ppp, qqq):
    return [ppp[q - 1] for q in qqq]


def reverse_composition(ppp, qqq):
    return [ppp[i] for i, q in sorted(enumerate(qqq), key=itemgetter(1))]


def solve(k, ppp, qqq):
    qp = reverse_composition(qqq, ppp)
    qpq = reverse_composition(qp, qqq)
    qpqp = composition(qpq, ppp)

    l, m = divmod(k - 1, 6)
    res = get_identity()
    tmp = qpqp
    while l:
        if l % 2 == 1:
            res = composition(res, tmp)
        tmp = composition(tmp, tmp)
        l >>= 1

    m = (k - 1) % 6
    if m == 0:
        base = ppp
    elif m == 1:
        base = qqq
    elif m == 2:
        base = reverse_composition(qqq, ppp)
    elif m == 3:
        res = composition(res, qqq)
        base = reverse_composition(get_identity(), ppp)
    elif m == 4:
        res = composition(res, qqq)
        res = reverse_composition(res, ppp)
        base = reverse_composition(get_identity(), qqq)
    elif m == 5:
        res = composition(res, qqq)
        res = reverse_composition(res, ppp)
        base = reverse_composition(get_identity(), qqq)
        base = composition(base, ppp)
    else:
        raise NotImplementedError

    ans = composition(res, base)
    ans = reverse_composition(ans, res)
    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(int, input().split()))
print(*solve(k, ppp, qqq))

Solution (Python):
from operator import itemgetter


def get_identity():
    return list(range(1, n + 1))


def composition(ppp, qqq):
    return [ppp[q - 1] for q in qqq]


def reverse_composition(ppp, qqq):
    return [ppp[i] for i, q in sorted(enumerate(qqq), key=itemgetter(1))]


def solve(k, ppp, qqq):
    qp = reverse_composition(qqq, ppp)
    qpq = reverse_composition(qp, qqq)
    qpqp = composition(qpq, ppp)
   
    l, m = divmod(k - 1, 6)
    res = get_identity()
    tmp = qpqp
    while l:
        if l % 2 == 1:
            res = composition(res, tmp)
        tmp = composition(tmp, tmp)
        l >>= 1

    m = (k - 1) % 6
    if m == 0:
        base = ppp
    elif m == 1:
        base = qqq
    elif m == 2:
        base = reverse_composition(qqq, ppp)
    elif m == 3:
        res = composition(res, qqq)
        base = reverse_composition(get_identity(), ppp)
    elif m == 4:
        res = composition(res, qqq)
        res = reverse_composition(res, ppp)
        base = reverse_composition(get_identity(), qqq)
    elif m == 5:
        res = composition(res, qqq)
        res = reverse_composition(res, ppp)
        base = reverse_composition(get_identity(), qqq)
        base = composition(base, ppp)
    else:
        raise NotImplementedError

    ans = composition(res, base)
    ans = reverse_composition(ans, res)
    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
qqq = list(map(int, input().split()))
print(*solve(k, ppp, qqq))

Solution (Python):
N,K=map(int,input().split())
p=[int(i)-1 for i in input().split()]
q=[int(i)-1 for i in input().split()]
def inv(seq):
    res=[0 for i in range(N)]
    for i in range(N):
        res[seq[i]]=i
    return res
def times(seq1,seq2):
    res=[0 for i in range(N)]
    for i in range(N):
        res[i]=seq1[seq2[i]]
    return res
md=[[0 for i in range(N)] for i in range(6)]
for i in range(N):
    md[0][i]=p[i]
    md[1][i]=q[i]
for i in range(2,6):
    md[i]=times(md[i-1],inv(md[i-2]))
A=times(times(q,inv(p)),times(inv(q),p))
T=(K-1)//6
def expseq(seq,k):
    if k==0:
        return [i for i in range(N)]
    elif k==1:
        return seq
    elif k%2==0:
        return expseq(times(seq,seq),k//2)
    else:
        return times(expseq(times(seq,seq),k//2),seq)
tmp=expseq(A,T)
ans=times(times(tmp,md[(K-1)%6]),inv(tmp))
print(" ".join([str(i+1) for i in ans]))

Solution (Python):
N,K=map(int,input().split())
p=[int(i)-1 for i in input().split()]
q=[int(i)-1 for i in input().split()]
def inv(seq):
    res=[0 for i in range(N)]
    for i in range(N):
        res[seq[i]]=i
    return res
def times(seq1,seq2):
    res=[0 for i in range(N)]
    for i in range(N):
        res[i]=seq1[seq2[i]]
    return res
md=[[0 for i in range(N)] for i in range(6)]
for i in range(N):
    md[0][i]=p[i]
    md[1][i]=q[i]
for i in range(2,6):
    md[i]=times(md[i-1],inv(md[i-2]))
A=times(times(times(q,inv(p)),inv(q)),p)
T=(K-1)//6
def expseq(seq,k):
    if k==0:
        return [i for i in range(N)]
    elif k==1:
        return seq
    elif k%2==0:
        return expseq(times(seq,seq),k//2)
    else:
        return times(expseq(times(seq,seq),k//2),seq)
tmp=expseq(A,T)
ans=times(times(tmp,md[(K-1)%6]),inv(tmp))
print(" ".join([str(i+1) for i in ans]))

Solution (Python):
from sys import stdin, stdout
from itertools import repeat
def pr(a):
    a = [x + 1 for x in a]
    stdout.write(' '.join(map(str, a)))
def main():
    n, k = map(int, stdin.readline().split())
    p = map(int, stdin.readline().split(), repeat(10, n))
    q = map(int, stdin.readline().split(), repeat(10, n))
    p = [x - 1 for x in p]
    q = [x - 1 for x in q]
    if k == 1:
        pr(p)
        return
    if k == 2:
        pr(q)
        return
    def inv(a):
        r = a[:]
        for i, x in enumerate(a):
            r[x] = i
        return r
    def comp(a, b):
        return [a[x] for x in b]
    pinv = inv(p)
    qinv = inv(q)
    b = q
    a = comp(q, pinv)
    if k == 3:
        pr(a)
        return
    w = [b, a]
    for i in xrange(4, 8):
        a, b = comp(a, inv(b)), a
        if k == i:
            pr(a)
            return
        w.append(a)
    y = range(n)
    x = comp(q, comp(pinv, comp(qinv, p)))
    r = (k - 8) / 6 + 1
    while r:
        if r & 1:
            y = comp(x, y)
        x = comp(x, x)
        r >>= 1
    t = comp(y, comp(w[(k - 8) % 6], inv(y)))
    pr(t)
main()