LyogQm9vc3QgZXhhbXBsZS9maWx0ZXIuY3BwCiAqIHR3byBleGFtcGxlcyBvZiBmaWx0ZXJzIGZvciBjb21wdXRpbmcgdGhlIHNpZ24gb2YgYSBkZXRlcm1pbmFudAogKiB0aGUgc2Vjb25kIGZpbHRlciBpcyBiYXNlZCBvbiBhbiBpZGVhIHByZXNlbnRlZCBpbgogKiAiSW50ZXJ2YWwgYXJpdGhtZXRpYyB5aWVsZHMgZWZmaWNpZW50IGR5bmFtaWMgZmlsdGVycyBmb3IgY29tcHV0YXRpb25hbAogKiBnZW9tZXRyeSIgYnkgQnL2bm5pbWFubiwgQnVybmlrZWwgYW5kIFBpb24sIDIwMDEKICoKICogQ29weXJpZ2h0IDIwMDMgR3VpbGxhdW1lIE1lbHF1aW9uZAogKgogKiBEaXN0cmlidXRlZCB1bmRlciB0aGUgQm9vc3QgU29mdHdhcmUgTGljZW5zZSwgVmVyc2lvbiAxLjAuCiAqIChTZWUgYWNjb21wYW55aW5nIGZpbGUgTElDRU5TRV8xXzAudHh0IG9yCiAqIGNvcHkgYXQgaHR0cDovL3d3dy5ib29zdC5vcmcvTElDRU5TRV8xXzAudHh0KQogKi8KCiNpbmNsdWRlIDxib29zdC9udW1lcmljL2ludGVydmFsLmhwcD4KI2luY2x1ZGUgPGlvc3RyZWFtPgoKbmFtZXNwYWNlIGR1bW15IHsKICB1c2luZyBuYW1lc3BhY2UgYm9vc3Q7CiAgdXNpbmcgbmFtZXNwYWNlIG51bWVyaWM7CiAgdXNpbmcgbmFtZXNwYWNlIGludGVydmFsX2xpYjsKICB0eXBlZGVmIHNhdmVfc3RhdGU8cm91bmRlZF9hcml0aF9vcHA8ZG91YmxlPiA+IFI7CiAgdHlwZWRlZiBjaGVja2luZ19ub19uYW48ZG91YmxlLCBjaGVja2luZ19ub19lbXB0eTxkb3VibGU+ID4gUDsKICB0eXBlZGVmIGludGVydmFsPGRvdWJsZSwgcG9saWNpZXM8UiwgUD4gPiBJOwp9Cgp0ZW1wbGF0ZTxjbGFzcyBUPgpjbGFzcyB2ZWN0b3IgewogIFQqIHB0cjsKcHVibGljOgogIHZlY3RvcihpbnQgZCkgeyBwdHIgPSAoVCopbWFsbG9jKHNpemVvZihUKSAqIGQpOyB9CiAgfnZlY3RvcigpIHsgZnJlZShwdHIpOyB9CiAgY29uc3QgVCYgb3BlcmF0b3JbXShpbnQgaSkgY29uc3QgeyByZXR1cm4gcHRyW2ldOyB9CiAgVCYgb3BlcmF0b3JbXShpbnQgaSkgeyByZXR1cm4gcHRyW2ldOyB9Cn07Cgp0ZW1wbGF0ZTxjbGFzcyBUPgpjbGFzcyBtYXRyaXggewogIGludCBkaW07CiAgVCogcHRyOwpwdWJsaWM6CiAgbWF0cml4KGludCBkKTogZGltKGQpIHsgcHRyID0gKFQqKW1hbGxvYyhzaXplb2YoVCkgKiBkaW0gKiBkaW0pOyB9CiAgfm1hdHJpeCgpIHsgZnJlZShwdHIpOyB9CiAgaW50IGdldF9kaW0oKSBjb25zdCB7IHJldHVybiBkaW07IH0KICB2b2lkIGFzc2lnbihjb25zdCBtYXRyaXg8VD4gJmEpIHsgbWVtY3B5KHB0ciwgYS5wdHIsIHNpemVvZihUKSAqIGRpbSAqIGRpbSk7IH0KICBjb25zdCBUKiBvcGVyYXRvcltdKGludCBpKSBjb25zdCB7IHJldHVybiAmKHB0cltpICogZGltXSk7IH0KICBUKiBvcGVyYXRvcltdKGludCBpKSB7IHJldHVybiAmKHB0cltpICogZGltXSk7IH0KfTsKCnR5cGVkZWYgZHVtbXk6OkkgSV9kYmw7CgovKiBjb21wdXRlIHRoZSBzaWduIG9mIGEgZGV0ZXJtaW5hbnQgdXNpbmcgYW4gaW50ZXJ2YWwgTFUtZGVjb21wb3NpdGlvbjsgdGhlCiAgIGZ1bmN0aW9uIGFuc3dlcnMgMSBvciAtMSBpZiB0aGUgZGV0ZXJtaW5hbnQgaXMgcG9zaXRpdmUgb3IgbmVnYXRpdmUgKGFuZAogICBtb3JlIGltcG9ydGFudGx5LCB0aGUgcmVzdWx0IG11c3QgYmUgcHJvdmFibGUpLCBvciAwIGlmIHRoZSBhbGdvcml0aG0gd2FzCiAgIHVuYWJsZSB0byBnZXQgYSBjb3JyZWN0IHNpZ24gKi8KaW50IGRldF9zaWduX2FsZ28xKGNvbnN0IG1hdHJpeDxkb3VibGU+ICZhKSB7CiAgaW50IGRpbSA9IGEuZ2V0X2RpbSgpOwogIHZlY3RvcjxpbnQ+IHAoZGltKTsKICBmb3IoaW50IGkgPSAwOyBpIDwgZGltOyBpKyspIHBbaV0gPSBpOwogIGludCBzaWcgPSAxOwogIElfZGJsOjp0cmFpdHNfdHlwZTo6cm91bmRpbmcgcm5kOwogIHR5cGVkZWYgYm9vc3Q6Om51bWVyaWM6OmludGVydmFsX2xpYjo6dW5wcm90ZWN0PElfZGJsPjo6dHlwZSBJOwogIG1hdHJpeDxJPiB1KGRpbSk7CiAgZm9yKGludCBpID0gMDsgaSA8IGRpbTsgaSsrKSB7CiAgICBjb25zdCBkb3VibGUqIGxpbmUxID0gYVtpXTsKICAgIEkqIGxpbmUyID0gdVtpXTsKICAgIGZvcihpbnQgaiA9IDA7IGogPCBkaW07IGorKykKICAgICAgbGluZTJbal0gPSBsaW5lMVtqXTsKICB9CiAgLy8gY29tcHV0YXRpb24gb2YgTCBhbmQgVQogIGZvcihpbnQgaSA9IDA7IGkgPCBkaW07IGkrKykgewogICAgLy8gcGFydGlhbCBwaXZvdGluZwogICAgewogICAgICBpbnQgcGl2b3QgPSBpOwogICAgICBkb3VibGUgbWF4ID0gMDsKICAgICAgZm9yKGludCBqID0gaTsgaiA8IGRpbTsgaisrKSB7CiAgICAgICAgY29uc3QgSSAmdiA9IHVbcFtqXV1baV07CiAgICAgICAgaWYgKHplcm9faW4odikpIGNvbnRpbnVlOwogICAgICAgIGRvdWJsZSBtID0gbm9ybSh2KTsKICAgICAgICBpZiAobSA+IG1heCkgeyBtYXggPSBtOyBwaXZvdCA9IGo7IH0KICAgICAgfQogICAgICBpZiAobWF4ID09IDApIHJldHVybiAwOwogICAgICBpZiAocGl2b3QgIT0gaSkgewogICAgICAgIHNpZyA9IC1zaWc7CiAgICAgICAgaW50IHRtcCA9IHBbaV07CiAgICAgICAgcFtpXSA9IHBbcGl2b3RdOwogICAgICAgIHBbcGl2b3RdID0gdG1wOwogICAgICB9CiAgICB9CiAgICAvLyBVW2ksP10KICAgIHsKICAgICAgSSAqbGluZTEgPSB1W3BbaV1dOwogICAgICBjb25zdCBJICZwaXZvdCA9IGxpbmUxW2ldOwogICAgICBpZiAoYm9vc3Q6Om51bWVyaWM6OmludGVydmFsX2xpYjo6Y2VybHQocGl2b3QsIDAuKSkgc2lnID0gLXNpZzsKICAgICAgZm9yKGludCBrID0gaSArIDE7IGsgPCBkaW07IGsrKykgewogICAgICAgIEkgKmxpbmUyID0gdVtwW2tdXTsKICAgICAgICBJIGZhY3QgPSBsaW5lMltpXSAvIHBpdm90OwogICAgICAgIGZvcihpbnQgaiA9IGkgKyAxOyBqIDwgZGltOyBqKyspIGxpbmUyW2pdIC09IGZhY3QgKiBsaW5lMVtqXTsKICAgICAgfQogICAgfQogIH0KICByZXR1cm4gc2lnOwp9CgovKiBjb21wdXRlIHRoZSBzaWduIG9mIGEgZGV0ZXJtaW5hbnQgdXNpbmcgYSBmbG9hdGluZy1wb2ludCBMVS1kZWNvbXBvc2l0aW9uCiAgIGFuZCBhbiBhIHBvc3RlcmlvcmkgaW50ZXJ2YWwgdmFsaWRhdGlvbjsgdGhlIG1lYW5pbmcgb2YgdGhlIGFuc3dlciBpcyB0aGUKICAgc2FtZSBhcyBwcmV2aW91c2x5ICovCmludCBkZXRfc2lnbl9hbGdvMihjb25zdCBtYXRyaXg8ZG91YmxlPiAmYSkgewogIGludCBkaW0gPSBhLmdldF9kaW0oKTsKICB2ZWN0b3I8aW50PiBwKGRpbSk7CiAgZm9yKGludCBpID0gMDsgaSA8IGRpbTsgaSsrKSBwW2ldID0gaTsKICBpbnQgc2lnID0gMTsKICBtYXRyaXg8ZG91YmxlPiBsdWkoZGltKTsKICB7CiAgICAvLyBjb21wdXRhdGlvbiBvZiBMIGFuZCBVCiAgICBtYXRyaXg8ZG91YmxlPiBsdShkaW0pOwogICAgbHUuYXNzaWduKGEpOwogICAgZm9yKGludCBpID0gMDsgaSA8IGRpbTsgaSsrKSB7CiAgICAgIC8vIHBhcnRpYWwgcGl2b3RpbmcKICAgICAgewogICAgICAgIGludCBwaXZvdCA9IGk7CiAgICAgICAgZG91YmxlIG1heCA9IHN0ZDo6YWJzKGx1W3BbaV1dW2ldKTsKICAgICAgICBmb3IoaW50IGogPSBpICsgMTsgaiA8IGRpbTsgaisrKSB7CiAgICAgICAgICBkb3VibGUgbSA9IHN0ZDo6YWJzKGx1W3Bbal1dW2ldKTsKICAgICAgICAgIGlmIChtID4gbWF4KSB7IG1heCA9IG07IHBpdm90ID0gajsgfQogICAgICAgIH0KICAgICAgICBpZiAobWF4ID09IDApIHJldHVybiAwOwogICAgICAgIGlmIChwaXZvdCAhPSBpKSB7CiAgICAgICAgICBzaWcgPSAtc2lnOwogICAgICAgICAgaW50IHRtcCA9IHBbaV07CiAgICAgICAgICBwW2ldID0gcFtwaXZvdF07CiAgICAgICAgICBwW3Bpdm90XSA9IHRtcDsKICAgICAgICB9CiAgICAgIH0KICAgICAgLy8gTFs/LGldIGFuZCBVW2ksP10KICAgICAgewogICAgICAgIGRvdWJsZSAqbGluZTEgPSBsdVtwW2ldXTsKICAgICAgICBkb3VibGUgcGl2b3QgPSBsaW5lMVtpXTsKICAgICAgICBpZiAocGl2b3QgPCAwKSBzaWcgPSAtc2lnOwogICAgICAgIGZvcihpbnQgayA9IGkgKyAxOyBrIDwgZGltOyBrKyspIHsKICAgICAgICAgIGRvdWJsZSAqbGluZTIgPSBsdVtwW2tdXTsKICAgICAgICAgIGRvdWJsZSBmYWN0ID0gbGluZTJbaV0gLyBwaXZvdDsKICAgICAgICAgIGxpbmUyW2ldID0gZmFjdDsKICAgICAgICAgIGZvcihpbnQgaiA9IGkgKyAxOyBqIDwgZGltOyBqKyspIGxpbmUyW2pdIC09IGxpbmUxW2pdICogZmFjdDsKICAgICAgICB9CiAgICAgIH0KICAgIH0KCiAgICAvLyBjb21wdXRhdGlvbiBvZiBhcHByb3hpbWF0ZSBpbnZlcnNlczogTGkgYW5kIFVpCiAgICBmb3IoaW50IGogPSAwOyBqIDwgZGltOyBqKyspIHsKICAgICAgZm9yKGludCBpID0gaiArIDE7IGkgPCBkaW07IGkrKykgewogICAgICAgIGRvdWJsZSAqbGluZSA9IGx1W3BbaV1dOwogICAgICAgIGRvdWJsZSBzID0gLSBsaW5lW2pdOwogICAgICAgIGZvcihpbnQgayA9IGogKyAxOyBrIDwgaTsgaysrKSBzIC09IGxpbmVba10gKiBsdWlba11bal07CiAgICAgICAgbHVpW2ldW2pdID0gczsKICAgICAgfQogICAgICBsdWlbal1bal0gPSAxIC8gbHVbcFtqXV1bal07CiAgICAgIGZvcihpbnQgaSA9IGogLSAxOyBpID49IDA7IGktLSkgewogICAgICAgIGRvdWJsZSAqbGluZSA9IGx1W3BbaV1dOwogICAgICAgIGRvdWJsZSBzID0gMDsKICAgICAgICBmb3IoaW50IGsgPSBpICsgMTsgayA8PSBqOyBrKyspIHMgLT0gbGluZVtrXSAqIGx1aVtrXVtqXTsKICAgICAgICBsdWlbaV1bal0gPSBzIC8gbGluZVtpXTsKICAgICAgfQogICAgfQogIH0KCiAgLy8gbm9ybSBvZiBQQVVpTGktSSBjb21wdXRlZCB3aXRoIGludGVydmFscwogIHsKICAgIElfZGJsOjp0cmFpdHNfdHlwZTo6cm91bmRpbmcgcm5kOwogICAgdHlwZWRlZiBib29zdDo6bnVtZXJpYzo6aW50ZXJ2YWxfbGliOjp1bnByb3RlY3Q8SV9kYmw+Ojp0eXBlIEk7CiAgICB2ZWN0b3I8ST4gbTEoZGltKTsKICAgIHZlY3RvcjxJPiBtMihkaW0pOwogICAgZm9yKGludCBpID0gMDsgaSA8IGRpbTsgaSsrKSB7CiAgICAgIGZvcihpbnQgaiA9IDA7IGogPCBkaW07IGorKykgbTFbal0gPSAwOwogICAgICBjb25zdCBkb3VibGUgKmwxID0gYVtwW2ldXTsKICAgICAgZm9yKGludCBqID0gMDsgaiA8IGRpbTsgaisrKSB7CiAgICAgICAgZG91YmxlIHYgPSBsMVtqXTsgICAgLy8gUEFbaSxqXQogICAgICAgIGRvdWJsZSAqbDIgPSBsdWlbal07IC8vIFVpW2osP10KICAgICAgICBmb3IoaW50IGsgPSBqOyBrIDwgZGltOyBrKyspIHsKICAgICAgICAgIHVzaW5nIGJvb3N0OjpudW1lcmljOjppbnRlcnZhbF9saWI6Om11bDsKICAgICAgICAgIG0xW2tdICs9IG11bDxJPih2LCBsMltrXSk7IC8vIFBBVWlbaSxrXQogICAgICAgIH0KICAgICAgfQogICAgICBmb3IoaW50IGogPSAwOyBqIDwgZGltOyBqKyspIG0yW2pdID0gbTFbal07IC8vIFBBVWlbaSxqXSAqIExpW2osal0KICAgICAgZm9yKGludCBqID0gMTsgaiA8IGRpbTsgaisrKSB7CiAgICAgICAgY29uc3QgSSAmdiA9IG0xW2pdOyAgLy8gUEFVaVtpLGpdCiAgICAgICAgZG91YmxlICpsMiA9IGx1aVtqXTsgLy8gTGlbaiw/XQogICAgICAgIGZvcihpbnQgayA9IDA7IGsgPCBqOyBrKyspCiAgICAgICAgICBtMltrXSArPSB2ICogbDJba107IC8vIFBBVWlMaVtpLGtdCiAgICAgIH0KICAgICAgbTJbaV0gLT0gMTsgLy8gUEFVaUxpLUkKICAgICAgZG91YmxlIHNzID0gMDsKICAgICAgZm9yKGludCBpID0gMDsgaSA8IGRpbTsgaSsrKSBzcyA9IHJuZC5hZGRfdXAoc3MsIG5vcm0obTJbaV0pKTsKICAgICAgaWYgKHNzID49IDEpIHJldHVybiAwOwogICAgfQogIH0KICByZXR1cm4gc2lnOwp9CgppbnQgbWFpbigpIHsKICBpbnQgZGltID0gMjA7CiAgbWF0cml4PGRvdWJsZT4gbShkaW0pOwogIGZvcihpbnQgaSA9IDA7IGkgPCBkaW07IGkrKykgZm9yKGludCBqID0gMDsgaiA8IGRpbTsgaisrKQogICAgbVtpXVtqXSA9IC8qMSAvIChpLWotMC4wMDEpKi8gY29zKDEraSpzaW4oMSArIGopKSAvKjEuLygxK2kraikqLzsKCiAgLy8gY29tcHV0ZSB0aGUgc2lnbiBvZiB0aGUgZGV0ZXJtaW5hbnQgb2YgYSAic3RyYW5nZSIgbWF0cml4IHdpdGggdGhlIHR3bwogIC8vIGFsZ29yaXRobXMsIHRoZSBmaXJzdCBzaG91bGQgZmFpbCBhbmQgdGhlIHNlY29uZCBzdWNjZWVkCiAgc3RkOjpjb3V0IDw8IGRldF9zaWduX2FsZ28xKG0pIDw8ICIgIiA8PCBkZXRfc2lnbl9hbGdvMihtKSA8PCBzdGQ6OmVuZGw7Cn0K