akhauriyash/Code-Regression huggingface dataset:
#[test]
fn test_solve() {
    assert_eq!(solve("gpg\n"), "0\n");
    assert_eq!(solve("ggppgggpgg\n"), "2\n");
}
fn solve(src: &str) -> String {
    let mut sc = Scanner::from_str(src);

    let s = sc.get();
    let n = s.len();

    let mut pa = 0;
    let mut si = 0;
    while let &Some(i) = &s[si..].find("p") {
        pa += 1;
        si += i + 1;
    }
    format!("{}\n", n / 2 - pa)
}
fn main() {
    let mut buf = String::new();
    use std::io::{Read, Write};
    std::io::stdin().read_to_string(&mut buf).unwrap();
    std::io::stdout().write_all(solve(&buf).as_bytes()).unwrap();
}
struct Scanner<'a>(std::str::SplitWhitespace<'a>);
impl<'a> Scanner<'a> {
    fn from_str(src: &str) -> Scanner {
        Scanner(src.split_whitespace())
    }
    fn get(&mut self) -> &str {
        self.0.next().unwrap()
    }
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.get().parse().ok().unwrap()
    }
}


Measured memory_bytes: 4476
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <list>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <iomanip>
#define INF 2147483647
 
using namespace std;


bool dpssum(int *a, int b, int n)
{
	int y[21][2001];

	for (int i = 0; i < n; i++)
		for (int j = 0; j <= b; j++)
			y[i][j] = 0;
	y[0][0] = 1;
	y[0][a[0]] = 1;

	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= b; j++) {
			if (y[i - 1][j] == 1)  
				y[i][j] = 1;
			else if (j - a[i] >= 0 && y[i - 1][j - a[i]] == 1)
				y[i][j] = 1;
		}
	}

	if (y[n - 1][b] == 1) return (true);
	else				  return (false);
} 

int main(void)
{
	int n, q;
	int x;
	int a[20];
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	cin >> q;

	for (int i = 0; i < q; i++) {
		cin >> x;
		if (dpssum(a, x, n))
			cout << "yes" << endl;
		else
			cout << "no" << endl;
	}


	
	

return (0);
}

Measured memory_bytes: 1312
N = int(input())
A = list(input())
B = [0]*N
C = [0]*N
for i in range(N):
  if A[i] == "I":
    B[i] = 1
  else:
    B[i] = -1
C[0] = B[0]
for i in range(1, N):
  C[i] = C[i-1]+B[i]
if max(C) < 0:
    print(0)
else:
    print(max(C))


Measured memory_bytes: 38256
#include<cstdio>
#include<cctype>

int main() {
    char str;
    while(1){
        scanf("%c", &str);
        
            if(islower(str)){
                printf("%c", toupper(str));
            }else if(isupper(str)){
                printf("%c", tolower(str));
            }else {
                printf("%c", str);
            }

        if(str == '\n') break;

    }
    return 0;
}


Measured memory_bytes: 2596
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    if (B == 100) B = 101;

    for (int a = 0; a < A; a++) B *= 100;
    cout << B << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
    char n[10];
    scanf("%s",n);
    if(((n[0]==n[1])&&(n[1]==n[2]))||((n[1]==n[2])&&(n[2]==n[3])))
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 128
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> bool chmin(T& a,const T& b) {
  if(a>b) {
    a=b;
    return true;
  }
  return false;
}
template<class T> bool chmax(T& a,const T& b) {
  if(a<b){
    a=b;
    return true;
  }
  return false;
}

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

