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>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v);
template <typename A, typename B>
ostream &operator<<(ostream &cout, pair<A, B> const &p) {
  return cout << "(" << p.first << ", " << p.second << ")";
}
template <typename A>
ostream &operator<<(ostream &cout, vector<A> const &v) {
  cout << "[";
  for (int i = 0; i < v.size(); i++) {
    if (i) cout << ", ";
    cout << v[i];
  }
  return cout << "]";
}
template <typename A, typename B>
istream &operator>>(istream &cin, pair<A, B> &p) {
  cin >> p.first;
  return cin >> p.second;
}
mt19937 rng(steady_clock::now().time_since_epoch().count());
void usaco(string filename) {
  freopen((filename + ".in").c_str(), "r", stdin);
  freopen((filename + ".out").c_str(), "w", stdout);
}
const long double pi = 3.14159265358979323846;
const long long mod = 1000000007;
long long n, m, k, q, Q, T, l, r, x, y, z;
long long a[1000005];
long long b[1000005];
long long c[1000005];
string second, t;
long long ans = 0;
long long vsh[80], nsh[80];
long long res[80];
long long rsh[80];
long long bv[80], szv[80];
int main() {
  {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  };
  cin >> Q;
  memset(vsh, 0, sizeof(vsh));
  memset(nsh, 0, sizeof(nsh));
  for (long long q = 0; q < (Q); q++) {
    int t;
    cin >> t;
    if (t != 3) {
      cin >> l >> k;
      long long base = 0, sz = 1, ind = 0;
      while (base + sz < l) {
        ++ind;
        base += sz;
        sz *= 2;
      }
      if (t == 1) {
        vsh[ind] = (vsh[ind] + k) % sz;
        if (vsh[ind] < 0) vsh[ind] += sz;
      } else {
        nsh[ind] = (nsh[ind] + k) % sz;
        if (nsh[ind] < 0) nsh[ind] += sz;
      }
    } else {
      cin >> l;
      long long base = 0, sz = 1, ind = 0, cshift = 0;
      long long pt = 0;
      while (base + sz < l) {
        cshift *= 2;
        cshift = (cshift + nsh[ind]) % sz;
        rsh[ind] = cshift;
        bv[ind] = base;
        szv[ind] = sz;
        base += sz;
        sz *= 2;
        ++ind;
      }
      cshift *= 2;
      cshift = (cshift + nsh[ind]) % sz;
      rsh[ind] = cshift;
      long long loc = (l - base - 1 + cshift + vsh[ind]) % sz;
      if (loc < 0) res[ind] += sz;
      res[ind] = l;
      long long cop = ind;
      while (ind) {
        --ind;
        loc /= 2;
        long long v = (loc - rsh[ind] - vsh[ind]) % szv[ind];
        if (v < 0) v += szv[ind];
        v += bv[ind] + 1;
        res[ind] = v;
      }
      for (long long i = (cop); i >= 0; i--) cout << res[i] << " ";
      cout << '\n';
    }
  }
}