After a separate mission, Tony has uncovered the hidden plans of the invading squirrel army. In an attempt to halt all communication on Earth — for an easier conquest — the squirrels are employing secret technologies to flood Discord with Nitro scams. These scams rely on users clicking into suspicious links (after being offered free Nitro, of course) and using their phones to scan QR codes, where then the real shenanigans start. The squirrels will then hijack the user's account and block all their friends after sending them the exact same scam message. Luckily, Tony has found a way to neutralize the threat:

There is a secret permutation ~a~ of ~1, 2, \dots, N~ where the ~i~-th element is denoted as ~a_i~. What it does, you have no idea — you're just going to have to trust. You are given a QR code represented by an ~N \times N~ binary matrix ~m~, which will help you find ~a~. The cell in the ~i~-th row from the top and ~j~-th column from the left is denoted as ~m_{i,j}~. An operation is defined as choosing some index ~i~ ~(1 < i < N)~ and replacing ~a_i~ with the median of ~a_{i-1}, a_i, a_{i+1}~. If ~m_{i,j} = 1~, it is possible to perform some number of operations (possibly none) on ~a~ and have ~a_i = j~. If ~m_{i,j} = 0~, this is impossible.

Please help Tony find ~a~ in order to survive the onslaught of Discord Nitro scams.

Constraints

~3 \leq N \leq 5\,000~

Input Specification

The first line contains a single integer ~N~.

The next ~N~ lines contain a binary string of length ~N~ representing each row of ~m~.

Output Specification

Output one line containing ~N~ integers: the permutation ~a~.

The data will guarantee that a valid permutation exists.

Sample Input

5
10000
00111
00110
00110
01000

Sample Output

1 5 3 4 2