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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class DivCmb_474D {

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter printer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		int nQ = Integer.parseInt(reader.readLine());

		long[] delta = new long[75];

		while (nQ-- > 0) {
			StringTokenizer inputData = new StringTokenizer(reader.readLine());
			int type = Integer.parseInt(inputData.nextToken());
			long target = Long.parseLong(inputData.nextToken());
			int tLevel = fLevel(target);
			long tLSize = fSize(tLevel);

			if (type != 3) {
				long shift = Long.parseLong(inputData.nextToken());
				delta[tLevel] = (delta[tLevel] - shift % tLSize + tLSize) % tLSize;

				if (type == 1) {
					int lLevel = tLevel + 1;
					long lLSize = tLSize * 2;
					delta[lLevel] = (delta[lLevel] + 2 * shift) % lLSize;
				}
			} else {
				long cNode = target;

				while (cNode != 0) {
					printer.print(cNode + " ");
					int cLevel = fLevel(cNode);
					long cLSize = fSize(cLevel);
					cNode -= delta[cLevel];
					if (cNode >= 2 * cLSize) {
						cNode -= cLSize;
					}
					if (cNode < cLSize) {
						cNode += cLSize;
					}
					
					cNode /= 2;
				}

				printer.println();
			}
		}
		printer.close();
	}

	// note node 1 is at level 1
	static int fLevel(long target) {
		return 64 - Long.numberOfLeadingZeros(target);
	}

	static long fSize(long level) {
		return 1L << (level - 1);
	}
	
	static void ass(boolean inp) {
		if(!inp) {
			throw new RuntimeException();
		}
	}
}