Deep Copy of a Linked List with Random Pointer

Given a linked list of n nodes where each node contains an integer value, a pointer to the next node, and a pointer to a random node (or null), your task is to create a deep copy of the list. The deep copy should duplicate the entire list, including the structure provided by the random pointers.

Note: The input linked list is represented by two lines. The first line contains the n integer values (in order). The second line contains n integers where the i-th number represents the index (0-indexed) of the random pointer for the i-th node or -1 if there is no random pointer. The next pointers are implicitly defined by the order of the nodes.

Your copied linked list should have exactly the same values and random pointer relationships as the original list. However, the nodes themselves must be newly allocated (i.e. deep copied).

inputFormat

The input is read from stdin and has the following format:

 n
 v1 v2 ... vn
 r1 r2 ... rn

Where:

• n is the number of nodes in the linked list. (n ≥ 0)
• v1, v2, ..., vn are the integer values of the nodes.
• r1, r2, ..., rn are the random pointer indices for the corresponding nodes. If ri is -1, then the i-th node's random pointer is null; otherwise, it points to the node at index ri (0-indexed).

outputFormat

The output should be printed to stdout in the same format as the input representation of the list:

 v1 v2 ... vn
 r1 r2 ... rn

This output represents the deep-copied list. The list’s structure, including the order and the random pointer relationships, should be identical to the original input list.

## sample

5
7 13 11 10 1
-1 0 4 2 0

7 13 11 10 1
-1 0 4 2 0

</p>