A poor old man works in a palace for a living. One day the old man's wife met with an accident. She needed an immediate operation but the old man's savings were not enough for the operation. He went running to the king to beg for money. The king told that he will not only pay the full amount for the operation but also double his salary. But for that the old man had to pass a test. The king showed him a pile of glass plates kept one above another, each one being smaller than the one beneath. The plates were kept in box 1. He had to transfer the plates to box 3 using box 2. However, there were some constraints. The old man could only take one plate at a time and he could only place a smaller plate on top of a larger plate. He could take a plate only from the top. Help the old man do so. There are N plates and he has to tell the nth move in the format (i, j) where a plate is being moved from ith box to jth box.
Note:
Given any number of plates, they can be transferred from box 1 to box 3 using box 2 using the following steps.
Step 1: Transfer first N-1 plates from box 1 to box 2 using box 3.
Step 2: Transfer the remaining plate from box 1 to box 3.
Step 3: Transfer the first N-1 plates from box 2 to box 3 using box 1.
Example 1:
Input: N = 2, n = 2
Output: 1 3
Explaination:  The plate on top of box 1 is 
first transferred to box 2. The second plate 
from box 1 is transferred to box 3 and finally 
the plate from box 2 is transferred to box 3. 
In each situation, all the constraints are 
satisfied. You are required to print the 2nd 
move which is "Move plate from box 1 to box 3", 
hence 1 3.
Example 2:
Input: N = 3, n = 4.
Output: 1 3
Explaination: The movements of plates will 
be from 1 to 3. Then from 1 to 2. Then from 
3 to 2. And finally 4th move from 1 to 3.
Your Task:
You do not need to read input or print anyting. Your task is to complete the function shiftPile() which takes N and n as input parameters and returns the nth move in a list.
Expected Time Complexity: O(2^{N})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 20
1 ≤ n ≤ 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Complete search

Starter code: #User function Template for python3



class Solution:

    def shiftPile(self, N, n):

        # code here

Solutions:
class Solution:

	def shiftPile(self, N, n):
		if n == 0:
			return
		ans = []
		self.helper('1', '3', '2', ans, N)
		return ans[n - 1]

	def helper(self, src, dest, space, ans, N):
		if N == 0:
			return
		self.helper(src, space, dest, ans, N - 1)
		ans.append([src, dest])
		self.helper(space, dest, src, ans, N - 1)


class Solution:

	def shiftPile(self, N, n):
		ans = []

		def toh(N, a, b, c):
			global n
			if len(ans) != 0 or N == 0:
				return
			toh(N - 1, a, c, b)
			if n == 1:
				ans.extend([str(a), str(c)])
				return
			n = n - 1
			toh(N - 1, b, a, c)
		toh(N, 1, 2, 3)
		return ans


class Solution:

	def shiftPile(self, N, n):

		def solve(src, temp, dest, N, arr):
			if N == 0:
				return
			solve(src, dest, temp, N - 1, arr)
			array.append([src, dest])
			solve(temp, src, dest, N - 1, arr)
		array = []
		solve('1', '2', '3', N, array)
		return array[n - 1]


class Solution:

	def shiftPile(self, N, n):

		def tower(N, a, b, c):
			nonlocal res
			if N == 0:
				return
			tower(N - 1, a, c, b)
			res.append([a, c])
			tower(N - 1, c, a, b)
		res = []
		tower(N, '1', '2', '3')
		return res[n - 1]

class Solution:

	def find(self, src, temp, dest, N, res):
		if N == 0:
			return
		self.find(src, dest, temp, N - 1, res)
		res.append([src, dest])
		self.find(temp, src, dest, N - 1, res)

	def shiftPile(self, N, n):
		res = []
		self.find('1', '2', '3', N, res)
		return res[n - 1]


class Solution:

	def find(self, src, temp, dest, N, res):
		if N == 0:
			return
		self.find(src, dest, temp, N - 1, res)
		res.append([src, dest])
		self.find(temp, src, dest, N - 1, res)

	def shiftPile(self, N, n):
		res = []
		self.find('1', '2', '3', N, res)
		return res[n - 1]


