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

Solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  long long x;
  cin >> x;
  vector<pair<pair<long long, long long>, int> > moves;
  while (x != 1) {
    if (x % 4 == 3) {
      long long shift = (x << 1);
      moves.push_back({{x, x}, 1});
      moves.push_back({{x, shift}, 0});
      x ^= shift;
    } else {
      int pos = 0;
      for (int i = 0; i < 30; i++)
        if ((x >> i) & 1) pos = i;
      long long shifted = x;
      for (int i = 0; i < pos; i++) {
        moves.push_back({{shifted, shifted}, 1});
        shifted <<= 1;
      }
      moves.push_back({{shifted, x}, 0});
      moves.push_back({{shifted, x}, 1});
      long long XOR = shifted ^ x;
      long long sum = shifted + x;
      moves.push_back({{XOR, sum}, 0});
      long long new_xor = XOR ^ sum;
      for (int i = pos + 1; i < 50; i++) {
        if (shifted == (1 << pos)) break;
        if ((shifted >> i) & 1) {
          moves.push_back({{shifted, new_xor}, 0});
          shifted ^= new_xor;
        }
        moves.push_back({{new_xor, new_xor}, 1});
        new_xor <<= 1;
      }
      moves.push_back({{x, shifted}, 0});
      x ^= shifted;
    }
  }
  cout << moves.size() << "\n";
  for (int i = 0; i < (int)moves.size(); i++) {
    cout << moves[i].first.first << " " << (moves[i].second ? "+ " : "^ ")
         << moves[i].first.second << "\n";
  }
  return 0;
}