鲁道夫和伯纳德决定和他们的朋友玩一个游戏。 $$$n$$$ 人们站成一圈,开始互相扔球。它们按顺时针顺序从 $$$1$$$ 到 $$$n$$$ 编号。
我们将球从一名球员传给他的邻居的运动称为转换。可以顺时针或逆时针进行过渡。
我们将从玩家 $$$y_1$$$ 到玩家 $$$y_2$$$ 的顺时针(逆时针)距离称为从玩家 $$$y_1$$$ 移动到玩家 $$$y_2$$$ 所需的顺时针(逆时针)转换次数。例如,如果 $$$n=7$$$,则从 $$$2$$$ 到 $$$5$$$ 的顺时针距离为 $$$3$$$,从 $$$2$$$ 到 $$$5$$$ 的逆时针距离为 $$$4$$$。
最初,球的编号为 $$$x$$$(玩家按顺时针方向编号)。在第 $$$i$$$ 次移动中,持球者顺时针或逆时针将球扔到 $$$r_i$$$ ($$$1 \le r_i \le n - 1$$$) 的距离处。例如,如果有 $$$7$$$ 玩家,第 $$$2$$$ 玩家接球后将球扔出 $$$5$$$ 距离,则球将被第 $$$7$$$ 玩家(顺时针投掷)或第 $$$4$$$ 玩家(逆时针投掷)接住。该示例的图示如下所示。
由于意外下雨,比赛在 $$$m$$$ 投掷后中断。雨停了,大家又聚在一起继续前行。然而,没有人记得谁拿球。事实证明,伯纳德记住了每次投掷的距离以及某些投掷的方向(顺时针或逆时针)。
鲁道夫请你帮助他,并根据伯纳德提供的信息,计算在 $$$m$$$ 投掷后可以拿球的球员数量。
输入
输入的第一行包含一个整数 $$$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$$$='0',则第 $$$i$$$ 次投掷是顺时针方向进行的,
- 如果 $$$c_i$$$='1',则第 $$$i$$$ 次抛出是逆时针进行的,
- 如果 $$$c_i$$$='?',则伯纳德不记得方向,并且第 $$$i$$$ 次投掷可能是顺时针或逆时针进行的。
保证所有测试用例的总和 $$$n \cdot m$$$ ($$$n$$$ 乘以 $$$m$$$)不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出两行。
第一行,输出比赛结束时可以控球的球员人数 $$$k$$$ ($$$1 \le k \le n$$$)。
在下一行中,输出 $$$k$$$ 个数字 $$$b_i$$$ ($$$1 \le b_i \le n$$$) — 按升序排列的玩家编号。所有数字必须不同。
示例
输入 #1
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 ?
输出 #1
3 2 4 6 1 11 4 3 5 7 9 3 2 3 5 1 3
注意
下面是第一个测试用例的三次抛出的说明。箭头表示可能的投掷方向。投球后可以持球的球员以灰色突出显示。