#include <stdio.h>
#include <malloc.h> // malloc(), free()
#include <string.h> // memcpy()
#include <assert.h>

struct CSR
{
    int M;   // number of rows
    int N;   // number of columns
    int NNZ; // Number of Non-Zero elements
    int *A;
    int *IA;
    int *JA;
};


void readMatrix(struct CSR *matrix);
int equalMatrix(struct CSR A, struct CSR B);
void printMatrix(struct CSR matrix);
void printMatrixCSR(struct CSR matrix);
void transposeMatrix(const struct CSR A, struct CSR *B);
void multiplyMatrix(const struct CSR A, const struct CSR B, struct CSR *C);


int main()
{
    struct CSR A={0}, At={0}, B={0}, Bt={0}, C={0};

    int C0A[]={3,-1,5,1,2,2,-1},C0IA[]={0,3,5,5,6,7},C0JA[]={0,1,2,0,2,1,2};
    struct CSR C0={5,3,7,C0A,C0IA,C0JA};
    int C1A[]={3,2,6,3,7,5,-2},C1IA[]={0,3,6,7},C1JA[]={0,1,2,0,1,2,2};
    struct CSR C1={3,3,7,C1A,C1IA,C1JA};
    int C2A[]={-1,2,9,3,-13,-4,6,2,-1,1,8,10,4,-2},C2IA[]={0,2,4,8,11,14},C2JA[]={0,3,0,1,0,1,3,4,0,1,3,0,1,4};
    struct CSR C2={5,5,14,C2A,C2IA,C2JA};

    readMatrix(&A);
    readMatrix(&B);

    if ((A.M != B.M)||(A.N != B.N))
    {
        printf("Matrix A and B are not of the same dimension!\n");
        return 1;
    }

    printf("\n");
    printf("Matrix A:\n");
    printMatrix(A);

    printf("Matrix B:\n");
    printMatrix(B);

    transposeMatrix(B, &Bt);
    assert(equalMatrix(Bt, C0));
    printf("Transpose Matrix B:\n");
    printMatrix(Bt);

    multiplyMatrix(A, Bt, &C);
    assert(equalMatrix(C, C1));

    printf("Matrix A * Matrix B':\n");
    printMatrix(C);

    transposeMatrix(A, &At);
    printf("Transpose Matrix A:\n");
    printMatrix(At);

    multiplyMatrix(At, B, &C);
    assert(equalMatrix(C, C2));

    printf("Matrix A' * Matrix B:\n");
    printMatrix(C);

    if (A.A) free(A.A), free(A.IA), free(A.JA);
    if (At.A) free(At.A), free(At.IA), free(At.JA);
    if (B.A) free(B.A), free(B.IA), free(B.JA);
    if (Bt.A) free(Bt.A), free(Bt.IA), free(Bt.JA);
    if (C.A) free(C.A), free(C.IA), free(C.JA);

    getchar();getchar();
    return 0;
}


void readMatrix(struct CSR *matrix)
{
    int i, row, prevRow;
    scanf("%d%d%d", &(matrix->M), &(matrix->N), &(matrix->NNZ));
    matrix->A = (int *) malloc(matrix->NNZ*sizeof(int));
    matrix->IA = (int *) malloc((matrix->M+1)*sizeof(int));
    matrix->JA = (int *) malloc(matrix->NNZ*sizeof(int));
    for (prevRow=-1,i=0; i<matrix->NNZ; i++)
    {
        scanf("%d%d%d", &row, &(matrix->JA[i]), &(matrix->A[i]));
        if (row!=prevRow) 
        {
            matrix->IA[row] = i;
            while (++prevRow<row) 
                matrix->IA[prevRow] = matrix->IA[row];
        }
    }
    matrix->IA[matrix->M] = matrix->NNZ;
}


int equalMatrix(struct CSR A, struct CSR B)
{
    int i;
    if (A.M!=B.M || A.N!=B.N || A.NNZ!=B.NNZ)
        return 0;
    for (i=0; i<A.NNZ; i++)
        if (A.A[i]!=B.A[i] || A.JA[i]!=B.JA[i])
            return 0;
    for (i=0; i<=A.M; i++)
        if (A.IA[i]!=B.IA[i])
            return 0;
    return 1;
}


void printMatrix(struct CSR matrix)
{
    int i, row;
    printf("%d * %d matrix with %d non-zero item:\n",
           matrix.M, matrix.N, matrix.NNZ);
    for (row=i=0; i<matrix.NNZ; i++)
    {
        while (i>=matrix.IA[row+1]) row++;
        printf("<%d,%d:%d>\n", row, matrix.JA[i], matrix.A[i]);
    }
    printf("====================\n");
}


