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.InputStreamReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.io.BufferedWriter;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskB {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = 7, m = in.nextInt();
        int i,j,k;
        Pair<Integer,Integer> d[] = new Pair[m];


        boolean u[] = new boolean[n];
        for(k=0;k<m;++k){
            d[k] = new Pair<Integer, Integer>(in.nextInt(), in.nextInt());
            u[d[k].first] = u[d[k].second] = true;
        }
        
        int g[][] = new  int[n][n];
        int deg[] = new int[n]; 
        for(k=0;k<m;++k){
            g[d[k].first][d[k].second]++;
            g[d[k].second][d[k].first]++;
            deg[d[k].first]++;
            deg[d[k].second]++;
        }
        
        int v1=-1, v2=-1;
        for(i=0;i<n;++i) if(deg[i]%2==1){
            if(v1==-1){ v1 = i; } else
            if(v2==-1){ v2 = i; } else{
                out.writeln("No solution");
                return;
            }
        }
        
        if(v1<0 && v2<0){
            for(i=0;i<n;++i)
            for(j=0;j<n;++j) if(g[i][j]>0){
                v1 = i;
                v2 = j;
               // g[i][j]--;
               // g[j][i]--;
                i = j = n;
            }
        }else
        if(v1<0 || v2<0){
            out.writeln("No solution");
            return;
        }
        
        ArrayList<Integer> way = new ArrayList<Integer>();
        dfs(v1, g, way);
        
        
        
        for(int v : way) u[v] = false;
        for(boolean b : u) if(b){
            out.writeln("No solution");
            return;
        }
        
        for(k=0;k<way.size()-1;++k){
            i = way.get(k);
            j = way.get(k+1);
            for(int l = 0;l<m;++l){
                if(d[l].first == i && d[l].second == j){
                    out.writeln(l+1," +");
                    d[l] = new Pair<Integer, Integer>(-1,-1);
                    break;
                }
                if(d[l].first == j && d[l].second == i){
                    out.writeln(l+1," -");
                    d[l] = new Pair<Integer, Integer>(-1,-1);
                    break;
                }
            }
        }
    }
    
    void dfs(int v, int g[][], ArrayList<Integer> ans){
        for(int i=0;i<g[v].length;++i) if(g[v][i]>0){
            g[v][i]--;
            g[i][v]--;
            dfs(i, g, ans);
        }
        ans.add(v);
    }
}

class InputReader{
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream){
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }
    
    public String next(){
        while (tokenizer == null || !tokenizer.hasMoreTokens()){
            try{
                tokenizer = new StringTokenizer(reader.readLine());
            }catch (IOException e){
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    
    public int nextInt(){
        return Integer.parseInt(next());
    }

    }

class OutputWriter{
    private PrintWriter out;

    public OutputWriter(Writer out){
        this.out = new PrintWriter(out);
    }

    public OutputWriter(OutputStream out){
        this.out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(out)));
    }

    public void write(Object ... o){
        for(Object x : o) out.print(x);
    }

    public void writeln(Object ... o){
        write(o);
        out.println();
    }

    public void close(){
        out.close();
    }
}

class Pair<X, Y> implements Comparable<Pair>{
    public X first;
    public Y second;
    
    public Pair(X x, Y y){
        first = x;
        second = y;
    }
    
    public int compareTo(Pair o) {
        int cmp = ((Comparable)first).compareTo(o.first);
        if(cmp!=0) return cmp;
        return ((Comparable)second).compareTo(o.second);
    }
    
    }