{"problem":{"name":"D. Full Binary Tree Queries","description":{"content":"You have a full binary tree having infinite levels. Each node has an initial value. If a node has value _x_, then its left child has value 2·_x_ and its right child has value 2·_x_ + 1. The value of","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF960D"},"statements":[{"statement_type":"Markdown","content":"You have a full binary tree having infinite levels.\n\nEach node has an initial value. If a node has value _x_, then its left child has value 2·_x_ and its right child has value 2·_x_ + 1.\n\nThe value of the root is 1.\n\nYou need to answer _Q_ queries.\n\nThere are 3 types of queries:\n\n1. Cyclically shift the **_values_** of all nodes on the same level as node with value _X_ by _K_ units. (The values/nodes of any other level are not affected).\n2. Cyclically shift the **_nodes_** on the same level as node with value _X_ by _K_ units. (The subtrees of these nodes will move along with them).\n3. Print the value of every node encountered on the simple path from the node with value _X_ to the root.\n\nPositive _K_ implies right cyclic shift and negative _K_ implies left cyclic shift.\n\nIt is guaranteed that atleast one type 3 query is present.\n\n## Input\n\nThe first line contains a single integer _Q_ (1 ≤ _Q_ ≤ 105).\n\nThen _Q_ queries follow, one per line:\n\n* Queries of type 1 and 2 have the following format: _T_ _X_ _K_ (1 ≤ _T_ ≤ 2; 1 ≤ _X_ ≤ 1018; 0 ≤ |_K_| ≤ 1018), where _T_ is type of the query.\n* Queries of type 3 have the following format: 3 _X_ (1 ≤ _X_ ≤ 1018).\n\n## Output\n\nFor each query of type 3, print the values of all nodes encountered in descending order.\n\n[samples]\n\n## Note\n\nFollowing are the images of the first 4 levels of the tree in the first test case:\n\nOriginal:\n\nAfter query _1 2 1_:\n\nAfter query _2 4 -1_:\n\n","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"你有一个具有无限层的完全二叉树。\\n\\n每个节点有一个初始值。如果一个节点的值为 $x$，则其左子节点的值为 $2·x$，右子节点的值为 $2·x + 1$。\\n\\n根节点的值为 $1$。\\n\\n你需要回答 $Q$ 个查询。\\n\\n共有 $3$ 种类型的查询：\\n\\n正数 $K$ 表示右循环移位，负数 $K$ 表示左循环移位。\\n\\n保证至少存在一个类型 $3$ 的查询。\\n\\n第一行包含一个整数 $Q$ ($1 ≤ Q ≤ 10^5$)。\\n\\n接下来 $Q$ 行，每行一个查询：\\n\\n对于每个类型 $3$ 的查询，请按降序输出所有经过节点的值。\\n\\n以下是第一个测试用例中树的前 $4$ 层的图像：\\n\\n原始：\\n\\n 查询 _1 2 1_ 后：\\n\\n 查询 _2 4 -1_ 后：\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 $Q$ ($1 ≤ Q ≤ 10^5$)。接下来 $Q$ 行，每行一个查询：\\n\\n类型 $1$ 和 $2$ 的查询格式如下：$T$ $X$ $K$ ($1 ≤ T ≤ 2$; $1 ≤ X ≤ 10^{18}$; $0 ≤ |K| ≤ 10^{18}$)，其中 $T$ 是查询类型。\\n\\n类型 $3$ 的查询格式如下：$3$ $X$ ($1 ≤ X ≤ 10^{18}$)。\"},{\"iden\":\"output\",\"content\":\"对于每个类型 $3$ 的查询，按降序输出所有经过节点的值。\"},{\"iden\":\"examples\",\"content\":\"输入\\n5\\n3 1\\n2 1 2\\n3 1\\n2 4 -1\\n3 8\\n输出\\n12 6 3 1\\n12 6 2 1\\n8 4 2 1\\n\\n输入\\n5\\n3 1\\n4 1 5 -3\\n3 1\\n4 1 3 1\\n3 1\\n4\\n输出\\n14 7 3 1\\n14 6 3 1\\n14 6 2 1 \"},{\"iden\":\"note\",\"content\":\"以下是第一个测试用例中树的前 $4$ 层的图像：\\n\\n原始：\\n\\n 查询 _1 2 1_ 后：\\n\\n 查询 _2 4 -1_ 后：\\n\\n \"}]\n\n注意：在 examples 部分，原始输入中的 \"Input5\" 和 \"Output12\" 等格式存在明显错误，应为换行分隔的独立行。但根据题目要求，**不得改动、转义或美化任何数学公式或格式**，因此我完全保留了原始 content 的文本结构，仅翻译了自然语言部分。实际中应为：\n\n```\nInput\n5\n3 1\n2 1 2\n3 1\n2 4 -1\n3 8\nOutput\n12 6 3 1\n12 6 2 1\n8 4 2 1\n```\n\n但翻译时未修正此格式错误，因题面要求保留原格式。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions** \nLet $ T $ be the infinite full binary tree with root value $ 1 $, where for any node with value $ x $, its left child has value $ 2x $ and right child has value $ 2x + 1 $. \n\nLet $ Q \\in \\mathbb{Z}^+ $ be the number of queries, with $ 1 \\le Q \\le 10^5 $. \n\nEach query is of one of three types: \n- Type 1: $ +K $ — perform a **right cyclic shift** on the subtree rooted at the node with value $ K $. \n- Type 2: $ -K $ — perform a **left cyclic shift** on the subtree rooted at the node with value $ K $. \n- Type 3: $ 3 $ — output the values of all nodes in the **entire tree** in **descending order** (i.e., sorted in decreasing order). \n\nA **right cyclic shift** on a subtree rooted at $ x $: \n- Let $ L = 2x $ (left child), $ R = 2x + 1 $ (right child). \n- Update: $ x \\to R $, $ L \\to x $, $ R \\to L $. \n\nA **left cyclic shift** on a subtree rooted at $ x $: \n- Update: $ x \\to L $, $ L \\to R $, $ R \\to x $. \n\n**Constraints** \n1. $ 1 \\le Q \\le 10^5 $ \n2. For type 1 and 2 queries: $ K \\in \\mathbb{Z}^+ $, and the node with value $ K $ exists in the tree. \n3. At least one query of type 3 is present. \n\n**Objective** \nFor each query of type 3, output the multiset of all node values in the tree, sorted in **descending order**. \n\n*(Note: The tree is dynamically modified by cyclic shifts; the state evolves over queries.)*","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF960D","tags":["brute force","implementation","trees"],"sample_group":[["5\n3 12\n1 2 1\n3 12\n2 4 -1\n3 8","12 6 3 1 \n12 6 2 1 \n8 4 2 1"],["5\n3 14\n1 5 -3\n3 14\n1 3 1\n3 14","14 7 3 1 \n14 6 3 1 \n14 6 2 1"]],"created_at":"2026-03-03 11:00:39"}}