{"raw_statement":[{"iden":"statement","content":"The ICM ACPC World Finals is coming! Unfortunately, the organizers of the competition were so busy preparing tasks that totally missed an important technical point — the organization of electricity supplement for all the participants workstations.\n\nThere are _n_ computers for participants, the _i_\\-th of which has power equal to positive integer _p__i_. At the same time there are _m_ sockets available, the _j_\\-th of which has power euqal to positive integer _s__j_. It is possible to connect the _i_\\-th computer to the _j_\\-th socket if and only if their powers are the same: _p__i_ = _s__j_. It is allowed to connect no more than one computer to one socket. Thus, if the powers of all computers and sockets are distinct, then no computer can be connected to any of the sockets.\n\nIn order to fix the situation professor Puch Williams urgently ordered a wagon of adapters — power splitters. Each adapter has one plug and one socket with a voltage divider between them. After plugging an adapter to a socket with power _x_, the power on the adapter's socket becomes equal to , it means that it is equal to the socket's power divided by two with rounding up, for example and .\n\nEach adapter can be used only once. It is possible to connect several adapters in a chain plugging the first to a socket. For example, if two adapters are plugged one after enother to a socket with power 10, it becomes possible to connect one computer with power 3 to this socket.\n\nThe organizers should install adapters so that it will be possible to supply with electricity the maximum number of computers _c_ at the same time. If there are several possible connection configurations, they want to find the one that uses the minimum number of adapters _u_ to connect _c_ computers.\n\nHelp organizers calculate the maximum number of connected computers _c_ and the minimum number of adapters _u_ needed for this.\n\nThe wagon of adapters contains enough of them to do the task. It is guaranteed that it's possible to connect at least one computer."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 200 000) — the number of computers and the number of sockets.\n\nThe second line contains _n_ integers _p_1, _p_2, ..., _p__n_ (1 ≤ _p__i_ ≤ 109) — the powers of the computers.\n\nThe third line contains _m_ integers _s_1, _s_2, ..., _s__m_ (1 ≤ _s__i_ ≤ 109) — the power of the sockets."},{"iden":"output","content":"In the first line print two numbers _c_ and _u_ — the maximum number of computers which can at the same time be connected to electricity and the minimum number of adapters needed to connect _c_ computers.\n\nIn the second line print _m_ integers _a_1, _a_2, ..., _a__m_ (0 ≤ _a__i_ ≤ 109), where _a__i_ equals the number of adapters orginizers need to plug into the _i_\\-th socket. The sum of all _a__i_ should be equal to _u_.\n\nIn third line print _n_ integers _b_1, _b_2, ..., _b__n_ (0 ≤ _b__i_ ≤ _m_), where the _b__j_\\-th equals the number of the socket which the _j_\\-th computer should be connected to. _b__j_ = 0 means that the _j_\\-th computer should not be connected to any socket. All _b__j_ that are different from 0 should be distinct. The power of the _j_\\-th computer should be equal to the power of the socket _b__j_ after plugging in _a__b__j_ adapters. The number of non-zero _b__j_ should be equal to _c_.\n\nIf there are multiple answers, print any of them."},{"iden":"examples","content":"Input\n\n2 2\n1 1\n2 2\n\nOutput\n\n2 2\n1 1\n1 2\n\nInput\n\n2 1\n2 100\n99\n\nOutput\n\n1 6\n6\n1 0"}],"translated_statement":[{"iden":"statement","content":"ICM ACPC 世界总决赛即将来临！不幸的是，比赛组织者忙于准备题目，完全忽略了一个重要技术问题——为所有参赛者的工作站提供电力补给。\n\n共有 #cf_span[n] 台计算机，其中第 #cf_span[i] 台的功率为正整数 #cf_span[pi]。同时有 #cf_span[m] 个插座可用，第 #cf_span[j] 个插座的功率为正整数 #cf_span[sj]。只有当计算机和插座的功率相同时，即 #cf_span[pi = sj]，才能将第 #cf_span[i] 台计算机连接到第 #cf_span[j] 个插座。每个插座最多只能连接一台计算机。因此，如果所有计算机和插座的功率互不相同，则无法连接任何计算机。\n\n为了解决这一问题，教授 Puch Williams 急需订购了一批适配器——电源分路器。每个适配器有一个插头和一个插座，中间有一个电压分压器。当将一个适配器插入功率为 #cf_span[x] 的插座时，适配器插座上的功率变为 $\\lceil x / 2 \\rceil$，即插座功率除以二后向上取整，例如 $\\lceil 5 / 2 \\rceil = 3$ 且 $\\lceil 6 / 2 \\rceil = 3$。\n\n每个适配器只能使用一次。可以将多个适配器串联使用，将第一个插入插座。例如，若将两个适配器依次插入功率为 #cf_span[10] 的插座，则最终插座的功率变为 $\\lceil \\lceil 10 / 2 \\rceil / 2 \\rceil = \\lceil 5 / 2 \\rceil = 3$，此时即可连接一台功率为 #cf_span[3] 的计算机。\n\n组织者需要安装适配器，使得同时能够供电的计算机数量 #cf_span[c] 最大。如果有多种连接配置能达到最大数量 #cf_span[c]，他们希望找到其中使用适配器数量 #cf_span[u] 最少的一种。\n\n请帮助组织者计算最多能连接的计算机数量 #cf_span[c] 以及实现该数量所需的最少适配器数量 #cf_span[u]。\n\n适配器的供应充足，足以完成任务。保证至少可以连接一台计算机。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 200 000]) —— 计算机和插座的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[1 ≤ pi ≤ 10^9]) —— 计算机的功率。\n\n第三行包含 #cf_span[m] 个整数 #cf_span[s1, s2, ..., sm] (#cf_span[1 ≤ si ≤ 10^9]) —— 插座的功率。\n\n第一行输出两个数字 #cf_span[c] 和 #cf_span[u] —— 同时能连接的计算机最大数量和连接 #cf_span[c] 台计算机所需的最少适配器数量。\n\n第二行输出 #cf_span[m] 个整数 #cf_span[a1, a2, ..., am] (#cf_span[0 ≤ ai ≤ 10^9])，其中 #cf_span[ai] 表示需要插入第 #cf_span[i] 个插座的适配器数量。所有 #cf_span[ai] 的总和应等于 #cf_span[u]。\n\n第三行输出 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn] (#cf_span[0 ≤ bi ≤ m])，其中 #cf_span[bj] 表示第 #cf_span[j] 台计算机应连接的插座编号。#cf_span[bj = 0] 表示第 #cf_span[j] 台计算机不应连接任何插座。所有非零的 #cf_span[bj] 应互不相同。第 #cf_span[j] 台计算机的功率应等于第 #cf_span[bj] 个插座在插入 #cf_span[abj] 个适配器后的功率。非零的 #cf_span[bj] 的数量应等于 #cf_span[c]。\n\n如果有多个答案，输出任意一个即可。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 200 000]) —— 计算机和插座的数量。第二行包含 #cf_span[n] 个整数 #cf_span[p1, p2, ..., pn] (#cf_span[1 ≤ pi ≤ 10^9]) —— 计算机的功率。第三行包含 #cf_span[m] 个整数 #cf_span[s1, s2, ..., sm] (#cf_span[1 ≤ si ≤ 10^9]) —— 插座的功率。"},{"iden":"output","content":"第一行输出两个数字 #cf_span[c] 和 #cf_span[u] —— 同时能连接的计算机最大数量和连接 #cf_span[c] 台计算机所需的最少适配器数量。第二行输出 #cf_span[m] 个整数 #cf_span[a1, a2, ..., am] (#cf_span[0 ≤ ai ≤ 10^9])，其中 #cf_span[ai] 表示需要插入第 #cf_span[i] 个插座的适配器数量。所有 #cf_span[ai] 的总和应等于 #cf_span[u]。第三行输出 #cf_span[n] 个整数 #cf_span[b1, b2, ..., bn] (#cf_span[0 ≤ bi ≤ m])，其中 #cf_span[bj] 表示第 #cf_span[j] 台计算机应连接的插座编号。#cf_span[bj = 0] 表示第 #cf_span[j] 台计算机不应连接任何插座。所有非零的 #cf_span[bj] 应互不相同。第 #cf_span[j] 台计算机的功率应等于第 #cf_span[bj] 个插座在插入 #cf_span[abj] 个适配器后的功率。非零的 #cf_span[bj] 的数量应等于 #cf_span[c]。如果有多个答案，输出任意一个即可。"},{"iden":"examples","content":"输入\n2 2\n1 1\n2 2\n输出\n2 2\n1 1\n1 2\n\n输入\n2 1\n2 100\n99\n输出\n1 66\n1 0"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ be the number of computers and sockets, respectively.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be the power values of computers, where $ p_i \\in \\mathbb{Z}^+ $.  \nLet $ S = (s_1, s_2, \\dots, s_m) $ be the power values of sockets, where $ s_j \\in \\mathbb{Z}^+ $.  \n\nFor a socket $ j $ with power $ s_j $, applying $ a $ adapters yields effective power:  \n$$\nf(s_j, a) = \\left\\lceil \\frac{s_j}{2^a} \\right\\rceil, \\quad a \\in \\mathbb{Z}_{\\geq 0}\n$$\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 200{,}000 $  \n2. $ 1 \\leq p_i, s_j \\leq 10^9 $  \n3. Each socket can be connected to at most one computer.  \n4. Each computer can be connected to at most one socket.  \n5. Adapters can be chained: applying $ a_j $ adapters to socket $ j $ reduces its power to $ \\left\\lceil \\frac{s_j}{2^{a_j}} \\right\\rceil $.  \n6. Total adapters used: $ u = \\sum_{j=1}^m a_j $, minimized subject to maximizing connected computers.  \n\n**Objective**  \nFind:  \n- Maximum number of computers $ c $ that can be connected.  \n- Minimum total number of adapters $ u $ required to achieve $ c $.  \n- Assignment vectors:  \n  - $ A = (a_1, \\dots, a_m) \\in \\mathbb{Z}_{\\geq 0}^m $, where $ a_j $ is the number of adapters on socket $ j $, $ \\sum a_j = u $.  \n  - $ B = (b_1, \\dots, b_n) \\in \\{0, 1, \\dots, m\\}^n $, where $ b_i = j $ means computer $ i $ is connected to socket $ j $, and $ b_i = 0 $ means unconnected.  \n    - All non-zero $ b_i $ are distinct.  \n    - $ p_i = \\left\\lceil \\frac{s_{b_i}}{2^{a_{b_i}}} \\right\\rceil $ for all $ b_i \\neq 0 $.  \n    - $ |\\{ i \\mid b_i \\neq 0 \\}| = c $.  \n\n**Output**  \n$ c, u $  \n$ A = (a_1, \\dots, a_m) $  \n$ B = (b_1, \\dots, b_n) $","simple_statement":null,"has_page_source":false}