#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <mpi.h>
#define MAX_STRING 10000
#define INFINITY 1000000
int Read_n(int my_rank, MPI_Comm comm);
MPI_Datatype Build_blk_col_type(int n, int loc_n);
void Read_matrix(int loc_mat[], int n, int loc_n,
MPI_Datatype blk_col_mpi_t, int my_rank, MPI_Comm comm);
void Print_local_matrix(int loc_mat[], int n, int loc_n, int my_rank);
void Print_matrix(int loc_mat[], int n, int loc_n,
MPI_Datatype blk_col_mpi_t, int my_rank, MPI_Comm comm);
void Dijkstra(int mat[], int dist[], int pred[], int n, int loc_n, int my_rank,
MPI_Comm comm);
void Initialize_matrix(int mat[], int loc_dist[], int loc_pred[], int known[],
int loc_n, int my_rank);
int Find_min_dist(int loc_dist[], int known[], int loc_n, int my_rank,
MPI_Comm comm);
int Global_vertex(int loc_u, int loc_n, int my_rank);
void Print_dists(int loc_dist[], int n, int loc_n, int my_rank, MPI_Comm comm);
void Print_paths(int loc_pred[], int n, int loc_n, int my_rank, MPI_Comm comm);
int main(int argc, char* argv[]) {
int *loc_mat, *loc_dist, *loc_pred;
int n, loc_n, p, my_rank;
MPI_Comm comm;
MPI_Datatype blk_col_mpi_t;
MPI_Init(&argc, &argv);
comm = MPI_COMM_WORLD;
MPI_Comm_size(comm, &p);
MPI_Comm_rank(comm, &my_rank);
n = Read_n(my_rank, comm);
loc_n = n/p;
loc_mat
= malloc(n
*loc_n
*sizeof(int)); loc_dist
= malloc(n
*loc_n
*sizeof(int)); loc_pred
= malloc(n
*loc_n
*sizeof(int)); blk_col_mpi_t = Build_blk_col_type(n, loc_n);
Read_matrix(loc_mat, n, loc_n, blk_col_mpi_t, my_rank, comm);
Dijkstra(loc_mat, loc_dist, loc_pred, n, loc_n, my_rank, comm);
Print_dists(loc_dist, n, loc_n, my_rank, comm);
Print_paths(loc_pred, n, loc_n, my_rank, comm);
MPI_Type_free(&blk_col_mpi_t);
MPI_Finalize();
return 0;
}
int Read_n(int my_rank, MPI_Comm comm) {
int n;
if (my_rank == 0)
printf("Enter number of vertices in the matrix: \n"); MPI_Bcast(&n, 1, MPI_INT, 0, comm);
return n;
}
MPI_Datatype Build_blk_col_type(int n, int loc_n) {
MPI_Aint lb, extent;
MPI_Datatype block_mpi_t;
MPI_Datatype first_bc_mpi_t;
MPI_Datatype blk_col_mpi_t;
MPI_Type_contiguous(loc_n, MPI_INT, &block_mpi_t);
MPI_Type_get_extent(block_mpi_t, &lb, &extent);
MPI_Type_vector(n, loc_n, n, MPI_INT, &first_bc_mpi_t);
MPI_Type_create_resized(first_bc_mpi_t, lb, extent,
&blk_col_mpi_t);
MPI_Type_commit(&blk_col_mpi_t);
MPI_Type_free(&block_mpi_t);
MPI_Type_free(&first_bc_mpi_t);
return blk_col_mpi_t;
}
void Read_matrix(int loc_mat[], int n, int loc_n,
MPI_Datatype blk_col_mpi_t, int my_rank, MPI_Comm comm) {
int* mat = NULL, i, j;
if (my_rank == 0) {
mat
= malloc(n
*n
*sizeof(int)); for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &mat
[i
*n
+ j
]); }
MPI_Scatter(mat, 1, blk_col_mpi_t,
loc_mat, n*loc_n, MPI_INT, 0, comm);
if (my_rank
== 0) free(mat
); }
void Print_local_matrix(int loc_mat[], int n, int loc_n, int my_rank) {
char temp[MAX_STRING];
char *cp = temp;
int i, j;
sprintf(cp
, "Proc %d >\n", my_rank
); for (i = 0; i < n; i++) {
for (j = 0; j < loc_n; j++) {
if (loc_mat[i*loc_n + j] == INFINITY)
else
sprintf(cp
, "%2d ", loc_mat
[i
*loc_n
+ j
]); }
}
}
void Print_matrix(int loc_mat[], int n, int loc_n,
MPI_Datatype blk_col_mpi_t, int my_rank, MPI_Comm comm) {
int* mat = NULL, i, j;
if (my_rank
== 0) mat
= malloc(n
*n
*sizeof(int)); MPI_Gather(loc_mat, n*loc_n, MPI_INT,
mat, 1, blk_col_mpi_t, 0, comm);
if (my_rank == 0) {
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
if (mat[i*n + j] == INFINITY)
else
}
}
}
void Dijkstra(int mat[], int loc_dist[], int loc_pred[], int n, int loc_n,
int my_rank, MPI_Comm comm) {
int i, u, *known, new_dist;
int loc_u, loc_v;
known
= malloc(loc_n
*sizeof(int)); Initialize_matrix(mat, loc_dist, loc_pred, known, loc_n, my_rank);
for (i = 1; i < n; i++) {
loc_u = Find_min_dist(loc_dist, known, loc_n, my_rank, comm);
int my_min[2], glbl_min[2];
int g_min_dist;
if (loc_u < INFINITY) {
my_min[0] = loc_dist[loc_u];
my_min[1] = Global_vertex(loc_u, loc_n, my_rank);
} else {
my_min[0] = INFINITY;
my_min[1] = INFINITY;
}
MPI_Allreduce(my_min, glbl_min, 1, MPI_2INT, MPI_MINLOC, comm);
u = glbl_min[1];
g_min_dist = glbl_min[0];
if (u/loc_n == my_rank) {
loc_u = u % loc_n;
known[loc_u] = 1;
}
for (loc_v = 0; loc_v < loc_n; loc_v++)
if (!known[loc_v]) {
new_dist = g_min_dist + mat[u*loc_n + loc_v];
if (new_dist < loc_dist[loc_v]) {
loc_dist[loc_v] = new_dist;
loc_pred[loc_v] = u;
}
}
}
}
void Initialize_matrix(int mat[], int loc_dist[], int loc_pred[], int known[],
int loc_n, int my_rank) {
for (int v = 0; v < loc_n; v++) {
loc_dist[v] = mat[0*loc_n + v];
loc_pred[v] = 0;
known[v] = 0;
}
if (my_rank == 0) {
known[0] = 1;
}
}
int Find_min_dist(int loc_dist[], int loc_known[], int loc_n, int my_rank,
MPI_Comm comm) {
int loc_v, loc_u;
int loc_min_dist = INFINITY;
loc_u = INFINITY;
for (loc_v = 0; loc_v < loc_n; loc_v++)
if (!loc_known[loc_v])
if (loc_dist[loc_v] < loc_min_dist) {
loc_u = loc_v;
loc_min_dist = loc_dist[loc_v];
}
return loc_u;
}
int Global_vertex(int loc_u, int loc_n, int my_rank) {
int global_u = loc_u + my_rank*loc_n;
return global_u;
}
void Print_dists(int loc_dist[], int n, int loc_n, int my_rank, MPI_Comm comm) {
int v;
int* dist = NULL;
if (my_rank == 0) {
}
MPI_Gather(loc_dist, loc_n, MPI_INT, dist, loc_n, MPI_INT, 0, comm);
if (my_rank == 0) {
printf("The distance from 0 to each vertex is:\n"); for (v = 1; v < n; v++)
printf("%3d %4d\n", v
, dist
[v
]); }
}
void Print_paths(int loc_pred[], int n, int loc_n, int my_rank, MPI_Comm comm) {
int v, w, *path, count, i;
int* pred = NULL;
if (my_rank == 0) {
}
MPI_Gather(loc_pred, loc_n, MPI_INT, pred, loc_n, MPI_INT, 0, comm);
if (my_rank == 0) {
printf("The shortest path from 0 to each vertex is:\n"); for (v = 1; v < n; v++) {
count = 0;
w = v;
while (w != 0) {
path[count] = w;
count++;
w = pred[w];
}
for (i = count-1; i >= 0; i--)
}
}
}
CiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPG1waS5oPgojZGVmaW5lIE1BWF9TVFJJTkcgMTAwMDAKI2RlZmluZSBJTkZJTklUWSAxMDAwMDAwCmludCBSZWFkX24oaW50IG15X3JhbmssIE1QSV9Db21tIGNvbW0pOwpNUElfRGF0YXR5cGUgQnVpbGRfYmxrX2NvbF90eXBlKGludCBuLCBpbnQgbG9jX24pOwp2b2lkIFJlYWRfbWF0cml4KGludCBsb2NfbWF0W10sIGludCBuLCBpbnQgbG9jX24sCiBNUElfRGF0YXR5cGUgYmxrX2NvbF9tcGlfdCwgaW50IG15X3JhbmssIE1QSV9Db21tIGNvbW0pOwp2b2lkIFByaW50X2xvY2FsX21hdHJpeChpbnQgbG9jX21hdFtdLCBpbnQgbiwgaW50IGxvY19uLCBpbnQgbXlfcmFuayk7CnZvaWQgUHJpbnRfbWF0cml4KGludCBsb2NfbWF0W10sIGludCBuLCBpbnQgbG9jX24sCiBNUElfRGF0YXR5cGUgYmxrX2NvbF9tcGlfdCwgaW50IG15X3JhbmssIE1QSV9Db21tIGNvbW0pOwp2b2lkIERpamtzdHJhKGludCBtYXRbXSwgaW50IGRpc3RbXSwgaW50IHByZWRbXSwgaW50IG4sIGludCBsb2NfbiwgaW50IG15X3JhbmssCiBNUElfQ29tbSBjb21tKTsKdm9pZCBJbml0aWFsaXplX21hdHJpeChpbnQgbWF0W10sIGludCBsb2NfZGlzdFtdLCBpbnQgbG9jX3ByZWRbXSwgaW50IGtub3duW10sCiBpbnQgbG9jX24sIGludCBteV9yYW5rKTsKaW50IEZpbmRfbWluX2Rpc3QoaW50IGxvY19kaXN0W10sIGludCBrbm93bltdLCBpbnQgbG9jX24sIGludCBteV9yYW5rLAogTVBJX0NvbW0gY29tbSk7CmludCBHbG9iYWxfdmVydGV4KGludCBsb2NfdSwgaW50IGxvY19uLCBpbnQgbXlfcmFuayk7CnZvaWQgUHJpbnRfZGlzdHMoaW50IGxvY19kaXN0W10sIGludCBuLCBpbnQgbG9jX24sIGludCBteV9yYW5rLCBNUElfQ29tbSBjb21tKTsKdm9pZCBQcmludF9wYXRocyhpbnQgbG9jX3ByZWRbXSwgaW50IG4sIGludCBsb2NfbiwgaW50IG15X3JhbmssIE1QSV9Db21tIGNvbW0pOwppbnQgbWFpbihpbnQgYXJnYywgY2hhciogYXJndltdKSB7CiBpbnQgKmxvY19tYXQsICpsb2NfZGlzdCwgKmxvY19wcmVkOwogaW50IG4sIGxvY19uLCBwLCBteV9yYW5rOwogTVBJX0NvbW0gY29tbTsKIE1QSV9EYXRhdHlwZSBibGtfY29sX21waV90OwogTVBJX0luaXQoJmFyZ2MsICZhcmd2KTsKIGNvbW0gPSBNUElfQ09NTV9XT1JMRDsKIE1QSV9Db21tX3NpemUoY29tbSwgJnApOwogTVBJX0NvbW1fcmFuayhjb21tLCAmbXlfcmFuayk7CiBuID0gUmVhZF9uKG15X3JhbmssIGNvbW0pOwogbG9jX24gPSBuL3A7CiBsb2NfbWF0ID0gbWFsbG9jKG4qbG9jX24qc2l6ZW9mKGludCkpOwogbG9jX2Rpc3QgPSBtYWxsb2Mobipsb2NfbipzaXplb2YoaW50KSk7CiBsb2NfcHJlZCA9IG1hbGxvYyhuKmxvY19uKnNpemVvZihpbnQpKTsKIGJsa19jb2xfbXBpX3QgPSBCdWlsZF9ibGtfY29sX3R5cGUobiwgbG9jX24pOwogUmVhZF9tYXRyaXgobG9jX21hdCwgbiwgbG9jX24sIGJsa19jb2xfbXBpX3QsIG15X3JhbmssIGNvbW0pOwogRGlqa3N0cmEobG9jX21hdCwgbG9jX2Rpc3QsIGxvY19wcmVkLCBuLCBsb2NfbiwgbXlfcmFuaywgY29tbSk7CiBQcmludF9kaXN0cyhsb2NfZGlzdCwgbiwgbG9jX24sIG15X3JhbmssIGNvbW0pOwogUHJpbnRfcGF0aHMobG9jX3ByZWQsIG4sIGxvY19uLCBteV9yYW5rLCBjb21tKTsKIGZyZWUobG9jX21hdCk7CiBmcmVlKGxvY19kaXN0KTsKIGZyZWUobG9jX3ByZWQpOwogTVBJX1R5cGVfZnJlZSgmYmxrX2NvbF9tcGlfdCk7CiBNUElfRmluYWxpemUoKTsKIHJldHVybiAwOwp9CmludCBSZWFkX24oaW50IG15X3JhbmssIE1QSV9Db21tIGNvbW0pIHsKIGludCBuOwogaWYgKG15X3JhbmsgPT0gMCkKIHByaW50ZigiRW50ZXIgbnVtYmVyIG9mIHZlcnRpY2VzIGluIHRoZSBtYXRyaXg6IFxuIik7CiBzY2FuZigiJWQiLCAmbik7CiBNUElfQmNhc3QoJm4sIDEsIE1QSV9JTlQsIDAsIGNvbW0pOwogcmV0dXJuIG47Cn0KTVBJX0RhdGF0eXBlIEJ1aWxkX2Jsa19jb2xfdHlwZShpbnQgbiwgaW50IGxvY19uKSB7CiBNUElfQWludCBsYiwgZXh0ZW50OwogTVBJX0RhdGF0eXBlIGJsb2NrX21waV90OwogTVBJX0RhdGF0eXBlIGZpcnN0X2JjX21waV90OwogTVBJX0RhdGF0eXBlIGJsa19jb2xfbXBpX3Q7CiBNUElfVHlwZV9jb250aWd1b3VzKGxvY19uLCBNUElfSU5ULCAmYmxvY2tfbXBpX3QpOwogTVBJX1R5cGVfZ2V0X2V4dGVudChibG9ja19tcGlfdCwgJmxiLCAmZXh0ZW50KTsKIE1QSV9UeXBlX3ZlY3RvcihuLCBsb2NfbiwgbiwgTVBJX0lOVCwgJmZpcnN0X2JjX21waV90KTsKIE1QSV9UeXBlX2NyZWF0ZV9yZXNpemVkKGZpcnN0X2JjX21waV90LCBsYiwgZXh0ZW50LAogJmJsa19jb2xfbXBpX3QpOwogTVBJX1R5cGVfY29tbWl0KCZibGtfY29sX21waV90KTsKIE1QSV9UeXBlX2ZyZWUoJmJsb2NrX21waV90KTsKIE1QSV9UeXBlX2ZyZWUoJmZpcnN0X2JjX21waV90KTsKIHJldHVybiBibGtfY29sX21waV90Owp9CnZvaWQgUmVhZF9tYXRyaXgoaW50IGxvY19tYXRbXSwgaW50IG4sIGludCBsb2NfbiwKIE1QSV9EYXRhdHlwZSBibGtfY29sX21waV90LCBpbnQgbXlfcmFuaywgTVBJX0NvbW0gY29tbSkgewogaW50KiBtYXQgPSBOVUxMLCBpLCBqOwogaWYgKG15X3JhbmsgPT0gMCkgewogbWF0ID0gbWFsbG9jKG4qbipzaXplb2YoaW50KSk7CiBmb3IgKGkgPSAwOyBpIDwgbjsgaSsrKQogZm9yIChqID0gMDsgaiA8IG47IGorKykKIHNjYW5mKCIlZCIsICZtYXRbaSpuICsgal0pOwogfQogTVBJX1NjYXR0ZXIobWF0LCAxLCBibGtfY29sX21waV90LAogbG9jX21hdCwgbipsb2NfbiwgTVBJX0lOVCwgMCwgY29tbSk7CgogaWYgKG15X3JhbmsgPT0gMCkgZnJlZShtYXQpOwp9CnZvaWQgUHJpbnRfbG9jYWxfbWF0cml4KGludCBsb2NfbWF0W10sIGludCBuLCBpbnQgbG9jX24sIGludCBteV9yYW5rKSB7CiBjaGFyIHRlbXBbTUFYX1NUUklOR107CiBjaGFyICpjcCA9IHRlbXA7CiBpbnQgaSwgajsKIHNwcmludGYoY3AsICJQcm9jICVkID5cbiIsIG15X3JhbmspOwogY3AgPSB0ZW1wICsgc3RybGVuKHRlbXApOwogZm9yIChpID0gMDsgaSA8IG47IGkrKykgewogZm9yIChqID0gMDsgaiA8IGxvY19uOyBqKyspIHsKIGlmIChsb2NfbWF0W2kqbG9jX24gKyBqXSA9PSBJTkZJTklUWSkKIHNwcmludGYoY3AsICIgaSAiKTsKIGVsc2UKIHNwcmludGYoY3AsICIlMmQgIiwgbG9jX21hdFtpKmxvY19uICsgal0pOwogY3AgPSB0ZW1wICsgc3RybGVuKHRlbXApOwogfQogc3ByaW50ZihjcCwgIlxuIik7CiBjcCA9IHRlbXAgKyBzdHJsZW4odGVtcCk7CiB9CiBwcmludGYoIiVzXG4iLCB0ZW1wKTsKfQp2b2lkIFByaW50X21hdHJpeChpbnQgbG9jX21hdFtdLCBpbnQgbiwgaW50IGxvY19uLAogTVBJX0RhdGF0eXBlIGJsa19jb2xfbXBpX3QsIGludCBteV9yYW5rLCBNUElfQ29tbSBjb21tKSB7CiBpbnQqIG1hdCA9IE5VTEwsIGksIGo7CgogaWYgKG15X3JhbmsgPT0gMCkgbWF0ID0gbWFsbG9jKG4qbipzaXplb2YoaW50KSk7CiBNUElfR2F0aGVyKGxvY19tYXQsIG4qbG9jX24sIE1QSV9JTlQsCiBtYXQsIDEsIGJsa19jb2xfbXBpX3QsIDAsIGNvbW0pOwogaWYgKG15X3JhbmsgPT0gMCkgewogZm9yIChpID0gMDsgaSA8IG47IGkrKykgewogZm9yIChqID0gMDsgaiA8IG47IGorKykKIGlmIChtYXRbaSpuICsgal0gPT0gSU5GSU5JVFkpCiBwcmludGYoIiBpICIpOwogZWxzZQogcHJpbnRmKCIlMmQgIiwgbWF0W2kqbiArIGpdKTsKIHByaW50ZigiXG4iKTsKIH0KIGZyZWUobWF0KTsKIH0KfQp2b2lkIERpamtzdHJhKGludCBtYXRbXSwgaW50IGxvY19kaXN0W10sIGludCBsb2NfcHJlZFtdLCBpbnQgbiwgaW50IGxvY19uLAogaW50IG15X3JhbmssIE1QSV9Db21tIGNvbW0pIHsKIGludCBpLCB1LCAqa25vd24sIG5ld19kaXN0OwogaW50IGxvY191LCBsb2NfdjsKIGtub3duID0gbWFsbG9jKGxvY19uKnNpemVvZihpbnQpKTsKIEluaXRpYWxpemVfbWF0cml4KG1hdCwgbG9jX2Rpc3QsIGxvY19wcmVkLCBrbm93biwgbG9jX24sIG15X3JhbmspOwogZm9yIChpID0gMTsgaSA8IG47IGkrKykgewogbG9jX3UgPSBGaW5kX21pbl9kaXN0KGxvY19kaXN0LCBrbm93biwgbG9jX24sIG15X3JhbmssIGNvbW0pOwogaW50IG15X21pblsyXSwgZ2xibF9taW5bMl07CiBpbnQgZ19taW5fZGlzdDsKIGlmIChsb2NfdSA8IElORklOSVRZKSB7CiBteV9taW5bMF0gPSBsb2NfZGlzdFtsb2NfdV07CiBteV9taW5bMV0gPSBHbG9iYWxfdmVydGV4KGxvY191LCBsb2NfbiwgbXlfcmFuayk7CiB9IGVsc2UgewogbXlfbWluWzBdID0gSU5GSU5JVFk7CiBteV9taW5bMV0gPSBJTkZJTklUWTsKIH0gCiBNUElfQWxscmVkdWNlKG15X21pbiwgZ2xibF9taW4sIDEsIE1QSV8ySU5ULCBNUElfTUlOTE9DLCBjb21tKTsKIHUgPSBnbGJsX21pblsxXTsKIGdfbWluX2Rpc3QgPSBnbGJsX21pblswXTsKIGlmICh1L2xvY19uID09IG15X3JhbmspIHsKIGxvY191ID0gdSAlIGxvY19uOwoga25vd25bbG9jX3VdID0gMTsKIH0KIGZvciAobG9jX3YgPSAwOyBsb2NfdiA8IGxvY19uOyBsb2NfdisrKQogaWYgKCFrbm93bltsb2Nfdl0pIHsKIG5ld19kaXN0ID0gZ19taW5fZGlzdCArIG1hdFt1KmxvY19uICsgbG9jX3ZdOwogaWYgKG5ld19kaXN0IDwgbG9jX2Rpc3RbbG9jX3ZdKSB7CiBsb2NfZGlzdFtsb2Nfdl0gPSBuZXdfZGlzdDsKIGxvY19wcmVkW2xvY192XSA9IHU7CiB9CiB9CiB9CiBmcmVlKGtub3duKTsKfQp2b2lkIEluaXRpYWxpemVfbWF0cml4KGludCBtYXRbXSwgaW50IGxvY19kaXN0W10sIGludCBsb2NfcHJlZFtdLCBpbnQga25vd25bXSwKIGludCBsb2NfbiwgaW50IG15X3JhbmspIHsKIGZvciAoaW50IHYgPSAwOyB2IDwgbG9jX247IHYrKykgewogbG9jX2Rpc3Rbdl0gPSBtYXRbMCpsb2NfbiArIHZdOwogbG9jX3ByZWRbdl0gPSAwOwoga25vd25bdl0gPSAwOwogfQogaWYgKG15X3JhbmsgPT0gMCkgewoga25vd25bMF0gPSAxOwogfQp9CmludCBGaW5kX21pbl9kaXN0KGludCBsb2NfZGlzdFtdLCBpbnQgbG9jX2tub3duW10sIGludCBsb2NfbiwgaW50IG15X3JhbmssCiBNUElfQ29tbSBjb21tKSB7CiBpbnQgbG9jX3YsIGxvY191OwogaW50IGxvY19taW5fZGlzdCA9IElORklOSVRZOwogbG9jX3UgPSBJTkZJTklUWTsKIGZvciAobG9jX3YgPSAwOyBsb2NfdiA8IGxvY19uOyBsb2NfdisrKQogaWYgKCFsb2Nfa25vd25bbG9jX3ZdKQogaWYgKGxvY19kaXN0W2xvY192XSA8IGxvY19taW5fZGlzdCkgewogbG9jX3UgPSBsb2NfdjsKIGxvY19taW5fZGlzdCA9IGxvY19kaXN0W2xvY192XTsKIH0KIHJldHVybiBsb2NfdTsKfQppbnQgR2xvYmFsX3ZlcnRleChpbnQgbG9jX3UsIGludCBsb2NfbiwgaW50IG15X3JhbmspIHsKIGludCBnbG9iYWxfdSA9IGxvY191ICsgbXlfcmFuaypsb2NfbjsKIHJldHVybiBnbG9iYWxfdTsKfQp2b2lkIFByaW50X2Rpc3RzKGludCBsb2NfZGlzdFtdLCBpbnQgbiwgaW50IGxvY19uLCBpbnQgbXlfcmFuaywgTVBJX0NvbW0gY29tbSkgewogaW50IHY7CiBpbnQqIGRpc3QgPSBOVUxMOwogaWYgKG15X3JhbmsgPT0gMCkgewogZGlzdCA9IG1hbGxvYyhuKnNpemVvZihpbnQpKTsKIH0KIE1QSV9HYXRoZXIobG9jX2Rpc3QsIGxvY19uLCBNUElfSU5ULCBkaXN0LCBsb2NfbiwgTVBJX0lOVCwgMCwgY29tbSk7CiBpZiAobXlfcmFuayA9PSAwKSB7CiBwcmludGYoIlRoZSBkaXN0YW5jZSBmcm9tIDAgdG8gZWFjaCB2ZXJ0ZXggaXM6XG4iKTsKIHByaW50ZigiIHYgZGlzdCAwLT52XG4iKTsKIHByaW50ZigiLS0tLSAtLS0tLS0tLS1cbiIpOwogZm9yICh2ID0gMTsgdiA8IG47IHYrKykKIHByaW50ZigiJTNkICU0ZFxuIiwgdiwgZGlzdFt2XSk7CiBwcmludGYoIlxuIik7CiBmcmVlKGRpc3QpOwogfQp9CnZvaWQgUHJpbnRfcGF0aHMoaW50IGxvY19wcmVkW10sIGludCBuLCBpbnQgbG9jX24sIGludCBteV9yYW5rLCBNUElfQ29tbSBjb21tKSB7CiBpbnQgdiwgdywgKnBhdGgsIGNvdW50LCBpOwogaW50KiBwcmVkID0gTlVMTDsKIGlmIChteV9yYW5rID09IDApIHsKIHByZWQgPSBtYWxsb2MobipzaXplb2YoaW50KSk7CiB9CiBNUElfR2F0aGVyKGxvY19wcmVkLCBsb2NfbiwgTVBJX0lOVCwgcHJlZCwgbG9jX24sIE1QSV9JTlQsIDAsIGNvbW0pOwogaWYgKG15X3JhbmsgPT0gMCkgewogcGF0aCA9IG1hbGxvYyhuKnNpemVvZihpbnQpKTsKIHByaW50ZigiVGhlIHNob3J0ZXN0IHBhdGggZnJvbSAwIHRvIGVhY2ggdmVydGV4IGlzOlxuIik7CiBwcmludGYoIiB2IFBhdGggMC0+dlxuIik7CiBwcmludGYoIi0tLS0gLS0tLS0tLS0tXG4iKTsKIGZvciAodiA9IDE7IHYgPCBuOyB2KyspIHsKIHByaW50ZigiJTNkOiAiLCB2KTsKIGNvdW50ID0gMDsKIHcgPSB2Owogd2hpbGUgKHcgIT0gMCkgewogcGF0aFtjb3VudF0gPSB3OwogY291bnQrKzsKIHcgPSBwcmVkW3ddOwogfQogcHJpbnRmKCIwICIpOwogZm9yIChpID0gY291bnQtMTsgaSA+PSAwOyBpLS0pCiBwcmludGYoIiVkICIsIHBhdGhbaV0pOwogcHJpbnRmKCJcbiIpOwogfQogZnJlZShwYXRoKTsKIGZyZWUocHJlZCk7CiB9Cn0=