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.HashMap;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

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

    static class DFullBinaryTreeQueries {
        public void solve(int testNumber, inputClass sc, PrintWriter out) {
            int q = sc.nextInt();
            HashMap<Integer, Long> valueShift = new HashMap<>();
            HashMap<Integer, Long> nodeShift = new HashMap<>();
            long pow[] = new long[64];
            pow[0] = 1;
            for (int i = 0; i < 64; i++) {
                valueShift.put(i, 0L);
                nodeShift.put(i, 0L);
                if (i > 0) pow[i] = pow[i - 1] * 2;
            }
            int t;
            long x, k;
            int level;

            for (int i = 0; i < q; i++) {
                t = sc.nextInt();
                if (t == 1) {
                    x = sc.nextLong();
                    k = sc.nextLong();
                    level = (int) (Math.log(x) / Math.log(2));
                    valueShift.put(level, (valueShift.get(level) + k) % pow[level]);
                } else if (t == 2) {
                    x = sc.nextLong();
                    k = sc.nextLong();
                    level = (int) (Math.log(x) / Math.log(2));
                    nodeShift.put(level, (nodeShift.get(level) + k) % pow[level]);
                } else {
                    x = sc.nextLong();
                    StringBuilder ans = new StringBuilder().append(x).append(" ");
                    level = (int) (Math.log(x) / Math.log(2));
                    x += valueShift.get(level);
                    if (x >= pow[level + 1]) {
                        x -= pow[level];
                    }
                    if (x < pow[level]) {
                        x += pow[level];
                    }
                    while (level > 0) {
                        x = x + nodeShift.get(level);
                        if (x >= pow[level + 1]) {
                            x -= pow[level];
                        }
                        if (x < pow[level]) {
                            x += pow[level];
                        }
                        x /= 2;
                        level = (int) (Math.log(x) / Math.log(2));
                        ans.append((x - valueShift.get(level) - (x - valueShift.get(level) >= pow[level + 1] ? pow[level] : 0)
                                + (x - valueShift.get(level) < pow[level] ? pow[level] : 0)

                        )).append(" ");
                    }
                    out.println(ans);
                }
            }
        }

    }

    static class inputClass {
        BufferedReader br;
        StringTokenizer st;

        public inputClass(InputStream in) {

            br = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}