#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct
{
void* pElements;
size_t ElementSize;
size_t Count; // how many elements exist
size_t TotalCount; // for how many elements space allocated
} tArray;
void ArrayInit(tArray* pArray, size_t ElementSize)
{
pArray->pElements = NULL;
pArray->ElementSize = ElementSize;
pArray->TotalCount = pArray->Count = 0;
}
void ArrayDestroy(tArray* pArray)
{
ArrayInit(pArray, 0);
}
int ArrayGrowByOne(tArray* pArray)
{
if (pArray->Count == pArray->TotalCount) // used up all allocated space
{
size_t newTotalCount, newTotalSize;
void* p;
if (pArray->TotalCount == 0)
{
newTotalCount = 1;
}
else
{
newTotalCount = 2 * pArray->TotalCount; // double the allocated count
if (newTotalCount / 2 != pArray->TotalCount) // count overflow
return 0;
}
newTotalSize = newTotalCount * pArray->ElementSize;
if (newTotalSize / pArray->ElementSize != newTotalCount) // size overflow
return 0;
p
= realloc(pArray
->pElements
, newTotalSize
); if (p == NULL) // out of memory
return 0;
pArray->pElements = p;
pArray->TotalCount = newTotalCount;
}
pArray->Count++;
return 1;
}
int ArrayInsertElement(tArray* pArray, size_t pos, void* pElement)
{
if (pos > pArray->Count) // bad position
return 0;
if (!ArrayGrowByOne(pArray)) // couldn't grow
return 0;
if (pos < pArray->Count - 1)
memmove((char*)pArray
->pElements
+ (pos
+ 1) * pArray
->ElementSize
, (char*)pArray->pElements + pos * pArray->ElementSize,
(pArray->Count - 1 - pos) * pArray->ElementSize);
memcpy((char*)pArray
->pElements
+ pos
* pArray
->ElementSize
, pElement,
pArray->ElementSize);
return 1;
}
typedef struct
{
int Id;
int Data;
tArray LinksTo; // links from this node to other nodes (array of Id's)
tArray LinksFrom; // back links from other nodes to this node (array of Id's)
} tNode;
typedef struct
{
tArray Nodes;
} tGraph;
void GraphInit(tGraph* pGraph)
{
ArrayInit(&pGraph->Nodes, sizeof(tNode));
}
void GraphPrintNodes(tGraph* pGraph)
{
size_t i, j;
if (pGraph->Nodes.Count == 0)
{
}
for (i = 0; i < pGraph->Nodes.Count; i++)
{
tNode* pNode = (tNode*)pGraph->Nodes.pElements + i;
printf("Node %d:\n Data: %d\n", pNode
->Id
, pNode
->Data
);
if (pNode->LinksTo.Count)
{
for (j = 0; j < pNode->LinksTo.Count; j++)
{
int* p = (int*)pNode->LinksTo.pElements + j;
}
}
}
}
void GraphDestroy(tGraph* pGraph)
{
size_t i;
for (i = 0; i < pGraph->Nodes.Count; i++)
{
tNode* pNode = (tNode*)pGraph->Nodes.pElements + i;
ArrayDestroy(&pNode->LinksTo);
ArrayDestroy(&pNode->LinksFrom);
}
ArrayDestroy(&pGraph->Nodes);
}
int NodeIdComparator(const void* p1, const void* p2)
{
const tNode* pa = p1;
const tNode* pb = p2;
if (pa->Id < pb->Id)
return -1;
if (pa->Id > pb->Id)
return 1;
return 0;
}
int IntComparator(const void* p1, const void* p2)
{
const int* pa = p1;
const int* pb = p2;
if (*pa < *pb)
return -1;
if (*pa > *pb)
return 1;
return 0;
}
size_t GraphFindNodeIndexById(tGraph* pGraph, int Id)
{
pGraph->Nodes.pElements,
pGraph->Nodes.Count,
pGraph->Nodes.ElementSize,
&NodeIdComparator);
if (pNode == NULL)
return (size_t)-1;
return pNode - (tNode*)pGraph->Nodes.pElements;
}
int GraphInsertNode(tGraph* pGraph, int Id, int Data)
{
size_t idx = GraphFindNodeIndexById(pGraph, Id);
tNode node;
if (idx != (size_t)-1) // node with this Id already exist
return 0;
node.Id = Id;
node.Data = Data;
ArrayInit(&node.LinksTo, sizeof(int));
ArrayInit(&node.LinksFrom, sizeof(int));
if (!ArrayInsertElement(&pGraph->Nodes, pGraph->Nodes.Count, &node))
return 0;
qsort(pGraph
->Nodes.
pElements, pGraph->Nodes.Count,
pGraph->Nodes.ElementSize,
&NodeIdComparator); // maintain order for binary search
return 1;
}
int GraphLinkNodes(tGraph* pGraph, int IdFrom, int IdTo)
{
size_t idxFrom = GraphFindNodeIndexById(pGraph, IdFrom);
size_t idxTo = GraphFindNodeIndexById(pGraph, IdTo);
tNode *pFrom, *pTo;
if (idxFrom == (size_t)-1 || idxTo == (size_t)-1) // one or both nodes don't exist
return 0;
pFrom = (tNode*)pGraph->Nodes.pElements + idxFrom;
pTo = (tNode*)pGraph->Nodes.pElements + idxTo;
// link IdFrom -> IdTo
pFrom->LinksTo.pElements,
pFrom->LinksTo.Count,
pFrom->LinksTo.ElementSize,
&IntComparator) == NULL) // IdFrom doesn't link to IdTo yet
{
if (!ArrayInsertElement(&pFrom->LinksTo, pFrom->LinksTo.Count, &IdTo))
return 0;
qsort(pFrom
->LinksTo.
pElements, pFrom->LinksTo.Count,
pFrom->LinksTo.ElementSize,
&IntComparator); // maintain order for binary search
}
// back link IdFrom <- IdTo
pTo->LinksFrom.pElements,
pTo->LinksFrom.Count,
pTo->LinksFrom.ElementSize,
&IntComparator) == NULL) // IdFrom doesn't link to IdTo yet
{
if (!ArrayInsertElement(&pTo->LinksFrom, pTo->LinksFrom.Count, &IdFrom))
return 0;
qsort(pTo
->LinksFrom.
pElements, pTo->LinksFrom.Count,
pTo->LinksFrom.ElementSize,
&IntComparator); // maintain order for binary search
}
return 1;
}
int main(void)
{
tGraph g;
printf("\nCreating empty graph...\n"); GraphInit(&g);
GraphPrintNodes(&g);
printf("\nInserting nodes...\n"); GraphInsertNode(&g, 0, 0);
GraphInsertNode(&g, 1, 101);
GraphInsertNode(&g, 2, 202);
GraphPrintNodes(&g);
printf("\nLinking nodes...\n"); GraphLinkNodes(&g, 0, 1);
GraphLinkNodes(&g, 0, 2);
GraphLinkNodes(&g, 1, 2);
GraphLinkNodes(&g, 2, 1);
GraphPrintNodes(&g);
printf("\nDestroying graph...\n"); GraphDestroy(&g);
GraphPrintNodes(&g);
// repeat
printf("\nLet's repeat...\n");
printf("\nCreating empty graph...\n"); GraphInit(&g);
GraphPrintNodes(&g);
printf("\nInserting nodes...\n"); GraphInsertNode(&g, 1, 111);
GraphInsertNode(&g, 2, 222);
GraphInsertNode(&g, 3, 333);
GraphPrintNodes(&g);
printf("\nLinking nodes...\n"); GraphLinkNodes(&g, 1, 2);
GraphLinkNodes(&g, 2, 3);
GraphLinkNodes(&g, 3, 1);
GraphPrintNodes(&g);
printf("\nDestroying graph...\n"); GraphDestroy(&g);
GraphPrintNodes(&g);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgoKdHlwZWRlZiBzdHJ1Y3QKewogIHZvaWQqIHBFbGVtZW50czsKICBzaXplX3QgRWxlbWVudFNpemU7CiAgc2l6ZV90IENvdW50OyAvLyBob3cgbWFueSBlbGVtZW50cyBleGlzdAogIHNpemVfdCBUb3RhbENvdW50OyAvLyBmb3IgaG93IG1hbnkgZWxlbWVudHMgc3BhY2UgYWxsb2NhdGVkCn0gdEFycmF5OwoKdm9pZCBBcnJheUluaXQodEFycmF5KiBwQXJyYXksIHNpemVfdCBFbGVtZW50U2l6ZSkKewogIHBBcnJheS0+cEVsZW1lbnRzID0gTlVMTDsKICBwQXJyYXktPkVsZW1lbnRTaXplID0gRWxlbWVudFNpemU7CiAgcEFycmF5LT5Ub3RhbENvdW50ID0gcEFycmF5LT5Db3VudCA9IDA7Cn0KCnZvaWQgQXJyYXlEZXN0cm95KHRBcnJheSogcEFycmF5KQp7CiAgZnJlZShwQXJyYXktPnBFbGVtZW50cyk7CiAgQXJyYXlJbml0KHBBcnJheSwgMCk7Cn0KCmludCBBcnJheUdyb3dCeU9uZSh0QXJyYXkqIHBBcnJheSkKewogIGlmIChwQXJyYXktPkNvdW50ID09IHBBcnJheS0+VG90YWxDb3VudCkgLy8gdXNlZCB1cCBhbGwgYWxsb2NhdGVkIHNwYWNlCiAgewogICAgc2l6ZV90IG5ld1RvdGFsQ291bnQsIG5ld1RvdGFsU2l6ZTsKICAgIHZvaWQqIHA7CgogICAgaWYgKHBBcnJheS0+VG90YWxDb3VudCA9PSAwKQogICAgewogICAgICBuZXdUb3RhbENvdW50ID0gMTsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgbmV3VG90YWxDb3VudCA9IDIgKiBwQXJyYXktPlRvdGFsQ291bnQ7IC8vIGRvdWJsZSB0aGUgYWxsb2NhdGVkIGNvdW50CiAgICAgIGlmIChuZXdUb3RhbENvdW50IC8gMiAhPSBwQXJyYXktPlRvdGFsQ291bnQpIC8vIGNvdW50IG92ZXJmbG93CiAgICAgICAgcmV0dXJuIDA7CiAgICB9CgogICAgbmV3VG90YWxTaXplID0gbmV3VG90YWxDb3VudCAqIHBBcnJheS0+RWxlbWVudFNpemU7CiAgICBpZiAobmV3VG90YWxTaXplIC8gcEFycmF5LT5FbGVtZW50U2l6ZSAhPSBuZXdUb3RhbENvdW50KSAvLyBzaXplIG92ZXJmbG93CiAgICAgIHJldHVybiAwOwoKICAgIHAgPSByZWFsbG9jKHBBcnJheS0+cEVsZW1lbnRzLCBuZXdUb3RhbFNpemUpOwogICAgaWYgKHAgPT0gTlVMTCkgLy8gb3V0IG9mIG1lbW9yeQogICAgICByZXR1cm4gMDsKCiAgICBwQXJyYXktPnBFbGVtZW50cyA9IHA7CiAgICBwQXJyYXktPlRvdGFsQ291bnQgPSBuZXdUb3RhbENvdW50OwogIH0KCiAgcEFycmF5LT5Db3VudCsrOwogIHJldHVybiAxOwp9CgppbnQgQXJyYXlJbnNlcnRFbGVtZW50KHRBcnJheSogcEFycmF5LCBzaXplX3QgcG9zLCB2b2lkKiBwRWxlbWVudCkKewogIGlmIChwb3MgPiBwQXJyYXktPkNvdW50KSAvLyBiYWQgcG9zaXRpb24KICAgIHJldHVybiAwOwoKICBpZiAoIUFycmF5R3Jvd0J5T25lKHBBcnJheSkpIC8vIGNvdWxkbid0IGdyb3cKICAgIHJldHVybiAwOwoKICBpZiAocG9zIDwgcEFycmF5LT5Db3VudCAtIDEpCiAgICBtZW1tb3ZlKChjaGFyKilwQXJyYXktPnBFbGVtZW50cyArIChwb3MgKyAxKSAqIHBBcnJheS0+RWxlbWVudFNpemUsCiAgICAgICAgICAgKGNoYXIqKXBBcnJheS0+cEVsZW1lbnRzICsgcG9zICogcEFycmF5LT5FbGVtZW50U2l6ZSwKICAgICAgICAgICAocEFycmF5LT5Db3VudCAtIDEgLSBwb3MpICogcEFycmF5LT5FbGVtZW50U2l6ZSk7CgogIG1lbWNweSgoY2hhciopcEFycmF5LT5wRWxlbWVudHMgKyBwb3MgKiBwQXJyYXktPkVsZW1lbnRTaXplLAogICAgICAgICBwRWxlbWVudCwKICAgICAgICAgcEFycmF5LT5FbGVtZW50U2l6ZSk7CgogIHJldHVybiAxOwp9Cgp0eXBlZGVmIHN0cnVjdAp7CiAgaW50IElkOwoKICBpbnQgRGF0YTsKCiAgdEFycmF5IExpbmtzVG87IC8vIGxpbmtzIGZyb20gdGhpcyBub2RlIHRvIG90aGVyIG5vZGVzIChhcnJheSBvZiBJZCdzKQogIHRBcnJheSBMaW5rc0Zyb207IC8vIGJhY2sgbGlua3MgZnJvbSBvdGhlciBub2RlcyB0byB0aGlzIG5vZGUgKGFycmF5IG9mIElkJ3MpCn0gdE5vZGU7Cgp0eXBlZGVmIHN0cnVjdAp7CiAgdEFycmF5IE5vZGVzOwp9IHRHcmFwaDsKCnZvaWQgR3JhcGhJbml0KHRHcmFwaCogcEdyYXBoKQp7CiAgQXJyYXlJbml0KCZwR3JhcGgtPk5vZGVzLCBzaXplb2YodE5vZGUpKTsKfQoKdm9pZCBHcmFwaFByaW50Tm9kZXModEdyYXBoKiBwR3JhcGgpCnsKICBzaXplX3QgaSwgajsKCiAgaWYgKHBHcmFwaC0+Tm9kZXMuQ291bnQgPT0gMCkKICB7CiAgICBwcmludGYoIkVtcHR5IGdyYXBoLlxuIik7CiAgfQoKICBmb3IgKGkgPSAwOyBpIDwgcEdyYXBoLT5Ob2Rlcy5Db3VudDsgaSsrKQogIHsKICAgIHROb2RlKiBwTm9kZSA9ICh0Tm9kZSopcEdyYXBoLT5Ob2Rlcy5wRWxlbWVudHMgKyBpOwoKICAgIHByaW50ZigiTm9kZSAlZDpcbiAgRGF0YTogJWRcbiIsIHBOb2RlLT5JZCwgcE5vZGUtPkRhdGEpOwoKICAgIGlmIChwTm9kZS0+TGlua3NUby5Db3VudCkKICAgIHsKICAgICAgcHJpbnRmKCIgIExpbmtzIHRvOlxuIik7CgogICAgICBmb3IgKGogPSAwOyBqIDwgcE5vZGUtPkxpbmtzVG8uQ291bnQ7IGorKykKICAgICAgewogICAgICAgIGludCogcCA9IChpbnQqKXBOb2RlLT5MaW5rc1RvLnBFbGVtZW50cyArIGo7CiAgICAgICAgcHJpbnRmKCIgICAgTm9kZSAlZFxuIiwgKnApOwogICAgICB9CiAgICB9CiAgfQp9Cgp2b2lkIEdyYXBoRGVzdHJveSh0R3JhcGgqIHBHcmFwaCkKewogIHNpemVfdCBpOwoKICBmb3IgKGkgPSAwOyBpIDwgcEdyYXBoLT5Ob2Rlcy5Db3VudDsgaSsrKQogIHsKICAgIHROb2RlKiBwTm9kZSA9ICh0Tm9kZSopcEdyYXBoLT5Ob2Rlcy5wRWxlbWVudHMgKyBpOwogICAgQXJyYXlEZXN0cm95KCZwTm9kZS0+TGlua3NUbyk7CiAgICBBcnJheURlc3Ryb3koJnBOb2RlLT5MaW5rc0Zyb20pOwogIH0KCiAgQXJyYXlEZXN0cm95KCZwR3JhcGgtPk5vZGVzKTsKfQoKaW50IE5vZGVJZENvbXBhcmF0b3IoY29uc3Qgdm9pZCogcDEsIGNvbnN0IHZvaWQqIHAyKQp7CiAgY29uc3QgdE5vZGUqIHBhID0gcDE7CiAgY29uc3QgdE5vZGUqIHBiID0gcDI7CgogIGlmIChwYS0+SWQgPCBwYi0+SWQpCiAgICByZXR1cm4gLTE7CiAgaWYgKHBhLT5JZCA+IHBiLT5JZCkKICAgIHJldHVybiAxOwogIHJldHVybiAwOwp9CgppbnQgSW50Q29tcGFyYXRvcihjb25zdCB2b2lkKiBwMSwgY29uc3Qgdm9pZCogcDIpCnsKICBjb25zdCBpbnQqIHBhID0gcDE7CiAgY29uc3QgaW50KiBwYiA9IHAyOwoKICBpZiAoKnBhIDwgKnBiKQogICAgcmV0dXJuIC0xOwogIGlmICgqcGEgPiAqcGIpCiAgICByZXR1cm4gMTsKICByZXR1cm4gMDsKfQoKc2l6ZV90IEdyYXBoRmluZE5vZGVJbmRleEJ5SWQodEdyYXBoKiBwR3JhcGgsIGludCBJZCkKewogIHROb2RlKiBwTm9kZSA9IGJzZWFyY2goJklkLAogICAgICAgICAgICAgICAgICAgICAgICAgcEdyYXBoLT5Ob2Rlcy5wRWxlbWVudHMsCiAgICAgICAgICAgICAgICAgICAgICAgICBwR3JhcGgtPk5vZGVzLkNvdW50LAogICAgICAgICAgICAgICAgICAgICAgICAgcEdyYXBoLT5Ob2Rlcy5FbGVtZW50U2l6ZSwKICAgICAgICAgICAgICAgICAgICAgICAgICZOb2RlSWRDb21wYXJhdG9yKTsKCiAgaWYgKHBOb2RlID09IE5VTEwpCiAgICByZXR1cm4gKHNpemVfdCktMTsKCiAgcmV0dXJuIHBOb2RlIC0gKHROb2RlKilwR3JhcGgtPk5vZGVzLnBFbGVtZW50czsKfQoKaW50IEdyYXBoSW5zZXJ0Tm9kZSh0R3JhcGgqIHBHcmFwaCwgaW50IElkLCBpbnQgRGF0YSkKewogIHNpemVfdCBpZHggPSBHcmFwaEZpbmROb2RlSW5kZXhCeUlkKHBHcmFwaCwgSWQpOwogIHROb2RlIG5vZGU7CgogIGlmIChpZHggIT0gKHNpemVfdCktMSkgLy8gbm9kZSB3aXRoIHRoaXMgSWQgYWxyZWFkeSBleGlzdAogICAgcmV0dXJuIDA7CgogIG5vZGUuSWQgPSBJZDsKICBub2RlLkRhdGEgPSBEYXRhOwogIEFycmF5SW5pdCgmbm9kZS5MaW5rc1RvLCBzaXplb2YoaW50KSk7CiAgQXJyYXlJbml0KCZub2RlLkxpbmtzRnJvbSwgc2l6ZW9mKGludCkpOwoKICBpZiAoIUFycmF5SW5zZXJ0RWxlbWVudCgmcEdyYXBoLT5Ob2RlcywgcEdyYXBoLT5Ob2Rlcy5Db3VudCwgJm5vZGUpKQogICAgcmV0dXJuIDA7CgogIHFzb3J0KHBHcmFwaC0+Tm9kZXMucEVsZW1lbnRzLAogICAgICAgIHBHcmFwaC0+Tm9kZXMuQ291bnQsCiAgICAgICAgcEdyYXBoLT5Ob2Rlcy5FbGVtZW50U2l6ZSwKICAgICAgICAmTm9kZUlkQ29tcGFyYXRvcik7IC8vIG1haW50YWluIG9yZGVyIGZvciBiaW5hcnkgc2VhcmNoCgogIHJldHVybiAxOwp9CgppbnQgR3JhcGhMaW5rTm9kZXModEdyYXBoKiBwR3JhcGgsIGludCBJZEZyb20sIGludCBJZFRvKQp7CiAgc2l6ZV90IGlkeEZyb20gPSBHcmFwaEZpbmROb2RlSW5kZXhCeUlkKHBHcmFwaCwgSWRGcm9tKTsKICBzaXplX3QgaWR4VG8gPSBHcmFwaEZpbmROb2RlSW5kZXhCeUlkKHBHcmFwaCwgSWRUbyk7CiAgdE5vZGUgKnBGcm9tLCAqcFRvOwoKICBpZiAoaWR4RnJvbSA9PSAoc2l6ZV90KS0xIHx8IGlkeFRvID09IChzaXplX3QpLTEpIC8vIG9uZSBvciBib3RoIG5vZGVzIGRvbid0IGV4aXN0CiAgICByZXR1cm4gMDsKCiAgcEZyb20gPSAodE5vZGUqKXBHcmFwaC0+Tm9kZXMucEVsZW1lbnRzICsgaWR4RnJvbTsKICBwVG8gPSAodE5vZGUqKXBHcmFwaC0+Tm9kZXMucEVsZW1lbnRzICsgaWR4VG87CgogIC8vIGxpbmsgSWRGcm9tIC0+IElkVG8KICBpZiAoYnNlYXJjaCgmSWRUbywKICAgICAgICAgICAgICBwRnJvbS0+TGlua3NUby5wRWxlbWVudHMsCiAgICAgICAgICAgICAgcEZyb20tPkxpbmtzVG8uQ291bnQsCiAgICAgICAgICAgICAgcEZyb20tPkxpbmtzVG8uRWxlbWVudFNpemUsCiAgICAgICAgICAgICAgJkludENvbXBhcmF0b3IpID09IE5VTEwpIC8vIElkRnJvbSBkb2Vzbid0IGxpbmsgdG8gSWRUbyB5ZXQKICB7CiAgICBpZiAoIUFycmF5SW5zZXJ0RWxlbWVudCgmcEZyb20tPkxpbmtzVG8sIHBGcm9tLT5MaW5rc1RvLkNvdW50LCAmSWRUbykpCiAgICAgIHJldHVybiAwOwoKICAgIHFzb3J0KHBGcm9tLT5MaW5rc1RvLnBFbGVtZW50cywKICAgICAgICAgIHBGcm9tLT5MaW5rc1RvLkNvdW50LAogICAgICAgICAgcEZyb20tPkxpbmtzVG8uRWxlbWVudFNpemUsCiAgICAgICAgICAmSW50Q29tcGFyYXRvcik7IC8vIG1haW50YWluIG9yZGVyIGZvciBiaW5hcnkgc2VhcmNoCiAgfQoKICAvLyBiYWNrIGxpbmsgSWRGcm9tIDwtIElkVG8KICBpZiAoYnNlYXJjaCgmSWRGcm9tLAogICAgICAgICAgICAgIHBUby0+TGlua3NGcm9tLnBFbGVtZW50cywKICAgICAgICAgICAgICBwVG8tPkxpbmtzRnJvbS5Db3VudCwKICAgICAgICAgICAgICBwVG8tPkxpbmtzRnJvbS5FbGVtZW50U2l6ZSwKICAgICAgICAgICAgICAmSW50Q29tcGFyYXRvcikgPT0gTlVMTCkgLy8gSWRGcm9tIGRvZXNuJ3QgbGluayB0byBJZFRvIHlldAogIHsKICAgIGlmICghQXJyYXlJbnNlcnRFbGVtZW50KCZwVG8tPkxpbmtzRnJvbSwgcFRvLT5MaW5rc0Zyb20uQ291bnQsICZJZEZyb20pKQogICAgICByZXR1cm4gMDsKCiAgICBxc29ydChwVG8tPkxpbmtzRnJvbS5wRWxlbWVudHMsCiAgICAgICAgICBwVG8tPkxpbmtzRnJvbS5Db3VudCwKICAgICAgICAgIHBUby0+TGlua3NGcm9tLkVsZW1lbnRTaXplLAogICAgICAgICAgJkludENvbXBhcmF0b3IpOyAvLyBtYWludGFpbiBvcmRlciBmb3IgYmluYXJ5IHNlYXJjaAogIH0KCiAgcmV0dXJuIDE7Cn0KCmludCBtYWluKHZvaWQpCnsKICB0R3JhcGggZzsKCiAgcHJpbnRmKCJcbkNyZWF0aW5nIGVtcHR5IGdyYXBoLi4uXG4iKTsKICBHcmFwaEluaXQoJmcpOwogIEdyYXBoUHJpbnROb2RlcygmZyk7CgogIHByaW50ZigiXG5JbnNlcnRpbmcgbm9kZXMuLi5cbiIpOwogIEdyYXBoSW5zZXJ0Tm9kZSgmZywgMCwgMCk7CiAgR3JhcGhJbnNlcnROb2RlKCZnLCAxLCAxMDEpOwogIEdyYXBoSW5zZXJ0Tm9kZSgmZywgMiwgMjAyKTsKICBHcmFwaFByaW50Tm9kZXMoJmcpOwoKICBwcmludGYoIlxuTGlua2luZyBub2Rlcy4uLlxuIik7CiAgR3JhcGhMaW5rTm9kZXMoJmcsIDAsIDEpOwogIEdyYXBoTGlua05vZGVzKCZnLCAwLCAyKTsKICBHcmFwaExpbmtOb2RlcygmZywgMSwgMik7CiAgR3JhcGhMaW5rTm9kZXMoJmcsIDIsIDEpOwogIEdyYXBoUHJpbnROb2RlcygmZyk7CgogIHByaW50ZigiXG5EZXN0cm95aW5nIGdyYXBoLi4uXG4iKTsKICBHcmFwaERlc3Ryb3koJmcpOwogIEdyYXBoUHJpbnROb2RlcygmZyk7CgogIC8vIHJlcGVhdAogIHByaW50ZigiXG5MZXQncyByZXBlYXQuLi5cbiIpOwoKICBwcmludGYoIlxuQ3JlYXRpbmcgZW1wdHkgZ3JhcGguLi5cbiIpOwogIEdyYXBoSW5pdCgmZyk7CiAgR3JhcGhQcmludE5vZGVzKCZnKTsKCiAgcHJpbnRmKCJcbkluc2VydGluZyBub2Rlcy4uLlxuIik7CiAgR3JhcGhJbnNlcnROb2RlKCZnLCAxLCAxMTEpOwogIEdyYXBoSW5zZXJ0Tm9kZSgmZywgMiwgMjIyKTsKICBHcmFwaEluc2VydE5vZGUoJmcsIDMsIDMzMyk7CiAgR3JhcGhQcmludE5vZGVzKCZnKTsKCiAgcHJpbnRmKCJcbkxpbmtpbmcgbm9kZXMuLi5cbiIpOwogIEdyYXBoTGlua05vZGVzKCZnLCAxLCAyKTsKICBHcmFwaExpbmtOb2RlcygmZywgMiwgMyk7CiAgR3JhcGhMaW5rTm9kZXMoJmcsIDMsIDEpOwogIEdyYXBoUHJpbnROb2RlcygmZyk7CgogIHByaW50ZigiXG5EZXN0cm95aW5nIGdyYXBoLi4uXG4iKTsKICBHcmFwaERlc3Ryb3koJmcpOwogIEdyYXBoUHJpbnROb2RlcygmZyk7CgogIHJldHVybiAwOwp9Cg==