마지막 만찬

키반은 유학을 떠나기 위해 나라를 떠나게 되었다. 그는 송별회를 열려고 친구들을 모두 식당으로 초대했다. 파티 날 전 2주 동안은 집에 머물러 달라고 부탁해, 친구 중 아무도 코로나바이러스에 감염되지 않았는지 확인하려 했다.

파티를 짧게 끝내기 위해 키반은 둥근 테이블을 예약하고, 한 사람씩 앉을 자리를 정했으며, 각 손님이 주문한 음식을 자리 앞에 놓아 두었다. 파티가 끝나고 모두 음식을 즐겼다. 그런데 파티 직후 열이 난 손님들이 있었다. 그래서 키반은 이들 모두에게 PCR 검사를 다시 받아 달라고 했다. 결과는 아무도 바라지 않았던 쪽이었다. 친구 몇 명이 코로나바이러스에 감염된 것이다.

PCR 검사는 거짓 음성이 나올 수 있지만 거짓 양성은 나오지 않는다. 따라서 음성 결과를 받은 사람은 건강하거나 감염된 상태이다. 양성 결과를 받은 사람은 반드시 감염된 것이다.

키반은 친구들이 어떻게 병에 걸렸는지 알지 못한다. 식당 매니저는 친구 중 정확히 한 명이 박쥐 수프를 주문했다고 알려 주었다. 키반은 이 수프를 주문했을 가능성이 있는 사람을 모두 찾으려 한다. 식당 CCTV 영상은 화질이 낮아 주문 내용은 보이지 않지만, 각자의 행동과 시각은 확인할 수 있다. 키반은 이 행동 기록으로 박쥐 수프를 주문해 바이러스를 퍼뜨렸을 수 있는 사람을 찾으려 한다.

키반은 친구들의 행동을 시간 순서대로 기록했다. 각 행동은 한 사람이 양옆 이웃 중 한 명과 대화했다는 뜻이다. 박쥐 수프를 먹은 사람은 즉시 감염된다. 이후 감염된 사람이 이웃과 대화하면 그 이웃도 감염된다. 바이러스가 퍼지는 경로는 이것뿐이다.

첫 줄에는 양의 정수 n, m, q가 주어진다 (1 ≤ m ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5). 각각 손님 수, 감염된 손님 수, 행동 기록 수이다. 손님은 시계 방향으로 1부터 n까지 번호가 매겨져 있다. 즉 i+1번 손님은 i번 손님의 왼쪽 이웃이며, 1번 손님은 n번 손님의 왼쪽 의자에 앉아 있다.

둘째 줄에는 서로 다른 정수 a_i (1 ≤ a_i ≤ n) m개가 주어진다. 각 값은 코로나바이러스에 감염된 손님의 번호이다.

다음 q개의 줄에는 시간 순서대로 행동이 주어진다. 각 줄에는 정수 b_i (1 ≤ b_i ≤ n)와 문자 c_i ∈ {L, R}가 주어지며, 이는 손님 b_i가 왼쪽(L) 또는 오른쪽(R) 이웃과 대화했음을 뜻한다.

박쥐 수프를 주문했을 수 있는 손님을 모두 오름차순으로 한 줄에 출력한다.