#include <bits/stdc++.h>
using namespace std;
int const MAX = 61;
vector<pair<long long, long long> > a;
long long mod[MAX];
int q;
void init() {
  for (int i = 0; i <= MAX - 1; i++) {
    long long l = (1LL << i);
    long long r = (1LL << (i + 1)) - 1;
    a.push_back(make_pair(l, r));
    mod[i] = r - l + 1;
  }
}
int getlevel(long long x) {
  for (int i = 0; i <= MAX - 1; i++) {
    if (a[i].first <= x && x <= a[i].second) return i;
  }
  assert(false);
  return 41;
}
int const Q = 1e5 + 41;
int t[Q];
long long k[Q];
long long x[Q];
long long sv[Q];
long long sp[Q];
long long add(long long a, long long b, long long mod) {
  a %= mod;
  b %= mod;
  a += b;
  while (a < 0) a += mod;
  while (a >= mod) a -= mod;
  return a;
}
long long getparx(long long x, int l) {
  long long y = x - a[l].first;
  y = add(y, sv[l], mod[l]);
  y = add(y, sp[l], mod[l]);
  y += a[l].first;
  y /= 2;
  y -= a[l - 1].first;
  y = add(y, -sv[l - 1], mod[l - 1]);
  y += a[l - 1].first;
  return y;
}
void solve() {
  for (int i = 1; i <= q; i++) {
    if (t[i] == 1) {
      int l = getlevel(x[i]);
      sv[l] = add(sv[l], k[i], mod[l]);
    } else if (t[i] == 2) {
      int l = getlevel(x[i]);
      sp[l] = add(sp[l], k[i], mod[l]);
    } else {
      vector<long long> ans;
      long long x = ::x[i];
      int l = getlevel(x);
      while (1) {
        ans.push_back(x);
        if (x == 1) break;
        x = getparx(x, l);
        l--;
      }
      for (int i = 0; i <= (int)ans.size() - 1; i++) {
        printf("%lld ", ans[i]);
      }
      printf("\n");
    }
  }
}
int main() {
  init();
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d", &t[i]);
    if (t[i] < 3) {
      scanf("%lld %lld", &x[i], &k[i]);
    } else {
      scanf("%lld", &x[i]);
    }
  }
  solve();
  return 0;
}

### Prompt

Please provide a Cpp coded solution 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;
int const MAX = 61;
vector<pair<long long, long long> > a;
long long mod[MAX];
int q;
void init() {
  for (int i = 0; i <= MAX - 1; i++) {
    long long l = (1LL << i);
    long long r = (1LL << (i + 1)) - 1;
    a.push_back(make_pair(l, r));
    mod[i] = r - l + 1;
  }
}
int getlevel(long long x) {
  for (int i = 0; i <= MAX - 1; i++) {
    if (a[i].first <= x && x <= a[i].second) return i;
  }
  assert(false);
  return 41;
}
int const Q = 1e5 + 41;
int t[Q];
long long k[Q];
long long x[Q];
long long sv[Q];
long long sp[Q];
long long add(long long a, long long b, long long mod) {
  a %= mod;
  b %= mod;
  a += b;
  while (a < 0) a += mod;
  while (a >= mod) a -= mod;
  return a;
}
long long getparx(long long x, int l) {
  long long y = x - a[l].first;
  y = add(y, sv[l], mod[l]);
  y = add(y, sp[l], mod[l]);
  y += a[l].first;
  y /= 2;
  y -= a[l - 1].first;
  y = add(y, -sv[l - 1], mod[l - 1]);
  y += a[l - 1].first;
  return y;
}
void solve() {
  for (int i = 1; i <= q; i++) {
    if (t[i] == 1) {
      int l = getlevel(x[i]);
      sv[l] = add(sv[l], k[i], mod[l]);
    } else if (t[i] == 2) {
      int l = getlevel(x[i]);
      sp[l] = add(sp[l], k[i], mod[l]);
    } else {
      vector<long long> ans;
      long long x = ::x[i];
      int l = getlevel(x);
      while (1) {
        ans.push_back(x);
        if (x == 1) break;
        x = getparx(x, l);
        l--;
      }
      for (int i = 0; i <= (int)ans.size() - 1; i++) {
        printf("%lld ", ans[i]);
      }
      printf("\n");
    }
  }
}
int main() {
  init();
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d", &t[i]);
    if (t[i] < 3) {
      scanf("%lld %lld", &x[i], &k[i]);
    } else {
      scanf("%lld", &x[i]);
    }
  }
  solve();
  return 0;
}

```