시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 7 6 6 85.714%

문제

자라나는 직교 나선이란 원점에서 출발하여 연속적으로 돌아가는 나선이다. 첫 부분은 항상 오른쪽으로 출발하며(양의 X축 방향), 그 다음 부분은 위로(양의 Y축 방향), 그 다음은 왼쪽으로(음의 X축 방향), 그 다음은 아래로(음의 Y축 방향) 진행한다. 단, 나선의 각 부분은 바로 이전의 부분보다 1 이상 증가한 길이를 가져야 한다. 첫 부분의 길이는 1 이상인 어떤 자연수라도 가능하다. 아래는 1,2,4,6,7,9,11,12,15,20의 길이로 자라나는 직교 나선의 예시이다.

1사분면의 어떤 점 (x,y)가 주어졌을 때, 직교 나선이 자라나서 그 점에 도달할 수 있을까? 있다면 어떤 방법으로 자라나는 것이 최소의 총합 길이를 가질까?

입력

첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 1000)

각 테스트 케이스는 테스트 케이스의 번호 T와 문제에서 설명한 점 X,Y로 이루어져 있다. (1 ≤ x ≤ 10000, 1 ≤ y ≤ 10000)

출력

각 테스트 케이스마다 테스트 케이스의 번호를 출력하고,

만일 어떤 방법으로 자라나더라도 도달할 수 없는 점이라면 NO PATH를, 도달 가능하다면 최소 총합 길이로 도달하기 위해 필요한 성장 횟수와 그 방법(매번 자라난 길이)을 출력한다.

점까지의 경로가 존재하는 모든 테스트 케이스에서 나선은 22회 이하의 성장으로 목적지에 도달 가능하다.

예제 입력 1

3
1 1 1
2 3 5
3 8 4

예제 출력 1

1 NO PATH
2 2 3 5
3 6 1 2 3 9 10 11

힌트