class Solution:

	def shiftPile(self, N, n):
		steps = []

		def hanoi(N, A, B, C):
			if N > 0:
				hanoi(N - 1, A, C, B)
				steps.append([A, C])
				hanoi(N - 1, B, A, C)
		hanoi(N, 1, 2, 3)
		res = list(map(str, steps[n - 1]))
		return res


class Solution:

	def shiftPile(self, N, n):
		res = func('1', '2', '3', N, [])
		return res[n - 1]

def func(source, helper, destination, N, ans):
	if N == 0:
		return
	func(source, destination, helper, N - 1, ans)
	ans.append([source, destination])
	func(helper, source, destination, N - 1, ans)
	return ans


def Toh(N, st, mid, end, A, n, co):
	if N == 1:
		co[0] += 1
		if co[0] == n:
			A.append(st)
			A.append(end)
		return
	Toh(N - 1, st, end, mid, A, n, co)
	Toh(1, st, mid, end, A, n, co)
	Toh(N - 1, mid, st, end, A, n, co)

class Solution:

	def shiftPile(self, N, n):
		co = [0]
		A = []
		Toh(N, '1', '2', '3', A, n, co)
		return A


class Solution:

	def shiftPile(self, N, n):
		if n == 0:
			return
		ans = []
		self.helperFunc('1', '3', '2', ans, N)
		return ans[n - 1]

	def helperFunc(self, src, dest, mid, ans, N):
		if N == 0:
			return
		self.helperFunc(src, mid, dest, ans, N - 1)
		ans.append([src, dest])
		self.helperFunc(mid, dest, src, ans, N - 1)


class Solution:

	def setPlates(self, N, a, b, c, ans):
		if N > 0:
			self.setPlates(N - 1, a, c, b, ans)
			ans.append([a, c])
			self.setPlates(N - 1, b, a, c, ans)
		return

	def shiftPile(self, N, n):
		ans = []
		self.setPlates(N, '1', '2', '3', ans)
		return ans[n - 1]


class Solution:
	arr = []

	def shift(self, start, end, middle, piles):
		if piles == 0:
			return
		self.shift(start, middle, end, piles - 1)
		self.arr.append([start, end])
		self.shift(middle, end, start, piles - 1)

	def shiftPile(self, N, n):
		self.arr = []
		self.shift('1', '3', '2', N)
		return self.arr[n - 1]


class Solution:

	def slove(self, src, dest, help, ans, N):
		if N == 0:
			return
		Solution.slove(self, src, help, dest, ans, N - 1)
		ans.append([src, dest])
		Solution.slove(self, help, dest, src, ans, N - 1)

	def shiftPile(self, N, n):
		if n == 0:
			return
		ans = []
		Solution.slove(self, '1', '3', '2', ans, N)
		return ans[n - 1]


class Solution:

	def shiftPile(self, N, n):

		def move(k, frm, spare, to):
			nonlocal n
			if k == 0:
				return None
			r = move(k - 1, frm, to, spare)
			if r:
				return r
			n -= 1
			if n == 0:
				return [frm, to]
			return move(k - 1, spare, frm, to)
		return move(N, '1', '2', '3')


class Solution:

	def dfs(self, n, src, aux, dest, m, ans, moveCount):
		if n == 1:
			moveCount[0] += 1
			if moveCount[0] == m:
				ans.append(src)
				ans.append(dest)
			return
		self.dfs(n - 1, src, dest, aux, m, ans, moveCount)
		moveCount[0] += 1
		if moveCount[0] == m:
			ans.append(src)
			ans.append(dest)
		self.dfs(n - 1, aux, src, dest, m, ans, moveCount)

	def shiftPile(self, n, m):
		ans = []
		moveCount = [0]
		self.dfs(n, '1', '2', '3', m, ans, moveCount)
		return ans


