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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author pttrung
 */
public class B {

    public static int[] dp;

    public static void main(String[] args) throws FileNotFoundException {

        Scanner in = new Scanner();
        PrintWriter out = new PrintWriter(System.out);
        // PrintWriter out = new PrintWriter(new FileOutputStream(new File("output.txt")));
        int n = in.nextInt();

        int[][] map = new int[7][7];
        Point[] data = new Point[n];
        int[] count = new int[7];
        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            data[i] = new Point(x, y);
            map[x][y]++;
            map[y][x]++;
            count[x]++;
            count[y]++;
        }
        ArrayList<Integer> result = new ArrayList();
        boolean found = false;
        for (int i = 0; i < 7; i++) {
            if (count[i] % 2 != 0) {
                found = true;
                dfs(i, map, result);
                break;
            }
        }
        if (!found) {
            for (int i = 0; i < 7; i++) {
                if (count[i] != 0) {
                    dfs(i, map, result);
                    break;
                }
            }
        }
        int[] check = new int[n];
        int[] re = new int[n];
        int total = 0;
        int index = 0;
        for (int i = result.size() - 1; i > 0; i--) {
            int a = result.get(i);
            int b = result.get(i - 1);
            for (int j = 0; j < n; j++) {
                if (check[j] == 0) {
                    if (data[j].x == a && data[j].y == b) {
                        re[index++] = j;
                        total++;
                        check[j] = 1;
                        break;
                    } else if (data[j].x == b && data[j].y == a) {
                        re[index++] = j;
                        total++;
                        check[j] = 2;
                        break;
                    }
                }
            }
        }
        if(total != n){
            out.println("No solution");
        }else{
            for(int i = 0; i < n; i++){
                out.print((re[i] + 1) + " ");
                if(check[re[i]] == 1){
                    out.println('+');
                }else{
                    out.println('-');
                }
            }
        }
        out.close();
    }

    public static void dfs(int node, int[][] map, ArrayList<Integer> result) {
        for (int i = 0; i < 7; i++) {
            if (map[node][i] > 0) {
                map[node][i]--;
                map[i][node]--;
                dfs(i, map, result);
            }
        }
        result.add(node);
    }

    static class FT {

        int[] data;

        FT(int n) {
            data = new int[n];
        }

        void update(int index, int val) {
            // System.out.println("UPDATE INDEX " + index);
            while (index < data.length) {
                data[index] += val;
                index += index & (-index);

                //    System.out.println("NEXT " +index);
            }
        }

        int get(int index) {
            //  System.out.println("GET INDEX " + index);
            int result = 0;
            while (index > 0) {
                result += data[index];
                index -= index & (-index);
                // System.out.println("BACK " + index);
            }
            return result;
        }
    }

    public static double dist(Point a, Point b) {
        double val = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
        return Math.sqrt(val);
    }

    public static class Point {

        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    public static long pow(long a, int b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long val = pow(a, b / 2);
        if (b % 2 == 0) {
            return val * val;
        } else {
            return val * val * a;
        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            // System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            // br = new BufferedReader(new FileReader(new File("input.txt")));
        }

        public String next() {

            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}