W3sicHJvYmxlbV9pZCI6IjEwNDM3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzkwXHViNzdjXHViMDk4XHViMjk0IFx1YzljMVx1YWQ1MCBcdWIwOThcdWMxMjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc5MFx1Yjc3Y1x1YjA5OFx1YjI5NCBcdWM5YzFcdWFkNTAgXHViMDk4XHVjMTIwXHVjNzc0XHViNzgwIFx1YzZkMFx1YzgxMFx1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NThcdWM1ZWMgXHVjNWYwXHVjMThkXHVjODAxXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YWMwMFx1YjI5NCBcdWIwOThcdWMxMjBcdWM3NzRcdWIyZTQuIFx1Y2NhYiBcdWJkODBcdWJkODRcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWNkOWNcdWJjMWNcdWQ1NThcdWJhNzAoXHVjNTkxXHVjNzU4IFhcdWNkOTUgXHViYzI5XHVkNWE1KSwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWJkODBcdWJkODRcdWM3NDAgXHVjNzA0XHViODVjKFx1YzU5MVx1Yzc1OCBZXHVjZDk1IFx1YmMyOVx1ZDVhNSksIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM3NDAgXHVjNjdjXHVjYWJkXHVjNzNjXHViODVjKFx1Yzc0Y1x1Yzc1OCBYXHVjZDk1IFx1YmMyOVx1ZDVhNSksIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM3NDAgXHVjNTQ0XHViNzk4XHViODVjKFx1Yzc0Y1x1Yzc1OCBZXHVjZDk1IFx1YmMyOVx1ZDVhNSkgXHVjOWM0XHVkNTg5XHVkNTVjXHViMmU0LiBcdWIyZTgsIFx1YjA5OFx1YzEyMFx1Yzc1OCBcdWFjMDEgXHViZDgwXHViZDg0XHVjNzQwIFx1YmMxNFx1Yjg1YyBcdWM3NzRcdWM4MDRcdWM3NTggXHViZDgwXHViZDg0XHViY2Y0XHViMmU0IDEgXHVjNzc0XHVjMGMxIFx1Yzk5ZFx1YWMwMFx1ZDU1YyBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhYzAwXHVjODM4XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YmQ4MFx1YmQ4NFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMSBcdWM3NzRcdWMwYzFcdWM3NzggXHVjNWI0XHViNWE0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yjc3Y1x1YjNjNCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIFx1YzU0NFx1Yjc5OFx1YjI5NCAxLDIsNCw2LDcsOSwxMSwxMiwxNSwyMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI4NWMgXHVjNzkwXHViNzdjXHViMDk4XHViMjk0IFx1YzljMVx1YWQ1MCBcdWIwOThcdWMxMjBcdWM3NTggXHVjNjA4XHVjMmRjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIHNyYz1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3VwbG9hZFwvaW1hZ2VzMlwvc3BpcmFsLnBuZ1wiIFwvPjxcL3A+XHJcblxyXG48cD4xXHVjMGFjXHViZDg0XHViYTc0XHVjNzU4IFx1YzViNFx1YjVhNCBcdWM4MTAgKHgseSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjOWMxXHVhZDUwIFx1YjA5OFx1YzEyMFx1Yzc3NCBcdWM3OTBcdWI3N2NcdWIwOThcdWMxMWMgXHVhZGY4IFx1YzgxMFx1YzVkMCBcdWIzYzRcdWIyZWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz8gXHVjNzg4XHViMmU0XHViYTc0IFx1YzViNFx1YjVhNCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjNzkwXHViNzdjXHViMDk4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWNkNWNcdWMxOGNcdWM3NTggXHVjZDFkXHVkNTY5IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFjMDBcdWM5YzhcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFAgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOCBUXHVjNjQwIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgXHVjODEwIFgsWVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IHggJmxlOyAxMDAwMCwgMSAmbGU7IHkgJmxlOyAxMDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1Yzc3YyBcdWM1YjRcdWI1YTQgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1Yzc5MFx1Yjc3Y1x1YjA5OFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWIzYzRcdWIyZWNcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWM4MTBcdWM3NzRcdWI3N2NcdWJhNzQgTk8gUEFUSFx1Yjk3YywgXHViM2M0XHViMmVjIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCBcdWNkNWNcdWMxOGMgXHVjZDFkXHVkNTY5IFx1YWUzOFx1Yzc3NFx1Yjg1YyBcdWIzYzRcdWIyZWNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMxMzFcdWM3YTUgXHVkNjlmXHVjMjE4XHVjNjQwIFx1YWRmOCBcdWJjMjlcdWJjOTUoXHViOWU0XHViYzg4IFx1Yzc5MFx1Yjc3Y1x1YjA5YyBcdWFlMzhcdWM3NzQpXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODEwXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMgXHViMDk4XHVjMTIwXHVjNzQwIDIyXHVkNjhjIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWMxMzFcdWM3YTVcdWM3M2NcdWI4NWMgXHViYWE5XHVjODAxXHVjOWMwXHVjNWQwIFx1YjNjNFx1YjJlYyBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA0MzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHcm93aW5nIFJlY3Rhbmd1bGFyIFNwaXJhbCIsImRlc2NyaXB0aW9uIjoiPHA+QSBncm93aW5nIHJlY3Rhbmd1bGFyIHNwaXJhbCBpcyBhIGNvbm5lY3RlZCBzZXF1ZW5jZSBvZiBzdHJhaWdodC1saW5lIHNlZ21lbnRzIHN0YXJ0aW5nIGF0IHRoZSBvcmlnaW4uIFRoZSBmaXJzdCBzZWdtZW50IGdvZXMgcmlnaHQgKHBvc2l0aXZlIHggZGlyZWN0aW9uKS4gVGhlIHNlZ21lbnQgZ29lcyB1cCAocG9zaXRpdmUgeSBkaXJlY3Rpb24pLiBUaGUgbmV4dCBzZWdtZW50IGdvZXMgbGVmdCAobmVnYXRpdmUgeCBkaXJlY3Rpb24pLiBUaGUgbmV4dCBzZWdtZW50IGdvZXMgZG93biAobmVnYXRpdmUgeSBkaXJlY3Rpb24pIGFuZCB0aGUgc2VxdWVuY2Ugb2YgZGlyZWN0aW9ucyByZXBlYXRzLiBFYWNoIHNlZ21lbnQgaGFzIGludGVnZXIgbGVuZ3RoIGFuZCBlYWNoIHNlZ21lbnQgaXMgYXQgbGVhc3Qgb25lIHVuaXQgbG9uZ2VyIHRoYW4gdGhlIHByZXZpb3VzIHNlZ21lbnQuIEluIHRoZSBzcGlyYWwgYmVsb3csIHRoZSBzZWdtZW50IGxlbmd0aHMgYXJlIDEsIDIsIDQsIDYsIDcsIDksIDExLCAxMiwgMTUsIDIwLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9zcGlyYWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjczcHg7IHdpZHRoOjI5M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBkZXRlcm1pbmUgdGhlIHNob3J0ZXN0IGdyb3dpbmcgcmVjdGFuZ3VsYXIgc3BpcmFsIChpbiB0b3RhbCBsZW5ndGgpIHRoYXQgZW5kcyBhdCBhIGdpdmVuIGludGVnZXIgcG9pbnQgKHgsIHkpIGluIHRoZSBmaXJzdCBxdWFkcmFudCBvciBkZXRlcm1pbmUgdGhhdCB0aGVyZSBpcyBubyBzdWNoIHNwaXJhbC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IHNob3VsZCBiZSBwcm9jZXNzZWQgaWRlbnRpY2FsbHkgYW5kIGluZGVwZW5kZW50bHkuPFwvcD5cclxuXHJcbjxwPkVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBvZiBpbnB1dCBjb25zaXN0aW5nIG9mIHRocmVlIHNwYWNlIHNlcGFyYXRlZCBkZWNpbWFsIGludGVnZXJzLiBUaGUgZmlyc3QgaW50ZWdlciBpcyB0aGEgZGF0YSBzZXQgbnVtYmVyLiBUaGUgbmV4dCB0d28gaW50ZWdlcnMgYXJlIHRoZSB4IGFuZCB5IGNvb3JkaW5hdGVzIG9mIHRoZSBkZXNpcmVkIGVuZCBwb2ludCAoMSAmbGU7IHggJmxlOyAxMDAwMCwgMSAmbGU7IHkgJmxlOyAxMDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgYSBzaW5nbGUgbGluZSBvZiBvdXRwdXQuIElmIHRoZXJlIGlzIG5vIHNwaXJhbCBzb2x1dGlvbiwgdGhlIGxpbmUgY29uc2lzdHMgb2YgdGhlIGRhdGEgc2V0IG51bWJlciwgYSBzaW5nbGUgc3BhY2UgYW5kICZxdW90O05PIFBBVEgmcXVvdDsgKHdpdGhvdXQgdGhlIHF1b3RlcykuIElmIHRoZXJlIGlzIGEgc29sdXRpb24sIHRoZSBsaW5lIGNvbnNpc3RzIG9mIHRoZSBkYXRhIHNldCBudW1iZXIsIGEgc2luZ2xlIHNwYWNlLCB0aGUgbnVtYmVyIG9mIHNlZ21lbnRzIGluIHRoZSBzb2x1dGlvbiwgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IHRoZSBsZW5ndGhzIG9mIHRoZSBzZWdtZW50cyBpbiBvcmRlciwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIFRoZSBpbnB1dCBkYXRhIHdpbGwgYmUgY2hvc2VuIHNvIHRoYXQgbm8gcGF0aCByZXF1aXJlcyBtb3JlIHRoYW4gMjIgc2VnbWVudHMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d