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.DataInputStream;
import java.io.InputStream;
import java.util.ArrayList;

/**
 *
 * @author dell
 */
public class Main {
    
    static ArrayList<Integer>[][] G = new ArrayList[7][7]; 
    static int total;
    static boolean[] visited = new boolean[101]; 
    static int[] ans= new int[101];
    
     public static void main(String[] args) throws Exception {
      
        Main obj = new Main();
        Parsedoubt in = obj. new Parsedoubt(System.in);
        StringBuffer sb = new StringBuffer();

        int numbers = in.nextInt();
        solve(sb, in , numbers);
       

    }
    
    public static void solve(StringBuffer sb, Parsedoubt in , int n) throws Exception{
        
        for(int j=0; j<7; j++){
         for(int i=0; i<7; i++){
          G[i][j] = new ArrayList<Integer>();
         }
        }
        
        int[] count = new int[7];
        
        for(int j=0; j<n; j++){
          int p = in.nextInt();
          int q = in.nextInt();
          G[p][q].add(j+1); 
          G[q][p].add(-j-1); 
          count[p]++;
          count[q]++;
        }
        
        int start = 0, odds = 0;
        for(int j=0; j<7; j++){
         if(count[j]%2 == 1){
            start = j;
            odds++;
         }   
        }
        
        if( odds == 2 || odds == 0){
           while(count[start] == 0) start++;
           dfs(start);
           if(total < n){
             System.out.println("No solution");
             return;
           }
           for (int i = 0; i < n; i++) {
	      System.out.print(Math.abs(ans[i]) + " ");
		 if (ans[i] > 0) System.out.println("-"); else System.out.println("+");
	   }
        }
        else{
         System.out.println("No solution"); 
         return;
        }
    }
    
    public static void dfs(int s){
    
       
        for(int j=0; j<7; j++){
          for( int p : G[s][j]){
             if(visited[Math.abs(p)]) continue;
             visited[Math.abs(p)] = true;
             dfs(j);
             ans[total++] = p;
          }
        }
    }
    
    class Parsedoubt {

    final private int BUFFER_SIZE = 1 << 17;
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;

    public Parsedoubt(InputStream in) {
        din = new DataInputStream(in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public String nextString() throws Exception {
        StringBuffer sb = new StringBuffer("");
        byte c = read();
        while (c <= ' ') {
            c = read();
        }
        do {
            sb.append((char) c);
            c = read();
        } while (c > ' ');
        return sb.toString();
    }

    public char nextChar() throws Exception {
        byte c = read();
        while (c <= ' ') {
            c = read();
        }
        return (char) c;
    }

    public int nextInt() throws Exception {
        int ret = 0;
        byte c = read();
        while (c <= ' ') {
            c = read();
        }
        boolean neg = c == '-';
        if (neg) {
            c = read();
        }
        do {
            ret = ret * 10 + c - '0';
            c = read();
        } while (c > ' ');
        if (neg) {
            return -ret;
        }
        return ret;
    }

    public long nextLong() throws Exception {
        long ret = 0;
        byte c = read();
        while (c <= ' ') {
            c = read();
        }
        boolean neg = c == '-';
        if (neg) {
            c = read();
        }
        do {
            ret = ret * 10 + c - '0';
            c = read();
        } while (c > ' ');
        if (neg) {
            return -ret;
        }
        return ret;
    }

    private void fillBuffer() throws Exception {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        if (bytesRead == -1) {
            buffer[0] = -1;
        }
    }

    private byte read() throws Exception {
        if (bufferPointer == bytesRead) {
            fillBuffer();
        }
        return buffer[bufferPointer++];
    }
}
}