A binary tree is a tree which is characterized by one of the following properties:

It can be empty (null).
It contains a root node only.
It contains a root node with a left subtree, a right subtree, or both. These subtrees are also binary trees.

In-order traversal is performed as

Traverse the left subtree.
Visit root.
Traverse the right subtree.

For this in-order traversal, start from the left child of the root node and keep exploring the left subtree until you reach a leaf.  When you reach a leaf, back up to its parent, check for a right child and visit it if there is one.  If there is not a child, you've explored its left and right subtrees fully. If there is a right child, traverse its left subtree then its right in the same manner.  Keep doing this until you have traversed the entire tree.  You will only store the values of a node as you visit when one of the following is true:

it is the first node visited, the first time visited 
it is a leaf, should only be visited once  
all of its subtrees have been explored, should only be visited once while this is true  
it is the root of the tree, the first time visited  

Swapping: Swapping subtrees of a node means that if initially node has left subtree L and right subtree R, then after swapping, the left subtree will be R and the right subtree, L.

For example, in the following tree, we swap children of node 1.

                                Depth
    1               1            [1]
   / \             / \
  2   3     ->    3   2          [2]
   \   \           \   \
    4   5           5   4        [3]

In-order traversal of left tree is 2 4 1 3 5 and of right tree is 3 5 1 2 4.

Swap operation: 

We define depth of a node as follows:

The root node is at depth 1.
If the depth of the parent node is d, then the depth of current node will be d+1.

Given a tree and an integer, k, in one operation, we need to swap the subtrees of all the nodes at each depth h, where h ∈ [k, 2k, 3k,...].  In other words, if h is a multiple of k, swap the left and right subtrees of that level.

You are given a tree of n nodes where nodes are indexed from [1..n] and it is rooted at 1. You have to perform t swap operations on it, and after each swap operation print the in-order traversal of the current state of the tree.

Function Description

Complete the swapNodes function in the editor below.  It should return a two-dimensional array where each element is an array of integers representing the node indices of an in-order traversal after a swap operation.

swapNodes has the following parameter(s): 

- indexes: an array of integers representing index values of each $node[i]$, beginning with $node[1]$, the first element, as the root. 

- queries: an array of integers, each representing a $\boldsymbol{\mbox{k}}$ value.

Input Format 

The first line contains n, number of nodes in the tree.   

Each of the next n lines contains two integers, a b, where a is the index of left child, and b is the index of right child of i^{th} node.   

Note: -1 is used to represent a null node.   

The next line contains an integer, t, the size of $queries$. 

Each of the next t lines contains an integer $\textit{queries}[i]$, each being a value $\boldsymbol{\mbox{k}}$.  

Output Format 

For each k, perform the swap operation and store the indices of your in-order traversal to your result array.  After all swap operations have been performed, return your result array for printing.  

Constraints  

$1\leq n\leq1024$    
$1\leq t\leq100$  
$1\leq k\leq n$  
Either $a=-1$ or $2<=a<=n$  
Either $b=-1$ or $2<=b<=n$  
The index of a non-null child will always be greater than that of its parent.  

Sample Input 0  

3
2 3
-1 -1
-1 -1
2
1
1

Sample Output 0  

3 1 2
2 1 3

Explanation 0

As nodes 2 and 3 have no children, swapping will not have any effect on them. We only have to swap the child nodes of the root node.

    1   [s]       1    [s]       1   
   / \      ->   / \        ->  / \  
  2   3 [s]     3   2  [s]     2   3

Note:  [s] indicates that a swap operation is done at this depth.

Sample Input 1  

5
2 3
-1 4
-1 5
-1 -1
-1 -1
1
2

Sample Output 1  

4 2 1 5 3

Explanation 1

Swapping child nodes of node 2 and 3 we get

    1                  1  
   / \                / \ 
  2   3   [s]  ->    2   3
   \   \            /   / 
    4   5          4   5  

Sample Input 2  

11
2 3
4 -1
5 -1
6 -1
7 8
-1 9
-1 -1
10 11
-1 -1
-1 -1
-1 -1
2
2
4

Sample Output 2  

2 9 6 4 1 3 7 5 11 8 10
2 6 9 4 1 3 7 5 10 8 11

Explanation 2  

Here we perform swap operations at the nodes whose depth is either 2 or 4 for $K=2$ and then at nodes whose depth is 4 for $K=4$.

         1                     1                          1             
        / \                   / \                        / \            
       /   \                 /   \                      /   \           
      2     3    [s]        2     3                    2     3          
     /      /                \     \                    \     \         
    /      /                  \     \                    \     \        
   4      5          ->        4     5          ->        4     5       
  /      / \                  /     / \                  /     / \      
 /      /   \                /     /   \                /     /   \     
6      7     8   [s]        6     7     8   [s]        6     7     8
 \          / \            /           / \              \         / \   
  \        /   \          /           /   \              \       /   \  
   9      10   11        9           11   10              9     10   11

Difficulty: MEDIUM
Tags: Tree algorithms

Starter code:

Solutions:
def inorder(T):
	stack = [1]
	result = []
	while stack:
		i = stack.pop()
		if i > 0:
			if T[i][1] > 0:
				stack.append(T[i][1])
			stack.append(-i)
			if T[i][0] > 0:
				stack.append(T[i][0])
		else:
			result.append(-i)
	return result

def swap(T, K):
	(toVisit, depth) = ([1], 1)
	while toVisit:
		if depth % K == 0:
			for i in toVisit:
				T[i] = (T[i][1], T[i][0])
		toVisit_ = []
		for i in toVisit:
			if T[i][0] > 0:
				toVisit_.append(T[i][0])
			if T[i][1] > 0:
				toVisit_.append(T[i][1])
		toVisit = toVisit_
		depth += 1
N = int(input())
T = [None] + [tuple((int(_) for _ in input().split())) for _ in range(N)]
N = int(input())
for _ in range(N):
	swap(T, int(input()))
	print(' '.join((str(_) for _ in inorder(T))))


from collections import deque

class Node:

	def __init__(self, index):
		self.left = None
		self.right = None
		self.index = index

def in_order_traverse(root):
	stack = deque([root])
	visited = set()
	while stack:
		node = stack.pop()
		if node is None:
			continue
		if node.index in visited:
			print(node.index, end=' ')
			continue
		visited.add(node.index)
		stack.append(node.right)
		stack.append(node)
		stack.append(node.left)

def swap(root, k):
	q = deque([(root, 1)])
	while q:
		(node, level) = q.popleft()
		if node is None:
			continue
		if level % k == 0:
			(node.left, node.right) = (node.right, node.left)
		q.append((node.left, level + 1))
		q.append((node.right, level + 1))
N = int(input())
nodes = [None] * (N + 1)
for i in range(1, N + 1):
	n = Node(i)
	(n.left_index, n.right_index) = [v if v > 0 else 0 for v in map(int, input().split())]
	nodes[i] = n
for n in nodes[1:]:
	left = nodes[n.left_index]
	right = nodes[n.right_index]
	n.left = left
	n.right = right
T = int(input())
root = nodes[1]
for _ in range(T):
	k = int(input())
	swap(root, k)
	in_order_traverse(root)
	print('')


__author__ = 'Girish'
import sys
sys.setrecursionlimit(10000)

class node:

	def __init__(self, data=None):
		self.left = None
		self.right = None
		self.data = data
head = node(1)
temp = head

def add_in_tree(depth, data=None, j=0):
	if data == None:
		data = [head]
	if depth == j:
		return 0
	else:
		ansli = []
		for i in data:
			(x, y) = [int(x) for x in input().split()]
			if x != -1:
				i.left = node(x)
				ansli.append(i.left)
			if y != -1:
				i.right = node(y)
				ansli.append(i.right)
			j += 1
	return 1 + add_in_tree(depth, ansli, j)

def inorder_traversal(node):
	if node != None:
		inorder_traversal(node.left)
		print(node.data, end=' ')
		inorder_traversal(node.right)

def swap_at(depth, max_dp, node=head, j=0):
	if max_dp == j:
		return
	if (j + 1) % depth == 0:
		t1 = node.left
		t2 = node.right
		(node.left, node.right) = (node.right, node.left)
		if t1 != None:
			swap_at(depth, max_dp, t1, j + 1)
		if t2 != None:
			swap_at(depth, max_dp, t2, j + 1)
	else:
		if node.left != None:
			swap_at(depth, max_dp, node.left, j + 1)
		if node.right != None:
			swap_at(depth, max_dp, node.right, j + 1)
max_dpth = add_in_tree(int(input()))
for i in range(int(input())):
	swap_at(int(input()), max_dpth - 1)
	inorder_traversal(head)
	print()


import sys

class Node:

	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None
		self.depth = 1

	def setLeft(self, left):
		self.left = left

	def setRight(self, right):
		self.right = right

	def setDepth(self, depth):
		self.depth = depth

	def getDepth(self):
		return self.depth

	def swapNode(self):
		(self.left, self.right) = (self.right, self.left)

def Solution(root):
	if root.left is None and root.right is None:
		return str(root.val)
	elif root.left is None:
		return str(root.val) + ' ' + Solution(root.right)
	elif root.right is None:
		return Solution(root.left) + ' ' + str(root.val)
	else:
		return Solution(root.left) + ' ' + str(root.val) + ' ' + Solution(root.right)
sys.setrecursionlimit(1050)
n = int(input())
nodes = []
nodes.append(Node(1))
for i in range(n):
	temp = [int(x) for x in input().split(' ')]
	for j in range(2):
		if temp[j] is not -1:
			tempNode = Node(temp[j])
			tempNode.setDepth(nodes[i].getDepth() + 1)
			nodes.append(tempNode)
			if j is 0:
				nodes[i].setLeft(tempNode)
			else:
				nodes[i].setRight(tempNode)
k = int(input())
for i in range(k):
	a = int(input())
	for x in nodes:
		if x.getDepth() % a is 0:
			x.swapNode()
	answer = Solution(nodes[0])
	print(answer)


def printTree(tree):
	s = ''
	todo = [(1, True)]
	while todo:
		(i, pl) = todo.pop()
		(a, b) = tree[i]
		if pl:
			todo.append((i, False))
			if a != -1:
				todo.append((a, True))
		else:
			s += ' %d' % i
			if b != -1:
				todo.append((b, True))
	print(s[1:])

def swapNodes(tree, k):
	todo = [(1, 1)]
	while todo:
		(i, d) = todo.pop()
		(a, b) = tree[i]
		if d % k == 0:
			tree[i] = (b, a)
		if a != -1:
			todo.append((a, d + 1))
		if b != -1:
			todo.append((b, d + 1))
n = int(input())
nodes = [None]
for _ in range(n):
	(a, b) = map(int, input().split())
	nodes.append((a, b))
t = int(input())
for _ in range(t):
	k = int(input())
	swapNodes(nodes, k)
	printTree(nodes)


import math
import sys
sys.setrecursionlimit(1500)

class node:

	def __init__(self, id):
		self.id = id
		self.left = None
		self.right = None

	def prettyprint(self):
		if self.left is not None:
			self.left.prettyprint()
		if self.id != -1:
			print(self.id, end=' ')
		if self.right is not None:
			self.right.prettyprint()

	def swapChilds(self):
		temp = self.left
		self.left = self.right
		self.right = temp

	def swapHeight(self, height, depth):
		if depth % height == 0:
			self.swapChilds()
		if self.left is not None:
			self.left.swapHeight(height, depth + 1)
		if self.right is not None:
			self.right.swapHeight(height, depth + 1)

class treeClass:

	def __init__(self, id):
		self.root = node(id)

	def prettyprint(self):
		self.root.prettyprint()
		print()

	def swapHeight(self, height):
		self.root.swapHeight(height, 1)

def fillTree(strtree):
	tofill = []
	tree = treeClass(strtree[0])
	tofill += [tree.root]
	pos = 1
	while len(tofill) > 0:
		tofill[0].left = node(strtree[pos])
		if strtree[pos] != -1:
			tofill += [tofill[0].left]
		tofill[0].right = node(strtree[pos + 1])
		if strtree[pos + 1] != -1:
			tofill += [tofill[0].right]
		tofill = tofill[1:]
		pos += 2
	return tree
strtree = [1]
N = int(input())
for n in range(0, N):
	line = [int(z) for z in input().split()]
	strtree += line
tree = fillTree(strtree)
T = int(input())
for t in range(0, T):
	K = int(input())
	tree.swapHeight(K)
	tree.prettyprint()
depth = math.ceil(math.log(len(strtree) + 1, 2))


from collections import defaultdict
nn = int(input())
tree = [[] for i in range(nn + 1)]
depth = [1] * (nn + 1)
maxDepth = 1
nodesAtDepth = defaultdict(list)
nodesAtDepth[1] = [1]
for i in range(1, nn + 1):
	(l, r) = map(int, input().split())
	tree[i] = [l, r]
	depth[l] = depth[r] = depth[i] + 1
	nodesAtDepth[depth[l]] += [l, r]
	maxDepth = max(maxDepth, depth[l])
so = int(input())
for i in range(0, so):
	d = int(input())
	for j in range(d, maxDepth, d):
		for node in nodesAtDepth[j]:
			kids = tree[node]
			(kids[1], kids[0]) = (kids[0], kids[1])
	ans = ''
	stack = [1]
	curr = 1
	while stack[0] != -1:
		if stack[-1] == -1:
			stack.pop()
			curr = stack.pop()
			ans += str(curr) + ' '
			curr = tree[curr][1]
			stack.append(curr)
			continue
		curr = tree[curr][0]
		stack.append(curr)
	print(ans)


__author__ = 'aditya.patel'
import sys

class Node:
	nodes = []

	def __init__(self, i, a, b):
		self.stage = i
		self.l = a
		self.r = b
		self.depth = None
		Node.nodes.append(self)

	def left(self):
		if self.l == -1:
			return None
		return Node.nodes[self.l - 1]

	def right(self):
		if self.r == -1:
			return None
		return Node.nodes[self.r - 1]

	@classmethod
	def inorder_print(cls):
		stack = []
		node = cls.head()
		while 1:
			while node is not None:
				stack.append(node)
				node = node.left()
			if len(stack) == 0:
				return
			node = stack.pop()
			sys.stdout.write('%d ' % node.stage)
			node = node.right()

	@classmethod
	def head(cls):
		return cls.nodes[0]

	def swap(self):
		tmp = self.l
		self.l = self.r
		self.r = tmp

	@classmethod
	def Swap_nodes(cls, k):
		depth_nodes = []
		depth = 1
		n = Node.head()
		n.depth = depth
		depth_nodes.insert(0, n)
		while len(depth_nodes) > 0:
			n = depth_nodes.pop()
			if n.depth % k == 0:
				n.swap()
			l = n.left()
			if l:
				l.depth = n.depth + 1
				depth_nodes.append(l)
			r = n.right()
			if r:
				r.depth = n.depth + 1
				depth_nodes.append(r)
N = int(input())
for i in range(1, N + 1):
	(a, b) = map(int, input().split(' '))
	Node(i, a, b)
T = int(input())
for i in range(T):
	k = int(input())
	Node.Swap_nodes(k)
	Node.inorder_print()
	sys.stdout.write('\n')


N = int(input())
L = [-1] * (N + 1)
R = [-1] * (N + 1)
for i in range(1, N + 1):
	(L[i], R[i]) = [int(k) for k in input().split()]
T = int(input())
for _ in range(T):
	K = int(input())
	visited = [False] * (N + 1)
	ordering = []
	Q = [(1, 1)]
	while len(Q) > 0:
		(v, d) = Q[-1]
		if not visited[v]:
			if d % K == 0:
				(L[v], R[v]) = (R[v], L[v])
			if L[v] >= 0:
				Q.append((L[v], d + 1))
			visited[v] = True
		else:
			Q.pop()
			ordering.append(v)
			if R[v] >= 0:
				Q.append((R[v], d + 1))
	print(' '.join(map(str, ordering)))


