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.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
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);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        ArrayList<Level> levels;
        long[] shifts;

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            levels = new ArrayList<>();
            shifts = new long[63];
            long g = 1;
            for (int i = 0; i <= 60; i++) {
                levels.add(new Level(g, g + g - 1));
                g *= 2;
            }
//        for(Level l : levels) {
//            out.println(l.start + " " + l.end);
//        }

            Arrays.fill(shifts, 0L);
            int q = in.nextInt();

            while (q-- > 0) {
                int T = in.nextInt();
                //out.println(Arrays.toString(shifts));
                if (T == 1) {
                    long X = in.nextLong();
                    long K = in.nextLong();

                    int L = getLevel(X);
                    long N = numElements(L);
                    shifts[L] = (shifts[L] + (K % N)) % N;
                    if (shifts[L] < 0) shifts[L] = shifts[L] + N;
                } else if (T == 2) {
                    long X = in.nextLong();
                    long K = in.nextLong();

                    int L = getLevel(X);
                    for (int i = L; i <= 60; i++) {
                        long N = numElements(i);
                        K = K % N;
                        shifts[i] = (shifts[i] + K) % N;
                        if (shifts[i] < 0) shifts[i] = shifts[i] + N;
                        K = K * 2;
                    }
                } else {
                    long X = in.nextLong();
                    int L = getLevel(X);
                    long pos = X - levels.get(L).start;
                    long ogPos = (pos + shifts[L]) % numElements(L);
                    out.print(X + " ");
                    for (int i = L - 1; i >= 0; i--) {
                        long upPos = ogPos / 2;
                        long cnt = numElements(i);
                        long ret = (upPos - shifts[i] + cnt) % cnt + levels.get(i).start;
                        out.print(ret + " ");
                        ogPos = upPos;
                    }
                    out.println();
                }
            }
        }

        private long numElements(int L) {
            Level l = levels.get(L);
            return l.end - l.start + 1;
        }

        private int getLevel(long V) {
            for (int i = 0; i < levels.size(); i++) {
                Level l = levels.get(i);
                if (l.start <= V && l.end >= V) {
                    return i;
                }
            }
            return -1;
        }

        private class Level {
            long start;
            long end;

            public Level(long start, long end) {
                this.start = start;
                this.end = end;
            }

        }

    }

    static class FastScanner {
        private BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;

        public FastScanner(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
        }

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

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

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

    }
}