#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
const double eps = 1e-8;
template <typename T>
inline void read(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
int q;
long long mrk[2][66], pw[66];
inline long long Pow(long long x, long long y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x)
    if (y & 1) ret = ret * x;
  return ret;
}
inline int Get_dep(long long x) {
  int cnt = 0;
  while (x) {
    x >>= 1;
    ++cnt;
  }
  return cnt;
}
inline long long Up(long long a, long long b) { return (a + b - 1) / b; }
inline long long trans(long long val, long long dep) {
  long long L = Pow(2, dep - 1), R = Pow(2, dep), Range = R - L;
  if (val < L) {
    val += Up((L - val), Range) * Range;
  } else if (val >= R) {
    val -= Up((val - R + 1), Range) * Range;
  }
  return val;
}
signed main() {
  read(q);
  pw[0] = 1;
  for (int i = 1; i <= 60; i++) pw[i] = pw[i - 1] << 1;
  for (int i = 1; i <= q; i++) {
    int type;
    long long x, k;
    read(type);
    if (type == 1) {
      read(x);
      read(k);
      int dep = Get_dep(x);
      mrk[0][dep] = (mrk[0][dep] + k) % pw[dep - 1];
    } else if (type == 2) {
      read(x);
      read(k);
      int dep = Get_dep(x);
      mrk[1][dep] = (mrk[1][dep] + k) % pw[dep - 1];
    } else if (type == 3) {
      read(x);
      int dep = Get_dep(x);
      x = trans(x + mrk[0][dep], dep);
      while (dep) {
        printf("%I64d ", trans(x - mrk[0][dep], dep));
        x = trans(x + mrk[1][dep], dep);
        x >>= 1;
        --dep;
      }
      puts("");
    }
  }
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

You have a full binary tree having infinite levels.

Each node has an initial value. If a node has value x, then its left child has value 2·x and its right child has value 2·x + 1. 

The value of the root is 1. 

You need to answer Q queries. 

There are 3 types of queries: 

  1. Cyclically shift the values of all nodes on the same level as node with value X by K units. (The values/nodes of any other level are not affected).
  2. Cyclically shift the nodes on the same level as node with value X by K units. (The subtrees of these nodes will move along with them).
  3. Print the value of every node encountered on the simple path from the node with value X to the root.



Positive K implies right cyclic shift and negative K implies left cyclic shift. 

It is guaranteed that atleast one type 3 query is present.

Input

The first line contains a single integer Q (1 ≤ Q ≤ 105).

Then Q queries follow, one per line: 

  * Queries of type 1 and 2 have the following format: T X K (1 ≤ T ≤ 2; 1 ≤ X ≤ 1018; 0 ≤ |K| ≤ 1018), where T is type of the query.
  * Queries of type 3 have the following format: 3 X (1 ≤ X ≤ 1018).

Output

For each query of type 3, print the values of all nodes encountered in descending order.

Examples

Input

5
3 12
1 2 1
3 12
2 4 -1
3 8


Output

12 6 3 1 
12 6 2 1 
8 4 2 1 


Input

5
3 14
1 5 -3
3 14
1 3 1
3 14


Output

14 7 3 1 
14 6 3 1 
14 6 2 1 

Note

Following are the images of the first 4 levels of the tree in the first test case:

Original: 

<image>

After query 1 2 1: 

<image>

After query 2 4 -1: 

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
const double eps = 1e-8;
template <typename T>
inline void read(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') {
    f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
int q;
long long mrk[2][66], pw[66];
inline long long Pow(long long x, long long y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x)
    if (y & 1) ret = ret * x;
  return ret;
}
inline int Get_dep(long long x) {
  int cnt = 0;
  while (x) {
    x >>= 1;
    ++cnt;
  }
  return cnt;
}
inline long long Up(long long a, long long b) { return (a + b - 1) / b; }
inline long long trans(long long val, long long dep) {
  long long L = Pow(2, dep - 1), R = Pow(2, dep), Range = R - L;
  if (val < L) {
    val += Up((L - val), Range) * Range;
  } else if (val >= R) {
    val -= Up((val - R + 1), Range) * Range;
  }
  return val;
}
signed main() {
  read(q);
  pw[0] = 1;
  for (int i = 1; i <= 60; i++) pw[i] = pw[i - 1] << 1;
  for (int i = 1; i <= q; i++) {
    int type;
    long long x, k;
    read(type);
    if (type == 1) {
      read(x);
      read(k);
      int dep = Get_dep(x);
      mrk[0][dep] = (mrk[0][dep] + k) % pw[dep - 1];
    } else if (type == 2) {
      read(x);
      read(k);
      int dep = Get_dep(x);
      mrk[1][dep] = (mrk[1][dep] + k) % pw[dep - 1];
    } else if (type == 3) {
      read(x);
      int dep = Get_dep(x);
      x = trans(x + mrk[0][dep], dep);
      while (dep) {
        printf("%I64d ", trans(x - mrk[0][dep], dep));
        x = trans(x + mrk[1][dep], dep);
        x >>= 1;
        --dep;
      }
      puts("");
    }
  }
  return 0;
}

```