시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

레이저박스라는 게임은 정사각형  모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 설치되어 있다. 레이저는 판의 끝에만 설치 될 수 있는데, 행의 맨 아래/맨 위, 열의 오른쪽 끝/왼쪽 끝에 설치 될 수 있다. 레이저에서 나온 빔은 그 행 혹은 열을 질러서 반대쪽을 비춘다.

게임은 우향우 거울을 임의의 칸마다 설치한 후, 레이저를 배치를 해 놓은 이후에 시작한다. 레이저를 켰을 때 나온 빔이 우향우 거울을 통과하면 진입한 방향과는 관계 없이 오른쪽으로 90도를 꺾어 다시 나아간다. 

레이저 빔이 마지막으로 어느 좌표를 향해 비춰지는지 구하라.

입력

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

테스트케이스의 첫 줄에는 보드의 크기 n(1 ≤ n ≤ 50)과 우향우 거울의 갯수 r(1 ≤ r ≤ 50)이 주어진다.

이어지는 r개의 줄에는 우향우 거울이 배치된 좌표 x y가 주어진다.(좌표는 1부터 시작한다) 중복된 좌표는 있을 수 없고, 매 칸마다 최대 1개의 우향우 거울이 놓일 수 있다.

마지막 줄에는 레이저의 좌표가 주어진다. 레이저는 행과 열의 끝, 즉 판 밖에 위치해야 하므로 레이저의 좌표에는 0 혹은 n + 1이 포함된다. 

예를 들어, 2x2보드의 1행 맨 밑에서 위로 쏘아지는 레이저의 좌표는 (3, 1)로써 주어진다. 마찬가지로 6x6보드의 6열 왼쪽 끝에서 오른쪽 끝으로 쏘아지는 레이저의 좌표는 (6, 0)이 되겠다.

출력

매 테스트케이스마다 빔이 보드를 떠나는 좌표 X Y를 출력하라. 레이저의 좌표와 마찬가지로 빔은 보드 밖으로 떠나기에 좌표에는 0 혹은 n + 1이 포함된다. 

만약 빔이 보드 밖을 떠나지 않을 경우의 출력은 0 0이 된다.

예제 입력

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

예제 출력

2 0
0 2

힌트