← 返回题目列表

Codeforces · 1941/D

D. 鲁道夫和球类游戏

中文机器翻译题面 查看原题

鲁道夫和伯纳德决定和他们的朋友玩一个游戏。 $$$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

注意

下面是第一个测试用例的三次抛出的说明。箭头表示可能的投掷方向。投球后可以持球的球员以灰色突出显示。