#796617 (C++23) No.2049 POP

• 問題: No.2049 POP
• ユーザー: tatananonano
• 提出日時: 2022-09-11 14:54:04
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 3 ms / 2,000 ms
• コード長: 20,624 bytes
• コンパイル時間: 5,376 ms
• コンパイル使用メモリ: 247,756 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-28 00:29:07
• 合計ジャッジ時間: 6,322 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	3 ms; 5,248 KB
testcase_03	AC	3 ms; 5,248 KB
testcase_04	AC	3 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	3 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	2 ms; 5,248 KB

ソースコード

#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <set>
#include <map>
#include <ctime>
#include <stack>
#include <functional>
#include <cstdio>
#include <string>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <numeric>
#include <complex>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef long double LD;
typedef double D;
typedef pair<ll,ll> P;
typedef pair<D,D> PD;
typedef map<ll,ll> M;
#define vp(c,n) vec c(n);rep(i,n){c[i]=i;}
#define out(x) cout<<x<<endl;
#define rep(i,n) for(long long int i=0;i<n;i++)
#define rrep(i,n) for(long long int i=1;i<n;i++)
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define jep(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define REP(i, n) FOR(i, 0, n)
#define fore(i,a) for(const auto &i:a)
#define RREP(var, n)  for (auto var = n - 1; var != static_cast<decltype(var)>(-1); var--)//なんですかこれは
#define all(x) (x).begin(),(x).end()
#define memset(v, h) memset((v), h, sizeof(v))
#define frac(x) x-floor(x)
#define eb emplace_back
#define pb push_back
#define pbd(x,y) push_back({x,y});
#define pbt(x,y,z) push_back({x,y,z});
#define bs binary_search 
#define lb lower_bound
#define ub upper_bound
#define SUM(x) accumulate(all(x),0)
#define IP(a,b) inner_product(all(a),begin(b),0.0)//内積の計算
#define PS(a,b) partial_sum(all(a),begin(b))//累積和(具体的にはbは個数以外空にしておいて格納されていく)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end()) //重複消去＆sort
#define fr(f,x) fixed<<setprecision(f)<<x //小数点以下f桁までの表示
#define TFU(s) transform(all(s),begin(s),::toupper);//alphabetで全て大文字にする
#define TFL(s) transform(all(s),begin(s),::tolower);//alphabetで全て小文字にする
#define replace(s,a,A) replace(all(s),'a','A')//文字列sのaをAに変換する
#define NP(a) next_permutation(all(a))//順列
#define in(a, b, x) (a<=x&&x<b)//a以上b未満
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define ROT(s,i) rotate(s.begin(),s.begin()+i,s.end())//sのi番目から後ろを前にする
#define fbit(i,n) rep(i,n)if(bit&(1<<i))//すぐ消す(見るよう)
#define foreach(y) for_each(all(y),[](ll x){cout<<x<<" ";});cout<<endl;//配列の吐き出し
#define PQ priority_queue//打ちにくいもん
#define PQD PQ<P,vector<P>,greater<P>>
#define PQS PQ<ll,vec,greater<ll>>
#define fi first//大文字になれない
#define se second
#define cauto const auto&
#define bit(n) (1LL<<(n))
#define cl clock()/CLOCKS_PER_SEC//時間計測
#define printd(n,x) cout<<std::fixed<<std::setprecision(n)<<x<<endl
#define cinv(a,n); rep(i,n){cin>>a[i];}//試験運転してみる(多分つかわない)
#define cinvv(a,n,m); rep(i,n){rep(j,m){cin>>a[i][j];}}
template<class T> inline bool chmax(T& a,T b){if(a < b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a > b){a=b;return 1;}return 0;}
typedef vector<ll> vec;
typedef vector<string> ves;
typedef vector<vec> mat;
//const ll mod = 1000000009;//手動で切り替える.
//const ll mod = 998244353;
const ll mod = 1000000007;
//const ll mod=1e9;
using mint =modint998244353;//.val()が必要に注意 一旦置いておく
//using mint =modint1000000009;
//using mint =modint1000000007;
const ll INF = bit(60);
//ll dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
//struct Edge{ll to,co;Edge(ll to=0,ll co=0):to(to),co(co){}};//ABC191で何となくsunukeさんの！！
//struct Edge {ll to;ll cost;};
//struct Edge {ll from;ll to;ll cost;};
//struct Edge {ll to;ll w;Edge(ll to,ll w):to(to),w(w){}}; //けんちょん本 G[頂点a].pb(Edge(頂点b,weight));とか
//using Graph = vector<vector<ll>>;
//struct Edge {ll to,t,k;Edge(ll to,ll t,ll k):to(to),t(t),k(k){}};//ABC192で何となく
//using Graph =vector<vector<Edge>>;
#define cing(a,b,c) a[b].pb(c);a[c].pb(b);
//vector<bool> seen;
//void gdfs(const Graph &G,ll v){seen[v]=true;fore(next_v,G[v]){if(seen[next_v])continue;gdfs(G,next_v);}}//それぞれの点でif(seen[i])continue;else gdfs(G,i)をする
ll modpow(ll a,ll n,ll mod){if(mod==1)return 0;ll ret=1;ll p=a%mod;while(n){if(n&1)ret=ret*p%mod;p=p*p%mod;n>>=1;}return ret; }
M factor(ll n) {M ret;for(ll i=2;i*i<=n;i++){while(n%i==0){ret[i]++;n /= i;}}if(n != 1){ret[n]=1;}return ret;}//素因数分解 mapにする
vec divisor(ll n){vec K;for(ll i=1;i*i<=n;i++){if(n%i==0){K.pb(i);if(i*i!=n)K.pb(n/i);}}sort(all(K));return K;}//約数列挙 cauto& a=divisor(100);的に書く
ll modlog(ll a,ll b,ll p){ll g=1;for(ll i=p;i;i/=2)(g*=a)%=p;g=gcd(g,p);ll t=1,c=0;for(;t%g;c++){if(t==b)return c;(t*=a)%=p;}if(b%g){return -1;}t/=g;b /= g;ll n=p/g,h=0,gs=1;for(;h*h<n; h++){(gs*=a)%=n;}unordered_map<ll,ll>bs;for(ll s=0,e=b;s<h;bs[e]=++s){(e *= a) %= n;}for(ll s = 0, e = t; s < n;){(e*=gs)%=n;s+=h;if(bs.count(e))return c+s-bs[e];}return -1;}//a^x≡b(modp) x_min
bool isprime(ll N){if(N==1){return false;}if(N==2){return true;}for(ll i=2;i*i<=N;i++){if(N%i==0)return false;}return true;}
static inline ll my_div(ll n, ll p) { return double(n) / p; };
ll prime_counting(ll N) {ll N2 = sqrt(N);ll NdN2 = my_div(N, N2);vec hl(NdN2);rrep(i,NdN2){hl[i] = my_div(N, i) - 1;}vec hs(N2 + 1);iota(begin(hs), end(hs), -1);for (int x = 2, pi = 0; x <= N2; ++x) {if (hs[x] == hs[x - 1]) {continue;}ll x2 = ll(x) * x;ll imax = min<ll>(NdN2, my_div(N, x2) + 1);ll ix = x;for (ll i = 1; i < imax; ++i) {hl[i] -= (ix < NdN2 ? hl[ix] : hs[my_div(N, ix)]) - pi;ix += x;}for (int n = N2; n >= x2; n--) {hs[n] -= hs[my_div(n, x)] - pi;}++pi;}return hl[1];}

//  /*
constexpr ll MAX = 3000000;ll fac[MAX],finv[MAX],inv[MAX];//int main(){cominit();}と打つのを忘れないように.
void cominit(){fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;for(int i=2;i<MAX;i++){fac[i]=fac[i-1]*i%mod;inv[i]=mod-inv[mod%i]*(mod/i)%mod;finv[i]=finv[i-1]*inv[i]%mod;}}
ll binom(ll n,ll k){if(n<k) return 0;if(n<0||k<0) return 0;return fac[n]*(finv[k]*finv[n-k]%mod)%mod;}
ll hom(ll n,ll k){if(n==0&&k==0) return 1;return binom(n+k-1,k);}
ll pom(ll n,ll k){if(n<k) return 0;return fac[n]*finv[n-k]%mod;}
//   */
mat binomial(ll n) {mat a(n+1,vec(n+1));rep(i,n+1)rep(j,i+1){if(j==0||j==i)a[i][j]=1;else a[i][j]=a[i-1][j-1]+a[i-1][j];}return a;}//O(n^2)
template<typename T>T phi(T n) {T ret=n;for(T i = 2; i * i <= n; i++){if(n % i == 0){ret -= ret / i;while(n % i == 0) n /= i;}}if(n > 1){ret -= ret / n;}return ret;}
template<typename T>T extgcd(T a, T b, T &x, T &y){T d = a;if(b != 0){d=extgcd(b,a%b,y,x);y -= (a / b) * x;}else {x = 1;y = 0;}return d;}
mat mat_mul(mat&a,mat&b){mat res(a.size(),vec(b[0].size()));rep(i,a.size()){rep(j,b[0].size()){rep(k,b.size()){(res[i][j]+=a[i][k]*b[k][j])%=mod;}}}return res;}
mat matpow(mat a,ll n){mat res(a.size(),vec(a.size()));rep(i,a.size())res[i][i]=1;while(n>0){if(n & 1)res=mat_mul(a,res);a=mat_mul(a,a);n>>=1;}return res;}
#define cinmat(a,x,y) mat a(x,vec(y));rep(i,x)rep(j,y)cin>>a[i][j];//;をつけなくていいよ!(お気持ちかなり使いやすそう使いにくかったらやめるけども)
#define comat(a,x,y) rep(i,x){rep(j,y){cout<<a[i][j]<<" ";}cout<<endl;}//;をつけなくていいよ！
#define FT(x) fenwick_tree<ll x> //fw(n);としてfw.add(p,x)->fw[p]+x  fw.sum(l,r)->Σ[l,r-1]fw[i] (O(logn)!!)
#define SA(s) vec suffix_arry(s)//よくわかんない
#define LCP(s,a) vec lcp_rray(s,a)//Long Common Prefix
#define ZA(s) z_algorithm(s)//上と同じようなやつ
#define IV(x,m) inv_mod(x,m)//逆元がなんと対応！！  //ついでに pair<ll,ll> crt(r,m) 解なし(0,0) n=0 (0,1) CRT!!
#define FS(n,m,a,b) floor_sum(n,m,a,b)//Σ[0,n-1]floor((a*i+b)/m) (これがなんとO(log(max(n,m,a,b))))
#define FFT(a,b,c) vec a=convolution(b,c)//FFT,NNT 畳み込み <ll m=mod>をFFT()の直後に挿入したらmodできる.
void ACC(vec a,vec &b){b[0]=0;rrep(i,a.size()){b[i]=b[i-1]+a[i-1];}return;}



















//幾何ライブラリの構築をする!!



using Point = complex<double>;
const D EPS = 1e-7;
const D PI = acosl(-1);
inline bool equal(const D &a, const D &b) { return fabs(a - b) < EPS; }
Point unitVector(const Point &a) { return a / abs(a); }//単位vec
Point normalVector(const Point &a) { return a * Point(0, 1); }//法線vec
D dot(const Point &a, const Point &b) {return (a.real() * b.real() + a.imag() * b.imag());}//内積
D cross(const Point &a, const Point &b) {return (a.real() * b.imag() - a.imag() * b.real());}//外積
Point rotate(const Point &p, const D &theta) {return Point(cos(theta) * p.real() - sin(theta) * p.imag(),sin(theta) * p.real() + cos(theta) * p.imag());}//pを反時計周りにtheta回転
D radianToDegree(const D &radian) { return radian * 180.0 / PI; }//ラジアン->度
D degreeToRadian(const D &degree) { return degree * PI / 180.0; }//度->ラジアン
int ccw(const Point &a, Point b, Point c) {b-= a,c-=a;if(cross(b,c)>EPS){return 1;}if(cross(b,c)<-EPS){return -1;}if(dot(b,c)<0){return 2;}if(norm(b)<norm(c)){return -2;}return 0;}// {(a, b, cが反時計回り),(a, b, cが時計回り),(c, a, bがこの順番で同一直線上) ,(a, b, cがこの順番で同一直線上),(cが線分ab上)}
struct Line {Point a, b;Line() = default;Line(Point a, Point b) : a(a), b(b) {}Line(D A, D B, D C) {if(equal(A, 0)) {a = Point(0, C / B), b = Point(1, C / B);} else if(equal(B, 0)) {b = Point(C / A, 0), b = Point(C / A, 1);} else {a = Point(0, C / B), b = Point(C / A, 0);}}};//直線のstruct
struct Segment : Line {Segment() = default;Segment(Point a, Point b) : Line(a, b) {}D get_dist() {return abs(a - b);}};//線分のstruct
struct Circle {Point p;D r;Circle() = default;Circle(Point p, D r) : p(p), r(r) {}};//円の構造体
bool isOrthogonal(const Line &a, const Line &b) {return equal(dot(a.b - a.a, b.b - b.a), 0);}//2直線の直交判定
bool isParallel(const Line &a, const Line &b) {return equal(cross(a.b - a.a, b.b - b.a), 0);}//2直線の平行判定
bool isPointOnLine(const Point &a, const Point &b, const Point &c) {return isParallel(Line(a, b), Line(a, c));}//点cが直線ab上にあるか
bool isPointOnSegment(const Point &a, const Point &b, const Point &c) {return (abs(a - c) + abs(c - b) < abs(a - b) + EPS);}//点cが"線分"ab上にあるか
D distanceBetweenLineAndPoint(const Line &l, const Point &p) {return abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);}//直線lと点pの距離を求める
D distanceBetweenSegmentAndPoint(const Segment &l, const Point &p) {if(dot(l.b - l.a, p - l.a) < EPS){return abs(p - l.a);}if(dot(l.a - l.b, p - l.b) < EPS){return abs(p - l.b);}return abs(cross(l.b - l.a, p - l.a)) / abs(l.b - l.a);}//線分lと点pの距離を求める
Point crossPoint(const Line &s, const Line &t) {D d1 = cross(s.b - s.a, t.b - t.a);D d2 = cross(s.b - s.a, s.b - t.a);if(equal(abs(d1), 0) && equal(abs(d2), 0)){return t.a;}return t.a + (t.b - t.a) * (d2 / d1);}//直線s, tの交点の計算
Point crossPoint(const Segment &s, const Segment &t) {return crossPoint(Line(s), Line(t));}//線分s, tの交点の計算
bool isIntersect(const Segment &s, const Segment &t, bool bound) {return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) < bound &&ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) < bound;}//線分sと線分tが交差しているかどうか(bound:線分の端点を含むか)
D distanceBetweenSegments(const Segment &s, const Segment &t) {if(isIntersect(s, t, 1)){return (D)(0);}D ans = distanceBetweenSegmentAndPoint(s, t.a);chmin(ans, distanceBetweenSegmentAndPoint(s, t.b));chmin(ans, distanceBetweenSegmentAndPoint(t, s.a));chmin(ans, distanceBetweenSegmentAndPoint(t, s.b));return ans;}//線分sとtの距離
Point projection(const Line &l, const Point &p) {D t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);return l.a + (l.a - l.b) * t;}//直線(線分)lに点pから引いた垂線の足を求める
Point projection(const Segment &l, const Point &p) {D t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);return l.a + (l.a - l.b) * t;}//直線(線分)lに点pから引いた垂線の足を求める
Point reflection(const Line &l, const Point &p) {return p + (projection(l, p) - p) * (D)2.0;}//直線lを対称軸として点pと線対称の位置にある点を求める
int isIntersect(const Circle &c1, const Circle &c2) {D d = abs(c1.p - c2.p);if(d > c1.r + c2.r + EPS){return 4;}if(equal(d, c1.r + c2.r)){return 3;}if(equal(d, abs(c1.r - c2.r))){return 1;}if(d < abs(c1.r - c2.r) - EPS){return 0;}return 2;}//{(2つの円が離れている場合),(外接している場合),(内接している場合),(内包している場合)} 2つの円の交差判定(返り値は共通接線の数)
vector<Point> crossPoint(const Circle &c1, const Circle &c2) {vector<Point> res;int mode = isIntersect(c1, c2);D d = abs(c1.p - c2.p);if(mode == 4){return res;}if(mode == 0){return res;}if(mode == 3) {D t = c1.r / (c1.r + c2.r);res.emplace_back(c1.p + (c2.p - c1.p) * t);return res;}if(mode == 1) {if(c2.r < c1.r - EPS) {res.emplace_back(c1.p + (c2.p - c1.p) * (c1.r / d));} else {res.emplace_back(c2.p + (c1.p - c2.p) * (c2.r / d));}return res;}D rc1 = (c1.r * c1.r + d * d - c2.r * c2.r) / (2 * d);D rs1 = sqrt(c1.r * c1.r - rc1 * rc1);if(c1.r - abs(rc1) < EPS){rs1 = 0;}Point e12 = (c2.p - c1.p) / abs(c2.p - c1.p);res.emplace_back(c1.p + rc1 * e12 + rs1 * e12 * Point(0, 1));res.emplace_back(c1.p + rc1 * e12 + rs1 * e12 * Point(0, -1));return res;}//2つの円の交点
bool isInCircle(const Circle &c, const Point &p) {D d = abs(c.p - p);return (equal(d, c.r) || d < c.r - EPS);}//点pが円cの内部(円周上も含む)に入っているかどうか
vector<Point> crossPoint(const Circle &c, const Line &l) {vector<Point> res;D d = distanceBetweenLineAndPoint(l, c.p);if(d > c.r + EPS) {return res;}Point h = projection(l, c.p);if(equal(d, c.r)) {res.emplace_back(h);return res;}Point e = unitVector(l.b - l.a);D ph = sqrt(c.r * c.r - d * d);res.emplace_back(h - e * ph);res.emplace_back(h + e * ph);return res;}//円cと直線lの交点
vector<Point> tangentToCircle(const Point &p, const Circle &c) {return crossPoint(c, Circle(p, sqrt(norm(c.p - p) - c.r * c.r)));}//点pを通る円cの接線(2本あるので、接点のみを返す)
vector<Line> tangent(const Circle &a, const Circle &b) {vector<Line> ret;D g = abs(a.p - b.p);if(equal(g, 0)){return ret;}Point u = unitVector(b.p - a.p);Point v = rotate(u, PI / 2);for(int s : {-1, 1}) {D h = (a.r + b.r * s) / g;if(equal(h * h, 1)) {ret.emplace_back(a.p + (h > 0 ? u : -u) * a.r,a.p + (h > 0 ? u : -u) * a.r + v);} else if(1 - h * h > 0) {Point U = u * h, V = v * sqrt(1 - h * h);ret.emplace_back(a.p + (U + V) * a.r,b.p - (U + V) * (b.r * s));ret.emplace_back(a.p + (U - V) * a.r,b.p - (U - V) * (b.r * s));}}return ret;}//円の共通接線
D PolygonArea(const vector<Point> &p) {D res = 0;int n = p.size();for(int i = 0; i < n - 1; i++) res += cross(p[i], p[i + 1]);res += cross(p[n - 1], p[0]);return res * 0.5;}//多角形の面積を求める
bool isConvex(const vector<Point> &p) {int n = p.size();int now, pre, nxt;for(int i = 0; i < n; i++) {pre = (i - 1 + n) % n;nxt = (i + 1) % n;now = i;if(ccw(p[pre], p[now], p[nxt]) == -1){return false;}}return true;}//凸多角形かどうか
vector<Point> ConvexHull(vector<Point> p) {int n = (int)p.size(), k = 0;sort(all(p), [](const Point &a, const Point &b) {return (real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b));});vector<Point> ch(2 * n);for(int i = 0; i < n; ch[k++] = p[i++]) { while(k >= 2 &&cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS)--k;}for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {while(k >= t &&cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < EPS)--k;}ch.resize(k - 1);return ch;}//凸包 O(NlogN)
int isContained(const vector<Point> &g, const Point &p) {bool in = false;int n = (int)g.size();for(int i = 0; i < n; i++) {Point a = g[i] - p, b = g[(i + 1) % n] - p;if(imag(a) > imag(b)){swap(a, b);}if(imag(a) <= EPS && EPS < imag(b) && cross(a, b) < -EPS){in = !in;}if(cross(a, b) == 0 && dot(a, b) <= 0) return 1;}return (in ? 2 : 0);}//多角形gに点pが含まれているか(含まれる:2,辺上にある:1,含まれない:0)
vector<Point> ConvexCut(vector<Point> p, Line l) {vector<Point> ret;int sz = (int)p.size();rep(i, sz){Point now = p[i];Point nxt = p[i == sz-1 ? 0 : i+1];if(ccw(l.a, l.b, now) != -1) ret.emplace_back(now);if(ccw(l.a, l.b, now) * ccw(l.a, l.b, nxt) < 0) {ret.emplace_back(crossPoint(Line(now, nxt), l));}}return ret;}//凸多角形pを直線lで切断し、その左側を返す













