Rudolf and the Ball Game
Contest: Codeforces Round 933 (Div. 3)
Difficulty rating: 1200
Tags: dfs and similar, dp, implementation

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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 ?

Example output:
3
2 4 6 
1
11 
4
3 5 7 9 
3
2 3 5 
1
3

Editorial:
Let's introduce a set of unique elements $$$q$$$, initially containing a single element $$$x$$$ — the index of the first player who started the game. For each $$$i$$$ from $$$1$$$ to $$$m$$$, we will update $$$q$$$ in such a way as to maintain the set of players who could have the ball after the $$$i$$$-th throw. For each element $$$q_j$$$ of the set $$$q$$$, we will remove $$$q_j$$$ from $$$q$$$, and also:
• if $$$c_i = $$$"$$$0$$$" or $$$c_i = $$$"$$$?$$$", add to $$$q$$$ the element $$$\left( (q_j + r_i - 1)\ mod\ n + 1 \right)$$$ — the index of the player who will receive the ball in case of a clockwise throw;
• if $$$c_i = $$$"$$$1$$$" or $$$c_i = $$$"$$$?$$$", add to $$$q$$$ the element $$$\left( (q_j - r_i - 1 + n)\ mod\ n + 1 \right)$$$ — the index of the player who will receive the ball in case of a counterclockwise throw. The term $$$n$$$ before the $$$mod$$$ operation is necessary to obtain a positive argument of this operation. Otherwise, in some programming languages, the $$$mod$$$ function will return a negative result, which does not correspond to the semantics of the problem.
After the $$$m$$$-th iteration of the described cyclic process, the set $$$q$$$ will contain the desired indices of all players who could have the ball at the end of the game.
At each iteration of the loop, the power of $$$q$$$ does not exceed $$$n$$$, and a total of exactly $$$m$$$ iterations will be performed. Thus, the asymptotic complexity of the algorithm is of the order $$$O(n * m)$$$.