/* Author: Prakhar Jain */
#include <stdio.h>
#include <stdlib.h>
#define RED 1
#define BLACK 2
struct node {
int key;
struct node *left, *right, *p;
int color;
};
typedef struct node *NODEPTR;
struct node NIL;
NODEPTR NILPTR = &NIL;
void inorder(NODEPTR x) {
if (x != NILPTR) {
inorder(x->left);
inorder(x->right);
}
}
NODEPTR search(NODEPTR root, int k) {
if (root == NILPTR || root->key == k)
return root;
if (k < root->key)
return search(root->left, k);
else
return search(root->right, k);
}
NODEPTR minimum(NODEPTR root) {
while (root->left != NILPTR)
root = root->left;
return root;
}
NODEPTR maximum(NODEPTR root) {
while (root->right != NILPTR)
root = root->right;
return root;
}
NODEPTR successor(NODEPTR root, int x) {
NODEPTR temp = search(root, x);
if (temp == NILPTR) {
printf("%d not in tree\n", x
); return temp;
}
if (temp->right != NILPTR)
return minimum(temp->right);
NODEPTR y = temp->p;
while (y != NILPTR && temp == y->right) {
temp = y;
y = y->p;
}
return y;
}
NODEPTR predecessor(NODEPTR root, int x) {
NODEPTR temp = search(root, x);
if (temp == NILPTR) {
printf("%d not in tree\n", x
); return temp;
}
if (temp->left != NILPTR)
return maximum(temp->left);
NODEPTR y = temp->p;
while (y != NILPTR && temp == y->left) {
temp = y;
y = y->p;
}
return y;
}
void leftrotate(NODEPTR *treeroot, NODEPTR x) {
NODEPTR y = x->right;
x->right = y->left;
if (y->left != NILPTR)
y->left->p = x;
y->p = x->p;
if (x->p == NILPTR)
*treeroot = y;
else if (x->p->left == x)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p = y;
}
void rightrotate(NODEPTR *treeroot, NODEPTR y) {
NODEPTR x = y->left;
y->left = x->right;
if (x->right != NILPTR)
x->right->p = y;
x->p = y->p;
if (y->p == NILPTR)
*treeroot = x;
else if (y->p->left == y)
y->p->left = x;
else
y->p->right = x;
x->right = y;
y->p = x;
}
void rbinsertfixup(NODEPTR *treeroot, NODEPTR z) {
while (z->p->color == RED) {
if (z->p == z->p->p->left) {
NODEPTR y = z->p->p->right;
if (y->color == RED) {
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else {
if (z == z->p->right) {
z = z->p;
leftrotate(treeroot,z);
}
z->p->color = BLACK;
z->p->p->color = RED;
rightrotate(treeroot,z->p->p);
}
}
else {
NODEPTR y = z->p->p->left;
if (y->color == RED) {
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else {
if (z == z->p->left) {
z = z->p;
rightrotate(treeroot,z);
}
z->p->color = BLACK;
z->p->p->color = RED;
leftrotate(treeroot,z->p->p);
}
}
}
(*treeroot)->color = BLACK;
}
void rbinsert(NODEPTR *treeroot, int z) {
NODEPTR Z
= (NODEPTR
) malloc(sizeof(struct node
)); Z->key = z;
NODEPTR y = NILPTR;
NODEPTR x = *treeroot;
while (x != NILPTR) {
y = x;
if (Z->key < x->key)
x = x->left;
else
x = x->right;
}
Z->p = y;
if (y == NILPTR)
*treeroot = Z;
else if (Z->key < y->key)
y->left = Z;
else
y->right = Z;
Z->left = NILPTR;
Z->right = NILPTR;
Z->color = RED;
rbinsertfixup(treeroot,Z);
}
void rbtransplant(NODEPTR *treeroot, NODEPTR u, NODEPTR v) {
if (u->p == NILPTR)
*treeroot = v;
else if (u == u->p->left)
u->p->left = v;
else
u->p->right = v;
v->p = u->p;
}
void rbdeletefixup(NODEPTR *treeroot, NODEPTR x) {
while (x != *treeroot && x->color == BLACK) {
if (x == x->p->left) {
NODEPTR w = x->p->right;
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
leftrotate(treeroot,x->p);
w = x->p->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->p;
}
else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rightrotate(treeroot,w);
w = x->p->right;
}
w->color = x->p->color;
x->p->color = BLACK;
w->right->color = BLACK;
leftrotate(treeroot,x->p);
x = *treeroot;
}
}
else {
NODEPTR w = x->p->left;
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
rightrotate(treeroot,x->p);
w = x->p->left;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->p;
}
else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
leftrotate(treeroot,w);
w = x->p->left;
}
w->color = x->p->color;
x->p->color = BLACK;
w->left->color = BLACK;
rightrotate(treeroot,x->p);
x = *treeroot;
}
}
}
x->color = BLACK;
}
void rbdelete(NODEPTR *treeroot, int z) {
NODEPTR Z = search(*treeroot, z);
if (Z == NILPTR) {
printf("Node to be deleted not found\n"); return;
}
NODEPTR y = Z;
int yoc = y->color;
NODEPTR x;
if (Z->left == NILPTR) {
x = Z->right;
rbtransplant(treeroot,Z,Z->right);
}
else if (Z->right == NILPTR) {
x = Z->left;
rbtransplant(treeroot,Z,Z->left);
}
else {
y = minimum(Z->right);
yoc = y->color;
x = y->right;
if (y->p == Z)
x->p = y;
else {
rbtransplant(treeroot,y,y->right);
y->right = Z->right;
y->right->p = y;
}
rbtransplant(treeroot,Z,y);
y->left = Z->left;
y->left->p = y;
y->color = Z->color;
}
if (yoc == BLACK)
rbdeletefixup(treeroot,x);
}
main()
{
NIL.left = NIL.right = NIL.p = NILPTR;
NIL.color = BLACK;
NODEPTR tree = NILPTR;
int n;
while (1) {
printf("1.Insert\n2.Search\n3.Inorder Walk\n4.Minimum\n5.Maximum\n6.Successor\n7.Predecessor\n8.Delete\n9.Exit\n"); if (n == 1) {
printf("Enter any number:\n"); int num;
rbinsert(&tree, num);
}
else if (n == 2) {
printf("Enter the number to be search\n"); int num;
if (search(tree, num) == NILPTR)
printf("%d not found\n", num
); else
}
else if (n == 3) {
inorder(tree);
}
else if (n == 4)
printf("%d\n", minimum
(tree
)->key
); else if (n == 5)
printf("%d\n", maximum
(tree
)->key
); else if (n == 6) {
printf("Enter the number whose successor needs to be found\n"); int num;
NODEPTR t = successor(tree, num);
if (t != NULL)
}
else if (n == 7) {
printf("Enter the number whose predecessor needs to be found\n"); int num;
NODEPTR t = predecessor(tree, num);
if (t != NULL)
}
else if (n == 8) {
printf("Enter the number to be deleted\n"); int num;
rbdelete(&tree, num);
}
else
break;
}
return 0;
}
LyogQXV0aG9yOiBQcmFraGFyIEphaW4gKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCiNkZWZpbmUgUkVECQkxCiNkZWZpbmUgQkxBQ0sJMgoKc3RydWN0IG5vZGUgewoJaW50IGtleTsKCXN0cnVjdCBub2RlICpsZWZ0LCAqcmlnaHQsICpwOwoJaW50IGNvbG9yOwp9OwoKdHlwZWRlZiBzdHJ1Y3Qgbm9kZSAqTk9ERVBUUjsKc3RydWN0IG5vZGUgTklMOwpOT0RFUFRSIE5JTFBUUiA9ICZOSUw7Cgp2b2lkIGlub3JkZXIoTk9ERVBUUiB4KSB7CglpZiAoeCAhPSBOSUxQVFIpIHsKCQlpbm9yZGVyKHgtPmxlZnQpOwoJCXByaW50ZigiJWQgIiwgeC0+a2V5KTsKCQlpbm9yZGVyKHgtPnJpZ2h0KTsKCX0KfQoKTk9ERVBUUiBzZWFyY2goTk9ERVBUUiByb290LCBpbnQgaykgewoJaWYgKHJvb3QgPT0gTklMUFRSIHx8IHJvb3QtPmtleSA9PSBrKQoJCXJldHVybiByb290OwoJaWYgKGsgPCByb290LT5rZXkpCgkJcmV0dXJuIHNlYXJjaChyb290LT5sZWZ0LCBrKTsKCWVsc2UKCQlyZXR1cm4gc2VhcmNoKHJvb3QtPnJpZ2h0LCBrKTsKfQoKTk9ERVBUUiBtaW5pbXVtKE5PREVQVFIgcm9vdCkgewoJd2hpbGUgKHJvb3QtPmxlZnQgIT0gTklMUFRSKQoJCXJvb3QgPSByb290LT5sZWZ0OwoJcmV0dXJuIHJvb3Q7Cn0KCk5PREVQVFIgbWF4aW11bShOT0RFUFRSIHJvb3QpIHsKCXdoaWxlIChyb290LT5yaWdodCAhPSBOSUxQVFIpCgkJcm9vdCA9IHJvb3QtPnJpZ2h0OwoJcmV0dXJuIHJvb3Q7Cn0KCk5PREVQVFIgc3VjY2Vzc29yKE5PREVQVFIgcm9vdCwgaW50IHgpIHsKCU5PREVQVFIgdGVtcCA9IHNlYXJjaChyb290LCB4KTsKCWlmICh0ZW1wID09IE5JTFBUUikgewoJCXByaW50ZigiJWQgbm90IGluIHRyZWVcbiIsIHgpOwoJCXJldHVybiB0ZW1wOwoJfQoJaWYgKHRlbXAtPnJpZ2h0ICE9IE5JTFBUUikKCQlyZXR1cm4gbWluaW11bSh0ZW1wLT5yaWdodCk7CglOT0RFUFRSIHkgPSB0ZW1wLT5wOwoJd2hpbGUgKHkgIT0gTklMUFRSICYmIHRlbXAgPT0geS0+cmlnaHQpIHsKCQl0ZW1wID0geTsKCQl5ID0geS0+cDsKCX0KCXJldHVybiB5Owp9CgpOT0RFUFRSIHByZWRlY2Vzc29yKE5PREVQVFIgcm9vdCwgaW50IHgpIHsKCU5PREVQVFIgdGVtcCA9IHNlYXJjaChyb290LCB4KTsKCWlmICh0ZW1wID09IE5JTFBUUikgewoJCXByaW50ZigiJWQgbm90IGluIHRyZWVcbiIsIHgpOwoJCXJldHVybiB0ZW1wOwoJfQoJaWYgKHRlbXAtPmxlZnQgIT0gTklMUFRSKQoJCXJldHVybiBtYXhpbXVtKHRlbXAtPmxlZnQpOwoJTk9ERVBUUiB5ID0gdGVtcC0+cDsKCXdoaWxlICh5ICE9IE5JTFBUUiAmJiB0ZW1wID09IHktPmxlZnQpIHsKCQl0ZW1wID0geTsKCQl5ID0geS0+cDsKCX0KCXJldHVybiB5Owp9CnZvaWQgbGVmdHJvdGF0ZShOT0RFUFRSICp0cmVlcm9vdCwgTk9ERVBUUiB4KSB7CglOT0RFUFRSIHkgPSB4LT5yaWdodDsKCXgtPnJpZ2h0ID0geS0+bGVmdDsKCWlmICh5LT5sZWZ0ICE9IE5JTFBUUikKCQl5LT5sZWZ0LT5wID0geDsKCXktPnAgPSB4LT5wOwoJaWYgKHgtPnAgPT0gTklMUFRSKQoJCSp0cmVlcm9vdCA9IHk7CgllbHNlIGlmICh4LT5wLT5sZWZ0ID09IHgpCgkJeC0+cC0+bGVmdCA9IHk7CgllbHNlCgkJeC0+cC0+cmlnaHQgPSB5OwoJeS0+bGVmdCA9IHg7Cgl4LT5wID0geTsKfQoKdm9pZCByaWdodHJvdGF0ZShOT0RFUFRSICp0cmVlcm9vdCwgTk9ERVBUUiB5KSB7CglOT0RFUFRSIHggPSB5LT5sZWZ0OwoJeS0+bGVmdCA9IHgtPnJpZ2h0OwoJaWYgKHgtPnJpZ2h0ICE9IE5JTFBUUikKCQl4LT5yaWdodC0+cCA9IHk7Cgl4LT5wID0geS0+cDsKCWlmICh5LT5wID09IE5JTFBUUikKCQkqdHJlZXJvb3QgPSB4OwoJZWxzZSBpZiAoeS0+cC0+bGVmdCA9PSB5KQoJCXktPnAtPmxlZnQgPSB4OwoJZWxzZQoJCXktPnAtPnJpZ2h0ID0geDsKCXgtPnJpZ2h0ID0geTsKCXktPnAgPSB4Owp9Cgp2b2lkIHJiaW5zZXJ0Zml4dXAoTk9ERVBUUiAqdHJlZXJvb3QsIE5PREVQVFIgeikgewoJd2hpbGUgKHotPnAtPmNvbG9yID09IFJFRCkgewoJCWlmICh6LT5wID09IHotPnAtPnAtPmxlZnQpIHsKCQkJTk9ERVBUUiB5ID0gei0+cC0+cC0+cmlnaHQ7CgkJCWlmICh5LT5jb2xvciA9PSBSRUQpIHsKCQkJCXotPnAtPmNvbG9yID0gQkxBQ0s7CgkJCQl5LT5jb2xvciA9IEJMQUNLOwoJCQkJei0+cC0+cC0+Y29sb3IgPSBSRUQ7CgkJCQl6ID0gei0+cC0+cDsKCQkJfQoJCQllbHNlIHsKCQkJCWlmICh6ID09IHotPnAtPnJpZ2h0KSB7CgkJCQkJeiA9IHotPnA7CgkJCQkJbGVmdHJvdGF0ZSh0cmVlcm9vdCx6KTsKCQkJCX0KCQkJCXotPnAtPmNvbG9yID0gQkxBQ0s7CgkJCQl6LT5wLT5wLT5jb2xvciA9IFJFRDsKCQkJCXJpZ2h0cm90YXRlKHRyZWVyb290LHotPnAtPnApOwoJCQl9CgkJfQoJCWVsc2UgewoJCQlOT0RFUFRSIHkgPSB6LT5wLT5wLT5sZWZ0OwoJCQlpZiAoeS0+Y29sb3IgPT0gUkVEKSB7CgkJCQl6LT5wLT5jb2xvciA9IEJMQUNLOwoJCQkJeS0+Y29sb3IgPSBCTEFDSzsKCQkJCXotPnAtPnAtPmNvbG9yID0gUkVEOwoJCQkJeiA9IHotPnAtPnA7CgkJCX0KCQkJZWxzZSB7CgkJCQlpZiAoeiA9PSB6LT5wLT5sZWZ0KSB7CgkJCQkJeiA9IHotPnA7CgkJCQkJcmlnaHRyb3RhdGUodHJlZXJvb3Qseik7CgkJCQl9CgkJCQl6LT5wLT5jb2xvciA9IEJMQUNLOwoJCQkJei0+cC0+cC0+Y29sb3IgPSBSRUQ7CgkJCQlsZWZ0cm90YXRlKHRyZWVyb290LHotPnAtPnApOwoJCQl9CgkJfQoJfQoJKCp0cmVlcm9vdCktPmNvbG9yID0gQkxBQ0s7Cn0KCnZvaWQgcmJpbnNlcnQoTk9ERVBUUiAqdHJlZXJvb3QsIGludCB6KSB7CglOT0RFUFRSIFogPSAoTk9ERVBUUikgbWFsbG9jKHNpemVvZihzdHJ1Y3Qgbm9kZSkpOwoJWi0+a2V5ID0gejsKCU5PREVQVFIgeSA9IE5JTFBUUjsKCU5PREVQVFIgeCA9ICp0cmVlcm9vdDsKCXdoaWxlICh4ICE9IE5JTFBUUikgewoJCXkgPSB4OwoJCWlmIChaLT5rZXkgPCB4LT5rZXkpCgkJCXggPSB4LT5sZWZ0OwoJCWVsc2UKCQkJeCA9IHgtPnJpZ2h0OwoJfQoJWi0+cCA9IHk7CglpZiAoeSA9PSBOSUxQVFIpCgkJKnRyZWVyb290ID0gWjsKCWVsc2UgaWYgKFotPmtleSA8IHktPmtleSkKCQl5LT5sZWZ0ID0gWjsKCWVsc2UKCQl5LT5yaWdodCA9IFo7CglaLT5sZWZ0ID0gTklMUFRSOwoJWi0+cmlnaHQgPSBOSUxQVFI7CglaLT5jb2xvciA9IFJFRDsKCXJiaW5zZXJ0Zml4dXAodHJlZXJvb3QsWik7Cn0KCnZvaWQgcmJ0cmFuc3BsYW50KE5PREVQVFIgKnRyZWVyb290LCBOT0RFUFRSIHUsIE5PREVQVFIgdikgewoJaWYgKHUtPnAgPT0gTklMUFRSKQoJCSp0cmVlcm9vdCA9IHY7CgllbHNlIGlmICh1ID09IHUtPnAtPmxlZnQpCgkJdS0+cC0+bGVmdCA9IHY7CgllbHNlCgkJdS0+cC0+cmlnaHQgPSB2OwoJdi0+cCA9IHUtPnA7Cn0KCnZvaWQgcmJkZWxldGVmaXh1cChOT0RFUFRSICp0cmVlcm9vdCwgTk9ERVBUUiB4KSB7Cgl3aGlsZSAoeCAhPSAqdHJlZXJvb3QgJiYgeC0+Y29sb3IgPT0gQkxBQ0spIHsKCQlpZiAoeCA9PSB4LT5wLT5sZWZ0KSB7CgkJCU5PREVQVFIgdyA9IHgtPnAtPnJpZ2h0OwoJCQlpZiAody0+Y29sb3IgPT0gUkVEKSB7CgkJCQl3LT5jb2xvciA9IEJMQUNLOwoJCQkJeC0+cC0+Y29sb3IgPSBSRUQ7CgkJCQlsZWZ0cm90YXRlKHRyZWVyb290LHgtPnApOwoJCQkJdyA9IHgtPnAtPnJpZ2h0OwoJCQl9CgkJCWlmICh3LT5sZWZ0LT5jb2xvciA9PSBCTEFDSyAmJiB3LT5yaWdodC0+Y29sb3IgPT0gQkxBQ0spIHsKCQkJCXctPmNvbG9yID0gUkVEOwoJCQkJeCA9IHgtPnA7CgkJCX0KCQkJZWxzZSB7CgkJCSAJaWYgKHctPnJpZ2h0LT5jb2xvciA9PSBCTEFDSykgewoJCQkJCXctPmxlZnQtPmNvbG9yID0gQkxBQ0s7CgkJCQkJdy0+Y29sb3IgPSBSRUQ7CgkJCQkJcmlnaHRyb3RhdGUodHJlZXJvb3Qsdyk7CgkJCQkJdyA9IHgtPnAtPnJpZ2h0OwoJCQkJfQoJCQkJdy0+Y29sb3IgPSB4LT5wLT5jb2xvcjsKCQkJCXgtPnAtPmNvbG9yID0gQkxBQ0s7CgkJCQl3LT5yaWdodC0+Y29sb3IgPSBCTEFDSzsKCQkJCWxlZnRyb3RhdGUodHJlZXJvb3QseC0+cCk7CgkJCQl4ID0gKnRyZWVyb290OwoJCQl9CgkJfQoJCWVsc2UgewoJCQlOT0RFUFRSIHcgPSB4LT5wLT5sZWZ0OwoJCQlpZiAody0+Y29sb3IgPT0gUkVEKSB7CgkJCQl3LT5jb2xvciA9IEJMQUNLOwoJCQkJeC0+cC0+Y29sb3IgPSBSRUQ7CgkJCQlyaWdodHJvdGF0ZSh0cmVlcm9vdCx4LT5wKTsKCQkJCXcgPSB4LT5wLT5sZWZ0OwoJCQl9CgkJCWlmICh3LT5sZWZ0LT5jb2xvciA9PSBCTEFDSyAmJiB3LT5yaWdodC0+Y29sb3IgPT0gQkxBQ0spIHsKCQkJCXctPmNvbG9yID0gUkVEOwoJCQkJeCA9IHgtPnA7CgkJCX0KCQkJZWxzZSB7CgkJCQlpZiAody0+bGVmdC0+Y29sb3IgPT0gQkxBQ0spIHsKCQkJCQl3LT5yaWdodC0+Y29sb3IgPSBCTEFDSzsKCQkJCQl3LT5jb2xvciA9IFJFRDsKCQkJCQlsZWZ0cm90YXRlKHRyZWVyb290LHcpOwoJCQkJCXcgPSB4LT5wLT5sZWZ0OwoJCQkJfQoJCQkJdy0+Y29sb3IgPSB4LT5wLT5jb2xvcjsKCQkJCXgtPnAtPmNvbG9yID0gQkxBQ0s7CgkJCQl3LT5sZWZ0LT5jb2xvciA9IEJMQUNLOwoJCQkJcmlnaHRyb3RhdGUodHJlZXJvb3QseC0+cCk7CgkJCQl4ID0gKnRyZWVyb290OwoJCQl9CgkJfQoJfQoJeC0+Y29sb3IgPSBCTEFDSzsKfQoKdm9pZCByYmRlbGV0ZShOT0RFUFRSICp0cmVlcm9vdCwgaW50IHopIHsKCU5PREVQVFIgWiA9IHNlYXJjaCgqdHJlZXJvb3QsIHopOwoJaWYgKFogPT0gTklMUFRSKSB7CgkJcHJpbnRmKCJOb2RlIHRvIGJlIGRlbGV0ZWQgbm90IGZvdW5kXG4iKTsKCQlyZXR1cm47Cgl9CglOT0RFUFRSIHkgPSBaOwoJaW50IHlvYyA9IHktPmNvbG9yOwoJTk9ERVBUUiB4OwoJaWYgKFotPmxlZnQgPT0gTklMUFRSKSB7CgkJeCA9IFotPnJpZ2h0OwoJCXJidHJhbnNwbGFudCh0cmVlcm9vdCxaLFotPnJpZ2h0KTsKCX0KCWVsc2UgaWYgKFotPnJpZ2h0ID09IE5JTFBUUikgewoJCXggPSBaLT5sZWZ0OwoJCXJidHJhbnNwbGFudCh0cmVlcm9vdCxaLFotPmxlZnQpOwoJfQoJZWxzZSB7CgkJeSA9IG1pbmltdW0oWi0+cmlnaHQpOwoJCXlvYyA9IHktPmNvbG9yOwoJCXggPSB5LT5yaWdodDsKCQlpZiAoeS0+cCA9PSBaKQoJCQl4LT5wID0geTsKCQllbHNlIHsKCQkJcmJ0cmFuc3BsYW50KHRyZWVyb290LHkseS0+cmlnaHQpOwoJCQl5LT5yaWdodCA9IFotPnJpZ2h0OwoJCQl5LT5yaWdodC0+cCA9IHk7CgkJfQoJCXJidHJhbnNwbGFudCh0cmVlcm9vdCxaLHkpOwoJCXktPmxlZnQgPSBaLT5sZWZ0OwoJCXktPmxlZnQtPnAgPSB5OwoJCXktPmNvbG9yID0gWi0+Y29sb3I7Cgl9CglpZiAoeW9jID09IEJMQUNLKQoJCXJiZGVsZXRlZml4dXAodHJlZXJvb3QseCk7Cn0KCm1haW4oKQp7CglOSUwubGVmdCA9IE5JTC5yaWdodCA9IE5JTC5wID0gTklMUFRSOwoJTklMLmNvbG9yID0gQkxBQ0s7CglOT0RFUFRSIHRyZWUgPSBOSUxQVFI7CglpbnQgbjsKCXdoaWxlICgxKSB7CgkJcHJpbnRmKCIxLkluc2VydFxuMi5TZWFyY2hcbjMuSW5vcmRlciBXYWxrXG40Lk1pbmltdW1cbjUuTWF4aW11bVxuNi5TdWNjZXNzb3JcbjcuUHJlZGVjZXNzb3JcbjguRGVsZXRlXG45LkV4aXRcbiIpOwoJCXNjYW5mKCIlZCIsICZuKTsKCQlpZiAobiA9PSAxKSB7CgkJCXByaW50ZigiRW50ZXIgYW55IG51bWJlcjpcbiIpOwoJCQlpbnQgbnVtOwoJCQlzY2FuZigiJWQiLCAmbnVtKTsKCQkJcmJpbnNlcnQoJnRyZWUsIG51bSk7CgkJfQoJCWVsc2UgaWYgKG4gPT0gMikgewoJCQlwcmludGYoIkVudGVyIHRoZSBudW1iZXIgdG8gYmUgc2VhcmNoXG4iKTsKCQkJaW50IG51bTsKCQkJc2NhbmYoIiVkIiwgJm51bSk7CgkJCWlmIChzZWFyY2godHJlZSwgbnVtKSA9PSBOSUxQVFIpCgkJCQlwcmludGYoIiVkIG5vdCBmb3VuZFxuIiwgbnVtKTsKCQkJZWxzZQoJCQkJcHJpbnRmKCIlZCBmb3VuZFxuIiwgbnVtKTsKCQl9CgkJZWxzZSBpZiAobiA9PSAzKSB7CgkJCWlub3JkZXIodHJlZSk7CgkJCXByaW50ZigiXG4iKTsKCQl9CgkJZWxzZSBpZiAobiA9PSA0KQoJCQlwcmludGYoIiVkXG4iLCBtaW5pbXVtKHRyZWUpLT5rZXkpOwoJCWVsc2UgaWYgKG4gPT0gNSkKCQkJcHJpbnRmKCIlZFxuIiwgbWF4aW11bSh0cmVlKS0+a2V5KTsKCQllbHNlIGlmIChuID09IDYpIHsKCQkJcHJpbnRmKCJFbnRlciB0aGUgbnVtYmVyIHdob3NlIHN1Y2Nlc3NvciBuZWVkcyB0byBiZSBmb3VuZFxuIik7CgkJCWludCBudW07CgkJCXNjYW5mKCIlZCIsICZudW0pOwoJCQlOT0RFUFRSIHQgPSBzdWNjZXNzb3IodHJlZSwgbnVtKTsKCQkJaWYgKHQgIT0gTlVMTCkKCQkJCXByaW50ZigiJWRcbiIsIHQtPmtleSk7CgkJfQoJCWVsc2UgaWYgKG4gPT0gNykgewoJCQlwcmludGYoIkVudGVyIHRoZSBudW1iZXIgd2hvc2UgcHJlZGVjZXNzb3IgbmVlZHMgdG8gYmUgZm91bmRcbiIpOwoJCQlpbnQgbnVtOwoJCQlzY2FuZigiJWQiLCAmbnVtKTsKCQkJTk9ERVBUUiB0ID0gcHJlZGVjZXNzb3IodHJlZSwgbnVtKTsKCQkJaWYgKHQgIT0gTlVMTCkKCQkJCXByaW50ZigiJWRcbiIsIHQtPmtleSk7CgkJfQoJCWVsc2UgaWYgKG4gPT0gOCkgewoJCQlwcmludGYoIkVudGVyIHRoZSBudW1iZXIgdG8gYmUgZGVsZXRlZFxuIik7CgkJCWludCBudW07CgkJCXNjYW5mKCIlZCIsICZudW0pOwoJCQlyYmRlbGV0ZSgmdHJlZSwgbnVtKTsKCQl9CgkJZWxzZSAKCQkJYnJlYWs7Cgl9CglyZXR1cm4gMDsKfQo=