Problem: Mahmoud was trying to solve the vertex cover problem on trees. The problem statement is:

Given an undirected tree consisting of n nodes, find the minimum number of vertices that cover all the edges. Formally, we need to find a set of vertices such that for each edge (u, v) that belongs to the tree, either u is in the set, or v is in the set, or both are in the set. Mahmoud has found the following algorithm:

  * Root the tree at node 1. 
  * Count the number of nodes at an even depth. Let it be evenCnt. 
  * Count the number of nodes at an odd depth. Let it be oddCnt. 
  * The answer is the minimum between evenCnt and oddCnt. 



The depth of a node in a tree is the number of edges in the shortest path between this node and the root. The depth of the root is 0.

Ehab told Mahmoud that this algorithm is wrong, but he didn't believe because he had tested his algorithm against many trees and it worked, so Ehab asked you to find 2 trees consisting of n nodes. The algorithm should find an incorrect answer for the first tree and a correct answer for the second one.

Input

The only line contains an integer n (2 ≤ n ≤ 105), the number of nodes in the desired trees.

Output

The output should consist of 2 independent sections, each containing a tree. The algorithm should find an incorrect answer for the tree in the first section and a correct answer for the tree in the second. If a tree doesn't exist for some section, output "-1" (without quotes) for that section only.

If the answer for a section exists, it should contain n - 1 lines, each containing 2 space-separated integers u and v (1 ≤ u, v ≤ n), which means that there's an undirected edge between node u and node v. If the given graph isn't a tree or it doesn't follow the format, you'll receive wrong answer verdict.

If there are multiple answers, you can print any of them.

Examples

Input

2


Output

-1
1 2


Input

8


Output

1 2
1 3
2 4
2 5
3 6
4 7
4 8
1 2
1 3
2 4
2 5
2 6
3 7
6 8

Note

In the first sample, there is only 1 tree with 2 nodes (node 1 connected to node 2). The algorithm will produce a correct answer in it so we printed  - 1 in the first section, but notice that we printed this tree in the second section.

In the second sample:

In the first tree, the algorithm will find an answer with 4 nodes, while there exists an answer with 3 nodes like this: <image> In the second tree, the algorithm will find an answer with 3 nodes which is correct: <image>

Solution (in JAVA):

