시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 197 76 47 39.167%

문제

N개의 수로 이루어진 수열 A가 주어진다. 

수열 A에서 연속된 부분 수열을 고르려고 한다. 부분 수열의 XOR 합이란, 부분 수열에 들어있는 모든 원소를 XOR한 값을 의미한다.

수열 A가 주어졌을 때, XOR 합이 가장 큰 부분 수열을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10)

각 테스트 케이스의 첫째 줄에는 배열의 크기 N (1 ≤ N ≤ 100,000), 둘째 줄에는 수열 A에 들어있는 수가 주어진다. 수열 A에 들어있는 수는 32비트 부호있는 정수 범위 안에 들어가는 음이 아닌 정수이다.

출력

각각의 테스트 케이스마다 수열 A의 연속된 부분 수열 중에서 XOR 합이 가장 큰 부분 수열의 XOR 합을 출력한다.

예제 입력 1

2
5
3 7 7 7 0
5
3 8 2 6 4

예제 출력 1

7
15
W3sicHJvYmxlbV9pZCI6IjEzNTA0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiWE9SIFx1ZDU2OSIsImRlc2NyaXB0aW9uIjoiPHA+Tlx1YWMxY1x1Yzc1OCBcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNCBBXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0IEFcdWM1ZDBcdWMxMWMgXHVjNWYwXHVjMThkXHViNDFjIFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVhY2UwXHViOTc0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc1OCBYT1IgXHVkNTY5XHVjNzc0XHViNzgwLCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjNmQwXHVjMThjXHViOTdjIFhPUlx1ZDU1YyBcdWFjMTJcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjQgQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBYT1IgXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgVCAmbGU7IDEwKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgTiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKSwgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjQgQVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMjE4XHVjNWY0IEFcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzIxOFx1YjI5NCAzMlx1YmU0NFx1ZDJiOCBcdWJkODBcdWQ2MzhcdWM3ODhcdWIyOTQgXHVjODE1XHVjMjE4IFx1YmM5NFx1YzcwNCBcdWM1NDhcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHViMjk0IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0IFx1YzkxMVx1YzVkMFx1YzExYyBYT1IgXHVkNTY5XHVjNzc0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc1OCBYT1IgXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMzUwNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlhPUiBTdW0iLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGFuIGFycmF5IG9mIE4gbnVtYmVycywgd2Ugd2lzaCB0byBjaG9vc2UgYSBjb250aWd1b3VzIHN1Yi1zZXF1ZW5jZSBvZiB0aGUgYXJyYXksIHNvIHRoYXQgdGhlIGJpdHdpc2UgWE9SIG9mIGFsbCBjaG9zZW4gbnVtYmVycyBpcyBtYXhpbXVtLiBCaXR3aXNlIFhPUiBpcyBkZWZpbmVkIGFzIGZvbGxvd3M6IGV2ZXJ5IGJpdCBpbiB0aGUgYW5zd2VyIGlzIG9idGFpbmVkIGJ5IGFwcGx5aW5nIFhPUiBsb2dpYyBvbiB0aGUgY29ycmVzcG9uZGluZyBiaXRzIG9mIHRoZSBzZXQgb2YgbnVtYmVycy4gRm9yIGV4YW1wbGUgNywgOCBhbmQgNSBhcmUgWE9SZWQgYXMgZm9sbG93cyw8XC9wPlxyXG5cclxuPHA+TnVtYmVycyBpbiBiaW5hcnk6ICZuYnNwOzAxMTEgJm5ic3A7MTAwMCAmbmJzcDswMTAxICZuYnNwOy0tLS0tICZuYnNwOzEwMTA8XC9wPlxyXG5cclxuPHA+U28gdGhlIGFuc3dlciBpcyAxMCAoaW4gZGVjaW1hbCkuIFRoZSBzYW1lIGFuc3dlciBjYW4gYmUgb2J0YWluZWQgaW4gQ1wvQysrXC9KYXZhIGJ5IHVzaW5nIHRoZSBYT1Igb3BlcmF0b3IgYXMgN144XjUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVC4gVGhlIGZpcnN0IGxpbmUgb2YgZWFjaCB0ZXN0LWNhc2UgY29udGFpbnMgb25lIGludGVnZXIsIE4gKHNpemUgb2YgdGhlIGFycmF5KS4gVGhlIG5leHQgTiBsaW5lcyBvZiBlYWNoIHRlc3QtY2FzZSBjb250YWluIGludGVnZXJzIGRlbm90aW5nIHRoZSBlbGVtZW50cyBvZiB0aGUgYXJyYXkuPFwvcD5cclxuXHJcbjxwPkNvbnN0cmFpbnRzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyBUICZsZTsgMTA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE4gJmxlOyAxMDAsIDAwMDxcL2xpPlxyXG5cdDxsaT5BbGwgaW5wdXQgaW50ZWdlcnMgd2lsbCBiZSBub24tbmVnYXRpdmUgYW5kIGZpdCBpbnRvIDMyIGJpdCBzaWduZWQgaW50ZWdlci48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbWF4aW11bSBzdW0gdGhhdCBjYW4gYmUgb2J0YWluZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d