Several Orz Pandas are in a line. However, God Wan is coming from left, while God Big Bread is coming from right. They're both very diaoable so Orz Pandas must hail to both of them.
The captain of Orz Pandas, CupSpirit, has invented a special 0-1 string to solve this problem. Assume S0is an empty string, and
∀i>0 Si= switch(Si-1)+”1”+reverse(Si-1)
Here “+” means concatenation of strings. reverse(x) means the result of reverting the string x, for example reverse(“100”)=”001”. And switch(x) means every '0' becomes '1' and every '1' becomes '0', for example switch(“100”)=”011”.
Now Captain CupSpirit has selected string SNto determine the direction of all Orz Pandas. If SN[i]=='0', the i-th Orz Panda should hail to God Wan. Otherwise the i-th Orz Panda should hail to God Big Bread. For example, if N = 3, the Orz Pandas would be like
Please determine the direction of K-th Orz Panda.