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

문제

지학이는 3차 다항식(cubic polynomial)을 좋아하는 잘 알려진 cubelover 이다.

어느 화창한 봄날, 지학이는 아파트 놀이터에서 승현이가 길이 n의 정수 수열 x1, x2, ..., xn 을 가지고 노는 것을 보았다. 지학이는 그 아파트의 짱이었고, 승현이보다 45일이나 먼저 태어난 형이었다. 지학이는 승현이를 보자 마자 갖고 놀던 수열을 빼앗아 갔다.

승현이는 그 자리에서 엉엉 울기 시작했고, 마음이 약해진 지학이는 승현이가 1 ≤ i ≤ n인 모든 정수 i에 대해 xi = ai3+bi2+ci+d를 만족하는 실수 a, b, c, d 를 찾으면 수열을 돌려주겠다고 약속했다. (사실 3차 다항식이라 a ≠ 0이어야 하긴 하는데, 지학이는 그 정도로 엄밀하게 굴고 싶진 않은 모양이다.)

간만에 학교를 나와 외출을 즐기고 있는 당신은, 울고 있는 승현이와 눈을 마주쳤다. 승현이는 여러분에게 곧장 달려와서, 빨리 그러한 실수 a, b, c, d 를 찾아달라고 졸랐다. 당신은 과연 승현이의 눈물을 닦아 줄 수 있는가?

입력

이 문제는 한 입력에 여러 개의 테스트 케이스가 주어진다. 첫번째 줄에 그러한 테스트 케이스의 개수 T (1 ≤ T ≤ 1000) 가 주어진다.

이후 T개의 줄이 주어진다. 첫번째로 수열의 길이인 정수 n (1 ≤ n ≤ 500) 이 주어진다. 이후 n 개의 정수가 주어진다. 이 중 i번째 정수는 xi (0 ≤ xi ≤ 50, 000, 000) 를 뜻한다.

출력

T개의 줄에 걸쳐, 만약에 승현이가 원하는 실수 a, b, c, d가 존재한다면 YES, 존재하지 않는다면 NO를 출력한다.

예제 입력 1

3
1 3
5 0 1 2 3 4
5 0 1 2 4 5

예제 출력 1

YES
YES
NO

힌트

첫번째 테스트 케이스에서, 가능한 답 중 하나는 a = 0, b = 0, c = 0, d = 3 이다.

