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:

/**
 * Date: 7 Apr, 2018
 * Link: 960 D
 *
 * @author Prasad-Chaudhari
 * @email prasadc8897@gmail.com
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class newProgram5 {

    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        FastIO2 in = new FastIO2();
        long changev[] = new long[65];
        long noOfNode[] = new long[63];
        for (int i = 0; i < 63; i++) {
            noOfNode[i] = (long) Math.pow(2, i);
        }
        int q = in.ni();
        StringBuilder sb = new StringBuilder();
        long lee = 0;
        while (q-- > 0) {
            int t = in.ni();
            long x = in.nl();
            if (t == 1 || t == 2) {
                long k = in.nl();
                int level_x = findLevel(x);
                k = (k + noOfNode[level_x]) % noOfNode[level_x];
                if (t == 1) {
                    changev[level_x] += (k % noOfNode[level_x] + noOfNode[level_x]) % noOfNode[level_x];
                    changev[level_x] %= noOfNode[level_x];
                } else {
                    for (int i = level_x; i <= 62; i++) {
                        changev[i] += ((noOfNode[i - level_x]) * ((k % noOfNode[i] + noOfNode[i]) % noOfNode[i])) % noOfNode[i];
                        changev[i] %= noOfNode[i];
                    }
                }
            } else {
                long nodePos = findNodePos(x, changev, noOfNode);
//                System.out.println(nodePos+" "+changev[findLevel(x)]);
                while (nodePos > 0) {
                    long ans = findValueAt(nodePos, changev, noOfNode);
                    sb.append(ans).append(" ");
                    lee+=lenngth(ans);
                    lee++;
                    nodePos /= 2;
                }
                sb.append("\n");
                lee++;
                if(lee>100000){
                    System.out.print(sb.toString());
                    sb = new StringBuilder();
                    lee=0;
                }
            }
        }
        System.out.println(sb.toString());
    }

    private static int findLevel(long x) {
        return (int) (Math.log(x) / Math.log(2));
    }

    private static long findNodePos(long x, long[] changev, long[] noofNode) {
        int level_x = findLevel(x);
        return (x + changev[level_x] + noofNode[level_x]) % noofNode[level_x] + noofNode[level_x];
    }

    private static long findValueAt(long nodePos, long[] changev, long[] noOfNode) {
        int level_x = findLevel(nodePos);
        return (nodePos - changev[level_x]) % noOfNode[level_x] + noOfNode[level_x];
    }
    
    private static int lenngth (long x){
        return (x+"").length();
    }

    static class FastIO2 {

        private final BufferedReader br;
        private String s[];
        private int index;

        public FastIO2() throws IOException {
            br = new BufferedReader(new InputStreamReader(System.in));
            s = br.readLine().split(" ");
            index = 0;
        }

        public int ni() throws IOException {
            return Integer.parseInt(nextToken());
        }

        public double nd() throws IOException {
            return Double.parseDouble(nextToken());
        }

        public long nl() throws IOException {
            return Long.parseLong(nextToken());
        }

        public String next() throws IOException {
            return nextToken();
        }

        public String nli() throws IOException {
            try {
                return br.readLine();
            } catch (IOException ex) {

            }
            return null;
        }

        public int[] gia(int n) throws IOException {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }

        public int[] gia(int n, int start, int end) throws IOException {
            validate(n, start, end);
            int a[] = new int[n];
            for (int i = start; i < end; i++) {
                a[i] = ni();
            }
            return a;
        }

        public double[] gda(int n) throws IOException {
            double a[] = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }

        public double[] gda(int n, int start, int end) throws IOException {
            validate(n, start, end);
            double a[] = new double[n];
            for (int i = start; i < end; i++) {
                a[i] = nd();
            }
            return a;
        }

        public long[] gla(int n) throws IOException {
            long a[] = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }

        public long[] gla(int n, int start, int end) throws IOException {
            validate(n, start, end);
            long a[] = new long[n];
            for (int i = start; i < end; i++) {
                a[i] = ni();
            }
            return a;
        }

        private String nextToken() throws IndexOutOfBoundsException, IOException {
            if (index == s.length) {
                s = br.readLine().split(" ");
                index = 0;
            }
            return s[index++];
        }

        private void validate(int n, int start, int end) {
            if (start < 0 || end >= n) {
                throw new IllegalArgumentException();
            }
        }
    }
}