All Closed-Walk Lengths

A country has N cities. Some ordered pairs of cities are connected by one-way roads. Two opposite one-way roads may both exist between the same pair of cities.

A traveler starts in one city and uses exactly one road per day. If the traveler can start from a city and return to that same city after using exactly x roads, then a closed walk of length x is possible.

The closed-walk string is an infinite binary string. Its characters are numbered from 1. The i-th character is 1 if a closed walk of length i is possible, and 0 otherwise.

This infinite string eventually becomes periodic. Write the repeating part in parentheses, as in 00110(1). If the same infinite string can be written in several ways, choose the representation that minimizes the number of characters outside the parentheses plus the number of characters inside the parentheses. If there is still a tie, choose the one with the shorter non-repeating prefix; if still tied, choose the one with the shorter repeating part.

Given the city information, output the shortest representation of the closed-walk string.

The first line contains the number of cities N.

Each of the next N lines contains a binary string of length N. If the j-th character of the i-th line is 1, there is a one-way road from city i to city j. If it is 0, there is no such road.

Print the shortest representation of the closed-walk string on one line. Enclose the repeating part in parentheses.

• 2 ≤ N ≤ 30
• Cities are numbered from 1 to N in input order.
• Each road character is either 0 or 1.