class Solution:

	def shiftPile(self, N, n):
		if n == 0:
			return
		ans = []
		self.helper('1', '3', '2', ans, N)
		return ans[n - 1]

	def helper(self, from_rod, to_rod, aux_rod, ans, N):
		if N == 0:
			return
		self.helper(from_rod, aux_rod, to_rod, ans, N - 1)
		ans.append([from_rod, to_rod])
		self.helper(aux_rod, to_rod, from_rod, ans, N - 1)


class Solution:

	def shiftPile(self, N, n):
		seq = []

		def move(N, fromB, toB, leftB):
			if N == 1:
				seq.append([fromB, toB])
				return
			move(N - 1, fromB, leftB, toB)
			seq.append([fromB, toB])
			move(N - 1, leftB, toB, fromB)
		move(N, '1', '3', '2')
		for i in range(len(seq)):
			if i == n - 1:
				return seq[i]


class Solution:

	def shiftPile(self, N, n):
		ans = []

		def solve(source, dest, aux, N):
			if N == 1:
				ans.append([source, dest])
				return
			solve(source, aux, dest, N - 1)
			ans.append([source, dest])
			solve(aux, dest, source, N - 1)
			return
		solve('1', '3', '2', N)
		return ans[n - 1]


class Solution:

	def shiftPile(self, N, n):
		a = []
		func('1', '2', '3', N, a)
		return a[n - 1]

def func(src, temp, dest, N, a):
	if N == 0:
		return
	func(src, dest, temp, N - 1, a)
	a.append([src, dest])
	func(temp, src, dest, N - 1, a)


class Solution:

	def shiftPile(self, N, n):
		res = []

		def recur(begin, helper, dest, N):
			if N == 0:
				return
			recur(begin, dest, helper, N - 1)
			res.append([begin, dest])
			recur(helper, begin, dest, N - 1)
		recur('1', '2', '3', N)
		return res[n - 1]


class Solution:

	def shiftPile(self, N, n):
		arr = []
		self.towerHanoi(N, '1', '2', '3', arr)
		return arr[n - 1]

	def towerHanoi(self, N, s, a, d, arr):
		if N > 0:
			self.towerHanoi(N - 1, s, d, a, arr)
			arr.append([s, d])
			self.towerHanoi(N - 1, a, s, d, arr)


class Solution:

	def TowOfHanoi(self, source, dest, helper, ans, n):
		if n == 1:
			ans.append([source, dest])
			return
		self.TowOfHanoi(source, helper, dest, ans, n - 1)
		ans.append([source, dest])
		self.TowOfHanoi(helper, dest, source, ans, n - 1)
		return

	def shiftPile(self, N, n):
		ans = []
		self.TowOfHanoi(1, 3, 2, ans, N)
		arr = []
		arr.append(str(ans[n - 1][0]))
		arr.append(str(ans[n - 1][1]))
		return arr


class Solution:

	def shiftPile(self, N, n):
		arr = []
		self.solve('1', '2', '3', N, arr)
		return arr[n - 1]

	def solve(self, src, temp, dest, N, arr):
		if N == 0:
			return
		self.solve(src, dest, temp, N - 1, arr)
		arr.append([src, dest])
		self.solve(temp, src, dest, N - 1, arr)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, n) = [int(x) for x in input().split()]
		ob = Solution()
		ans = ob.shiftPile(N, n)
		print(ans[0] + ' ' + ans[1])


class Solution:

	def shiftPile(self, N, n):
		(source, temp, dest) = ('1', '2', '3')
		for i in range(N - 1, -1, -1):
			mid = 1 << i
			if n == mid:
				return [source, dest]
			elif n < mid:
				(temp, dest) = (dest, temp)
			else:
				n -= mid
				(source, temp) = (temp, source)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, n) = [int(x) for x in input().split()]
		ob = Solution()
		ans = ob.shiftPile(N, n)
		print(ans[0] + ' ' + ans[1])


