시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB41717514842.165%

문제

지학이는 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/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3NzQgXHViYjM4XHVjODFjXHViMjk0IFx1ZDU1YyBcdWM3ODVcdWI4MjVcdWM1ZDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZGY4XHViN2VjXHVkNTVjIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKDEgJmxlOyBUICZsZTsgMTAwMCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IFRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOFx1Yjg1YyBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc4IFx1YzgxNVx1YzIxOCBuICgxICZsZTsgbiAmbGU7IDUwMCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHVkNmM0IG4gXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM5MTEgaVx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgeDxzdWI+aTxcL3N1Yj4gKDAgJmxlOyB4PHN1Yj5pPFwvc3ViPiAmbGU7IDUwLCAwMDAsIDAwMCkgXHViOTdjIFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAsIFx1YjljY1x1YzU3ZFx1YzVkMCBcdWMyYjlcdWQ2MDRcdWM3NzRcdWFjMDAgXHVjNmQwXHVkNTU4XHViMjk0IFx1YzJlNFx1YzIxOCBhLCBiLCBjLCBkXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YmE3NCBZRVMsIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQgTk9cdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIyZjUgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjI5NCBhID0gMCwgYiA9IDAsIGMgPSAwLCBkID0gMyBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzOTgxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUG9seW5vbWlhbCBFc3RpbWF0ZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBudW1iZXIgb2Ygc3BlY3RhdG9ycyBhdCB0aGUgRklGQSBXb3JsZCBDdXAgaW5jcmVhc2VzIHllYXIgYWZ0ZXIgeWVhci4gQXMgeW91IHNlbGwgdGhlIGFkdmVydGlzZW1lbnQgc2xvdHMgZHVyaW5nIHRoZSBnYW1lcyBmb3IgdGhlIGNvbWluZyB5ZWFycywgeW91IG5lZWQgdG8gY29tZSB1cCB3aXRoIHRoZSBwcmljZSBhIGNvbXBhbnkgaGFzIHRvIHBheSBpbiBvcmRlciB0byBnZXQgYW4gYWR2ZXJ0aXNlbWVudCBzbG90LiBGb3IgdGhpcywgeW91IG5lZWQgYSBnb29kIGVzdGltYXRlIGZvciB0aGUgbnVtYmVyIG9mIHNwZWN0YXRvcnMgaW4gdGhlIGNvbWluZyBnYW1lcywgYmFzZWQgb24gdGhlIG51bWJlciBvZiBzcGVjdGF0b3JzIGluIHRoZSBwYXN0IGdhbWVzLjxcL3A+XHJcblxyXG48cD5Zb3VyIGludHVpdGlvbiB0ZWxscyB5b3UgdGhhdCBtYXliZSB0aGUgbnVtYmVyIG9mIHNwZWN0YXRvcnMgY291bGQgYmUgbW9kZWxlZCBwcmVjaXNlbHkgYnkgYSBwb2x5bm9taWFsIG9mIGRlZ3JlZSBhdCBtb3N0IDMuIFRoZSB0YXNrIGlzIHRvIGNoZWNrIGlmIHRoaXMgaW50dWl0aW9uIGlzIHRydWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgc3RhcnRzIHdpdGggYSBwb3NpdGl2ZSBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2Ygb25lIGxpbmUuIFRoZSBsaW5lIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgMSAmbGU7IG4gJmxlOyA1MDAsIGZvbGxvd2VkIGJ5IG4gaW50ZWdlcnMgeDxzdWI+MTxcL3N1Yj4sIC4gLiAuICwgeDxzdWI+bjxcL3N1Yj4gd2l0aCAwICZsZTsgeDxzdWI+aTxcL3N1Yj4gJmxlOyA1MCAwMDAgMDAwIGZvciBhbGwgaSwgdGhlIG51bWJlciBvZiBzcGVjdGF0b3JzIGluIHBhc3QgZ2FtZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCAmbGRxdW87WUVTJnJkcXVvOyBpZiB0aGVyZSBpcyBhIHBvbHlub21pYWwgcCAod2l0aCByZWFsIGNvZWZmaWNpZW50cykgb2YgZGVncmVlIGF0IG1vc3QgMyBzdWNoIHRoYXQgcChpKSA9IHg8c3ViPmk8XC9zdWI+IGZvciBhbGwgaS4gT3RoZXJ3aXNlLCBwcmludCAmbGRxdW87Tk8mcmRxdW87LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=