#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define bit(mask,i) ((mask>>i)&1)
#define all(x) (x).begin(),(x).end()
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vector<int>>
#define pb push_back
#define enl '\n'
#define fi first
#define se second
#define FOR0(i,b) for(int i=(0),_b=(b);i<_b;i++)
#define FOR(i, a, b) for(int i=(a),_b=(b);i<=_b;i++)
#define FOD(i, a, b) for(int i=(a),_b=(b);i>=_b;i--)
mt19937 Rd(time(0));
ll Rand(ll l,ll r){
return l+Rd()%(r-l+1);
}
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int maxN=1e6,cc=500,N=1e6+5,MOD=1e9+7,base=31;
const ll oo=1e18;
int n;
void inp(){
}
void solve(){
}
int main(){
//freopen("name.inp","r",stdin);
//freopen("name.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
inp();
solve();
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgdWxsIHVuc2lnbmVkIGxvbmcgbG9uZwojZGVmaW5lIGJpdChtYXNrLGkpICgobWFzaz4+aSkmMSkKI2RlZmluZSBhbGwoeCkgKHgpLmJlZ2luKCksKHgpLmVuZCgpCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgaWkgcGFpcjxpbnQsaW50PgojZGVmaW5lIGlpaSBwYWlyPGlpLGludD4KI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIHZpaSB2ZWN0b3I8aWk+CiNkZWZpbmUgdnZpIHZlY3Rvcjx2ZWN0b3I8aW50Pj4KI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBlbmwgJ1xuJwojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgRk9SMChpLGIpIGZvcihpbnQgaT0oMCksX2I9KGIpO2k8X2I7aSsrKQojZGVmaW5lIEZPUihpLCBhLCBiKSBmb3IoaW50IGk9KGEpLF9iPShiKTtpPD1fYjtpKyspCiNkZWZpbmUgRk9EKGksIGEsIGIpIGZvcihpbnQgaT0oYSksX2I9KGIpO2k+PV9iO2ktLSkKbXQxOTkzNyBSZCh0aW1lKDApKTsKbGwgUmFuZChsbCBsLGxsIHIpewogICAgcmV0dXJuIGwrUmQoKSUoci1sKzEpOwp9Cm10MTk5MzdfNjQgcm5kKGNocm9ubzo6c3RlYWR5X2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7Cgpjb25zdCBpbnQgbWF4Tj0xZTYsY2M9NTAwLE49MWU2KzUsTU9EPTFlOSs3LGJhc2U9MzE7CmNvbnN0IGxsIG9vPTFlMTg7CgppbnQgbjsKCnZvaWQgaW5wKCl7Cn0KCnZvaWQgc29sdmUoKXsKfQoKaW50IG1haW4oKXsKICAgIC8vZnJlb3BlbigibmFtZS5pbnAiLCJyIixzdGRpbik7CiAgICAvL2ZyZW9wZW4oIm5hbWUub3V0IiwidyIsc3Rkb3V0KTsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBjb3V0LnRpZShOVUxMKTsKICAgIGlucCgpOwogICAgc29sdmUoKTsKfQo=