Description

Rudolf和Bernard决定和他们的朋友们玩一个游戏。有n个人站成一个圆圈，开始互相传球。他们按顺时针顺序从1到n编号。

我们把传球的过程称为一个转移，即球从一个球员传给他的邻居。转移可以顺时针或逆时针进行。

我们把从球员y1到球员y2的顺时针（逆时针）距离定义为需要进行的顺时针（逆时针）转移次数，以从球员y1到球员y2移动为例。例如，如果n=7，那么从2到5的顺时针距离是3，逆时针距离从2到5是4。

最初，球在编号为x的球员手中（球员按顺时针编号）。在第i次传球时，持球者将球传递ri（1≤ri≤n−1）的距离，可以是顺时针或逆时针。例如，如果有7个球员，第2个球员在接到球后传递了5的距离，那么球将被第7个球员（顺时针传球）或第4个球员（逆时针传球）接住。下面是这个例子的示意图。

由于突然下雨，游戏在m次传球后中断。雨停后，伙伴们再次聚在一起继续游戏。然而，没有人记得谁持球。结果，Bernard记得每次传球的距离以及一些传球的方向（顺时针或逆时针）。

Rudolf请你帮忙，根据Bernard提供的信息，计算在m次传球后可能持球的球员编号。

输入

输入的第一行包含一个整数t（1≤t≤1e4） — 测试用例的数量。然后是每个测试用例的描述。

每个测试用例的第一行包含三个整数n,m,x（2≤n≤1000,1≤m≤1000，1≤x≤n） — 球员数量，传球次数，以及首次传球的球员编号。

接下来的m行包含每次传球的信息。每行包含一个整数ri（1≤ri≤n−1） — 第i次传球的距离，以及一个符号ci，可以是'0'、'1'或'?'：

• 如果ci='0'，则第i次传球是顺时针进行的，
• 如果ci='1'，则第i次传球是逆时针进行的，
• 如果ci='?'，则Bernard不记得方向，第i次传球可以是顺时针或逆时针进行。

保证所有测试用例的总和n⋅m（n乘以m）不超过2e5。

输出

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

第一行输出可能持球的球员数量k（1≤k≤n）。

接下来一行输出k个球员编号bi（1≤bi≤n） — 按升序排列的球员编号。所有编号必须不同。

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

Note

下面是第一个测试用例的三次传球的示意图。箭头表示可能的传球方向。接到传球后可能持球的球员用灰色标出。