P3490 [POI 2009] FIB-Words 2

The following task is a significantly harder version of task Words from the third stage of 16th Polish OI. It wasn't used in the contest itself, but is an extension for those who solved "Words" and want more. :-) 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 , and if it is, you shuold find minimal such .

The first line of the standard input contains a single integer , . The second line of standard input holds  non-negative integers (), separated by single spaces.

Your programme should print out  lines to the standard output, one for each test unit. Your programm should print to standard output minimal non-negative integer , such that  is a substring of , or NIE (no in Polish) if such  doesn't exist.