class BinaryTree:

	def __init__(self, value=None):
		self.value = value
		self.left = None
		self.right = None

	def __str__(self):
		s = bt.in_order_traversal(lambda node: '%s ' % node.value, '')
		return s.strip()

	def in_order_traversal(self, f, init):
		result = init
		q = []
		node = self
		while len(q) > 0 or node is not None:
			if node is not None:
				q.append(node)
				node = node.left
			else:
				node = q.pop()
				result += f(node)
				node = node.right
		return result

	def level_order_traversal(self, f, init):
		result = init
		q = [self]
		level = 0
		while len(q) > 0:
			new_q = []
			level += 1
			for node in q:
				result += f(level, node)
				if not node.left is None:
					new_q.append(node.left)
				if not node.right is None:
					new_q.append(node.right)
			q = new_q
		return result

	def swap_children(self, k):

		def swap(level, node):
			if level % k == 0:
				(node.left, node.right) = (node.right, node.left)
			return []
		self.level_order_traversal(swap, [])

	def read_from_input(self, n=None):
		q = [self]
		while len(q) > 0:
			new_q = []
			for node in q:
				if n is not None:
					if n <= 0:
						return
					n -= 1
				(left, right) = map(int, input().split())
				if left != -1:
					node.left = BinaryTree(left)
					new_q.append(node.left)
				if right != -1:
					node.right = BinaryTree(right)
					new_q.append(node.right)
			q = new_q
n = int(input())
bt = BinaryTree(1)
bt.read_from_input(n)
t = int(input())
while t > 0:
	k = int(input())
	bt.swap_children(k)
	print(bt)
	t -= 1


import sys
sys.setrecursionlimit(10000)

class Tree:

	def __init__(self, data):
		if data == -1:
			self.data = None
		else:
			self.data = data
		self.left = None
		self.right = None

	def inorderTraversal(self):
		if self.left != None:
			self.left.inorderTraversal()
		if self.data != None:
			print(self.data, end=' ')
		if self.right != None:
			self.right.inorderTraversal()

def arrayToTree(treeMap, head, i):
	tmpNode = head
	queue = []
	for (key, value) in treeMap.items():
		if tmpNode.data == key:
			if value[0] == -1:
				tmpNode.left = None
			else:
				tmpNode.left = Tree(value[0])
			if value[1] == -1:
				tmpNode.right = None
			else:
				tmpNode.right = Tree(value[1])
			if value[0] != -1:
				queue.append(tmpNode.left)
			if value[1] != -1:
				queue.append(tmpNode.right)
		else:
			node = queue.pop(0)
			if node.data == key:
				node.left = Tree(value[0])
				node.right = Tree(value[1])
				if value[0] != -1:
					queue.append(node.left)
				if value[1] != -1:
					queue.append(node.right)

def swapSubTrees(head, depth, currentDepth):
	if head == None:
		return
	currentDepth = currentDepth + 1
	if currentDepth == depth:
		tmpNode = head.left
		head.left = head.right
		head.right = tmpNode
	else:
		swapSubTrees(head.left, depth, currentDepth)
		swapSubTrees(head.right, depth, currentDepth)

def findMaxDepth(tree):
	if tree == None:
		return 0
	leftHeight = findMaxDepth(tree.left)
	rightHeight = findMaxDepth(tree.right)
	return max(leftHeight, rightHeight) + 1
tree = [1]
numNodes = int(input())
treeMap = {}
i = 0
while i < numNodes:
	(a, b) = map(int, input().split())
	treeMap[i + 1] = [a, b]
	i = i + 1
head = Tree(1)
arrayToTree(treeMap, head, 0)
i = 0
numDepth = int(input())
maxDepth = findMaxDepth(head)
while i < numDepth:
	k = int(input())
	for j in range(1, maxDepth):
		if j * k < maxDepth:
			swapSubTrees(head, j * k, 0)
	i = i + 1
	head.inorderTraversal()
	if i < numDepth:
		print()


from collections import deque

class Node:

	def __init__(self, num):
		self.num = num
		self.leftChild = None
		self.rightChild = None

	def __repr__(self):
		left_child_num = -1 if self.leftChild is None else self.leftChild.num
		right_child_num = -1 if self.rightChild is None else self.rightChild.num
		return str(self.num) + '(' + str(left_child_num) + ' , ' + str(right_child_num) + ')'

	def setLeftChild(self, leftChild):
		self.leftChild = leftChild

	def setRightChild(self, rightChild):
		self.rightChild = rightChild

	def __hash__(self):
		return hash(self.num)

	def __eq__(self, other):
		return self.num == other.num

def getHeight_iter(root_node):
	node_queue = deque()
	level_to_nodes_dict = dict()
	node_queue.append(root_node)
	height = 0
	while True:
		count = len(node_queue)
		if len(node_queue) == 0:
			return (height, level_to_nodes_dict)
		height += 1
		while count > 0:
			top_node = node_queue.popleft()
			if height in level_to_nodes_dict:
				level_to_nodes_dict[height].append(top_node)
			else:
				level_to_nodes_dict[height] = [top_node]
			count -= 1
			if top_node.leftChild is not None:
				node_queue.append(top_node.leftChild)
			if top_node.rightChild is not None:
				node_queue.append(top_node.rightChild)

def swap(nodes):
	for n in nodes:
		temp_child = n.leftChild
		n.leftChild = n.rightChild
		n.rightChild = temp_child

def inorder_traverse_iter(root_node, order):
	stack = []
	current = root_node
	while True:
		while current is not None:
			stack.append(current)
			current = current.leftChild
		if not stack:
			return
		current = stack.pop()
		order.append(str(current.num))
		while current.rightChild is None and stack:
			current = stack.pop()
			order.append(str(current.num))
		current = current.rightChild
nodes = int(input())
root_node = None
nodes_dict = dict()
for i in range(0, nodes):
	j = i + 1
	node = Node(j)
	if node in nodes_dict:
		node = nodes_dict[node]
	else:
		nodes_dict[node] = node
	(left_num, right_num) = input().split()
	(left_num, right_num) = (int(left_num), int(right_num))
	if left_num >= 2:
		left_child = Node(left_num)
		if left_child in nodes_dict:
			node = nodes_dict[left_child]
		else:
			nodes_dict[left_child] = left_child
		node.setLeftChild(left_child)
	if right_num >= 2:
		right_child = Node(right_num)
		if right_child in nodes_dict:
			node = nodes_dict[right_child]
		else:
			nodes_dict[right_child] = right_child
		node.setRightChild(right_child)
	if i == 0:
		root_node = node
(height, level_to_nodes_dict) = getHeight_iter(root_node)
T = int(input())
for i in range(0, T):
	depth_index = int(input())
	result = []
	increment_fac = depth_index
	while depth_index <= height:
		nodes_at_level = level_to_nodes_dict[depth_index]
		swap(nodes_at_level)
		depth_index += increment_fac
	order = []
	inorder_traverse_iter(root_node, order)
	string = ' '.join(order)
	print(string)


class BinaryTree:

	def __init__(self, index):
		self.left = None
		self.right = None
		self.index = index

	def insert_left(self, child):
		if self.left is None:
			self.left = child
		else:
			child.left = self.left
			self.left = child

	def insert_right(self, child):
		if self.right is None:
			self.right = child
		else:
			child.right = self.right
			self.right = child

	def swap_subtrees(self):
		tmp = self.left
		self.left = self.right
		self.right = tmp

	def display(self):
		if self.left is not None:
			self.left.display()
		print('%d ' % self.index, end='')
		if self.right is not None:
			self.right.display()

def get_tree():
	num_nodes = int(input())
	nodes = []
	root = BinaryTree(1)
	nodes.append(root)
	for i in range(1, num_nodes + 1):
		(left, right) = [int(e) for e in input().split()]
		left_tree = None
		right_tree = None
		if left != -1:
			left_tree = BinaryTree(left)
			nodes[0].insert_left(left_tree)
		if right != -1:
			right_tree = BinaryTree(right)
			nodes[0].insert_right(right_tree)
		nodes.pop(0)
		if left != -1:
			nodes.append(left_tree)
		if right != -1:
			nodes.append(right_tree)
	return root

def swap(tree, cur_level, K):
	nodes = [[tree, 1]]
	cur = nodes[0][0]
	cur_level = 1
	while len(nodes) > 0 and cur != None:
		(cur, cur_level) = nodes.pop(0)
		if cur_level % K == 0:
			cur.swap_subtrees()
		if cur.left is not None:
			nodes.append([cur.left, cur_level + 1])
		if cur.right is not None:
			nodes.append([cur.right, cur_level + 1])
	return tree

def do_swaps(tree):
	T = int(input())
	for k in range(T):
		K = int(input())
		new_tree = swap(tree, 1, K)
		display_iterative(new_tree)

def display_iterative(tree):
	nodes = []
	cur = tree
	done = False
	while not done:
		if cur is not None:
			nodes.append(cur)
			cur = cur.left
		elif nodes:
			cur = nodes.pop()
			print('%d ' % cur.index, end='')
			cur = cur.right
		else:
			done = True
	print('')
tree = get_tree()
do_swaps(tree)


import sys

class Node:

	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

	def set_left(self, l):
		self.left = l

	def set_right(self, r):
		self.right = r

	def traverse(self):
		if self.left:
			self.left.traverse()
		print(self.val, end=' ')
		if self.right:
			self.right.traverse()

	def swap(self, i, K):
		if i == K:
			tmp = self.left
			self.left = self.right
			self.right = tmp
			i = 0
		if self.left:
			self.left.swap(i + 1, K)
		if self.right:
			self.right.swap(i + 1, K)
sys.setrecursionlimit(2000)
N = int(sys.stdin.readline())
nodes = [Node(i) for i in range(1, N + 1)]
for node in nodes:
	[left, right] = [int(X) for X in sys.stdin.readline().split()]
	if left != -1:
		node.set_left(nodes[left - 1])
	if right != -1:
		node.set_right(nodes[right - 1])
root = nodes[0]
T = int(sys.stdin.readline())
for case in range(T):
	K = int(sys.stdin.readline())
	root.swap(1, K)
	root.traverse()
	print()


__author__ = 'mtadmk'
import sys

class Tree:

	def __init__(self, depth, id):
		self.depth = depth
		self.id = id
		self.left = None
		self.right = None

def pr(arg):
	if db:
		print(arg)

def printit(v):
	for i in range(0, len(v)):
		sys.stdout.write(str(v[i]) + ' ')
	sys.stdout.write('\n')

def in_order(root):
	if root:
		return in_order(root.left) + [root.id] + in_order(root.right)
	return []

def get_by_id(i, nodes):
	return [x for x in nodes if x.id == i].pop()

def process(k, nodes):
	mult = 1
	while True:
		kk = k * mult
		mult += 1
		depth_nodes = [x for x in nodes if x.depth == kk]
		if len(depth_nodes) == 0:
			break
		for x in depth_nodes:
			tmp = x.left
			x.left = x.right
			x.right = tmp
	printit(in_order(get_by_id(1, nodes)))
	return nodes
sys.setrecursionlimit(10000)
db = False
nodes = [Tree(1, 1)]
if not db:
	n = int(input())
	for i in range(1, n + 1):
		(left, right) = list(map(int, input().split()))
		parent = get_by_id(i, nodes)
		if left != -1:
			left_tree = Tree(parent.depth + 1, left)
			parent.left = left_tree
			nodes.append(left_tree)
		if right != -1:
			right_tree = Tree(parent.depth + 1, right)
			parent.right = right_tree
			nodes.append(right_tree)
	t = int(input())
	for i in range(0, t):
		k = int(input())
		nodes = process(k, nodes)
else:
	pass


N = int(input())
tree = [[int(ch) for ch in input().split()] for i in range(N)]
levels = [True] * N

def traverse():
	stack = []
	stack.append((1, 0, 0))
	traversal = []
	while len(stack) > 0:
		(node, level, state) = stack.pop()
		if state == 0:
			stack.append((node, level, 1))
			L = tree[node - 1][0] if levels[level] else tree[node - 1][1]
			if L != -1:
				stack.append((L, level + 1, 0))
		elif state == 1:
			stack.append((node, level, 2))
			traversal.append(node)
		elif state == 2:
			stack.append((node, level, 3))
			R = tree[node - 1][1] if levels[level] else tree[node - 1][0]
			if R != -1:
				stack.append((R, level + 1, 0))
		elif state == 4:
			pass
	print(' '.join((str(i) for i in traversal)))
T = int(input())
for Ti in range(T):
	K = int(input())
	Ki = K
	while Ki <= N:
		levels[Ki - 1] = not levels[Ki - 1]
		Ki += K
	traverse()


import sys
sys.setrecursionlimit(10000)

class Node:

	def __init__(self, val):
		self.left = None
		self.right = None
		self.val = val
		self.h = 1

	def setChildren(self, left, right):
		self.left = left
		self.right = right

	def traverse(self):
		if self.left >= 0:
			nodes[self.left].traverse()
		print(self.val + 1, end=' ')
		if self.right >= 0:
			nodes[self.right].traverse()

	def __repr__(self):
		return str(self.val)

	def swap(self):
		(self.left, self.right) = (self.right, self.left)
n = int(input())
nodes = [Node(x) for x in range(n)]
for i in range(n):
	(left, right) = [int(x) - 1 for x in input().split()]
	nodes[i].setChildren(left, right)
	if left >= 0:
		nodes[left].h = nodes[i].h + 1
	if right >= 0:
		nodes[right].h = nodes[i].h + 1
t = int(input())
for i in range(t):
	k = int(input())
	for n in nodes:
		if n.h % k == 0:
			n.swap()
	nodes[0].traverse()
	print()


import sys
sys.setrecursionlimit(10000)

def parse(n):
	tree = dict()
	for i in range(1, n + 1):
		tree[i] = tuple(map(int, input().split()))
	return tree

def inorder(tree, root):
	if root == -1:
		return []
	(left, right) = tree[root]
	return inorder(tree, left) + [root] + inorder(tree, right)

def doswap(tree, root, swaplvl):
	currnodes = [root]
	currlvl = 1
	while currnodes:
		if currlvl % swaplvl == 0:
			for node in currnodes:
				(l, r) = tree[node]
				tree[node] = (r, l)
		nextnodes = []
		for node in currnodes:
			(l, r) = tree[node]
			if l != -1:
				nextnodes.append(l)
			if r != -1:
				nextnodes.append(r)
		currnodes = nextnodes
		currlvl += 1
n = int(input())
tree = parse(n)
t = int(input())
for i in range(t):
	doswap(tree, 1, int(input()))
	print(' '.join(map(str, inorder(tree, 1))))


import math
import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, value, left, right):
		self.value = value
		self.left = left
		self.right = right

def main():
	n = int(input())
	nodes = [Node(i, None, None) for i in range(1, n + 1)]
	for i in range(n):
		[left, right] = [int(value) for value in input().split()]
		if left != -1:
			nodes[i].left = nodes[left - 1]
		if right != -1:
			nodes[i].right = nodes[right - 1]
	height = getHeight(nodes[0])
	for _ in range(int(input())):
		levelIncrement = int(input())
		for level in range(levelIncrement, height, levelIncrement):
			nodesToSwap = nodesAtLevel(nodes[0], level)
			for node in nodesToSwap:
				if node != None:
					(node.left, node.right) = (node.right, node.left)
		printStack = inorderTraversal(nodes[0])
		print(' '.join([str(value) for value in printStack]))

def getHeight(root):
	if root != None:
		return max([1 + getHeight(root.left), 1 + getHeight(root.right)])
	return 0

def nodesAtLevel(root, level):
	nodes = []
	nodes.append(root)
	numNodesAtCurrentLevel = 1
	numNodesAtNextLevel = 0
	currentLevel = 1
	if currentLevel == level:
		return nodes
	while nodes:
		node = nodes[0]
		del nodes[0]
		numNodesAtCurrentLevel -= 1
		if node.left != None:
			nodes.append(node.left)
			numNodesAtNextLevel += 1
		if node.right != None:
			nodes.append(node.right)
			numNodesAtNextLevel += 1
		if numNodesAtCurrentLevel == 0:
			currentLevel += 1
			if currentLevel == level:
				return nodes
			numNodesAtCurrentLevel = numNodesAtNextLevel
			numNodesAtNextLevel = 0
	return nodes

def inorderTraversal(root):
	if root == None:
		return
	nodes = []
	printStack = []
	done = False
	current = root
	while not done:
		if current != None:
			nodes.append(current)
			current = current.left
		elif nodes:
			current = nodes.pop()
			printStack.append(current.value)
			current = current.right
		else:
			done = True
	return printStack
main()


import sys
sys.setrecursionlimit(1500)

class BinaryTree:

	def __init__(self, val, depth):
		self.left = None
		self.right = None
		self.val = val
		self.depth = depth

	def traverse(self):
		if self.left != None:
			self.left.traverse()
		print(self.val, end=' ')
		if self.right != None:
			self.right.traverse()
		if self.depth == 1:
			print('')

	def swap_children(self):
		temp = self.right
		self.right = self.left
		self.left = temp
