도미노 킬링

어릴 때 자주 하던 놀이 중 하나가 도미노다. 타일에 적힌 수를 맞춰 바닥에 늘어놓는 원래 게임이 아니라, 타일을 세워 길게 늘어놓고 맨 앞을 밀어 전부 쓰러뜨리는 그 놀이다.

배치가 어긋나면 전부 넘어지지는 않는다. 도미노 배치와 처음 미는 방향이 주어질 때 몇 개가 넘어지는지 구하라.

도미노는 판 위의 정수 좌표에 서 있다. $x$축은 왼쪽에서 오른쪽으로, $y$축은 위에서 아래로 향한다. 위에서 내려다보면 도미노는 짧은 선분으로 보이고, 놓인 방향은 |, -, /, \ 네 가지다.

그림의 검은 선은 도미노의 윗면이고, 붉은 표시는 그 도미노가 넘어질 자리다. 도미노는 자기 선분과 수직인 두 방향 중 한쪽으로 넘어지며, 정확히 한 칸 옆에 눕는다. $(x, y)$에 선 도미노가 눕는 칸은 다음과 같다.

• |: $(x-1, y)$ 또는 $(x+1, y)$
• -: $(x, y-1)$ 또는 $(x, y+1)$
• /: $(x-1, y-1)$ 또는 $(x+1, y+1)$
• \: $(x+1, y-1)$ 또는 $(x-1, y+1)$

도미노의 크기는 자기가 눕는 칸에 선 도미노 하나만 밀도록 정해져 있다. 밀린 도미노는 자신의 두 방향 중 들어온 방향과 내적이 양수인 쪽으로 넘어진다.

넘어지는 도미노가 자신과 90도를 이루는 도미노를 치면 그 도미노는 넘어지지 않는다. 친 쪽은 넘어진 것으로 센다. 90도를 이루는 짝은 |와 -, 그리고 /와 \뿐이다. 90도가 아닌 두 도미노 사이에서는 내적이 0이 되지 않으므로 넘어질 방향이 하나로 정해진다.

이미 넘어진 도미노를 다시 밀면 아무 일도 일어나지 않는다.

문제 이름은 이 놀이의 일본어 이름인 ドミノ倒し를 어떤 번역기가 옮긴 결과에서 왔다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스의 첫 줄에는 정수 네 개가 공백으로 구분되어 주어진다. 도미노의 개수 $N$ ($1 \le N \le 100000$), 처음 밀리는 도미노의 번호 $S$ ($0 \le S < N$, 도미노는 입력에 나온 순서대로 0번부터 센다), 그리고 미는 방향인 $F_x$와 $F_y$이며 $F_x$와 $F_y$는 각각 -1, 0, 1 중 하나다.

이어지는 $N$개의 줄에는 도미노 하나가 정수 두 개와 기호 하나로 주어진다. 정수는 도미노의 좌표 $x$와 $y$ ($0 \le x, y \le 100000$)이고, 기호는 위에서 내려다본 방향으로 |, -, /, \ 중 하나다. 같은 칸에 도미노가 둘 이상 서 있는 경우는 없다.

$(F_x, F_y)$는 항상 $S$번 도미노가 넘어질 수 있는 두 방향 중 하나다. 예를 들어 $S$번 도미노의 방향이 |이면 $(F_x, F_y)$는 $(1, 0)$ 또는 $(-1, 0)$이다.

마지막 줄에는 0이 네 개 주어진다. 이 줄은 케이스가 아니므로 처리하지 않는다.

각 케이스마다 넘어지는 도미노의 개수를 한 줄에 출력한다. 처음 밀린 도미노도 개수에 포함한다.

첫 번째 케이스에서는 맨 위의 도미노를 방향 $(0, 1)$, 그림에서 아래쪽으로 민다. 다음 도미노가 넘어지고 그 다음 도미노가 이어서 넘어져 네 개가 모두 눕는다.

두 번째 케이스에서는 $(0, 1)$의 도미노를 방향 $(0, 1)$로 민다. $(0, 2)$의 도미노가 넘어지고 이어서 $(1, 3)$의 도미노가 넘어지며, 결국 여덟 개가 모두 눕는다. $(1, 0)$의 도미노가 넘어질 때 $(0, 1)$의 도미노는 이미 누워 있으므로 더 이상 아무 일도 일어나지 않는다.

세 번째 케이스에서는 $(1, 0)$의 도미노를 오른쪽으로 민다. $(2, 0)$과 $(3, 1)$의 도미노만 넘어진다. $(4, 2)$의 도미노는 $(3, 1)$의 도미노에 밀리지만 90도를 이루고 있어 넘어지지 않는다.