#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Fast Power
ll binpow(ll a, ll b){
ll res = 1;
while(b){
if(b & 1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
// Modular Power
ll modpow(ll a,ll b,ll mod){
ll res=1;
a%=mod;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
int main(){
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nCgovLyBGYXN0IFBvd2VyCmxsIGJpbnBvdyhsbCBhLCBsbCBiKXsKICAgIGxsIHJlcyA9IDE7CiAgICB3aGlsZShiKXsKICAgICAgICBpZihiICYgMSkgcmVzICo9IGE7CiAgICAgICAgYSAqPSBhOwogICAgICAgIGIgPj49IDE7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgovLyBNb2R1bGFyIFBvd2VyCmxsIG1vZHBvdyhsbCBhLGxsIGIsbGwgbW9kKXsKICAgIGxsIHJlcz0xOwogICAgYSU9bW9kOwogICAgd2hpbGUoYil7CiAgICAgICAgaWYoYiYxKSByZXM9KHJlcyphKSVtb2Q7CiAgICAgICAgYT0oYSphKSVtb2Q7CiAgICAgICAgYj4+PTE7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgoKCgppbnQgbWFpbigpewoKfQo=