#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <cassert>
//naive quicksort
template < class bidi_iterator, class predicate>
void quick_sort( const bidi_iterator first, const bidi_iterator last, const predicate& pred) {
using std:: swap ;
if ( first == last) //0
return ;
bidi_iterator next = std:: next ( first) ;
if ( next == last) // 1
return ;
if ( std:: next ( next) == last) { // 2
if ( pred( * next, * first) )
swap( * first, * next) ;
return ;
}
//3+
bidi_iterator mid = std:: partition ( next, last, std:: bind2nd ( pred, * first) ) ;
if ( mid! = next) { //1+ on left
bidi_iterator prev = std:: prev ( mid) ;
swap( * first, * prev) ;
if ( std:: next ( next) ! = mid) //2+ on left
quick_sort( first, prev, pred) ;
}
if ( mid! = last && mid! = std:: prev ( last) ) //2+ on right
quick_sort( mid, last, pred) ;
assert ( std:: is_sorted ( first, last, pred) ) ;
}
template < class bidi_iterator>
void quick_sort( const bidi_iterator first, const bidi_iterator last) {
typedef typename std:: iterator_traits < bidi_iterator> :: value_type value_type;
return quick_sort( first, last, std:: less < value_type> ( ) ) ;
}
//inplace quicksort
//This sort needs to work on a series of "chunks" in a certain format.
// Each chunk is: [(1)pivot][(?) data less than pivot, but greater than pivot of previous chunk]
// Given data: 17,16,8,6,18,12,14,13,8,6,5,19,22,12,16,20,7,0,10,6,15,18,19,6
// We chunk it: [17,16,8,6,6,12,14,13,8,6,5,15,6,12,16,10,7,0],[20,18,19,18,19],[22]
// Then we iterate over the list, one chunk at a time: [17,16,8,6,6,12,14,13,8,6,5,15,6,12,16,10,7,0]
// splitting each chunk into two subchunks: [16,7,8,6,6,12,14,13,8,6,5,15,6,12,0,10],[17,16,]
// A chunk that is 1 element (only the pivot, no data) is in the correct location.
template < class bidi_iterator, class predicate>
void inplace_sort( const bidi_iterator first, const bidi_iterator last, const predicate& pred) {
using std:: swap ;
using std:: distance ;
if ( first == last)
return ;
bidi_iterator beginchunk = first;
bidi_iterator endchunk = last;
bool cached_end = true ;
//Rearrange the origional data into "Chunks"
//Basically, just quicksort down the right side until we find the biggest element
do {
bidi_iterator mid = std:: partition ( std:: next ( beginchunk) , last, std:: bind2nd ( pred, * beginchunk) ) ;
if ( beginchunk == first) //cache first chunk size
endchunk = mid;
beginchunk = mid;
} while ( beginchunk ! = last) ;
beginchunk = first; //starting from the left
do {
//find first unsorted chunk (first consecutive unsorted elements)
bidi_iterator newpivot = std:: next ( beginchunk) ;
while ( newpivot! = last && pred( * beginchunk, * newpivot) ) {
beginchunk = newpivot;
++ newpivot;
cached_end = false ;
}
//if it's all sorted, we're done
if ( newpivot== last)
break ;
if ( cached_end == false ) {
//find the end of the chunk (first element greater than *beginchunk)
endchunk = std:: next ( newpivot) ;
int len = 2 ;
while ( endchunk! = last && pred( * endchunk, * beginchunk) ) {
++ len;
++ endchunk;
}
}
bidi_iterator mid = endchunk;
// if the chunk is two elements, just swap
if ( std:: next ( newpivot) == endchunk) {
swap( * beginchunk, * newpivot) ;
beginchunk = endchunk; //move to the next chunk
cached_end = false ;
} else {
//if more than two, partition into two seperate chunks
//first, parition on newpivot (the first element)
mid = std:: partition ( std:: next ( newpivot) , endchunk, std:: bind2nd ( pred, * newpivot) ) ;
//this means we have to move the pivots
//so the newpivot pivot begins the first subchunk
//and the beginchunk pivot begins the second subchunk
swap( * beginchunk, * newpivot) ;
bidi_iterator prev = std:: prev ( mid) ;
if ( newpivot ! = prev) {
swap( * newpivot, * prev) ;
//and cached the endchunk since we know it already
endchunk = mid;
cached_end = true ;
} else
cached_end = false ;
//and "repeat" which will do the left side
}
} while ( beginchunk ! = last) ;
assert ( std:: is_sorted ( first, last, pred) ) ;
return ;
}
template < class bidi_iterator>
void inplace_sort( bidi_iterator begin, bidi_iterator end) {
typedef typename std:: iterator_traits < bidi_iterator> :: value_type value_type;
return inplace_sort( begin, end, std:: less < value_type> ( ) ) ;
}
#include <cstdlib>
#include <ctime>
#include <vector>
template < typename T>
struct tracer : std:: less < T> {
static unsigned count;
bool operator( ) ( T x, T y) const {
++ count;
return std:: less < T> :: operator ( ) ( x, y) ;
}
} ;
template < typename T>
unsigned tracer< T> :: count = 0 ;
int main( ) {
unsigned test_size;
while ( std:: cin >> test_size) {
double stdsort_time= 0 ;
double inplacesort_time= 0 ;
srand ( ( unsigned ) time ( NULL ) ) ;
std:: vector < int > data( test_size) ;
for ( unsigned i= 0 ; i< data.size ( ) ; ++ i)
data[ i] = 10000 + rand ( ) ;
std:: vector < int > data2;
{
data2 = data;
std:: sort ( data2.begin ( ) , data2.end ( ) , tracer< int > ( ) ) ;
data2 = data;
clock_t begin = clock ( ) ;
std:: sort ( data2.begin ( ) , data2.end ( ) ) ;
clock_t end = clock ( ) ;
stdsort_time = double ( end- begin) / CLOCKS_PER_SEC ;
}
std:: cout << "comparisons: " << tracer< int > :: count << ' ' ;
std:: cout << "std::sort took " << stdsort_time << "s.\n " ;
tracer< int > :: count = 0 ;
{
data2 = data;
quick_sort( data2.begin ( ) , data2.end ( ) , tracer< int > ( ) ) ;
data2 = data;
clock_t begin = clock ( ) ;
quick_sort( data2.begin ( ) , data2.end ( ) ) ;
clock_t end = clock ( ) ;
stdsort_time = double ( end- begin) / CLOCKS_PER_SEC ;
}
std:: cout << "comparisons: " << tracer< int > :: count << ' ' ;
std:: cout << "quicksort took " << stdsort_time << "s.\n " ;
tracer< int > :: count = 0 ;
{
data2 = data;
inplace_sort( data2.begin ( ) , data2.end ( ) , tracer< int > ( ) ) ;
data2 = data;
clock_t begin = clock ( ) ;
inplace_sort( data2.begin ( ) , data2.end ( ) ) ;
clock_t end = clock ( ) ;
inplacesort_time = double ( end- begin) / CLOCKS_PER_SEC ;
}
std:: cout << "comparisons: " << tracer< int > :: count << ' ' ;
std:: cout << "inplace_sort took " << inplacesort_time << "s.\n " ;
}
return 0 ;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8Y2Fzc2VydD4KCi8vbmFpdmUgcXVpY2tzb3J0CnRlbXBsYXRlPGNsYXNzIGJpZGlfaXRlcmF0b3IsIGNsYXNzIHByZWRpY2F0ZT4Kdm9pZCBxdWlja19zb3J0KGNvbnN0IGJpZGlfaXRlcmF0b3IgZmlyc3QsIGNvbnN0IGJpZGlfaXRlcmF0b3IgbGFzdCwgY29uc3QgcHJlZGljYXRlJiBwcmVkKSB7Cgl1c2luZyBzdGQ6OnN3YXA7CglpZiAoZmlyc3QgPT0gbGFzdCkgLy8wCgkJcmV0dXJuOwoJYmlkaV9pdGVyYXRvciBuZXh0ID0gc3RkOjpuZXh0KGZpcnN0KTsKCWlmIChuZXh0ID09IGxhc3QpICAvLyAxCgkJcmV0dXJuOwoJaWYgKHN0ZDo6bmV4dChuZXh0KSA9PSBsYXN0KSB7IC8vIDIgCgkJaWYgKHByZWQoKm5leHQsICpmaXJzdCkpCgkJCXN3YXAoKmZpcnN0LCAqbmV4dCk7CgkJcmV0dXJuOwoJfQoJLy8zKwoJYmlkaV9pdGVyYXRvciBtaWQgPSBzdGQ6OnBhcnRpdGlvbihuZXh0LCBsYXN0LCBzdGQ6OmJpbmQybmQocHJlZCwgKmZpcnN0KSk7CglpZiAobWlkIT1uZXh0KSB7IC8vMSsgb24gbGVmdAoJCWJpZGlfaXRlcmF0b3IgcHJldiA9IHN0ZDo6cHJldihtaWQpOwoJCXN3YXAoKmZpcnN0LCAqcHJldik7CgkJaWYgKHN0ZDo6bmV4dChuZXh0KSE9bWlkKSAvLzIrIG9uIGxlZnQKCQkJcXVpY2tfc29ydChmaXJzdCwgcHJldiwgcHJlZCk7Cgl9CglpZiAobWlkIT1sYXN0ICYmIG1pZCE9c3RkOjpwcmV2KGxhc3QpKSAvLzIrIG9uIHJpZ2h0CgkJcXVpY2tfc29ydChtaWQsIGxhc3QsIHByZWQpOwoJYXNzZXJ0KHN0ZDo6aXNfc29ydGVkKGZpcnN0LCBsYXN0LCBwcmVkKSk7Cn0KdGVtcGxhdGU8Y2xhc3MgYmlkaV9pdGVyYXRvcj4Kdm9pZCBxdWlja19zb3J0KGNvbnN0IGJpZGlfaXRlcmF0b3IgZmlyc3QsIGNvbnN0IGJpZGlfaXRlcmF0b3IgbGFzdCkgewoJdHlwZWRlZiB0eXBlbmFtZSBzdGQ6Oml0ZXJhdG9yX3RyYWl0czxiaWRpX2l0ZXJhdG9yPjo6dmFsdWVfdHlwZSB2YWx1ZV90eXBlOwoJcmV0dXJuIHF1aWNrX3NvcnQoZmlyc3QsIGxhc3QsIHN0ZDo6bGVzczx2YWx1ZV90eXBlPigpKTsKfQoKLy9pbnBsYWNlIHF1aWNrc29ydAovL1RoaXMgc29ydCBuZWVkcyB0byB3b3JrIG9uIGEgc2VyaWVzIG9mICJjaHVua3MiIGluIGEgY2VydGFpbiBmb3JtYXQuCi8vIEVhY2ggY2h1bmsgaXM6IFsoMSlwaXZvdF1bKD8pIGRhdGEgbGVzcyB0aGFuIHBpdm90LCBidXQgZ3JlYXRlciB0aGFuIHBpdm90IG9mIHByZXZpb3VzIGNodW5rXQovLyAgICAgR2l2ZW4gZGF0YTogIDE3LDE2LDgsNiwxOCwxMiwxNCwxMyw4LDYsNSwxOSwyMiwxMiwxNiwyMCw3LDAsMTAsNiwxNSwxOCwxOSw2Ci8vICAgICBXZSBjaHVuayBpdDogWzE3LDE2LDgsNiw2LDEyLDE0LDEzLDgsNiw1LDE1LDYsMTIsMTYsMTAsNywwXSxbMjAsMTgsMTksMTgsMTldLFsyMl0KLy8gVGhlbiB3ZSBpdGVyYXRlIG92ZXIgdGhlIGxpc3QsIG9uZSBjaHVuayBhdCBhIHRpbWU6ICBbMTcsMTYsOCw2LDYsMTIsMTQsMTMsOCw2LDUsMTUsNiwxMiwxNiwxMCw3LDBdCi8vICAgIHNwbGl0dGluZyBlYWNoIGNodW5rIGludG8gdHdvIHN1YmNodW5rczogWzE2LDcsOCw2LDYsMTIsMTQsMTMsOCw2LDUsMTUsNiwxMiwwLDEwXSxbMTcsMTYsXQovLyBBIGNodW5rIHRoYXQgaXMgMSBlbGVtZW50IChvbmx5IHRoZSBwaXZvdCwgbm8gZGF0YSkgaXMgaW4gdGhlIGNvcnJlY3QgbG9jYXRpb24uCnRlbXBsYXRlPGNsYXNzIGJpZGlfaXRlcmF0b3IsIGNsYXNzIHByZWRpY2F0ZT4Kdm9pZCBpbnBsYWNlX3NvcnQoY29uc3QgYmlkaV9pdGVyYXRvciBmaXJzdCwgY29uc3QgYmlkaV9pdGVyYXRvciBsYXN0LCBjb25zdCBwcmVkaWNhdGUmIHByZWQpIHsKCXVzaW5nIHN0ZDo6c3dhcDsKCXVzaW5nIHN0ZDo6ZGlzdGFuY2U7CglpZiAoZmlyc3QgPT0gbGFzdCkKCQlyZXR1cm47CgliaWRpX2l0ZXJhdG9yIGJlZ2luY2h1bmsgPSBmaXJzdDsKCWJpZGlfaXRlcmF0b3IgZW5kY2h1bmsgPSBsYXN0OwoJYm9vbCBjYWNoZWRfZW5kID0gdHJ1ZTsKCS8vUmVhcnJhbmdlIHRoZSBvcmlnaW9uYWwgZGF0YSBpbnRvICJDaHVua3MiCgkvL0Jhc2ljYWxseSwganVzdCBxdWlja3NvcnQgZG93biB0aGUgcmlnaHQgc2lkZSB1bnRpbCB3ZSBmaW5kIHRoZSBiaWdnZXN0IGVsZW1lbnQKCWRvIHsKCQliaWRpX2l0ZXJhdG9yIG1pZCA9IHN0ZDo6cGFydGl0aW9uKHN0ZDo6bmV4dChiZWdpbmNodW5rKSwgbGFzdCwgc3RkOjpiaW5kMm5kKHByZWQsICpiZWdpbmNodW5rKSk7CgkJaWYgKGJlZ2luY2h1bmsgPT0gZmlyc3QpICAvL2NhY2hlIGZpcnN0IGNodW5rIHNpemUKCQkJZW5kY2h1bmsgPSBtaWQ7CgkJYmVnaW5jaHVuayA9IG1pZDsKCX0gd2hpbGUoYmVnaW5jaHVuayAhPSBsYXN0KTsKCWJlZ2luY2h1bmsgPSBmaXJzdDsgLy9zdGFydGluZyBmcm9tIHRoZSBsZWZ0CglkbyB7CgkJLy9maW5kIGZpcnN0IHVuc29ydGVkIGNodW5rIChmaXJzdCBjb25zZWN1dGl2ZSB1bnNvcnRlZCBlbGVtZW50cykKCQliaWRpX2l0ZXJhdG9yIG5ld3Bpdm90ID0gc3RkOjpuZXh0KGJlZ2luY2h1bmspOwoJCXdoaWxlKG5ld3Bpdm90IT1sYXN0ICYmIHByZWQoKmJlZ2luY2h1bmssICpuZXdwaXZvdCkpIHsKCQkJYmVnaW5jaHVuayA9IG5ld3Bpdm90OyAKCQkJKytuZXdwaXZvdDsKCQkJY2FjaGVkX2VuZCA9IGZhbHNlOwoJCX0KCQkvL2lmIGl0J3MgYWxsIHNvcnRlZCwgd2UncmUgZG9uZQoJCWlmIChuZXdwaXZvdD09bGFzdCkgCgkJCWJyZWFrOwoJCWlmIChjYWNoZWRfZW5kID09IGZhbHNlKSB7CgkJCS8vZmluZCB0aGUgZW5kIG9mIHRoZSBjaHVuayAoZmlyc3QgZWxlbWVudCBncmVhdGVyIHRoYW4gKmJlZ2luY2h1bmspCgkJCWVuZGNodW5rID0gc3RkOjpuZXh0KG5ld3Bpdm90KTsKCQkJaW50IGxlbiA9IDI7CgkJCXdoaWxlKGVuZGNodW5rIT1sYXN0ICYmIHByZWQoKmVuZGNodW5rLCAqYmVnaW5jaHVuaykpIHsKCQkJCSsrbGVuOwoJCQkJKytlbmRjaHVuazsKCQkJfQoJCX0KCQliaWRpX2l0ZXJhdG9yIG1pZCA9ZW5kY2h1bms7CgkJLy8gaWYgdGhlIGNodW5rIGlzIHR3byBlbGVtZW50cywganVzdCBzd2FwCgkJaWYgKHN0ZDo6bmV4dChuZXdwaXZvdCkgPT0gZW5kY2h1bmspIHsKCQkJc3dhcCgqYmVnaW5jaHVuaywgKm5ld3Bpdm90KTsJCgkJCWJlZ2luY2h1bmsgPSBlbmRjaHVuazsgLy9tb3ZlIHRvIHRoZSBuZXh0IGNodW5rCgkJCWNhY2hlZF9lbmQgPSBmYWxzZTsKCQl9IGVsc2UgeyAKCQkJLy9pZiBtb3JlIHRoYW4gdHdvLCBwYXJ0aXRpb24gaW50byB0d28gc2VwZXJhdGUgY2h1bmtzCgkJCS8vZmlyc3QsIHBhcml0aW9uIG9uIG5ld3Bpdm90ICh0aGUgZmlyc3QgZWxlbWVudCkKCQkJbWlkID0gc3RkOjpwYXJ0aXRpb24oc3RkOjpuZXh0KG5ld3Bpdm90KSwgZW5kY2h1bmssIHN0ZDo6YmluZDJuZChwcmVkLCAqbmV3cGl2b3QpKTsJCgkJCS8vdGhpcyBtZWFucyB3ZSBoYXZlIHRvIG1vdmUgdGhlIHBpdm90cwoJCQkvL3NvIHRoZSBuZXdwaXZvdCBwaXZvdCBiZWdpbnMgdGhlIGZpcnN0IHN1YmNodW5rCgkJCS8vYW5kIHRoZSBiZWdpbmNodW5rIHBpdm90IGJlZ2lucyB0aGUgc2Vjb25kIHN1YmNodW5rCgkJCXN3YXAoKmJlZ2luY2h1bmssICpuZXdwaXZvdCk7CgkJCWJpZGlfaXRlcmF0b3IgcHJldiA9IHN0ZDo6cHJldihtaWQpOwoJCQlpZiAobmV3cGl2b3QgIT0gcHJldikgewoJCQkJc3dhcCgqbmV3cGl2b3QsICpwcmV2KTsKCQkJCS8vYW5kIGNhY2hlZCB0aGUgZW5kY2h1bmsgc2luY2Ugd2Uga25vdyBpdCBhbHJlYWR5CgkJCQllbmRjaHVuayA9IG1pZDsKCQkJCWNhY2hlZF9lbmQgPSB0cnVlOwoJCQl9IGVsc2UKCQkJCWNhY2hlZF9lbmQgPSBmYWxzZTsKCQkJLy9hbmQgInJlcGVhdCIgd2hpY2ggd2lsbCBkbyB0aGUgbGVmdCBzaWRlCgkJfQoJfSB3aGlsZShiZWdpbmNodW5rICE9IGxhc3QpOwoJYXNzZXJ0KHN0ZDo6aXNfc29ydGVkKGZpcnN0LCBsYXN0LCBwcmVkKSk7CglyZXR1cm47Cn0KCnRlbXBsYXRlPGNsYXNzIGJpZGlfaXRlcmF0b3I+CnZvaWQgaW5wbGFjZV9zb3J0KGJpZGlfaXRlcmF0b3IgYmVnaW4sIGJpZGlfaXRlcmF0b3IgZW5kKSB7Cgl0eXBlZGVmIHR5cGVuYW1lIHN0ZDo6aXRlcmF0b3JfdHJhaXRzPGJpZGlfaXRlcmF0b3I+Ojp2YWx1ZV90eXBlIHZhbHVlX3R5cGU7CglyZXR1cm4gaW5wbGFjZV9zb3J0KGJlZ2luLCBlbmQsIHN0ZDo6bGVzczx2YWx1ZV90eXBlPigpKTsKfQoKI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxjdGltZT4KI2luY2x1ZGUgPHZlY3Rvcj4KCnRlbXBsYXRlIDx0eXBlbmFtZSBUPgpzdHJ1Y3QgdHJhY2VyIDogc3RkOjpsZXNzPFQ+IHsKICAgIHN0YXRpYyB1bnNpZ25lZCBjb3VudDsKIAogICAgYm9vbCBvcGVyYXRvcigpKFQgeCwgVCB5KSBjb25zdCB7CiAgICAgICAgKytjb3VudDsKICAgICAgICByZXR1cm4gc3RkOjpsZXNzPFQ+OjpvcGVyYXRvcigpKHgsIHkpOwogICAgfQp9Owp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4KdW5zaWduZWQgdHJhY2VyPFQ+Ojpjb3VudCA9IDA7CiAKaW50IG1haW4oKSB7CiAgICAgICAgdW5zaWduZWQgdGVzdF9zaXplOwogICAgICAgIHdoaWxlKHN0ZDo6Y2luID4+IHRlc3Rfc2l6ZSkgeyAKCQkJZG91YmxlIHN0ZHNvcnRfdGltZT0wOwoJCQlkb3VibGUgaW5wbGFjZXNvcnRfdGltZT0wOwoJCQlzcmFuZCgodW5zaWduZWQpdGltZShOVUxMKSk7CgkJCXN0ZDo6dmVjdG9yPGludD4gZGF0YSh0ZXN0X3NpemUpOwoJCQlmb3IodW5zaWduZWQgaT0wOyBpPGRhdGEuc2l6ZSgpOyArK2kpCgkJCQkJZGF0YVtpXSA9IDEwMDAwK3JhbmQoKTsKCQkJc3RkOjp2ZWN0b3I8aW50PiBkYXRhMjsKCQkJewoJCQkJCWRhdGEyID0gZGF0YTsKCQkJCQlzdGQ6OnNvcnQoZGF0YTIuYmVnaW4oKSwgZGF0YTIuZW5kKCksIHRyYWNlcjxpbnQ+KCkpOwoJCQkJCWRhdGEyID0gZGF0YTsKCQkJCQljbG9ja190IGJlZ2luID0gY2xvY2soKTsKCQkJCQlzdGQ6OnNvcnQoZGF0YTIuYmVnaW4oKSwgZGF0YTIuZW5kKCkpOwoJCQkJCWNsb2NrX3QgZW5kID0gY2xvY2soKTsKCQkJCQlzdGRzb3J0X3RpbWUgPSBkb3VibGUoZW5kLWJlZ2luKS9DTE9DS1NfUEVSX1NFQzsKCQkJfQoJCQlzdGQ6OmNvdXQgPDwgImNvbXBhcmlzb25zOiAiIDw8IHRyYWNlcjxpbnQ+Ojpjb3VudCA8PCAnICc7CgkJCXN0ZDo6Y291dCA8PCAic3RkOjpzb3J0ICAgIHRvb2sgIiA8PCBzdGRzb3J0X3RpbWUgPDwgInMuXG4iOwoJCQl0cmFjZXI8aW50Pjo6Y291bnQgPSAwOwoJCQl7CgkJCQkJZGF0YTIgPSBkYXRhOwoJCQkJCXF1aWNrX3NvcnQoZGF0YTIuYmVnaW4oKSwgZGF0YTIuZW5kKCksIHRyYWNlcjxpbnQ+KCkpOwoJCQkJCWRhdGEyID0gZGF0YTsKCQkJCQljbG9ja190IGJlZ2luID0gY2xvY2soKTsKCQkJCQlxdWlja19zb3J0KGRhdGEyLmJlZ2luKCksIGRhdGEyLmVuZCgpKTsKCQkJCQljbG9ja190IGVuZCA9IGNsb2NrKCk7CgkJCQkJc3Rkc29ydF90aW1lID0gZG91YmxlKGVuZC1iZWdpbikvQ0xPQ0tTX1BFUl9TRUM7CgkJCX0KCQkJc3RkOjpjb3V0IDw8ICJjb21wYXJpc29uczogIiA8PCB0cmFjZXI8aW50Pjo6Y291bnQgPDwgJyAnOwoJCQlzdGQ6OmNvdXQgPDwgInF1aWNrc29ydCAgICB0b29rICIgPDwgc3Rkc29ydF90aW1lIDw8ICJzLlxuIjsKCQkJdHJhY2VyPGludD46OmNvdW50ID0gMDsKCQkJewoJCQkJCWRhdGEyID0gZGF0YTsKCQkJCQlpbnBsYWNlX3NvcnQoZGF0YTIuYmVnaW4oKSwgZGF0YTIuZW5kKCksIHRyYWNlcjxpbnQ+KCkpOwoJCQkJCWRhdGEyID0gZGF0YTsKCQkJCQljbG9ja190IGJlZ2luID0gY2xvY2soKTsKCQkJCQlpbnBsYWNlX3NvcnQoZGF0YTIuYmVnaW4oKSwgZGF0YTIuZW5kKCkpOwoJCQkJCWNsb2NrX3QgZW5kID0gY2xvY2soKTsKCQkJCQlpbnBsYWNlc29ydF90aW1lID0gZG91YmxlKGVuZC1iZWdpbikvQ0xPQ0tTX1BFUl9TRUM7CgkJCX0KCQkJc3RkOjpjb3V0IDw8ICJjb21wYXJpc29uczogIiA8PCB0cmFjZXI8aW50Pjo6Y291bnQgPDwgJyAnOwoJCQlzdGQ6OmNvdXQgPDwgImlucGxhY2Vfc29ydCB0b29rICIgPDwgaW5wbGFjZXNvcnRfdGltZSA8PCAicy5cbiI7CgkJfQogICAgICAgIHJldHVybiAwOwp9CiAK