#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
using i64 = long long;
using ui64 = unsigned long long;
int a[N];
#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define sz(x) (x).size()
#define all(x) (x).begin() , (x).end()
#define srt(x) sort(all(x))
#define vii vector<int,int>
#define vi vector<int>
#define pb push_back
#define ins insert
#define FOR(i ,a , b) for (int i = (a); i <= (b); ++i)
#define FORD(i , a , b) for (int i = (b); i >= (a); --i)
#define REP(i , a , b) for (int i = (a); i < (b); ++i)
#define REPD(i , a , b) for (int i = (b) - 1 ; i >= (a); --i)
#define seea(x,a) FOR(i,1,x) cin>>a[i]
#define seev(x,a) FOR(i,1,x){int v; cin>>v; a.pb(v);}
#define sees(x,s) FOR(i,1,x){int v; cin>>v; s.ins(v);}
template <class T>
void compress(vector<T> &a)
{
sort(a.begin() , a.end());
a.resize(unique(a.begin() , a.end()) - a.begin());
return;
}
template<class T>
void printArr(T& container , string separator = "" , string finish = "\n")
{
for (auto& item : container) cout << item << separator;
cout << finish;
}
template<class T>
bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
T lcm(T x , T y) {return (x * y) / gcd(x , y);}
void INPUT(string name)
{
iostream::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if(!fopen((name + ".inp").c_str() , "r")) return;
freopen((name + ".inp").c_str() , "r" , stdin);
freopen((name + ".out").c_str() , "w+" , stdout);
}
void solve(){
}
int32_t main()
{
INPUT("");
int test=1;//cin>>test;
while(test--)
solve();
return 0;
}
//CR7GOAT-FAKERGOAT
//GLORY FOR T1 (5 STARS*)
//editor:KNS-Samtd
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBOPTFlNSs3Owp1c2luZyBpNjQgPSBsb25nIGxvbmc7CnVzaW5nIHVpNjQgPSB1bnNpZ25lZCBsb25nIGxvbmc7CmludCBhW05dOwojZGVmaW5lIE1BU0soeCkgKChpNjQpKDEpIDw8ICh4KSkKI2RlZmluZSBCSVQobWFzayAsIHgpICgoKG1hc2spID4+ICh4KSkgJiAoMSkpCiNkZWZpbmUgc3ooeCkgKHgpLnNpemUoKQojZGVmaW5lIGFsbCh4KSAoeCkuYmVnaW4oKSAsICh4KS5lbmQoKQojZGVmaW5lIHNydCh4KSBzb3J0KGFsbCh4KSkKCiNkZWZpbmUgdmlpIHZlY3RvcjxpbnQsaW50PgojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgaW5zIGluc2VydAoKI2RlZmluZSBGT1IoaSAsYSAsIGIpIGZvciAoaW50IGkgPSAoYSk7IGkgPD0gKGIpOyArK2kpCiNkZWZpbmUgRk9SRChpICwgYSAsIGIpIGZvciAoaW50IGkgPSAoYik7IGkgPj0gKGEpOyAtLWkpCiNkZWZpbmUgUkVQKGkgLCBhICwgYikgZm9yIChpbnQgaSA9IChhKTsgaSA8IChiKTsgKytpKQojZGVmaW5lIFJFUEQoaSAsIGEgLCBiKSBmb3IgKGludCBpID0gKGIpIC0gMSA7IGkgPj0gKGEpOyAtLWkpCgojZGVmaW5lIHNlZWEoeCxhKSBGT1IoaSwxLHgpIGNpbj4+YVtpXQojZGVmaW5lIHNlZXYoeCxhKSBGT1IoaSwxLHgpe2ludCB2OyBjaW4+PnY7IGEucGIodik7fQojZGVmaW5lIHNlZXMoeCxzKSBGT1IoaSwxLHgpe2ludCB2OyBjaW4+PnY7IHMuaW5zKHYpO30KCnRlbXBsYXRlIDxjbGFzcyBUPgp2b2lkIGNvbXByZXNzKHZlY3RvcjxUPiAmYSkKewogICAgc29ydChhLmJlZ2luKCkgLCBhLmVuZCgpKTsKICAgIGEucmVzaXplKHVuaXF1ZShhLmJlZ2luKCkgLCBhLmVuZCgpKSAtIGEuYmVnaW4oKSk7CiAgICByZXR1cm47Cn0KdGVtcGxhdGU8Y2xhc3MgVD4Kdm9pZCBwcmludEFycihUJiBjb250YWluZXIgLCBzdHJpbmcgc2VwYXJhdG9yID0gIiIgLCBzdHJpbmcgZmluaXNoID0gIlxuIikKewogICAgZm9yIChhdXRvJiBpdGVtIDogY29udGFpbmVyKSBjb3V0IDw8IGl0ZW0gPDwgc2VwYXJhdG9yOwogICAgY291dCA8PCBmaW5pc2g7Cn0KCnRlbXBsYXRlPGNsYXNzIFQ+CiAgICBib29sIG1heGltaXplKFQgJmEgLCBUIGIpIHtpZiAoYSA8IGIpIHJldHVybiBhID0gYiAsIHRydWU7IGVsc2UgcmV0dXJuIGZhbHNlO30KdGVtcGxhdGU8Y2xhc3MgVD4KICAgIGJvb2wgbWluaW1pemUoVCAmYSAsIFQgYikge2lmIChhID4gYikgcmV0dXJuIGEgPSBiICwgdHJ1ZTsgZWxzZSByZXR1cm4gZmFsc2U7fQp0ZW1wbGF0ZTxjbGFzcyBUPgogICAgVCBnY2QoVCB4ICwgVCB5KSB7d2hpbGUgKHkpIHN3YXAoeSAsIHggJT0geSk7IHJldHVybiB4O30KdGVtcGxhdGU8Y2xhc3MgVD4KICAgIFQgbGNtKFQgeCAsIFQgeSkge3JldHVybiAoeCAqIHkpIC8gZ2NkKHggLCB5KTt9Cgp2b2lkIElOUFVUKHN0cmluZyBuYW1lKQp7CiAgICBpb3N0cmVhbTo6c3luY193aXRoX3N0ZGlvKDApOwoJY2luLnRpZSgwKTsgY291dC50aWUoMCk7CiAgICBpZighZm9wZW4oKG5hbWUgKyAiLmlucCIpLmNfc3RyKCkgLCAiciIpKSByZXR1cm47CiAgICBmcmVvcGVuKChuYW1lICsgIi5pbnAiKS5jX3N0cigpICwgInIiICwgc3RkaW4pOwogICAgZnJlb3BlbigobmFtZSArICIub3V0IikuY19zdHIoKSAsICJ3KyIgLCBzdGRvdXQpOwp9CnZvaWQgc29sdmUoKXsKCn0KaW50MzJfdCBtYWluKCkKewogICAgSU5QVVQoIiIpOwogICAgaW50IHRlc3Q9MTsvL2Npbj4+dGVzdDsKICAgIHdoaWxlKHRlc3QtLSkKICAgIAlzb2x2ZSgpOwoJcmV0dXJuIDA7Cn0KCi8vQ1I3R09BVC1GQUtFUkdPQVQKLy9HTE9SWSBGT1IgVDEgKDUgU1RBUlMqKQovL2VkaXRvcjpLTlMtU2FtdGQK