/* Authors: Vu Hoang Bach from Phuoc Hoa Secondary School */
/* Enjoy TheFatRat's music while reading my code. Link: https://w...content-available-to-author-only...e.com/watch?v=GCx9FU59FJc&t=669s */
//#pragma GCC optimize("O3", "unroll-loops")
//#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
#include <bits/stdc++.h>
#define ldb long double
//#define double ldb
#define db double
#define name "test"
#define unomap unordered_map
#define unoset unordered_set
#define endl '\n'
#define str string
#define strstr stringstream
#define sz(a) a.size()
#define ll long long
//#define int ll
#define pii pair <int, int>
#define pll pair <ll, ll>
#define Unique(a) a.resize(unique(all(a)) - a.begin())
#define ull unsigned ll
#define fir first
#define sec second
#define idc cin.ignore()
#define lb lower_bound
#define ub upper_bound
#define all(s) s.begin(), s.end()
#define rev reverse
#define sigma ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define skibidi int main
#define rizz signed main
#define gcd __gcd
#define found(a, mp) mp.find(a) != mp.end()
#define game_over exit(0);
#define stfu return 0;
#define stop break;
#define odd(n) n & 1
#define pushb push_back
#define popb pop_back
#define pushf push_front
#define popf pop_front
#define even(n) !odd(n)
#define mul2x(a, x) a << x
#define div2x(a, x) a >> x
#define no_check continue;
#define lcm(a, b) a / __gcd(a, b) * b
#define log_base(x, base) log(x) / log(base)
#define debug clog << "No errors!"; game_over;
#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 meme memset
#define pqueue priority_queue
#define want(x) cout << fixed << setprecision(x);
using namespace std;
const int MOD = 1e9 + 7; // 998244353
const int inf = 1e9;
const ll INF = 1e18;
const int N = 2e5;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(const ll &L, const ll &R)
{
return uniform_int_distribution<ll> (L, R) (rng);
}
void cook()
{
}
skibidi()
//rizz()
{
srand(time(NULL));
sigma;
/*
if (fopen(name".INP", "r"))
{
freopen(name".INP", "r", stdin);
freopen(name".OUT", "w", stdout);
}
*/
int numTest = 1;
// cin >> numTest;
while (numTest--)
{
cook();
}
stfu;
}
LyogQXV0aG9yczogVnUgSG9hbmcgQmFjaCBmcm9tIFBodW9jIEhvYSBTZWNvbmRhcnkgU2Nob29sICovCi8qIEVuam95IFRoZUZhdFJhdCdzIG11c2ljIHdoaWxlIHJlYWRpbmcgbXkgY29kZS4gTGluazogaHR0cHM6Ly93Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLmNvbS93YXRjaD92PUdDeDlGVTU5RkpjJnQ9NjY5cyAqLwoKLy8jcHJhZ21hIEdDQyBvcHRpbWl6ZSgiTzMiLCAidW5yb2xsLWxvb3BzIikKLy8jcHJhZ21hIEdDQyB0YXJnZXQoImF2eDIiLCAiYm1pIiwgImJtaTIiLCAibHpjbnQiLCAicG9wY250IikKCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIGxkYiBsb25nIGRvdWJsZQovLyNkZWZpbmUgZG91YmxlIGxkYgojZGVmaW5lIGRiIGRvdWJsZQojZGVmaW5lIG5hbWUgInRlc3QiCiNkZWZpbmUgdW5vbWFwIHVub3JkZXJlZF9tYXAKI2RlZmluZSB1bm9zZXQgdW5vcmRlcmVkX3NldAojZGVmaW5lIGVuZGwgJ1xuJwojZGVmaW5lIHN0ciBzdHJpbmcKI2RlZmluZSBzdHJzdHIgc3RyaW5nc3RyZWFtCiNkZWZpbmUgc3ooYSkgYS5zaXplKCkKI2RlZmluZSBsbCBsb25nIGxvbmcKLy8jZGVmaW5lIGludCBsbAojZGVmaW5lIHBpaSBwYWlyIDxpbnQsIGludD4KI2RlZmluZSBwbGwgcGFpciA8bGwsIGxsPgojZGVmaW5lIFVuaXF1ZShhKSBhLnJlc2l6ZSh1bmlxdWUoYWxsKGEpKSAtIGEuYmVnaW4oKSkKI2RlZmluZSB1bGwgdW5zaWduZWQgbGwKI2RlZmluZSBmaXIgZmlyc3QKI2RlZmluZSBzZWMgc2Vjb25kCiNkZWZpbmUgaWRjIGNpbi5pZ25vcmUoKQojZGVmaW5lIGxiIGxvd2VyX2JvdW5kCiNkZWZpbmUgdWIgdXBwZXJfYm91bmQKI2RlZmluZSBhbGwocykgcy5iZWdpbigpLCBzLmVuZCgpCiNkZWZpbmUgcmV2IHJldmVyc2UKI2RlZmluZSBzaWdtYSBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApLCBjaW4udGllKDApLCBjb3V0LnRpZSgwKTsKI2RlZmluZSBza2liaWRpIGludCBtYWluCiNkZWZpbmUgcml6eiBzaWduZWQgbWFpbgojZGVmaW5lIGdjZCBfX2djZAojZGVmaW5lIGZvdW5kKGEsIG1wKSBtcC5maW5kKGEpICE9IG1wLmVuZCgpCiNkZWZpbmUgZ2FtZV9vdmVyIGV4aXQoMCk7CiNkZWZpbmUgc3RmdSByZXR1cm4gMDsKI2RlZmluZSBzdG9wIGJyZWFrOwojZGVmaW5lIG9kZChuKSBuICYgMQojZGVmaW5lIHB1c2hiIHB1c2hfYmFjawojZGVmaW5lIHBvcGIgcG9wX2JhY2sKI2RlZmluZSBwdXNoZiBwdXNoX2Zyb250CiNkZWZpbmUgcG9wZiBwb3BfZnJvbnQKI2RlZmluZSBldmVuKG4pICFvZGQobikKI2RlZmluZSBtdWwyeChhLCB4KSBhIDw8IHgKI2RlZmluZSBkaXYyeChhLCB4KSBhID4+IHgKI2RlZmluZSBub19jaGVjayBjb250aW51ZTsKI2RlZmluZSBsY20oYSwgYikgYSAvIF9fZ2NkKGEsIGIpICogYgojZGVmaW5lIGxvZ19iYXNlKHgsIGJhc2UpIGxvZyh4KSAvIGxvZyhiYXNlKQojZGVmaW5lIGRlYnVnIGNsb2cgPDwgIk5vIGVycm9ycyEiOyBnYW1lX292ZXI7CiNkZWZpbmUgZm9ydyhpLCBhLCBiKSBmb3IgKGludCBpID0gYTsgaSA8PSBiOyArK2kpCiNkZWZpbmUgZm9ydzIoaSwgYSwgYikgZm9yIChsbCBpID0gYTsgaSA8PSBiOyArK2kpCiNkZWZpbmUgZm9ycyhpLCBhLCBiKSBmb3IgKGludCBpID0gYTsgaSA+PSBiOyAtLWkpCiNkZWZpbmUgZm9yczIoaSwgYSwgYikgZm9yIChsbCBpID0gYTsgaSA+PSBiOyAtLWkpCiNkZWZpbmUgbWVtZSBtZW1zZXQKI2RlZmluZSBwcXVldWUgcHJpb3JpdHlfcXVldWUKI2RlZmluZSB3YW50KHgpIGNvdXQgPDwgZml4ZWQgPDwgc2V0cHJlY2lzaW9uKHgpOwp1c2luZyBuYW1lc3BhY2Ugc3RkOwpjb25zdCBpbnQgTU9EID0gMWU5ICsgNzsgLy8gOTk4MjQ0MzUzCmNvbnN0IGludCBpbmYgPSAxZTk7CmNvbnN0IGxsIElORiA9IDFlMTg7CmNvbnN0IGludCBOID0gMmU1OwoKbXQxOTkzN182NCBybmcoY2hyb25vOjpzdGVhZHlfY2xvY2s6Om5vdygpLnRpbWVfc2luY2VfZXBvY2goKS5jb3VudCgpKTsKbGwgcmFuZG9tKGNvbnN0IGxsICZMLCBjb25zdCBsbCAmUikKewogICAgcmV0dXJuIHVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjxsbD4gKEwsIFIpIChybmcpOwp9Cgp2b2lkIGNvb2soKQp7Cgp9Cgpza2liaWRpKCkKLy9yaXp6KCkKewogICAgc3JhbmQodGltZShOVUxMKSk7CiAgICBzaWdtYTsKICAgIC8qCiAgICBpZiAoZm9wZW4obmFtZSIuSU5QIiwgInIiKSkKICAgIHsKICAgICAgICBmcmVvcGVuKG5hbWUiLklOUCIsICJyIiwgc3RkaW4pOwogICAgICAgIGZyZW9wZW4obmFtZSIuT1VUIiwgInciLCBzdGRvdXQpOwogICAgfQogICAgKi8KICAgIGludCBudW1UZXN0ID0gMTsKLy8gICAgY2luID4+IG51bVRlc3Q7CiAgICB3aGlsZSAobnVtVGVzdC0tKQogICAgewogICAgICAgIGNvb2soKTsKICAgIH0KICAgIHN0ZnU7Cn0K