/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// create LL
		Node head = createNewNode(1);
		Node two = createNewNode(2);
		Node three = createNewNode(3);
		Node four = createNewNode(4);
		
		head.next = two;
		two.next = three;
		three.next = four;
		
		head.random = three;
		two.random = four;
		
		Node clonedList = clone(head);
		Node current = clonedList;
		while(current != null)
		{
			System.out.println("val: "+ current.value );
			if( current.random != null)
				System.out.println(" random: " + current.random.value);
			current = current.next;
		}
	}
	
	public static Node clone(Node head)
	{
		if( head == null )
		{
			return null;
		}
		
		Node current = head;
		while( current != null) 
		{
			Node temp = createNewNode(current.value);
			temp.next = current.next;
			current.next = temp;
			current = temp.next;
		}
		
		Node clonedHead = head.next;
		
		current = head;
		while( current != null )
		{
			if( current.random != null) 
			{
				current.next.random = current.random.next;	
			}
			
			current = current.next.next;
		}
		
		current = head;
		while( current != null )
		{
			Node temp = current.next;
			current.next = temp.next;
			current = current.next;
			if( current != null)
			{
				temp.next = current.next;	
			}
		}
		
		return clonedHead;
	}
	
	public static Node createNewNode(int value)
	{
		Node node = new Node(value);
		return node;
	}
}

class Node
{
	int value;
	Node next;
	Node random;
	
	public Node(int val)
	{
		value = val;
	}
}