tree_list = {1: BinaryTree('1', 1)}
depth_list = [[tree_list[1]]]

def swap_trees(k):
	for tl in depth_list[k - 1::k]:
		for tree in tl:
			tree.swap_children()
	tree_list[1].traverse()
N = int(input())
for n in range(1, N + 1):
	(a, b) = [int(x) for x in input().split()]
	tree = tree_list[n]
	if a != -1:
		tree.left = BinaryTree(a, tree.depth + 1)
		tree_list[a] = tree.left
		try:
			depth_list[tree.depth].append(tree.left)
		except IndexError:
			depth_list.append([tree.left])
	if b != -1:
		tree.right = BinaryTree(b, tree.depth + 1)
		tree_list[b] = tree.right
		try:
			depth_list[tree.depth].append(tree.right)
		except IndexError:
			depth_list.append([tree.right])
T = int(input())
for t in range(T):
	K = int(input())
	swap_trees(K)


def print_inorder(nodes):
	to_print = []
	stack = [(1, False)]
	while len(stack) != 0:
		elem = stack.pop()
		node_i = elem[0]
		if elem[1]:
			to_print.append(node_i)
			continue
		left = nodes[node_i]['left']
		right = nodes[node_i]['right']
		if right != -1:
			stack.append((right, False))
		stack.append((node_i, True))
		if left != -1:
			stack.append((left, False))
	print(' '.join((str(i) for i in to_print)))
N = int(input())
nodes = {}
for i in range(1, N + 1):
	(left, right) = [int(i) for i in input().split()]
	nodes[i] = {'left': left, 'right': right}
swaps = {}
node_by_depth = {1: [1]}
queue = [(1, 1)]
while len(queue) != 0:
	elem = queue.pop(0)
	node_index = elem[0]
	left = nodes[node_index]['left']
	right = nodes[node_index]['right']
	depth = elem[1]
	new_depth = depth + 1
	if new_depth not in node_by_depth:
		node_by_depth[new_depth] = []
	if left != -1:
		queue.append((left, depth + 1))
		node_by_depth[new_depth].append(left)
	if right != -1:
		queue.append((right, depth + 1))
		node_by_depth[new_depth].append(right)
	count = 0
	for K in swaps.keys():
		if depth % K == 0:
			count += 1
	if count % 2 == 1:
		nodes[nodex_index] = {'left': right, 'right': left}
T = int(input())
for t in range(T):
	K = int(input())
	for depth in node_by_depth.keys():
		if depth % K == 0:
			for node_i in node_by_depth[depth]:
				node = nodes[node_i]
				nodes[node_i] = {'left': node['right'], 'right': node['left']}
	print_inorder(nodes)


import sys
sys.setrecursionlimit(15000)
d = [0] * 2048
l = [0] * 2048
r = [0] * 2048
res = []

def w_tree(current):
	if l[current] > 0:
		w_tree(l[current])
	if current != 0:
		res.append(current)
	else:
		res.append(1)
	if r[current] > 0:
		w_tree(r[current])

def calc_dep(current, depth):
	d[current] = depth
	if l[current] > 0:
		calc_dep(l[current], depth + 1)
	if r[current] > 0:
		calc_dep(r[current], depth + 1)

def print_tree():
	s = ' '.join([str(c) for c in res])
	print(s)

def inverse():
	n = int(input())
	for i in range(1, n + 1):
		(l[i], r[i]) = list(map(int, input().split()))
	calc_dep(1, 1)
	for z in range(int(input())):
		k = int(input())
		for i in range(1, n + 1):
			if d[i] % k == 0:
				(l[i], r[i]) = (r[i], l[i])
		w_tree(1)
		print_tree()
		res.clear()
inverse()


import collections
import math
import sys