class Solution:

	def helper(self, N, n, box1, box3, box2, steps):
		if N == 0 or n == 0:
			return
		if N == 1:
			steps.append([box1, box3])
			return
		self.helper(N - 1, n, box1, box2, box3, steps)
		self.helper(1, n, box1, box3, box2, steps)
		self.helper(N - 1, n, box2, box3, box1, steps)

	def shiftPile(self, N, n):
		steps = []
		self.helper(N, n, '1', '3', '2', steps)
		return steps[n - 1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, n) = [int(x) for x in input().split()]
		ob = Solution()
		ans = ob.shiftPile(N, n)
		print(ans[0] + ' ' + ans[1])


class Solution:

	def shiftPile(self, N, n):

		def move(k, frm, spare, to):
			nonlocal n
			if k == 0:
				return None
			r = move(k - 1, frm, to, spare)
			if r:
				return r
			n -= 1
			if n == 0:
				return [frm, to]
			return move(k - 1, spare, frm, to)
		return move(N, '1', '2', '3')
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, n) = [int(x) for x in input().split()]
		ob = Solution()
		ans = ob.shiftPile(N, n)
		print(ans[0] + ' ' + ans[1])


class Solution:

	def shiftPile(self, N, n):

		def rec(N, fromm, to, aux, ans, temp):
			if N == 1:
				temp = []
				temp.append(str(fromm))
				temp.append(str(to))
				ans.append(temp)
				return
			rec(N - 1, fromm, aux, to, ans, temp)
			temp = []
			temp.append(str(fromm))
			temp.append(str(to))
			ans.append(temp)
			rec(N - 1, aux, to, fromm, ans, temp)
		ans = []
		temp = []
		rec(N, 1, 3, 2, ans, temp)
		return ans[n - 1]


class Solution:

	def __init__(self):
		self.steps = []

	def shiftPile(self, N, n):
		self.n = n
		self.solveTowerOfHanoi(N, 1, 3, 2)
		return self.steps[n - 1]

	def solveTowerOfHanoi(self, N, source, destination, auxRod):
		if N == 1:
			self.steps.append([str(source), str(destination)])
			self.n -= 1
			return
		self.solveTowerOfHanoi(N - 1, source, auxRod, destination)
		if self.n is 0:
			return
		self.solveTowerOfHanoi(1, source, destination, auxRod)
		if self.n is 0:
			return
		self.solveTowerOfHanoi(N - 1, auxRod, destination, source)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, n) = [int(x) for x in input().split()]
		ob = Solution()
		ans = ob.shiftPile(N, n)
		print(ans[0] + ' ' + ans[1])


class Solution:

	def __init__(self):
		self.steps = []

	def shiftPile(self, N, n):
		self.n = n
		self.solveTowerOfHanoi(N, '1', '3', '2')
		return self.steps[0]

	def solveTowerOfHanoi(self, N, source, destination, auxRod):
		if N == 1:
			self.n -= 1
			if self.n == 0:
				self.steps.append([source, destination])
			return
		self.solveTowerOfHanoi(N - 1, source, auxRod, destination)
		self.solveTowerOfHanoi(1, source, destination, auxRod)
		self.solveTowerOfHanoi(N - 1, auxRod, destination, source)


def toh(N, A, C, B, n, q, count):
	if N == 0 or n == 0:
		return
	if N == 1:
		count[0] = count[0] + 1
		if count[0] == n:
			q.append(A)
			q.append(C)
		return
	toh(N - 1, A, B, C, n, q, count)
	toh(1, A, C, B, n, q, count)
	toh(N - 1, B, C, A, n, q, count)

class Solution:

	def shiftPile(self, N, n):
		count = [0]
		q = []
		toh(N, '1', '3', '2', n, q, count)
		return q


def toh(N, f, t, a, n, c):
	if N == 1:
		c.append((str(f), str(t)))
		return
	toh(N - 1, f, a, t, n, c)
	c.append((str(f), str(t)))
	toh(N - 1, a, t, f, n, c)

class Solution:

	def shiftPile(self, N, n):
		c = []
		toh(N, 1, 3, 2, n, c)
		return c[n - 1]


