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


import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class algo74
{
    public static void main(String args[]) throws IOException
    {
        in=new BufferedReader(new InputStreamReader(System.in));
        out=new PrintWriter(System.out);
        int q=scanInt();
        int n=61;
        long pow[]=new long[n];
        long start[]=new long[n];
        long above[]=new long[n+1];
        int abc[]=new int[n+1];
        long mul=1;
        for(int i=0;i<n;i++)
        {
            pow[i]=mul;
            start[i]=mul;
            above[i+1]=mul;
            mul=mul*2;
        }
        int cas,lev;
        long x,x1,k,k1,rem;
        while(q-->0)
        {
            cas=scanInt();
            switch(cas)
            {
                case 1:
                x=scanLong();
                k=scanLong();
                lev=-1;
                if(x==1)
                continue;
                while(x>0)
                {
                    x=x/2;
                    lev++;
                }
                k1=k%pow[lev];
                if(k1<0)
                k1=k1+pow[lev];
                rem=k1%2;
                k1=k1/2;
                if(rem%2==1)
                {
                    if(abc[lev]==1)
                    {
                        abc[lev]=0;
                        k1++;
                    }
                    else
                    abc[lev]=1;
                }
                above[lev]=above[lev]+k1;
                if(above[lev]>=start[lev])
                above[lev]=above[lev]-start[lev]+start[lev-1];
                k1=k%pow[lev];
                if(k1<0)
                k1=k1+pow[lev];
                k1=pow[lev]-k1;
                above[lev+1]=above[lev+1]+k1;
                if(above[lev+1]>=start[lev+1])
                above[lev+1]=above[lev+1]-start[lev+1]+start[lev];
                break;
                
                case 2:
                x=scanLong();
                k=scanLong();
                lev=-1;
                if(x==1)
                continue;
                while(x>0)
                {
                    x=x/2;
                    lev++;
                }
                k1=k%pow[lev];
                if(k1<0)
                k1=k1+pow[lev];
                rem=k1%2;
                k1=k1/2;
                if(rem%2==1)
                {
                    if(abc[lev]==1)
                    {
                        abc[lev]=0;
                        k1++;
                    }
                    else
                    abc[lev]=1;
                }
                above[lev]=above[lev]+k1;
                if(above[lev]>=start[lev])
                above[lev]=above[lev]-start[lev]+start[lev-1];
                break;
                
                case 3:
                x=scanLong();
                x1=x;
                lev=-1;
                while(x1>0)
                {
                    x1=x1/2;
                    lev++;
                }
                while(lev>0)
                {
                    out.print(x);
                    out.print(' ');
                    x=x-start[lev]+abc[lev];
                    x=x/2;
                    x=above[lev]+x;
                    if(x>=start[lev])
                    x=x-start[lev]+start[lev-1];
                    lev--;
                }
                out.println('1');
                break;
            }
        }
        in.close();
        out.close();
    }
    static int scanInt() throws IOException {
        return parseInt(scanString());
    }

    static long scanLong() throws IOException {
        return parseLong(scanString());
    }
    
    static String scanString() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }
    
    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;
}