{"problem":{"name":"[NFLSPC #6] 9.pop_book();","description":{"content":"在长度为 $m$ 的环形操场上有 $n$ 个人，第 $i$ 个人在 $t_i$ 时刻从位置 $p_i$ 出发以 $v_i$ 单位长度每秒的速度移动。现在 $0$ 时刻 *Alek 岁*在位置 $0$ 处，速度为 $0$，会跟着经过他的速度最快的人移动。$q$ 次询问 $T_i$ 时刻 *Alek 岁*的移动距离。可以证明这是一个整数。 注：从位置 $0$ 出发逆时针方向 $x$（$0\\leq x","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9933"},"statements":[{"statement_type":"Markdown","content":"在长度为 $m$ 的环形操场上有 $n$ 个人，第 $i$ 个人在 $t_i$ 时刻从位置 $p_i$ 出发以 $v_i$ 单位长度每秒的速度移动。现在 $0$ 时刻 *Alek 岁*在位置 $0$ 处，速度为 $0$，会跟着经过他的速度最快的人移动。$q$ 次询问 $T_i$ 时刻 *Alek 岁*的移动距离。可以证明这是一个整数。\n\n注：从位置 $0$ 出发逆时针方向 $x$（$0\\leq x < m$）单位长度的位置称为位置 $x$。所有人的运动方向都是逆时针。\n\n多组数据。\n\n## Input\n\n第一行一个整数 $T$ 表示数据组数。对于每组数据：\n\n- 第一行三个整数 $n, m, q$，分别表示人数，操场长度和询问个数。\n- 接下来 $n$ 行，每行三个整数 $p_i, v_i, t_i$，分别表示第 $i$ 个人出发时的位置，移动速度（单位长度每秒）和出发时间。\n- 接下来 $q$ 行，每行一个整数 $T_i$ 表示一次询问。\n\n## Output\n\n对于每个询问，输出一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n*Alek 岁*在操场上跑圈。他看到有人超过他，很不爽。于是他采取了以下策略：\n\n## Note\n\n对于所有数据，$1\\leq T\\leq 10 ^ 3$，$1\\leq n, \\sum n\\leq 5\\times 10 ^ 5$，$1\\leq m, q, \\sum q \\leq 10 ^ 6$，$1\\leq v_i, t_i, T_i\\leq 10 ^ 9$，$0\\leq p_i < m$。保证 $t_i$ 单调不降，$T_i$ 单调递增。\n\n- 子任务 1（$10$ 分）：$n\\leq 5$。\n- 子任务 2（$10$ 分）：$n\\leq 50$。\n- 子任务 3（$20$ 分）：$n\\leq 500$。\n- 子任务 4（$20$ 分）：$n\\leq 5\\times 10 ^ 3$。\n- 子任务 5（$20$ 分）：$n\\leq 5\\times 10 ^ 4$。\n- 子任务 6（$20$ 分）：无特殊限制。\n\n**请注意，子任务并没有保证 $\\sum q$ 的数量级**。\n\n本题 IO 量较大，建议使用 `scanf/printf` 或关闭流同步的 `cin/cout` 或快速读入和快速输出。\n\nSource：NFLSPC #6 I by Alex_Wei","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9933","tags":["O2优化"],"sample_group":[["1\n3 30 8\n0 2 1\n6 5 2\n25 4 4\n1\n5\n9\n10\n11\n12\n13\n14\n","0\n8\n16\n19\n23\n27\n31\n36\n"]],"created_at":"2026-03-03 11:09:25"}}