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.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        if (!"true".equals(System.getProperty("ONLINE_JUDGE"))) {
            System.setIn(new FileInputStream(new File("input.txt")));
        }
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader inp = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(inp, out);
        out.close();
    }

    private static class Solver {
        private int depth(long x) {
            if (x == 1) {
                return 0;
            }
            return depth(x / 2) + 1;
        }
        private void solve(InputReader inp, PrintWriter out) {
            long[] length   = new long[63];
            long[] shift    = new long[63];
            for (int i = 0; i < 63; ++i) {
                shift[i] = 0;
                length[i] = i == 0 ? 1 : (length[i - 1] * 2);
            }

            int q = inp.nextInt();
            for (; q > 0; --q) {
                int type = inp.nextInt();
                if (type == 1) {
                    long x = inp.nextLong();
                    long k = inp.nextLong();
                    int t = depth(x);
                    shift[t] = ((shift[t] + k) % length[t] + length[t]) % length[t];
                } else if (type == 2) {
                    long x = inp.nextLong();
                    long k = inp.nextLong();
                    for (int t0 = depth(x), t = t0; t < 63; ++t) {
                        if (t > t0) {
                            k = (k * 2) % length[t];
                        }
                        shift[t] = ((shift[t] + k) % length[t] + length[t]) % length[t];
                    }
                } else {
                    long x = inp.nextLong();
                    int t = depth(x);
                    long d = x - length[t];
                    d = (d + shift[t]) % length[t];
                    for (; x > 0; x /= 2, d /= 2, t -= 1) {
                        long value = (d - shift[t] + length[t]) % length[t] + length[t];
                        out.print(value + " ");
                    }
                    out.println();
                }
            }
        }
    }

    private static class RandomStuff {
        static public int[] ArrayFilled(int size, int value) {
            int[] a = new int[size];
            for (int i = 0; i < size; ++i) {
                a[i] = value;
            }
            return a;
        }
        static public int[] UnitArrayZERO(int size) {
            int[] a = new int[size];
            for (int i = 0; i < size; ++i) {
                a[i] = i;
            }
            return a;
        }
        static public int[] UnitArrayONE(int size) {
            int[] a = new int[size];
            for (int i = 0; i < size; ++i) {
                a[i] = i + 1;
            }
            return a;
        }
    }

    private static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        private InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}