void printMatrixCSR(struct CSR matrix)
{
    int i, iRow=0;
    printf("%d * %d matrix with %d non-zero item:\n",
           matrix.M, matrix.N, matrix.NNZ);
    printf("A = ");
    for (i=0; i<matrix.NNZ; i++)
        printf("%d ", matrix.A[i]);
    printf("\nIA = ");
    for (i=0; i<=matrix.M; i++)
        printf("%d ", matrix.IA[i]);
    printf("\nJA = ");
    for (i=0; i<matrix.NNZ; i++)
        printf("%d ", matrix.JA[i]);
    printf("\n====================\n");
}


void transposeMatrix(const struct CSR A, struct CSR *B)
{
    int i, iB=0, row, *index;

    B->M = A.N, B->N = A.M, B->NNZ = A.NNZ;

    if (B->A) free(B->A), free(B->IA), free(B->JA);
    B->A = (int *) malloc(B->NNZ*sizeof(int));
    B->IA = (int *) malloc((B->M+1)*sizeof(int));
    index = (int *) malloc((B->M+1)*sizeof(int));
    B->JA = (int *) malloc(B->NNZ*sizeof(int));

    for (i=0; i<=A.N; i++)
        B->IA[i] = 0;
    for (i=0; i<A.NNZ; i++)
        B->IA[A.JA[i]+1]++; // counting element's in B's row
    for (i=1; i<=B->M; i++)
        index[i] = B->IA[i] += B->IA[i-1]; // accumulating
    index[0] = 0; 

    for (row=0,i=0; i<A.NNZ; i++)
    {
        while (i>=A.IA[row+1]) row++;
        iB = index[A.JA[i]]++;
        B->A[iB] = A.A[i];
        B->JA[iB] = row;
    }
    free(index);
}


void multiplyMatrix(const struct CSR A, const struct CSR B, struct CSR *C)
{
    int iA, iC, iA1, iB1, iArow, iCrow, iA1row, iB1row, sum, *tmp;
    struct CSR B1 = {0};
    transposeMatrix(B, &B1);

    if (C->A) free(C->A), free(C->IA), free(C->JA);
    C->M = A.M;
    C->N = B.N;
    C->A = (int *) malloc(C->M*C->N*sizeof(int)); // temporary
    C->IA = (int *) malloc((C->M+1)*sizeof(int));
    C->JA = (int *) malloc(C->M*C->N*sizeof(int)); // temporary

    iA = iC = iArow = iCrow = C->IA[0] = 0;
    while (iA < A.NNZ)
    {
        sum = 0;
        iA1 = iA; iA1row = iArow; 
        iB1 = iB1row = 0;
        while (iB1 < B1.NNZ)
        {
            if (A.JA[iA1] == B1.JA[iB1])
            {
                sum += A.A[iA1] * B1.A[iB1];
                iA1++; iB1++;
            }
            else if (A.JA[iA1] > B1.JA[iB1])
                iB1++;
            else // if (A.JA[iA1] < B1.JA[iB1])
                iA1++;
            if (iA1 >= A.IA[iA1row+1])
                while (iB1 < B1.IA[iB1row+1]) iB1++;
            if (iB1 >= B1.IA[iB1row+1])
            {
                if (iB1 < B1.NNZ)
                    iA1 = iA;
                else
                    iA1 = A.IA[iA1row+1];
                if (sum!=0)
                {
                    while (iA1row > iCrow) C->IA[++iCrow] = iC;
                    C->JA[iC] = iB1row;
                    C->A[iC++] = sum;
                    sum = 0;
                }
                while (iA1>=A.IA[iA1row+1]) iA1row++;
                while (iB1>=B1.IA[iB1row+1]) iB1row++;
            }
        }
        iA = iA1, iArow = iA1row;
    }
    C->NNZ = iC;
    C->IA[C->M] = iC;

    tmp = C->A;
    C->A = (int *) malloc(C->NNZ*sizeof(int));
    memcpy(C->A, tmp, C->NNZ*sizeof(int));
    free(tmp);

    tmp = C->JA;
    C->JA = (int *) malloc(C->NNZ*sizeof(int));
    memcpy(C->JA, tmp, C->NNZ*sizeof(int));
    free(tmp);

    free(B1.A), free(B1.IA), free(B1.JA);
}

/*

Sample inputs:
3 5 7
0 1 3
0 3 1
1 0 1
1 2 3
1 3 4
2 2 -2
2 4 2
3 5 7
0 0 3
0 1 1
1 0 -1
1 3 2
2 0 5
2 1 2
2 4 -1

*/