//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
//#define int ll
#define endl '\n'
#define unoset unordered_set
#define unomap unordered_map
#define strstr stringstream
#define SZ(a) (int)a.size()
#define Unique(a) a.resize(unique(all(a)) - a.begin())
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define rev reverse
#define gcd __gcd
#define pushb push_back
#define popb pop_back
#define pushf push_front
#define popf pop_front
#define emp emplace
#define empb emplace_back
#define empf emplace_front
#define lcm(a, b) (a / __gcd(a, b) * b)
#define log_base(x, base) log(x) / log(base)
#define debug cerr<<"No errors!",exit(0);
#define forw(i, a, b) for (int i = a; i <= b; ++i)
#define forw2(i, a, b) for (ll i = a; i <= b; ++i)
#define fors(i, a, b) for (int i = a; i >= b; --i)
#define fors2(i, a, b) for (ll i = a; i >= b; --i)
#define pqueue priority_queue
#define sqrt sqrtl
#define i128 __int128
#define popcount __builtin_popcountll
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1LL) << (x))
#define want_digit(x) cout << fixed << setprecision(x);
#define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
#define mapa make_pair
#define ms(a, x) memset(a, x, sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
typedef string str;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MOD = 1e9 + 7; // 998244353
const int inf = 1e9;
const ll INF = 1e18; // MASK(63) - 1
const int limN = 1e5 + 5;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll random(const ll &L, const ll &R) {
return uniform_int_distribution<ll> (L, R) (rng);
}
/* -------~~~~~~===== END OF TEMPLATE =====~~~~~~------- */
void solve() {
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
#define name "test"
if (fopen(name".INP", "r")) {
freopen(name".INP", "r", stdin);
freopen(name".OUT", "w", stdout);
}
bool testCase = false;
int numTest = 1;
// cin >> numTest;
forw (i, 1, numTest) {
if (testCase) cout << "Case #" << i << ": ";
solve();
}
return 0;
}
/*
≽(•⩊ •マ≼
Ɲyαɦ~!
*/
Ly8jcHJhZ21hIEdDQyBvcHRpbWl6ZSgiTzMsdW5yb2xsLWxvb3BzIikKLy8jcHJhZ21hIEdDQyB0YXJnZXQoImF2eDIsYm1pLGJtaTIsbHpjbnQscG9wY250IikKCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8jZGVmaW5lIGludCBsbAojZGVmaW5lIGVuZGwgJ1xuJwojZGVmaW5lIHVub3NldCB1bm9yZGVyZWRfc2V0CiNkZWZpbmUgdW5vbWFwIHVub3JkZXJlZF9tYXAKI2RlZmluZSBzdHJzdHIgc3RyaW5nc3RyZWFtCiNkZWZpbmUgU1ooYSkgKGludClhLnNpemUoKQojZGVmaW5lIFVuaXF1ZShhKSBhLnJlc2l6ZSh1bmlxdWUoYWxsKGEpKSAtIGEuYmVnaW4oKSkKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIGxiIGxvd2VyX2JvdW5kCiNkZWZpbmUgdWIgdXBwZXJfYm91bmQKI2RlZmluZSBhbGwocykgcy5iZWdpbigpLCBzLmVuZCgpCiNkZWZpbmUgcmFsbChzKSBzLnJiZWdpbigpLCBzLnJlbmQoKQojZGVmaW5lIHJldiByZXZlcnNlCiNkZWZpbmUgZ2NkIF9fZ2NkCiNkZWZpbmUgcHVzaGIgcHVzaF9iYWNrCiNkZWZpbmUgcG9wYiBwb3BfYmFjawojZGVmaW5lIHB1c2hmIHB1c2hfZnJvbnQKI2RlZmluZSBwb3BmIHBvcF9mcm9udAojZGVmaW5lIGVtcCBlbXBsYWNlCiNkZWZpbmUgZW1wYiBlbXBsYWNlX2JhY2sKI2RlZmluZSBlbXBmIGVtcGxhY2VfZnJvbnQKI2RlZmluZSBsY20oYSwgYikgKGEgLyBfX2djZChhLCBiKSAqIGIpCiNkZWZpbmUgbG9nX2Jhc2UoeCwgYmFzZSkgbG9nKHgpIC8gbG9nKGJhc2UpCiNkZWZpbmUgZGVidWcgY2Vycjw8Ik5vIGVycm9ycyEiLGV4aXQoMCk7CiNkZWZpbmUgZm9ydyhpLCBhLCBiKSAgZm9yIChpbnQgaSA9IGE7IGkgPD0gYjsgKytpKQojZGVmaW5lIGZvcncyKGksIGEsIGIpIGZvciAobGwgaSA9IGE7IGkgPD0gYjsgKytpKQojZGVmaW5lIGZvcnMoaSwgYSwgYikgIGZvciAoaW50IGkgPSBhOyBpID49IGI7IC0taSkKI2RlZmluZSBmb3JzMihpLCBhLCBiKSBmb3IgKGxsIGkgPSBhOyBpID49IGI7IC0taSkKI2RlZmluZSBwcXVldWUgcHJpb3JpdHlfcXVldWUKI2RlZmluZSBzcXJ0IHNxcnRsCiNkZWZpbmUgaTEyOCBfX2ludDEyOAojZGVmaW5lIHBvcGNvdW50IF9fYnVpbHRpbl9wb3Bjb3VudGxsCiNkZWZpbmUgQklUKHgsIGkpICgoKHgpID4+IChpKSkgJiAxKQojZGVmaW5lIE1BU0soeCkgKCgxTEwpIDw8ICh4KSkKI2RlZmluZSB3YW50X2RpZ2l0KHgpIGNvdXQgPDwgZml4ZWQgPDwgc2V0cHJlY2lzaW9uKHgpOwojZGVmaW5lIGV4Y3V0aW5nX3RpbWUgMTAwMC4wICogY2xvY2soKSAvIENMT0NLU19QRVJfU0VDCiNkZWZpbmUgbWFwYSBtYWtlX3BhaXIKI2RlZmluZSBtcyhhLCB4KSBtZW1zZXQoYSwgeCwgc2l6ZW9mKGEpKQoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKdHlwZWRlZiBsb25nIGRvdWJsZSBsZGI7CnR5cGVkZWYgZG91YmxlIGRiOwp0eXBlZGVmIHN0cmluZyBzdHI7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gcGlpOwp0eXBlZGVmIHBhaXI8bGwsIGxsPiBwbGw7Cgpjb25zdCBpbnQgTU9EID0gMWU5ICsgNzsgLy8gOTk4MjQ0MzUzCmNvbnN0IGludCBpbmYgPSAxZTk7CmNvbnN0IGxsIElORiA9IDFlMTg7IC8vIE1BU0soNjMpIC0gMQpjb25zdCBpbnQgbGltTiA9IDFlNSArIDU7CgptdDE5OTM3XzY0IHJuZyhjaHJvbm86OnN0ZWFkeV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCkpOwppbmxpbmUgbGwgcmFuZG9tKGNvbnN0IGxsICZMLCBjb25zdCBsbCAmUikgewogICAgcmV0dXJuIHVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjxsbD4gKEwsIFIpIChybmcpOwp9CgovKiAtLS0tLS0tfn5+fn5+PT09PT0gRU5EIE9GIFRFTVBMQVRFID09PT09fn5+fn5+LS0tLS0tLSAqLwoKdm9pZCBzb2x2ZSgpIHsKCn0KCnNpZ25lZCBtYWluKCkgewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpLCBjaW4udGllKG51bGxwdHIpOwogICAgI2RlZmluZSBuYW1lICJ0ZXN0IgogICAgaWYgKGZvcGVuKG5hbWUiLklOUCIsICJyIikpIHsKICAgICAgICBmcmVvcGVuKG5hbWUiLklOUCIsICJyIiwgc3RkaW4pOwogICAgICAgIGZyZW9wZW4obmFtZSIuT1VUIiwgInciLCBzdGRvdXQpOwogICAgfQogICAgYm9vbCB0ZXN0Q2FzZSA9IGZhbHNlOwogICAgaW50IG51bVRlc3QgPSAxOwogICAgLy8gY2luID4+IG51bVRlc3Q7CiAgICBmb3J3IChpLCAxLCBudW1UZXN0KSB7CiAgICAgICAgaWYgKHRlc3RDYXNlKSBjb3V0IDw8ICJDYXNlICMiIDw8IGkgPDwgIjogIjsKICAgICAgICBzb2x2ZSgpOwogICAgfQogICAgcmV0dXJuIDA7Cn0KCi8qCuKJvSjigKLiqYog4oCi44Oe4om8Csadec6xyaZ+IQoqLwoK