//const int INF=5e8;
int h,w;
char buf[15][15];
int main(){
  cin>>h>>w;
  REP(i,h) scanf("%s",buf[i]);

  int flag[15]={0};
  int h2=(h+1)/2;
  REP(i,h2) flag[i+h-h2]=1;

  int cnt2=0;
  do{
    int perm[15]={0};
    REP(i,h2) perm[i]=i;
    do{
      ++cnt2;
      if(cnt2%10000==0) dump(cnt2);
      vector<int> up(h2),down(h2);
      int c0=0,c1=0;
      REP(i,h){
        if(flag[i]==1) up[perm[c0]]=i,++c0;
        else down[c1]=i,++c1;
      }
      if(h&1) down[h2-1]=up[h2-1];
      bool fail=false;
      REP(i,h2) if(down[i]>up[i]){
        fail=true;
      }
      if(fail) continue;
      auto get=[&](int c,const vector<int>& x){
        string res;
        REP(i,h2) res+=buf[x[i]][c];
        return res;
      };

      map<pair<string,string>,int> cnt;
      REP(i,w){
        cnt[mp(get(i,up),get(i,down))]++;
      }
      int ocnt=0;
      for(auto e:cnt){
        string s1=e.fr.fr,s2=e.fr.sc;
        if(s1!=s2 && (!cnt.count(mp(s2,s1)) || e.sc!=cnt[mp(s2,s1)])) {
          fail=true;
          break;
        }
        if(s1==s2){
          ocnt+=e.sc%2;
          if(ocnt>(w%2)) {
            fail=true;
            break;
          }
        }
      }
      if(!fail){
        puts("YES");
        return 0;
      }
    }while(next_permutation(perm,perm+h2));
  }while(next_permutation(flag,flag+h));
  puts("NO");

  return 0;
}





Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
#define MOD 998244353
using namespace std;
typedef long long ll;
int main() {
  int n, cnt, sum = 0, mini;
  vector<pair<int, int> > vp, vm;
  string s;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> s;
    cnt = 0;
    mini = 0;
    for (int j = 0; j < s.length(); j++) {
      if (s[j] == '(') {
        cnt++;
      } else {
        cnt--;
      }
      mini = min(mini, cnt);
    }
    sum += cnt;
    if (cnt > 0) {
      vp.push_back({mini, cnt});
    } else {
      vm.push_back({mini - cnt, cnt});
    }
  }
  sort(vm.begin(), vm.end());
  sort(vp.begin(), vp.end());
  if (sum != 0) {
    cout << "No" << endl;
    return 0;
  }
  for (int i = 0; i < vp.size(); i++) {
    if (sum + vp[vp.size() - 1 - i].first < 0) {
      cout << "No" << endl;
      return 0;
    }
    sum += vp[vp.size() - 1 - i].second;
  }
  for (int i = 0; i < vm.size(); i++) {
    if (sum + vm[i].first + vm[i].second < 0) {
      cout << "No" << endl;
      return 0;
    }
    sum += vm[i].second;
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 11224
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define REP(i, n) for(int i = 0; i < (int)(n); i++)


int main() {

  ll N, K;
  cin >> N >> K;
  double val = 0;
  vector<ll> d(N);
  int maxt;
  REP(i, N){
    ll j = i + 1;
    ll count = 0;
    while(j < K) {
      j *= 2;
      count++;
    }
    if (i == 0) maxt = count;
    d[i] = count;
    val += pow(2, maxt - count);
    //cout << count;
  }

  val /= (double)N;
  val /= (double)pow(2, maxt);

  //cout << val << endl;
  printf("%.12f\n", val);
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>   
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
     
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}
using Graph = vector<vector<int>>;
Graph G;

vector<ll> nanagogo;
ll n;

bool checker755(ll m){
    set<int> se;
    while(m > 0){
        se.insert(m % 10);
        m /= 10;
    }
    return se.size() == 3 ? true : false;
}

void dfs(ll m, int digits){
    if(m <= n and checker755(m)) nanagogo.push_back(m);
    if(digits <= 8){
        dfs(m * 10 + 3, digits + 1);
        dfs(m * 10 + 5, digits + 1);
        dfs(m * 10 + 7, digits + 1);
    }
}

int main(){
    cin >> n;
    dfs(0, 0);
    cout << nanagogo.size() << endl;
}

Measured memory_bytes: 3708
#include <stdio.h>
#include <string.h>

int main(){
 int A, B;
 char S[25];
 char T[25];
 char U[25];
 
 scanf("%s %s", S, T);
 scanf("%d %d", &A, &B);
 scanf("%s", U);
 
 if(strcmp(U,S)==0){
  printf("%d %d", A-1, B);
 }else if(strcmp(U,T)==0){
  printf("%d %d", A, B-1);
 }
 return 0;
}

Measured memory_bytes: 1736
(N, M, K), As, Bs = readlines.map{_1.split.map(&:to_i)}

s = ->(a){a.each_with_object([0]){|e, o| o << o.last + e}.take_while{_1 <= K}}
as, bs = s[As], s[Bs]
ma = ->(x, y){x > y ? x : y}
ans, j = 0, bs.size - 1
as.each_with_index do |a, i|
  j -= 1 while bs[j] > K - a
  ans = ma[i + j, ans]
end
puts ans

Measured memory_bytes: 45116
S = int(input())
array = []
array.append(S)

while True:
  count = 0
  if S % 2 == 0:
    S = S / 2
    array.append(S)
  else:
    S = 3 * S + 1
    array.append(S)
  for i in range(len(array)):
    if S == array[i]:
      count += 1
      if count == 2:
        print(i + 1)
        exit()
        

Measured memory_bytes: 9180
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll N = 1e9+7;
const int n_max = 1e5+10;

int main(){
    int n,k; cin >> n >> k;
    vector<int> a(n);
    ll sum = 0;
    priority_queue<ll> q;
    priority_queue<ll> qtemp;
    priority_queue<ll> clear;
    rep(i,n){
        cin >> a[i];
        sum += a[i];
        // q.push(a[i]);
    }
    priority_queue<ll> pq;
    for(int i = 1;i <= sqrt(sum); i++){
        if(sum % i == 0){
            pq.push(i);pq.push(sum/i);
        }
    }
    // bool ok = true;
    int ans = 0;
    while(pq.size()){
        ll temp = pq.top();pq.pop();
        ll tsum = 0;
        rep(i,n){
            q.push(a[i]%temp);
            tsum += a[i]%temp;
        }
        qtemp = q;
        ll count= 0;
        rep(i,tsum/temp){
            ll temp2 = qtemp.top();qtemp.pop();
            count += temp - temp2;
        }
        if(count <= k) {
            ans = temp;
            break;
        }
        q = clear;
    }
    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;

bool odd_digit(int i)
{
    int cnt = 0;
    while(i)
    {
        i /= 10;
        cnt++;
    }
    if(cnt & 1)
        return true;
    return false;
}


int main()
{
  int n;
  cin >> n;
  int res = 0;
  for(int i = 1; i <= n; i++)
  {
      if(odd_digit(i))
        res++;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 888
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define MAXN 131072
#define INF 1000000000000000000LL
using namespace std;
typedef long long LL;
struct node
{
	LL in,out;
	node(){};
	node(LL _in,LL _out):in(_in),out(_out){};
};
vector<node> nd[MAXN+5],tmp1,tmp2;
int n,fa[MAXN+5],ch[MAXN+5][2],d[MAXN+5];
LL dep[MAXN+5];
LL lim;
void vector_merge(vector<node> &G,vector<node> &l,vector<node> &r)
{
	G.clear();
	int siz1=l.size(),siz2=r.size(),p1=0,p2=0;
	if(siz2==0)
		return;
	while(p1<siz1)
	{
		while(p2<siz2&&l[p1].out+r[p2].in<=lim) p2++;
		if(p2)	p2--;
		if(l[p1].out+r[p2].in<=lim)
			G.push_back(node(l[p1].in,r[p2].out));
		p1++;
	}
}
void Insert(vector<node> &G,node &x)
{
	int siz=G.size();
	if(siz==0)	G.push_back(x);
	else if(G[siz-1].out>x.out)	G.push_back(x);
}
void merge_sort(vector<node> &l,vector<node> &r,vector<node> &G)
{
	G.clear();
	int siz1=l.size(),siz2=r.size();
	int p1=0,p2=0;
	while(p1<siz1||p2<siz2)
	{
		if(p2>=siz2||(p1<siz1&&l[p1].in<r[p2].in))
			Insert(G,l[p1++]);
		else
			Insert(G,r[p2++]);
	}
}
void DFS(int u)
{
	if(!d[u])
	{
		nd[u].clear();
		nd[u].push_back(node(dep[u],dep[u]));
		return;
	}
	int ls=ch[u][0],rs=ch[u][1];
	DFS(ls);DFS(rs);
	lim+=2LL*dep[u];
	vector_merge(tmp1,nd[ls],nd[rs]);
	vector_merge(tmp2,nd[rs],nd[ls]);
	merge_sort(tmp1,tmp2,nd[u]);
	lim-=2LL*dep[u];
}
int main()
{
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		scanf("%d %lld",&fa[i],&dep[i]);
		ch[fa[i]][d[fa[i]]++]=i;
		dep[i]+=dep[fa[i]];
	}
	LL L=0,R=INF;
	while(L<R)
	{
		lim=(L+R)/2LL;
		DFS(1);
		if(nd[1].size()!=0)
			R=lim;
		else
			L=lim+1;
	}
	printf("%lld\n",R);
	return 0;
}

Measured memory_bytes: 29924
from fractions import gcd

n = int(input())
A = list(map(int, input().split()))

# 入力が2つなら最大値が解となる
if n == 2:
    print(max(A))
    exit()

# A1 A2 A3の最大公約数はA1とA2の最大公約数とA3の最大公約数と同値になるので、
# 左右から順番に最大公約数を求めていく。
# 初期値を代入する（右からは0番目にAの最初の要素を、左からは末尾にAの末尾の要素）
gcdL = [0]*n
gcdR = [0]*n
gcdL[0] = A[0]
gcdR[-1] = A[-1]

for i in range(1, n):
    gcdL[i] = gcd(gcdL[i-1], A[i])
    gcdR[-i-1] = gcd(gcdR[-i], A[-i-1])

# A0～AiとAi+1～Anの最大公約数を求めていく
# 最大値が解となる
ans = gcdR[1]
for i in range(1, n-1):
    tmp = gcd(gcdL[i-1], gcdR[i+1])
    ans = max(ans, tmp)
ans = max(ans, gcdL[-2])

print(ans)


Measured memory_bytes: 16152
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long LL;

inline int read()
{
	char c=getchar();int num=0,f=1;
	for(;!isdigit(c);c=getchar())
		f=c=='-'?-1:f;
	for(;isdigit(c);c=getchar())
		num=num*10+c-'0';
	return num*f;
}

const int N=1e5+5;

int n,E,T,x[N];
LL f[N];

int main()
{
	n=read(),E=read(),T=read();
	for(int i=1;i<=n;++i) x[i]=read();
	LL mn=1ll<<60;
	for(int i=1,j=0;i<=n;++i)
	{
		while(T<=2*(x[i]-x[j+1])) mn=min(mn,f[j]-2*x[j+1]),++j;
		if(i!=j) f[i]=min(mn+2*x[i],f[j]+T);
		else f[i]=mn+2*x[i];
	}
	cout<<f[n]+E;
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;
ll fat[201010];

ll fexp(ll x, ll y){
	ll ret = 1LL;
	x %= MOD;
	while(y){
		if(y & 1LL) ret = (ret * x) % MOD;
		y /= 2LL;
		x = (x * x) % MOD;
	}
	return ret;
}

void compute(int n, int m){
	fat[0] = 1LL;
	for(ll i = 1 ; i <= (long long)(n + m) ; i ++)
		fat[i] = (fat[i - 1] * i) % MOD;
	return;
}

ll bn(ll n, ll k){
	if(k > n) return 0LL;
	return ((((fat[n]*fexp(fat[k],MOD-2)) % MOD)*fexp(fat[n-k],MOD-2))%MOD);
}

int main(){
	
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, a, b;
	cin >> n >> m >> a >> b;
	
	compute(n, m);
	
	ll bad = 0LL;
	for(int i = n - a ; i < n ; i ++){
		ll val = bn(i + b - 1, b - 1);
		int h = n - 1 - i;
		int w = m - 1 - b;
	//	cout << val << " " << calc(n - i) << "\n";
		bad = (bad + ((bn(h + w, w)*val) % MOD)) % MOD;
	}
	
	//cout << bad << "\n";
	
	//cout << bn(n - 1 + m - 1 , m - 1) << "\n";
	
	cout << (bn(n - 1 + m - 1, m - 1) - bad + MOD) % MOD << "\n";
	
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int n;
  cin >> n;
  vector<vector<int>> a(n, vector<int>(n));
  rep(i, n) {
    rep(j, n) {
      cin >> a[i][j];
    }
  }

  ll ans = 0;
  rep(i, n) {
    FOR(j, i + 1, n) {
      bool flag = true;
      rep(k, n) {
        if (i == k || k == j) continue;
        if (a[i][j] > a[i][k] + a[k][j]) {
          cout << -1 << endl;
          return 0;
        }
        else if (a[i][j] == a[i][k] + a[k][j]) flag = false;
      }
      if (flag) ans += a[i][j];
    }
  }
  cout << ans << endl;


  
  return 0;
}

Measured memory_bytes: 640
//
//  main.cpp
//  CoderWork
//
//  Created by Minoru Hayashi on 2020/02/29.
//  Copyright © 2020 Minoru Hayashi. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for (int i=0; i<(n); i++)
#define REP2(i,x,n) for (int i=x; i<(n); i++)
#define ALL(n) begin(n), end(n)

using ll = long long;

template<class T> inline bool chmin(T& a, T b){ if(a>b){a=b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b){ if(a<b){a=b; return 1;} return 0;}

// const ll INF = 1LL<<60;
// const ll MOD = 1000000007;

//#define __DBG__




void solve(void){
  
  string S, R;
  int Q;
  cin >> S >> Q;
  
  string Head="";
  string Tail="";
  
  int flag=0;
    
  REP(i,Q){
    int T, F;
    char C;

    cin >> T;
    if(T==1){
      flag=(flag+1)%2;
    }
    else
    {
      //T=2
      cin >> F >> C;
      if(flag==0){
        if(F==1){
          // S F1
          Head=C+Head;
        }
        else
        {
          // S F2
          Tail = Tail+C;
        }
      }
      else
      {
        // flag=1
        if(F==1){
          // R F1
          Tail=Tail+C;
        }
        else
        {
          // R F2
          Head=C+Head;
        }
      }
    }
  }
  
  S=Head+S+Tail;
  
  
  if(flag){
    reverse(ALL(S));
  }

  cout << S << endl;

  
  return;
}

int main(int argc, const char * argv[]) {



    // cinを高速にするためのおまじない
    cin.tie(0);
    ios::sync_with_stdio(false);
  
    solve();
 
    return 0;
}





Measured memory_bytes: 1320
n,w=map(int,input().split())
dp=[999999999999999]*(100001)
dp[0]=0
for i in range(n):
	wt,val=map(int,input().split())
	for j in range(100000,val-1,-1):
		dp[j]=min(dp[j],dp[j-val]+wt)
for i in range(100000,-1,-1):
	if dp[i]<=w:
		print(i)
		exit()

Measured memory_bytes: 41580
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N, M;
	cin >> N >> M;
	vector< pair<int,int> > A(N);
	for(int i =0; i < N; i++) {
		cin >> A[i].ff;
		A[i].ss =i;
	}
	sort(begin(A), end(A));
	vector< vector<int> > G(N);
	for(int i =0; i < M; i++) {
		int x,y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	queue<int> q;
	vector<int> comp(N, -1);
	int C =0;
	for(int i =0; i < N; i++) if(comp[i] == -1) {
		comp[i] =i;
		q.push(i);
		while(!q.empty()) {
			ALL_THE(G[q.front()], it) if(comp[*it] == -1) {
				comp[*it] =i;
				q.push(*it);
			}
			q.pop();
		}
		C++;
	}

	vector<int> cnt(N, 0);
	int rem =(N-1-M)*2, cntc =0;
	cat ans =0;
	for(int i =0; i < N; i++) {
		if(cnt[comp[A[i].ss]] == N-1-M) continue;
		if(cnt[comp[A[i].ss]] > 0 && rem-1+cntc < C) continue;
		if(cnt[comp[A[i].ss]] == 0) cntc++;
		ans +=A[i].ff;
		cnt[comp[A[i].ss]]++;
		rem--;
		if(rem == 0) break;
	}

	if(rem) {
		cout << "Impossible\n";
		return 0;
	}
	cout << ans << "\n";
	return 0;}

// look at my code
// my code is amazing


Measured memory_bytes: 7296
#include<bits/stdc++.h>
using namespace std;

long long a[100005],b[100005],c[100005],d[1000005];

int main() {
    int x,y,A,B,C,p=0,i;
    scanf("%d%d%d%d%d",&x,&y,&A,&B,&C);
    for(i=0; i<A; i++)
        scanf("%lld",&a[i]);
    for(i=0; i<B; i++)
        scanf("%lld",&b[i]);
    for(i=0; i<C; i++)
        scanf("%lld",&c[i]);
    sort(a,a+A);
    sort(b,b+B);
    sort(c,c+C);
    for(i=A-1;i>=A-x;i--){
        d[p++]=a[i];
    }
    for(i=B-1;i>=B-y;i--){
        d[p++]=b[i];
    }
    sort(d,d+p);
    int j=C-1;
    for(i=0;i<p;i++){
        if(c[j]>d[i]){
             d[i]=c[j];
             j--;
        }
    }
    long long sum=0;
    for(i=0;i<p;i++)
        sum+=d[i];
    printf("%lld\n",sum);
}


Measured memory_bytes: 5632
import sys
input = sys.stdin.readline


def main():
    N, L = map(int, input().split())
    S = []
    for _ in range(N):
        S.append(input().strip())
    S.sort()
    ans = ""
    for s in S:
        ans += s
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include<iostream>
using namespace std;

int main()
{
    int n; cin>>n ;

    int digit = to_string(n).length();
    int ans = 0;
    
    // 1桁目
    if (1 < digit)
    {
        ans += 9;
    }
    else
    {
        // 1桁の値
        cout << n << endl;
        return 0;
    }

    // 2桁目
    if(2 < digit)
    {
    }
    else
    {
        cout << ans << endl;
        return 0;   
    }
    
    // 3桁目
    if(3 < digit)
    {
        ans += 900;
    }
    else
    {
        ans += (n - 99);
        cout << ans << endl;
        return 0;   
    }

    // 4桁目
    if(4 < digit)
    {
        
    }
    else
    {
        cout << ans << endl;
        return 0;   
    }

    // 5桁目
    if(5 < digit)
    {
        ans += 90000;
        cout << ans << endl;
        return 0;
    }
    else
    {
        ans += (n - 9999);
        cout << ans << endl;
        return 0;   
    }


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;

#define fast_cin() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000000
#define ll long long
#define db double
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)

#define vl vector<ll>
#define vs vector<string>

#define mapll map<ll,ll>
#define mapss map<string,string>
#define mapsl map<string,ll>
#define mapls map<ll,string>

#define pll pair<ll,ll>
#define pss pair<string,string>
#define psl pair<ll,string>
#define pls pair<string,ll>

#define minheap priority_queue<ll>
#define maxheap priority_queue<ll,vector<ll> ,greater<ll>>

#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
const ll mod=1e9 + 7;


ll takemod(ll a) {
    return ((a%mod)+mod)%mod;
}

ll gcd(ll a, ll b) { 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);        
}

ll fast_exp(ll base, ll expo) {
    ll res=1;
    while(expo>0) {
        if(expo&1) res=(res*base)%mod;
        base=(base*base)%mod;
        expo>>=1;}
    return res;
}

ll modinv(ll a) {
    return takemod(fast_exp(takemod(a), mod-2));
}



signed main() 
{
    fast_cin();
    vl v1(4);
    For(i,0,4)
    {
        cin>>v1[i];
    }
    sort(v1.begin(),v1.end());
    if(v1[0]==1 and v1[1]==4 and v1[2]==7 and v1[3]==9)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;    
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define MAX(x,y) x=max(x,y)
#define MIN(x,y) x=min(x,y)
#define inf 0x3f3f3f3f
using namespace std;

const int N=400005;

int n,v,g[N*2],f[N*2],bin[25],tot,len[25],lef[25][N],rig[25][N],a[N],bel[N],p1[N],p2[N];
bool ans[N];

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void dp()
{
    bin[0]=1;
    for (int i=1;i<=tot;i++) bin[i]=bin[i-1]*2;
    for (int i=0;i<bin[tot];i++) g[i]=n+1;
    for (int i=0;i<bin[tot];i++)
        for (int j=0;j<=tot;j++)
            if (!(i&bin[j])) MAX(f[i+bin[j]],rig[j][f[i]+1]),MIN(g[i+bin[j]],lef[j][g[i]-1]);
    for (int i=0;i<bin[tot];i++)
    {
        int l=f[i],r=g[i^(bin[tot]-1)];
        if (l+1>=r)
        {
            for (int j=1;j<=n;j++) ans[j]=1;
            return;
        }
        if (p1[bel[l+1]]<=l+1&&p2[bel[l+1]]>=r-1) ans[bel[l+1]]=1;
    }
}

int main()
{
    n=read();v=read();
    for (int i=1;i<=n;i++) a[i]=read();
    tot=0;len[0]=0;
    while (v) len[++tot]=v,v>>=1;
    sort(len,len+tot+1);
    memset(lef,inf,sizeof(lef));
    for (int i=0;i<tot;i++)
        for (int j=1;j<=n;j++)
        {
            int l=j;
            while (l<n&&a[l+1]-a[l]<=len[i]) l++;
            rig[i][j]=l;lef[i][l]=j;j=l;
        }
    int id=0;
    for (int j=1;j<=n;j++)
    {
        int l=j;bel[j]=++id;
        while (l<n&&a[l+1]-a[l]<=len[tot]) l++,bel[l]=id;
        p1[id]=j;p2[id]=l;j=l;
    }
    dp();
    for (int i=1;i<=n;i++) puts(ans[bel[i]]?"Possible":"Impossible");
    return 0;
}
/*
考虑最后走过的区间肯定只有log段，那么我们就状压表示从左到右（和从右到左）用了哪些段能走到的最远距离 
*/

Measured memory_bytes: 80256
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
template<class T,class Y>T LCM(T a,Y b){return (a*b)/GCD(a,b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

using vi=vector<int>;
using vii=vector<vi>;

#define REP(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()
#define decimal(x) fixed<<setprecision(x)

int main(){
    int N,M;
    cin>>N>>M;
    vector<vector<int>> Graph(N,vector<int>());
    vector<int> memo(N,-1);
    rep(i,M){
        int a,b;
        cin>>a>>b;
        a--,b--;
        Graph[a].pb(b);
        Graph[b].pb(a);
    }
    queue<int> que;
    vector<bool> dist(N,false);
    que.push(0);
    while(!que.empty()){
        int a=que.front();
        que.pop();
        for(auto x:Graph[a]){
            if(dist[x])continue;
            dist[x]=true;
            memo[x]=a;
            que.push(x);
        }
    }
    REP(i,1,N){
        if(memo[i]==-1){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    REP(i,1,N)cout<<memo[i]+1<<endl;
    return 0;
}

//a=97,z=122

Measured memory_bytes: 10168
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
  	cin>>n>>k;
  	vector<int>vec1(n);
  	vector<int>vec2(0);
  	for(int i=0;i<n;i++){
    cin>>vec1.at(i);
    if(vec1.at(i)>=k){
    vec2.push_back(vec1.at(i));
    }
    }
  	cout<<vec2.size()<<endl;
}

Measured memory_bytes: 1148
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)n; i++)
#define PI 3.14159265358979323846
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define pll pair<long long, long long>
using namespace std;
using ll = long long;
using ld = long double;

// グローバル変数（入力）
ll n;

void input() { 
  cin >> n;
}

void solve() {
  cout << (ll)ceil(n/1000.0)*1000.0 - n << endl;
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 3900
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <limits>
#include <algorithm>
#include <map>
#include <iterator>
#include <queue>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
#define rrepd(i,a,b) for (int i=(a-1);i>=(b);--i)
#define rrep(i,n) rrepd(i,n,0)
typedef long long ll;
typedef pair<int, int> P;


int main(int argc, const char * argv[]) {

  int n;
  cin >> n;
  vector<int> a;
  rep(i,n){
    int a_i;
    cin >> a_i;
    if (i%2 == 0){
      a.push_back(a_i);
    }else{
      a.insert(a.begin(), a_i);
    }
  }

  if (n%2 == 1){
    rrep(i, a.size()){
      cout << a[i] << ' ';
    }
    cout << endl;
  }else{
    rep(i, a.size()){
      cout << a[i] << ' ';
    }
    cout << endl;
  }
  return 0;
  
}

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define ll long long 


int main(){
	
	int n, w;
	cin >> n >> w;
	ll wt[n + 1], val[n + 1];
	for(int i = 0; i < n; i++){
		cin >> wt[i] >> val[i];
	}
	ll dp[n + 1][w + 1];

	for(int i = 0; i <= n; i++){
		for(int j  = 0; j <= w; j++){
			if(!i || !w) dp[i][j] = 0;
			else if( j >= wt[i - 1]) dp[i][j] = max(dp[i - 1][j], val[i - 1]  + dp[i - 1][j - wt[i - 1]]);
			else dp[i][j] = dp[i - 1][j];
		}
	}
	
	cout << dp[n][w] << endl;


}


Measured memory_bytes: 82388
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		Set<Character> set = new HashSet<Character>();
		for (int i = 0; i < k; i++) {
			set.add(sc.next().charAt(0));
		}
		sc.close();

		for (int i = n; ; i++) {
			String s = String.valueOf(i);
			boolean flg = true;
			for (int j = 0; j < s.length(); j++) {
				char ch = s.charAt(j);
				if (set.contains(ch)) {
					flg = false;
					break;
				}
			}
			if (flg) {
				System.out.println(i);
				return;
			}
		}
	}
}


Measured memory_bytes: 26708
a = input()
b = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']

for i in range(26):
    if b[i] == a:
        print('A')
        break
    elif i == 25:
        print('a')

Measured memory_bytes: 9068
#include<iostream>
#include<vector>
#define N 20

using namespace std;

int main() {

	vector<char> str(20);

	int i = 0,j;

	while(cin >> str[i]){
		i++;
	}

	for(j = i-1;j >=0;j--){
		cout << str[j];
	}
	cout << endl;
	
	return 0;
}

Measured memory_bytes: 2988
#include "bits/stdc++.h"
#define rep(i, j) for (int i = 0; i < j; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using ull = unsigned long long;

ll gcd(ll x, ll y);
int fac(ll n, vector<int> num);

const int INF = 1001001001;

//mint�p�̕ϐ� (10��9��)
const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }

int main() {
    int n;
    cin >> n;
    vector<ull> t(n);
    rep(i, n) cin >> t[i];

    ll ans = t[0];
    for (int i = 1; i < n; i++) {
        ans = t[i] / gcd(ans, t[i]) * ans;
    }
    

    cout << ans << endl;
    return 0;
}

/*���C�u�����ő����*/
//���[�O���b�h�̌ݏ��@
ll gcd(ll x, ll y) {
    ll num[3];
    num[0] = (x > y) ? x : y;
    num[1] = (x <= y) ? x : y;
    num[2] = num[0] % num[1];

    while (num[2]) {
        num[0] = num[1];
        num[1] = num[2];
        num[2] = num[0] % num[1];
    }

    return num[1];
}

/*�f��������*/
//���색�C�u����
int fac(ll n, vector<int> num) {
    ll kazu = n;
    for (int i = 2; i <= sqrt(n); i++) {
        while (1) {
            if (kazu % i != 0) break;

            kazu /= i;
            num[i]++;
        }
    }
    if (kazu == n && n != 1) return 1;
    int ans = 0;
    if (kazu != 1) ans++;
    for (int i = 2; i <= sqrt(n); i++) {
        for (int j = 1; j <= num[i]; j++) {
            num[i] -= j;
            ans++;
        }
    }
    return ans;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n);++i)
using namespace std;
using ll = long long; 
using P = pair<int,int>;

int main(void){
  string s;
  cin >> s;
  if(s=="AAA" ||s== "BBB")cout << "No" <<endl;
  else cout << "Yes" <<endl;
return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

struct Cat{
    int id, x, width;
};

int W, Q;
int cats[110];

int whereCatSleeps(int width){
    for(int i=0,j=0;i<W;){
        for(;j<W&&cats[j]==-1;j++);
        if(j-i >= width){return i;}
        j += 1;
        i = j;
    }
    return -1;
}

int main(){
    while(std::cin >> W >> Q, W || Q){
        std::fill(cats, cats+110, -1);

        REP(i, Q){
            char c;
            std::cin >> c;

            if(c == 's'){
                int id, width;
                std::cin >> id >> width;

                int pos = whereCatSleeps(width);
                if(pos >= 0){
                    std::cout << pos << std::endl;
                    for(int i=pos;i<pos+width;i++){cats[i] = id;}
                }else{
                    std::cout << "impossible" << std::endl;
                }
            }else{
                int id;
                std::cin >> id;

                for(int i=0;i<W;i++){
                    if(cats[i] == id){
                        while(i<W&&cats[i]==id){cats[i] = -1; i += 1;}
                    }
                }
            }
        }

        std::cout << "END" << std::endl;
    }
}

Measured memory_bytes: 1156
#[allow(unused_imports)]
use proconio::{fastout, input};

#[fastout]
fn main() {
    input!(n: usize, sp: [(String, usize); n]);

    let mut aaa = Vec::new();

    for i in 0..n {
        aaa.push(((&sp[i].0, sp[i].1), i));
    }
    aaa.sort_by(|a, b| {
        if (a.0).0 != (b.0).0 {
            (b.0).0.cmp((&a.0).0)
        } else {
            (a.0).1.cmp(&((b.0).1))
        }
    });

    for v in aaa.iter().rev() {
        println!("{}", (v.1) + 1);
    }
}


Measured memory_bytes: 2124
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod = 998244353;
const int N = 1e5 + 5;

int main()
{
	ios::sync_with_stdio(false);
	cout.tie(NULL);
	int n;
	cin >> n;
	int z = sqrt(n),sum = (2*(n-2)+1);
	for(int i = 2; i*i < n; i++){
		int t = n/i-i;
		if(n % i == 0)
			t--;
		sum = sum + 1 + t*2;
	}
	cout << sum << endl;
	return 0;  
} 

Measured memory_bytes: 3684
#include <bits/stdc++.h>

using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using f64 = double;
using f80 = long double;

#define FOR(v, a, b) for(i64 v = (a); v < (b); ++v)
#define FORE(v, a, b) for(i64 v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(i64 v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

using namespace std;

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T> void pout(const T &value){std::cout << value << "\n";}
template <typename T, typename ...Args> void pout(const T &value, const Args&... args){std::cout << value << " ";pout(args...);}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}
template <typename T> auto make_vector(int n, int m, const T &value){return vector<vector<T>>(n, vector<T>(m, value));}


struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;



int main(){
  i64 x;
  while(cin >> x){
    i64 ans = 0;

    ans += (x / 500) * 1000;
    x %= 500;

    ans += (x / 5) * 5;

    pout(ans);
  }


  return 0;
}


Measured memory_bytes: 256
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define L
#define LL long long
using namespace std;

inline int gi() {
  char cj = getchar();
  int ans = 0, f = 1;
  while (cj < '0' || cj > '9') { if (cj == '-') f = -1; cj = getchar();}
  while (cj >= '0' && cj <= '9') ans = ans * 10 + cj - '0', cj = getchar();
  return f * ans;
}

char s[200];

int main() {
  //freopen("i18n.in", "r", stdin);
  //freopen("i18n.out", "w", stdout);
  scanf("%s", s);
  int l = strlen(s);
  cout << s[0] << l - 2 << s[l - 1] << endl;
  return 0;
}


Measured memory_bytes: 256
mod=998244353
k,n=map(int,input().split())

def modinv(n):
    return pow(n,mod-2,mod)
m=n+k
Fact=[1]
for i in range(1,m+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(m+1)
Finv[-1]=modinv(Fact[-1])
for i in range(m-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod
def comb(n,r):
    if r<0 or n<r:
        return 0
    return Fact[n]*Finv[r]*Finv[n-r]%mod
def hcomb(n,r):
    return comb(n+r-1,r)
Pow=[1]*(k+1)
for i in range(k):
    Pow[i+1]=Pow[i]*2%mod
def solve(x):
    ret=0
    if x%2:
        p=x//2
        for q in range(p+1):
            ret+=Pow[q]*comb(p,q)*hcomb(k-2*p+q,n-q)
            ret%=mod
    else:
        p=x//2-1
        for q in range(p+1):
            ret+=Pow[q]*comb(p,q)*(hcomb(k-2*p+q-1,n-q)+hcomb(k-2*p+q-1,n-q-1))
            ret%=mod
    return ret
Ans=[]
for i in range(2,k+2):
    Ans.append(solve(i))
print(*Ans,sep='\n')
print(*reversed(Ans[:k-1]),sep='\n')

Measured memory_bytes: 52060
#include <bits/stdc++.h>


using namespace std;

#define re return
#define sz(a) (int)a.size()
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
#define re return
#define forn(i, n) for (int i = 0; i < int(n); i++)


typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long double ld;

ll n, ans;
vector<ll> a, b;

int main() {
	iostream::sync_with_stdio(0);
	//freopen("a.in", "r", stdin);
	cin >> n;
	a.resize(n);
	b.resize(n);
	forn (i, n)
		cin >> a[i] >> b[i];
	for (int i = n - 1; i >= 0; i--) {
		ll ck = (a[i] + ans) % b[i];
		if (ck > 0) {
			ans += b[i] - ck;
		}
	}
	cout << ans;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);


	int N = getint();

	int kotae = getint();
	rep1(i, N - 1) {
		kotae = __gcd(getint(), kotae);
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> int_pair;
typedef pair<ll,ll> ll_pair;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
const int N=100;
const int W=10000;
int n,w,v[N],wi[N];
int dp[N+1][W+1];

int main(){
	FOR(i,0,N+1)FOR(j,0,W+1)dp[i][j]=0;
	cin>>n>>w;
	FOR(i,0,n){
		cin>>v[i]>>wi[i];
	}
	FOR(i,0,n){
		FOR(j,0,w+1){
			if(j<wi[i]){
				dp[i+1][j]=dp[i][j];
			}else{
				dp[i+1][j]=max(dp[i][j],dp[i][j-wi[i]]+v[i]);
			}
		}
	}
	cout<<dp[n][w]<<endl;


	return 0;
}


Measured memory_bytes: 7056
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
    int N, T, A;
    cin >> N >> T >> A;

    vector<pair<int, double>> t(N);
    for (int n = 0; n < N; n++) {
        int h;
        cin >> h;
        t[n].first = n;
        t[n].second = abs(T - h * 0.006 - A);
    }

    sort(t.begin(), t.end(), [](const auto& a, const auto& b) { return a.second < b.second; });

    cout << t[0].first + 1 << endl;

    return 0;
}


Measured memory_bytes: 256
//----------------------------おまじない
#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")
//----------------------------
#define FOR(i,j,n) for (int i=(j);i<(n);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define REPN(i,n) for (int i=(n);i>=0;i--)
#define I(n) scanf("%d", &(n))
#define LL(n) scanf("%lld", &(n))
#define pb(n) push_back((n))
#define mp(i,j) make_pair((i),(j))
#define eb(i,j) emplace_back((i),(j))
#include <bits/stdc++.h>
using namespace std;

//------------------------------typedef集
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
typedef vector<vpi> vvpi;
typedef vector<vvi> vvvi;
typedef long long ll;
const int mod = 1000000007;

ll n,dp,ret;
vi q;
string s;

int main(){
    cin >> n;
    cin >> s;
    cin >> s;
    int cont = 0;
    char stack = s[0];
    for (auto c: s){
        if (c==stack) {
            cont++;
        } else{
            q.pb(cont);
            cont = 1;
            stack = c;
        }
    }
    q.pb(cont);

    ret = q[0]==1 ? 3 : 6;
    FOR(i,1,q.size()){
        if(q[i-1]==1 && q[i]==1) ret *= 2;
        if(q[i-1]==1 && q[i]==2) ret *= 2;
        if(q[i-1]==2 && q[i]==1) ret *= 1;
        if(q[i-1]==2 && q[i]==2) ret *= 3;
        ret %= mod;
    }
    cout << ret << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
int mod(ll a){
    int c=a%1000000007;
    if(c>=0)return c;
    else return c+1000000007;
}
typedef pair<int,int> i_i;


int main(){
    int q;cin>>q;
    while(q){
        char s[1005],t[1005];cin>>s>>t;
        ll ls=strlen(s),lt=strlen(t);
        for(ll i=ls-1;i>=0;i--)s[i+1]=s[i];
        for(ll j=lt-1;j>=0;j--)t[j+1]=t[j];
        int dp[ls+1][lt+1];
        for(int i=0;i<=ls;i++)dp[i][0]=0;
        for(int j=0;j<=lt;j++)dp[0][j]=0;
        for(int i=1;i<=ls;i++){
            for(int j=1;j<=lt;j++){
                if(s[i]==t[j])dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        cout<<dp[ls][lt]<<endl;
        q--;
    }
    
    return 0;
}








Measured memory_bytes: 7004
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func mpow(x int, n int) int {
	result := 1
	for n != 0 {
		if n&1 == 1 {
			result *= x
			result %= 1000000007
		}
		x *= x
		x %= 1000000007
		n >>= 1
	}
	return result
}

func mcomb(n int, k int) int {
	a := 1
	b := 1
	for i := 0; i < k; i++ {
		a *= n - i
		a %= 1000000007
		b *= i + 1
		b %= 1000000007
	}
	return a * mpow(b, 1000000005) % 1000000007
}

func main() {
	n := readInt()
	a := readInt()
	b := readInt()

	result := mpow(2, n) - 1
	result -= mcomb(n, a)
	result += 1000000007
	result %= 1000000007
	result -= mcomb(n, b)
	result += 1000000007
	result %= 1000000007
	fmt.Println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
const int mx=40;
double x[mx],y[mx],z[mx];
const double eps=1e-4;
double d(int i,int j){
   return sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2)+pow(z[i]-z[j],2));
}
bool eq(double x,double y){
   return fabs(x-y)<eps;
}
int main(){
   int t,n;
   scanf("%d",&t);
   double qr,rp,pq;
   while(t--){
      scanf("%lf %lf %lf",&qr,&rp,&pq);
      scanf("%d",&n);
      for(int i=0;i<n;i++){
         scanf("%lf %lf %lf",x+i,y+i,z+i);
      }
      int p,q,r;
      for(int i=0;i<n;i++){
         for(int j=0;j<n;j++) if(j!=i){
            for(int k=0;k<n;k++) if(k!=i && k!=j){
               double l1=d(i,j);
               double l2=d(j,k);
               double l3=d(k,i);
               double r1=l1/qr;
               double r2=l2/rp;
               double r3=l3/pq;
               if(eq(r1,r2)&&eq(r1,r3)&&eq(r2,r3)){
                  q=i,r=j,p=k;   
               }
            }
         }
      }
      printf("%d %d %d\n",p+1,q+1,r+1);
   }
   return 0;
}

Measured memory_bytes: 1228