Problem: You have a blackboard and initially only an odd number x is written on it. Your goal is to write the number 1 on the blackboard.

You may write new numbers on the blackboard with the following two operations. 

  * You may take two numbers (not necessarily distinct) already on the blackboard and write their sum on the blackboard. The two numbers you have chosen remain on the blackboard. 
  * You may take two numbers (not necessarily distinct) already on the blackboard and write their [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) on the blackboard. The two numbers you have chosen remain on the blackboard. 

Perform a sequence of operations such that at the end the number 1 is on the blackboard.

Input

The single line of the input contains the odd integer x (3 ≤ x ≤ 999,999).

Output

Print on the first line the number q of operations you perform. Then q lines should follow, each describing one operation. 

  * The "sum" operation is described by the line "a + b", where a, b must be integers already present on the blackboard. 
  * The "xor" operation is described by the line "a ^ b", where a, b must be integers already present on the blackboard. 

The operation symbol (+ or ^) must be separated from a, b by a whitespace.

You can perform at most 100,000 operations (that is, q≤ 100,000) and all numbers written on the blackboard must be in the range [0, 5⋅10^{18}]. It can be proven that under such restrictions the required sequence of operations exists. You can output any suitable sequence of operations.

Examples

Input


3


Output


5
3 + 3
3 ^ 6
3 + 5
3 + 6
8 ^ 9


Input


123


Output


10
123 + 123
123 ^ 246
141 + 123
246 + 123
264 ^ 369
121 + 246
367 ^ 369
30 + 30
60 + 60
120 ^ 121

Solution (in JAVA):

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

public class _1427E {
    static int[] MODS = {1000000007, 998244353};
    static int MOD = MODS[0];
    static ArrayList<Operation> list = new ArrayList<>();

    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        long x = sc.nextLong();
        long last = x;
        int pow = (int) (Math.log(x) / Math.log(2));
        for (int i = 0; i < pow; i++) {
            list.add(new Operation(last, last, false));
            last *= 2;
        }
        list.add(new Operation(last, last, false));
        list.add(new Operation(x, last, true));
        long y = x ^ (list.get(list.size()-1).y);
        long[] vals = gcdWithBezout(x, y);
        long a = vals[1];
        long b = vals[2];
        addOperations(x, Math.abs(a));
        long first = x * Math.abs(a);
        addOperations(y, Math.abs(b));
        long second = y * Math.abs(b);
        if (first < second) {
            long temp = first;
            first = second;
            second = temp;
        }
        if (first % 2 == 0) {
            list.add(new Operation(first, x, false));
            list.add(new Operation(second, x, false));
            first += x;
            second += x;
        }
        list.add(new Operation(first, second, true));
        out.println(list.size());
        for (int i = 0; i < list.size(); i++) {
            out.println(list.get(i));
        }
        out.close();
    }

    public static void addOperations(long x, long a) {
        ArrayList<Long> powers = new ArrayList<>();
        long b = a;
        while (b > 0) {
            powers.add(b % 2);
            b /= 2;
        }
        long last = x;
        ArrayList<Long> multiply = new ArrayList<>();
        for (int i = 0; i < powers.size() - 1; i++) {
            list.add(new Operation(last, last, false));
            if (powers.get(i) == 1) {
                multiply.add(last);
            }
            last *= 2;
        }
        for (int i = 0; i < multiply.size(); i++) {
            list.add(new Operation(last, multiply.get(i), false));
            last = last + multiply.get(i);
        }
    }

    public static long[] gcdWithBezout(long p, long q) {
        if (q == 0) {
            return new long[]{p, 1, 0};
        }
        long[] vals = gcdWithBezout(q, p % q);
        long d = vals[0];
        long a = vals[2];
        long b = vals[1] - (p / q) * vals[2];
        return new long[] { d, a, b };
    }

    static class Operation {
        long x;
        long y;
        boolean xor;
        public Operation(long x, long y, boolean xor) {
            this.x = x;
            this.y = y;
            this.xor = xor;
        }
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(x);
            sb.append(" ");
            if (xor) {
                sb.append("^");
            }
            else {
                sb.append("+");
            }
            sb.append(" ");
            sb.append(y);
            return sb.toString();
        }
    }

    public static PrintWriter out;

    public 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;
        }
    }
}