struct Barrett {
  using u32 = unsigned int;
  using i64 = long long;
  using u64 = unsigned long long;
  u32 m;
  u64 im;
  Barrett() : m(), im() {}
  Barrett(int n) : m(n), im(u64(-1) / m + 1) {}
  constexpr inline i64 quo(u64 n) {
    u64 x = u64((__uint128_t(n) * im) >> 64);
    u32 r = n - x * m;
    return m <= r ? x - 1 : x;
  }
  constexpr inline i64 rem(u64 n) {
    u64 x = u64((__uint128_t(n) * im) >> 64);
    u32 r = n - x * m;
    return m <= r ? r + m : r;
  }
  constexpr inline pair<i64, int> quorem(u64 n) {
    u64 x = u64((__uint128_t(n) * im) >> 64);
    u32 r = n - x * m;
    if (m <= r) return {x - 1, r + m};
    return {x, r};
  }
  constexpr inline i64 pow(u64 n, i64 p) {
    u32 a = rem(n), r = m == 1 ? 0 : 1;
    while (p) {
      if (p & 1) r = rem(u64(r) * a);
      a = rem(u64(a) * a);
      p >>= 1;
    }
    return r;
  }
};
struct prime_power_binomial {
  int p, q, M;
  vector<int> fac, ifac, inv;
  int delta;
  Barrett bm, bp;

