🏡 index : github.com/captn3m0/codechef.git

---
category_name: medium
problem_code: ANCOIMP
problem_name: 'Anticommutative implication'
languages_supported:
    - ADA
    - ASM
    - BASH
    - BF
    - C
    - 'C99 strict'
    - CAML
    - CLOJ
    - CLPS
    - 'CPP 4.3.2'
    - 'CPP 4.9.2'
    - CPP14
    - CS2
    - D
    - ERL
    - FORT
    - FS
    - GO
    - HASK
    - ICK
    - ICON
    - JAVA
    - JS
    - 'LISP clisp'
    - 'LISP sbcl'
    - LUA
    - NEM
    - NICE
    - NODEJS
    - 'PAS fpc'
    - 'PAS gpc'
    - PERL
    - PERL6
    - PHP
    - PIKE
    - PRLG
    - PYPY
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM chicken'
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '0.5 - 1'
source_sizelimit: '50000'
problem_author: kaizer
problem_tester: null
date_added: 29-03-2015
tags:
    - kaizer
editorial_url: 'http://discuss.codechef.com/problems/ANCOIMP'
time:
    view_start_date: 1434360600
    submit_start_date: 1434360600
    visible_start_date: 1434360600
    end_date: 1735669800
    current: 1493557455
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/JUNE15/mandarin/ANCOIMP.pdf) and [Russian](http://www.codechef.com/download/translated/JUNE15/russian/ANCOIMP.pdf).

Chef is impressed by mathematical logic and linear algebra. He wants to combine his favorite subjects, so he introduced the concept of logical operations on boolean matrices.

He defines **A → B** to be a matrix **C** such that **Cij = Aij → Bij** and **¬ A** to be a matrix **B** such that **Bij = ¬ Aij**

Now Chef wants to study such system of equations: **A → X = ¬ O** and **X → A = O**

 Where **O** is matrix such that all its entries is 0.
However, Chef realized that such system has solution if and only if **A = O**. Since such solution is too trivial, Chef has decided to search for an approximate solution for arbitrary **A**. Thus, Chef is searching for such **X** that **A → X = ¬ O** and **X → A** has as much as possible entries which are equal to 0.

But the solution space turned to be very large, so he reduced it to a matrices of a special form. Now he is looking for **X** such that **Xij = yi xor yj** for some boolean vector **y**. Since now **X** is symmetric, Chef restricts **A** to also be symmetric.

 Help Chef to resolve this difficult problem, or say that there is no solution.

 Here → denotes the logical implication. p → q = !p || (p && q). Here ¬ denotes logical negation. ¬p = !p

### Input

The first line of the input contains an integer **T** denoting the number of test cases. The description of **T** test cases follows.

The first line of each test case contains a single integer **N** denoting the size of **A**. The next **N** lines contain **N** space-separated integers **A\[i\]1**, **A\[i\]2**, ..., **A\[i\]N** denoting the i-th row of matrix **A**.
It's guaranteed that **A** is symmetric.

### Output

 For each test case, output a single line containing **N** integers - vector **y**, described in the statement, if there is a solution, or **-1**, if there is not. In case there are several solutions, print any solution.

### Constraints and Subtasks

- 0 ≤ **Aij** ≤ **1**

**Subtask 1: (15 points)**

- **1** ≤ **T** ≤  **1000**
- **1 ≤ N ≤ 10**

**Subtask 2: (25 points)**

- **1** ≤ **T** ≤  **500**
- **1 ≤ N ≤ 20**

**Subtask 3: (60 points)**

- **1** ≤ **T** ≤  **100**
- **1** ≤ **N** ≤ **1000**
- The sum of **N2** over all test cases in one test file does not exceed **106**

### Example

<pre><b>Input:</b>
3
4
0 0 0 1
0 0 0 1
0 0 0 0
1 1 0 0
4
1 0 0 1
0 1 0 1
0 0 0 0
1 1 0 0
2
0 0
0 0
<b>Output:</b>
0 0 1 1
-1
0 1
</pre>### Explanation

**Example case 1.**

Matrix which is determined by vector y is

<pre>
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0
</pre> 
Then **A → X = ¬ O** and **X → A** is

<pre>
1 1 0 1
1 1 0 1
0 0 1 1
1 1 1 1
</pre>**Example case 2.**

**A11 = 1** and **X11 = y1 xor y1 = 0**. So **A11 → X11 = 0** and condition **A → X = ¬ O** can not be satisfied.