P14445 [ICPC 2025 Xi'an Practice] Follow the Sequence

在一个二维笛卡尔坐标系中，你从原点 $(0,0)$ 出发。 给定一个长度为 $n$ 的字符串 $s$，表示一段行走指令序列。第 $i$ 个字符 $s_i$ 属于集合 $\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\}$。 将字符串 $s$ 无限次重复，构造出一条无限长的字符串 $s'$。形式化地，$s'_i = s_{((i - 1) \bmod n) + 1}$。 接着你依次处理 $s'$ 的每个字符，按照如下规则移动： - 若 $s'_i = \texttt{U}$，则移动至 $(x, y+1)$。 - 若 $s'_i = \texttt{D}$，则移动至 $(x, y-1)$。 - 若 $s'_i = \texttt{L}$，则移动至 $(x-1, y)$。 - 若 $s'_i = \texttt{R}$，则移动至 $(x+1, y)$。 这一过程将无限持续下去。你还被给定了 $m$ 个关键点，其中第 $i$ 个关键点的坐标为 $(p_i, q_i)$。你的任务是求出在无限行走过程中被访问到的 **不同的** 关键点数量。

输入包含多个测试用例。第一行是一个整数 $t$（$1 \leq t \leq 5 \cdot 10^5$），表示测试用例个数。对每个测试用例： - 第一行包含两个整数 $n$ 与 $m$（$1 \le n, m \le 5 \cdot 10^5$），分别表示字符串 $s$ 的长度和关键点的数量。 - 第二行包含长度为 $n$ 的字符串 $s$。 - 接下来的 $m$ 行中，每行包含两个整数 $p_i$ 和 $q_i$（$-10^9 \le p_i, q_i \le 10^9$），表示一个关键点的坐标。 保证所有测试用例中 $n$ 的总和以及 $m$ 的总和均不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一行，包含一个整数，表示被访问到的不同关键点数量。

在第一个测试用例中，仅有两个关键点 $(0,0)$ 与 $(0,-1)$ 会被访问到。 在第二个测试用例中，有四个关键点 $(0,0)$、$(0,-1)$、$(-1,0)$ 与 $(-1,1)$ 会被访问到。 翻译由 ChatGPT-5 完成