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 PYTHON3):

Solution:
import sys
input = sys.stdin.readline
from math import gcd

x=int(input())
import random
#x=(random.randint(1,999999//2))*2+1
XLIST=[x]
XSET=set()

def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): # axy=a*1+b*0,bxy=a*0+b*1なので,a,bに対応する係数の初期値は(1,0),(0,1)
    # print(a,b,axy,bxy)
    q,r=divmod(a,b)

    if r==0:
        return bxy,b # a*bxy[0]+b*bxy[1]=b
   
    rxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # rに対応する係数を求める.
    return Ext_Euc(b,r,bxy,rxy)

ANS=[]
USED=set()
flag=0
while True:
    if flag:
        break
    x=random.choice(XLIST)
    if x in USED:
        continue
    USED.add(x)
    y=x
    
    for i in range(20):
        
        if gcd(x,y^x)==1:
            k,l=Ext_Euc(x,y^x)[0]

            tt,tu=abs(k)*x,(y^x)*abs(l)
            if tt^tu==1:
                flag=1
                break
            else:
                ANS.append(str(x)+" ^ "+str(y))
                XLIST.append(x^y)
                
        else:
            ANS.append(str(y)+" + "+str(y))
            if y<=999999:
                XLIST.append(x)
            y=2*y

z=y^x
ANS.append(str(y)+" ^ "+str(x))
#print(x,z)

A=Ext_Euc(x,z)
#print(A)

k,l=abs(A[0][0]),abs(A[0][1])

XLIST=[x]
ANS.append(str(x)+" + "+str(x))
x=x+x
while x<25*10**17:
    XLIST.append(x)
    ANS.append(str(x)+" + "+str(x))
    x=2*x

ZLIST=[z]
ANS.append(str(z)+" + "+str(z))
z=z+z
while z<25*10**17:
    ZLIST.append(z)
    ANS.append(str(z)+" + "+str(z))
    z=2*z

XLIST2=[0]*60
for i in range(60):
    if k & (1<<i) != 0:
        XLIST2[i]=1

flag=0
for i in range(60):
    if XLIST2[i]==1:
        if flag==0:
            NOW=XLIST[i]
            flag=1
        else:
            ANS.append(str(NOW)+" + "+str(XLIST[i]))
            NOW+=XLIST[i]

NOW0=NOW
ZLIST2=[0]*60
for i in range(60):
    if l & (1<<i) != 0:
        ZLIST2[i]=1

flag=0
for i in range(60):
    if ZLIST2[i]==1:
        if flag==0:
            NOW=ZLIST[i]
            flag=1
        else:
            ANS.append(str(NOW)+" + "+str(ZLIST[i]))
            NOW+=ZLIST[i]

NOW1=NOW
ANS.append(str(NOW0)+" ^ "+str(NOW1))
#print(NOW1,NOW0)

print(len(ANS))
for ans in ANS:
    print(ans)