W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Let be a function acting on strings composed of the digits 0 and 1. The function transforms the string by replacing (independently and concurrently) every digit 0 with 1 and every digit 1 with the string . For example , (i.e. assigns an empty string to the empty string). Note that is an injection, or a one-to-one function. By we denote the function composed with itself times. In particular, is the identity function .
We are interested in the strings of the form for This sequence begins with the following strings:
, , , , , .
We call the string a substring of the string if it occurs in as a contiguous (i.e. one-block) subsequence. A sequence of integers is given. Your task is to check whether a string of the form is a substring of for some .
The first line of the standard input contains a single integer , , denoting the number of test units. The first line of each test unit's description contains one integer , . The second line of each description holds non-negative integers , separated by single spaces. The sum of the numbers in the second line of any test unit description does not exceed .
Your programme should print out lines to the standard output, one for each test unit. Each line corresponding to a test unit should contain one word: TAK (yes in Polish - if is a substring of for some in that test unit, or NIE (no in Polish) otherwise.
For the input data:
2 2 1 2 2 2 0
the correct result is:
TAK NIE
Explanation of the example: The string from the first test unit is - it is a substring of for example. In the second test unit there is a string , which is not a substring of for any .
Task authors: Wojciech Rytter and Bartosz Walczak.