An Animal Contest 7 P4 - Squirrel Shenanigans

View as PDF

Submit solution


Points: 20
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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

Comments

There are no comments at the moment.