class Solution:

	def shiftPile(self, N, n):
		ans = []
		self.toh(ans, '1', '3', '2', N)
		return ans[n - 1]

	def toh(self, ans, src, dest, aux, N):
		if N == 1:
			ans.append([src, dest])
			return
		self.toh(ans, src, aux, dest, N - 1)
		ans.append([src, dest])
		self.toh(ans, aux, dest, src, N - 1)
		return


class Solution:

	def helper(self, N, fromm, mid, to, ans):
		if N == 0:
			return
		self.helper(N - 1, fromm, to, mid, ans)
		currMove = [fromm, to]
		ans.append(currMove)
		self.helper(N - 1, mid, fromm, to, ans)

	def shiftPile(self, N, n):
		ans = []
		fromm = '1'
		mid = '2'
		to = '3'
		self.helper(N, fromm, mid, to, ans)
		return ans[n - 1]


class Solution:

	def shiftPile(self, N, n):
		arr = []
		self.solve('1', '3', '2', N, arr)
		return arr[n - 1]

	def solve(self, fromm, to, aux, N, arr):
		if N == 0:
			return
		self.solve(fromm, aux, to, N - 1, arr)
		arr.append([fromm, to])
		self.solve(aux, to, fromm, N - 1, arr)


class Solution:

	def shiftPile(self, N, n):
		self.count = 1

		def f(N, a, b, c, n):
			if N == 1:
				if self.count == n:
					res.append(str(a))
					res.append(str(c))
				self.count += 1
				return
			f(N - 1, a, c, b, n)
			f(1, a, b, c, n)
			f(N - 1, b, a, c, n)
		res = []
		f(N, 1, 2, 3, n)
		return res


arr = [0, 0]

def func(N, n, count, source, destination, helper):
	if N == 1:
		count[0] += 1
		if count[0] == n:
			arr[0] = str(source)
			arr[1] = str(destination)
			return arr
		return
	func(N - 1, n, count, source, helper, destination)
	func(1, n, count, source, destination, helper)
	func(N - 1, n, count, helper, destination, source)
	return arr

class Solution:

	def shiftPile(self, N, n):
		count = [0]
		f = func(N, n, count, 1, 3, 2)
		return f


class Solution:

	def __init__(self):
		self.iMoveNumber = 0
		self.listMoves = list()
		self.n = 0
		pass

	def print(self, *args):
		pass

	def shiftPile(self, N, n):
		pass
		self.n = n
		self.moveThem(N, 1, 3)
		self.print('listMoves', self.listMoves)
		iMoveIndex = n - 1
		self.print('move number n', n, self.listMoves[iMoveIndex])
		cSource = str(self.listMoves[iMoveIndex][0])
		cTarget = str(self.listMoves[iMoveIndex][1])
		return (cSource, cTarget)

	def moveOne(self, iSource, iTarget, cInfo):
		self.iMoveNumber += 1
		self.print('Move', cInfo, self.iMoveNumber, ': from', iSource, 'to', iTarget)
		self.listMoves.append([iSource, iTarget])

	def moveThem(self, iTiles, iSource, iTarget):
		self.print('moveThem', iTiles, iSource, iTarget)
		if iTiles == 1:
			self.moveOne(iSource, iTarget, 'last one')
			return
		iNewTiles = iTiles - 1
		iIntermediate = 6 - iSource - iTarget
		iNewSource = iSource
		if iNewTiles % 2 == 0:
			iNewTarget = iIntermediate
		else:
			iNewTarget = iTarget
		iNewTarget = iIntermediate
		iNewIntermediate = 6 - iNewSource - iNewTarget
		if self.iMoveNumber > self.n:
			return
		self.moveThem(iNewTiles, iNewSource, iNewTarget)
		self.moveOne(iSource, iTarget, 'middle')
		self.moveThem(iNewTiles, iNewTarget, iTarget)


