Rudolf and the Ball Game

### 题目描述 $n$ 个人站成一个圈，按照顺时针编号依次是 $1$ 到 $n$。 现在这 $n$ 个人玩一个传球游戏，第 $i$ 次传球可以向顺时针方向传给与自己距离为 $d_i$ 的距离，或者向逆时针方向传给与自己距离为 $r_i$ 的距离。 游戏总共进行了 $m$ 轮传球，给你初始拿到球的人的编号 $x$ 和每次传球的方向和距离 $r_i$（有可能方向未知），求出最后可能是谁拿到了球，**按编号从小到大**输出。 ------------ ### 输入格式 **本题有多组数据**。 第一行一个整数 $t$，表示测试用例的数量。 对于每一组测试用例： 第一行三个整数 $n,m,x$。 接下来 $m$ 行包含每次的传球信息：传球的距离 $r_i$，以及传球的方向 $c_i$： - $c_i=$ '0'，则这次传球为顺时针； - $c_i=$ '1'，则这次传球为逆时针； - $c_i=$ '?'，则这次传球方向未知，可以是顺时针也可以是逆时针。 ------------ ### 输出格式 对于每一组数据，共两行： 第一行一个整数 $k$，表示最后可能拿到球的人的数量。 第二行 $k$ 个整数，表示最后可能拿到球的人的编号 ------------ ### 说明/提示 #### 样例解释 下面是第一个测试用例的三次传球的示意图。箭头表示可能的传球方向。在传球后可能持有球的玩家被标记为灰色。    ------------ #### 数据范围 对于 $100\%$ 的数据，$1 \le t \le 1000,1 \le x \le n \le 1000,1 \le m \le 1000,1 \le n\cdot m \le 2\cdot10^5,1 \le r_i \le n-1$。

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.

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 $ .

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.

5
6 3 2
2 ?
2 ?
2 ?
12 1 2
3 1
10 7 4
2 ?
9 1
4 ?
7 0
2 0
8 1
5 ?
5 3 1
4 0
4 ?
1 ?
4 1 1
2 ?

3
2 4 6 
1
11 
4
3 5 7 9 
3
2 3 5 
1
3

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.