#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = (1 << 20);
template <class T>
struct fenwick
{
int sz;
vector<T> tr;
void init(int n)
{
sz = n + 1;
tr.assign(sz + 2, 0);
}
T query(int idx)
{
T ans = 0;
for(; idx >= 1; idx -= (idx & -idx))
ans += tr[idx];
return ans;
}
void update(int idx, T val)
{
if(idx <= 0) return;
for(; idx <= sz; idx += (idx & -idx))
tr[idx] += val;
}
T query(int l, int r) { return query(r) - query(l - 1); }
};
template<class T>
struct compressed_fenwick
{
fenwick<T> t;
vector<int> li;
int get_idx(int x) { return lower_bound(li.begin(), li.end(), x) - li.begin() + 1; }
void update(int x, T val) { t.update(get_idx(x), val); }
void add_to_prep(int x) { li.push_back(x); }
void prepare()
{
sort(li.begin(), li.end());
li.erase(unique(li.begin(), li.end()), li.end());
t.init(li.size() + 2);
}
T query(int x) { return t.query(get_idx(x) - 1); }
T size() { return t.query(t.sz); }
};
void read()
{
}
void solve()
{
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
read();
solve();
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgZW5kbCAnXG4nCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpjb25zdCBpbnQgTUFYTiA9ICgxIDw8IDIwKTsKCnRlbXBsYXRlIDxjbGFzcyBUPgpzdHJ1Y3QgZmVud2ljawp7CglpbnQgc3o7Cgl2ZWN0b3I8VD4gdHI7CgoJdm9pZCBpbml0KGludCBuKQoJewoJCXN6ID0gbiArIDE7CgkJdHIuYXNzaWduKHN6ICsgMiwgMCk7Cgl9CgoJVCBxdWVyeShpbnQgaWR4KQoJewoJCVQgYW5zID0gMDsKCQlmb3IoOyBpZHggPj0gMTsgaWR4IC09IChpZHggJiAtaWR4KSkKCQkJYW5zICs9IHRyW2lkeF07CgkJcmV0dXJuIGFuczsKCX0KCgl2b2lkIHVwZGF0ZShpbnQgaWR4LCBUIHZhbCkKCXsKCQlpZihpZHggPD0gMCkgcmV0dXJuOwoJCWZvcig7IGlkeCA8PSBzejsgaWR4ICs9IChpZHggJiAtaWR4KSkKCQkJdHJbaWR4XSArPSB2YWw7Cgl9CgoJVCBxdWVyeShpbnQgbCwgaW50IHIpIHsgcmV0dXJuIHF1ZXJ5KHIpIC0gcXVlcnkobCAtIDEpOyB9Cn07Cgp0ZW1wbGF0ZTxjbGFzcyBUPgpzdHJ1Y3QgY29tcHJlc3NlZF9mZW53aWNrCnsKCWZlbndpY2s8VD4gdDsKCXZlY3RvcjxpbnQ+IGxpOwoKCWludCBnZXRfaWR4KGludCB4KSB7IHJldHVybiBsb3dlcl9ib3VuZChsaS5iZWdpbigpLCBsaS5lbmQoKSwgeCkgLSBsaS5iZWdpbigpICsgMTsgfQoJdm9pZCB1cGRhdGUoaW50IHgsIFQgdmFsKSB7IHQudXBkYXRlKGdldF9pZHgoeCksIHZhbCk7IH0KCgl2b2lkIGFkZF90b19wcmVwKGludCB4KSB7IGxpLnB1c2hfYmFjayh4KTsgfQoJdm9pZCBwcmVwYXJlKCkKCXsKCQlzb3J0KGxpLmJlZ2luKCksIGxpLmVuZCgpKTsKCQlsaS5lcmFzZSh1bmlxdWUobGkuYmVnaW4oKSwgbGkuZW5kKCkpLCBsaS5lbmQoKSk7CgkJdC5pbml0KGxpLnNpemUoKSArIDIpOwoJfQoKCVQgcXVlcnkoaW50IHgpIHsgcmV0dXJuIHQucXVlcnkoZ2V0X2lkeCh4KSAtIDEpOyB9CglUIHNpemUoKSB7IHJldHVybiB0LnF1ZXJ5KHQuc3opOyB9Cn07Cgp2b2lkIHJlYWQoKQp7Cgp9Cgp2b2lkIHNvbHZlKCkKewoKfQoKaW50IG1haW4oKQp7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWNpbi50aWUoTlVMTCk7CgoJcmVhZCgpOwoJc29sdmUoKTsKCXJldHVybiAwOwp9Cg==