{"problem":{"name":"[USACO24FEB] Lazy Cow P","description":{"content":"Bessie 正在努力为美国件算机奥林匹克二月的竞赛准备测试用例。每一分钟，她可以选择不准备测试用例，不花费能量；或者对于某个正整数 $a$，花费 $3^{a−1}$ 能量准备 $a$ 个测试用例。 Farmer John 有 $D$（$1\\le D\\le 2\\cdot 10^5$）个需求。对于第 $i$ 个需求，他告诉 Bessie，在前 $m_i$ 分钟内她总共需要准备至少 $b_i$ 个测","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10196"},"statements":[{"statement_type":"Markdown","content":"Bessie 正在努力为美国件算机奥林匹克二月的竞赛准备测试用例。每一分钟，她可以选择不准备测试用例，不花费能量；或者对于某个正整数 $a$，花费 $3^{a−1}$ 能量准备 $a$ 个测试用例。\n\nFarmer John 有 $D$（$1\\le D\\le 2\\cdot 10^5$）个需求。对于第 $i$ 个需求，他告诉 Bessie，在前 $m_i$ 分钟内她总共需要准备至少 $b_i$ 个测试用例（$1\\le m_i\\le 10^6,1\\le b_i\\le 10^{12}$）。\n\n令 $e_i$ 为满足前 $i$ 个需求 Bessie 最小需要花费的能量。输出 $e_1,\\ldots,e_D$ 模 $10^9+7$ 的余数。 \n\n## Input\n\n输入的第一行包含 $D$。以下 $D$ 行，第 $i$ 行包含两个空格分隔的整数 $m_i$ 和 $b_i$。\n\n## Output\n\n输出 $D$ 行，第 $i$ 行包含 $e_i \\bmod 10^9+7$。 \n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n对于第一个测试用例，\n\n- $i=1$：如果 Bessie 在前 $5$ 天分别制作 $[2,3,2,2,2]$ 个测试用例，她将花费 $3^1+3^2+3^1+3^1+3^1=21$ 单位能量，并在第 $5$ 天结束时制作了 $11$ 个测试用例。\n- $i=2$：Bessie 可以遵循上面的策略，确保在第 $5$ 天结束时制作了 $11$ 个测试用例，而这将自动满足第二个需求。\n- $i=3$：如果 Bessie 在前 $10$ 天分别制作 $[2,3,2,2,2,0,1,1,1,1]$ 个测试用例，她将花费 $25$ 单位能量并满足所有需求。可以证明她无法花费更少的能量。\n- $i=4$：如果 Bessie 在前 $10$ 天每一天制作 $3$ 个测试用例，她将花费 $3^2\\cdot 10=90$ 单位能量并满足所有需求。\n\n对于每一个 $i$，可以证明 Bessie 无法花费更少的能量满足前 $i$ 个需求。\n\n### 测试点性质\n\n- 测试点 $4-5$：$D\\le 100$，且对于所有 $i$，$m_i\\le 100$。\n- 测试点 $6-8$：$D\\le 3000$。\n- 测试点 $9-20$：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10196","tags":["线段树","二分","USACO","2024","O2优化","凸包"],"sample_group":[["4\n5 11\n6 10\n10 15\n10 30","21\n21\n25\n90"],["2\n100 5\n100 1000000000000","5\n627323485"],["20\n303590 482848034083\n180190 112716918480\n312298 258438719980\n671877 605558355401\n662137 440411075067\n257593 261569032231\n766172 268433874550\n8114 905639446594\n209577 11155741818\n227183 874665904430\n896141 55422874585\n728247 456681845046\n193800 632739601224\n443005 623200306681\n330325 955479269245\n377303 177279745225\n880246 22559233849\n58084 155169139314\n813702 758370488574\n929760 785245728062","108753959\n108753959\n108753959\n148189797\n148189797\n148189797\n148189797\n32884410\n32884410\n32884410\n32884410\n32884410\n32884410\n32884410\n3883759\n3883759\n3883759\n3883759\n3883759\n3883759"]],"created_at":"2026-03-03 11:09:25"}}