// CODE__ANTI__MOSS
#include <bits/stdc++.h>
#define buffspeed ios_base::sync_with_stdio(false);\
cin.tie(0);\
cout.tie(0)
#define fopenn(tenfile) if(fopen(tenfile".inp","r")){\
freopen (tenfile".inp","r",stdin);\
freopen (tenfile".out","w",stdout);\
}
#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define compile (1.0 clock() / CLOCKS_PER_SEC)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse4,avx2,fma")
#define int long long
#define __DEPTRAIVCL__ signed main()
#define skibidi dopdop
using namespace std;
// SPEED GOD
/*
static struct FastInput {
static constexpr int BUF_SIZE = 1 << 20;
char buf[BUF_SIZE];
size_t chars_read = 0;
size_t buf_pos = 0;
FILE *in = stdin;
char cur = 0;
inline char get_char() {
if (buf_pos >= chars_read) {
chars_read = fread(buf, 1, BUF_SIZE, in);
buf_pos = 0;
buf[0] = (chars_read == 0 ? -1 : buf[0]);
}
return cur = buf[buf_pos++];
}
inline void tie(int) {}
inline explicit operator bool() {
return cur != -1;
}
inline static bool is_blank(char c) {
return c <= ' ';
}
inline bool skip_blanks() {
while (is_blank(cur) && cur != -1) {
get_char();
}
return cur != -1;
}
inline FastInput& operator>>(char& c) {
skip_blanks();
c = cur;
return *this;
}
inline FastInput& operator>>(string& s) {
if (skip_blanks()) {
s.clear();
do {
s += cur;
} while (!is_blank(get_char()));
}
return *this;
}
template <typename T>
inline FastInput& read_integer(T& n) {
n = 0;
if (skip_blanks()) {
int sign = +1;
if (cur == '-') {
sign = -1;
get_char();
}
do {
n += n + (n << 3) + cur - '0';
} while (!is_blank(get_char()));
n *= sign;
}
return *this;
}
template <typename T>
inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
return read_integer(n);
}
#if !defined(_WIN32) | defined(_WIN64)
inline FastInput& operator>>(__int128& n) {
return read_integer(n);
}
#endif
template <typename T>
inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
n = 0;
if (skip_blanks()) {
string s;
(*this) >> s;
sscanf(s.c_str(), "%lf", &n);
}
return *this;
}
} fast_input;
#define cin fast_input
*/
void skibidiinput(){
}
void AC(){
}
void skibidioutput(){
}
__DEPTRAIVCL__{
//skibidi
buffspeed;
fopenn("");
skibidiinput();
skibidioutput();
//🦆🦆🦆🦆
}
Ly8gQ09ERV9fQU5USV9fTU9TUwojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBidWZmc3BlZWQgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7XAogICAgICAgICAgICAgICAgICAgIGNpbi50aWUoMCk7XAogICAgICAgICAgICAgICAgICAgIGNvdXQudGllKDApCiNkZWZpbmUgZm9wZW5uKHRlbmZpbGUpIGlmKGZvcGVuKHRlbmZpbGUiLmlucCIsInIiKSl7XAogICAgICAgICAgICAgICAgICAgICAgICAgICAgZnJlb3BlbiAodGVuZmlsZSIuaW5wIiwiciIsc3RkaW4pO1wKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZyZW9wZW4gKHRlbmZpbGUiLm91dCIsInciLHN0ZG91dCk7XAogICAgICAgICAgICAgICAgICAgICAgICB9CiNwcmFnbWEgR0NDIG9wdGltaXplKCJPMyx1bnJvbGwtbG9vcHMsbm8tc3RhY2stcHJvdGVjdG9yIikKI3ByYWdtYSBHQ0MgdGFyZ2V0KCJhdngyLGJtaSxibWkyLGx6Y250LHBvcGNudCIpCiNkZWZpbmUgY29tcGlsZSAoMS4wIGNsb2NrKCkgLyBDTE9DS1NfUEVSX1NFQykKI3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk8zLHVucm9sbC1sb29wcyIpCiNwcmFnbWEgR0NDIHRhcmdldCgic3NlNCxhdngyLGZtYSIpCiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIF9fREVQVFJBSVZDTF9fIHNpZ25lZCBtYWluKCkKI2RlZmluZSBza2liaWRpIGRvcGRvcAp1c2luZyBuYW1lc3BhY2Ugc3RkOwovLyBTUEVFRCBHT0QKLyoKc3RhdGljIHN0cnVjdCBGYXN0SW5wdXQgewogIHN0YXRpYyBjb25zdGV4cHIgaW50IEJVRl9TSVpFID0gMSA8PCAyMDsKICBjaGFyIGJ1ZltCVUZfU0laRV07CiAgc2l6ZV90IGNoYXJzX3JlYWQgPSAwOwogIHNpemVfdCBidWZfcG9zID0gMDsKICBGSUxFICppbiA9IHN0ZGluOwogIGNoYXIgY3VyID0gMDsKCiAgaW5saW5lIGNoYXIgZ2V0X2NoYXIoKSB7CiAgICBpZiAoYnVmX3BvcyA+PSBjaGFyc19yZWFkKSB7CiAgICAgIGNoYXJzX3JlYWQgPSBmcmVhZChidWYsIDEsIEJVRl9TSVpFLCBpbik7CiAgICAgIGJ1Zl9wb3MgPSAwOwogICAgICBidWZbMF0gPSAoY2hhcnNfcmVhZCA9PSAwID8gLTEgOiBidWZbMF0pOwogICAgfQogICAgcmV0dXJuIGN1ciA9IGJ1ZltidWZfcG9zKytdOwogIH0KCiAgaW5saW5lIHZvaWQgdGllKGludCkge30KCiAgaW5saW5lIGV4cGxpY2l0IG9wZXJhdG9yIGJvb2woKSB7CiAgICByZXR1cm4gY3VyICE9IC0xOwogIH0KCiAgaW5saW5lIHN0YXRpYyBib29sIGlzX2JsYW5rKGNoYXIgYykgewogICAgcmV0dXJuIGMgPD0gJyAnOwogIH0KCiAgaW5saW5lIGJvb2wgc2tpcF9ibGFua3MoKSB7CiAgICB3aGlsZSAoaXNfYmxhbmsoY3VyKSAmJiBjdXIgIT0gLTEpIHsKICAgICAgZ2V0X2NoYXIoKTsKICAgIH0KICAgIHJldHVybiBjdXIgIT0gLTE7CiAgfQoKICBpbmxpbmUgRmFzdElucHV0JiBvcGVyYXRvcj4+KGNoYXImIGMpIHsKICAgIHNraXBfYmxhbmtzKCk7CiAgICBjID0gY3VyOwogICAgcmV0dXJuICp0aGlzOwogIH0KCiAgaW5saW5lIEZhc3RJbnB1dCYgb3BlcmF0b3I+PihzdHJpbmcmIHMpIHsKICAgIGlmIChza2lwX2JsYW5rcygpKSB7CiAgICAgIHMuY2xlYXIoKTsKICAgICAgZG8gewogICAgICAgIHMgKz0gY3VyOwogICAgICB9IHdoaWxlICghaXNfYmxhbmsoZ2V0X2NoYXIoKSkpOwogICAgfQogICAgcmV0dXJuICp0aGlzOwogIH0KCiAgdGVtcGxhdGUgPHR5cGVuYW1lIFQ+CiAgaW5saW5lIEZhc3RJbnB1dCYgcmVhZF9pbnRlZ2VyKFQmIG4pIHsKICAgIG4gPSAwOwogICAgaWYgKHNraXBfYmxhbmtzKCkpIHsKICAgICAgaW50IHNpZ24gPSArMTsKICAgICAgaWYgKGN1ciA9PSAnLScpIHsKICAgICAgICBzaWduID0gLTE7CiAgICAgICAgZ2V0X2NoYXIoKTsKICAgICAgfQogICAgICBkbyB7CiAgICAgICAgbiArPSBuICsgKG4gPDwgMykgKyBjdXIgLSAnMCc7CiAgICAgIH0gd2hpbGUgKCFpc19ibGFuayhnZXRfY2hhcigpKSk7CiAgICAgIG4gKj0gc2lnbjsKICAgIH0KICAgIHJldHVybiAqdGhpczsKICB9CgogIHRlbXBsYXRlIDx0eXBlbmFtZSBUPgogIGlubGluZSB0eXBlbmFtZSBlbmFibGVfaWY8aXNfaW50ZWdyYWw8VD46OnZhbHVlLCBGYXN0SW5wdXQmPjo6dHlwZSBvcGVyYXRvcj4+KFQmIG4pIHsKICAgIHJldHVybiByZWFkX2ludGVnZXIobik7CiAgfQoKICAjaWYgIWRlZmluZWQoX1dJTjMyKSB8IGRlZmluZWQoX1dJTjY0KQogIGlubGluZSBGYXN0SW5wdXQmIG9wZXJhdG9yPj4oX19pbnQxMjgmIG4pIHsKICAgIHJldHVybiByZWFkX2ludGVnZXIobik7CiAgfQogICNlbmRpZgoKICB0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4KICBpbmxpbmUgdHlwZW5hbWUgZW5hYmxlX2lmPGlzX2Zsb2F0aW5nX3BvaW50PFQ+Ojp2YWx1ZSwgRmFzdElucHV0Jj46OnR5cGUgb3BlcmF0b3I+PihUJiBuKSB7CiAgICBuID0gMDsKICAgIGlmIChza2lwX2JsYW5rcygpKSB7CiAgICAgIHN0cmluZyBzOwogICAgICAoKnRoaXMpID4+IHM7CiAgICAgIHNzY2FuZihzLmNfc3RyKCksICIlbGYiLCAmbik7CiAgICB9CiAgICByZXR1cm4gKnRoaXM7CiAgfQp9IGZhc3RfaW5wdXQ7CiNkZWZpbmUgY2luIGZhc3RfaW5wdXQKKi8Kdm9pZCBza2liaWRpaW5wdXQoKXsKICAgIAp9CnZvaWQgQUMoKXsKICAgIAp9CnZvaWQgc2tpYmlkaW91dHB1dCgpewogICAgCn0KX19ERVBUUkFJVkNMX197CiAgICAvL3NraWJpZGkKICAgIGJ1ZmZzcGVlZDsKICAgIGZvcGVubigiIik7CiAgICBza2liaWRpaW5wdXQoKTsKICAgIHNraWJpZGlvdXRwdXQoKTsKICAgIC8v8J+mhvCfpobwn6aG8J+mhgp9