#include <algorithm>
#include <utility>
#include <iostream>
 
struct my_cmp
{
    bool operator()(unsigned char a, unsigned char b)
    {
        return a < b;
    }
};
 
struct my_cmp2
{
    bool operator()(unsigned char a, unsigned char b)
    {
        std::cerr << (int) a << ' ' << (int) b << '\n';
        return a < b;
    }
};
 
template<unsigned int Len>
struct reverse_if
{
    template<typename T, typename P>
    void operator()(T* a, P pred)
    {
        using std::swap;
        if (pred(*(a + Len - 1), *a)) swap(*a, *(a + Len - 1));
        reverse_if<Len - 2> rif;
        rif(a + 1, pred);
    }
};
 
template<>
struct reverse_if<0>
{
    template<typename T, typename P>
    void operator()(T* a, P pred) {}
};
 
 
template<unsigned int Len, unsigned int Count>
struct shift_swap_if_help
{
    template<typename T, typename P>
    void operator()(T* a, P pred)
    {
        using std::swap;
        if (pred(*(a + Len), *a)) swap(*a, *(a + Len));
        shift_swap_if_help<Len, Count - 1> ssif;
        ssif(a + 1, pred);
    }
};
 
template<unsigned int Len>
struct shift_swap_if_help<Len, 0>
{
    template<typename T, typename P>
    void operator()(T* a, P Pred) {}
};
 
template<unsigned int Len>
struct shift_swap_if
{
    template<typename T, typename P>
    void operator()(T* a, P pred)
    {
        shift_swap_if_help<Len, Len> ssif;
        ssif(a, pred);
    }
};
 
template<unsigned int Len>
struct shift_chain
{
    template<typename T, typename P>
    void operator()(T* a, P pred)
    {
        shift_swap_if<Len/2> ssif;
        ssif(a, pred);
 
        shift_chain<Len / 2> upper;
        shift_chain<Len / 2> lower;
        upper(a, pred);
        lower(a + Len/2, pred);
    }
};
 
template<>
struct shift_chain<0>
{
    template<typename T, typename P>
    void operator()(T* a, P pred) {}
};
 
template<unsigned int Len>
struct block
{
    template<typename T, typename P>
    void operator()(T* a, P pred)
    {
        reverse_if<Len> rif;
        rif(a, pred);
 
        shift_chain<Len / 2> upper;
        shift_chain<Len / 2> lower;
        upper(a, pred);
        lower(a + Len/2, pred);
    }
};
 
template<unsigned int Depth>
struct bitonic_sort
{
 
    template<typename T, typename P>
    void operator()(T* a, P pred)
    {
        bitonic_sort<Depth / 2> upper;
        bitonic_sort<Depth / 2> lower;
        upper(a, pred);
        lower(a + (Depth / 2), pred);
 
        block<Depth> blk;
        blk(a, pred);
    }
};
 
template<>
struct bitonic_sort<1>
{
 
    template<typename T, typename P>
    void operator()(T* a, P pred) {}
};
 
template<unsigned int Len>
void test_bitonic(unsigned int idx)
{
    unsigned char a[Len];
    for (auto& e : a) e = 0;
    a[idx] = 1;
 
    for (auto e : a) std::cerr << (int) e << ' ';
    std::cerr << " ->  ";
 
    bitonic_sort<Len> bsort;
    bsort(a, my_cmp{});
 
    for (auto e : a) std::cerr << (int) e << ' ';
    std::cerr << '\n';
}
 
template<unsigned int Len>
void test_bitonic_index()
{
    unsigned char a[Len];
    for (unsigned int i = 0; i < Len; ++i)
        a[i] = i;
 
    for (auto e : a) std::cerr << (int) e << ' ';
    std::cerr << " ->  ";
 
    bitonic_sort<Len> bsort;
    bsort(a, my_cmp2{});
 
    for (auto e : a) std::cerr << (int) e << ' ';
    std::cerr << '\n';
}
 
 
 