class TreeNode:

	def __init__(self, data=None, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

	def print_in_order(self):
		if self.left:
			self.left.print_in_order()
		print(self.data, end=' ')
		if self.right:
			self.right.print_in_order()

	def nodes_at_level(self, level):
		queue = collections.deque()
		temp_queue = []
		temp_queue.append(self)
		index = 1
		while index < level:
			for x in temp_queue:
				queue.append(x)
			temp_queue.clear()
			while queue:
				node = queue.popleft()
				if node.left:
					temp_queue.append(node.left)
				if node.right:
					temp_queue.append(node.right)
			index += 1
		return temp_queue

	def swap_branches(self):
		left = self.left
		self.left = self.right
		self.right = left

def height(node):
	if not node:
		return 0
	else:
		return 1 + max(height(node.left), height(node.right))

def prepare_tree():
	inpt = input()
	root = TreeNode(1)
	length = int(inpt)
	i = 0
	tree = collections.deque()
	tree.append(root)
	while tree and i < length:
		inpt = input()
		data = inpt.split(' ')
		node = tree.popleft()
		if data[0] != '-1':
			node.left = TreeNode(int(data[0]))
			tree.append(node.left)
		if data[1] != '-1':
			node.right = TreeNode(int(data[1]))
			tree.append(node.right)
		i += 1
	return root

def get_ks():
	inpt = input()
	(j, ks) = (0, [])
	while j < int(inpt):
		ks.append(int(input()))
		j += 1
	return ks

def main():
	tree = prepare_tree()
	h = height(tree)
	ks = get_ks()
	for k in ks:
		for i in range(1, int(h / k) + 1):
			nodes = tree.nodes_at_level(k * i)
			[node.swap_branches() for node in nodes]
		tree.print_in_order()
		print()
sys.setrecursionlimit(15000)
main()


class Node:

	def __init__(self, data, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

	def swap(self):
		r = self.right
		self.right = self.left
		self.left = r

def get_node(trees, n):
	if n == -1:
		return None
	else:
		return trees[n - 1]

def read_tree():
	n = int(input())
	trees = [Node(k) for k in range(1, n + 1)]
	for k in range(0, n):
		lr = list(map(int, input().split()))
		t = trees[k]
		(t.left, t.right) = (get_node(trees, lr[0]), get_node(trees, lr[1]))
	return trees[0]

def read_ks():
	ks = []
	t = int(input())
	for i in range(0, t):
		ks.append(int(input()))
	return ks
from collections import deque

def do_swaps(root, k):
	q = deque()
	q.append((root, 1))
	while len(q) > 0:
		(node, d) = q.popleft()
		if node.left:
			q.append((node.left, d + 1))
		if node.right:
			q.append((node.right, d + 1))
		if d % k == 0:
			node.swap()

def print_tree(node):
	q = deque()
	q.append(node)
	node = node.left
	while node or len(q) > 0:
		if node:
			q.append(node)
			node = node.left
		else:
			node = q.pop()
			print('{} '.format(node.data), end='')
			node = node.right
	print('', flush=True)
root = read_tree()
ks = read_ks()
for k in ks:
	do_swaps(root, k)
	print_tree(root)


import sys

class Node(object):

	def __init__(self, data=None, left_node=None, right_node=None):
		self.data = data
		self.left = left_node
		self.right = right_node

	def __str__(self):
		return '<Node {} {} {}>'.format(self.left, self.data, self.right)

def Inorder(root):
	if not root:
		return []
	return Inorder(root.left) + [str(root.data)] + Inorder(root.right)

def swap_nodes(root, k, d=1):
	if not root:
		return
	if not d % k:
		(root.left, root.right) = (root.right, root.left)
	swap_nodes(root.left, k, d + 1)
	swap_nodes(root.right, k, d + 1)
n_nodes = int(input())
node = [Node(i) for i in range(n_nodes + 1)]
for i in range(1, n_nodes + 1):
	(l, r) = map(int, input().split())
	if l > 0:
		node[i].left = node[l]
	if r > 0:
		node[i].right = node[r]
sys.setrecursionlimit(8000)
n_tests = int(input())
for t in range(n_tests):
	k = int(input())
	swap_nodes(node[1], k)
	print(' '.join(Inorder(node[1])))


from collections import defaultdict, deque

class BinaryNode(object):

	def __init__(self, value, left, right):
		self.value = value
		self.left = left
		self.right = right

class BinaryTree(object):

	def __init__(self, root):
		self.root = root
		self.depths = self.compute_depths(self.root)

	@classmethod
	def from_input(cls):
		nodes = [None] * int(input())
		for i in range(len(nodes)):
			(left, right) = map(int, input().split())
			nodes[i] = BinaryNode(i + 1, left if left > 0 else None, right if right > 0 else None)
		for node in nodes:
			if node.left is not None:
				node.left = nodes[node.left - 1]
			if node.right is not None:
				node.right = nodes[node.right - 1]
		return cls(nodes[0] if nodes else None)

	def compute_depths(self, root):
		depths = defaultdict(set)
		queue = []
		if root is not None:
			queue.append((root, 1))
		while queue:
			(node, depth) = queue.pop()
			depths[depth].add(node)
			if node.left is not None:
				queue.append((node.left, depth + 1))
			if node.right is not None:
				queue.append((node.right, depth + 1))
		return depths

	def swap_K(self, K):
		for depth in range(K, len(self.depths) + 1, K):
			self.swap_depth(depth)

	def swap_depth(self, depth):
		for node in self.depths[depth]:
			self.swap_node(node)

	def swap_node(self, node):
		(node.left, node.right) = (node.right, node.left)

	def __repr__(self):
		if self.root is None:
			return ''
		result = []
		order = deque([self.root])
		while order:
			node = order.pop()
			if isinstance(node, int):
				result.append(node)
			else:
				if node.right is not None:
					order.append(node.right)
				order.append(node.value)
				if node.left is not None:
					order.append(node.left)
		return ' '.join(map(str, result))
tree = BinaryTree.from_input()
T = int(input())
for _ in range(T):
	K = int(input())
	tree.swap_K(K)
	print(tree)


import sys
sys.setrecursionlimit(15000)
nodes = []

def inorder(i, nodes):
	results = []
	left = nodes[i][0]
	right = nodes[i][1]
	if left != -1:
		results.extend(inorder(left - 1, nodes))
	results.append(i + 1)
	if right != -1:
		results.extend(inorder(right - 1, nodes))
	return results

def goto_depth(i, k):
	results = []
	left = nodes[i][0]
	right = nodes[i][1]
	if k == 1:
		if left == -1 and right == -1:
			return []
		return [i]
	if left != -1:
		results.extend(goto_depth(left - 1, k - 1))
	if right != -1:
		results.extend(goto_depth(right - 1, k - 1))
	return results

def swap(i, nodes):
	nodes[i].reverse()

def pp(arr):
	print(' '.join([str(i) for i in arr]))
max_depth = 0
N = int(input())
for i in range(0, N):
	nodes.append([int(i) for i in input().split(' ')])
	left = nodes[i][0]
	right = nodes[i][1]
	if left != -1 or right != -1:
		max_depth += 1
T = int(input())
for i in range(T):
	K = int(input())
	k = K
	while k < max_depth + 2:
		swap_list = goto_depth(0, k)
		for idx in swap_list:
			swap(idx, nodes)
		k += K
	pp(inorder(0, nodes))


from sys import stdin
from sys import setrecursionlimit
data = stdin.read().splitlines()
N = int(data[0])
TREE = list((tuple(map(int, i.split(' '))) for i in data[1:N + 1]))
T = int(data[N + 1])
K = tuple((int(i) for i in data[N + 2:]))
setrecursionlimit(N + 1000)

class TreeNode:

	def __init__(self, data, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

	def __str__(self):
		return str(self.data)

def print_inorder(node):
	if node.left:
		print_inorder(node.left)
	print('{0} '.format(node.data), end='')
	if node.right:
		print_inorder(node.right)
nodes = [TreeNode(i) for i in range(1, N + 1)]
for (i, (left, right)) in enumerate(TREE):
	n = nodes[i]
	if left > 0:
		n.left = nodes[left - 1]
	if right > 0:
		n.right = nodes[right - 1]

def swap_tree(root, depth, current_depth=1):
	if current_depth % depth == 0:
		(root.left, root.right) = (root.right, root.left)
	if root.left:
		swap_tree(root.left, depth, current_depth + 1)
	if root.right:
		swap_tree(root.right, depth, current_depth + 1)
for k in K:
	swap_tree(nodes[0], k)
	print_inorder(nodes[0])
	print()


import sys
sys.setrecursionlimit(20000)

class Node(object):

	def __init__(self, val, parent=None, left=None, right=None):
		self.parent = parent
		self.left = left
		self.right = right
		self.val = val

	def inorder(self):
		if self.left:
			self.left.inorder()
		print(self.val, end=' ')
		if self.right:
			self.right.inorder()

	def swap(self):
		(self.left, self.right) = (self.right, self.left)
nodes = {}
nodes[1] = Node(1)
tree = nodes[1]
depths = [1]
N = int(input())
for i in range(1, N + 1):
	(a, b) = [int(x) for x in input().split()]
	if a != -1:
		nodes[a] = Node(a, parent=nodes[i])
		nodes[i].left = nodes[a]
		if i >= depths[-1]:
			depths.append(a)
	if b != -1:
		nodes[b] = Node(b, parent=nodes[i])
		nodes[i].right = nodes[b]
		if i >= depths[-1]:
			depths.append(b)
highest = max(nodes.keys())
depths.append(highest + 1)
T = int(input())
for i in range(T):
	K = int(input())
	j = 1
	while j * K < len(depths):
		for index in range(depths[j * K - 1], depths[j * K]):
			nodes[index].swap()
		j += 1
	tree.inorder()
	print()


import sys
sys.setrecursionlimit(15000)

def inorder(nodes, i):
	result = []
	if i != -1:
		result += inorder(nodes, nodes[i][0])
		result.append(str(i))
		result += inorder(nodes, nodes[i][1])
	return result

def get_depth_nodes(nodes, depth):
	if depth < 1:
		return []
	elif depth == 1:
		return [1]
	results = []
	for i in get_depth_nodes(nodes, depth - 1):
		results += [j for j in nodes[i] if j != -1]
	return results

def swap(nodes, k):
	depth = k
	nodes_at_depth = get_depth_nodes(nodes, depth)
	while nodes_at_depth:
		for i in nodes_at_depth:
			(nodes[i][0], nodes[i][1]) = (nodes[i][1], nodes[i][0])
		depth += k
		nodes_at_depth = get_depth_nodes(nodes, depth)
n = int(input().strip())
nodes = [[1]]
for i in range(n):
	nodes.append([int(i) for i in input().strip().split()])
t = int(input().strip())
for i in range(t):
	k = int(input().strip())
	swap(nodes, k)
	result = inorder(nodes, 1)
	print(' '.join(result))


def Inorder(s, tree):
	if s == -1:
		return
	Inorder(tree[s][0], tree)
	print(s, end=' ')
	Inorder(tree[s][1], tree)

def Swap(s, tree, K, depth):
	if s == -1:
		return
	if depth % K == 0:
		(tree[s][0], tree[s][1]) = (tree[s][1], tree[s][0])
	Swap(tree[s][0], tree, K, depth + 1)
	Swap(tree[s][1], tree, K, depth + 1)

def Inorder(s, tree):
	marked = set()
	Q = [s]
	while Q:
		s = Q.pop()
		if s == -1:
			continue
		if s in marked:
			print(s, end=' ')
			continue
		marked.add(s)
		Q += [tree[s][1], s, tree[s][0]]

def Swap(s, tree, K, depth):
	Q = [(s, depth)]
	while Q:
		(s, depth) = Q.pop()
		if s == -1:
			continue
		if depth % K == 0:
			(tree[s][0], tree[s][1]) = (tree[s][1], tree[s][0])
		Q.append((tree[s][0], depth + 1))
		Q.append((tree[s][1], depth + 1))
N = int(input())
tree = {}
for n in range(1, N + 1):
	(a, b) = map(int, input().split())
	tree[n] = [a, b]
T = int(input())
for _ in range(T):
	K = int(input())
	Swap(1, tree, K, 1)
	Inorder(1, tree)
	print()


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, val, left=None, right=None, depth=1):
		self.v = val
		self.l = left
		self.r = right
		self.d = depth

def inorder(top):
	r = ''
	if top.l is not None:
		r += inorder(top.l)
	r += str(top.v) + ' '
	if top.r is not None:
		r += inorder(top.r)
	return r

def swap(node):
	tmp = node.l
	node.l = node.r
	node.r = tmp
N = int(input())
nodes = []
for i in range(1, N + 1):
	nodes.append(Node(i))
for i in range(N):
	(il, ir) = map(int, input().split())
	if il != -1:
		nodes[i].l = nodes[il - 1]
		nodes[i].l.d = nodes[i].d + 1
	if ir != -1:
		nodes[i].r = nodes[ir - 1]
		nodes[i].r.d = nodes[i].d + 1
T = int(input())
for i in range(T):
	K = int(input())
	for j in range(N):
		if nodes[j].d % K == 0:
			swap(nodes[j])
	print(inorder(nodes[0]))


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, data, depth=1, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right
		self.depth = depth

def inOrderTraversal(head):
	if head:
		inOrderTraversal(head.left)
		traversal.append(head.data)
		inOrderTraversal(head.right)

def getDepthNodes(head, k):
	if head:
		getDepthNodes(head.left, k)
		if head.depth == k:
			depthNodes.append(head)
		getDepthNodes(head.right, k)
head = Node(1)
q = [head]
maxDepth = 0
for i in range(int(input())):
	(a, b) = map(int, input().split())
	current = q.pop(0)
	if a != -1:
		current.left = Node(a, current.depth + 1)
		maxDepth = current.depth + 1
		q.append(current.left)
	if b != -1:
		current.right = Node(b, current.depth + 1)
		maxDepth = current.depth + 1
		q.append(current.right)
for _ in range(int(input())):
	traversal = []
	depth = int(input())
	for d in range(depth, maxDepth, depth):
		depthNodes = []
		getDepthNodes(head, d)
		for node in depthNodes:
			(node.left, node.right) = (node.right, node.left)
	inOrderTraversal(head)
	print(' '.join([str(x) for x in traversal]))


import sys

class Node:

	def __init__(self, key):
		(self.key, self.left, self_right) = (key, None, None)

def build_tree(children, n):
	(nodes, root_flags) = ([], [True] * n)
	for i in range(0, n):
		nodes.append(Node(i))
	for i in range(0, n):
		nodes[i].left = None if children[i][0] == -1 else nodes[children[i][0] - 1]
		nodes[i].right = None if children[i][1] == -1 else nodes[children[i][1] - 1]
	for i in range(0, n):
		if nodes[i].left is not None:
			root_flags[nodes[i].left.key] = False
		if nodes[i].right is not None:
			root_flags[nodes[i].right.key] = False
	for i in range(0, n):
		if root_flags[i]:
			return nodes[i]

def swap_children(root, height, k):
	if root is None:
		return
	swap_children(root.left, height + 1, k)
	swap_children(root.right, height + 1, k)
	if height % k == 0:
		(root.left, root.right) = (root.right, root.left)

def print_inorder(root):
	if root is not None:
		print_inorder(root.left)
		print(root.key + 1, end=' ')
		print_inorder(root.right)

def get_height(root):
	if root is not None:
		return 1 + max(get_height(root.left), get_height(root.right))
	return 0
sys.setrecursionlimit(10000)
(n, edges) = (int(input()), [])
for i in range(0, n):
	edges.append(list(map(int, input().split())))
root = build_tree(edges, n)
t = int(input())
for i in range(0, t):
	k = int(input())
	swap_children(root, 1, k)
	print_inorder(root)
	print()


import sys
sys.setrecursionlimit(1000000)

def count_depth(node, depth):
	depthOfNodes[node] = depth
	if leftChild[node]:
		count_depth(leftChild[node], depth + 1)
	if rightChild[node]:
		count_depth(rightChild[node], depth + 1)

def in_order(node):
	if leftChild[node]:
		in_order(leftChild[node])
	print(node, end=' ')
	if rightChild[node]:
		in_order(rightChild[node])
N = int(input())
leftChild = [0 for i in range(N + 1)]
rightChild = [0 for i in range(N + 1)]
depthOfNodes = [0 for i in range(N + 1)]
for i in range(1, N + 1):
	(l, r) = map(int, input().split())
	if l > 0:
		leftChild[i] = l
	if r > 0:
		rightChild[i] = r
count_depth(1, 1)
T = int(input())
for i in range(T):
	depth = int(input())
	for node in range(1, N + 1):
		if not depthOfNodes[node] % depth:
			(leftChild[node], rightChild[node]) = (rightChild[node], leftChild[node])
	in_order(1)
	print()


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, _data=None, _left=None, _right=None):
		self.data = _data
		self.left = _left
		self.right = _right

def createNode(data):
	if data == -1:
		return None
	else:
		return Node(data)

def print_traversal(head):
	if head == None:
		return
	print_traversal(head.left)
	print(head.data, end=' ')
	print_traversal(head.right)

def swapNode(head, depth, k):
	if head == None:
		return
	if depth % k == 0:
		temp = head.left
		head.left = head.right
		head.right = temp
	swapNode(head.left, depth + 1, k)
	swapNode(head.right, depth + 1, k)
n = int(input())
hnode = Node(1)
q = []
q.append(hnode)
while len(q) != 0:
	if n == 0:
		break
	current = q.pop(0)
	(a, b) = [int(x) for x in input().split()]
	current.left = createNode(a)
	current.right = createNode(b)
	if current.left != None:
		q.append(current.left)
	if current.right != None:
		q.append(current.right)
	n -= 1
t = int(input())
for i in range(t):
	k = int(input())
	hcurrent = hnode
	swapNode(hcurrent, 1, k)
	print_traversal(hcurrent)
	print()


from collections import deque
N = int(input())
TREE = [None]

def swap_nodes(root_idx, k):
	queue = deque([(root_idx, 1)])
	while queue:
		(idx, depth) = queue.popleft()
		(l, r) = TREE[idx]
		if depth % k == 0:
			TREE[idx] = (r, l)
		if l != -1:
			queue.append((l, depth + 1))
		if r != -1:
			queue.append((r, depth + 1))

def inorder(root_idx):
	stack = []
	stack.append((root_idx, False))
	while stack:
		(c, expanded) = stack.pop()
		if expanded:
			yield c
			continue
		(l, r) = TREE[c]
		if r != -1:
			stack.append((r, False))
		if l != -1:
			stack.append((c, True))
			stack.append((l, False))
		else:
			yield c
for _ in range(N):
	(l, r) = [int(i) for i in input().split(' ', 1)]
	TREE.append((l, r))
T = int(input())
for _ in range(T):
	K = int(input())
	swap_nodes(1, K)
	print(' '.join((str(i) for i in inorder(1))))


def inOrder(l):
	n = l[0]
	s = []
	r = []
	while s or n != -1:
		if n != -1:
			s.append(n)
			n = l[2 * n - 1]
		else:
			n = s.pop()
			r.append(n)
			n = l[2 * n]
	print(' '.join(map(str, r)))

def swapTree(l, k):
	h = 1
	i = 1
	while i < len(l):
		if (d[i] - 1) % k == 0:
			(l[i], l[i + 1]) = (l[i + 1], l[i])
			i += 2
		else:
			i += 1
	inOrder(l)
n = int(input())
l = [1]
d = [-1] * len(l)
d[0] = 1
for i in range(1, n + 1):
	l.extend(map(int, input().split()))
	d.extend([d[l.index(i)] + 1] * 2)
t = int(input())
for i in range(t):
	k = int(input())
	swapTree(l, k)


import sys
sys.setrecursionlimit(15000)

def swapDepth(nodes, root, depth, k):
	if root is None or root == -1:
		return
	(l, r) = nodes[root - 1]
	if depth % k == 0:
		nodes[root - 1] = (r, l)
	swapDepth(nodes, l, depth + 1, k)
	swapDepth(nodes, r, depth + 1, k)

def inOrder(root, nodes):
	if root == -1:
		return None
	(l, r) = nodes[root - 1]
	return ' '.join([str(i) for i in [inOrder(l, nodes), root, inOrder(r, nodes)] if i])
N = int(input().strip())
nodes = []
for i in range(N):
	(l, r) = input().strip().split(' ')
	nodes.append((int(l), int(r)))
T = int(input().strip())
for _ in range(T):
	swapDepth(nodes, 1, 1, int(input().strip()))
	print(inOrder(1, nodes))


import sys
sys.setrecursionlimit(15000)

def inorder(start=1):
	if start == -1:
		return
	inorder(left[start - 1])
	s.append(start)
	inorder(right[start - 1])

def get_depths(n=1, d=1):
	if n == -1:
		return
	depth[n - 1] = d
	d += 1
	get_depths(left[n - 1], d)
	get_depths(right[n - 1], d)
left = []
right = []
N = int(input())
for n in range(N):
	(a, b) = [int(x) for x in input().split()]
	left.append(a)
	right.append(b)
depth = [1] * N
get_depths()
T = int(input())
for t in range(T):
	s = []
	K = int(input())
	for (i, d) in enumerate(depth):
		if d % K == 0:
			(left[i], right[i]) = (right[i], left[i])
	inorder()
	print(' '.join(map(str, s)))


import queue
N = int(input())
Nodes = []
for i in range(N):
	Nodes.append([int(x) - 1 for x in input().split()] + [0])
q = queue.Queue()
q.put(0)
Nodes[0][2] = 1
while not q.empty():
	i = q.get()
	deg = Nodes[i][2]
	if Nodes[i][0] != -2:
		Nodes[Nodes[i][0]][2] = deg + 1
		q.put(Nodes[i][0])
	if Nodes[i][1] != -2:
		Nodes[Nodes[i][1]][2] = deg + 1
		q.put(Nodes[i][1])
T = int(input())
for _ in range(T):
	k = int(input())
	for i in range(N):
		if Nodes[i][2] % k == 0:
			temp = Nodes[i][0]
			Nodes[i][0] = Nodes[i][1]
			Nodes[i][1] = temp
	list = []
	s = queue.LifoQueue()
	current = 0
	while current != -2:
		s.put(current)
		current = Nodes[current][0]
	while not s.empty():
		i = s.get()
		list.append(i + 1)
		current = Nodes[i][1]
		while current != -2:
			s.put(current)
			current = Nodes[current][0]
	print(' '.join(map(str, list)))


from queue import Queue

class Node(object):

	def __init__(self, data=None, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

def swap(node):
	left = node.left
	node.left = node.right
	node.right = left

def add_children(node, children, node_queue):
	left = children[0]
	right = children[1]
	if left != -1:
		left_node = Node(left)
		node.left = left_node
		node_queue.put(left_node)
	if right != -1:
		right_node = Node(right)
		node.right = right_node
		node_queue.put(right_node)

def _inorder(root):
	node_stack = []
	order = []
	curr_node = root
	while node_stack or curr_node:
		if curr_node:
			node_stack.append(curr_node)
			curr_node = curr_node.left
		else:
			curr_node = node_stack.pop()
			order.append(curr_node.data)
			curr_node = curr_node.right
	return order

def inorder_traversal(root):
	order = _inorder(root)
	print(' '.join([str(i) for i in order]))

def swap_nodes(root, depth):
	curr_depth = 1
	nodes_at_curr_depth = []
	nodes_at_curr_depth.append(root)
	while nodes_at_curr_depth:
		nodes_at_next_depth = []
		for n in nodes_at_curr_depth:
			if curr_depth % depth == 0:
				swap(n)
			if n.left:
				nodes_at_next_depth.append(n.left)
			if n.right:
				nodes_at_next_depth.append(n.right)
		nodes_at_curr_depth = nodes_at_next_depth
		curr_depth += 1
num_nodes = int(input().strip())
root = Node(1)
node_queue = Queue()
node_queue.put(root)
for i in range(num_nodes):
	curr_node = node_queue.get()
	children = [int(i) for i in input().strip().split(' ')]
	add_children(curr_node, children, node_queue)
num_swaps = int(input().strip())
for i in range(num_swaps):
	depth = int(input().strip())
	swap_nodes(root, depth)
	inorder_traversal(root)


import sys

class TreeNode:

	def __init__(self, data=1, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

	def swapNode(self, k, i=1):
		if i % k == 0:
			(self.left, self.right) = (self.right, self.left)
		if self.left is not None:
			self.left.swapNode(k, i + 1)
		if self.right is not None:
			self.right.swapNode(k, i + 1)

	def toList(self):
		lstr = [str(self.data)]
		if self.left is not None:
			lstr = self.left.toList() + lstr
		if self.right is not None:
			lstr = lstr + self.right.toList()
		return lstr

def buildTree(arrIdx, i=1):
	if i == -1:
		return None
	return TreeNode(i, buildTree(arrIdx, arrIdx[i - 1][0]), buildTree(arrIdx, arrIdx[i - 1][1]))

def main():
	sys.setrecursionlimit(15000)
	n = int(input())
	arrIdx = [None] * n
	for i in range(n):
		(l, r) = input().split()
		(l, r) = (int(l), int(r))
		arrIdx[i] = (l, r)
	tree = buildTree(arrIdx)
	t = int(input())
	for i in range(t):
		k = int(input())
		tree.swapNode(k)
		print(' '.join(tree.toList()))
	return 0
exit(main())


import sys
sys.setrecursionlimit(1500)

def inorder(n, nodes):
	(left, right) = nodes[n]
	r = []
	if left != -1:
		r.append(inorder(left, nodes))
	r.append(str(n))
	if right != -1:
		r.append(inorder(right, nodes))
	return ' '.join(r)

def swap(k, n, d, nodes):
	if d % k == 0:
		temp = nodes[n][0]
		nodes[n][0] = nodes[n][1]
		nodes[n][1] = temp
	(left, right) = nodes[n]
	if left != -1:
		swap(k, left, d + 1, nodes)
	if right != -1:
		swap(k, right, d + 1, nodes)
n = int(input())
nodes = {}
for i in range(n):
	(left, right) = map(int, input().split())
	nodes[i + 1] = [left, right]
t = int(input())
for _ in range(t):
	k = int(input())
	swap(k, 1, 1, nodes)
	print(inorder(1, nodes))


class Node:

	def __init__(self, data, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

	def __str__(self):
		return 'Node(%s)' % self.data

def read_nodes():
	root = Node(1)
	q = [root]

	def read_node(n):
		if n != -1:
			node = Node(n)
			q.append(node)
			return node
	while len(q) > 0:
		(node, *q) = q
		(l, r) = map(int, input().split(' '))
		node.left = read_node(l)
		node.right = read_node(r)
	return root

def swap_level(root, top_lvl):
	st = [[root, top_lvl, 1]]
	while len(st) > 0:
		(node, lvl, cur_lvl) = st.pop()
		next_lvl = lvl
		if lvl == cur_lvl:
			l = node.left
			node.left = node.right
			node.right = l
			next_lvl += top_lvl
		if node.left:
			st.append([node.left, next_lvl, cur_lvl + 1])
		if node.right:
			st.append([node.right, next_lvl, cur_lvl + 1])

def print_tree(root):
	st = [[root, 'left']]
	l = []
	while len(st) > 0:
		(node, dir) = st.pop()
		if dir == 'left':
			st.append([node, 'right'])
			st.append([node, ''])
			if node.left:
				st.append([node.left, 'left'])
		elif dir == 'right':
			if node.right:
				st.append([node.right, 'left'])
		else:
			l.append(node.data)
	print(' '.join([str(n) for n in l]))

def main():
	n = int(input())
	root = read_nodes()
	k = int(input())
	for i in range(k):
		swap_level(root, int(input()))
		print_tree(root)
main()


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, key):
		self.key = key
		self.left = None
		self.right = None
		self.depth = 1

def swap(node):
	(node.left, node.right) = (node.right, node.left)

def pre_order_swap(root, d, k):
	if root is not None:
		if d % k == 0:
			swap(root)
		pre_order_swap(root.left, d + 1, k)
		pre_order_swap(root.right, d + 1, k)

def in_order_print(root):
	if root is not None:
		in_order_print(root.left)
		print(root.key, end=' ')
		in_order_print(root.right)
N = int(input())
root = Node(1)
nodes = [root]
for i in range(0, N):
	(a, b) = [int(x) for x in input().split()]
	if a != -1:
		l = len(nodes)
		n1 = Node(a)
		nodes[i].left = n1
		nodes.append(n1)
	if b != -1:
		l = len(nodes)
		n2 = Node(b)
		nodes[i].right = n2
		nodes.append(n2)
T = int(input())
K = []
for i in range(0, T):
	k = int(input())
	K.append(k)
for k in K:
	pre_order_swap(root, 1, k)
	in_order_print(root)
	print()


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, data, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

def parse_tree(n):
	nodes = [Node(1)]
	for i in range(n):
		(l, r) = map(int, input().split())
		if l != -1:
			nodes[i].left = Node(l)
			nodes.append(nodes[i].left)
		if r != -1:
			nodes[i].right = Node(r)
			nodes.append(nodes[i].right)
	return nodes[0]

def inorder(tree):
	if not tree:
		return
	inorder(tree.left)
	print(tree.data, end=' ')
	inorder(tree.right)

def invert(tree, level):

	def invert_(tree, level, current_level):
		if not tree:
			return
		if current_level % level == 0:
			(tree.left, tree.right) = (tree.right, tree.left)
		if tree.left:
			invert_(tree.left, level, current_level + 1)
		if tree.right:
			invert_(tree.right, level, current_level + 1)
	invert_(tree, level, 1)
n = int(input())
tree = parse_tree(n)
t = int(input())
for _ in range(t):
	invert(tree, int(input()))
	inorder(tree)
	print()


class Node:

	def __init__(self, val=None, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right
		self.depth = None

	def __str__(self):
		vals = []
		node = self
		to_process = []
		while node is not None or len(to_process) > 0:
			if node is None:
				node = to_process.pop()
				vals.append(node.val)
				node = node.right
				continue
			if node.left is not None:
				to_process.append(node)
				node = node.left
			else:
				vals.append(node.val)
				node = node.right
		return ' '.join([str(i) for i in vals])

	def swap(self, depth):
		target_depths = [depth * i for i in range(1, 1025)]
		node = self
		depth = 1
		to_swap = []
		to_process = []
		while node is not None or len(to_process) > 0:
			if node is None:
				node = to_process.pop()
				depth = node.depth
				if depth in target_depths:
					to_swap.append(node)
				node = node.right
				depth += 1
				continue
			if node.left is not None:
				node.depth = depth
				to_process.append(node)
				node = node.left
				depth += 1
			else:
				if depth in target_depths:
					to_swap.append(node)
				node = node.right
				depth += 1
		for node in to_swap:
			left_temp = node.left
			node.left = node.right
			node.right = left_temp
root = Node(1)
to_process = [root]
for n in range(int(input())):
	node = to_process.pop(0)
	vals = [int(i) for i in input().split()]
	if vals[0] != -1:
		node.left = Node(vals[0])
		to_process.append(node.left)
	if vals[1] != -1:
		node.right = Node(vals[1])
		to_process.append(node.right)
for swp in range(int(input())):
	k = int(input())
	root.swap(k)
	print(root)


import sys
sys.setrecursionlimit(2000)

class TreeNode:

	def __init__(self, data=None):
		self.right = None
		self.left = None
		self.parent = None
		self.data = data
		self.depth = 1

def in_order(root):
	if root.left:
		in_order(root.left)
	print(root.data, end=' ')
	if root.right:
		in_order(root.right)

def swap_children(node):
	(node.left, node.right) = (node.right, node.left)
n = int(input().strip())
d = 0
nodes = [TreeNode(i + 1) for i in range(0, n)]
for i in range(0, n):
	children = [int(x) for x in input().strip().split()]
	if children[0] != -1:
		nodes[i].left = nodes[children[0] - 1]
		nodes[children[0] - 1].parent = nodes[i]
		nodes[children[0] - 1].depth = nodes[i].depth + 1
	if children[1] != -1:
		nodes[i].right = nodes[children[1] - 1]
		nodes[children[1] - 1].parent = nodes[i]
		nodes[children[1] - 1].depth = nodes[i].depth + 1
t = int(input().strip())
for i in range(0, t):
	k = int(input().strip())
	x = list(filter(lambda x: x.depth % k == 0, nodes))
	for u in x:
		swap_children(u)
	in_order(nodes[0])
	print('')


import sys
sys.setrecursionlimit(1500)

def inorder(root):
	if not root:
		return
	inorder(root[1])
	print(root[0], end=' ')
	inorder(root[2])

def swapchildren(root, K, currentlevel):
	if not root:
		return
	if currentlevel % K == 0:
		(root[1], root[2]) = (root[2], root[1])
	swapchildren(root[1], K, currentlevel + 1)
	swapchildren(root[2], K, currentlevel + 1)
N = int(input())
nodes = [[i + 1, None, None] for i in range(N)]
for i in range(N):
	(left, right) = [int(x) for x in input().split()]
	if left != -1:
		nodes[i][1] = nodes[left - 1]
	if right != -1:
		nodes[i][2] = nodes[right - 1]
T = int(input())
for _ in range(T):
	K = int(input())
	swapchildren(nodes[0], K, 1)
	inorder(nodes[0])
	print()


l = []
depths = []
import sys
sys.setrecursionlimit(2048)

def inOrder(root):
	if root == -1:
		return
	inOrder(l[root].left)
	print(root, end=' ')
	inOrder(l[root].right)

class node:

	def __init__(self, val, left, right):
		self.left = left
		self.right = right
		self.val = val
l = [0 for i in range(int(input()) + 1)]
depths = [1 for i in l]
for i in range(1, len(l)):
	l[i] = [int(x) for x in input().split()]
	l[i] = node(i, l[i][0], l[i][1])
	if l[i].right != -1:
		depths[l[i].right] = depths[l[i].val] + 1
	if l[i].left != -1:
		depths[l[i].left] = depths[l[i].val] + 1
for i in range(int(input())):
	j = int(input())
	for c in range(1, len(l)):
		if depths[c] % j == 0:
			(l[c].left, l[c].right) = (l[c].right, l[c].left)
	inOrder(1)
	print()


def main():
	n = int(input())
	node_to_children = {}
	node_to_depth = {1: 1}
	for i in range(1, n + 1):
		[l, r] = list(map(int, input().split()))
		node_to_children[i] = [l, r]
		depth_of_i = node_to_depth[i]
		node_to_depth[l] = depth_of_i + 1
		node_to_depth[r] = depth_of_i + 1
	node_to_depth.pop(-1)
	depth_to_nodes = {}
	max_depth = 1
	for node in node_to_depth.keys():
		if node_to_depth[node] > max_depth:
			max_depth = node_to_depth[node]
		if node_to_depth[node] in depth_to_nodes:
			depth_to_nodes[node_to_depth[node]].append(node)
		else:
			depth_to_nodes[node_to_depth[node]] = [node]
	result_list = find_inorder_of_swaped_nodes(node_to_children, depth_to_nodes, max_depth)
	for each_list in result_list:
		for node in each_list:
			print(node, end=' ')
		print()

def find_inorder_of_swaped_nodes(node_to_children, depth_to_nodes, max_depth):
	t = int(input())
	result_list = []
	for m in range(t):
		k = int(input())
		i = 1
		while k * i < max_depth:
			depth = i * k
			nodes_at_depth = depth_to_nodes[depth]
			for node in nodes_at_depth:
				[l, r] = node_to_children[node]
				node_to_children[node] = [r, l]
			i += 1
		result_list.append(find_inorder_iteratively(1, node_to_children))
	return result_list

def find_inorder_iteratively(root, node_to_children):
	node_to_parent = {}
	for node in node_to_children.keys():
		node_to_parent[node_to_children[node][0]] = node
		node_to_parent[node_to_children[node][1]] = node
	node_to_parent.pop(-1)
	node_to_parent[1] = -1
	result = []
	if root != -1:
		while node_to_children[root][0] != -1:
			root = node_to_children[root][0]
		while root != -1:
			result.append(root)
			if node_to_children[root][1] != -1:
				root = node_to_children[root][1]
				while node_to_children[root][0] != -1:
					root = node_to_children[root][0]
			else:
				while node_to_parent[root] != -1 and node_to_children[node_to_parent[root]][1] == root:
					root = node_to_parent[root]
				root = node_to_parent[root]
	return result
main()


import sys
sys.setrecursionlimit(15000)

class node:

	def __init__(self, data=0, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

def inorder(root):
	if root != None:
		inorder(root.left)
		if root.data != -1:
			print(root.data, end=' ')
		inorder(root.right)

def swap(luck, t):
	for i in range(1, len(luck)):
		tmp = i * t - 1
		if tmp < len(luck):
			for tnode in luck[tmp]:
				if tnode != None:
					tmp1 = tnode.left
					tnode.left = tnode.right
					tnode.right = tmp1
	inorder(luck[0][0])
	print()
root = node()
root.data = 1
n = int(input())
err = 0
if n >= 1 and n <= 1024:
	lookup = [list() for i in range(0, n + 1)]
	lookup[0].append(root)
	i = 0
	for index in range(0, len(lookup) - 1):
		for tnode in lookup[index]:
			if i < n:
				(a, b) = map(int, input().split())
				i += 1
				nleft = node(a, None, None)
				nright = node(b, None, None)
				if a != -1:
					tnode.left = nleft
					lookup[index + 1].append(nleft)
				if b != -1:
					tnode.right = nright
					lookup[index + 1].append(nright)
				if a != -1 and (a < 2 or a > n):
					err = 1
				if b != -1 and (b < 2 or b > n):
					err = 1
	if err == 0:
		t = int(input())
		A = []
		if t >= 1 and t <= 100:
			for idx in range(0, t):
				tmp = int(input())
				if tmp < 1 or tmp > n:
					err = 1
				A.append(tmp)
		if err == 0:
			for g in A:
				swap(lookup, g)


import sys
sys.setrecursionlimit(15000)

def main():
	ROOT_NODE = 1
	lines = sys.stdin.read().splitlines()
	N = int(lines[0])
	tree = {}
	for i in list(range(1, N + ROOT_NODE)):
		tree[i] = list(map(int, lines[i].split()))
	depth = int(lines[N + ROOT_NODE])
	for i in list(range(N + ROOT_NODE + 1, N + ROOT_NODE + 1 + depth)):
		swap(tree, ROOT_NODE, int(lines[i]), 1)
		print('')

def swap(tree, node, targetDepth, depth):
	if node == -1:
		return
	if depth % targetDepth == 0:
		temp = tree[node][0]
		tree[node][0] = tree[node][1]
		tree[node][1] = temp
	swap(tree, tree[node][0], targetDepth, depth + 1)
	print(node, end=' ')
	swap(tree, tree[node][1], targetDepth, depth + 1)
main()


def inorder(root):
	if root != -1:
		inorder(L[root][0])
		print(root, end=' ')
		inorder(L[root][1])

def swapNodes(root, K, depth):
	if root == -1:
		return
	if depth % K == 0:
		(L[root][0], L[root][1]) = (L[root][1], L[root][0])
	swapNodes(L[root][0], K, depth + 1)
	swapNodes(L[root][1], K, depth + 1)
import sys
sys.setrecursionlimit(15000)
N = int(input())
L = [0] * (N + 1)
for i in range(1, N + 1):
	L[i] = list(map(int, input().split()))
T = int(input())
for i in range(T):
	K = int(input())
	swapNodes(1, K, 1)
	inorder(1)
	print()


import sys
sys.setrecursionlimit(2000)

class Node:

	def __init__(self, data=None, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

	def traverse(self):
		if self.left:
			self.left.traverse()
		print(self.data, end=' ')
		if self.right:
			self.right.traverse()

	def swap(self, s, l=1):
		x = l % s == 0
		if self.left:
			self.left.swap(s, l + 1)
		if self.right:
			self.right.swap(s, l + 1)
		if x:
			(self.left, self.right) = (self.right, self.left)
root = Node(1)
nodes = [root]
for i in range(int(input())):
	lst = []
	for n in nodes:
		x = [int(i) for i in input().split()]
		if x[0] != -1:
			n.left = Node(x[0])
			lst.append(n.left)
		if x[1] != -1:
			n.right = Node(x[1])
			lst.append(n.right)
	nodes = lst
for i in range(int(input())):
	root.swap(int(input()))
	root.traverse()
	print()


import sys
sys.setrecursionlimit(1046)

class Node:

	def __init__(self):
		self.left = None
		self.right = None

def InOrder(tree, index=0):
	if tree[index].left:
		InOrder(tree, tree[index].left)
	print(index + 1, end=' ')
	if tree[index].right:
		InOrder(tree, tree[index].right)

def NextLevel(tree, curLevel):
	result = []
	for i in curLevel:
		if tree[i].left:
			result += [tree[i].left]
		if tree[i].right:
			result += [tree[i].right]
	return result
tree = []
for _ in range(int(input())):
	tree += [Node()]
	(tree[-1].left, tree[-1].right) = map(lambda i: None if int(i) == -1 else int(i) - 1, input().split())
for _1 in range(int(input())):
	levelNodes = [0]
	K = int(input())
	while len(levelNodes):
		for _2 in range(K - 1):
			levelNodes = NextLevel(tree, levelNodes)
		for i in levelNodes:
			(tree[i].left, tree[i].right) = (tree[i].right, tree[i].left)
		levelNodes = NextLevel(tree, levelNodes)
	InOrder(tree)
	print('')


import sys
from collections import deque

class Node:

	def __init__(self, data, left, right):
		self.data = data
		self.left = left if left > 0 else None
		self.right = right if right > 0 else None
nodes = [Node(i + 1, *map(int, input().split())) for i in range(int(input()))]
for node in nodes:
	if node.left:
		node.left = nodes[node.left - 1]
	if node.right:
		node.right = nodes[node.right - 1]
sys.setrecursionlimit(5000)

def inorder(root):
	if root:
		inorder(root.left)
		print(root.data, end=' ')
		inorder(root.right)
for _ in range(int(input())):
	K = int(input())
	d = deque()
	d.append((1, nodes[0]))
	while len(d):
		(h, node) = d.pop()
		if not h % K:
			(node.left, node.right) = (node.right, node.left)
		if node.left:
			d.append((h + 1, node.left))
		if node.right:
			d.append((h + 1, node.right))
	inorder(nodes[0])
	print()


class Node:

	def __init__(self, value, depth):
		self.value = str(value)
		self.left = None
		self.right = None
		self.depth = depth

def swap_nodes(nodes, level):
	for node in nodes:
		if node.depth % level == 0:
			hold = node.left
			node.left = node.right
			node.right = hold

def create_tree(nodes):
	for i in range(tree_input_count):
		node = nodes[i]
		(x, y) = input().split(' ')
		if x != '-1':
			node.left = Node(x, node.depth + 1)
			nodes.append(node.left)
		if y != '-1':
			node.right = Node(y, node.depth + 1)
			nodes.append(node.right)
	return nodes

def print_tree(node):
	result = []
	stack = []
	while len(stack) or node:
		if node:
			stack.append(node)
			node = node.left
		else:
			node = stack.pop()
			result.append(str(node.value))
			node = node.right
	print(' '.join(result))
tree_input_count = int(input())
root = Node(1, 1)
nodes = create_tree([root])
comands_count = int(input())
commands = []
for x in range(comands_count):
	commands.append(int(input()))
for command in commands:
	swap_nodes(nodes, command)
	print_tree(nodes[0])


import sys

def swap(cur, depth, tree, K):
	if cur not in tree:
		return
	left = tree[cur][0]
	right = tree[cur][1]
	if depth % K == 0:
		tree[cur] = [right, left]
	if left != -1:
		swap(left, depth + 1, tree, K)
	if right != -1:
		swap(right, depth + 1, tree, K)

def inorder(cur, tree):
	if cur not in tree:
		return
	s = ''
	if tree[cur][0] != -1:
		s += inorder(tree[cur][0], tree) + ' '
	s += str(cur)
	if tree[cur][1] != -1:
		s += ' ' + inorder(tree[cur][1], tree)
	return s
sys.setrecursionlimit(2000)
N = int(input().strip())
tree = {}
for i in range(N):
	(left, right) = map(int, input().strip().split())
	tree[i + 1] = [left, right]
T = int(input().strip())
for _ in range(T):
	swap(1, 1, tree, int(input().strip()))
	print(inorder(1, tree))


class node:

	def __init__(self, data, left, right):
		self.data = data
		self.left = left
		self.right = right

def findNode(root, i):
	if root is not None:
		if root.data == i:
			return root
		else:
			result = findNode(root.left, i)
			if result is None:
				result = findNode(root.right, i)
			return result
	else:
		return None

def heightOfTree(root):
	if root is not None:
		lh = 1 + heightOfTree(root.left)
		rh = 1 + heightOfTree(root.right)
		return lh if lh > rh else rh
	else:
		return 0

def swapSubTree(current):
	temp = current.left
	current.left = current.right
	current.right = temp

def inOrderPrint(root):
	if root != None:
		inOrderPrint(root.left)
		print(root.data, end=' ')
		inOrderPrint(root.right)

def parseAndSwap(root, depth):
	if root is not None:
		if depth == 1:
			swapSubTree(root)
			return
		else:
			parseAndSwap(root.left, depth - 1)
			parseAndSwap(root.right, depth - 1)

def addChildren(parent, a, b):
	if a == -1:
		parent.left = None
	else:
		parent.left = node(a, None, None)
	if b == -1:
		parent.right = None
	else:
		parent.right = node(b, None, None)
import sys
sys.setrecursionlimit(15000)
root = node
root.data = 1
for i in range(int(input())):
	l = [int(i) for i in input().split()]
	current = findNode(root, i + 1)
	if current != None:
		addChildren(current, l[0], l[1])
height = heightOfTree(root)
for i in range(int(input())):
	K = int(input())
	j = 1
	while j * K <= height:
		parseAndSwap(root, j * K)
		j = j + 1
	inOrderPrint(root)
	print('')


import math

class Node:

	def __init__(self, data, left, right):
		self.data = data
		self.right = right
		self.left = left

def inOrder(root):
	stack = [(False, root)]
	acc = []
	while stack:
		(flag, val) = stack.pop()
		if val:
			if not flag:
				stack.append((False, val.right))
				stack.append((True, val))
				stack.append((False, val.left))
			else:
				print(val.data, end=' ')

def maxDepth(root):
	if not root:
		return 0
	(stack, level) = ([root], 1)
	while stack:
		curr_num_nodes = len(stack)
		next_nodes = []
		while curr_num_nodes > 0:
			curr_num_nodes -= 1
			node = stack.pop()
			if node.left:
				next_nodes.append(node.left)
			if node.right:
				next_nodes.append(node.right)
		if next_nodes:
			level += 1
		stack = next_nodes
	return level
levels = int(input())
root = [Node(1, None, None)]
for i in range(levels):
	st = input().split(' ')
	a = int(st[0])
	b = int(st[1])
	if a != -1:
		root[i].left = Node(a, None, None)
		root.append(root[i].left)
	if b != -1:
		root[i].right = Node(b, None, None)
		root.append(root[i].right)
depth = maxDepth(root[0])
numSwaps = int(input())
for i in range(numSwaps):
	swapDepth = int(input())
	itr = swapDepth
	j = 1
	while itr <= depth:
		arr = [[root[0]]]
		k = 0
		while k < itr - 1 and len(arr) > 0:
			lenn = len(arr[0])
			if lenn > 0:
				arr.append([])
			for m in range(lenn):
				if arr[0][m].left != None:
					arr[1].append(arr[0][m].left)
				if arr[0][m].right != None:
					arr[1].append(arr[0][m].right)
			arr.pop(0)
			k += 1
		for e in arr:
			for ii in range(len(e)):
				t = e[ii].left
				e[ii].left = e[ii].right
				e[ii].right = t
		j += 1
		itr = swapDepth * j
	inOrder(root[0])
	print()


class Tree:

	def __init__(self, node_num, left=None, right=None, parent=None):
		self.node_num = node_num
		self.left = left
		self.right = right
		self.parent = parent

def print_inorder(root):
	stack = []
	curr = root
	is_done = 0
	while not is_done:
		if curr is not None:
			stack.append(curr)
			curr = curr.left
		elif len(stack) > 0:
			curr = stack.pop()
			print(str(curr.node_num) + ' ', end='')
			curr = curr.right
		else:
			is_done = 1

def swap(node, k, n):
	if node == None:
		return
	if node.depth == k * n:
		tmp = node.left
		node.left = node.right
		node.right = tmp
		swap(node.left, k, n + 1)
		swap(node.right, k, n + 1)
	else:
		swap(node.left, k, n)
		swap(node.right, k, n)

def swap_iter(nodes, k):
	for (t, l, r) in nodes:
		if t.depth % k == 0:
			tmp = t.left
			t.left = t.right
			t.right = tmp
n_nodes = int(input())
tree_nodes = []
for i in range(n_nodes):
	(l, r) = map(int, input().split())
	tree_nodes.append((Tree(i + 1), l, r))
if len(tree_nodes) > 1:
	tree_nodes[0][0].depth = 1
for (t, l, r) in tree_nodes:
	if l == -1:
		t.left = None
	else:
		t.left = tree_nodes[l - 1][0]
		t.left.depth = t.depth + 1
	if r == -1:
		t.right = None
	else:
		t.right = tree_nodes[r - 1][0]
		t.right.depth = t.depth + 1
root = tree_nodes[0][0]
n_swaps = int(input())
for _ in range(n_swaps):
	k = int(input())
	swap_iter(tree_nodes, k)
	print_inorder(root)
	print()


import sys
sys.setrecursionlimit(15000)

class Node(object):

	def __init__(self, data, left=None, right=None, parent=None, depth=None):
		self.data = data
		self.left = left
		self.right = right
		self.parent = parent
		self.depth = depth

	def swap_children(self):
		(self.left, self.right) = (self.right, self.left)

	def set_depths(self, depth):
		self.depth = depth
		if self.left is not None:
			self.left.set_depths(depth + 1)
		if self.right is not None:
			self.right.set_depths(depth + 1)

def inorder_print(c):
	if c:
		inorder_print(c.left)
		print(c.data, end=' ')
		inorder_print(c.right)

def find_root(nodes):
	for node in nodes:
		if node.parent is None:
			return node
	return None

def main():
	n = int(input())
	nodes = [Node(i + 1) for i in range(n)]
	for i in range(n):
		(a, b) = (int(x) for x in input().split())
		if a != -1:
			nodes[i].left = nodes[a - 1]
			nodes[a - 1].parent = nodes[i]
		if b != -1:
			nodes[i].right = nodes[b - 1]
			nodes[b - 1].parent = nodes[i]
	root = find_root(nodes)
	root.set_depths(1)
	for _ in range(int(input())):
		k = int(input())
		depth = n + 1
		while depth > 1:
			depth -= 1
			if depth % k == 0:
				for node in nodes:
					if node.depth == depth:
						node.swap_children()
		inorder_print(root)
		print()
main()


import sys
sys.setrecursionlimit(15000)
N = int(sys.stdin.readline())
adj = {}
for x in range(1, N + 1):
	(left, right) = [int(i) for i in sys.stdin.readline().split()]
	adj[x] = (left, right)
T = int(sys.stdin.readline())
swaps = [None] * T
for x in range(T):
	swaps[x] = int(sys.stdin.readline())

def walk(idx, K, depth=1, passn=1):
	if idx == -1:
		return
	(left, right) = adj[idx]
	do_swap = False
	for k in K[:passn]:
		swap_here = depth % k == 0
		do_swap = do_swap ^ swap_here
	if do_swap:
		walk(right, K, depth + 1, passn)
		print(idx, end=' ')
		walk(left, K, depth + 1, passn)
	else:
		walk(left, K, depth + 1, passn)
		print(idx, end=' ')
		walk(right, K, depth + 1, passn)
passn = 0
for k in swaps:
	passn += 1
	walk(1, swaps, passn=passn)
	print('')


import sys
sys.setrecursionlimit(2000)

class Node:

	def __init__(self, data=-1, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

def do_swap(tree, k, h=1):
	if not tree:
		return
	if h % k == 0:
		(tree.left, tree.right) = (tree.right, tree.left)
	do_swap(tree.left, k, h + 1)
	do_swap(tree.right, k, h + 1)

def inorder_print(tree):
	if not tree:
		return
	inorder_print(tree.left)
	print(tree.data, end=' ')
	inorder_print(tree.right)
n = int(input())
arr = [Node(i + 1) for i in range(n)]
for i in range(n):
	(a, b) = [int(x) for x in input().split()]
	node = arr[i]
	if a != -1:
		node.left = arr[a - 1]
	if b != -1:
		node.right = arr[b - 1]
t = int(input())
for _ in range(t):
	k = int(input())
	do_swap(arr[0], k)
	inorder_print(arr[0])
	print()


import sys
sys.setrecursionlimit(2048)
nodes = list((list((int(s) for s in input().split(' '))) for i in range(0, int(input()))))
swaps = list(([int(input())] for i in range(0, int(input()))))

class Node:
	data = None
	left = None
	right = None

	def __init__(self, data):
		self.data = data

	def set_children(self, data):
		if data[0] >= 0:
			self.left = Node(data[0])
		if data[1] >= 0:
			self.right = Node(data[1])

	def swap(self):
		temp = self.left
		self.left = self.right
		self.right = temp

class BinaryTree:
	root = Node(1)

	def __init__(self, data):
		i = 0

		def cb(node, depth):
			nonlocal i
			node.set_children(data[i])
			i += 1
		while i < len(data):
			self.inorder_traversal(cb, self.get_max_depth())

	def get_max_depth(self):
		max_depth = 1

		def cb(node, depth):
			nonlocal max_depth
			max_depth = max(max_depth, depth)
		self.inorder_traversal(cb)
		return max_depth

	def inorder_traversal(self, cb, at_depth=None):

		def traverse(node, depth):
			if node:
				traverse(node.left, depth + 1)
				if at_depth is None or at_depth == depth:
					cb(node, depth)
				traverse(node.right, depth + 1)
		traverse(self.root, 1)

	def __str__(self):
		datas = list()
		self.inorder_traversal(lambda node, depth: datas.append(str(node.data)))
		return ' '.join(datas)
tree = BinaryTree(nodes)
max_depth = tree.get_max_depth()
for i in range(0, len(swaps)):
	swap = swaps[i]
	m = 1
	while swap[len(swap) - 1] < max_depth:
		m += 1
		d = swap[0] * m
		if d <= max_depth:
			swap.append(d)
		else:
			break

	def cb(node, depth):
		if depth in swap:
			node.swap()
	for j in range(0, len(swap)):
		tree.inorder_traversal(lambda node, depth: node.swap(), swap[j])
	print(tree)


import sys
sys.setrecursionlimit(1500)
N = int(input())
(left, right) = ([None], [None])
for _ in range(N):
	(l, r) = [int(i) for i in input().strip().split()]
	left.append(l)
	right.append(r)
T = int(input())
k_vals = []
for _ in range(T):
	k_vals.append(int(input()))
depths = [0] * (len(left) + len(right))

def calculate_depths(curr, depth):
	depths[curr] = depth
	if left[curr] > 0:
		calculate_depths(left[curr], depth + 1)
	if right[curr] > 0:
		calculate_depths(right[curr], depth + 1)

def print_tree_inorder(curr):
	if left[curr] > 0:
		print_tree_inorder(left[curr])
	print(curr, end=' ')
	if right[curr] > 0:
		print_tree_inorder(right[curr])

def swap(i, j):
	temp = left[i]
	left[i] = right[j]
	right[j] = temp

def handle_swap_queries(queries):
	for k in k_vals:
		for i in range(1, N):
			if depths[i] % k == 0:
				swap(i, i)
		print_tree_inorder(1)
		print()
calculate_depths(1, 1)
handle_swap_queries(k_vals)


from collections import deque
num_nodes = 0

class node(object):

	def __init__(self, data):
		self.data = data
		self.right = None
		self.left = None

	def add_left(self, node):
		self.left = node

	def add_right(self, node):
		self.right = node

	def swap(self):
		temp = self.right
		self.right = self.left
		self.left = temp

	def swap_level2(self, node, level, prev_level):
		if level == 0:
			return
		if prev_level + 1 < level:
			if node.left:
				node.swap_level(node.left, level, prev_level + 1)
			if node.right:
				node.swap_level(node.right, level, prev_level + 1)
		else:
			node.swap()

	def swap_level(self, node, level, prev_level):
		if level == 0:
			return
		if prev_level == 0:
			next_level = [node]
			this_levl = []
		while prev_level + 1 < level:
			this_level = next_level
			next_level = []
			for n in this_level:
				if n.left:
					next_level.append(n.left)
				if n.right:
					next_level.append(n.right)
			prev_level += 1
		this_level = next_level
		next_level = []
		for n in this_level:
			n.swap()

	def print_tree(self, node):
		if not node:
			return
		current = node
		while current:
			if current.left is None:
				print(current.data, end=' ')
				current = current.right
			else:
				pre = current.left
				while pre.right and pre.right != current:
					pre = pre.right
				if not pre.right:
					pre.right = current
					current = current.left
				else:
					pre.right = None
					print(current.data, end=' ')
					current = current.right

	def print_tree2(self, node):
		if node.left:
			node.print_tree(node.left)
		print(node.data, end=' ')
		if node.right:
			node.print_tree(node.right)
num_nodes = int(input())
root = node(1)
n = root
nodes = deque([n])
nodes2 = deque()
levels = 1
for i in range(num_nodes):
	(l, r) = map(int, input().split(' '))
	n = nodes.popleft()
	if l != -1:
		k = node(l)
		n.add_left(k)
		nodes2.append(k)
	if r != -1:
		k = node(r)
		n.add_right(k)
		nodes2.append(k)
	if len(nodes) == 0:
		levels += 1
		nodes = nodes2
		nodes2 = deque()
num_swaps = int(input())
for i in range(num_swaps):
	s = int(input())
	s1 = s
	count = 2
	while s1 < levels:
		root.swap_level(root, s1, 0)
		s1 = s * count
		count += 1
	root.print_tree(root)
	print('')


import sys
sys.setrecursionlimit(15000)

class Node(object):

	def __init__(self, data=None, depth=None, left=None, right=None):
		self.depth = depth
		self.data = data
		self.left = left
		self.right = right

def inorder_print(root):
	if root:
		inorder_print(root.left)
		print(root.data, end=' ')
		inorder_print(root.right)

def swap_nodes(node, depth):
	if node:
		if node.depth % depth == 0:
			tmp = node.left
			node.left = node.right
			node.right = tmp
		swap_nodes(node.left, depth)
		swap_nodes(node.right, depth)
n = int(input())
root = Node(1, 1)
current = None
queue = [root]
head = root
count = 1
for _ in range(1, n + 1):
	if queue:
		current = queue.pop(0)
	(left, right) = map(int, input().split(' '))
	if left != -1:
		current.left = Node(left, depth=current.depth + 1)
		queue.append(current.left)
	if right != -1:
		current.right = Node(right, depth=current.depth + 1)
		queue.append(current.right)
t = int(input())
for _ in range(t):
	k = int(input())
	root = head
	swap_nodes(root, k)
	inorder_print(head)
	print()


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, value, left=None, right=None):
		self.value = value
		self.left = left
		self.right = right

	def height(self):
		if self.value == -1:
			return 0
		else:
			l = self.left.height() + 1
			r = self.right.height() + 1
			if l >= r:
				return l
			else:
				return r

	def insert(self, value):
		if value > self.value:
			if self.right is None:
				self.right = Node(value)
			else:
				self.right.insert(value)
		elif self.left is None:
			self.left = Node(value)
		else:
			self.left.insert(value)

	def insertLeft(self, value):
		self.left = Node(value)

	def insertRight(self, value):
		self.right = Node(value)

	def swapLevel(self, level):
		if self.value == -1:
			return
		if level == 1:
			self.swap()
		else:
			self.left.swapLevel(level - 1)
			self.right.swapLevel(level - 1)

	def swap(self):
		tmp = self.left
		self.left = self.right
		self.right = tmp

	def value(self):
		return self.value

	def left(self):
		return self.left

	def right(self):
		return self.right

	def printTree(self):
		if self.left is not None:
			self.left.printTree()
		if self.value != -1:
			sys.stdout.write(str(self.value) + ' ')
		if self.right is not None:
			self.right.printTree()

def insertAtLevel(node, level, count):
	if node.value == -1:
		return count
	if level == 1:
		sin = input().split()
		l = int(sin[0])
		r = int(sin[1])
		node.insertLeft(l)
		node.insertRight(r)
		count += 1
		return count
	else:
		count = insertAtLevel(node.left, level - 1, count)
		return insertAtLevel(node.right, level - 1, count)

def main():
	node = Node(1)
	level = 1
	N = int(input().strip())
	count = 0
	while count < N:
		count = insertAtLevel(node, level, count)
		level += 1
	maxHeight = node.height()
	S = int(input().strip())
	for x in range(S):
		k = int(input().strip())
		l = k
		while l <= maxHeight:
			node.swapLevel(l)
			l += k
		node.printTree()
		print()
main()


class Node:

	def __init__(self, data=None, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

def create_Tree():
	n = int(input())
	root = Node(1)
	queue = [root]
	dict_depth = {1: [root]}
	for i in range(n):
		(left, right) = [int(data) for data in input().strip().split()]
		value = []
		if left != -1:
			queue[0].left = Node(left)
			queue.append(queue[0].left)
			value.append(queue[0].left)
		if right != -1:
			queue[0].right = Node(right)
			queue.append(queue[0].right)
			value.append(queue[0].right)
		depth = tree_depth(root)
		if depth in dict_depth:
			dict_depth[depth] += value
		else:
			dict_depth.update({depth: value})
		queue.pop(0)
	return (root, dict_depth)

def tree_depth(root):
	if root != None:
		height_L = 0
		height_R = 0
		try:
			if root.left != None:
				height_L = tree_depth(root.left)
		except:
			if root.left != None:
				height_L = tree_depth(root.left)
		try:
			if root.right != None:
				height_R = tree_depth(root.right)
		except:
			if root.right != None:
				height_R = tree_depth(root.right)
		return max(height_L, height_R) + 1
	else:
		return 0

def swap(queue):
	for height in queue:
		for h in height:
			(h.left, h.right) = (h.right, h.left)

def inOrder(root):
	if root != None:
		try:
			inOrder(root.left)
		except:
			inOrder(root.left)
		print(root.data, end=' ')
		try:
			inOrder(root.right)
		except:
			inOrder(root.right)
(root, dict_depth) = create_Tree()
depth = max(dict_depth)
q = int(input())
for i in range(q):
	k = int(input())
	queue = []
	height = [j * k for j in range(1, depth) if j * k < depth]
	for h in height:
		queue.append(dict_depth[h])
	swap(queue)
	inOrder(root)
	print()


import sys
sys.setrecursionlimit(1 << 20)

class Node(object):

	def __init__(self, id, left=None, right=None):
		self.id = id
		self.left = left
		self.right = right

	def swapChilds(self):
		(self.left, self.right) = (self.right, self.left)

	def stringInOrder(self):
		result = ''
		if self.left != None:
			result += self.left.stringInOrder()
		result += '{} '.format(self.id)
		if self.right != None:
			result += self.right.stringInOrder()
		return result

	def dfsSwap(self, depth, k):
		if depth % k == 0:
			self.swapChilds()
		if self.left != None:
			self.left.dfsSwap(depth + 1, k)
		if self.right != None:
			self.right.dfsSwap(depth + 1, k)
N = int(input())
node_list = [Node(i) for i in range(1, N + 1)]
for i in range(0, N):
	(a, b) = map(int, input().split(' '))
	if a != -1:
		node_list[i].left = node_list[a - 1]
	if b != -1:
		node_list[i].right = node_list[b - 1]
swap_tasks_count = int(input())
for _ in range(swap_tasks_count):
	k = int(input())
	node_list[0].dfsSwap(1, k)
	print(node_list[0].stringInOrder())


import sys
sys.setrecursionlimit(2000)

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def inorder(root):
	if root is None:
		return
	inorder(root.left)
	print(root.data, end=' ')
	inorder(root.right)

def rotate(h, H, root):
	if root is None:
		return
	h -= 1
	if h == 0:
		(root.left, root.right) = (root.right, root.left)
		h = H
	rotate(h, H, root.left)
	rotate(h, H, root.right)

def createTree():
	N = int(input())
	tree = [Node(i) for i in range(N + 1)]
	for i in range(1, N + 1):
		(a, b) = (int(s) for s in input().split(' '))
		if a == -1:
			a = None
		else:
			a = tree[a]
		if b == -1:
			b = None
		else:
			b = tree[b]
		(tree[i].left, tree[i].right) = (a, b)
	return tree[1]
tree = createTree()
for _ in range(int(input())):
	k = int(input())
	rotate(k, k, tree)
	inorder(tree)
	print()


import sys

class Node:

	def __init__(self, data, left, right):
		self.data = data
		self.left = left
		self.right = right

	def swap(self, k, height):
		if height % k == 0:
			tmp = self.left
			self.left = self.right
			self.right = tmp
		if self.left != None:
			self.left.swap(k, height + 1)
		if self.right != None:
			self.right.swap(k, height + 1)

	def inOrder(self):
		if self.left != None:
			self.left.inOrder()
		sys.stdout.write('{} '.format(self.data))
		if self.right != None:
			self.right.inOrder()
tree = Node(1, None, None)
nodes = {1: tree}
n = int(input().strip())
for i in range(1, n + 1):
	(a, b) = map(int, input().strip().split(' '))
	if a != -1:
		nodes[a] = Node(a, None, None)
		nodes[i].left = nodes[a]
	if b != -1:
		nodes[b] = Node(b, None, None)
		nodes[i].right = nodes[b]
t = int(input().strip())
sys.setrecursionlimit(999999)
for i in range(t):
	k = int(input().strip())
	tree.swap(k, 1)
	tree.inOrder()
	sys.stdout.write('\n')


import sys
sys.setrecursionlimit(15000)

class node(object):

	def __init__(self, data=None, left=None, right=None):
		self.left = left
		self.right = right
		self.data = data
reqNodes = []

def inOrder(root):
	if not root:
		return
	inOrder(root.left)
	print(root.data, end=' ')
	inOrder(root.right)

def depthNodes(root, depth, reqDepth):
	if not root:
		return
	if depth % reqDepth == 0:
		reqNodes.append(root)
	depthNodes(root.left, depth + 1, reqDepth)
	depthNodes(root.right, depth + 1, reqDepth)

def constructBinary(nodes):
	if nodes:
		prev = None
		current = None
		queue = []
		root = None
		for i in range(0, nodes + 1):
			if i == 0:
				root = node(data=1)
				prev = None
				queue.append(root)
			else:
				(left, right) = input().split(' ')
				right = int(right)
				left = int(left)
				lnode = None
				rnode = None
				if left != -1:
					lnode = node(data=left)
					queue.append(lnode)
				if right != -1:
					rnode = node(data=right)
					queue.append(rnode)
				current.left = lnode
				current.right = rnode
				prev = current
			if not len(queue):
				break
			current = queue.pop(0)
		return root
	else:
		return None

def main():
	nodes = int(input())
	root = constructBinary(nodes)
	if root:
		TestCaseN = int(input())
		testcases = []
		for i in range(0, TestCaseN):
			testcases.append(int(input()))
		for i in testcases:
			depthNodes(root, 1, i)
			for item in reqNodes:
				right = item.right
				item.right = item.left
				item.left = right
			del reqNodes[:]
			inOrder(root)
			print('')
main()


class Node:

	def __init__(self, data, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

def traverse_tree(root):
	(stack, node) = ([], root)
	while len(stack) > 0 or node is not None:
		if node is not None:
			stack.append(node)
			node = node.left
		else:
			node = stack.pop()
			yield node
			node = node.right

def print_tree(root):
	print(' '.join((str(node.data) for node in traverse_tree(root))))

def swap_subtrees(root, K):
	queue = [(1, root)]
	while len(queue) > 0:
		(depth, node) = queue.pop(0)
		if node is None:
			continue
		queue.append((depth + 1, node.left))
		queue.append((depth + 1, node.right))
		if depth % K == 0:
			(node.left, node.right) = (node.right, node.left)
N = int(input().strip())
nodes = [Node(n + 1) for n in range(N)]
for n in range(N):
	(l, r) = (int(x) - 1 for x in input().strip().split())
	if l >= 0:
		nodes[n].left = nodes[l]
	if r >= 0:
		nodes[n].right = nodes[r]
root = nodes[0]
T = int(input().strip())
for t in range(T):
	K = int(input().strip())
	swap_subtrees(root, K)
	print_tree(root)


from sys import stdin
from queue import Queue
from queue import LifoQueue as Stack

class Tree:

	def __init__(self, data, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

	@classmethod
	def create(cls, lst, parents):
		root = cls(lst[0])
		nodes = [root]
		i = 1
		while i < len(lst):
			left = cls(lst[i]) if lst[i] != -1 else None
			right = cls(lst[i + 1]) if lst[i + 1] != -1 else None
			parent_node = nodes[parents[i]]
			parent_node.left = left
			parent_node.right = right
			nodes.append(left)
			nodes.append(right)
			i += 2
		return root

	def swap(self, k, idx=1):
		q = Queue()
		q.put([self, idx])
		while not q.empty():
			(n, i) = q.get()
			if i % k == 0:
				(n.left, n.right) = (n.right, n.left)
			if n.left:
				q.put([n.left, i + 1])
			if n.right:
				q.put([n.right, i + 1])

	def print_inorder(self):
		s = Stack()
		s.put(self.right)
		s.put(self.data)
		s.put(self.left)
		while not s.empty():
			n = s.get()
			if not n:
				continue
			if isinstance(n, Tree):
				s.put(n.right)
				s.put(n.data)
				s.put(n.left)
			else:
				print(n, end=' ')
		print('')

	def print_preorder(self, end='\n'):
		print(self.data, end=' ')
		if self.left:
			self.left.print_preorder(end='')
		if self.right:
			self.right.print_preorder(end='')
		print(end, end='')
n = int(stdin.readline().strip())
a = [1]
ps = [-1]
p = 0
for i in range(n):
	(x, y) = stdin.readline().strip().split(' ')
	while a[p] == -1:
		p += 1
	a.append(int(x))
	a.append(int(y))
	ps.append(p)
	ps.append(p)
	p += 1
tree = Tree.create(a, ps)
t = int(stdin.readline().strip())
for _ in range(t):
	k = int(stdin.readline().strip())
	tree.swap(k)
	tree.print_inorder()


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, data, height=0, left=None, right=None):
		self.data = data
		self.height = height
		self.left = left
		self.right = right

def InOrderTraversal(root):
	if root == None:
		return
	InOrderTraversal(root.left)
	print(root.data, end=' ')
	InOrderTraversal(root.right)
n = int(input())
nodes = [Node(x + 1) for x in range(n)]
nodes[0].height = 1
root = nodes[0]
for i in range(n):
	(l, r) = input().split()
	(l, r) = (int(l), int(r))
	if l != -1:
		nodes[l - 1].height = nodes[i].height + 1
		nodes[i].left = nodes[l - 1]
	if r != -1:
		nodes[r - 1].height = nodes[i].height + 1
		nodes[i].right = nodes[r - 1]
t = int(input())
for i in range(t):
	k = int(input())
	for node in nodes:
		if node.height % k == 0:
			temp = node.left
			node.left = node.right
			node.right = temp
	InOrderTraversal(root)
	print()


def build_tree(N):
	tree = [[-1 for x in range(4)] for y in range(N)]
	for i in range(N):
		children = input()
		(left, right) = [int(x) for x in children.split(' ')]
		if left != -1:
			tree[i][0] = left - 1
		if right != -1:
			tree[i][1] = right - 1
		if tree[i][0] != -1:
			tree[tree[i][0]][2] = i
		if tree[i][1] != -1:
			tree[tree[i][1]][2] = i
	for i in range(N):
		d = 1
		j = i
		while tree[j][2] != -1:
			d += 1
			j = tree[j][2]
		tree[i][3] = d
	return tree

def inorder(tree):
	i = 0
	result = []
	stack = [0]
	while len(result) < len(tree):
		if tree[i][0] != -1 and tree[i][0] not in result:
			stack.append(i)
			i = tree[i][0]
		else:
			if i not in result:
				result += [i]
			if tree[i][1] != -1 and tree[i][1] not in result:
				stack.append(i)
				i = tree[i][1]
			else:
				i = stack.pop()
	return result

def inorder2(tree, i):
	left = tree[i][0]
	right = tree[i][1]
	result = []
	if left != -1:
		result += inorder(tree, left)
	result += [str(i + 1)]
	if right != -1:
		result += inorder(tree, right)
	return result

def print_tree(tree):
	print(' '.join([str(z + 1) for z in inorder(tree)]))

def swap(tree, D):
	for node in tree:
		if node[3] == D:
			tmp = node[0]
			node[0] = node[1]
			node[1] = tmp
	return tree
N = int(input())
tree = build_tree(N)
T = int(input())
for t in range(T):
	K = int(input())
	for i in range(N):
		swap(tree, (i + 1) * K)
	print_tree(tree)


class Node:

	def __init__(self, i):
		self.data = i
		(self.left, self.right) = (None, None)

def ReadInput():
	numNodes = int(input().strip())
	d = {}
	for i in range(1, numNodes + 1):
		n = Node(i)
		d[i] = n
	for i in range(1, numNodes + 1):
		n = d[i]
		lr = input().strip().split(' ')
		l = int(lr[0])
		r = int(lr[1])
		if l > 0:
			n.left = d[l]
		if r > 0:
			n.right = d[r]
	li = []
	for _ in range(int(input().strip())):
		li.append(int(input().strip()))
	return (d[1], li)

def InorderTraversal(node):
	if node == None:
		return []
	li = []
	cur = node
	st = []
	while True:
		if cur != None:
			st.append(cur)
			cur = cur.left
		elif len(st) > 0:
			cur = st.pop()
			li.append(str(cur.data))
			cur = cur.right
		else:
			break
	return li

def PrintResults(tree, heights):
	if tree == None:
		print('')
		return
	ht = 1
	d = {}
	st = [tree]
	while len(st) > 0:
		d[ht] = st
		ht += 1
		li = []
		for node in st:
			if node.left != None:
				li.append(node.left)
			if node.right != None:
				li.append(node.right)
		st = li
	for height in heights:
		mult = 1
		while height * mult in d:
			for node in d[height * mult]:
				(node.left, node.right) = (node.right, node.left)
			mult += 1
		print(' '.join(InorderTraversal(tree)))
(tree, heights) = ReadInput()
PrintResults(tree, heights)


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, data=0, left=None, right=None, depth=0):
		self.data = data
		self.left = left
		self.right = right
		self.depth = depth

def traverse(current_node):
	if current_node is None:
		return
	else:
		traverse(current_node.left)
		print(current_node.data, end=' ')
		traverse(current_node.right)
n = int(input())
nodes = [Node(data=i + 1) for i in range(n)]
nodes[0].depth = 1
max_depth = 1
for i in range(n):
	(l, r) = [int(x) for x in input().split()]
	if l != -1:
		nodes[i].left = nodes[l - 1]
		new_depth = nodes[i].depth + 1
		nodes[l - 1].depth = new_depth
		if new_depth > max_depth:
			max_depth = new_depth
	if r != -1:
		nodes[i].right = nodes[r - 1]
		new_depth = nodes[i].depth + 1
		nodes[r - 1].depth = new_depth
		if new_depth > max_depth:
			max_depth = new_depth
ops = int(input())
for j in range(ops):
	target_depth = int(input())
	current_depth = target_depth
	current_op = 1
	while current_depth < max_depth:
		for node in nodes:
			if node.depth == current_depth:
				(node.right, node.left) = (node.left, node.right)
		current_op += 1
		current_depth = current_op * target_depth
	traverse(nodes[0])
	print('\n', end='')


import collections
import sys
sys.setrecursionlimit(15000)

def inorderprint(root):
	if not root:
		return
	inorderprint(root.left)
	print(root.val, end=' ')
	inorderprint(root.right)
n = int(input())

class TreeNode(object):

	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None
root = TreeNode(1)
queue = collections.deque([root])
for _ in range(n):
	if queue:
		node = queue.popleft()
	(x, y) = map(int, input().split())
	if x != -1:
		node.left = TreeNode(x)
		queue.append(node.left)
	if y != -1:
		node.right = TreeNode(y)
		queue.append(node.right)

def preorder(root, depth, k):
	if not root:
		return
	if depth % k == 0:
		(root.left, root.right) = (root.right, root.left)
	preorder(root.left, depth + 1, k)
	preorder(root.right, depth + 1, k)
	return
q = int(input())
for _ in range(q):
	k = int(input())
	preorder(root, 1, k)
	inorderprint(root)
	print()


import sys
from collections import deque

class Node(object):

	def __init__(self, data, left, right, level):
		self.data = data
		self.left = left
		self.right = right
		self.level = level

def print_in_order(root):
	dq = deque()
	current = root
	done = False
	while not done:
		if current is not None:
			dq.append(current)
			current = current.left
		elif len(dq) > 0:
			current = dq.pop()
			print(current.data, end=' ')
			current = current.right
		else:
			done = True

def swap(root, level):
	dq = deque([root])
	the_list = []
	while len(dq) > 0:
		node = dq.popleft()
		if node.level < level:
			if node.left is not None:
				dq.append(node.left)
			if node.right is not None:
				dq.append(node.right)
		elif node.level == level:
			the_list.append(node)
		else:
			continue
	for node in the_list:
		tmp = node.left
		node.left = node.right
		node.right = tmp
lines = int(sys.stdin.readline().strip())
root = Node(1, None, None, 1)
dq = deque()
dq.append(root)
node = None
for _ in range(lines):
	node = dq.popleft()
	(data_left, data_right) = [int(x.strip()) for x in sys.stdin.readline().strip().split(' ')]
	if data_left != -1:
		node.left = Node(data_left, None, None, node.level + 1)
		dq.append(node.left)
	if data_right != -1:
		node.right = Node(data_right, None, None, node.level + 1)
		dq.append(node.right)
levels = node.level
lines = int(sys.stdin.readline().strip())
ks = []
for _ in range(lines):
	ks.append(int(sys.stdin.readline().strip()))
for k in ks:
	multiplier = 1
	km = k * multiplier
	while km <= levels:
		swap(root, km)
		multiplier += 1
		km = k * multiplier
	print_in_order(root)
	print()


import sys

class Node:

	def __init__(self, val, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

def traverse(n):
	order = []
	node = n
	nodestack = []

	def stack_left(nd):
		cn = nd
		nds = []
		while cn != None:
			nds.append(cn)
			cn = cn.left
		return nds
	nodestack += stack_left(node)
	while len(nodestack) != 0:
		node = nodestack.pop()
		order.append(node.val)
		if node.right != None:
			nodestack += stack_left(node.right)
	return order
stack = []
N = int(input())
root = Node(1)
stack.append(root)
for i in range(N):
	ns = [int(s) for s in input().split(' ')]
	cnode = stack.pop(0)
	if ns[0] != -1:
		left = Node(ns[0])
		cnode.left = left
		stack.append(left)
	if ns[1] != -1:
		right = Node(ns[1])
		cnode.right = right
		stack.append(right)
swaps = []
T = int(input())
for i in range(T):
	swaps.append(int(input()))

def levelswap(s):
	stack = [root]
	for i in range(1, s):
		if len(stack) == 0:
			return -1
		nstack = []
		while len(stack) != 0:
			node = stack.pop(0)
			if node.left != None:
				nstack.append(node.left)
			if node.right != None:
				nstack.append(node.right)
		stack = nstack
	while len(stack) != 0:
		n = stack.pop()
		tmp = n.left
		n.left = n.right
		n.right = tmp
	return 0
for s in swaps:
	n = 1
	while levelswap(s * n) == 0:
		n += 1
	print(' '.join([str(i) for i in traverse(root)]))


from sys import setrecursionlimit
setrecursionlimit(2000)

def readints():
	return [int(fld) for fld in input().strip().split()]

def readtree():
	ans = [None]
	for _ in range(int(input())):
		ans.append(readints())
	return ans

def swap(nodes, cur, level, repeat):
	if cur == -1:
		return
	if level == 1:
		nodes[cur] = nodes[cur][::-1]
		level = repeat + 1
	swap(nodes, nodes[cur][0], level - 1, repeat)
	swap(nodes, nodes[cur][1], level - 1, repeat)

def traverse(nodes, cur):
	if cur == -1:
		return
	traverse(nodes, nodes[cur][0])
	print(cur, end=' ')
	traverse(nodes, nodes[cur][1])

def main():
	nodes = readtree()
	nops = int(input())
	for _ in range(nops):
		level = int(input())
		swap(nodes, 1, level, level)
		traverse(nodes, 1)
		print()
main()


import sys
sys.setrecursionlimit(15000)

class Node(object):

	def __init__(self, left=None, right=None, val=None):
		self.left = left
		self.right = right
		self.val = val

def readInTree(nodeList, currLineNum, maxLineNum, listIndex):
	if currLineNum <= maxLineNum:
		lineArr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
		currNode = nodeList[listIndex]
		if lineArr[0] != -1:
			leftNode = Node(None, None, lineArr[0])
			currNode.left = leftNode
			nodeList.append(leftNode)
		if lineArr[1] != -1:
			rightNode = Node(None, None, lineArr[1])
			currNode.right = rightNode
			nodeList.append(rightNode)
		readInTree(nodeList, currLineNum + 1, maxLineNum, listIndex + 1)

def populateInOrderList(node, listResults):
	if node.left is None and node.right is None:
		listResults.append(node.val)
	else:
		if node.left is not None:
			populateInOrderList(node.left, listResults)
		listResults.append(node.val)
		if node.right is not None:
			populateInOrderList(node.right, listResults)

def printCurrentTree(node):
	listResults = []
	populateInOrderList(rootNode, listResults)
	strResult = ''
	for i in range(0, len(listResults)):
		if i == 0:
			strResult += str(listResults[i])
		else:
			strResult += ' ' + str(listResults[i])
	print(strResult)

def performSwaps(node, currDepth, k):
	if node.left is not None or node.right is not None:
		if currDepth % k == 0:
			tempNode = node.right
			node.right = node.left
			node.left = tempNode
		if node.left is not None:
			performSwaps(node.left, currDepth + 1, k)
		if node.right is not None:
			performSwaps(node.right, currDepth + 1, k)
numNodes = int(input())
rootNode = Node(None, None, 1)
nodeList = []
nodeList.append(rootNode)
readInTree(nodeList, 1, numNodes, 0)
numSwaps = int(input())
for i in range(0, numSwaps):
	swapLevelK = int(input())
	performSwaps(rootNode, 1, swapLevelK)
	printCurrentTree(rootNode)


import sys
sys.setrecursionlimit(1500)

def xswap(t, k):
	return xswap_h(t, k, 1)

def xswap_h(t, k, a):
	if t == None or (t.left == None and t.right == None):
		return t
	if a % k == 0:
		return Tree(t.data, xswap_h(t.right, k, a + 1), xswap_h(t.left, k, a + 1))
	else:
		return Tree(t.data, xswap_h(t.left, k, a + 1), xswap_h(t.right, k, a + 1))

def inord(t):
	if t == None:
		return []
	else:
		return inord(t.left) + [t.data] + inord(t.right)

class Tree(object):

	def __init__(self, data, left, right):
		self.left = left
		self.right = right
		self.data = data
n = int(input())
d = {}
for i in range(1, n + 1):
	d[i] = [int(x) for x in input().split(' ')]
k = {}
k[-1] = None
for i in range(1, n + 1)[::-1]:
	k[i] = Tree(i, k[d[i][0]], k[d[i][1]])
tt = k[1]
q = int(input())
for i in range(q):
	z = int(input())
	tt = xswap(tt, z)
	for j in inord(tt):
		print(j, end=' ')
	print('\n', end='')


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, index=1, left=-1, right=-1):
		self.index = index
		self.left = left
		self.right = right

def traverseAndSwap(node, curlevel, level):
	if curlevel % level is 0:
		temp = node.left
		node.left = node.right
		node.right = temp
	if node.left is not -1:
		traverseAndSwap(node.left, curlevel + 1, level)
	if node.right is not -1:
		traverseAndSwap(node.right, curlevel + 1, level)

def inorder(root):
	if root is -1:
		return
	inorder(root.left)
	print(root.index, end=' ')
	inorder(root.right)

def main():
	nodes = int(input().strip())
	root = Node()
	queue = [root]
	for n in range(nodes):
		(left, right) = map(int, input().strip().split(' '))
		cur = None
		if len(queue):
			cur = queue[0]
			del queue[0]
		if left is not -1:
			cur.left = Node(left)
			queue.append(cur.left)
		if right is not -1:
			cur.right = Node(right)
			queue.append(cur.right)
	swaps = int(input().strip())
	for s in range(swaps):
		level = int(input().strip())
		traverseAndSwap(root, 1, level)
		inorder(root)
		print()
main()


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, value, left, right, depth):
		self.value = value
		self.left = left
		self.right = right
		self.depth = depth

def traverse(head):
	if head == None:
		return []
	res = traverse(head.left)
	res = res + [head.value]
	res = res + traverse(head.right)
	return res

def swap(head, depth):
	if head == None:
		return
	if head.depth == depth:
		tmp = head.left
		head.left = head.right
		head.right = tmp
		return
	swap(head.left, depth)
	swap(head.right, depth)
tree = {}
N = int(sys.stdin.readline().strip())
node = Node(1, None, None, 1)
tree[1] = node
max_height = 1
for value in range(1, N + 1):
	(left_value, right_value) = map(int, sys.stdin.readline().strip().split())
	node = tree.get(value)
	if left_value != -1:
		node.left = Node(left_value, None, None, node.depth + 1)
		tree[left_value] = node.left
	if right_value != -1:
		node.right = Node(right_value, None, None, node.depth + 1)
		tree[right_value] = node.right
	if (left_value != -1 or right_value != -1) and max_height < node.depth + 1:
		max_height = node.depth + 1
T = int(sys.stdin.readline().strip())
for line in sys.stdin.readlines():
	K = int(line.strip())
	iteration = 1
	while max_height >= K * iteration:
		swap(tree.get(1), K * iteration)
		iteration += 1
	print(' '.join(map(str, traverse(tree.get(1)))))


class Tree:

	def __init__(self, index):
		self.index = index

	def print(self):
		ind = []
		cur = self
		stack = []
		while cur or stack:
			if cur:
				stack.append(cur)
				cur = cur.L
			else:
				ind.append(stack[-1].index)
				cur = stack[-1].R
				stack.pop()
		print(' '.join([str(x) for x in ind]))

	def setSubTree(self, L, R):
		self.L = L
		self.R = R

	def swap(self):
		(self.L, self.R) = (self.R, self.L)
depth_map = {}
N = int(input())
trees = [None] + [Tree(i) for i in range(1, N + 1)] + [None]
trees[1].depth = 1
for n in range(1, N + 1):
	(l, r) = [int(x) for x in input().split()]
	trees[n].setSubTree(trees[l], trees[r])
	if trees[l]:
		trees[l].depth = trees[n].depth + 1
	if trees[r]:
		trees[r].depth = trees[n].depth + 1
	depth_map.setdefault(trees[n].depth, []).append(trees[n])
T = int(input())
for t in range(T):
	K = int(input())
	for i in range(N // K + 1):
		for tree in depth_map.get(i * K, []):
			tree.swap()
	trees[1].print()


import sys
sys.setrecursionlimit(15000)

class Node:

	def __init__(self, data, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

def inOrderPrint(root):
	if root:
		inOrderPrint(root.left)
		print(root.data, end=' ')
		inOrderPrint(root.right)

def swapTree(root, K, h=1):
	if root:
		if h % K == 0:
			(root.left, root.right) = (root.right, root.left)
		swapTree(root.left, K, h + 1)
		swapTree(root.right, K, h + 1)
N = int(input().strip())
root = Node(data=1)
nodes = [root]
for i in range(N):
	(left_data, right_data) = list(map(int, input().strip().split()))
	node = nodes[i]
	if left_data > 0:
		node.left = Node(data=left_data)
		nodes.append(node.left)
	if right_data > 0:
		node.right = Node(data=right_data)
		nodes.append(node.right)
T = int(input().strip())
for i in range(T):
	K = int(input().strip())
	swapTree(root, K)
	inOrderPrint(root)
	print()


class Node:

	def __init__(self, data):
		self.data = data
		self.left = self.right = None

	def swap(self):
		tmp = self.left
		self.left = self.right
		self.right = tmp

	def __str__(self):
		return 'Data={}'.format(self.data)

	def __repr__(self):
		return 'Data={}'.format(self.data)

def parse_input_to_tree():
	nodes_num = int(input())
	if nodes_num <= 0:
		return None
	ret = Node(1)
	q = [ret]
	while q:
		curr = q.pop(0)
		(left_data, right_data) = tuple(map(int, input().split()))
		if left_data != -1:
			curr.left = Node(left_data)
			q.append(curr.left)
		if right_data != -1:
			curr.right = Node(right_data)
			q.append(curr.right)
	return ret

def parse_k_vals():
	k_num = int(input())
	ret = []
	for _ in range(k_num):
		ret.append(int(input()))
	return ret

def solution(tree, k_vals):
	for k in k_vals:
		swap_at_k(tree, k)
		print_tree(tree)
		print()

def swap_at_k(tree, k, curr_level=1):
	if tree is None:
		return
	if curr_level % k == 0:
		tree.swap()
	swap_at_k(tree.left, k, curr_level + 1)
	swap_at_k(tree.right, k, curr_level + 1)

def print_tree(tree):
	if tree is None:
		return
	print_tree(tree.left)
	print(tree.data, end=' ')
	print_tree(tree.right)

def main():
	import sys
	sys.setrecursionlimit(1500)
	tree = parse_input_to_tree()
	k_vals = parse_k_vals()
	solution(tree, k_vals)
main()


import sys
N = int(sys.stdin.readline().strip())
tree = []
for i in range(N):
	(a, b) = sys.stdin.readline().strip().split()
	tree.append([int(a), int(b)])
T = int(sys.stdin.readline().strip())

def get_height(node):
	if node == -1:
		return 0
	left_index = tree[node][0]
	right_index = tree[node][1]
	return 1 + max(get_height(left_index), get_height(right_index))

def do_swap(node, depth, K):
	if node == -1:
		return
	if depth % K == 0:
		(tree[node - 1][0], tree[node - 1][1]) = (tree[node - 1][1], tree[node - 1][0])
	left_index = tree[node - 1][0]
	right_index = tree[node - 1][1]
	if left_index != -1:
		do_swap(left_index, depth + 1, K)
	if right_index != -1:
		do_swap(right_index, depth + 1, K)

def do_swap2(node, K):
	queue = [(node, 1)]
	while queue:
		(node, depth) = queue.pop(0)
		if depth % K == 0:
			(tree[node - 1][0], tree[node - 1][1]) = (tree[node - 1][1], tree[node - 1][0])
		if tree[node - 1][0] != -1:
			queue.append((tree[node - 1][0], depth + 1))
		if tree[node - 1][1] != -1:
			queue.append((tree[node - 1][1], depth + 1))

def do_print(node):
	if node == -1:
		return
	left_index = tree[node - 1][0]
	do_print(left_index)
	print(node, end=' ')
	right_index = tree[node - 1][1]
	do_print(right_index)

def do_print2(node):
	curr = node
	stack = []
	while True:
		if curr != -1:
			stack.append(curr)
			curr = tree[curr - 1][0]
		else:
			if not stack:
				break
			curr = stack.pop()
			print(curr, end=' ')
			curr = tree[curr - 1][1]
for i in range(T):
	K = int(sys.stdin.readline().strip())
	do_swap2(1, K)
	do_print2(1)
	print()


import sys
sys.setrecursionlimit(2000)

class Node:

	def __init__(self, data):
		self.data = data
		self.left = self.right = None

	def print(self):
		if self.left:
			self.left.print()
		print(self.data, end=' ')
		if self.right:
			self.right.print()

	def swap(self, level, curr_level):
		if curr_level % level == 0:
			(self.left, self.right) = (self.right, self.left)
		if self.left:
			self.left.swap(level, curr_level + 1)
		if self.right:
			self.right.swap(level, curr_level + 1)

def read_input():
	return [int(s) for s in input().strip().split(' ')]

def find(root, val):
	if root:
		if root.data == val:
			return root
		left = find(root.left, val)
		if left:
			return left
		right = find(root.right, val)
		if right:
			return right
	return None
n = read_input()[0]
root = Node(1)
for i in range(1, n + 1):
	node = find(root, i)
	(l, r) = read_input()
	if l != -1:
		node.left = find(root, l) or Node(l)
	if r != -1:
		node.right = find(root, r) or Node(r)
t = read_input()[0]
for i in range(t):
	swap = read_input()[0]
	root.swap(swap, 1)
	root.print()
	print()


N = int(input())

class Node(object):

	def __init__(self, data, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

def in_order(root):
	stack = [root]
	visited = []
	while len(stack) > 0:
		node = stack[-1]
		stack = stack[:-1]
		if not node:
			continue
		if node not in visited:
			visited.append(node)
			stack.append(node.right)
			stack.append(node)
			stack.append(node.left)
		elif node in visited:
			print('{} '.format(node.data), end='')

def turn(root, k):
	queue = [root, 'OI']
	depth = 1
	while len(queue) > 0:
		node = queue[0]
		queue = queue[1:]
		if not node:
			continue
		if node == 'OI':
			if len(queue) > 0:
				queue.append('OI')
				depth += 1
			continue
		if depth % k == 0:
			temp = node.left
			node.left = node.right
			node.right = temp
		queue.append(node.left)
		queue.append(node.right)
root = Node(1)
queue = [root]
for i in range(N):
	(l, r) = map(int, input().split(' '))
	current = queue[0]
	queue = queue[1:]
	if l != -1:
		current.left = Node(l)
		queue.append(current.left)
	if r != -1:
		current.right = Node(r)
		queue.append(current.right)
T = int(input())
for i in range(T):
	k = int(input())
	turn(root, k)
	in_order(root)
	print()