개미와 비트코인

$N$마리의 개미가 각자 전 재산을 모아 1BTC의 비트코인을 샀다. 비트코인은 개미 모두의 것이므로 개미들은 비트코인을 돌려가며 관리하려고 한다.

개미들은 모두 길이 $L$인 막대 위에 서 있으며 왼쪽 또는 오른쪽을 바라보고 있다. 막대의 가장 왼쪽 끝 좌표는 0이고 가장 오른쪽 끝 좌표는 $L$이다. 모든 개미는 정수 좌표에 서 있으며, 같은 곳에 있는 개미는 없다.

개미는 바라보는 방향으로 1초에 1만큼 움직인다. 개미가 막대의 끝에 도달하면 방향을 바꿔 다시 걷는다. 두 개미가 만나면(같은 좌표에 있으면) 두 개미 모두 방향을 바꾼다. 비트코인을 가진 개미가 다른 개미와 만나면, 비트코인을 그 개미에게 건네고 방향을 바꾼다. 방향을 바꾸거나 비트코인을 건네는 데는 시간이 걸리지 않는다.

위 그림은 비트코인을 가진 개미를 포함해 네 마리의 개미가 있는 상황이다. 잠시 시간이 지나면 아래 그림의 상황이 된다.

그림에서 첫 번째 개미와 두 번째 개미가 만났고, 네 번째 개미는 막대의 끝에 도달했다. 따라서 세 번째 개미를 제외한 모든 개미가 방향을 바꾼다.

이후 조금 지나면 세 번째 개미와 네 번째 개미가 만난다. 세 번째 개미가 비트코인을 가지고 있으므로, 네 번째 개미에게 비트코인을 준 뒤 방향을 바꾼다.

개미들은 $T$초 후에 어떤 개미가 비트코인을 갖고 있을지 알고 싶어 한다. 개미들의 정보가 주어졌을 때, $T$초 후에 비트코인을 갖고 있는 개미의 번호를 구하는 프로그램을 작성하라. 개미는 매우 작아서 점으로 간주해도 무방하다.

첫 번째 줄에 개미의 수 $N$, 막대의 길이 $L$, 시간 $T$가 주어진다. ($1 \le N \le 100\,000$, $1 \le L, T \le 1\,000\,000\,000$, $N+1 \le L$)

두 번째 줄부터 $N$개의 줄에는 $1, 2, \cdots, N$번 개미의 위치(좌표)와 이동 방향이 주어진다. 개미의 위치는 1 이상 $L-1$ 이하의 정수이며 서로 다르다. 이동 방향은 L(왼쪽) 또는 R(오른쪽)이다.

마지막 줄에는 비트코인을 갖고 있는 개미의 번호가 1 이상 $N$ 이하의 정수로 주어진다.

$T$초 후에 비트코인을 갖고 있는 개미의 번호를 출력한다.

$T$초가 지난 상황에서 모든 개미의 위치가 서로 다르다는 것은 보장된다.