#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
inline unsigned int myrand(int n) {
  unsigned int u = rand() % n;
  int c = rand() % 10;
  u ^= u << c;
  u ^= (u << 7) & 263692864;
  u ^= (u << 15) & 402273075;
  u %= n;
  return u;
}
long long lf[1111], st[1111], ed[1111];
long long len[1111];
int get(long long first) {
  for (int i = 0; i < 62; i++) {
    if (st[i] <= first and first <= ed[i]) return i;
  }
}
int main() {
  for (int i = 0; i < 62; i++) {
    lf[i] = (1ll << i);
    st[i] = lf[i];
    if (i)
      ed[i - 1] = st[i] - 1;
    else
      ed[i] = 1;
  }
  ed[61] = (1ll << 62) - 1;
  for (int i = 0; i < 62; i++) len[i] = ed[i] - st[i] + 1;
  int q;
  cin >> q;
  long long t, first, k;
  int level;
  while (q--) {
    gn(t, first);
    if (t == 3) {
      level = get(first);
      long long pos = (first - lf[level] + len[level]) % len[level] + 1;
      while (level >= 0) {
        long long ans = lf[level] + pos - 1;
        if (ans > ed[level]) ans -= len[level];
        printf("%I64d ", ans);
        level--;
        pos++;
        pos /= 2;
      }
      puts("");
    } else {
      gn(k);
      level = get(first);
      k = -k;
      if (t == 1) {
        lf[level] += k;
        lf[level] %= len[level];
        (lf[level] += len[level]) %= len[level];
        lf[level] += st[level];
      } else {
        for (int i = level; i < 62; i++) {
          k %= len[i];
          lf[i] += k;
          lf[i] %= len[i];
          (lf[i] += len[i]) %= len[i];
          lf[i] += st[i];
          k <<= 1;
        }
      }
    }
  }
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
inline unsigned int myrand(int n) {
  unsigned int u = rand() % n;
  int c = rand() % 10;
  u ^= u << c;
  u ^= (u << 7) & 263692864;
  u ^= (u << 15) & 402273075;
  u %= n;
  return u;
}
long long lf[1111], st[1111], ed[1111];
long long len[1111];
int get(long long first) {
  for (int i = 0; i < 62; i++) {
    if (st[i] <= first and first <= ed[i]) return i;
  }
}
int main() {
  for (int i = 0; i < 62; i++) {
    lf[i] = (1ll << i);
    st[i] = lf[i];
    if (i)
      ed[i - 1] = st[i] - 1;
    else
      ed[i] = 1;
  }
  ed[61] = (1ll << 62) - 1;
  for (int i = 0; i < 62; i++) len[i] = ed[i] - st[i] + 1;
  int q;
  cin >> q;
  long long t, first, k;
  int level;
  while (q--) {
    gn(t, first);
    if (t == 3) {
      level = get(first);
      long long pos = (first - lf[level] + len[level]) % len[level] + 1;
      while (level >= 0) {
        long long ans = lf[level] + pos - 1;
        if (ans > ed[level]) ans -= len[level];
        printf("%I64d ", ans);
        level--;
        pos++;
        pos /= 2;
      }
      puts("");
    } else {
      gn(k);
      level = get(first);
      k = -k;
      if (t == 1) {
        lf[level] += k;
        lf[level] %= len[level];
        (lf[level] += len[level]) %= len[level];
        lf[level] += st[level];
      } else {
        for (int i = level; i < 62; i++) {
          k %= len[i];
          lf[i] += k;
          lf[i] %= len[i];
          (lf[i] += len[i]) %= len[i];
          lf[i] += st[i];
          k <<= 1;
        }
      }
    }
  }
  return 0;
}

```