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.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author prakharjain
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        _960D solver = new _960D();
        solver.solve(1, in, out);
        out.close();
    }

    static class _960D {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int q = in.nextInt();

            long[] shift = new long[60];

            long[] rs = new long[60];
            long[] re = new long[60];

            rs[0] = 1;
            re[0] = 1;
            for (int i = 1; i < 60; i++) {
                rs[i] = rs[i - 1] * 2;
                re[i] = (rs[i] * 2) - 1;
            }

            while (q-- > 0) {
                int t = in.nextInt();

                long x = in.nextLong(), k = -1;
                if (t <= 2) {
                    k = in.nextLong();
                }

                if (t == 1) {

                    for (int i = 0; i < 60; i++) {
                        if (x >= rs[i] && x <= re[i]) {

                            shift[i] += k;
                            break;

                        }
                    }

                } else if (t == 2) {
                    boolean f = false;
                    int g = 0;
                    for (int i = 0; i < 60; i++) {
                        if (x >= rs[i] && x <= re[i]) {

                            shift[i] += k;
                            f = true;

                            g++;
                        } else if (f) {
                            shift[i] += (1l << g) * k;
                            g++;
                        }
                    }
                } else {

                    norm(shift, rs, re);

                    int ci = -1;
                    for (int i = 0; i < 60; i++) {
                        if (x >= rs[i] && x <= re[i]) {

                            ci = i;
                            break;

                        }
                    }

                    long cli = getIndFromNum(x, rs[ci], re[ci], shift[ci]) + rs[ci] - 1;

                    while (ci >= 0) {

                        out.print(getNumFromInd(cli - rs[ci] + 1, rs[ci], re[ci], shift[ci]));
                        out.print(" ");
                        ci--;
                        cli /= 2;
                    }

                    out.println();

                }
            }
        }

        long getNumFromInd(long ind, long rs, long re, long shift) {

            long acn = rs + ind - 1;

            acn -= shift;

            long r = re - rs + 1;

            if (acn < rs) {
                acn += r;
            }

            if (acn > re) {

                acn -= r;
            }

            return acn;
        }

        long getIndFromNum(long num, long rs, long re, long shift) {

            long aci = num - rs + 1;

            aci += shift;

            long r = re - rs + 1;

            if (aci > r) {

                aci -= r;
            }

            if (aci < 1) {

                aci += r;
            }

            return aci;
        }

        void norm(long[] shifts, long[] rs, long[] re) {
            for (int i = 0; i < 60; i++) {

                long r = re[i] - rs[i] + 1;

                shifts[i] %= r;
            }
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println() {
            writer.println();
        }

        public void close() {
            writer.close();
        }

        public void print(long i) {
            writer.print(i);
        }

    }
}