Keivan 即将出国留学。他邀请了所有的朋友到一家餐馆举行告别派对。他要求他们在派对前两周待在家里，以确保他们中没有人感染冠状病毒。

为了让派对简短，Keivan 预订了一张圆桌，指定了每个人的座位，并将客人的餐点放在了他们的座位前。派对结束后，每个人都享受了美食。不幸的是，一些客人在派对后立即发烧了。因此，Keivan 要求他们所有人再次进行 PCR 检测。检测结果并不如所有人所愿。冠状病毒感染了一些朋友。我们知道 PCR 检测可能会出现假阴性，但绝不会出现假阳性。这意味着如果一个人的检测结果为阴性，他可能是健康的，也可能已经感染了冠状病毒。但是，检测结果为阳性的人肯定感染了病毒。

现在，Keivan 很困惑。他不知道他的朋友们是如何生病的。餐馆经理告诉他，他的朋友中恰好有一人点了蝙蝠汤。他决心找出那些可能点了这道汤的人。因此，他要求查看监控录像。不幸的是，餐馆的闭路电视拍摄的视频质量很低，很难看清他们的餐点。然而，他可以看到他们的活动和时间。通过这些活动，他想找出那些可能点了蝙蝠汤并传播了冠状病毒的人。

Keivan 按时间顺序记录了他朋友们的活动。每项活动都表明一个人与他相邻的邻居进行了交谈。我们知道，喝了蝙蝠汤的人会立即感染病毒。此后，如果一个生病的人与他的邻居交谈，第二个人就会生病。除此之外，没有其他病毒传播途径。

输入格式

第一行包含三个正整数 $n, m$ 和 $q$ ($1 \le m \le n \le 10^5, 1 \le q \le 10^5$)，分别表示客人的数量、生病客人的数量以及客人活动的总数。客人按顺时针方向编号为 $1$ 到 $n$。这意味着客人 $i+1$ 是客人 $i$ 的左邻（客人 $1$ 坐在客人 $n$ 的左侧）。下一行包含 $m$ 个不同的整数 $a_i$ ($1 \le a_i \le n$)，每个整数表示一名感染了冠状病毒的客人。

接下来的 $q$ 行按时间先后顺序描述了客人的活动。每行包含一个整数 $b_i$ ($1 \le b_i \le n$) 和一个字符 $c_i$ ($c_i \in \{L, R\}$)。这表示客人 $b_i$ 与他的左侧 ($L$) 或右侧 ($R$) 的人交谈。

输出格式

按升序在一行中打印所有可能点了蝙蝠汤的客人。

样例

样例输入 1

3 1 3
2
1 L
2 L
3 L

样例输出 1

1 2

样例输入 2

3 2 2
2 3
1 R
3 R

样例输出 2

1 3