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.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;
import java.util.Map.Entry;

public class Main
{
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;
	private PrintWriter pw;
	private long mod = 1000000000
			+ 7;

	private StringBuilder ans_sb;

	private void soln()
	{
		int q = nextInt();
		long[] shift = new long[70];
		long[] s1 = new long[70];
		while (q-- > 0)
		{
			int t = nextInt();
			if (t == 1)
			{
				long x = nextLong();
				long k = nextLong();
				String s = Long
						.toBinaryString(
								x);
				int level = s
						.length()
						- 1;
				long tot = (long) Math
						.pow(2, level
								+ 1);
				shift[level] += k;
				shift[level] %= tot;
			} else if (t == 3)
			{
				// debug(s1);
				// debug(shift);
				long x = nextLong();
				String s = Long
						.toBinaryString(
								x);
				int level = s
						.length()
						- 1;
				// debug(level);
				long par = x;
				while (par != 1
						&& level > 0)
				{
					long tot = (long) Math
							.pow(2, level
									+ 1);
					long tot1 = (long) Math
							.pow(2, level);
					pw.print(
							par + " ");
					// debug(par);
					long tmp = (x
							+ shift[level]
							+ tot)
							% tot;
					if (tmp < tot1)
					{
						tmp += tot1;
					}
					// debug(tmp);
					tmp = (tmp
							+ s1[level]
							+ tot)
							% tot;
					if (tmp < tot1)
					{
						tmp += tot1;
					}
					// System.out.println(tmp);
					par = value1(
							tmp / 2,
							shift[level
									- 1],
							level - 1);
					x = par;
					level--;
				}
				pw.println(
						1);
			} else
			{
				long x = nextLong();
				long k = nextLong();
				String s = Long
						.toBinaryString(
								x);
				int level = s
						.length()
						- 1;
				long tot = (long) Math
						.pow(2, level
								+ 1);
				s1[level] += k;
				s1[level] %= tot;
			}
		}

	}

	public long value1(
			long v,
			long shift,
			int lvl)
	{
		long tot = (long) Math
				.pow(2, lvl
						+ 1);
		// debug(v);
		// long tot1 = (long) Math.pow(2, level);
		long tot1 = (long) Math
				.pow(2, lvl);
		long tmp = (v
				- shift
				+ tot)
				% tot;
		// debug(tmp);
		if (tmp < tot1)
			tmp += tot1;
		return tmp;
	}

	class BitsetLong
	{

		static final int LOG = 6;
		static final int SIZE = 1 << LOG;
		static final int MASK = SIZE
				- 1;

		private long[] data;

		public BitsetLong(
				int n)
		{
			data = new long[(n >> LOG)
					+ 2];
		}

		void set(
				int i)
		{
			data[i >> LOG] |= 1L << (i
					& MASK);
		}

		void unset(
				int i)
		{
			data[i >> LOG] &= ~(1L << (i
					& MASK));
		}

		void flip(
				int i)
		{
			data[i >> LOG] ^= 1L << (i
					& MASK);
		}

		int get(int i)
		{
			return (int) ((data[i >> LOG] >>> (i
					& MASK))
					& 1);
		}

		void print()
		{
			for (int i = 0; i < data.length; i++)
			{
				System.out
						.print(Long
								.toString(
										data[i],
										2));
			}
			System.out
					.println();
		}

		long getWord(
				int i)
		{
			if (i <= -SIZE
					|| (i >> LOG)
							+ 1 >= data.length)
			{
				return 0;
			}
			int rem = i
					& MASK;
			int idx = i >> LOG;

			if (rem == 0)
			{
				return data[idx];
			}

			long head = idx < 0
					? 0
					: (data[idx] >>> rem);
			long tail = data[idx
					+ 1] << (SIZE
							- rem);

			return head
					| tail;
		}
	}

	int count(
			long[] bs,
			int len)
	{
		int ret = 0;
		for (int i = 0; i << 6 < len; i++)
		{
			if (((i + 1) << 6) <= len)
			{
				ret += Long
						.bitCount(
								bs[i]);
			} else
			{
				int rem = len
						& 63;
				ret += Long
						.bitCount(
								bs[i] << (64
										- rem));
			}
		}
		return ret;
	}

	private String solveEqn(
			long a,
			long b)
	{
		long x = 0,
				y = 1,
				lastx = 1,
				lasty = 0,
				temp;
		while (b != 0)
		{
			long q = a
					/ b;
			long r = a
					% b;
			a = b;
			b = r;
			temp = x;
			x = lastx
					- q * x;
			lastx = temp;
			temp = y;
			y = lasty
					- q * y;
			lasty = temp;
		}
		return lastx
				+ " "
				+ lasty;
	}

	private void debug(
			Object... o)
	{
		System.out
				.println(
						Arrays.deepToString(
								o));
	}

	private long pow(
			long a,
			long b,
			long c)
	{
		if (b == 0)
			return 1;
		long p = pow(
				a,
				b / 2,
				c);
		p = (p * p)
				% c;
		return (b
				% 2 == 0)
						? p
						: (a * p)
								% c;
	}

	private long gcd(
			long n,
			long l)
	{
		if (l == 0)
			return n;
		return gcd(
				l,
				n % l);
	}

	public static void main(
			String[] args)
			throws Exception
	{
		/*
		 * new Thread(null, new Runnable() {
		 * 
		 * @Override public void run() { new Main().solve(); } }, "1", 1 << 26).start();
		 */
		new Main()
				.solve();
	}

	public StringBuilder solve()
	{
		InputReader(
				System.in);
		/*
		 * try { InputReader(new FileInputStream("C:\\Users\\hardik\\Desktop\\in.txt"));
		 * } catch(FileNotFoundException e) {}
		 */
		pw = new PrintWriter(
				System.out);
		// ans_sb = new StringBuilder();
		soln();

		pw.close();
		// System.out.println(ans_sb);
		return ans_sb;
	}

	public void InputReader(
			InputStream stream1)
	{
		stream = stream1;
	}

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

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

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

	private 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;
	}

	private 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;
	}

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

	private 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();
	}

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

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

	private void pArray(
			int[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out
					.print(arr[i]
							+ " ");
		}
		System.out
				.println();
		return;
	}

	private void pArray(
			long[] arr)
	{
		for (int i = 0; i < arr.length; i++)
		{
			System.out
					.print(arr[i]
							+ " ");
		}
		System.out
				.println();
		return;
	}

	private boolean isSpaceChar(
			int c)
	{
		if (filter != null)
			return filter
					.isSpaceChar(
							c);
		return isWhitespace(
				c);
	}

	private char nextChar()
	{
		int c = read();
		while (isSpaceChar(
				c))
			c = read();
		char c1 = (char) c;
		while (!isSpaceChar(
				c))
			c = read();
		return c1;
	}

	private interface SpaceCharFilter
	{
		public boolean isSpaceChar(
				int ch);
	}
}