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 math

x = int(input())
ops = []

def ext_euc(a, b) :
    s = 0
    old_s = 1
    t = 1
    old_t = 0
    while a != 0 :
        q = b//a
        r = b%a
        m, n = old_s-s*q, old_t-t*q
        b,a,old_s,old_t,s,t = a,r,s,t,m,n
    return b,old_s,old_t

def get_mul(a, b) :
    base = a
    cur = 0
    while b > 0 :
        if b%2 == 1 :
            if cur > 0 :
                ops.append(str(cur) + ' + ' + str(base))
            cur += base
        ops.append(str(base) + ' + ' + str(base))
        base = 2*base
        b = b//2
    return cur

# find two coprime
e = math.floor(math.log2(x))
for i in range(e) :
    ops.append(str(x * (1 << i))+' + '+str(x * (1 << i)))
ops.append(str(x) + ' ^ ' + str((1 << e)*x))
y = ((1 << e)*x)^x
pair = ext_euc(x, -y)
p = pair[2]
q = pair[1]
while p < 0 or q < 0 :
    p += y
    q += x
if q % 2 == 1 : 
    p += y
    q += x
# print(p)
# print(q)
pro1=get_mul(x,p)
pro2=get_mul(y,q)
ops.append(str(pro1) + ' ^ ' + str(pro2))

print(len(ops))
for i in ops :
    print(i)
# print(p, q)
# print(y)
# print(x*p-y*q)