폭발하는 공

좌표평면 위에 여러 개의 공이 있다. 각 공은 위, 아래, 왼쪽, 오른쪽 중 하나의 방향으로만 움직이며, 모든 공의 속도는 초당 1이다. 공의 움직임은 연속적이므로, 예를 들어 1/3초 동안 공은 1/3만큼 이동한다.

두 개 이상의 공이 같은 시각에 같은 위치에 도착하면 그 공들은 폭발하여 사라진다. 이미 사라진 공은 이후의 충돌에 참여하지 않는다.

각 공의 시작점과 이동 방향이 주어졌을 때, 절대로 폭발하지 않는 공의 번호를 구하시오.

첫째 줄에 공의 개수 N이 주어진다. (2 <= N <= 500)

둘째 줄부터 N개의 줄에는 각 공의 시작 좌표와 이동 방향이 주어진다. 시작 좌표는 0 이상 100,000,000 이하인 정수이고, 방향은 up, down, left, right 중 하나이다.

서로 다른 두 공이 같은 시작 좌표를 갖는 경우는 없다.

절대로 폭발하지 않는 공의 번호를 작은 번호부터 한 줄에 하나씩 출력한다. 입력에서 첫 번째로 주어진 공의 번호는 1, 두 번째로 주어진 공의 번호는 2이며, 이후 공들도 같은 방식으로 번호가 붙는다.

모든 공이 폭발한다면 all을 출력한다.