CF1941D.Rudolf and the Ball Game

Rudolf and Bernard decided to play a game with their friends. $n$ people stand in a circle and start throwing a ball to each other. They are numbered from $1$ to $n$ in the clockwise order.

Let's call a transition a movement of the ball from one player to his neighbor. The transition can be made clockwise or counterclockwise.

Let's call the clockwise (counterclockwise) distance from player $y_1$ to player $y_2$ the number of transitions clockwise (counterclockwise) that need to be made to move from player $y_1$ to player $y_2$. For example, if $n=7$ then the clockwise distance from $2$ to $5$ is $3$, and the counterclockwise distance from $2$ to $5$ is $4$.

Initially, the ball is with the player number $x$ (players are numbered clockwise). On the $i$-th move the person with the ball throws it at a distance of $r_i$ ($1 \le r_i \le n - 1$) clockwise or counterclockwise. For example, if there are $7$ players, and the $2$nd player, after receiving the ball, throws it a distance of $5$, then the ball will be caught by either the $7$th player (throwing clockwise) or the $4$th player (throwing counterclockwise). An illustration of this example is shown below.

The game was interrupted after $m$ throws due to unexpected rain. When the rain stopped, the guys gathered again to continue. However, no one could remember who had the ball. As it turned out, Bernard remembered the distances for each of the throws and the direction for some of the throws (clockwise or counterclockwise).

Rudolf asks you to help him and based on the information from Bernard, calculate the numbers of the players who could have the ball after $m$ throws.

鲁道夫和伯纳德决定和朋友们玩一个游戏。$n$ 个人围成一个圆圈，并开始互相抛球。他们按顺时针方向编号为 $1$ 到 $n$。

我们称一次“传递”为球从一名玩家传给其相邻玩家的动作。该传递可以是顺时针方向，也可以是逆时针方向。

我们定义玩家 $y_1$ 到玩家 $y_2$ 的“顺时针距离”（或“逆时针距离”）为：从玩家 $y_1$ 出发，沿顺时针方向（或逆时针方向）传递球所需经过的最少传递次数。例如，若 $n=7$，则玩家 $2$ 到玩家 $5$ 的顺时针距离为 $3$，而逆时针距离为 $4$。

初始时，球在编号为 $x$ 的玩家手中（玩家编号按顺时针顺序）。在第 $i$ 次传递中，持球者将球沿顺时针或逆时针方向传递 $r_i$（其中 $1 \le r_i \le n - 1$）个位置。例如，若有 $7$ 名玩家，且第 $2$ 号玩家接到球后将其传递 $5$ 个位置，则球将被第 $7$ 号玩家（顺时针传递）或第 $4$ 号玩家（逆时针传递）接住。该示例的图示如下：

由于突发降雨，游戏在进行了 $m$ 次传递后被迫中断。雨停后，大家重新聚集准备继续游戏，但无人记得此时球在谁手中。结果发现，伯纳德还记得每次传递的距离 $r_i$，以及其中部分传递的方向（顺时针或逆时针）。

鲁道夫请你帮忙，根据伯纳德提供的信息，计算出经过 $m$ 次传递后，球可能在哪些编号的玩家手中。

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case contains three integers $n, m, x$ ($2 \le n \le 1000$, $1 \le m \le 1000$, $1 \le x \le n$) — the number of players, the number of throws made, and the number of the player who threw the ball first, respectively.

The next $m$ lines contain information about each throw in order. Each of them contains an integer $r_i$ ($1 \le r_i \le n - 1$) — the distance at which the $i$-th throw was made, and a symbol $c_i$, equal to '0', '1', or '?':

• if $c_i$='0', then the $i$-th throw was made clockwise,
• if $c_i$='1', then the $i$-th throw was made counterclockwise,
• if $c_i$='?', then Bernard does not remember the direction and the $i$-th throw could have been made either clockwise or counterclockwise.

It is guaranteed that the sum $n \cdot m$ ($n$ multiplied by $m$) over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n, m, x$（$2 \le n \le 1000$，$1 \le m \le 1000$，$1 \le x \le n$），分别表示玩家数量、投球次数以及第一个投球的玩家编号。

接下来的 $m$ 行按顺序描述每次投球的信息。每行包含一个整数 $r_i$（$1 \le r_i \le n - 1$）——表示第 $i$ 次投球的距离，以及一个字符 $c_i$，其值为 '0'、'1' 或 '?'：

• 若 $c_i = \text{'0'}$，则第 $i$ 次投球为顺时针方向；
• 若 $c_i = \text{'1'}$，则第 $i$ 次投球为逆时针方向；
• 若 $c_i = \text{'?'}$，则 Bernard 不记得投球方向，第 $i$ 次投球可能为顺时针或逆时针方向。

保证所有测试用例中 $n \cdot m$（即 $n$ 与 $m$ 的乘积）之和不超过 $2 \cdot 10^5$。

For each test case, output two lines.

In the first line, output the number of players $k$ ($1 \le k \le n$) who could have the ball at the end of the game.

In the next line, output $k$ numbers $b_i$ ($1 \le b_i \le n$) — the numbers of the players in increasing order. All numbers must be different.

对于每个测试用例，输出两行。

第一行输出最终可能持球的玩家人数 $k$（$1 \le k \le n$）。

下一行输出 $k$ 个数 $b_i$（$1 \le b_i \le n$），表示这些玩家的编号，按升序排列。所有数字必须互不相同。

Below is an illustration of three throws for the first test case. The arrows denote possible throw directions. Players who could have the ball after the throw are highlighted in gray.

以下是第一个测试用例的三次传球示意图。箭头表示可能的传球方向。传球后可能持球的球员以灰色高亮显示。