거울 뒤의 화면

악마 박승원은 세계에서 가장 강력한 레이저를 찾고 있으며, 그 일을 당신에게 맡겼다. 당신에게는 레이저 시제품이 있지만, 제작 예산을 받으려면 먼저 시뮬레이션 결과를 박승원에게 보여 주어야 한다.

시뮬레이션은 2차원 평면 위에 "거울", "광선 스플리터", "광선 감지기"를 배치하면서 시작한다. 각 물체는 하나의 선분으로 표현된다.

• 거울(M): 광선이 거울에 닿으면 거울 선분에 대해 반사되어 진행한다.
• 감지기(D): 들어오는 광선을 흡수한다.
• 스플리터(S): 들어오는 광선을 두 개로 나눈다. 하나는 스플리터를 그대로 통과하여 방향이 바뀌지 않고, 다른 하나는 스플리터 선분에 대해 반사되어 진행한다.

시작점과 방향이 주어진 레이저를 발사했을 때, 어떤 감지기들이 광선을 흡수하는지 구하라. 문제를 단순화하기 위해 다음을 가정한다.

• 시뮬레이션은 한 변의 길이가 $100$인 정사각형 구역만 다루면 되며, 모든 물체는 이 구역 안에 있다.
• 주어지는 선분들은 서로 겹치거나 만나지 않는다.
• 레이저는 정사각형 구역의 가장자리에서 발사된다.
• 모든 광선이 구역 밖으로 빠져나가거나 감지기에 흡수되면 시뮬레이션이 끝난다.
• 시뮬레이션 전체에서 레이저 광선의 반사 횟수는 $100$번 미만이다.
• 감지기는 최소 $1$개 존재한다.
• 시뮬레이션 도중 레이저 광선이 어떤 물체와 한 직선 위에 놓이는 경우는 없다.

첫째 줄에 테스트 케이스의 수 $N$이 주어진다. 각 테스트 케이스는 다음과 같이 구성된다.

• 첫째 줄에 "x,y i,j" 형식으로 레이저의 시작점 $(x, y)$와 방향 벡터 $(i, j)$가 주어진다. 시작점은 구역 가장자리 위의 한 점이다. 모든 수는 정수이며 $-1024 \le i, j \le 1024$이다.
• 둘째 줄에 물체의 수 $P$가 주어진다. $(1 \le P \le 100)$
• 이어지는 $P$개의 줄에 물체가 하나씩 주어진다. 각 줄은 물체의 종류를 나타내는 문자로 시작하며, "M"은 거울, "S"는 스플리터, "D"는 감지기를 뜻한다. 그 뒤에 선분의 두 끝점이 각각 "x,y" 형식으로 주어진다.
• 물체는 입력에 등장한 순서대로 $1$번부터 $P$번까지 번호가 매겨진다.

각 테스트 케이스마다 먼저 "DATA SET #k"를 출력한다. 여기서 $k$는 테스트 케이스 번호($1$부터 시작)이다.

광선을 흡수한 감지기가 하나도 없으면 "NO BEAMS DETECTED"를 출력한다.

그렇지 않으면, 광선을 흡수한 감지기의 번호(입력에서의 물체 번호)를 오름차순으로 한 줄에 하나씩 출력한다. 같은 감지기가 여러 광선을 흡수하더라도 번호는 한 번만 출력한다.

Enigma - The Screen Behind The Mirror