P7596 「EZEC-8」游戏蛇

小 A 和小 B 是两条蛇，他们正在一棵特殊的树上做游戏。 这棵树的结构如下：首先有一条长度为 $n$ 的链，称为“主链”。主链由 $1$ 至 $n$ 这 $n$ 个节点构成。在主链上，编号相邻的点有边相连，否则则没有。 主链上的每一个点都挂着一条链，称为“副链”。主链上的第 $i$ 个点挂的副链长度（链上的点数）为 $x_i$。 小 A 和小 B 初始时都在主链上，具体而言，小 A 的**蛇尾**在点 $a$，**蛇头**在点 $b$，小 B 的**蛇头**在点 $c$，**蛇尾**在点 $d$。满足 $1\le a

无

无

**本题采用捆绑测试。** - Subtask 1（10 points）：$n,q \le500$。 - Subtask 2（10 points）：$n\le10^5$，$q\le500$。 - Subtask 3（5 points）：所有 $x_i$ 都相等。 - Subtask 4（10 points）：所有询问中小 A 和小 B 的长度总和不超过 $5\times10^7$。 - Subtask 5（15 points）：$x_i$ 在 $[1,10^9]$ 内随机生成。 - Subtask 6（20 points）：$n\le5\times10^3$。 - Subtask 7（30 points）：无特殊限制。 对于 $100\%$ 的数据，$1\le n,q\le5\times10^5$，$1\le x_i\le10^9$，$1\le a