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

문제

레이저박스라는 게임은 정사각형  모양의 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이 된다.

예제 입력 1

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

예제 출력 1

2 0
0 2
W3sicHJvYmxlbV9pZCI6IjM3MDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4MDhcdWM3NzRcdWM4MDBcdWJlNTRcdWM3NDAgXHVjNWI0XHViNTE0XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI4MDhcdWM3NzRcdWM4MDBcdWJjMTVcdWMyYTRcdWI3N2NcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSAmbmJzcDtcdWJhYThcdWM1OTFcdWM3NTggbiB4IG4gXHViY2Y0XHViNGRjXHVjNWQwXHVjMTFjIFx1YzljNFx1ZDU4OVx1ZDU1Y1x1YjJlNC4gKFx1Y2NiNFx1YzJhNFx1ZDMxMFx1Yzc0NCBcdWMwYzFcdWMwYzFcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0KSBcdWI4MDhcdWM3NzRcdWM4MDBcdWJjMTVcdWMyYTRcdWM3NTggXHVjNzg0XHVjNzU4XHVjNzU4IFx1Y2U3OFx1YjljOFx1YjJlNCBcdWM2YjBcdWQ1YTVcdWM2YjAgXHVhYzcwXHVjNmI4XHVjNzc0XHViNzdjXHViMjk0IFx1YzdhNVx1Y2U1OFx1YWMwMCBcdWMxMjRcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwLCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHViODA4XHVjNzc0XHVjODAwIFx1ZDU1Y1x1YWMxY1x1YWMwMCBcdWMxMjRcdWNlNThcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWI4MDhcdWM3NzRcdWM4MDBcdWIyOTQgXHVkMzEwXHVjNzU4IFx1YjA1ZFx1YzVkMFx1YjljYyBcdWMxMjRcdWNlNTggXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1ZDU4OVx1Yzc1OCBcdWI5ZTggXHVjNTQ0XHViNzk4XC9cdWI5ZTggXHVjNzA0LCBcdWM1ZjRcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1YjA1ZFwvXHVjNjdjXHVjYWJkIFx1YjA1ZFx1YzVkMCBcdWMxMjRcdWNlNTggXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjgwOFx1Yzc3NFx1YzgwMFx1YzVkMFx1YzExYyBcdWIwOThcdWM2MjggXHViZTU0XHVjNzQwIFx1YWRmOCBcdWQ1ODkgXHVkNjM5XHVjNzQwIFx1YzVmNFx1Yzc0NCBcdWM5YzhcdWI3ZWNcdWMxMWMgXHViYzE4XHViMzAwXHVjYWJkXHVjNzQ0IFx1YmU0NFx1Y2Q5OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIFx1YzZiMFx1ZDVhNVx1YzZiMCBcdWFjNzBcdWM2YjhcdWM3NDQgXHVjNzg0XHVjNzU4XHVjNzU4IFx1Y2U3OFx1YjljOFx1YjJlNCBcdWMxMjRcdWNlNThcdWQ1NWMgXHVkNmM0LCBcdWI4MDhcdWM3NzRcdWM4MDBcdWI5N2MgXHViYzMwXHVjZTU4XHViOTdjIFx1ZDU3NCBcdWIxOTNcdWM3NDAgXHVjNzc0XHVkNmM0XHVjNWQwIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHViODA4XHVjNzc0XHVjODAwXHViOTdjIFx1Y2YzMFx1Yzc0NCBcdWI1NGMgXHViMDk4XHVjNjI4IFx1YmU1NFx1Yzc3NCBcdWM2YjBcdWQ1YTVcdWM2YjAgXHVhYzcwXHVjNmI4XHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YmE3NCBcdWM5YzRcdWM3ODVcdWQ1NWMgXHViYzI5XHVkNWE1XHVhY2ZjXHViMjk0IFx1YWQwMFx1YWNjNCBcdWM1YzZcdWM3NzQgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIDkwXHViM2M0XHViOTdjIFx1YWViZVx1YzViNCBcdWIyZTRcdWMyZGMgXHViMDk4XHVjNTQ0XHVhYzA0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI4MDhcdWM3NzRcdWM4MDAgXHViZTU0XHVjNzc0IFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyBcdWM1YjRcdWIyOTAgXHVjODhjXHVkNDVjXHViOTdjIFx1ZDVhNVx1ZDU3NCBcdWJlNDRcdWNkYjBcdWM5YzBcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjZDFkIFx1YWMyZlx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWQwNmNcdWFlMzAgbigxICZsZTsgbiAmbGU7IDUwKVx1YWNmYyBcdWM2YjBcdWQ1YTVcdWM2YjAgXHVhYzcwXHVjNmI4XHVjNzU4IFx1YWMyZlx1YzIxOCByKDEgJmxlOyByICZsZTsgNTApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IHJcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzZiMFx1ZDVhNVx1YzZiMCBcdWFjNzBcdWM2YjhcdWM3NzQgXHViYzMwXHVjZTU4XHViNDFjIFx1Yzg4Y1x1ZDQ1YyB4IHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LihcdWM4OGNcdWQ0NWNcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQpIFx1YzkxMVx1YmNmNVx1YjQxYyBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWFjZTAsIFx1YjllNCBcdWNlNzhcdWI5YzhcdWIyZTQgXHVjZDVjXHViMzAwIDFcdWFjMWNcdWM3NTggXHVjNmIwXHVkNWE1XHVjNmIwIFx1YWM3MFx1YzZiOFx1Yzc3NCBcdWIxOTNcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI4MDhcdWM3NzRcdWM4MDBcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViODA4XHVjNzc0XHVjODAwXHViMjk0IFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWM3NTggXHViMDVkLCBcdWM5ODkgXHVkMzEwIFx1YmMxNlx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYmMwXHViODVjIFx1YjgwOFx1Yzc3NFx1YzgwMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWM1ZDBcdWIyOTQgMCBcdWQ2MzlcdWM3NDAgbiArIDFcdWM3NzQgXHVkM2VjXHVkNTY4XHViNDFjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAyeDJcdWJjZjRcdWI0ZGNcdWM3NTggMVx1ZDU4OSBcdWI5ZTggXHViYzExXHVjNWQwXHVjMTFjIFx1YzcwNFx1Yjg1YyBcdWMzZDhcdWM1NDRcdWM5YzBcdWIyOTQgXHViODA4XHVjNzc0XHVjODAwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAoMywgMSlcdWI4NWNcdWMzNjggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMgNng2XHViY2Y0XHViNGRjXHVjNzU4IDZcdWM1ZjQgXHVjNjdjXHVjYWJkIFx1YjA1ZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmQgXHViMDVkXHVjNzNjXHViODVjIFx1YzNkOFx1YzU0NFx1YzljMFx1YjI5NCBcdWI4MDhcdWM3NzRcdWM4MDBcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0ICg2LCAwKVx1Yzc3NCBcdWI0MThcdWFjYTBcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWU0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWJlNTRcdWM3NzQgXHViY2Y0XHViNGRjXHViOTdjIFx1YjVhMFx1YjA5OFx1YjI5NCBcdWM4OGNcdWQ0NWMgWCBZXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy4gXHViODA4XHVjNzc0XHVjODAwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YzY0MCBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWI4NWMgXHViZTU0XHVjNzQwIFx1YmNmNFx1YjRkYyBcdWJjMTZcdWM3M2NcdWI4NWMgXHViNWEwXHViMDk4XHVhZTMwXHVjNWQwIFx1Yzg4Y1x1ZDQ1Y1x1YzVkMFx1YjI5NCAwIFx1ZDYzOVx1Yzc0MCBuICsgMVx1Yzc3NCBcdWQzZWNcdWQ1NjhcdWI0MWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCBcdWJlNTRcdWM3NzQgXHViY2Y0XHViNGRjIFx1YmMxNlx1Yzc0NCBcdWI1YTBcdWIwOThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWNkOWNcdWI4MjVcdWM3NDAgMCAwXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNzA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFzZXJib3giLCJkZXNjcmlwdGlvbiI6IjxwPkEgbGFzZXJib3ggaXMgYSBnYW1lIGludm9sdmluZyBzb21lIG9wdGljYWwgZXF1aXBtZW50LiBUaGUgZ2FtZSBib2FyZCBpcyBhIHNxdWFyZSBuICZ0aW1lczsgbiBncmlkLiBPbiBlYWNoIGdyaWQgcG9pbnQsIGEgZ2FkZ2V0IGNhbGxlZCBhIHJpZ2h0LXR1cm5lciBjYW4gYmUgcGxhY2VkIGFuZCBzZXZlcmFsIHN1Y2ggZ2FkZ2V0cyBhcmUgaW5jbHVkZWQuIEZpbmFsbHksIHRoZXJlIGlzIGEgcnVieSBsYXNlciwgYW5kIGlmIHRoZSBsYXNlciBpcyBtb3VudGVkIGF0IHRoZSBib3R0b20gZW5kIG9mIGEgY29sdW1uLCB0aGUgYmVhbSB3aWxsIGJlIGRpcmVjdGVkIG5vcnRod2FyZHMgdGhyb3VnaCB0aGF0IGNvbHVtbi4gQW5hbG9nb3VzbHksIHRoZSBsYXNlciBiZWFtIG1heSBiZSBkaXJlY3RlZCBzb3V0aHdhcmRzIGZyb20gdGhlIHRvcCBvZiBhIGNvbHVtbiwgZWFzdHdhcmRzIGZyb20gdGhlIHN0YXJ0IG9mIGEgcm93IG9yIHdlc3R3YXJkcyBmcm9tIHRoZSBlbmQgb2YgdGhlIHJvdy48XC9wPlxyXG5cclxuPHA+VGhlIGdhbWUgc3RhcnRzIHdpdGggc29tZSByaWdodC10dXJuZXJzIGJlaW5nIHNwcmVhZCBvdXQgb24gc29tZSBncmlkIHBvaW50cyBhbmQgdGhlIGxhc2VyIChzd2l0Y2hlZCBvZmYpIGJlaW5nIG1vdW50ZWQgc29tZXdoZXJlIGFsb25nIHRoZSBib3JkZXIgb2YgdGhlIHJlY3RhbmdsZS4gVGhlIHBsYXllciB0aGVuIHRyaWVzIHRvIGRlZHVjZSB3aGVyZSB0aGUgYmVhbSB3aWxsIGVtZXJnZSB3aGVuIHRoZSBsYXNlciBpcyBzd2l0Y2hlZCBvbi4gVGhlIGVmZmVjdCBvZiBhIHJpZ2h0LXR1cm5lciBpcyB0byBkZWZsZWN0IHRoZSBiZWFtIG5pbmV0eSBkZWdyZWVzIHRvIHRoZSByaWdodCwgcmVnYXJkbGVzcyBvZiBmcm9tIHdoaWNoIG9mIHRoZSBmb3VyIGRpcmVjdGlvbnMgaXQgZW50ZXJzLjxcL3A+XHJcblxyXG48cD5Zb3VyIHByb2dyYW0gbXVzdCBkbyBleGFjdGx5IHdoYXQgdGhlIHBsYXllciBpcyBzdXBwb3NlZCB0byBkby48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBpcyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyLCB0ZWxsaW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0byBmb2xsb3cuIFRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHR3byBpbnRlZ2VycyBuIHIsIHdoZXJlIDEgJmxlOyBuICZsZTsgNTAgaXMgdGhlIHNpemUgb2YgdGhlIGJvYXJkIGFuZCAxICZsZTsgciAmbGU7IDUwIHRoZSBudW1iZXIgb2YgcmlnaHQtdHVybmVycy4gVGhlIGZvbGxvd2luZyByIGxpbmVzIGNvbnRhaW4gdGhlIGNvb3JkaW5hdGVzIHggeSBvZiB0aGUgcmlnaHQtdHVybmVycy4gTm8gdHdvIHJpZ2h0LXR1cm5lcnMgd2lsbCBoYXZlIHRoZSBzYW1lIGNvb3JkaW5hdGVzLjxcL3A+XHJcblxyXG48cD5GaW5hbGx5LCBhIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMgaW5kaWNhdGluZyB0aGUgbGFzZXIgcG9zaXRpb24gZm9sbG93cy4gVGhlIGJvdHRvbSBvZiBjb2x1bW4gc2l4IGlzIGRlbm90ZWQgYnkgNiAwIGFuZCB0aGUgc3RhcnQgb2Ygcm93IHNldmVuIGJ5IDAgNy4gSWYgdGhlIHplcm9lcyBhcmUgcmVwbGFjZWQgYnkgbiArIDEsIHRoZSBsYXNlciBpcyBwbGFjZWQgYXQgdGhlIHRvcCBvZiBjb2x1bW4gc2l4IGFuZCB0aGUgZW5kIG9mIHJvdyBzZXZlbiwgcmVzcGVjdGl2ZWx5PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgY29vcmRpbmF0ZXMgWCBZIG9mIHRoZSBiZWFtIGFzIGl0IGxlYXZlcyB0aGUgYm9hcmQuIFRoZSBzYW1lIHJ1bGVzIGFzIGZvciB0aGUgbGFzZXIgYXBwbHksIHNvIFggbWF5IGVxdWFsIDAgb3IgbiArIDEgb3IgZWxzZSBZIGVxdWFsIDAgb3IgbiArIDEuIElmIHRoZSBiZWFtIGdldHMgY2F1Z2h0IGFuZCBkb2VzIG5vdCBsZWF2ZSB0aGUgYm9hcmQsIHRoZSBvdXRwdXQgc2hvdWxkIGJlIDAgMC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=