2719 - 레이져 박스

• Submit
• Status
• Discuss
• Summary

Description

레이져는 일직선으로 쭉쭉 나아가다가 거울을 만나게되면 반사되는 성질을 가지고 있다. 여기 그 레이져의 성질을 이용해서 장난감을 하나 만들어둔게 있다. 바로 '레이져박스'이다.

레이져박스 내부는 nxn 격자로 이루어져있으며 내부에는 격자중 일부에 "right-turner"라 불리는 장치들로 구성되어있다. right-turner는 레이져가 들어온 방향이 어디가 됐든 오른쪽 90도 방향으로 꺽여져서 나가도록 만드는 장치이다. right turner 를 만들기 위해선 루비 6개를 준비하고, 더 이상의 자세한 설명은 생략한다.

 

 

레이져박스를 가지고 노는 방법은 다양하지만, 우리는 신사답게 레이져를 쏘면서 놀 것이다. 박스 바깥에서 레이져를 쐈을 때, 내부적으로 right-turner에 의해서 빛의 방향이 변경되다가 어디론가 밖으로 빠져나올 것이다. 레이져를 쏘는 위치에 따라서 이 밖으로 나오는 빛의 위치도 중구난방으로 달라질 것이다.

 

레이져박스에서 right-turner의 위치와 레이져를 발사한 곳의 위치가 주어졌을 때 빛이 어느위치에서 나올 것인지 계산하는 프로그램을 작성하시오.

Input

첫째줄에는 테스트케이스의 개수가 주어진다.

각 테스트케이스마다 첫 줄에는 n과 r이 주어진다. (1 ≤ n, r ≤ 50) n은 레이져박스의 크기를 나타내고 r은 right-turnner의 개수를 나타낸다.

이어서 r개의 줄에 걸쳐서 right-tunner의 위치가 x y 형태로 주어진다. x축과 y축은 문제에 그려진 그림에서 나와있는것을 따른다. (1 ≤ x, y ≤ n) right-tunner 2개가 같은 위치에 놓여지지 않는다.

테스트케이스의 마지막줄에는 레이져를 발사하는 위치값 x0 y0 이 주어진다. 이 위치는 레이져박스의 밖에 위치하며 발사방향은 레이져박스 내부를 향해서 발사한다고 한다. 또 레이져박스의 모서리보다 정확히 1칸 떨어져있는 위치로 주어진다. 예를 들어 바닥에서 x0=6인 위치에서 위쪽을 향해 레이져를 쏜다면, 6 0 으로 들어올 것이고, 오른쪽 면에서 y0=7인 위치에서 왼쪽을 향해 레이져를 쏜다면 n+1 7이 들어올 것이다. 0 0 이나 n+1 n+1 같이 레이져의 내부 방향이 대각선인 입력은 들어오지 않는다. (0 ≤ x0, y0 ≤ n+1) 

Output

각 테스트케이스마다 레이져가 빠져나오는 위치를 출력한다. 레이져를 발사하는 위치값과 동일한 형태로, 그러니까 x값이 0 또는 n+1 이거나, y값이 0 또는 n+1이 되는 형태로 출력한다. 만약 레이져가 밖으로 나우지 못하는 경우에는 0 0 을 출력한다.

Sample Input

2
2 3
1 1
1 2
2 2
3 1
3 6
1 1
1 3
2 2
2 3
3 1
3 2
2 0

Sample Output

2 0
0 2