int main()
{
    //test_bitonic<4>(2);
    //std::cerr << '\n';
    //test_bitonic_index<4>();
 
    test_bitonic<1>(0);
 
    std::cerr << '\n';
 
    test_bitonic<2>(0);
    test_bitonic<2>(1);
 
    std::cerr << '\n';
 
    for(unsigned int i = 0; i < 4; ++i)
        test_bitonic<4>(i);
    std::cerr << '\n';
 
    for(unsigned int i = 0; i < 8; ++i)
        test_bitonic<8>(i);
    std::cerr << '\n';
 
    for(unsigned int i = 0; i < 16; ++i)
        test_bitonic<16>(i);
    std::cerr << '\n';
 
    return 0;
}

I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxpb3N0cmVhbT4KCnN0cnVjdCBteV9jbXAKewogICAgYm9vbCBvcGVyYXRvcigpKHVuc2lnbmVkIGNoYXIgYSwgdW5zaWduZWQgY2hhciBiKQogICAgewogICAgICAgIHJldHVybiBhIDwgYjsKICAgIH0KfTsKCnN0cnVjdCBteV9jbXAyCnsKICAgIGJvb2wgb3BlcmF0b3IoKSh1bnNpZ25lZCBjaGFyIGEsIHVuc2lnbmVkIGNoYXIgYikKICAgIHsKICAgICAgICBzdGQ6OmNlcnIgPDwgKGludCkgYSA8PCAnICcgPDwgKGludCkgYiA8PCAnXG4nOwogICAgICAgIHJldHVybiBhIDwgYjsKICAgIH0KfTsKCnRlbXBsYXRlPHVuc2lnbmVkIGludCBMZW4+CnN0cnVjdCByZXZlcnNlX2lmCnsKICAgIHRlbXBsYXRlPHR5cGVuYW1lIFQsIHR5cGVuYW1lIFA+CiAgICB2b2lkIG9wZXJhdG9yKCkoVCogYSwgUCBwcmVkKQogICAgewogICAgICAgIHVzaW5nIHN0ZDo6c3dhcDsKICAgICAgICBpZiAocHJlZCgqKGEgKyBMZW4gLSAxKSwgKmEpKSBzd2FwKCphLCAqKGEgKyBMZW4gLSAxKSk7CiAgICAgICAgcmV2ZXJzZV9pZjxMZW4gLSAyPiByaWY7CiAgICAgICAgcmlmKGEgKyAxLCBwcmVkKTsKICAgIH0KfTsKCnRlbXBsYXRlPD4Kc3RydWN0IHJldmVyc2VfaWY8MD4KewogICAgdGVtcGxhdGU8dHlwZW5hbWUgVCwgdHlwZW5hbWUgUD4KICAgIHZvaWQgb3BlcmF0b3IoKShUKiBhLCBQIHByZWQpIHt9Cn07CgoKdGVtcGxhdGU8dW5zaWduZWQgaW50IExlbiwgdW5zaWduZWQgaW50IENvdW50PgpzdHJ1Y3Qgc2hpZnRfc3dhcF9pZl9oZWxwCnsKICAgIHRlbXBsYXRlPHR5cGVuYW1lIFQsIHR5cGVuYW1lIFA+CiAgICB2b2lkIG9wZXJhdG9yKCkoVCogYSwgUCBwcmVkKQogICAgewogICAgICAgIHVzaW5nIHN0ZDo6c3dhcDsKICAgICAgICBpZiAocHJlZCgqKGEgKyBMZW4pLCAqYSkpIHN3YXAoKmEsICooYSArIExlbikpOwogICAgICAgIHNoaWZ0X3N3YXBfaWZfaGVscDxMZW4sIENvdW50IC0gMT4gc3NpZjsKICAgICAgICBzc2lmKGEgKyAxLCBwcmVkKTsKICAgIH0KfTsKCnRlbXBsYXRlPHVuc2lnbmVkIGludCBMZW4+CnN0cnVjdCBzaGlmdF9zd2FwX2lmX2hlbHA8TGVuLCAwPgp7CiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBULCB0eXBlbmFtZSBQPgogICAgdm9pZCBvcGVyYXRvcigpKFQqIGEsIFAgUHJlZCkge30KfTsKCnRlbXBsYXRlPHVuc2lnbmVkIGludCBMZW4+CnN0cnVjdCBzaGlmdF9zd2FwX2lmCnsKICAgIHRlbXBsYXRlPHR5cGVuYW1lIFQsIHR5cGVuYW1lIFA+CiAgICB2b2lkIG9wZXJhdG9yKCkoVCogYSwgUCBwcmVkKQogICAgewogICAgICAgIHNoaWZ0X3N3YXBfaWZfaGVscDxMZW4sIExlbj4gc3NpZjsKICAgICAgICBzc2lmKGEsIHByZWQpOwogICAgfQp9OwoKdGVtcGxhdGU8dW5zaWduZWQgaW50IExlbj4Kc3RydWN0IHNoaWZ0X2NoYWluCnsKICAgIHRlbXBsYXRlPHR5cGVuYW1lIFQsIHR5cGVuYW1lIFA+CiAgICB2b2lkIG9wZXJhdG9yKCkoVCogYSwgUCBwcmVkKQogICAgewogICAgICAgIHNoaWZ0X3N3YXBfaWY8TGVuLzI+IHNzaWY7CiAgICAgICAgc3NpZihhLCBwcmVkKTsKCiAgICAgICAgc2hpZnRfY2hhaW48TGVuIC8gMj4gdXBwZXI7CiAgICAgICAgc2hpZnRfY2hhaW48TGVuIC8gMj4gbG93ZXI7CiAgICAgICAgdXBwZXIoYSwgcHJlZCk7CiAgICAgICAgbG93ZXIoYSArIExlbi8yLCBwcmVkKTsKICAgIH0KfTsKCnRlbXBsYXRlPD4Kc3RydWN0IHNoaWZ0X2NoYWluPDA+CnsKICAgIHRlbXBsYXRlPHR5cGVuYW1lIFQsIHR5cGVuYW1lIFA+CiAgICB2b2lkIG9wZXJhdG9yKCkoVCogYSwgUCBwcmVkKSB7fQp9OwoKdGVtcGxhdGU8dW5zaWduZWQgaW50IExlbj4Kc3RydWN0IGJsb2NrCnsKICAgIHRlbXBsYXRlPHR5cGVuYW1lIFQsIHR5cGVuYW1lIFA+CiAgICB2b2lkIG9wZXJhdG9yKCkoVCogYSwgUCBwcmVkKQogICAgewogICAgICAgIHJldmVyc2VfaWY8TGVuPiByaWY7CiAgICAgICAgcmlmKGEsIHByZWQpOwoKICAgICAgICBzaGlmdF9jaGFpbjxMZW4gLyAyPiB1cHBlcjsKICAgICAgICBzaGlmdF9jaGFpbjxMZW4gLyAyPiBsb3dlcjsKICAgICAgICB1cHBlcihhLCBwcmVkKTsKICAgICAgICBsb3dlcihhICsgTGVuLzIsIHByZWQpOwogICAgfQp9OwoKdGVtcGxhdGU8dW5zaWduZWQgaW50IERlcHRoPgpzdHJ1Y3QgYml0b25pY19zb3J0CnsKCiAgICB0ZW1wbGF0ZTx0eXBlbmFtZSBULCB0eXBlbmFtZSBQPgogICAgdm9pZCBvcGVyYXRvcigpKFQqIGEsIFAgcHJlZCkKICAgIHsKICAgICAgICBiaXRvbmljX3NvcnQ8RGVwdGggLyAyPiB1cHBlcjsKICAgICAgICBiaXRvbmljX3NvcnQ8RGVwdGggLyAyPiBsb3dlcjsKICAgICAgICB1cHBlcihhLCBwcmVkKTsKICAgICAgICBsb3dlcihhICsgKERlcHRoIC8gMiksIHByZWQpOwoKICAgICAgICBibG9jazxEZXB0aD4gYmxrOwogICAgICAgIGJsayhhLCBwcmVkKTsKICAgIH0KfTsKCnRlbXBsYXRlPD4Kc3RydWN0IGJpdG9uaWNfc29ydDwxPgp7CgogICAgdGVtcGxhdGU8dHlwZW5hbWUgVCwgdHlwZW5hbWUgUD4KICAgIHZvaWQgb3BlcmF0b3IoKShUKiBhLCBQIHByZWQpIHt9Cn07Cgp0ZW1wbGF0ZTx1bnNpZ25lZCBpbnQgTGVuPgp2b2lkIHRlc3RfYml0b25pYyh1bnNpZ25lZCBpbnQgaWR4KQp7CiAgICB1bnNpZ25lZCBjaGFyIGFbTGVuXTsKICAgIGZvciAoYXV0byYgZSA6IGEpIGUgPSAwOwogICAgYVtpZHhdID0gMTsKCiAgICBmb3IgKGF1dG8gZSA6IGEpIHN0ZDo6Y2VyciA8PCAoaW50KSBlIDw8ICcgJzsKICAgIHN0ZDo6Y2VyciA8PCAiIC0+ICAiOwoKICAgIGJpdG9uaWNfc29ydDxMZW4+IGJzb3J0OwogICAgYnNvcnQoYSwgbXlfY21we30pOwoKICAgIGZvciAoYXV0byBlIDogYSkgc3RkOjpjZXJyIDw8IChpbnQpIGUgPDwgJyAnOwogICAgc3RkOjpjZXJyIDw8ICdcbic7Cn0KCnRlbXBsYXRlPHVuc2lnbmVkIGludCBMZW4+CnZvaWQgdGVzdF9iaXRvbmljX2luZGV4KCkKewogICAgdW5zaWduZWQgY2hhciBhW0xlbl07CiAgICBmb3IgKHVuc2lnbmVkIGludCBpID0gMDsgaSA8IExlbjsgKytpKQogICAgICAgIGFbaV0gPSBpOwoKICAgIGZvciAoYXV0byBlIDogYSkgc3RkOjpjZXJyIDw8IChpbnQpIGUgPDwgJyAnOwogICAgc3RkOjpjZXJyIDw8ICIgLT4gICI7CgogICAgYml0b25pY19zb3J0PExlbj4gYnNvcnQ7CiAgICBic29ydChhLCBteV9jbXAye30pOwoKICAgIGZvciAoYXV0byBlIDogYSkgc3RkOjpjZXJyIDw8IChpbnQpIGUgPDwgJyAnOwogICAgc3RkOjpjZXJyIDw8ICdcbic7Cn0KCgoKaW50IG1haW4oKQp7CiAgICAvL3Rlc3RfYml0b25pYzw0PigyKTsKICAgIC8vc3RkOjpjZXJyIDw8ICdcbic7CiAgICAvL3Rlc3RfYml0b25pY19pbmRleDw0PigpOwoKICAgIHRlc3RfYml0b25pYzwxPigwKTsKCiAgICBzdGQ6OmNlcnIgPDwgJ1xuJzsKCiAgICB0ZXN0X2JpdG9uaWM8Mj4oMCk7CiAgICB0ZXN0X2JpdG9uaWM8Mj4oMSk7CgogICAgc3RkOjpjZXJyIDw8ICdcbic7CgogICAgZm9yKHVuc2lnbmVkIGludCBpID0gMDsgaSA8IDQ7ICsraSkKICAgICAgICB0ZXN0X2JpdG9uaWM8ND4oaSk7CiAgICBzdGQ6OmNlcnIgPDwgJ1xuJzsKCiAgICBmb3IodW5zaWduZWQgaW50IGkgPSAwOyBpIDwgODsgKytpKQogICAgICAgIHRlc3RfYml0b25pYzw4PihpKTsKICAgIHN0ZDo6Y2VyciA8PCAnXG4nOwoKICAgIGZvcih1bnNpZ25lZCBpbnQgaSA9IDA7IGkgPCAxNjsgKytpKQogICAgICAgIHRlc3RfYml0b25pYzwxNj4oaSk7CiAgICBzdGQ6OmNlcnIgPDwgJ1xuJzsKCiAgICByZXR1cm4gMDsKfQ==