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.IOException;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.TreeMap;

public class Main {
  private static final int H = 62;
  
	public static void main(String[] args) {
		FasterScanner sc = new FasterScanner();
		
		long[] size = new long[H];
		long[] lo = new long[H];
		long[] hi = new long[H];
		long[] shift = new long[H];
		for (int i = 1; i < H; ++i) {
		  size[i] = (1L << (i - 1));
		  lo[i] = (1L << (i - 1));
		  hi[i] = (1L << i) - 1;
		}

		int Q = sc.nextInt();
		
		for (int q = 0; q < Q; ++q) {
		  int T = sc.nextInt();
		  
		  switch (T) {
		    case 1: {
		      long X = sc.nextLong();
		      long K = sc.nextLong();
		      int start;
		      for (int h = 1; ; ++h) {
		        if (lo[h] <= X && X <= hi[h]) {
		          start = h;
		          break;
		        }
		      }
		      long amount = ((K % size[start]) + size[start]) % size[start];
		      shift[start] = (shift[start] + amount) % size[start];
		      break;
		    }
		    case 2: {
		      long X = sc.nextLong();
		      long K = sc.nextLong();
		      int start;
		      for (int h = 1; ; ++h) {
		        if (lo[h] <= X && X <= hi[h]) {
		          start = h;
		          break;
		        }
		      }
	        long amount = ((K % size[start]) + size[start]) % size[start];
		      for (int h = start; h < H; ++h) {
		        shift[h] = (shift[h] + amount) % size[h];
		        amount = (amount << 1) % (size[h] << 1);
		      }
		      break;
		    }
		    case 3: {
		      long X = sc.nextLong();
		      int start;
		      long pos;
      	  for (int h = 1; ; ++h) {
      	    if (lo[h] <= X && X <= hi[h]) {
      	      start = h;
      	      pos = X - lo[h] + shift[h];
      	      break;
      	    }
      	  }
		      StringBuilder sb = new StringBuilder();
      	  for (int h = start; h > 0; --h) {
      	    long what = lo[h] + ((pos - shift[h] + size[h]) % size[h]);
      	    pos >>= 1;
      	    sb.append(what + " ");
      	  }
      	  System.out.println(sb.toString());
		      break;
		    }
		  }
		  // for (int h = 1; h <= 6; ++h) {
		  //   System.out.format("h = %d, lo = %d, hi = %d, shift = %d, size = %d\n", h, lo[h], hi[h], shift[h], size[h]);
		  // }
		}
	}
	
// 	private static long[] find(long[] lo, long[] hi, long[] shift, long val) {
// 	}
	
// 	private static long get(long[] lo, long[] hi, long[] shift, long pos) {
// 	}

	public static class FasterScanner {
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

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

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

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

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

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

		public int[] nextIntArray(int n) {
			return nextIntArray(n, 0);
		}

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

		public long[] nextLongArray(int n) {
			return nextLongArray(n, 0);
		}

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

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

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