A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. Return the head of the copied list.

For this problem, encode each node as "val,randomIndex" where randomIndex is the 0-based index of the random pointer node, or -1 if null.

Example:

Input:
7 -1
13 0
11 4
10 2
1 0
Output: (same structure)
7 -1
13 0
11 4
10 2
1 0

Input format: n lines of "val randomIndex".

Output format: Same format for the deep copy.