Alice and Bob are playing a game with strings. There will be $$$t$$$ rounds in the game. In each round, there will be a string $$$s$$$ consisting of lowercase English letters.

Alice moves first and both the players take alternate turns. Alice is allowed to remove any substring of even length (possibly empty) and Bob is allowed to remove any substring of odd length from $$$s$$$.

More formally, if there was a string $$$s = s_1s_2 \ldots s_k$$$ the player can choose a substring $$$s_ls_{l+1} \ldots s_{r-1}s_r$$$ with length of corresponding parity and remove it. After that the string will become $$$s = s_1 \ldots s_{l-1}s_{r+1} \ldots s_k$$$.

After the string becomes empty, the round ends and each player calculates his/her score for this round. The score of a player is the sum of values of all characters removed by him/her. The value of $$$\texttt{a}$$$ is $$$1$$$, the value of $$$\texttt{b}$$$ is $$$2$$$, the value of $$$\texttt{c}$$$ is $$$3$$$, $$$\ldots$$$, and the value of $$$\texttt{z}$$$ is $$$26$$$. The player with higher score wins the round. For each round, determine the winner and the difference between winner's and loser's scores. Assume that both players play optimally to maximize their score. It can be proved that a draw is impossible.

Let's call a string $$$s$$$ perfectly balanced if for all possible triplets $$$(t,u,v)$$$ such that $$$t$$$ is a non-empty substring of $$$s$$$ and $$$u$$$ and $$$v$$$ are characters present in $$$s$$$, the difference between the frequencies of $$$u$$$ and $$$v$$$ in $$$t$$$ is not more than $$$1$$$.

For example, the strings "aba" and "abc" are perfectly balanced but "abb" is not because for the triplet ("bb",'a','b'), the condition is not satisfied.

You are given a string $$$s$$$ consisting of lowercase English letters only. Your task is to determine whether $$$s$$$ is perfectly balanced or not.

A string $$$b$$$ is called a substring of another string $$$a$$$ if $$$b$$$ can be obtained by deleting some characters (possibly $$$0$$$) from the start and some characters (possibly $$$0$$$) from the end of $$$a$$$.

You are given a positive integer $$$n$$$. Let's call some positive integer $$$a$$$ without leading zeroes palindromic if it remains the same after reversing the order of its digits. Find the number of distinct ways to express $$$n$$$ as a sum of positive palindromic integers. Two ways are considered different if the frequency of at least one palindromic integer is different in them. For example, $$$5=4+1$$$ and $$$5=3+1+1$$$ are considered different but $$$5=3+1+1$$$ and $$$5=1+3+1$$$ are considered the same.

Formally, you need to find the number of distinct multisets of positive palindromic integers the sum of which is equal to $$$n$$$.

Since the answer can be quite large, print it modulo $$$10^9+7$$$.

Long ago, you thought of two finite arithmetic progressions $$$A$$$ and $$$B$$$. Then you found out another sequence $$$C$$$ containing all elements common to both $$$A$$$ and $$$B$$$. It is not hard to see that $$$C$$$ is also a finite arithmetic progression. After many years, you forgot what $$$A$$$ was but remember $$$B$$$ and $$$C$$$. You are, for some reason, determined to find this lost arithmetic progression. Before you begin this eternal search, you want to know how many different finite arithmetic progressions exist which can be your lost progression $$$A$$$.

Two arithmetic progressions are considered different if they differ in their first term, common difference or number of terms.

It may be possible that there are infinitely many such progressions, in which case you won't even try to look for them! Print $$$-1$$$ in all such cases.

Even if there are finite number of them, the answer might be very large. So, you are only interested to find the answer modulo $$$10^9+7$$$.

The symbol $$$\wedge$$$ is quite ambiguous, especially when used without context. Sometimes it is used to denote a power ($$$a\wedge b = a^b$$$) and sometimes it is used to denote the XOR operation ($$$a\wedge b=a\oplus b$$$).

You have an ambiguous expression $$$E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$$$. You can replace each $$$\wedge$$$ symbol with either a $$$\texttt{Power}$$$ operation or a $$$\texttt{XOR}$$$ operation to get an unambiguous expression $$$E'$$$.