class Solution:

	def TowerOfHanoi(self, n, from_rod, to_rod, aux_rod):
		if n == 0:
			return
		if n > 1:
			self.TowerOfHanoi(n - 1, from_rod, aux_rod, to_rod)
		self.count += 1
		if self.count == self.m:
			self.ans = [from_rod, to_rod]
		if n > 1:
			self.TowerOfHanoi(n - 1, aux_rod, to_rod, from_rod)

	def shiftPile(self, N, n):
		(self.count, self.ans, self.m) = (0, ['', ''], n)
		self.TowerOfHanoi(N, '1', '3', '2')
		return self.ans


class Solution:
	val = 0

	def shiftPile(self, N, n):
		self.val = n
		res = []

		def hanoi_helper(r, src, dst, aux, res):
			if r == 0:
				return
			hanoi_helper(r - 1, src, aux, dst, res)
			self.val -= 1
			if self.val == 0:
				res.append(src)
				res.append(dst)
				return
			hanoi_helper(r - 1, aux, dst, src, res)
		hanoi_helper(N, '1', '3', '2', res)
		return res


class Solution:

	def shiftPile(self, N, n):
		(start, spare, goal) = ('1', '2', '3')
		for i in range(N - 1, -1, -1):
			mid = 1 << i
			if n == mid:
				return [start, goal]
			elif n < mid:
				(spare, goal) = (goal, spare)
			else:
				n -= mid
				(start, spare) = (spare, start)


import sys
sys.setrecursionlimit(10000)

class Solution:

	def shiftPile(self, N, n):
		global ANS
		ANS = []

		def shift(N, n, A, C, B):
			if N == 1:
				moves[0] = moves[0] + 1
				if moves[0] == n:
					ANS.extend([str(A[0]), str(C[0])])
				return
			shift(N - 1, n, A, B, C)
			shift(1, n, A, C, B)
			if moves[0] == n:
				return
			shift(N - 1, n, B, C, A)
			return
		A = [1] + [1] * N
		B = [2]
		C = [3]
		moves = [0]
		shift(N, n, A, C, B)
		return ANS


class Solution:

	def shiftPile(self, N, n):
		lis = []

		def rec(source, des, helper, lis, N):
			if N == 1:
				lis.append([source, des])
				return
			rec(source, helper, des, lis, N - 1)
			lis.append([source, des])
			rec(helper, des, source, lis, N - 1)
			return
		rec(1, 3, 2, lis, N)
		lis1 = []
		lis1.append(str(lis[n - 1][0]))
		lis1.append(str(lis[n - 1][1]))
		return lis1


class Solution:

	def shiftPile(self, N, n):

		def recurse(src, des, hel, res, N):
			if N == 1:
				res.append((src, des))
				return
			recurse(src, hel, des, res, N - 1)
			res.append((src, des))
			recurse(hel, des, src, res, N - 1)
		res = []
		recurse(1, 3, 2, res, N)
		return str(res[n - 1][0]) + str(res[n - 1][1])


class Solution:

	def helper(self, s, d, h, N, n, cnt, answer):
		if N == 1:
			cnt[0] += 1
			if cnt[0] == n:
				answer.append(str(s))
				answer.append(str(d))
			return
		if cnt[0] < n:
			self.helper(s, h, d, N - 1, n, cnt, answer)
		cnt[0] += 1
		if cnt[0] == n:
			answer.append(str(s))
			answer.append(str(d))
		if cnt[0] < n:
			self.helper(h, d, s, N - 1, n, cnt, answer)

	def shiftPile(self, N, n):
		s = 1
		h = 2
		d = 3
		cnt = [0]
		answer = []
		self.helper(s, d, h, N, n, cnt, answer)
		return answer


class Solution:

	def shiftPile(self, N, n):
		(start, end) = (1, 3)
		res = []

		def hanoi(N, start, end):
			if N == 1:
				res.append([str(start), str(end)])
			else:
				aux = 6 - (start + end)
				hanoi(N - 1, start, aux)
				res.append([str(start), str(end)])
				hanoi(N - 1, aux, end)
		hanoi(N, start, end)
		return res[n - 1]