Solution:
 import java.io.*;
    import java.util.*;
  
 
  
        public class Codeforces {
    	
    		   public static long log2(long x)
    			{
    				long p=1;
    				long ans=0;
    				while(x>=p)
    				{
    					p*=2;
    					ans++;
    				}
    				return ans-1;
    			}
    		   
    		   
    		   public static void extendedgcd(int a, int b)
    		   {
    			   x=0;
    			   y=0;
    			   gc=0;
    			   xgcd(a,b);
    			   pw.println(a+"*"+x+" + "+b+"*"+y+" = "+gc);
    			   
    		   }
    		   
    		   
    		   public static long modex(long a, long b, long c)
    		   {
    			   if(b==0)
    				   return 1;
    			   else if(b==1)
    				   return a%c;
    			   else if(b%2==0)
    			   {
    				   	return modex((a*a)%c,b/2,c);
    			   }
    			   else
    			   {
    				   return (a*modex((a*a)%c,b/2,c))%c;
    				   
    			   }
    			   
    			   
    		   }
    		   
    		   
    		   public static void xgcd(int a, int b)
    		   {
    			   
    			   if(b==0)
    			   {
    				   x=1;
    				   y=0;
    				   gc=a;
    				   
    				   
    			   }
    			   else
    			   {
    				   xgcd(b,a%b);
    				   int temp = x;
    				   x=y;
    				   y = temp - ((a/b)*y);
    				   
    			   }
    		   }
    		   
    		   public static long gcd(long a, long b)
    		   {
    			   if(b==0)return a;
    			   else return gcd(b,a%b);
    			   
    		   }
    		   
    		   static int x,y,gc;
    		   
    		  
    		
    		   
    		   static HashSet<Character> set;
    		   
    		   
    		   
    		   public static long expmod(long a, long b, long mod)
    		   {
    			   if(b==0)return 1;
    			   if(b==1)return a;
    			   
    			   if(b%2==0)
    			   {
    				   return ((expmod(a,b/2,mod)%mod)*(expmod(a,b/2,mod)%mod))%mod;
    			   }
    			   else
    			   {
    				   return ((a%mod)*(expmod(a,b/2,mod)%mod)*(expmod(a,b/2,mod)%mod))%mod;
    			   }
    		   }
    		   
    		   static class Comp implements Comparator<Point>
    		   {

				@Override
				public int compare(Point arg0, Point arg1) {
					
					if(arg0.x>arg1.x)return 1;
					if(arg0.x<arg1.x)return -1;
					return 0;
				}
    			   
    		   }
    		   
    		   
    		   static class STComp implements Comparator<Integer>
    		   {

				@Override
				public int compare(Integer arg0, Integer arg1) {
					
					return arg0.compareTo(arg1); 
				}
    			   
    		   }
    		   
    		   static class Point
    		   {
    			   int x,y,ind;
    			   
    			    public Point(int a, int b)
    			    {
    			    	x=a;
    			    	y=b;
    			    	ind=0;
    			    }
    			   
    			    @Override
    			    public boolean equals(Object o) {
    			 
    			        // If the object is compared with itself then return true  
    			        if (o == this) {
    			            return true;
    			        }
    			 
    			        /* Check if o is an instance of Complex or not
    			          "null instanceof [type]" also returns false */
    			        if (!(o instanceof Point)) {
    			            return false;
    			        }
    			         
    			        // typecast o to Complex so that we can compare data members 
    			        Point c = (Point) o;
    			         
    			        // Compare the data members and return accordingly 
    			        return x==c.x&&y==c.y;
    			                
    			    }
    			    
    		   }
    		   
    		 
    		   
    		  
    		   
    		   public static boolean issub(String s1, String s2)
    		   {
    			   if(s1.length()>s2.length())
    			   return false;
    			   
    			   int l1 = s1.length();
    			   int l2 = s2.length();
    			   
    			   
    			   for(int i=0;i<=l2-l1;i++)
    			   {
    				   String sub = s2.substring(i, i+l1);
    				   if(s1.equals(sub))return true;
    			   }
    			   
    			   return false;
    		   }
    		   
    		   
    		   
    		   public static String enc(String s, int n)
    		   {
    			   String s1 = s.substring(0,n);
    			   String s2 = s.substring(n, s.length());
    			   
    			  String re="";
    			  for(int i=s1.length()-1;i>=0;i--)re+=s1.charAt(i);
    			  
    			  return re+s2;
    			   
    			   
    			   
    		   }
    		 
    		   
    		   
    		   static int vis[];
    		   
    		   public static void dfs(int x)
    		   {
    			   vis[x]=1;
    			   
    			   ArrayList<Integer> li = adj[x];
    			   
    			   for(int ch:li)
    			   {
    				   
    				   if(vis[ch]==0)dfs(ch);
    				   
    			   }
    			   
    		   }
    		   /*
    		   public static void dfsm(int x, HashSet<Integer> set)
    		   {
    			   vis2[x]=1;
    			   
    			   ArrayList<Integer> li = adj[x];
    			   
    			   for(int ch:li)
    			   {
    				   //if(!set.contains(ch))continue;
    				   if(vis2[ch]==0)dfsm(ch,set);
    				   
    			   }
    			   
    		   }
    		   */
    		   
    		  
    		
    		   public static void countPaths(int s, int d, ArrayList<Integer> pa)
    		   {
    			   
    			   vis2[s]=1;
    			   if(s==d)
    			   {
    				   pa.add(s);
    				 //  paths[ct] = new ArrayList<Integer>(pa);
    				   ct++;
    			   }
    			   else
    			   {
    				   ArrayList<Integer> li = adj[s];
    				   pa.add(s);
    				   
    				   for(int ad: li)
    				   {
    					   if(vis2[ad]==0)countPaths(ad,d,pa);
    				   }
    				   
    				   
    			   }
    			   
    			   if(pa.size()>1)pa.remove(pa.size()-1);
    			   vis2[s]=0;
    			   return ;
    		   }
    		  
    		   
    		   
    		   public static boolean dif(String s1, String s2)
    		   {
    			   int ct=0;
    			   if(s1.length()!=s2.length())return false;
    			   for(int i=0;i<s1.length();i++)
    			   {
    				   if(s1.charAt(i)!=s2.charAt(i))ct++;
    				   
    			   }
    			   
    			   if(ct==1)return true;
    			   else return false;
    			   
    			   
    		   }
    		   
    		   
    		   
    		   
    		   static void add(int arr[], int N, int lo,
                       int hi, int val)
    		   {
							    arr[lo] += val;
							    if (hi != N - 1)
							       arr[hi + 1] -= val;
    		   }
 
// Utility method to get actual array from 
// operation array
static void updateArray(int arr[], int N)
{
    // convert array into prefix sum array
    for (int i = 1; i < N; i++)
        arr[i] += arr[i - 1];
}
  
// method to print final updated array
static void printArr(int arr[], int N)
{
    updateArray(arr, N);
    for (int i = 0; i < N; i++)
        System.out.print(""+arr[i]+" ");
    System.out.print("\n");
}
  
    		   
  
    		  static int cyc;
    		   
    		   
    		  
    		  public static void dfsmod(int v, HashSet<Integer> set)
    		  {
    			  vis2[v]=1;
    			  
    			  ArrayList<Integer> li = adj[v];
    			  
    			  set.add(v);
    			  
    			  for(int ch: li)
    			  {
    				  if(set.contains(ch))
    				  {
    					  cyc=1;
    					  pw.println("** "+ch+" "+v);
    				  }
    				  if(vis2[ch]==0)dfsmod(ch,set);
    				  
    			  }
    			  
    			  set.remove(v);
    			  
    			  
    		  }
    		  
    		  
    		  	public static boolean isps(int x)
    		  	{
    		  		int sq = (int)Math.sqrt(x);
    		  		
    		  		return sq>0&&sq*sq==x;
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  		
    		  	}
    		  
    		  	 public static void combinations(String suffix,String prefix)
    		  	 {
    		         if(prefix.length()<0)return;
    		         pw.println(suffix);
    		        	 
    		        	 
    		         for(int i=0;i<prefix.length();i++)
    		          combinations(suffix+prefix.charAt(i),prefix.substring(i+1,prefix.length()));
    		         
    		     }
    		  	
    		  	
    		  	 
    		
    		  	 
    		  	 
    		  	 public static void topo(int x)
    		  	 {
    		  		 vis2[x]=1;
    		  		// pw.println("vis "+x);
    		  		 ArrayList<Integer> li = adj[x];
    		  		// pw.println(x+" has siz "+li.size());
    		  		// Integer i = x;
    		  		 for(int ch: li)
    		  		 {
    		  			
    		  			 if(vis2[ch]==0)
    		  				 {topo(ch);
    		  				//pw.println(x+" "+ch);
    		  				 }
    		  		 }
    		  		 
    		  		 st.push(x);
    		  		 //pw.println(i+" pushed");
    		  	 }
    		  	 
    		  	 
    	  		   

    		 	static  ArrayList<Integer>[] adj;
    		 	static int[] vis2;
    		 	static int ct;

    		     public static void ch(Stack<Integer> s)
    		     {
    		    	 s.push(4);
    		    	 return;
    		     }
    		     
    		     static Stack<Integer> st;
    		     
    		     
    		     static class PQnode implements Comparable<PQnode>
    		     {
    		    	 int value;
    		    	 int distance;
    		    	 
    		    	 public PQnode(int x, int y)
    		    	 {
    		    		 value=x;
    		    		 distance=y;
    		    	 }

					@Override
					public int compareTo(PQnode o) {
					return Integer.compare(this.distance, o.distance);
						
					
					
					}
					
					
					  @Override
		    		    public  boolean equals(Object o)
		    		    {
		    		    	if(o==this)return true;
		    		    	
		    		    	if(!(o instanceof PQnode))
		    		    	{
		    		    		return false;
		    		    	}
		    		    	
		    		    	PQnode node = (PQnode) o;
		    		    	
		    		    	return value==node.value&&distance==node.distance;
		    		    	
		    		    }
    		     }
    		  
    		  
    		     static class Compq implements Comparator<PQnode>
    		     {

					
					public int compare(PQnode arg0, PQnode arg1) {
						
						if(arg0.distance>arg1.distance)return 1;
						if(arg0.distance<arg1.distance)return -1;
						return 0;
					}
    		    	 
    		    	 
    		    	 
    		     }
    		     
    		     public static void printpa(int pa[],int x)
    		     {
    		    	 if(pa[x]==-1)
    		    		 
    		    		 pw.println(x);
    		    	 else
    		    	 {
    		    		 printpa(pa, pa[x]);
    		    		 pw.println(x);
    		    	 }
    		     }
    		     
    		     
    		     static class Node
    		     {
    		    	 int data;
    		    	 Node next;
    		    	 
    		    	 public Node(int x)
    		    	 {
    		    		 data =x;
    		    		 next=null;
    		    	 }
    		     }
    		     
    		     static Node he;
    		     static Node rev(Node n)
    		     {
    		    	 if(n.next==null)
    		    	 {
    		    		he=n;
    		    		return n;
    		    		 
    		    	 }
    		    	 else
    		    	 {
    		    		 Node rt = rev(n.next);
    		    		 rt.next=n;
    		    		 return n;
    		    	 }
    		    	 
    		     }
    		     
    		     
    		     
    		     
    		     public static int trap(final int[] A) {
    		    	    
    		         int n = A.length;
    		         int arr[] = new int[A.length];
    		         for(int i=0;i<A.length;i++)arr[i]=A[i];
    		         int nge[] = new int[A.length];
    		         
    		         Stack<Point> st = new Stack<Point>();
    		         //int ip=0;
    		         
    		        
    		         
    		         st.push(new Point(arr[0],0));
    		         
    		         for(int i=1;i<n;i++)
    		         {
    		             Point p = new Point(arr[i],i);
    		             
    		             while(!st.isEmpty()&&p.x>=st.peek().x)
    		             {
    		                 Point pop = st.pop();
    		                 nge[pop.y]=p.y;
    		             }
    		             st.push(p);
    		             
    		         }
    		         
    		         while(!st.isEmpty())
    		         {
    		             Point p = st.pop();
    		             nge[p.y]=-1;
    		         }
    		         
    		         int ans=0;
    		        for(int i=0;i<n;i++)System.out.print(nge[i]+" ");
    		        pw.println(); 
    		        for(int i=0;i<n;)
    		         {
    		             if(arr[i]!=0)
    		             {
    		                 int ng = nge[i];
    		                 if(ng==-1)
    		                 {
    		                   int j=i+1;
    		                   while(j<n&&arr[j]==0)j++;
    		                   
    		                   if(j!=n)
    		                   {int ad = (j-i-1)*arr[j];
    		                       ans+=ad;
    		                     System.out.println("1* "+i+" "+j+" "+ad);
    		                     i=j;
    		                     
    		                   }
    		                  
    		                   
    		                 }
    		                 else
    		                 {
    		                    int sub=0;
    		                    int j = i+1;
    		                    while(j<n&j<ng)
    		                    {
    		                        sub+=arr[j];
    		                        j++;
    		                    }
    		                    
    		                    int ad = (arr[i]*(ng-i-1))-sub;
    		                    System.out.println("2* "+i+" "+j+" "+ng+" "+ad);
    		                    ans += ad;
    		                    
    		                    i=ng;
    		                     
    		                 }
    		             }
    		             else
    		             {
    		            	 i++;
    		             }
    		         }
    		         
    		         
    		         return ans;
    		         
    		     }
    		     
    		     
    		     
    		     public static int round(int st, int end, int a, int b)
    		     {
    		    	 int mid = (st+end)/2;
    		    	 
    		    	 if(a<=mid&&b>=mid+1)return 0;
    		    	 else
    		    	 {
    		    		 if(a<=mid&&b<=mid)
    		    		 {
    		    			 return 1+round(st,mid,a,b);
    		    			 
    		    		 }
    		    		 else
    		    		 {
    		    			 return 1+round(mid+1,end,a,b);
    		    			 
    		    		 }
    		    		 
    		    	 }
    		    	 
    		    	 
    		    	 
    		     }
    		     
    		     
    		     
    		     public static void main(String[] args) 
    	   {
    		    	
    		    int n = sc.nextInt();
    		    
    		    if(n>=8)
    		    {
    		    	
    		    	pw.println("1 2");
    		    	pw.println("1 3");
    		    	pw.println("2 4");
    		    	pw.println("2 5");
    		    	pw.println("3 6");
    		    	pw.println("4 7");
    		    	
    		    	
    		    	for(int i=8;i<=n;i++)pw.println("4 "+i);
    		    	
    		    	
    		    	for(int i=2;i<=n;i++)
    		    		pw.println(1+" "+i);
    		    }
    		    else
    		    {
    		    	if(n==7)
    		    	{
    		    		
    		    		pw.println("1 2");
    		    		pw.println("1 3");
    		    		pw.println("1 4");
    		    		pw.println("2 5");
    		    		pw.println("2 6");
    		    		pw.println("2 7");
    		    		
    		    		
    		    		
    		    		
    		    		for(int i=2;i<=n;i++)
        		    		pw.println(1+" "+i);
    		    		
    		    		
    		    	}
    		    	else
    		    	if(n==6)
    		    	{
    		    		pw.println("1 2");
    		    		pw.println("1 3");
    		    		pw.println("1 4");
    		    		pw.println("2 5");
    		    		pw.println("2 6");
    		    		//pw.println("4 7");
    		    		
    		    		
    		    		
    		    		
    		    		for(int i=2;i<=n;i++)
        		    		pw.println(1+" "+i);
    		    		
    		    	}
    		    	else
    		    		
    		    	{
    		    	
    		    	
    		    	pw.println(-1);
    		    	
    		    	for(int i=2;i<=n;i++)
    		    		pw.println(1+" "+i);
    		    	}
    		    	
    		    	
    		    
    		    	
    		    }
    		    
    		    
    		    	 
    		    	 
    		    	/*int dist = (be-ae)/2;
    		    	
    		    	int ct=0;
    		    	while(dist!=0)
    		    	{
    		    		dist/=2;
    		    		ct++;
    		    	}
    		    	 
    		    	int rn = ct+1;
    		    	
    		    
    		    	
    		    	pw.println(l2);
    		    	
    		    	if(rn==l2)
    		    	{
    		    		pw.println("Final!");
    		    	}
    		    	else
    		    	{
    		    		
    		    		pw.println(rn);
    		    	}
    		    	*/
    		    	
    		    	
    		    	 /*int a[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    		    	 for(int i=0;i<a.length;i++)pw.print(a[i]+" ");
    		    	 pw.println();
    		    	 trap(a);*/
    		    	 
    		    	 /*
    		    	 int n = sc.nextInt();
    		    	 int a  = sc.nextInt();
    		    	 int b = sc.nextInt();
    		    	 long sum=0;
    		    	 
    		    	 int arr[] = new int[n];
    		    	 
    		    	 for(int i=0;i<n;i++)
    		    	 {	 arr[i]=sc.nextInt();
    		    	 	sum+=arr[i];
    		    	 }
    		    	 
    		    	 
    		    	 int as = (arr[0]*a)/b;
    		    	 
    		    	 int bl[] = new int[n-1];
    		    	 
    		    	 for(int i=1;i<n;i++)
    		    	 {
    		    		 bl[i-1]=arr[i];
    		    	 }
    		    	 
    		    	 Arrays.sort(bl);
    		    	 
    		    	 if(sum<=as)
    		    	 {
    		    		 pw.println(0);
    		    		 pw.close();
    		    		 return;
    		    	 }
    		    	 
    		    	 int ans=0;
    		    	 for(int i=n-2	;i>=0;i--)
    		    	 {
    		    		 sum = sum-bl[i];
    		    		 ans++;
    		    		 if(sum<=as)break;
    		    		 
    		    	 }
    		    		 pw.println(ans);
    		    	 
    		    	 */
    		    			 
    		    			 
    		    	 
    		    	 
    		    	 
    		    	 

    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    	 
    		    			 
    		    	 
    		    	 
    		    	 
    		    	
    		    	//pw.println(ans);
    		    	 
    		    	 /*int n  =sc.nextInt();
    		  		int k = sc.nextInt();
    		  		
    		  		int arr[] = new int[n];
    		  		
    		  		for(int i=0;i<n;i++)arr[i]=sc.nextInt();
    		  		
    		  		int pref[] =  new int[n];
    		  		
    		  		for(int i=0;i<n;i++)
    		  		{
    		  			if(i==0)
    		  			{
    		  				pref[i]=arr[i];
    		  			}
    		  			else
    		  			{
    		  				pref[i]=pref[i-1]+arr[i];
    		  			}
    		  		}
    		  				
    		  		double ans = Float.MIN_VALUE;
    		  		
    		  		
    		  		
    		  		for(int i=k;i<=n;i++)
    		  		{
    		  			
    		  			int p1 = 0;
    		  			int p2= i-1;
    		  			
    		  			while(p2<=n)
    		  			{
    		  				//pw.println("calc "+p1+" "+p2);
    		  				double rsum = (p1==0)?pref[p2]:pref[p2]-pref[p1-1];
    		  				double avg = rsum/i;
    		  				//pw.println(i);
    		  				ans = Math.max(ans, avg);
    		  				p1++;
    		  				p2++;
    		  				//pw.println("********");
    		  				if(p2==n)break;
    		  			}
    		  			
    		  		}
    		    	 
    		  		pw.println(ans);
    		    	 */
    		    	 
    		    	 /*
    		    	 */
    		    	
    		    	
    		    	
    		    	/* 
    		    	Node n1 = new Node(1);
    		    	Node n2 = new Node(2);
    		    	Node n3 = new Node(3);
    		    	n1.next=n2;
    		    	n2.next=n3;
    		    	n3.next=null;
    		    	
    		    	rev(n1);
    		    	
    		    	while(he!=null)
    		    	{
    		    		pw.println(he.data);
    		    		he=he.next;
    		    	}
    		    	 */
    		    	 /* 
    		    	int n = sc.nextInt();
    		  		 
    		  		int x = sc.nextInt();
    		  		int y = sc.nextInt();
    		  		
    		  		String st = sc.nextLine();
    		  		int ind[] = new int[n];
    		  		int indct=0;
    		  		for(int i=0;i<st.length();i++)
    		  		{
    		  			if(st.charAt(i)=='1')
    		  			{
    		  				ind[indct++]=i;
    		  			}
    		  			
    		  		}
    		  		
    		  		
    		  		int r=0;
    		  		if(indct==0||indct==1)
    		  		{
    		  			if(indct==0)
    		  			{
    		  				pw.println(y);
    		  				pw.close();
    		  				return;
    		  			}
    		  			else
    		  			{
    		  				r=1;
    		  			}
    		  		}
    		  		
    		  		
    		  		else
    		  		{
    		  		
    		  		for(int i=0;i<indct-1;i++)
    		  		{
    		  			if(ind[i+1]-ind[i]>1)r++;
    		  		}
    		  		
    		  		if(r==0)
    		  		{
    		  			if(r==0)
    		  			{
    		  				pw.println(0);
    		  				pw.close();
    		  				return;
    		  			}
    		  			
    		  		}
    		  		
    		  		r++;
    		  		
    		  		}
    		  		
    		  		
    		  		//pw.println("r "+r);
    		  		
    		  		
    		  		long ans = Long.MAX_VALUE;
    		  		
    		  		for(int rev=0;rev<=r;rev++)
    		  		{
    		  			long left = r-rev;
    		  			long p = (left+1)*y + x*rev;
    		  			//pw.println(" p "+p);
    		  			ans = Math.min(p, ans);
    		  		}
    		  		
    		  		
    		  		pw.println(ans);
    		  		 */
    		  			
    		  				
    		  		 
    		  		 /*PriorityQueue<PQnode> pq = new PriorityQueue<PQnode>();
    		  		
    		  		 pw.println(pq.size());
    		  		 
    		  		 pq.add(new PQnode(1,2));
    		  		 pq.add(new PQnode(3,4));
    		  		 
    		  		 pw.println(pq.size());
    		  		pq.remove(new PQnode(1,2));
    		  		 pw.println(pq.size());
    		  		 
    		  		 
    		  		 
    		  		 int parent[] = new int[4];
    		  		 Arrays.fill(parent, -1);
    		  		 ArrayList<Point> adj[] = new ArrayList[4];
    		  		 
    		  		 for(int i=0;i<4;i++)adj[i] = new ArrayList<Point>();
    		  		 
    		  		 adj[0].add(new Point(1,10));
    		  		 adj[0].add(new Point(2,20));
    		  		 
    		  		 adj[1].add(new Point(0,10));
    		  		adj[1].add(new Point(2,5));
    		  		adj[1].add(new Point(3,16));
    		  		
    		  		adj[2].add(new Point(0,20));
    		  		adj[2].add(new Point(1,5));
    		  		adj[2].add(new Point(3,20));
    		  		
    		  		adj[3].add(new Point(1,16));
    		  		adj[3].add(new Point(2,20));
    		  		 
    		  		 
    		  		 
    		  		 PriorityQueue<PQnode> pq = new PriorityQueue<PQnode>(new Compq());
    		  		 HashSet<Integer> pres = new HashSet<Integer>();
    		  		 
    		  		 int[] dist = new int[4];
    		  		 
    		  		 for(int i=0;i<4;i++)
    		  		 {
    		  			 if(i==0)
    		  			 {
    		  				pq.add(new PQnode(i,0)); 
    		  				dist[i]=0;
    		  			 }
    		  			 else
    		  			 {
    		  				 pq.add(new PQnode(i,Integer.MAX_VALUE));
    		  				 dist[i]=Integer.MAX_VALUE;
    		  			 }
    		  			 pres.add(i);
    		  			 
    		  		 }
    		  		 
    		  		 
    		  		 while(!pq.isEmpty())
    		  		 {
    		  			 PQnode pop = pq.poll();
    		  			 pres.remove(pop.value);
    		  			// pw.println(pop.value+" "+pop.distance);
    		  			 dist[pop.value]=pop.distance;
    		  			 for(Point p: adj[pop.value])
    		  			 {
    		  				 if(pres.contains(p.x))
    		  				 {
    		  					 if(p.y+dist[pop.value]<dist[p.x])
    		  					 {
    		  						 pw.println("ha");
    		  						
    		  						 pq.remove(new PQnode(p.x,dist[p.x]));
    		  						 dist[p.x]=p.y+dist[pop.value];
    		  						 pq.add(new PQnode(p.x,p.y+dist[pop.value]));
    		  						 parent[p.x]=pop.value;
    		  					 }
    		  				 }
    		  			 }
    		  			 
    		  		 }
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 for(int i=0;i<4;i++)pw.print(dist[i]+" ");
    		  		pw.println();
    		  		 printpa(parent, 3	);
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 Dijkstra over.
    		  		 */
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 
    		  		 /*
    		  		st = new Stack<Integer>();
    		  		 
    			 
    			  cyc=0;
       			adj = new ArrayList[4];
       			vis2 = new int[4];
       			
       			Arrays.fill(vis2, 0);
       			for(int i=0;i<4;i++)adj[i] = new ArrayList<Integer>();
       			   
       			
       			adj[0].add(1);
       			adj[0].add(2);
       			adj[0].add(3);
       			
       			adj[1].add(3);
       			
       			//adj[2].add(0);
       			adj[2].add(1);
    			   //adj[3].add(2);
    			   
       			st = new Stack<Integer>();
    			
       			topo(0);
    			   
    			 while(!st.isEmpty())pw.println(st.pop());
    			 */
    				 
    			/*
    			int n = sc.nextInt();
    			
    			int arr[] = new int[n];
    			
    			for(int i=0;i<n;i++)arr[i]=sc.nextInt();
    			
    			long ansg =0,ansv = Long.MAX_VALUE; 
    			
    			int arr2[] = new int[n];
    			for(int i=0;i<n;i++)arr2[i]=arr[i]-i;
    		
    			for(int i=0;i<n;i++)
    			{
    				int x = arr2[i];
    				
    				if(x<=0)
    				{
    					
    					if(i<ansv)
    					{
    						
    						ansg=i;
    						ansv=i;
    					}
    				}
    				else
    				{
    					float t = ((float)x)/n;
    					long tt = (long)Math.ceil(t);
    					
    					long ex = i;
    					long ti = tt*n+ex;
    					
    					
    					if(ti<ansv)
    					{
    						//pw.println("** "+i);
    						ansg=i;
    						ansv=ti;
    					}
    					
    				}
    				
    				
    				
    			}
    			
    			pw.println(ansg+1);
    			*/
    			   
    			   
    			   
    		
    			   
    			   
    	
    			   
    			   /*ct=0;
    			
    			paths= new ArrayList[10];
    			adj = new ArrayList[4];
    			vis2 = new int[4];
    			
    			for(int i=0;i<4;i++)adj[i] = new ArrayList<Integer>();
    			   
    			for(int i=0;i<10;i++)paths[i] = new ArrayList<Integer>();
    			
    			adj[0].add(1);
    			adj[0].add(2);
    			adj[0].add(3);
    			
    			adj[1].add(3);
    			
    			adj[2].add(0);
    			adj[2].add(1);
    			
    			countPaths(2,3, new ArrayList<Integer>());
    			pw.println(ct);
    			   
    			for(int i=0;i<ct;i++)pw.println(paths[i]);
    			  */ 
    			   
    			   
    			   
    			   /*
    			   int n = sc.nextInt();
    			int m = sc.nextInt();
    			
    			int arr[] = new int[n];
    			
    			for(int i=0;i<n;i++)arr[i]=sc.nextInt();
    			
    			int req = n/m;
    			
    			int[] rem = new int[m];
    			
    			
    			HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    			for(int i=0;i<n;i++)
    			{
    				rem[arr[i]%m]++;
    				
    			}
    			int li=-1;
    			long ans=0;
    			for(int i=0;i<m;i++)
    			{
    				if(rem[i]>=req)
    				{
    					rem[(i+1)%m]+=rem[i]-req;
    					ans+=(rem[i]-req);
    				}
    				else
    				{
    					li=i;
    					
    				}
    			}
    			
    			for(int i=0;i<li;i++)
    			{
    				if(rem[i]>=req)
    				{
    					rem[(i+1)%m]+=rem[i]-req;
    					ans+=(rem[i]-req);
    				}
    				else
    				{
    					li=i;
    					
    				}
    			}
    			pw.println(ans);
    			*/
    			
    			
    			
    			   //pw.println(pa);
    		/*	  NGE 
       		int[] sto = {100,80,60,70,60,75,85};
       		int n = sto.length;
       		
       		int[] spa = new int[n];
       		spa[0]=1;
       		
       		Stack<Integer> st = new Stack<Integer>();
       		st.push(0);
       		
       		for(int i=1;i<n;i++)
       		{
       			
       			while(!st.isEmpty()&&sto[st.peek()]<=sto[i])st.pop();
       			
       			spa[i]=(st.isEmpty())?i+1:i-st.peek();
       			st.push(i);
       			
       		}
    			  
       		
       		for(int i=0;i<n;i++)pw.print(sto[i]+" ");
    			   pw.println();
    			   for(int i=0;i<n;i++)pw.print(spa[i]+" ");
    			  
    			   
    			   int[] nge = new int[n];
    			   
    			   st.clear();
    			   Stack<Point> st2 = new Stack<Point>();
    			   st2.push(new Point(sto[0],0));
    			   
    			   for(int i=1;i<n;i++)
    			   {
    				   while(!st2.isEmpty()&&st2.peek().x<sto[i])
    				   {
    					   Point pop = st2.pop();
    					   nge[pop.y]=sto[i];
    				   }
    				   st2.push(new Point(sto[i],i));
    				   
    			   }
    			   
    			   while(!st2.isEmpty())
    			   {
    				   nge[st2.pop().y]=-1;
    			   }
    			  
    			   pw.println();
    			   for(int i=0;i<n;i++)pw.print(sto[i]+" ");
    			   pw.println();
    			   for(int i=0;i<n;i++)pw.print(nge[i]+" ");
    			 */ 
    			   
    			   /*  int r = 2000000000;
    			  pw.println(r);
    			int n = sc.nextInt();
    			int k = sc.nextInt();
    			int l = sc.nextInt();
    			int m = n*k;
    			int arr[] = new int[m];
    			
    			for(int i=0;i<m;i++)arr[i]=sc.nextInt();
    			
    			Arrays.sort(arr);
    			
    			int limit = l+arr[0];
    			int li=-1;
    			
    			for(int i=0;i<m;i++)
    			{
    				//pw.println(arr[i]);
    				if(arr[i]>limit)
    				{
    					//pw.println(arr[i]);
    					li=i; break;
    				}
    			}
    			//pw.println(limit+" "+li);
    			if(li==-1)li=n;
    			
    			int noofsmallest = li;
    			
    			if(noofsmallest<n)
    			{
    				pw.println(0);
    			}
    			else
    			{
    				li--;
    				long ans=0;
    				for(int i=0;i<n-1;i++)
    				{
    					ans+=(long)arr[li];
    					li--;
    				}
    				ans+=arr[0];
    				pw.println(ans);
    				
    			}
    			  */ 
    			   
    			   
    			   
    		
    			 
    			  
    			pw.close();  
    			   
    	   }
    		   
    		   
    		   
    		   static  class MyScanner 
    			{
    	
    			BufferedReader br;
    			StringTokenizer st;
    	
    			public MyScanner() 
    			{
    				br = new BufferedReader(new InputStreamReader(System.in));
    			}
    	
    			String next() 
    			{
    				
    				while (st == null || !st.hasMoreElements()) 
    				{
    					try 
    					{
    						st = new StringTokenizer(br.readLine());
    					} catch (IOException e) 
    					{
    						e.printStackTrace();
    					}
    				}
    				return st.nextToken();
    			}
    	
    			int nextInt() 
    			{
    				return Integer.parseInt(next());
    			}
    	
    			long nextLong() 
    			{
    				return Long.parseLong(next());
    			}
    	
    			double nextDouble() 
    			{
    				return Double.parseDouble(next());
    			}
    	
    			String nextLine()
    			{
    				String str = "";
    				try 
    				{
    					str = br.readLine();
    				} catch (IOException e) 
    				{
    					e.printStackTrace();
    				}
    				return str;
    			}
    	
    		}
    	
    		static MyScanner sc = new  MyScanner();
    		static PrintWriter pw = new PrintWriter(System.out, true);
    		
    		static class DisjointSet
    		{
    			int[] parent;
    			int[] rank;
    			int n;
    			
    			public DisjointSet(int x)
    			{
    				n=x;
    				parent = new int[x];
    				rank = new int[x];
    				
    				for(int i=0;i<n;i++)
    				{
    					parent[i]=i;
    				}
    				
    			}
    			
    			public int find(int x)
    			{
    				
    				if(parent[x]==x)
    					return x;
    				else 
    					return find(parent[x]);
    			}
    			
    			public void union(int i, int j)
    			{
    				int iroot = find(i);
    				int jroot = find(j);
    				
    				if(iroot==jroot)
    					return;
    				
    				if(rank[iroot]<rank[jroot])
    				{
    					parent[iroot]=jroot;
    					
    				}
    				else if(rank[jroot]<rank[iroot])
    				{
    					parent[jroot]=iroot;
    				}
    				else
    				{
    					parent[iroot]=jroot;
    					rank[jroot]++;
    					
    				}
    				
    				
    				
    				
    			}
    			
    			
    			
    			
    			
    		}
    	
    		
    	}