sys.setrecursionlimit(1 << 30)
def create_tree(indexes):
    tree_arr = [-1 for _ in range(1025)]
    tree_arr[1] = 1

    _next = []
    frontier = [1]
    indexes_pos = 0
    while frontier:
        for v in frontier:

            if indexes_pos >= len(indexes):
                return tree_arr

            if v != -1:
                left_c, right_c = indexes[indexes_pos][0], indexes[indexes_pos][1]
                tree_arr[v] = [left_c, right_c]
                _next.append(left_c)
                _next.append(right_c)
                indexes_pos += 1

        frontier = _next
        _next = []

    return tree_arr


def swapNodes(indexes, queries):
    tree = create_tree(indexes)
    height = 1025
    controller = [0 for _ in range(height)]
    traverse_res = []
    
    def traverse(lvl, idx):
        if idx >= len(tree) or idx == -1:
            return
            
        left = tree[idx][0]
        right = tree[idx][1]
        if controller[lvl] == 1:
            left = tree[idx][1]
            right = tree[idx][0]
            
        traverse(lvl+1, left)
        traverse_res.append(idx)
        traverse(lvl+1, right)
        
        return
    
    res = []
    for q in queries:
        tmp = q
        while q < height-1:
            controller[q-1] = not controller[q-1]
            q += tmp
        traverse(0, 1)
        res.append(traverse_res)
        traverse_res = []
				
        
    return res
        

from collections import deque
sys.setrecursionlimit(500000)

#
# Complete the 'swapNodes' function below.
#
# The function is expected to return a 2D_INTEGER_ARRAY.
# The function accepts following parameters:
#  1. 2D_INTEGER_ARRAY indexes
#  2. INTEGER_ARRAY queries
#

class node:
    def __init__(self, info, depth):
        self.info = info
        self.depth = depth
        self.left = None
        self.right = None
        
def createTree(indexes):
    q = deque()
    root = node(1, 1)
    q.append(root)
    
    for x in indexes:
        ele = q.popleft()
        if x[0] != -1:
            ele.left = node(x[0], ele.depth + 1)
            q.append(ele.left)
        if x[1] != -1:
            ele.right = node(x[1], ele.depth + 1)
            q.append(ele.right)
        if len(q) == 0:
            break
            
    return root
    
    
def inorder(root):
    values = []
    
    def inorder_traversal(root):
        if root is None:
            return
        inorder_traversal(root.left)
        values.append(root.info)
        inorder_traversal(root.right)
        
    inorder_traversal(root)
    return values
        
        
def nodesStack(root):
    stack = [root]
    values = []
    while len(stack) != 0:
        ele = stack.pop()
        values.append(ele)
        if ele.left:
            stack.append(ele.left)
        if ele.right:
            stack.append(ele.right)
            
    return values

def swapNodes(indexes, queries):
    # Write your code here
    root = createTree(indexes)
    nodes = nodesStack(root)
    finalarray = []
    for k in queries:
        for n in nodes:
            if n.depth % k == 0:
                if n.left is None and n.right is None:
                    pass
                elif n.left is None and n.right:
                    n.left = n.right
                    n.right = None
                elif n.right is None and n.left:
                    n.right = n.left
                    n.left = None
                else:
                    temp = n.right
                    n.right = n.left
                    n.left = temp
        finalarray.append(inorder(root))
        
    return finalarray

class Node {
    constructor(val) {
        this.val = val;
        this.levelNum = null;
        this.left = null;
        this.right = null;
    }
}

/**
 * Swap nodes in a binary tree at the levels listed in the queries array.
 * @param {Array<Array<Number>>} indexes
 * @param {Array<Number>} queries
 * @returns {Array<Array<Number>>}
 */
function swapNodes(indexes, queries) {
    if (!indexes?.length || !queries?.length) {
        return [];
    } else if (indexes.length === 1) {
        return indexes;
    }

    // Construct binary tree from indexes (which is a 2-dimensional array)
    const root = new Node(1);
    root.levelNum = 1;
    const buildQueue = [root];
    for (const [leftVal, rightVal] of indexes) {
        const node = buildQueue.shift();
        if (leftVal !== -1) {
            node.left = new Node(leftVal);
            buildQueue.push(node.left);
        }
        if (rightVal !== -1) {
            node.right = new Node(rightVal);
            buildQueue.push(node.right);
        }
    }

    // `factor` is `k` from the instructions
    const allResults = [];
    for (const factor of queries) {
        const result = [];
        traverseInOrderAndSwap(root, factor, result);
        allResults.push(result);
    }

    return allResults;
}

/**
 * Traverse in-order (DFS) and swap the nodes at the appropriate levels.
 * @param {Node} node
 * @param {Number} factor
 * @param {Array<Number>} result
 */
function traverseInOrderAndSwap(node, factor, result) {
    const isSwapLevel = node?.levelNum % factor === 0;
    if (isSwapLevel) {
        const holder = node.left;
        node.left = node.right;
        node.right = holder;
    }

    if (node.left) {
        node.left.levelNum = node.levelNum + 1;
        traverseInOrderAndSwap(node.left, factor, result);
    }
    if (node.val) result.push(node.val);
    if (node.right) {
        node.right.levelNum = node.levelNum + 1;
        traverseInOrderAndSwap(node.right, factor, result);
    }
}

class Node {
    public:
        int data;
        Node* left;
        Node* right;
        Node(int x) : data(x), left(nullptr), right(nullptr) {}
};

void inorder(Node* root, vector<int>& res_value) {
    if(!root) return;
    inorder(root->left, res_value);
    res_value.push_back(root->data);
    inorder(root->right, res_value);
}

void swapNodesUtil(Node* root, int level, int k) {
    if(!root || (!root->left && !root->right)) return;

    
    if(level % k == 0) {
        swap(root->left, root->right);
    }
    swapNodesUtil(root->left, level + 1, k);
    swapNodesUtil(root->right, level + 1, k);
    
}

vector<vector<int>> swapNodes(vector<vector<int>> indexes, vector<int> queries) {
    Node* root = new Node(1);
    
    //build tree from queue
    queue<Node*> q;
    q.push(root);
    for(int i = 0;i<indexes.size();i++) {
        Node* cur = q.front();
        q.pop();
        cout << cur->data << endl;
        if(indexes[i][0] != -1)
        {
            cur->left = new Node(indexes[i][0]);
            q.push(cur->left);
        }

        if(indexes[i][1] != -1) {
            cur->right = new Node(indexes[i][1]);
            q.push(cur->right);
        }
        
    }
    
    // swap node and travelsal to save tree to array
    vector<vector<int>> res;
    for(int i = 0;i<queries.size();i++) {
        vector<int> res_value;
        swapNodesUtil(root, 1, queries[i]);
        inorder(root,res_value);
        res.push_back(res_value);
    }
    return res;
    
}