class Solution:

	def towerHanoi(self, N, sourceBox, mainBox, tempBox, arr):
		if N == 1:
			arr.append([sourceBox, mainBox])
		else:
			self.towerHanoi(N - 1, sourceBox, tempBox, mainBox, arr)
			arr.append([sourceBox, mainBox])
			self.towerHanoi(N - 1, tempBox, mainBox, sourceBox, arr)

	def shiftPile(self, N, n):
		arr = []
		self.towerHanoi(N, '1', '3', '2', arr)
		return arr[n - 1]


class Solution:

	def __init__(self):
		self.cnt = 0

	def toh(self, N, n, src, dest, helper, res):
		if N == 0:
			return
		self.toh(N - 1, n, src, helper, dest, res)
		self.cnt += 1
		if self.cnt == n:
			res.append([str(src), str(dest)])
		self.toh(N - 1, n, helper, dest, src, res)

	def shiftPile(self, N, n):
		res = []
		self.toh(N, n, 1, 3, 2, res)
		return res[0]


class Solution:

	def hanoi(self, N, a, c, b, n, p):
		if N == 0:
			return
		self.hanoi(N - 1, a, b, c, n, p)
		p += [[str(a), str(c)]]
		self.hanoi(N - 1, b, c, a, n, p)

	def shiftPile(self, N, n):
		p = []
		self.hanoi(N, 1, 3, 2, n, p)
		return [p[n - 1][0], p[n - 1][1]]


class Solution:

	def shiftPile(self, N, n):
		li = []

		def rec(N, s, a, d):
			if N == 1:
				li.append([s, d])
				return
			rec(N - 1, s, d, a)
			li.append([s, d])
			rec(N - 1, a, s, d)
		rec(N, '1', '2', '3')
		return li[n - 1]


class Solution:
	step = 0

	def shiftPile(self, N, n):
		ans = []

		def helper(plate, from_rod, to_rod, aux_nod):
			if plate == 0:
				return
			helper(plate - 1, from_rod, aux_nod, to_rod)
			self.step += 1
			if self.step == n:
				ans.extend([from_rod, to_rod])
			helper(plate - 1, aux_nod, to_rod, from_rod)
		helper(N, '1', '3', '2')
		return ans


class Solution:

	def __init__(self):
		self.ans = 0
		self.y = 0

	def shiftPile(self, N, k):

		def TowerOfHanoi(n, from_rod, to_rod, aux_rod):
			if n == 0:
				return [0, 0]
			TowerOfHanoi(n - 1, from_rod, aux_rod, to_rod)
			self.ans += 1
			if self.ans == k:
				self.y = [from_rod, to_rod]
			TowerOfHanoi(n - 1, aux_rod, to_rod, from_rod)
		TowerOfHanoi(N, '1', '3', '2')
		return self.y


class Solution:

	def shiftPile(self, N, n):
		ans = []
		self.toh(N, '1', '3', '2', ans)
		v = []
		v.append(ans[n - 1][0])
		v.append(ans[n - 1][1])
		return v

	def toh(self, n, src, dst, helper, ans):
		if n == 0:
			return
		self.toh(n - 1, src, helper, dst, ans)
		ans.append([src, dst])
		self.toh(n - 1, helper, dst, src, ans)


class Solution:

	def shiftPile(self, N, n):
		res = []

		def towerOfHanoi(disks, source, aux, target):
			if disks == 1:
				res.append([source, target])
				return
			towerOfHanoi(disks - 1, source, target, aux)
			res.append([source, target])
			towerOfHanoi(disks - 1, aux, source, target)
		towerOfHanoi(N, '1', '2', '3')
		return res[n - 1]


class Solution:

	def shiftPile(self, N, n):
		dp = [0] * (N + 1)
		for i in range(1, N + 1):
			dp[i] = 2 * dp[i - 1] + 1

		def helper(N, n, order):
			(s, d, t) = order
			if n == dp[N - 1] + 1:
				return (s, d)
			elif n < dp[N - 1] + 1:
				return helper(N - 1, n, (s, t, d))
			else:
				return helper(N - 1, n - dp[N - 1] - 1, (t, d, s))
		return helper(N, n, ('1', '3', '2'))