31574번 - 개미와 비트코인

문제

$N$마리의 개미가 각자 전 재산을 끌어 모아서 1BTC의 비트코인을 샀다 비트코인은 개미 모두의 것이기 때문에 개미들은 비트코인을 돌려가면서 관리하려고 한다.

개미들은 모두 길이 $L$인 막대에 서 있으며 왼쪽 또는 오른쪽을 바라보고 있다. 막대의 가장 왼쪽 끝 지점의 좌표는 이며 가장 오른쪽 끝 지점의 좌표는 $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, \cdot\cdot\cdot, N$번 개미의 정보가 주어진다. 각 줄마다 개미의 위치(좌표)와 이동방향이 주어진다. 개미의 위치는 1ドル$ 이상 $L-1$ 이하의 정수이며 서로 다르다. 개미의 이동방향은 L (왼쪽) 또는 R (오른쪽) 로 주어진다.

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

출력

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

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

제한

힌트