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.BufferedReader;
// import java.io.FileInputStream;
// import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

import static java.lang.Math.*;
import static java.util.Arrays.copyOf;
import static java.util.Arrays.fill;
import static java.util.Arrays.sort;
import static java.util.Collections.reverseOrder;
import static java.util.Collections.sort;

public class Main {
    FastScanner in;
    PrintWriter out;

    private void solve() throws IOException {
        solveD();
    }

    private void solveD() throws IOException {
        long[] len = new long[62];
        long[] sum = new long[62];
        long[] cnt = new long[62];
        long[] move = new long[62];
        long ss = 0, xx = 1;
        for (int i = 0; i < len.length; i++) {
            len[i] = xx;
            ss += xx;
            sum[i] = ss;
            //out.println(i + ": " + len[i] + " " + sum[i]);
            xx *= 2;
        }
        //out.flush();


        int q = in.nextInt(), t;
        long x, k = -1;
        int id;
        while (q-- > 0) {
            t = in.nextInt();
            x = in.nextLong();
            if (t < 3)
                k = in.nextLong();

            id = 0;
            while (sum[id] < x)
                id++;

            if (t == 1) {
                cnt[id] = (cnt[id] - k % len[id] + len[id]) % len[id];
            } else if (t == 2) {
                move[id] = (move[id] + k % len[id] + len[id]) % len[id];
            } else {
                x = len[id] + (x - cnt[id]) % len[id];
                while (id >= 0) {
                    out.print(len[id] + (x - len[id] + cnt[id]) % len[id] + " ");
                    x = len[id] + (x - len[id] + move[id]) % len[id];
                    x /= 2;
                    id--;
                }
                out.println();
            }
        }
    }

    private void solveE() throws IOException {

    }

    private void solveF() throws IOException {

    }

    class FastScanner {
        StringTokenizer st;
        BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        boolean hasNext() throws IOException {
            return br.ready() || (st != null && st.hasMoreTokens());
        }

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

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

        double nextDouble() throws IOException {
            return Double.parseDouble(next().replace(',', '.'));
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        boolean hasNextLine() throws IOException {
            return br.ready();
        }

    }

    private void run() throws IOException {
        in = new FastScanner(System.in); // new FastScanner(new FileInputStream(".in"));
        out = new PrintWriter(System.out); // new PrintWriter(new FileOutputStream(".out"));

        solve();

        out.flush();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}