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.io.*; import java.util.*;
public class E {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        long X=Integer.parseInt(br.readLine());
        StringBuilder sb=new StringBuilder();
        long p=1; long k=X;
        int q=0;
        while(p<X){
            sb.append(k+" + "+k+"\n");
            q++;
            p*=2; k*=2;
            
        }
        
        long kk=k;
        k/=2;
        sb.append(X+" ^ "+k+"\n"); k^=X; q++;
        
        while(p<k){
            sb.append(kk+" + "+kk+"\n");
            q++;
            p*=2; kk*=2;
        }
        
        //System.out.println(k);
        int pp=1; long l=k;
        while(pp<X){
            sb.append(l+" + "+l+"\n");q++;
            pp*=2; l*=2;
        }
        long ans=inv(k%X,X);//k*ans=1 mod x
        
        String s=Long.toBinaryString(ans);
        long cur=(long) k*(1<<(s.length()-1));
        
        for (int i = 1; i <s.length(); i++) {
            if(s.charAt(i)=='1'){
                
                sb.append(cur+" + "+(k<<(s.length()-1-i))+"\n"); q++;
                cur+=(long) k<<(s.length()-1-i);
            }
        }
        
        long ans2=(long) (k*ans-1)/X;
        
        String s2=Long.toBinaryString(ans2);
        long cur2=(long) X<<(s2.length()-1);
        //System.out.println(cur2);
        for (int i = 1; i <s2.length(); i++) {
            if(s2.charAt(i)=='1'){
                sb.append(cur2+" + "+(X<<(s2.length()-1-i))+"\n");q++;
                
                cur2+=(long) X<<(s2.length()-1-i);
                
            } 
        }
        //System.out.println(k*ans-1);
        //System.out.println(cur2+" "+cur);
        if(cur2%2==0){
            sb.append(cur2+" ^ "+cur+"\n");q++;
        }else{
            
            sb.append(cur2+" + "+X+"\n");
            sb.append(cur+" + "+X+"\n");
            sb.append((cur2+X)+" ^ "+(cur+X)+"\n");
            q+=3;
        }
        System.out.println(q);
        System.out.println(sb.toString());
    }
    //Special Cases: n=1, etc
    //Bounds: Overflow, ?
    public static long inv(long a, long b){//Computes modular inverse of a mod b
        //Assume b>a and gcd(a,b)=1, 
        if(a==1)return 1;
        long q=b/a;
        long r=b-q*a;
        long y=-inv(r,a);
        return ((b*y+1)/a)+b;
        
    }
}