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.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {

		SC scan = new SC();
		PrintWriter pw = new PrintWriter(System.out);
		
		long[] level = new long[64];
		int q = scan.nextInt();
		while(q-- > 0) {
			int type = scan.nextInt();
			long x = scan.nextLong();
			int l = log2(x);
			if(type == 1) {
				long k = scan.nextLong() % (1L << l);
				level[l] += k;
				level[l + 1] -= 2*k;
			}
			else if(type == 2) {
				long k = scan.nextLong() % (1L << l);
				level[l] += k;
			}
			else {
				while(l > 0) {
					pw.print(x + " ");
					level[l] %= (1L << l);
					x += level[l];
					x %= (1L << l);
					x += (1L << l);
					x %= (1L << l);
					x += (1L << l);
					x /= 2;
					l--;
				}
				pw.println(1);
			}
		}
		pw.flush();
	}
	
	static int log2(long x) {
		int s = 0, e = 62;
		while(s < e) {
			long m = (s + e) / 2;
			if((1L << m) < x) s = (int) m + 1;
			else e = (int) m;
		}
		if((1L << e) > x) e--;
		return e;
	}
	
	static class SC {
		
		BufferedReader br;
		StringTokenizer st;

		public SC() throws Exception {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer("");
		}
		
		public SC(String fn) throws Exception {
			br = new BufferedReader(new FileReader(fn));
			st = new StringTokenizer("");
		}

		String nextLine() throws Exception {
			return br.readLine();
		}

		String next() throws Exception {
			while (!st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		int nextInt() throws Exception {
			return Integer.parseInt(next());

		}

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

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