W3sicHJvYmxlbV9pZCI6IjM5ODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNTBcdWJlMGNcdWI3ZWNcdWJjODQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzljMFx1ZDU1OVx1Yzc3NFx1YjI5NCAzXHVjYzI4IFx1YjJlNFx1ZDU2ZFx1YzJkZChjdWJpYyBwb2x5bm9taWFsKVx1Yzc0NCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjNzk4IFx1YzU0Y1x1YjgyNFx1YzljNCBjdWJlbG92ZXIgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWIyOTAgXHVkNjU0XHVjYzNkXHVkNTVjIFx1YmQwNFx1YjBhMCwgXHVjOWMwXHVkNTU5XHVjNzc0XHViMjk0IFx1YzU0NFx1ZDMwY1x1ZDJiOCBcdWIxODBcdWM3NzRcdWQxMzBcdWM1ZDBcdWMxMWMgXHVjMmI5XHVkNjA0XHVjNzc0XHVhYzAwIFx1YWUzOFx1Yzc3NCBuXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWMyMThcdWM1ZjQgeDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+LCAuLi4sIHg8c3ViPm48XC9zdWI+IFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHViMTc4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJjZjRcdWM1NThcdWIyZTQuIFx1YzljMFx1ZDU1OVx1Yzc3NFx1YjI5NCBcdWFkZjggXHVjNTQ0XHVkMzBjXHVkMmI4XHVjNzU4IFx1YzlmMVx1Yzc3NFx1YzVjOFx1YWNlMCwgXHVjMmI5XHVkNjA0XHVjNzc0XHViY2Y0XHViMmU0IDQ1XHVjNzdjXHVjNzc0XHViMDk4IFx1YmEzY1x1YzgwMCBcdWQwZGNcdWM1YjRcdWIwOWMgXHVkNjE1XHVjNzc0XHVjNWM4XHViMmU0LiBcdWM5YzBcdWQ1NTlcdWM3NzRcdWIyOTQgXHVjMmI5XHVkNjA0XHVjNzc0XHViOTdjIFx1YmNmNFx1Yzc5MCBcdWI5YzhcdWM3OTAgXHVhYzE2XHVhY2UwIFx1YjE4MFx1YjM1OCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViZTdjXHVjNTU3XHVjNTQ0IFx1YWMxNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmI5XHVkNjA0XHVjNzc0XHViMjk0IFx1YWRmOCBcdWM3OTBcdWI5YWNcdWM1ZDBcdWMxMWMgXHVjNWM5XHVjNWM5IFx1YzZiOFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1ODhcdWFjZTAsIFx1YjljOFx1Yzc0Y1x1Yzc3NCBcdWM1N2RcdWQ1NzRcdWM5YzQgXHVjOWMwXHVkNTU5XHVjNzc0XHViMjk0IFx1YzJiOVx1ZDYwNFx1Yzc3NFx1YWMwMCAxICZsZTsgaSAmbGU7IG5cdWM3NzggXHViYWE4XHViNGUwIFx1YzgxNVx1YzIxOCBpXHVjNWQwIFx1YjMwMFx1ZDU3NCB4PHN1Yj5pPFwvc3ViPiA9IGFpPHN1cD4zPFwvc3VwPitiaTxzdXA+MjxcL3N1cD4rY2krZFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMmU0XHVjMjE4IGEsIGIsIGMsIGQgXHViOTdjIFx1Y2MzZVx1YzczY1x1YmE3NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViM2NjXHViODI0XHVjOGZjXHVhY2EwXHViMmU0XHVhY2UwIFx1YzU3ZFx1YzE4ZFx1ZDU4OFx1YjJlNC4gKFx1YzBhY1x1YzJlNCAzXHVjYzI4IFx1YjJlNFx1ZDU2ZFx1YzJkZFx1Yzc3NFx1Yjc3YyBhICZuZTsgMFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NThcdWFlMzQgXHVkNTU4XHViMjk0XHViMzcwLCBcdWM5YzBcdWQ1NTlcdWM3NzRcdWIyOTQgXHVhZGY4IFx1YzgxNVx1YjNjNFx1Yjg1YyBcdWM1YzRcdWJjMDBcdWQ1NThcdWFjOGMgXHVhZDc0XHVhY2UwIFx1YzJmNlx1YzljNCBcdWM1NGFcdWM3NDAgXHViYWE4XHVjNTkxXHVjNzc0XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVhYzA0XHViOWNjXHVjNWQwIFx1ZDU1OVx1YWQ1MFx1Yjk3YyBcdWIwOThcdWM2NDAgXHVjNjc4XHVjZDljXHVjNzQ0IFx1Yzk5MFx1YWUzMFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViMmY5XHVjMmUwXHVjNzQwLCBcdWM2YjhcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzJiOVx1ZDYwNFx1Yzc3NFx1YzY0MCBcdWIyMDhcdWM3NDQgXHViOWM4XHVjOGZjXHVjY2U0XHViMmU0LiBcdWMyYjlcdWQ2MDRcdWM3NzRcdWIyOTQgXHVjNWVjXHViN2VjXHViZDg0XHVjNWQwXHVhYzhjIFx1YWNlN1x1YzdhNSBcdWIyZWNcdWI4MjRcdWM2NDBcdWMxMWMsIFx1YmU2OFx1YjlhYyBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVjMmU0XHVjMjE4IGEsIGIsIGMsIGQgXHViOTdjIFx1Y2MzZVx1YzU0NFx1YjJlY1x1Yjc3Y1x1YWNlMCBcdWM4NzhcdWI3OTBcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWFjZmNcdWM1ZjAgXHVjMmI5XHVkNjA0XHVjNzc0XHVjNzU4IFx1YjIwOFx1YmIzY1x1Yzc0NCBcdWIyZTZcdWM1NDQgXHVjOTA0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWFjMDA/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3NzQgXHViYjM4XHVjODFjXHViMjk0IFx1ZDU1YyBcdWM3ODVcdWI4MjVcdWM1ZDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCAoMSAmbGU7IFQgJmxlOyAxMDAwKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgVFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWJcdWJjODhcdWM5ZjhcdWI4NWMgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3OCBcdWM4MTVcdWMyMTggbiAoMSAmbGU7IG4gJmxlOyA1MDApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1ZDZjNCBuIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjOTExIGlcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4XHViMjk0IHg8c3ViPmk8XC9zdWI+ICgwICZsZTsgeDxzdWI+aTxcL3N1Yj4gJmxlOyA1MCwgMDAwLCAwMDApIFx1Yjk3YyBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwLCBcdWI5Y2NcdWM1N2RcdWM1ZDAgXHVjMmI5XHVkNjA0XHVjNzc0XHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWMyZTRcdWMyMTggYSwgYiwgYywgZFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQgWUVTLCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IE5PXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIyZjUgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjI5NCBhID0gMCwgYiA9IDAsIGMgPSAwLCBkID0gMyBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTgxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUG9seW5vbWlhbCBFc3RpbWF0ZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBudW1iZXIgb2Ygc3BlY3RhdG9ycyBhdCB0aGUgRklGQSBXb3JsZCBDdXAgaW5jcmVhc2VzIHllYXIgYWZ0ZXIgeWVhci4gQXMgeW91IHNlbGwgdGhlIGFkdmVydGlzZW1lbnQgc2xvdHMgZHVyaW5nIHRoZSBnYW1lcyBmb3IgdGhlIGNvbWluZyB5ZWFycywgeW91IG5lZWQgdG8gY29tZSB1cCB3aXRoIHRoZSBwcmljZSBhIGNvbXBhbnkgaGFzIHRvIHBheSBpbiBvcmRlciB0byBnZXQgYW4gYWR2ZXJ0aXNlbWVudCBzbG90LiBGb3IgdGhpcywgeW91IG5lZWQgYSBnb29kIGVzdGltYXRlIGZvciB0aGUgbnVtYmVyIG9mIHNwZWN0YXRvcnMgaW4gdGhlIGNvbWluZyBnYW1lcywgYmFzZWQgb24gdGhlIG51bWJlciBvZiBzcGVjdGF0b3JzIGluIHRoZSBwYXN0IGdhbWVzLjxcL3A+XHJcblxyXG48cD5Zb3VyIGludHVpdGlvbiB0ZWxscyB5b3UgdGhhdCBtYXliZSB0aGUgbnVtYmVyIG9mIHNwZWN0YXRvcnMgY291bGQgYmUgbW9kZWxlZCBwcmVjaXNlbHkgYnkgYSBwb2x5bm9taWFsIG9mIGRlZ3JlZSBhdCBtb3N0IDMuIFRoZSB0YXNrIGlzIHRvIGNoZWNrIGlmIHRoaXMgaW50dWl0aW9uIGlzIHRydWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgc3RhcnRzIHdpdGggYSBwb3NpdGl2ZSBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2Ygb25lIGxpbmUuIFRoZSBsaW5lIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgMSAmbGU7IG4gJmxlOyA1MDAsIGZvbGxvd2VkIGJ5IG4gaW50ZWdlcnMgeDxzdWI+MTxcL3N1Yj4sIC4gLiAuICwgeDxzdWI+bjxcL3N1Yj4gd2l0aCAwICZsZTsgeDxzdWI+aTxcL3N1Yj4gJmxlOyA1MCAwMDAgMDAwIGZvciBhbGwgaSwgdGhlIG51bWJlciBvZiBzcGVjdGF0b3JzIGluIHBhc3QgZ2FtZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCAmbGRxdW87WUVTJnJkcXVvOyBpZiB0aGVyZSBpcyBhIHBvbHlub21pYWwgcCAod2l0aCByZWFsIGNvZWZmaWNpZW50cykgb2YgZGVncmVlIGF0IG1vc3QgMyBzdWNoIHRoYXQgcChpKSA9IHg8c3ViPmk8XC9zdWI+IGZvciBhbGwgaS4gT3RoZXJ3aXNlLCBwcmludCAmbGRxdW87Tk8mcmRxdW87LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==