Саяхан Поликарпус “bitwise AND” гэдэг (AND гэж бас дуудагддаг) эерэг тооны үйлдлийг сурчээ. Одоо тэрээр өөрийн сурсан үйлдэлийн тусламжтайгаар сургуулийн IT-гийн багшид гайхалтай үйлдэл үзүүлэх гэж байна.

Тэгэхийн тулд Поликарпус бага зэрэг эрт сургууль дээр ирээд самбар дээр сөрөг биш $a_1, a_2 ,a_3, … , a_n$ тоонуудыг бичсэн. Мөн тэрээр квадрат матриц $n*n$ хэмжээтэй $b$ матрицийг бичсэн. $b$ матрицийн $i$-р мөрний $j$-р багананы (бид үүнийг $b_{ij}$ гэж тэмдэглэнэ.) тоо нь дараахтай тэнцэнэ:

-$a_i$ болон $a_j$ хоёр тооны AND $(b_{ij}$ = $a_{i}$ & $a_{j}$) үйлдэлийн хариу.

-хэрвээ $i = j$ бол -1.

$b$ матрицийг бичиж дуусгасныхаа дараа Поликарпус баяртайгаар a дараалалыг арчижээ. Гэхдээ асуудалын гол нь багш дараалалын тусламжтайгаар Поликарпусын тооцоолол зөв эсэхийг шалгадаг. Поликарпуст гэнэт дараалалыг сэргээх шаардлага гарсан ба сэргээхгүй бол тэр өөрийгөө зөв тоолж чаддаг гэдгийг батлаж чадахгүй. Поликарпуст өгөгдсөн $b$ матрицийн дагуу $a$ дараалалыг сэргээхэд туслаарай. Поликарпус том тоонд дургүй тиймээс сэргээгдсэн дараалалын тоонууд $10^9$-өөс хэтрэхгүй.

Оролт:

Эхний мөрөнд ганц $n$ тоо - $b$ матрицийн хэмжээ. Дараагийн $n$ мөр болгон $b$ матрицийг илэрхийлнэ. $i$-р мөр болгон $n$ ширхэг тоо агуулах ба $j$-р тоо нь $b_{ij}$ болно. $i$ нь $(1 ≤ i ≤ n)$ байх ба $b_{ii}$ = -1. Бүх $i, j$-ийн хувьд $(1≤i,j≤n; i≠n)$ байх ба энэ нөхцөлөөс $0 ≤ b_{ij} ≤ 10^9, b_{ij} = b_{ji}$ болно.

Гаралт:

$n$ ширхэг эерэг а дараалалын элементүүдийг хэвлэнэ. Зайгаар тусгаарлаж хэвлэнэ.

Бодлогын нөхцөлийг хангах а дараалал оршин байх ба хэд хэдэн хувилбартай бол та алыг нь ч хэвлэсэн болно.

Хэрвээ та “bitwise AND” үйлдэлийг мэдэхгүй бол доорхи линкээр орж уншаарай. http://en.wikipedia.org/wiki/Bitwise_operation