Problem: You have a set of dominoes. Each domino is a rectangular tile with a line dividing its face into two square ends. Can you put all dominoes in a line one by one from left to right so that any two dominoes touched with the sides that had the same number of points? You can rotate the dominoes, changing the left and the right side (domino "1-4" turns into "4-1").

Input

The first line contains number n (1 ≤ n ≤ 100). Next n lines contains the dominoes. Each of these lines contains two numbers — the number of points (spots) on the left and the right half, correspondingly. The numbers of points (spots) are non-negative integers from 0 to 6.

Output

Print "No solution", if it is impossible to arrange the dominoes in the required manner. If the solution exists, then describe any way to arrange the dominoes. You put the dominoes from left to right. In each of n lines print the index of the domino to put in the corresponding position and then, after a space, character "+" (if you don't need to turn the domino) or "–" (if you need to turn it).

Examples

Input

5
1 2
2 4
2 4
6 4
2 1


Output

2 -
1 -
5 -
3 +
4 -

Solution (in JAVA):

Solution:
import java.io.*;
import java.text.DecimalFormat;
import java.util.*;

public class Main {
	static int mod = (int)1e9+7;
	static int inf = (int)1e9+7;
	static int N = 1005;
	int n, tot, m;
	int[][] G = new int[N][N];
	int[] Ru = new int[N], ans1 = new int[N], ans2 = new int[N], x = new int[N], y = new int[N];
	void dfs(int u) {
		for (int i = 0; i < m; i ++) {
			if (G[u][i]>0) {
				G[u][i]--;
				G[i][u]--;
				
				dfs(i);
			
				tot++;
				ans1[tot]=u;
				ans2[tot]=i;
			}
		}
	}
    void work() throws Exception {
    	n = cin.nextInt();
    	for (int i = 1; i <= n; i ++) {
    		x[i] = cin.nextInt();
    		y[i] = cin.nextInt();
    		G[x[i]][y[i]]++;
    		G[y[i]][x[i]]++;
    		Ru[x[i]]++;
    		Ru[y[i]]++;
    	}
    	m = 7;
    	ArrayList<Integer> vec = new ArrayList();
    	vec.clear();
    	for (int i = 0; i < m; i ++) {
    		if (Ru[i]%2 == 1) vec.add(i);
    	}
    	if (vec.size()==2) dfs(vec.get(0));
    	else if (vec.size()==0) dfs(x[1]);
    	else {
    		out.println("No solution");
    		return;
    	}
    	
    	if (tot!=n) {
    		out.println("No solution");
    		return;
    	}
    	
    	for (int i = n; i >= 1; i --) {
    		for (int j = 1; j <= n; j ++) {
    			if (ans1[i]==x[j] && ans2[i]==y[j]) {
    				out.println(j + " +");
    				x[j]=-1; y[j]=-1;
    				break;
    			} else if (ans1[i]==y[j] && ans2[i]==x[j])
    			{
    				out.println(j + " -");
    				x[j]=-1;y[j]=-1;
    				break;
    			}
    		}
    	}
    }  
    static PrintWriter out = new PrintWriter(System.out);
    Scanner cin = new Scanner(System.in);
  
//  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));;
//  StringTokenizer str = null;
//    private String next() throws Exception{
//    	while (str == null || !str.hasMoreElements())
//    	    str = new StringTokenizer(in.readLine());
//    	return str.nextToken();
//    } 
//    private int nextInt() throws Exception{
//    	return Integer.parseInt(next());
//    }
//    private long nextLong() throws Exception{
//    	return Long.parseLong(next());
//    }
    static int dx[] = {0,1,0,-1};
    static int dy[] = {1,0,-1,0};
    class pair implements Comparable<pair>{
    	int first, second;
    	pair(int x, int y) {
    		first = x;
    		second = y;
    	}
		public int compareTo(pair o) {
			// TODO auto-generated method stub
			if(first != o.first) return ((Integer)first).compareTo(o.first);
			else return ((Integer)second).compareTo(o.second); 
		}
    }
    int upper_bound(int[] A, int l, int r, int val) {// upper_bound(A+l,A+r,val)-A;
    	int pos = r;
    	r--;
    	while (l <= r) {
	    	int mid = (l + r) >> 1;
	    	if (A[mid] <= val) {
	    		l = mid + 1;
	    	} else {
	    		pos = mid;
	    		r = mid - 1;
	    	}
    	}
    	return pos;
    }
    int lower_bound(int[] A, int l, int r, int val) {// upper_bound(A+l,A+r,val)-A;
		int pos = r;
		r--;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (A[mid] < val) {
				l = mid + 1;
			} else {
				pos = mid;
				r = mid - 1;
			}
		}
		return pos;
	}
    
    DecimalFormat df=new DecimalFormat("0.000000");
    public static void main(String[] args) throws Exception{
        Main wo = new Main();
        wo.work();
        out.close();
    }
}