====== Pebbles ======

‎$n$‎ دسته سنگ‌ریزه داریم که در دسته ‎$i$‎ ام ‎$a_i$‎ سنگ‌ریزه قرار دارد. می‌دانیم به ازای هر ‎$1 \leq i < n$‎ داریم ‎$a_i \leq a_{i+1}$.

‎
دو نفر بازی زیر را روی سنگ‌ریزه‌ها انجام می‌دهند:
‎   
  * ‎ هر نفر در نو‌بت خود یک دسته را انتحاب می‌کند و تعدادی از سنگ ریزه‌های آن را بیرون می‌اندازد، در صورتی که بعد از حرکت او به ازای یک ‎$i > 1$‎ ، ‎$a_i < a_{i-1}$‎ باشد او بازنده بازی خواهد بود. در غیر این صورت بازی ادامه پیدا می‌کند.
  * ‎‎ در صورتی که بعد از حر کت یک بازیکن هیچ دسته‌ای دارای سنگ‌ریزه نباشد، آن بازی کن برنده بازی خواهد بود.
   ‎
‎
در صورتی که هر دو بازیکن بهترین بازی خود را انجام دهند ، چه کسی برنده بازی خواهد بود؟‎
‎
===== ورودی ====
  * در سطر اول ورودی عدد ‎$1 \leq t \leq 10$‎ نشان‌دهنده تعداد تست‌ها آمده است‎.
  * در سطر اول هر تست عدد ‎$1 \leq n \leq 1000$‎ و در سطر بعدی ‎$n$‎ عدد ‎$a_1$‎ تا ‎$a_n$‎ آمده است‎.
===== خروجی =====


به ازای هر تست، در صورتی که نفر اول برنده بازی خواهد بود عبارت ‎TAK و در غیر این صورت عبارت ‎NIE‎ را چاپ کنید.
‎
===== محدودیت‌ها =====

  * محدودیت زمان: ۲ ثانیه
  * محدودیت حافظه: ۲۵۶ مگابایت


===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|‎2 \\ 2 \\ ‎2 2 \\ 3 \\ ‎1 2 4‎‎| ‎‎NIE‎‎ \\ ‎TAK‎|

</WRAP>



<پاسخ>
فرض کنید ‎$\lceil \frac{n}{2} \rceil$‎ عدد به صورت زیر تعریف شده باشند:
‎
‎   
  * ‎ در صورتی که ‎$n$‎ زوج باشد ، به ازای هر ‎$1 \leq i \leq \frac{n}{2}$‎ ، ‎$b_i = a_{2  i}-a_{2 \times i-1}$‎.
  * ‎ در صورتی که ‎$n$‎ فرد باشد ، ‎$b_1 = a_1$‎ و ‎$b_{2 \leq i \leq \frac{n+1}{2}} = a_{2  i‎ -‎1}-a_{2  i‎ -2}$.
   ‎‎
در این صورت بازی به شکل زیر خواهد بود‎:

‎
در هر مرحله هرکس می‌تواند یا تعداد خاصی به یکی از ‎$b_i$‎ ها اضافه کند، یا هر تعداد دلخواه از یکی از ‎$b_i$‎ ها کم کند. هر چند زمانی که تمامی ‎$b_i$‎ ها برابر با ‎صفر‎ باشد لزوماً پایان بازی نیست اما اگر یکی از بازیکن‌ها بتواند طوری بازی کند که نوبت او حداقل یکی از ‎$b_i$‎ ها بیش‌تر از صفر باشد برنده‌ی بازی خواهد بود. (چون در حالت نهایی بازی حتماً تمام ‎$b_i$‎ ها برابر با صفر خواهد بود).


می‌توان نشان داد که اگر ‎$x = b_1 \bigoplus b_2 \bigoplus \cdots \bigoplus b_{\lceil \frac{n}{2} \rceil}$‎ و ‎$x > 0$‎ حتما یک عدد ‎$j$‎ وجود دارد به شرطی که ‎$b_j > b_j \bigoplus x$‎. یا به عبارت دیگر اگر ‎xor $b_i$‎ ها ناصفر باشد ، می‌توان یکی از ‎$b_i$‎ ها را تعداد کاهش داد به طوری که xor‎ اعداد برابر با ‎صفر شود‎.


می‌توان نشان داد در صورتی نفر اول برنده‌ی بازی خواهد بود که ‎xor $b_i$‎ ها در ابتدا مخالف صفر‎ باشد، در این صورت او در هر مرحله یکی از ‎$b_i$‎ ها را طوری کاهش می‌دهد که xor اعداد برابر با ‎صفر‎ باشد و نفر دیگر با حرکت خود باعث می‌شود که ‎xor‎ اعداد ناصفر شود. پس اگر این استراتژی را ادامه دهد هیچ وقت نوبت او ‎xor‎ اعداد برابر با ‎صفر نخواهد بود و نتیجتاً هیچ وقت تمام ‎$b_i$‎ ها برابر با ‎صفر نخواهد بود و او برنده بازی است‎.

‎
در صورتی که ‎xor $b_i$‎ ها در ابتدا برابر با صفر‎ باشد نفر دوم با استراتژی گفته شده می تواند برنده بازی باشد.


**پيچيدگي**


می‌توان به راحتی مقدایر ‎$b_i$‎ ها را با ‎$o(n)$‎ عملیات به‌دست آورد و بر حسب ‎xor‎ آنها پاسخ سؤال را خروجی داد.
</پاسخ>

  * [[سوال ۷۱|سوال بعد]]
  * [[سوال ۶۹|سوال قبل]]