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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using PII = pair<int, int>;
using TI3 = tuple<int, int, int>;
using LL = long long;
using ULL = unsigned long long;
using MAT = array<array<LL, 2>, 2>;
template <class T>
void _read(T &x) {
  cin >> x;
}
void _read(int &x) { scanf("%d", &x); }
void _read(LL &x) { scanf("%lld", &x); }
void _read(ULL &x) { scanf("%llu", &x); }
void _read(double &x) { scanf("%lf", &x); }
void _read(char &x) { scanf(" %c", &x); }
void _read(char *x) { scanf("%s", x); }
void read() {}
template <class T, class... U>
void read(T &head, U &...tail) {
  _read(head);
  read(tail...);
}
template <class T>
void _print(const T &x) {
  cout << x;
}
void _print(const int &x) { printf("%d", x); }
void _print(const LL &x) { printf("%lld", x); }
void _print(const double &x) { printf("%.16lf", x); }
void _print(const char &x) { putchar(x); }
void _print(const char *x) { printf("%s", x); }
template <class T>
void _print(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _print(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void print() {}
template <class T, class... U>
void print(const T &head, const U &...tail) {
  _print(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  print(tail...);
}
template <class T>
void print1(T &x, int cond = 0) {
  _print(x);
  printf("%c", " \n"[cond]);
}
const int MOD = 1000000007;
LL shift[100];
int main() {
  int Q;
  read(Q);
  for (int q = 0; q < (int)(Q); q++) {
    int T;
    LL X, K;
    read(T);
    if (T == 1) {
      read(X, K);
      LL lvl = LL(log2l(X));
      LL n = 1LL << lvl;
      shift[lvl] = (shift[lvl] + n + K) % n;
    } else if (T == 2) {
      read(X, K);
      LL lvl = LL(log2l(X));
      LL n = 1LL << lvl;
      for (int i = lvl; i < (int)(61); i++) {
        shift[i] = (shift[i] + n + K) % n;
        n <<= 1;
        K <<= 1;
      }
    } else {
      read(X);
      LL lvl = LL(log2l(X));
      LL n = 1LL << lvl;
      for (int i = lvl;
           (-1 > 0 and i < (int)(-1)) or (-1 < 0 and i > (int)(-1)); i += -1) {
        print1(X, i == 0);
        if (i == 0) {
          break;
        }
        X = n + (X + shift[i]) % n / 2;
        n >>= 1;
        X = n + (X + n - shift[i - 1]) % n;
      }
    }
  }
  return 0;
}