#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("-O3", "Ofast", "unroll-loops")
#define whole(O) O.begin (), O.end ()
#define tS(O) (int) O.size ()
#define sqr(O) (O) * (O)
#define pw(O) (1LL << O)
using namespace std;
const long long Mod = 1e9 + 7;
const int MaXn = 5 * 1e5 + 1;
using namespace __gnu_pbds;
template <typename O>
using Ordered_Set = tree <O, null_type, less <O>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rnd(chrono :: system_clock :: now ().time_since_epoch ().count ());
int main () {
ios_base :: sync_with_stdio (0);
cin.tie (0); cout.tie (0);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+CiNpbmNsdWRlIDxleHQvcGJfZHMvdHJlZV9wb2xpY3kuaHBwPgoKI3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCItTzMiLCAiT2Zhc3QiLCAidW5yb2xsLWxvb3BzIikKCiNkZWZpbmUgd2hvbGUoTykgTy5iZWdpbiAoKSwgTy5lbmQgKCkKCiNkZWZpbmUgdFMoTykgKGludCkgTy5zaXplICgpCgojZGVmaW5lIHNxcihPKSAoTykgKiAoTykKI2RlZmluZSBwdyhPKSAoMUxMIDw8IE8pCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgbG9uZyBsb25nIE1vZCA9IDFlOSArIDc7CmNvbnN0IGludCBNYVhuID0gNSAqIDFlNSArIDE7Cgp1c2luZyBuYW1lc3BhY2UgX19nbnVfcGJkczsKCnRlbXBsYXRlIDx0eXBlbmFtZSBPPgp1c2luZyBPcmRlcmVkX1NldCA9IHRyZWUgPE8sIG51bGxfdHlwZSwgbGVzcyA8Tz4sIHJiX3RyZWVfdGFnLCB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+OwoKbXQxOTkzN182NCBybmQoY2hyb25vIDo6IHN5c3RlbV9jbG9jayA6OiBub3cgKCkudGltZV9zaW5jZV9lcG9jaCAoKS5jb3VudCAoKSk7CgppbnQgbWFpbiAoKSB7CgogICAgaW9zX2Jhc2UgOjogc3luY193aXRoX3N0ZGlvICgwKTsKICAgIGNpbi50aWUgKDApOyBjb3V0LnRpZSAoMCk7CgoKICAgIHJldHVybiAwOwp9Cg==