Read problems statements in [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

A permutation is an array consisting of $N$ distinct integers from $1$ to $N$ in arbitrary order.

Chef has two permutation arrays $A$ and $P$ of length $N$. Chef performs the following three types of operations on the array $A$:
$1$ : Permute the array $A$ according to the order defined by permutation $P$.That is, replace $A$ with the array $B$ where $B[P[i]]=A[i]$.
$2 \ x \ y$ : Swap the elements at positions $x$ and $y$ in $A$.
$3 \ x$ : Output the element at position $x$ in array $A$. 

For each operation of type $3$, Chef wants you to output the element at position $x$ in array $A$ after all preceding operations have been applied.

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
The first line of each test case contains a single integer $N$.
The second line contains $N$ integers denoting elements of array $A$.
The third line contains $N$ integers denoting elements of array $P$.
The fourth line contains a single integer $Q$, denoting the number of operations to be performed.
$Q$ lines follow, each describing an operation of one of the three types above.

------ Output ------
For each test case, for each query of type $3$, output the answer in a separate line.

------ Constraints ------
$1 ≤ T ≤ 1000$
$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ A[i],P[i], x, y ≤ N$
$A$ and $P$ are permutations.
$x\ne y$ in type $2$ operations.
The sum of $N$ and the sum of $Q$ over all test cases do not exceed $10^{5}$.

----- Sample Input 1 ------ 
1

3

1 2 3

2 3 1

3

1

2 2 3

3 1
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
Initially, array $A$ is $[1,2,3]$.
It changes as follows: $[1,2,3]$ -> $[3,1,2]$ -> $[3,2,1]$.
So, we output element at position $1$ in array $A$, which is $3$.

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Combinatorics

Range queries

Data structures

Tree queries
Skill types: Data structures

Range queries

Starter code:

Solutions:
def get_value(k, ind, cycles, cycle, index_in_cycle):
	m = len(cycles[cycle[ind]])
	return cycles[cycle[ind]][index_in_cycle[ind] - k % m] - 1

def determine_cycles(p, n, cycles):
	visited = [False] * n
	i = 1
	while i <= n:
		if not visited[i - 1]:
			visited[i - 1] = True
			cycles.append([i])
			j = p[i - 1]
			while j != i:
				visited[j - 1] = True
				cycles[-1].append(j)
				j = p[j - 1]
		i = i + 1
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	p = list(map(int, input().split()))
	cycles = []
	cycle = [0] * n
	index_in_cycle = [0] * n
	determine_cycles(p, n, cycles)
	no_of_cycles = len(cycles)
	for i in range(no_of_cycles):
		cycle_i = cycles[i]
		for j in range(len(cycle_i)):
			c = cycles[i][j]
			cycle[c - 1] = i
			index_in_cycle[c - 1] = j
	no_of_permutations = 0
	q = int(input())
	for _ in range(q):
		query = list(map(int, input().split()))
		if query[0] == 1:
			no_of_permutations += 1
		elif query[0] == 2:
			x = query[1] - 1
			y = query[2] - 1
			x1 = get_value(no_of_permutations, x, cycles, cycle, index_in_cycle)
			y1 = get_value(no_of_permutations, y, cycles, cycle, index_in_cycle)
			(a[x1], a[y1]) = (a[y1], a[x1])
		else:
			ind = query[1] - 1
			print(a[get_value(no_of_permutations, ind, cycles, cycle, index_in_cycle)])


t = int(input())
for _ in range(t):
	n = int(input())
	A = ['X'] + list(map(int, input().split()))
	p = ['X'] + list(map(int, input().split()))
	cycle = {}
	cycle_name_of = {}
	index_in_cycle = {}
	already = {}
	for i in range(1, n + 1):
		if already.get(i, True):
			already[i] = False
			cycle[i] = [[i], 1]
			cycle_name_of[i] = i
			index_in_cycle[i] = cycle[i][1] - 1
			j = p[i]
			while j != i:
				cycle[i][0].append(j)
				cycle[i][1] += 1
				cycle_name_of[j] = i
				index_in_cycle[j] = cycle[i][1] - 1
				already[j] = False
				j = p[j]
	count = 0

	def find_original(index, count):
		the_cycle_it_belongs_to = cycle_name_of[index]
		m = cycle[the_cycle_it_belongs_to][1]
		elements = cycle[the_cycle_it_belongs_to][0]
		return elements[int((index_in_cycle[index] - count % m + m) % m)]
	q = int(input())
	for Q in range(q):
		l = list(map(int, input().split()))
		if l[0] == 1:
			count += 1
		elif l[0] == 2:
			a = find_original(l[1], count)
			b = find_original(l[2], count)
			(A[a], A[b]) = (A[b], A[a])
		elif l[0] == 3:
			print(A[find_original(l[1], count)])


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	P = list(map(int, input().split()))
	cur = []
	vis = {}
	for c in range(n):
		if c in vis:
			continue
		cur.append([])
		while True:
			if c in vis:
				break
			cur[-1].append(A[c])
			vis[c] = (len(cur) - 1, len(cur[-1]) - 1)
			c = P[c] - 1
	o = 0

	def g(cur, z):
		n = len(cur[z[0]])
		return cur[z[0]][((z[1] - o) % n + n) % n]

	def g2(cur, z, v):
		n = len(cur[z[0]])
		cur[z[0]][((z[1] - o) % n + n) % n] = v
	for _ in range(int(input())):
		s = list(map(int, input().split()))
		if len(s) == 1:
			o += 1
		elif s[0] == 2:
			z1 = vis[s[1] - 1]
			z2 = vis[s[2] - 1]
			x = g(cur, z1)
			y = g(cur, z2)
			g2(cur, z1, y)
			g2(cur, z2, x)
		else:
			z1 = vis[s[1] - 1]
			print(g(cur, z1))


import sys
input = sys.stdin.readline
import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	vis = [0] * (n + 1)
	arrs = []
	for i in range(n):
		if vis[i + 1] == 0:
			vis[i + 1] = 1
			l = [i + 1]
			while p[l[-1] - 1] != l[0]:
				vis[p[l[-1] - 1]] = 1
				l.append(p[l[-1] - 1])
			arrs.append(l)
	pos = [None] * (n + 1)
	for i in range(len(arrs)):
		for j in range(len(arrs[i])):
			pos[arrs[i][j]] = [i, j]
	ops = 0
	q = int(input())
	for qq in range(q):
		l = [int(x) for x in input().split()]
		if l[0] == 1:
			ops = ops + 1
			continue
		if l[0] == 2:
			x = l[1]
			y = l[2]
			i = pos[x][0]
			j = pos[x][1]
			j = (j - ops + len(arrs[i])) % len(arrs[i])
			p1 = arrs[i][j] - 1
			i = pos[y][0]
			j = pos[y][1]
			j = (j - ops + len(arrs[i])) % len(arrs[i])
			p2 = arrs[i][j] - 1
			(a[p1], a[p2]) = (a[p2], a[p1])
			continue
		if l[0] == 3:
			x = l[1]
			i = pos[x][0]
			j = pos[x][1]
			j = (j - ops + len(arrs[i])) % len(arrs[i])
			p = arrs[i][j] - 1
			print(a[p])