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

In a two-dimensional Cartesian coordinate system, you begin at the origin $(0,0)$. You are given a string $s$ of length $n$, representing a walking sequence. The $i$-th character $s_i$ belongs to the set $\{\texttt{U},\texttt{D},\texttt{L},\texttt{R}\}$. An infinitely long string $s'$ is constructed by repeating $s$ indefinitely. Formally, $s'_i = s_{((i - 1) \bmod n) + 1}$. Now, you process each character of $s'$ in order, moving according to the following rules: - If $s'_i = \texttt{U}$, move to $(x, y+1)$. - If $s'_i = \texttt{D}$, move to $(x, y-1)$. - If $s'_i = \texttt{L}$, move to $(x-1, y)$. - If $s'_i = \texttt{R}$, move to $(x+1, y)$. This process continues indefinitely. You are also given $m$ key points, where the $i$-th key point has coordinates $(p_i, q_i)$. Your task is to determine the number of $\textbf{distinct}$ key points that are visited during the infinite walking process.

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 5 \cdot 10^5$), the number of test cases. For each test case: - The first line contains two integers $n$ and $m$ ($1 \le n, m \le 5 \cdot 10^5$), where $n$ is the length of the string $s$ and $m$ is the number of key points. - The second line contains the string $s$ of length $n$. - The next $m$ lines each contain two integers $p_i$ and $q_i$ ($-10^9 \le p_i, q_i \le 10^9$), representing the coordinates of a key point. It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $5 \cdot 10^5$.

For each test case, output a single line containing a single integer, representing the number of distinct key points visited.

In the first test case, only two key points $(0,0)$ and $(0,-1)$ are visited. In the second test case, four key points $(0,0),(0,-1),(-1,0)$ and $(-1,1)$ are visited.