The value of this expression $$$E'$$$ is determined according to the following rules:

• All $$$\texttt{Power}$$$ operations are performed before any $$$\texttt{XOR}$$$ operation. In other words, the $$$\texttt{Power}$$$ operation takes precedence over $$$\texttt{XOR}$$$ operation. For example, $$$4\;\texttt{XOR}\;6\;\texttt{Power}\;2=4\oplus (6^2)=4\oplus 36=32$$$.
• Consecutive powers are calculated from left to right. For example, $$$2\;\texttt{Power}\;3 \;\texttt{Power}\;4 = (2^3)^4 = 8^4 = 4096$$$.

You are given an array $$$B$$$ of length $$$n$$$ and an integer $$$k$$$. The array $$$A$$$ is given by $$$A_i=2^{B_i}$$$ and the expression $$$E$$$ is given by $$$E=A_1\wedge A_2\wedge A_3\wedge\ldots\wedge A_n$$$. You need to find the XOR of the values of all possible unambiguous expressions $$$E'$$$ which can be obtained from $$$E$$$ and has at least $$$k$$$ $$$\wedge$$$ symbols used as $$$\texttt{XOR}$$$ operation. Since the answer can be very large, you need to find it modulo $$$2^{2^{20}}$$$. Since this number can also be very large, you need to print its binary representation without leading zeroes. If the answer is equal to $$$0$$$, print $$$0$$$.

This is an interactive problem.

A city has $$$n^2$$$ buildings divided into a grid of $$$n$$$ rows and $$$n$$$ columns. You need to build a road of some length $$$D(A,B)$$$ of your choice between each pair of adjacent by side buildings $$$A$$$ and $$$B$$$. Due to budget limitations and legal restrictions, the length of each road must be a positive integer and the total length of all roads should not exceed $$$48\,000$$$.

There is a thief in the city who will start from the topmost, leftmost building (in the first row and the first column) and roam around the city, occasionally stealing artifacts from some of the buildings. He can move from one building to another adjacent building by travelling through the road which connects them.

You are unable to track down what buildings he visits and what path he follows to reach them. But there is one tracking mechanism in the city. The tracker is capable of storing a single integer $$$x$$$ which is initially $$$0$$$. Each time the thief travels from a building $$$A$$$ to another adjacent building $$$B$$$ through a road of length $$$D(A,B)$$$, the tracker changes $$$x$$$ to $$$x\oplus D(A,B)$$$. Each time the thief steals from a building, the tracker reports the value $$$x$$$ stored in it and resets it back to $$$0$$$.

It is known beforehand that the thief will steal in exactly $$$k$$$ buildings but you will know the values returned by the tracker only after the thefts actually happen. Your task is to choose the lengths of roads in such a way that no matter what strategy or routes the thief follows, you will be able to exactly tell the location of all the buildings where the thefts occurred from the values returned by the tracker.

First read a single line containing two integers $$$n$$$ $$$(2\leq n\leq 32)$$$ and $$$k$$$ $$$(1\leq k\leq 1024)$$$ denoting the number of rows and number of thefts respectively.

Let's denote the $$$j$$$-th building in the $$$i$$$-th row by $$$B_{i,j}$$$.

Then print $$$n$$$ lines each containing $$$n-1$$$ integers. The $$$j$$$-th integer of the $$$i$$$-th line must be the value of $$$D(B_{i,j},B_{i,j+1})$$$.

Then print $$$n-1$$$ lines each containing $$$n$$$ integers. The $$$j$$$-th integer of the $$$i$$$-th line must be the value of $$$D(B_{i,j},B_{i+1,j})$$$.

Remember that the total length of the roads must not exceed $$$48\,000$$$.

Then answer $$$k$$$ queries. First read the value $$$x$$$ returned by the tracker. Then print two integers denoting the row number and column number of the building where the theft occurred. After that you will be able to answer the next query (if such exists).

After printing the answers do not forget to output end of line and flush the output buffer. Otherwise you will get the verdict Idleness limit exceeded. To flush the buffer, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• Read documentation for other languages.

Hacks

You cannot make hacks in this problem.