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 Main
{

    static int mod = (int) (1e9+7);
    static InputReader in;
    static PrintWriter out;
    
    public static void main(String[] args)
    {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);            
        
        int q = in.nextInt();
        long[] shift = new long[63];

        while(q-- > 0){
            int t = in.nextInt();
            long x = in.nextLong();
            if(t == 1){
                long k = in.nextLong();
                int h = 63 - Long.numberOfLeadingZeros(x);
                shift[h] = (shift[h] + k) % (1l << h);
            }
            else if(t == 2){
                long k = in.nextLong();
                int h = 63 - Long.numberOfLeadingZeros(x);
                while(h < 63){
                    shift[h] = (shift[h] + k) % (1l << h);
                    h++;
                    k *= 2;
                }
            }
            else{
                out.print(x + " ");
                int h = 63 - Long.numberOfLeadingZeros(x);
                x += shift[h];
                if(x < ((1l << h))) x += (1l << h);
                if(x >= (1l << (h + 1))) x -= (1l << h);
                
                while(x > 1){
                    x /= 2;
                    h = 63 - Long.numberOfLeadingZeros(x);
                    long y = x - shift[h];
                    if(y < ((1l << h))) y += (1l << h);
                    if(y >= (1l << (h + 1))) y -= (1l << h);
                    out.print(y + " ");
                }
                out.println();
            }
        }
        
        out.close();
        
    }

    static void debug(Object... o)
    {
            System.out.println(Arrays.deepToString(o));
    }

    static class Pair implements Comparable<Pair>
    {

        int x,y,i;
        
        Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        
        Pair (int x, int y, int i)
        {
		this.x = x;
                this.y = y;
                this.i = i;
	}
        
	public int compareTo(Pair o)
        {
            return Integer.compare(this.x,o.x);
		//return 0;
	}

        public boolean equals(Object o)
        {
            if (o instanceof Pair)
            {
                Pair p = (Pair)o;
                return p.x == x && p.y==y;
            }
            return false;
        }

        @Override
        public String toString()
        {
            return x + " "+ y + " " + i;
        }
        
        public int hashCode()
        {
            return new Long(x).hashCode() * 31 + new Long(y).hashCode();
        }
    
    } 

    static long gcd(long x, long y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }

    static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }

    static long pow(long n, long p, long m) {
        long result = 1;
        if (p == 0) {
            return 1;
        }

        while (p != 0) {
            if (p % 2 == 1) {
                result *= n;
            }
            if (result >= m) {
                result %= m;
            }
            p >>= 1;
            n *= n;
            if (n >= m) {
                n %= m;
            }
        }
        return result;
    }

    static long pow(long n, long p) {
        long result = 1;
        if (p == 0) {
            return 1;
        }

        while (p != 0) {
            if (p % 2 == 1) {
                result *= n;
            }
            p >>= 1;
            n *= n;
        }
        return result;
    }

    static class InputReader
    {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

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

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

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

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

        public int[] nextIntArray(int n)
        {
                int a[] = new int[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextInt();
                }
                return a;
        }

        public long[] nextLongArray(int n)
        {
                long a[] = new long[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextLong();
                }
                return a;
        }

        public String readString()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
        }

        public String nextLine()
        {
                int c = snext();
                while (isSpaceChar(c))
                        c = snext();
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
        }

        public boolean isSpaceChar(int c)
        {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c)
        {
                return c == '\n' || c == '\r' || c == -1;
        }

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

    }
}