H. Permutation Composition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alex like math, and permutations are math. So he made a problem about permutations.

A permutation is a list of distinct integers from $$$1 \dots N$$$. Alex gives you two permutations, of length $$$N$$$: $$$a_1, a_2, \dots, a_N$$$ and $$$b_1, b_2, \dots, b_N$$$.

Alex is interested in permutation composition. Thus, he created two operations on the permutations:

Type 1 operation:

Compute $$$a'_i = b_{a_i}$$$ for all $$$1 \leq i \leq N$$$. Then, assign $$$a_i = a'_i$$$ for all $$$1 \leq i \leq N$$$.

Type 2 operation:

Compute $$$b'_i = a_{b_i}$$$ for all $$$1 \leq i \leq N$$$. Then, assign $$$b_i = b'_i$$$ for all $$$1 \leq i \leq N$$$.

He will then apply those operations $$$Q$$$ times and ask you to print out both permutations after all the operations.

However, Alex realized this problem was too hard for him to solve. So he decided to make it harder by making the operations more complicated:

Type 1 operation:

Compute $$$a'_i = a_{b_{a_i}}$$$ for all $$$1 \leq i \leq N$$$. Then, assign $$$a_i = a'_i$$$ for all $$$1 \leq i \leq N$$$.

Type 2 operation:

Compute $$$b'_i = b_{a_{b_i}}$$$ for all $$$1 \leq i \leq N$$$. Then, assign $$$b_i = b'_i$$$ for all $$$1 \leq i \leq N$$$.

Alex will now apply the new operations instead of the old operations to the permutations $$$Q$$$ times and asks you to print out both permutations after all the operations.

Input

The first line of input contains one integer $$$N \ (1 \leq N \leq 10^5)$$$.

The following line of input contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N \ (1 \leq a_i \leq N)$$$. It is guaranteed $$$a$$$ is a permutation.

The following line of input contains $$$N$$$ integers $$$b_1, b_2, \dots, b_N \ (1 \leq b_i \leq N)$$$. It is guaranteed $$$b$$$ is a permutation.

The following line of input contains one integer $$$Q \ (1 \leq Q \leq 10^5)$$$.

The following $$$Q$$$ lines of input contain $$$1$$$, or $$$2$$$, specifying which type of operation is performed.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1−4$$$ satisfy $$$n \leq 5000$$$, $$$q \leq 5000$$$.

Tests $$$5-12$$$ satisfy $$$a_i = i$$$ for $$$1 \leq i \leq N$$$.

Tests $$$13-20$$$ satisfy no additional constraints.

Output

Output two lines.

The first line contains integers $$$a_1, a_2, \dots a_N$$$, representing $$$a$$$ after all the operations.

The second line contains integers $$$b_1, b_2, \dots b_N$$$, representing $$$b$$$ after all the operations.

Example
Input
5
1 3 4 2 5
5 4 3 1 2
2
1
2
Output
5 4 1 2 3 
3 4 5 2 1
Note

In the sample, initially, $$$a = 1, 3, 4, 2, 5$$$, and $$$b = 5, 4, 3, 1, 2$$$

In the first operation, which is a type 1 operation, $$$a_{b_{a_1}} = 5$$$, $$$a_{b_{a_2}} = 4$$$, $$$a_{b_{a_3}} = 1$$$, $$$a_{b_{a_4}} = 2$$$, $$$a_{b_{a_5}} = 3$$$. Thus, $$$a$$$ becomes $$$5, 4, 1, 2, 3$$$, and $$$b = 5, 4, 3, 1, 2$$$ stays the same.

In the second operation, which is a type 2 operation, $$$b_{a_{b_1}} = 3$$$, $$$b_{a_{b_2}} = 4$$$, $$$b_{a_{b_3}} = 5$$$, $$$b_{a_{b_4}} = 2$$$, $$$b_{a_{b_5}} = 1$$$. Thus, after the operation, $$$a = 5, 4, 1, 2, 3$$$, and $$$b = 3, 4, 5, 2, 1$$$.

In the third operation, which is a type 2 operation, $$$b_{a_{b_1}} = 3$$$, $$$b_{a_{b_2}} = 4$$$, $$$b_{a_{b_3}} = 5$$$, $$$b_{a_{b_4}} = 2$$$, $$$b_{a_{b_5}} = 1$$$. Thus, after the operation, $$$a = 5, 4, 1, 2, 3$$$, and $$$b = 3, 4, 5, 2, 1$$$.

Thus, after all the operations $$$a = 5, 4, 1, 2, 3$$$, and $$$b = 3, 4, 5, 2, 1$$$.

—

Problem Idea: Alex_C

Problem Preparation: Alex_C

Occurrences: Advanced H