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

public class D474 {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int q = sc.nextInt();
        Query [] queries = new Query[q];
        for (int i = 0; i < q; i++) {
            int t = sc.nextInt();
            Query qq = new Query(t);
            qq.x = sc.nextLong();
            if (t == 1 || t == 2) {
                qq.k = sc.nextLong();
            }
            queries[i] = qq;
        }
        Map<Long, Long> name = new HashMap<>();
        Map<Long, Long> parent = new HashMap<>();
        for (int i = 0; i < q; i++) {
            if (queries[i].type == 1) {
                long x = queries[i].x; long k = queries[i].k;
                long bit = Long.highestOneBit(x);
                long put = (name.getOrDefault(bit, 0L) + k) % bit;
                if (put < 0) put += bit;
                name.put(bit, put);
            } else if (queries[i].type == 2) {
                long x = queries[i].x; long k = queries[i].k;
                long bit = Long.highestOneBit(x);
                long put = (parent.getOrDefault(bit, 0L) + k) % bit;
                if (put < 0) put += bit;
                parent.put(bit, put);
            } else {
                long cur = queries[i].x;
                while (cur != 1) {
                    out.print(cur + " ");
                    long bit = Long.highestOneBit(cur);
                    long actualName = cur + name.getOrDefault(bit,0L);
                    if (actualName >= 2 * bit) actualName -= bit;
                    long goTo = actualName + parent.getOrDefault(bit, 0L);
                    if (goTo >= 2 * bit) goTo -= bit;
                    long par = goTo / 2;
                    cur = par - name.getOrDefault(bit / 2, 0L);
                    if (cur < bit / 2) cur += bit / 2;
                }
                out.print(1);
                out.println();
            }
        }
        out.close();
    }

    static class Query {
        int type; long x; long k;
        Query(int type) {
            this.type = type;
        }
    }


    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

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

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }


    }

}