#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <string>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
/*
* the strassen algorithm implementation was taken from
* https://g...content-available-to-author-only...b.com/MartinThoma/matrix-multiplication
* */
// Set LEAF_SIZE to 1 if you want to the pure strassen algorithm
// otherwise, the ikj-algorithm will be applied when the split
// matrices are as small as LEAF_SIZE x LEAF_SIZE
int leafsize;
using namespace std;
typedef vector<int> vi;
/*
* Implementation of the strassen algorithm, similar to
* http://e...content-available-to-author-only...a.org/w/index.php?title=Strassen_algorithm&oldid=498910018#Source_code_of_the_Strassen_algorithm_in_C_language
*/
void strassen(vector< vector<int> > &A,
vector< vector<int> > &B,
vector< vector<int> > &C, unsigned int tam);
unsigned int nextPowerOfTwo(int n);
void strassenR(vector< vector<int> > &A,
vector< vector<int> > &B,
vector< vector<int> > &C,
int tam);
void sum(vector< vector<int> > &A,
vector< vector<int> > &B,
vector< vector<int> > &C, int tam);
void subtract(vector< vector<int> > &A,
vector< vector<int> > &B,
vector< vector<int> > &C, int tam);
void printMatrix(vector< vector<int> > matrix, int n);
void read(string filename, vector< vector<int> > &A, vector< vector<int> > &B);
void ikjalgorithm(vector< vector<int> > A,
vector< vector<int> > B,
vector< vector<int> > &C, int n) {
for (int i = 0; i < n; i++) {
for (int k = 0; k < n; k++) {
for (int j = 0; j < n; j++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
}
void strassenR(vector< vector<int> > &A,
vector< vector<int> > &B,
vector< vector<int> > &C, int tam) {
if (tam <= leafsize) {
ikjalgorithm(A, B, C, tam);
return;
}
// other cases are treated here:
else {
int newTam = tam/2;
vector<int> inner (newTam);
vector< vector<int> >
a11(newTam,inner), a12(newTam,inner), a21(newTam,inner), a22(newTam,inner),
b11(newTam,inner), b12(newTam,inner), b21(newTam,inner), b22(newTam,inner),
c11(newTam,inner), c12(newTam,inner), c21(newTam,inner), c22(newTam,inner),
p1(newTam,inner), p2(newTam,inner), p3(newTam,inner), p4(newTam,inner),
p5(newTam,inner), p6(newTam,inner), p7(newTam,inner),
aResult(newTam,inner), bResult(newTam,inner);
int i, j;
//dividing the matrices in 4 sub-matrices:
for (i = 0; i < newTam; i++) {
for (j = 0; j < newTam; j++) {
a11[i][j] = A[i][j];
a12[i][j] = A[i][j + newTam];
a21[i][j] = A[i + newTam][j];
a22[i][j] = A[i + newTam][j + newTam];
b11[i][j] = B[i][j];
b12[i][j] = B[i][j + newTam];
b21[i][j] = B[i + newTam][j];
b22[i][j] = B[i + newTam][j + newTam];
}
}
// Calculating p1 to p7:
sum(a11, a22, aResult, newTam); // a11 + a22
sum(b11, b22, bResult, newTam); // b11 + b22
strassenR(aResult, bResult, p1, newTam); // p1 = (a11+a22) * (b11+b22)
sum(a21, a22, aResult, newTam); // a21 + a22
strassenR(aResult, b11, p2, newTam); // p2 = (a21+a22) * (b11)
subtract(b12, b22, bResult, newTam); // b12 - b22
strassenR(a11, bResult, p3, newTam); // p3 = (a11) * (b12 - b22)
subtract(b21, b11, bResult, newTam); // b21 - b11
strassenR(a22, bResult, p4, newTam); // p4 = (a22) * (b21 - b11)
sum(a11, a12, aResult, newTam); // a11 + a12
strassenR(aResult, b22, p5, newTam); // p5 = (a11+a12) * (b22)
subtract(a21, a11, aResult, newTam); // a21 - a11
sum(b11, b12, bResult, newTam); // b11 + b12
strassenR(aResult, bResult, p6, newTam); // p6 = (a21-a11) * (b11+b12)
subtract(a12, a22, aResult, newTam); // a12 - a22
sum(b21, b22, bResult, newTam); // b21 + b22
strassenR(aResult, bResult, p7, newTam); // p7 = (a12-a22) * (b21+b22)
// calculating c21, c21, c11 e c22:
sum(p3, p5, c12, newTam); // c12 = p3 + p5
sum(p2, p4, c21, newTam); // c21 = p2 + p4
sum(p1, p4, aResult, newTam); // p1 + p4
sum(aResult, p7, bResult, newTam); // p1 + p4 + p7
subtract(bResult, p5, c11, newTam); // c11 = p1 + p4 - p5 + p7
sum(p1, p3, aResult, newTam); // p1 + p3
sum(aResult, p6, bResult, newTam); // p1 + p3 + p6
subtract(bResult, p2, c22, newTam); // c22 = p1 + p3 - p2 + p6
// Grouping the results obtained in a single matrix:
for (i = 0; i < newTam ; i++) {
for (j = 0 ; j < newTam ; j++) {
C[i][j] = c11[i][j];
C[i][j + newTam] = c12[i][j];
C[i + newTam][j] = c21[i][j];
C[i + newTam][j + newTam] = c22[i][j];
}
}
}
}
unsigned int nextPowerOfTwo(int n) {
return pow(2, int(ceil(log2(n))));
}
void strassen(vector< vector<int> > &A,
vector< vector<int> > &B,
vector< vector<int> > &C, unsigned int n) {
//unsigned int n = tam;
unsigned int m = nextPowerOfTwo(n);
vector<int> inner(m);
vector< vector<int> > APrep(m, inner), BPrep(m, inner), CPrep(m, inner);
for(unsigned int i=0; i<n; i++) {
for (unsigned int j=0; j<n; j++) {
APrep[i][j] = A[i][j];
BPrep[i][j] = B[i][j];
}
}
strassenR(APrep, BPrep, CPrep, m);
for(unsigned int i=0; i<n; i++) {
for (unsigned int j=0; j<n; j++) {
C[i][j] = CPrep[i][j];
}
}
}
void sum(vector< vector<int> > &A,
vector< vector<int> > &B,
vector< vector<int> > &C, int tam) {
int i, j;
for (i = 0; i < tam; i++) {
for (j = 0; j < tam; j++) {
C[i][j] = A[i][j] + B[i][j];
}
}
}
void subtract(vector< vector<int> > &A,
vector< vector<int> > &B,
vector< vector<int> > &C, int tam) {
int i, j;
for (i = 0; i < tam; i++) {
for (j = 0; j < tam; j++) {
C[i][j] = A[i][j] - B[i][j];
}
}
}
int getMatrixSize(string filename) {
string line;
ifstream infile;
infile.open (filename.c_str());
getline(infile, line);
return count(line.begin(), line.end(), '\t') + 1;
}
void read(string filename, vector< vector<int> > &A, vector< vector<int> > &B) {
string line;
FILE* matrixfile = freopen(filename.c_str(), "r", stdin);
if (matrixfile == 0) {
cerr << "Could not read file " << filename << endl;
return;
}
int i = 0, j, a;
while (getline(cin, line) && !line.empty()) {
istringstream iss(line);
j = 0;
while (iss >> a) {
A[i][j] = a;
j++;
}
i++;
}
i = 0;
while (getline(cin, line)) {
istringstream iss(line);
j = 0;
while (iss >> a) {
B[i][j] = a;
j++;
}
i++;
}
fclose (matrixfile);
}
void printMatrix(vector< vector<int> > matrix, int n) {
for (int i=0; i < n; i++) {
for (int j=0; j < n; j++) {
if (j != 0) {
cout << "\t";
}
cout << matrix[i][j];
}
cout << endl;
}
}
int main (int argc, char* argv[]) {
int n;
leafsize = 2048;
scanf("%d\n", &n);
vector<vi> A;
vector<int> inner (n);
vector< vector<int> > C(n, inner);
A.assign(n, vi());
for(int i = 0; i < n; i++) {
A[i].assign(n, 0);
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
char c;
scanf("%c", &c);
A[i][j] = c - '0';
} scanf("\n");
}
strassen(A, A, C, n);
/*
printMatrix(A, n);
printf("----------------------------------------\n");
printMatrix(C, n);
*/
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(C[i][j] > 0 and i != j and A[i][j] != 1)
ans++;
}
}
printf("%d\n", ans);
return 0;
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxzc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8ZnN0cmVhbT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y21hdGg+CgovKgogKiB0aGUgc3RyYXNzZW4gYWxnb3JpdGhtIGltcGxlbWVudGF0aW9uIHdhcyB0YWtlbiBmcm9tCiAqIGh0dHBzOi8vZy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uYi5jb20vTWFydGluVGhvbWEvbWF0cml4LW11bHRpcGxpY2F0aW9uCiAqICovCgovLyBTZXQgTEVBRl9TSVpFIHRvIDEgaWYgeW91IHdhbnQgdG8gdGhlIHB1cmUgc3RyYXNzZW4gYWxnb3JpdGhtCi8vIG90aGVyd2lzZSwgdGhlIGlrai1hbGdvcml0aG0gd2lsbCBiZSBhcHBsaWVkIHdoZW4gdGhlIHNwbGl0Ci8vIG1hdHJpY2VzIGFyZSBhcyBzbWFsbCBhcyBMRUFGX1NJWkUgeCBMRUFGX1NJWkUKaW50IGxlYWZzaXplOwoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CgovKgogKiBJbXBsZW1lbnRhdGlvbiBvZiB0aGUgc3RyYXNzZW4gYWxnb3JpdGhtLCBzaW1pbGFyIHRvIAogKiBodHRwOi8vZS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uYS5vcmcvdy9pbmRleC5waHA/dGl0bGU9U3RyYXNzZW5fYWxnb3JpdGhtJm9sZGlkPTQ5ODkxMDAxOCNTb3VyY2VfY29kZV9vZl90aGVfU3RyYXNzZW5fYWxnb3JpdGhtX2luX0NfbGFuZ3VhZ2UKICovCiAKdm9pZCBzdHJhc3Nlbih2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJkEsIAogICAgICAgICAgICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQiwgCiAgICAgICAgICAgICAgdmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZDLCB1bnNpZ25lZCBpbnQgdGFtKTsKdW5zaWduZWQgaW50IG5leHRQb3dlck9mVHdvKGludCBuKTsKdm9pZCBzdHJhc3NlblIodmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZBLCAKICAgICAgICAgICAgICB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJkIsIAogICAgICAgICAgICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQywgCiAgICAgICAgICAgICAgaW50IHRhbSk7CnZvaWQgc3VtKHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQSwgCiAgICAgICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQiwgCiAgICAgICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQywgaW50IHRhbSk7CnZvaWQgc3VidHJhY3QodmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZBLCAKICAgICAgICAgICAgICB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJkIsIAogICAgICAgICAgICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQywgaW50IHRhbSk7Cgp2b2lkIHByaW50TWF0cml4KHZlY3RvcjwgdmVjdG9yPGludD4gPiBtYXRyaXgsIGludCBuKTsKdm9pZCByZWFkKHN0cmluZyBmaWxlbmFtZSwgdmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZBLCB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJkIpOwoKdm9pZCBpa2phbGdvcml0aG0odmVjdG9yPCB2ZWN0b3I8aW50PiA+IEEsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiBCLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQywgaW50IG4pIHsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCBuOyBrKyspIHsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBuOyBqKyspIHsKICAgICAgICAgICAgICAgIENbaV1bal0gKz0gQVtpXVtrXSAqIEJba11bal07CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cn0KCnZvaWQgc3RyYXNzZW5SKHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQSwgCiAgICAgICAgICAgICAgdmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZCLCAKICAgICAgICAgICAgICB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJkMsIGludCB0YW0pIHsKICAgIGlmICh0YW0gPD0gbGVhZnNpemUpIHsKICAgICAgICBpa2phbGdvcml0aG0oQSwgQiwgQywgdGFtKTsKICAgICAgICByZXR1cm47CiAgICB9CiAKICAgIC8vIG90aGVyIGNhc2VzIGFyZSB0cmVhdGVkIGhlcmU6CiAgICBlbHNlIHsKICAgICAgICBpbnQgbmV3VGFtID0gdGFtLzI7CiAgICAgICAgdmVjdG9yPGludD4gaW5uZXIgKG5ld1RhbSk7CiAgICAgICAgdmVjdG9yPCB2ZWN0b3I8aW50PiA+IAogICAgICAgICAgICBhMTEobmV3VGFtLGlubmVyKSwgYTEyKG5ld1RhbSxpbm5lciksIGEyMShuZXdUYW0saW5uZXIpLCBhMjIobmV3VGFtLGlubmVyKSwKICAgICAgICAgICAgYjExKG5ld1RhbSxpbm5lciksIGIxMihuZXdUYW0saW5uZXIpLCBiMjEobmV3VGFtLGlubmVyKSwgYjIyKG5ld1RhbSxpbm5lciksCiAgICAgICAgICAgICAgYzExKG5ld1RhbSxpbm5lciksIGMxMihuZXdUYW0saW5uZXIpLCBjMjEobmV3VGFtLGlubmVyKSwgYzIyKG5ld1RhbSxpbm5lciksCiAgICAgICAgICAgIHAxKG5ld1RhbSxpbm5lciksIHAyKG5ld1RhbSxpbm5lciksIHAzKG5ld1RhbSxpbm5lciksIHA0KG5ld1RhbSxpbm5lciksIAogICAgICAgICAgICBwNShuZXdUYW0saW5uZXIpLCBwNihuZXdUYW0saW5uZXIpLCBwNyhuZXdUYW0saW5uZXIpLAogICAgICAgICAgICBhUmVzdWx0KG5ld1RhbSxpbm5lciksIGJSZXN1bHQobmV3VGFtLGlubmVyKTsKIAogICAgICAgIGludCBpLCBqOwogCiAgICAgICAgLy9kaXZpZGluZyB0aGUgbWF0cmljZXMgaW4gNCBzdWItbWF0cmljZXM6CiAgICAgICAgZm9yIChpID0gMDsgaSA8IG5ld1RhbTsgaSsrKSB7CiAgICAgICAgICAgIGZvciAoaiA9IDA7IGogPCBuZXdUYW07IGorKykgewogICAgICAgICAgICAgICAgYTExW2ldW2pdID0gQVtpXVtqXTsKICAgICAgICAgICAgICAgIGExMltpXVtqXSA9IEFbaV1baiArIG5ld1RhbV07CiAgICAgICAgICAgICAgICBhMjFbaV1bal0gPSBBW2kgKyBuZXdUYW1dW2pdOwogICAgICAgICAgICAgICAgYTIyW2ldW2pdID0gQVtpICsgbmV3VGFtXVtqICsgbmV3VGFtXTsKIAogICAgICAgICAgICAgICAgYjExW2ldW2pdID0gQltpXVtqXTsKICAgICAgICAgICAgICAgIGIxMltpXVtqXSA9IEJbaV1baiArIG5ld1RhbV07CiAgICAgICAgICAgICAgICBiMjFbaV1bal0gPSBCW2kgKyBuZXdUYW1dW2pdOwogICAgICAgICAgICAgICAgYjIyW2ldW2pdID0gQltpICsgbmV3VGFtXVtqICsgbmV3VGFtXTsKICAgICAgICAgICAgfQogICAgICAgIH0KIAogICAgICAgIC8vIENhbGN1bGF0aW5nIHAxIHRvIHA3OgogCiAgICAgICAgc3VtKGExMSwgYTIyLCBhUmVzdWx0LCBuZXdUYW0pOyAvLyBhMTEgKyBhMjIKICAgICAgICBzdW0oYjExLCBiMjIsIGJSZXN1bHQsIG5ld1RhbSk7IC8vIGIxMSArIGIyMgogICAgICAgIHN0cmFzc2VuUihhUmVzdWx0LCBiUmVzdWx0LCBwMSwgbmV3VGFtKTsgLy8gcDEgPSAoYTExK2EyMikgKiAoYjExK2IyMikKIAogICAgICAgIHN1bShhMjEsIGEyMiwgYVJlc3VsdCwgbmV3VGFtKTsgLy8gYTIxICsgYTIyCiAgICAgICAgc3RyYXNzZW5SKGFSZXN1bHQsIGIxMSwgcDIsIG5ld1RhbSk7IC8vIHAyID0gKGEyMSthMjIpICogKGIxMSkKIAogICAgICAgIHN1YnRyYWN0KGIxMiwgYjIyLCBiUmVzdWx0LCBuZXdUYW0pOyAvLyBiMTIgLSBiMjIKICAgICAgICBzdHJhc3NlblIoYTExLCBiUmVzdWx0LCBwMywgbmV3VGFtKTsgLy8gcDMgPSAoYTExKSAqIChiMTIgLSBiMjIpCiAKICAgICAgICBzdWJ0cmFjdChiMjEsIGIxMSwgYlJlc3VsdCwgbmV3VGFtKTsgLy8gYjIxIC0gYjExCiAgICAgICAgc3RyYXNzZW5SKGEyMiwgYlJlc3VsdCwgcDQsIG5ld1RhbSk7IC8vIHA0ID0gKGEyMikgKiAoYjIxIC0gYjExKQogCiAgICAgICAgc3VtKGExMSwgYTEyLCBhUmVzdWx0LCBuZXdUYW0pOyAvLyBhMTEgKyBhMTIKICAgICAgICBzdHJhc3NlblIoYVJlc3VsdCwgYjIyLCBwNSwgbmV3VGFtKTsgLy8gcDUgPSAoYTExK2ExMikgKiAoYjIyKSAgIAogCiAgICAgICAgc3VidHJhY3QoYTIxLCBhMTEsIGFSZXN1bHQsIG5ld1RhbSk7IC8vIGEyMSAtIGExMQogICAgICAgIHN1bShiMTEsIGIxMiwgYlJlc3VsdCwgbmV3VGFtKTsgLy8gYjExICsgYjEyCiAgICAgICAgc3RyYXNzZW5SKGFSZXN1bHQsIGJSZXN1bHQsIHA2LCBuZXdUYW0pOyAvLyBwNiA9IChhMjEtYTExKSAqIChiMTErYjEyKQogCiAgICAgICAgc3VidHJhY3QoYTEyLCBhMjIsIGFSZXN1bHQsIG5ld1RhbSk7IC8vIGExMiAtIGEyMgogICAgICAgIHN1bShiMjEsIGIyMiwgYlJlc3VsdCwgbmV3VGFtKTsgLy8gYjIxICsgYjIyCiAgICAgICAgc3RyYXNzZW5SKGFSZXN1bHQsIGJSZXN1bHQsIHA3LCBuZXdUYW0pOyAvLyBwNyA9IChhMTItYTIyKSAqIChiMjErYjIyKQogCiAgICAgICAgLy8gY2FsY3VsYXRpbmcgYzIxLCBjMjEsIGMxMSBlIGMyMjoKIAogICAgICAgIHN1bShwMywgcDUsIGMxMiwgbmV3VGFtKTsgLy8gYzEyID0gcDMgKyBwNQogICAgICAgIHN1bShwMiwgcDQsIGMyMSwgbmV3VGFtKTsgLy8gYzIxID0gcDIgKyBwNAogCiAgICAgICAgc3VtKHAxLCBwNCwgYVJlc3VsdCwgbmV3VGFtKTsgLy8gcDEgKyBwNAogICAgICAgIHN1bShhUmVzdWx0LCBwNywgYlJlc3VsdCwgbmV3VGFtKTsgLy8gcDEgKyBwNCArIHA3CiAgICAgICAgc3VidHJhY3QoYlJlc3VsdCwgcDUsIGMxMSwgbmV3VGFtKTsgLy8gYzExID0gcDEgKyBwNCAtIHA1ICsgcDcKIAogICAgICAgIHN1bShwMSwgcDMsIGFSZXN1bHQsIG5ld1RhbSk7IC8vIHAxICsgcDMKICAgICAgICBzdW0oYVJlc3VsdCwgcDYsIGJSZXN1bHQsIG5ld1RhbSk7IC8vIHAxICsgcDMgKyBwNgogICAgICAgIHN1YnRyYWN0KGJSZXN1bHQsIHAyLCBjMjIsIG5ld1RhbSk7IC8vIGMyMiA9IHAxICsgcDMgLSBwMiArIHA2CiAKICAgICAgICAvLyBHcm91cGluZyB0aGUgcmVzdWx0cyBvYnRhaW5lZCBpbiBhIHNpbmdsZSBtYXRyaXg6CiAgICAgICAgZm9yIChpID0gMDsgaSA8IG5ld1RhbSA7IGkrKykgewogICAgICAgICAgICBmb3IgKGogPSAwIDsgaiA8IG5ld1RhbSA7IGorKykgewogICAgICAgICAgICAgICAgQ1tpXVtqXSA9IGMxMVtpXVtqXTsKICAgICAgICAgICAgICAgIENbaV1baiArIG5ld1RhbV0gPSBjMTJbaV1bal07CiAgICAgICAgICAgICAgICBDW2kgKyBuZXdUYW1dW2pdID0gYzIxW2ldW2pdOwogICAgICAgICAgICAgICAgQ1tpICsgbmV3VGFtXVtqICsgbmV3VGFtXSA9IGMyMltpXVtqXTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKdW5zaWduZWQgaW50IG5leHRQb3dlck9mVHdvKGludCBuKSB7CiAgICByZXR1cm4gcG93KDIsIGludChjZWlsKGxvZzIobikpKSk7Cn0KCnZvaWQgc3RyYXNzZW4odmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZBLCAKICAgICAgICAgICAgICB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJkIsIAogICAgICAgICAgICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQywgdW5zaWduZWQgaW50IG4pIHsKICAgIC8vdW5zaWduZWQgaW50IG4gPSB0YW07CiAgICB1bnNpZ25lZCBpbnQgbSA9IG5leHRQb3dlck9mVHdvKG4pOwogICAgdmVjdG9yPGludD4gaW5uZXIobSk7CiAgICB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gQVByZXAobSwgaW5uZXIpLCBCUHJlcChtLCBpbm5lciksIENQcmVwKG0sIGlubmVyKTsKCiAgICBmb3IodW5zaWduZWQgaW50IGk9MDsgaTxuOyBpKyspIHsKICAgICAgICBmb3IgKHVuc2lnbmVkIGludCBqPTA7IGo8bjsgaisrKSB7CiAgICAgICAgICAgIEFQcmVwW2ldW2pdID0gQVtpXVtqXTsKICAgICAgICAgICAgQlByZXBbaV1bal0gPSBCW2ldW2pdOwogICAgICAgIH0KICAgIH0KCiAgICBzdHJhc3NlblIoQVByZXAsIEJQcmVwLCBDUHJlcCwgbSk7CiAgICBmb3IodW5zaWduZWQgaW50IGk9MDsgaTxuOyBpKyspIHsKICAgICAgICBmb3IgKHVuc2lnbmVkIGludCBqPTA7IGo8bjsgaisrKSB7CiAgICAgICAgICAgIENbaV1bal0gPSBDUHJlcFtpXVtqXTsKICAgICAgICB9CiAgICB9Cn0KCnZvaWQgc3VtKHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQSwgCiAgICAgICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQiwgCiAgICAgICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQywgaW50IHRhbSkgewogICAgaW50IGksIGo7CiAKICAgIGZvciAoaSA9IDA7IGkgPCB0YW07IGkrKykgewogICAgICAgIGZvciAoaiA9IDA7IGogPCB0YW07IGorKykgewogICAgICAgICAgICBDW2ldW2pdID0gQVtpXVtqXSArIEJbaV1bal07CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIHN1YnRyYWN0KHZlY3RvcjwgdmVjdG9yPGludD4gPiAmQSwgCiAgICAgICAgICAgICAgdmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZCLCAKICAgICAgICAgICAgICB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJkMsIGludCB0YW0pIHsKICAgIGludCBpLCBqOwogCiAgICBmb3IgKGkgPSAwOyBpIDwgdGFtOyBpKyspIHsKICAgICAgICBmb3IgKGogPSAwOyBqIDwgdGFtOyBqKyspIHsKICAgICAgICAgICAgQ1tpXVtqXSA9IEFbaV1bal0gLSBCW2ldW2pdOwogICAgICAgIH0KICAgIH0gICAKfQoKaW50IGdldE1hdHJpeFNpemUoc3RyaW5nIGZpbGVuYW1lKSB7CiAgICBzdHJpbmcgbGluZTsKICAgIGlmc3RyZWFtIGluZmlsZTsKICAgIGluZmlsZS5vcGVuIChmaWxlbmFtZS5jX3N0cigpKTsKICAgIGdldGxpbmUoaW5maWxlLCBsaW5lKTsKICAgIHJldHVybiBjb3VudChsaW5lLmJlZ2luKCksIGxpbmUuZW5kKCksICdcdCcpICsgMTsKfQoKdm9pZCByZWFkKHN0cmluZyBmaWxlbmFtZSwgdmVjdG9yPCB2ZWN0b3I8aW50PiA+ICZBLCB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gJkIpIHsKICAgIHN0cmluZyBsaW5lOwogICAgRklMRSogbWF0cml4ZmlsZSA9IGZyZW9wZW4oZmlsZW5hbWUuY19zdHIoKSwgInIiLCBzdGRpbik7CiAgICAKICAgIGlmIChtYXRyaXhmaWxlID09IDApIHsKICAgICAgICBjZXJyIDw8ICJDb3VsZCBub3QgcmVhZCBmaWxlICIgPDwgZmlsZW5hbWUgPDwgZW5kbDsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgaW50IGkgPSAwLCBqLCBhOwogICAgd2hpbGUgKGdldGxpbmUoY2luLCBsaW5lKSAmJiAhbGluZS5lbXB0eSgpKSB7CiAgICAgICAgaXN0cmluZ3N0cmVhbSBpc3MobGluZSk7CiAgICAgICAgaiA9IDA7CiAgICAgICAgd2hpbGUgKGlzcyA+PiBhKSB7CiAgICAgICAgICAgIEFbaV1bal0gPSBhOwogICAgICAgICAgICBqKys7CiAgICAgICAgfQogICAgICAgIGkrKzsKICAgIH0KCiAgICBpID0gMDsKICAgIHdoaWxlIChnZXRsaW5lKGNpbiwgbGluZSkpIHsKICAgICAgICBpc3RyaW5nc3RyZWFtIGlzcyhsaW5lKTsKICAgICAgICBqID0gMDsKICAgICAgICB3aGlsZSAoaXNzID4+IGEpIHsKICAgICAgICAgICAgQltpXVtqXSA9IGE7CiAgICAgICAgICAgIGorKzsKICAgICAgICB9CiAgICAgICAgaSsrOwogICAgfQoKICAgIGZjbG9zZSAobWF0cml4ZmlsZSk7Cn0KCnZvaWQgcHJpbnRNYXRyaXgodmVjdG9yPCB2ZWN0b3I8aW50PiA+IG1hdHJpeCwgaW50IG4pIHsKICAgIGZvciAoaW50IGk9MDsgaSA8IG47IGkrKykgewogICAgICAgIGZvciAoaW50IGo9MDsgaiA8IG47IGorKykgewogICAgICAgICAgICBpZiAoaiAhPSAwKSB7CiAgICAgICAgICAgICAgICBjb3V0IDw8ICJcdCI7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgY291dCA8PCBtYXRyaXhbaV1bal07CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgZW5kbDsKICAgIH0KfQoKaW50IG1haW4gKGludCBhcmdjLCBjaGFyKiBhcmd2W10pIHsKICAgIGludCBuOwogICAgbGVhZnNpemUgPSAyMDQ4OwogICAgc2NhbmYoIiVkXG4iLCAmbik7CiAgICB2ZWN0b3I8dmk+IEE7CiAgICB2ZWN0b3I8aW50PiBpbm5lciAobik7CiAgICB2ZWN0b3I8IHZlY3RvcjxpbnQ+ID4gQyhuLCBpbm5lcik7CiAgICBBLmFzc2lnbihuLCB2aSgpKTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBBW2ldLmFzc2lnbihuLCAwKTsKICAgIH0KICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBmb3IoaW50IGogPSAwOyBqIDwgbjsgaisrKSB7CiAgICAgICAgICAgIGNoYXIgYzsKICAgICAgICAgICAgc2NhbmYoIiVjIiwgJmMpOwogICAgICAgICAgICBBW2ldW2pdID0gYyAtICcwJzsKICAgICAgICB9IHNjYW5mKCJcbiIpOwogICAgfQogICAgc3RyYXNzZW4oQSwgQSwgQywgbik7CiAgICAvKgogICAgcHJpbnRNYXRyaXgoQSwgbik7CiAgICBwcmludGYoIi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS1cbiIpOwogICAgcHJpbnRNYXRyaXgoQywgbik7CiAgICAqLwogICAgaW50IGFucyA9IDA7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgZm9yKGludCBqID0gMDsgaiA8IG47IGorKykgewogICAgICAgICAgICBpZihDW2ldW2pdID4gMCBhbmQgaSAhPSBqIGFuZCBBW2ldW2pdICE9IDEpCiAgICAgICAgICAgICAgICBhbnMrKzsKICAgICAgICB9CiAgICB9CiAgICBwcmludGYoIiVkXG4iLCBhbnMpOwogICAgcmV0dXJuIDA7Cn0KCg==