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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        R474D solver = new R474D();
        solver.solve(1, in, out);
        out.close();
    }

    static class R474D {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int q = in.ni();
            long[] ks = new long[60];
            long[] pows = new long[60];
            for (int i = 0; i < 60; i++) {
                pows[i] = 1L << i;
            }
            for (int i = 0; i < q; i++) {
                int op = in.ni();
                if (op == 1) {
                    long x = in.nl(), k = in.nl();
                    int level = Long.numberOfTrailingZeros(Long.highestOneBit(x));
                    ks[level] = (ks[level] + k) % pows[level];
                } else if (op == 2) {
                    long x = in.nl(), k = in.nl();
                    int level = Long.numberOfTrailingZeros(Long.highestOneBit(x));
                    for (int j = level; j < 60; j++) {
                        k %= pows[j];
                        ks[j] = (ks[j] + k) % pows[j];
                        k *= 2L;
                    }
                } else {
                    long x = in.nl();
                    if (x == 1) {
                        out.println(1);
                        continue;
                    }
                    int level = Long.numberOfTrailingZeros(Long.highestOneBit(x));
                    long posInt = (x - (1L << level) + ks[level]) % pows[level];
                    if (posInt < 0)
                        posInt = (posInt + pows[level]) % pows[level];
                    long pos = (1L << level) + posInt;
                    out.print(x + " ");
                    for (int j = level - 1; j > 0; j--) {
                        pos >>= 1;
                        long numInt = (pos - (1L << j) - ks[j]) % pows[j];
                        if (numInt < 0)
                            numInt = (numInt + pows[j]) % pows[j];
                        long y = (1L << j) + numInt;
                        out.print(y + " ");
                    }
                    out.println('1');
                }
            }
        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String ns() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(ns());
        }

        public long nl() {
            return Long.parseLong(ns());
        }

    }
}