  prime_power_binomial(int _p, int _q) : p(_p), q(_q) {
    assert(1 < p && p <= ((1LL << 30) - 1));
    assert(_q > 0);
    long long m = 1;
    while (_q--) {
      m *= p;
      assert(m <=((1LL << 30) - 1));
    }
    M = m;
    bm = Barrett(M), bp = Barrett(p);
    enumerate();
    delta = (p == 2 && q >= 3) ? 1 : M - 1;
  }

  void enumerate() {
    int MX = min<int>(M, 20000000 + 10);
    fac.resize(MX);
    ifac.resize(MX);
    inv.resize(MX);
    fac[0] = ifac[0] = inv[0] = 1;
    fac[1] = ifac[1] = inv[1] = 1;
    for (int i = 2; i < MX; i++) {
      if (i % p == 0) {
        fac[i] = fac[i - 1];
        fac[i + 1] = bm.rem(1LL * fac[i - 1] * (i + 1));
        i++;
      } else {
        fac[i] = bm.rem(1LL * fac[i - 1] * i);
      }
    }
    ifac[MX - 1] = bm.pow(fac[MX - 1], M / p * (p - 1) - 1);
    for (int i = MX - 2; i > 1; --i) {
      if (i % p == 0) {
        ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1));
        ifac[i - 1] = ifac[i];
        i--;
      } else {
        ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1));
      }
    }
  }

  long long Lucas(long long n, long long m) {
    int res = 1;
    while (n) {
      int n0, m0;
      tie(n, n0) = bp.quorem(n);
      tie(m, m0) = bp.quorem(m);
      if (n0 < m0) return 0;
      res = bm.rem(1LL * res * fac[n0]);
      int buf = bm.rem(1LL * ifac[n0 - m0] * ifac[m0]);
      res = bm.rem(1LL * res * buf);
    }
    return res;
  }

  long long C(long long n, long long m) {
    if (n < m || n < 0 || m < 0) return 0;
    if (q == 1) return Lucas(n, m);
    long long r = n - m;
    int e0 = 0, eq = 0, i = 0;
    int res = 1;
    while (n) {
      res = bm.rem(1LL * res * fac[bm.rem(n)]);
      res = bm.rem(1LL * res * ifac[bm.rem(m)]);
      res = bm.rem(1LL * res * ifac[bm.rem(r)]);
      n = bp.quo(n);
      m = bp.quo(m);
      r = bp.quo(r);
      int eps = n - m - r;
      e0 += eps;
      if (e0 >= q) return 0;
      if (++i >= q) eq += eps;
    }
    if (eq & 1) res = bm.rem(1LL * res * delta);
    res = bm.rem(1LL * res * bm.pow(p, e0));
    return res;
  }
};
struct binomial_mod {
  int mod;
  vector<int> M;
  vector<prime_power_binomial> cs;

  binomial_mod(long long md) : mod(md) {
    assert(1 <= md);
    assert(md <= ((1LL << 30) - 1));
    for (int i = 2; i * i <= md; i++) {
      if (md % i == 0) {
        int j = 0, k = 1;
        while (md % i == 0) md /= i, j++, k *= i;
        M.push_back(k);
        cs.emplace_back(i, j);
        assert(M.back() == cs.back().M);
      }
    }
    if (md != 1) {
      M.push_back(md);
      cs.emplace_back(md, 1);
    }
    assert(M.size() == cs.size());
  }

  long long C(long long n, long long m) {
    if (mod == 1) return 0;
    vector<long long> rem, d;
    for (int i = 0; i < (int)cs.size(); i++) {
      rem.push_back(cs[i].C(n, m));
      d.push_back(M[i]);
    }
    return crt(rem, d).first;
  }
};





int main(){
ll n;
cin>>n;
string s;
cin>>s;
cout<<s.substr(1,s.size()-2)<<endl;
}