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.*;
import java.util.*;
public class CF960D
{
	static long[] nPL = new long[100];
	static long[] lastNode = new long[100];
	static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
   public static void main(String[] args) throws Exception
   {
      TomScanner sc = new TomScanner(System.in);
      long[] q1 = new long[100];
		long[] q2 = new long[100];
		lastNode[0]=1;
		nPL[0] = 1;
		for(int k=1; k<100; k++)
		{
			nPL[k]=nPL[k-1]*2;
			lastNode[k]=lastNode[k-1]*2+1;
		}
		long n = sc.nextLong();
		for(int k=0; k<n; k++)
		{
			int qt = sc.nextInt();
			if(qt==1 || qt == 2)	//rotate values
			{
				long node = sc.nextLong();
				long shiftNum = sc.nextLong();
				int ix = getLevel(node);
				long[] arr;
				if(qt==1)
					arr=q1;
				else arr = q2;
				arr[ix] = (arr[ix]+shiftNum)%nPL[ix];
			}
			else	//query type 3
			{
				long node = sc.nextLong();
				int ix = getLevel(node);
				for(int z=1; z<=ix; z++)
				{
					q1[z] = (q1[z]+q2[z]) % nPL[ix];
					q2[z+1] = (q2[z]*2+q2[z+1]) % nPL[ix+1];
					q2[z]=0;
				}
				long loc = (node - nPL[ix] + q1[ix]) % nPL[ix];
				if(loc<0)	loc+=nPL[ix];
				if(node>1) log.write(""+node);
				for(int z=ix-1; z>0; z--)
				{
					loc = loc/2;
					node = (loc-q1[z])%nPL[z];
					if(node<0) node+=nPL[z];
					log.write(" "+(node+nPL[z]));
				}
				log.write(" "+1+"\n");
			}
		}
		log.flush();
   }
	public static int getLevel(long node)
	{
		int level=0;
		while(lastNode[level]<node)
			level++;
		return level;
	}
}

class TomScanner
{
   BufferedReader	br;
   StringTokenizer st;
      
   public TomScanner(String fileNameIn)
   {
      try{
         FileReader fr = new FileReader(fileNameIn);
         br	= new	BufferedReader(fr);
      }
      catch(Exception e){System.out.println("Read Error");}
   }
   public TomScanner(InputStream is)
   {
      br = new BufferedReader(new InputStreamReader(is));
   }
   public static StringTokenizer	getst(BufferedReader	br) throws Exception{
      return new StringTokenizer(br.readLine(),	" ");
   }
   public String next()
   {
      try{
         return st.nextToken();
      }
      catch(Exception e){
         try{
            st = getst(br);
            return st.nextToken();
         }
         catch(Exception e2){
            return null;}
      }
   }
   public long nextLong(){
      return Long.parseLong(next());
   }
   public int nextInt(){
      return Integer.parseInt(next());
   }
}