akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// std::ios::sync_with_stdio(false);

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

map<int,int> dp[2];

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    int N;
    while (cin >> N) {
        int cur,nxt; cur = 0; nxt = 1;
        dp[0].clear();
        dp[cur][0] = 0;
        FOR(_,0,N) {
            int s; cin >> s;
            dp[nxt].clear();
            FOR_ALL(i,dp[cur]) {
                const int k = i->first;
                const int v = i->second;
                const int K = (k+s) % 10;
                const int V = v+s;
                dp[nxt][K] = max(dp[nxt][K], V);
                dp[nxt][k] = max(dp[nxt][k], v);
            }
            swap(cur,nxt);
        }
        int ans = 0;
        FOR_ALL(i,dp[cur]) {
            int v = i->second;
            if (v % 10 == 0)
                v = 0;
            ans = max(ans,v);
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f(i,x,n) for(int i=x;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200005,INF=1<<30;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        int N,M;cin>>N>>M;
        if(N+M==0) break;
        
        vector<int> A(M);
        
        for(int i=0;i<N;i++){
            int a,b;cin>>a>>b;
            a--;
            A[a]=max(A[a],b);
        }
        
        int sum=0;
        
        for(int i=0;i<M;i++){
            sum+=A[i];
        }
        
        cout<<sum<<endl;
    }
}



Measured memory_bytes: 3028
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int n, a, b, ans=0;
	cin >> n >> a >> b;
	for(int i=1; i<=n; i++){
		int tmp=i,sum=0;
		while(tmp){
			sum += tmp%10;
			tmp /= 10;
		}
		if(sum>=a && sum<=b)
			ans += i;
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> d(n);
    for(int i=0; i<n; i++){
        cin>>d.at(i);
    }
    sort(d.begin(),d.end());
    int ans=d.at(n/2)-d.at(n/2-1);
    cout<<ans<<endl;

}

Measured memory_bytes: 3756
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if( a < b ){
			int c = a ;
			a = b ;
			b = c; //swap
		}
		for(int i = 0 ; i  < a ; i++){
			System.out.print(b);
		}
	}
}


Measured memory_bytes: 21716
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> H(N,0);
	for (int i = 0; i < N; i++) cin >> H[i];
	sort(H.begin(), H.end());
	long long ans = 0;
	for (int i = 0; i < N - K; i++) ans += H[i];
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<string.h>
#define N 1000

int main(void)
{
  int i, j, n, t = 0, h = 0, len_t = 0, len_h = 0, len = 0;
  char T[N][101], H[N][101];

  scanf("%d", &n);

  for(i = 0; i < n; i++) {
    scanf("%s %s", T[i], H[i]);
    len_t = strlen(T[i]);
    len_h = strlen(H[i]);
    if(strcmp(T[i], H[i]) == 0) t ++, h++;

    for(j = 0; (len_t > len_h) ? T[i][j] : H[i][j] != '\0'; j++) {
      if(T[i][j] > H[i][j]) {
	t+= 3;
	break;
      }
      if(T[i][j] < H[i][j]) {
	h += 3;
	break;
      }
    }
  }

  printf("%d %d\n", t, h);

  return 0;
}

Measured memory_bytes: 808
def main():
    L, *A = map(int, open(0))

    D = [(2, 1), (1, 0), (0, 1)]

    s0 = s1 = s2 = s3 = s4 = 0

    for a in A:
        e, o = D[(a - 1) % 2 + 1 if a else 0]

        s0 += a
        s1 = s0 if s0 < s1 + e else s1 + e
        s2 = s1 if s1 < s2 + o else s2 + o
        s3 = s2 if s2 < s3 + e else s3 + e
        s4 = s3 if s3 < s4 + a else s4 + a

    print(min(s0, s1, s2, s3, s4))

if __name__ == '__main__':
    main()


Measured memory_bytes: 11036
#include<stdio.h>
#include<math.h>
typedef struct{
  double x;
  double y;
} P;
void func(int,P,P);

int main(){
  int n;
  P start1,start2;
  start1.x=0;
  start2.x=100;
  start1.y=0;
  start2.y=0;
  scanf("%d",&n);
  printf("%.8lf %.8lf\n",start1.x,start1.y);
  func(n,start1,start2);
  printf("%.8lf %.8lf\n",start2.x,start2.y);
  return 0;
}
void func(int n,P p1,P p2){
  P s,t,u;
  if(n==0) return;
 
  s.x=p1.x+(p2.x+-p1.x)/3.0;
  s.y=p1.y+(p2.y-p1.y)/3.0;
  t.x=p1.x+2*(p2.x-p1.x)/3.0;
  t.y=p1.y+2*(p2.y-p1.y)/3.0;
  u.x=s.x+(t.x-s.x)*cos(60.0*M_PI/180.0)-(t.y-s.y)*sin(60.0*M_PI/180.0);
  u.y=s.y+(t.x-s.x)*sin(60.0*M_PI/180.0)+(t.y-s.y)*cos(60.0*M_PI/180.0);
 
  
 
  func(n-1, p1, s);
      printf("%.8lf %.8lf\n",s.x,s.y);
     func(n-1, s, u);
      printf("%.8lf %.8lf\n",u.x,u.y);
     func(n-1, u, t);
      printf("%.8lf %.8lf\n",t.x,t.y);
     func(n-1, t, p2);
}
  
  




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

const int MAXK = 1e5 + 10;
const int MOD = 1e9 + 7;

int pref[MAXK],dp[MAXK],N,K;

int calc(int a,int b)
{
	if(a < 0) a = 0;
	int ans = pref[b];
	if(a != 0) ans -= pref[a-1];
	return ans % MOD;
}
int main()
{
	cin >> N >> K;
	dp[0] = 1;
	for(int kid = 1;kid<=N;kid++)
    {
		int c;
		cin >> c;
		pref[0] = dp[0];
		dp[0] = 0;
		for(int i = 1;i<=K;i++){
			pref[i] = (pref[i-1] + dp[i]) % MOD;
		}
		for(int i = 0;i<=K;i++)
        {
			dp[i] = calc(i-c,i);
		}
	}
	int ans = dp[K];
	if(ans < 0) ans += MOD; 
	printf("%d\n",ans);
}

Measured memory_bytes: 4544
#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
    return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
    return (!b) ? a: gcd(b, a % b);
}
int poww(int a, int b){
    int res = 1;
    while (b > 0){
        if (b & 1) res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD, b >>= 1;
    }
    return res;
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int ddx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, ddy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/

ll n, x;
ll solve(ll b, ll a){
    if (b <= a){
        if (a == b) return 2 * a;
        return a + b + solve(a - b, b);
    }
    if (b % a == 0) return 2ll * b;
    ll t = b / a;
    return (2 * t + 1) * a + b % a + solve(a - (b % a), b % a);
}
void init(){
    scanf("%lld%lld", &n, &x);
}
void solve(){
    ll ans = x + solve(x, n - x);
    printf("%lld\n", ans);
}
int main(){
    int T = 1;
    while (T--){
        init();
        solve();
    }
    return 0;
}

Measured memory_bytes: 3776
n = int(input())
P = list(map(int,input().split()))
P = [int(i+1==P[i]) for i in range(n)]+[0]

ans = 0
ex = 0
for p in P:
  if p and ex:
    ans += 1
    ex = 0
  elif p:
    ex = 1
  elif ex:
    ans += 1
    ex = 0
print(ans)



Measured memory_bytes: 14008
N  = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
count = 0
monstarsum = sum(A)
for i in range(N):
  tmpwon = min(A[i],B[i])
  A[i] -= tmpwon
  A[i+1] -= min([A[i+1],B[i] - tmpwon])

ans = monstarsum - sum(A)
print(ans)

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

using namespace std;

#define LIMIT 100
typedef pair<int64_t, int64_t> ii;
typedef int64_t ll;
int gcd(ll a, ll b) { return (b==0)?a:gcd(b, a%b); }
int lcm(ll a, ll b) { ll i=(a/gcd(a,b))*b; assert(i>0); return i; }

//  ***** MAIN *****
int main(){
  //ios::sync_with_stdio(false);
  cin.tie(NULL);
  char x, y;

  cin >> x >> y;

  if(x < y){
    std::cout << '<' << std::endl;
  }
  else if (x > y){
    std::cout << '>' << std::endl;
  }
  else {
    std::cout << '=' << std::endl;
  }

  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int


// quoted from beet-aizu
template <typename T,typename E, typename F, typename G, typename H>
struct LazySegmentTree{
    //using F = function<T(T,T)>;
    //using G = function<T(T,E)>;
    //using H = function<E(E,E)>;
    int n,height;
    F f;
    G g;
    H h;
    T ti;
    E ei;
    vector<T> dat;
    vector<E> laz;
    LazySegmentTree(F f,G g,H h,T ti,E ei):
        f(f),g(g),h(h),ti(ti),ei(ei){}

    void init(int n_){
        n=1;height=0;
        while(n<n_) n<<=1,height++;
        dat.assign(2*n,ti);
        laz.assign(2*n,ei);
    }
    void build(const vector<T> &v){
        int n_=v.size();
        init(n_);
        for(int i=0;i<n_;i++) dat[n+i]=v[i];
        for(int i=n-1;i;i--)
            dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
    }
    inline T reflect(int k){
        return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
    }
    inline void eval(int k){
        if(laz[k]==ei) return;
        laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
        laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
        dat[k]=reflect(k);
        laz[k]=ei;
    }
    inline void thrust(int k){
        for(int i=height;i;i--) eval(k>>i);
    }
    inline void recalc(int k){    
        while(k>>=1)
            dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
    }
    void update(int a,int b,E x){
        thrust(a+=n);
        thrust(b+=n-1);
        for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
            if(l&1) laz[l]=h(laz[l],x),l++;
            if(r&1) --r,laz[r]=h(laz[r],x);
        }
        recalc(a);
        recalc(b);
    }
    void set_val(int a,T x){
        thrust(a+=n);
        dat[a]=x;laz[a]=ei;
        recalc(a);
    }
    T query(int a,int b){
        thrust(a+=n);
        thrust(b+=n-1);
        T vl=ti,vr=ti;
        for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
            if(l&1) vl=f(vl,reflect(l++));
            if(r&1) vr=f(reflect(--r),vr);
        }
        return f(vl,vr);
    }
};

signed main(){
    
    int n, q; cin >> n >> q;
    using T = pair<int, int>;
    using E = int;
    auto f = [](T l, T r){
        return T(l.first + r.first, l.second + r.second);
    };
    auto g = [](T l, E r){
        return T(l.first + l.second * r, l.second);       
    };
    auto h = [](E l, E r){
        return l + r;
    };

    LazySegmentTree<T, E, decltype(f), decltype(g), decltype(h)> sg(f, g, h, T(0, 0), 0);
    sg.build(vector<T>(n, T(0, 1)));
    for(int i = 0; i < q; i++){
        int com; cin >> com;
        if(!com){
            int s, t, x; cin >> s >> t >> x;
            sg.update(s - 1, t, x);
        }else{
            int s, t; cin >> s >> t;
            cout << sg.query(s - 1, t).first << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 10480
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;

vector<int> moji[26];

int ctoi(char c){
	return c - 'a';
}

int main(){
	string s, t;
	cin >> s >> t;

	s += s;
	
	for (int i = 0; i < s.length(); i++){
		moji[ctoi(s[i])].push_back(i+1);
	}

	ll ans = 0;
	int now = 0, j = 0;
	for (int i = 0; i < t.length(); i++){
		if (moji[ctoi(t[i])].size() == 0){
			cout << -1 << endl;
			return 0;
		}

		auto iter = lower_bound(moji[ctoi(t[i])].begin(), moji[ctoi(t[i])].end(), now+1);
		ans = j*s.length()/2 + *iter;
		if (*iter >= s.length()/2){
			now = *iter - s.length()/2;
			j++;
		}else{
			now = *iter;
		}
	}
	cout << ans << endl;
	return 0;
}


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

vi a, used;
bool ok;
void dfs(int x) {
    if(used[x]) {
        if(a[a[x]] != x) ok = false;
        return;
    }
    used[x] = 1;
    dfs(a[x]);
}
constexpr ll MOD = 1e9 + 7;
ll modpow(ll x, ll n) {
    ll res = 1;
    while(n) {
        if(n & 1) res = x * res % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}
vector<ll> prd(101010), p(101010), iprd(101010);
vector<ll> inv(101010);
ll P(int a, int b) {
    if(b > a or b < 0) return 0;
    return prd[a] * iprd[a - b] % MOD;
}
main() {
    prd[0] = p[0] = inv[1] = 1;
    rep(i, 100010) prd[i + 1] = prd[i] * (i + 1) % MOD;
    rep(i, 100010) p[i + 1] = p[i] * 2 % MOD;
    rep(i, 100010) inv[i + 2] = modpow(i + 2, MOD - 2);
    iprd[0] = 1;
    rep(i, 100010) iprd[i + 1] = iprd[i] * inv[i + 1] % MOD;
    inv[1] = 1;
    while(1) {
        int n;
        cin >> n;
        if(!n) return 0;
        ok = true;
        a.resize(n);
        used = vector<int>(n);
        rep(i, n) cin >> a[i], a[i]--;
        ll k = 0, s = 0;
        vi in(n);
        rep(i, n) in[a[i]]++;
        rep(i, n) if(in[i] > 2) ok = false;
        rep(i, n) {
            if(!used[i] and !in[i]) dfs(i);
        }
        rep(i, n) {
            if(!used[i]) dfs(i);
        }
        rep(i, n) {
            if(a[a[i]] == i) {
                k++;
                if(in[i] == 1 and in[a[i]] == 1) s++;
            }
        }
        k /= 2, s /= 2;
        if(!ok) {
            cout << 0 << endl;
            continue;
        }
        ll ans = prd[k + 1] * p[k] % MOD;
        // cout << k << " " << s << endl;
        if(k == s) {
            if(s & 1)
                ans = ans * inv[2] % MOD;
            else {
                ans = ans * (s + 2) / 2 % MOD * inv[s + 1] % MOD;
            }
        } else {
            for(int i = 1; i <= s; ++i) {
                ll t = P(s, i) * (i + 1) % MOD;
                if(i & 1)
                    t = t * inv[2] % MOD;
                else
                    t = t * i % MOD * inv[2] % MOD * inv[i + 1] % MOD;
                ans -= t * (k - s) % MOD * prd[k - i - 1] % MOD * p[k + 1] % MOD;
                if(ans < 0) ans += MOD;
                if(k - i > 1) ans -= t * (k - s) % MOD * (k - s - 1) % MOD * prd[k - i - 1] % MOD * p[k] % MOD;
                if(ans < 0) ans += MOD;
            }
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 7324
n,m=map(int,input().split())
acount=0
wcount=0
a=[0]*n
w=[0]*n
for i in range(m):
  p,m=map(str,input().split())
  p=int(p)
  if m=="AC":
    if a[p-1]==0:
      acount+=1
      a[p-1]+=1
  else:
    if a[p-1]==0:
      w[p-1]+=1
      
for i in range(n):
  if a[i-1]==1:
    wcount+=w[i-1]
    
print(acount,wcount)

Measured memory_bytes: 4596
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 9e18;
constexpr int inf = 1e9;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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;
};

// intやllをstringに変換
template<typename T> inline string toString(const T &a){
  ostringstream oss;
  oss << a;
  return oss.str();
};
// ----------------------------------------------------------------------------

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> S(N,-1);
  for(int i=0; i<M; i++){
    int s,c;
    cin >> s >> c;
    s--;
    if(S[s] == -1){
      S[s] = c;
    }else if(S[s] != c){
      cout << -1 << endl;
      return 0;
    }
  }
  if(N == 1){
    if(S[0] == -1){
      cout << 0 << endl;
    }else{
      cout << S[0] << endl;
    }
  }else if(N == 2){
    if(S[0] == 0){
      cout << -1 << endl;
      return 0;
    }
    if(S[0] == -1){
      S[0] = 1;
    }
    if(S[1] == -1){
      S[1] = 0;
    }
    cout << S[0]*10 + S[1] << endl;
  }else{
    if(S[0] == 0){
      cout << -1 << endl;
      return 0;
    }
    if(S[0] == -1){
      S[0] = 1;
    }
    if(S[1] == -1){
      S[1] = 0;
    }
    if(S[2] == -1){
      S[2] = 0;
    }
    cout << S[0]*100 + S[1]*10 + S[2] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import sys
import time
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = int(input())
a = list(map(int,input().split()))
q = int(input())
bc = [list(map(int,input().split())) for i in range(q)]

ans = 0
data = [0]*100010
for i in a:
  data[i] += 1
  ans += i

for b,c in bc:
  ans += c*data[b] - b*data[b]
  data[c] += data[b]
  data[b] = 0
  print(ans)

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

// ?????¬???????????¬??????
#pragma region MACRO
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define PED cout << "\n"
#define rep(i,n) for(int i=0; i<(int)n; ++i)
#define REP(i,x,n) for(int i=x; i<(int)n; ++i)
#define repi(i,n) for(int i=0; i<=(int)n; ++i)
#define REPI(i,x,n) for(int i=x; i<=(int)n; ++i)
#define ILP while(true)
#define FOR(i,c) for(__typeof((c).begin())!=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#pragma endregion

// ???
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long double> vld;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#pragma endregion

// Effective std
#pragma region ESTD
template<typename C, typename T> int count(C& c, T t) { return count(ALL(c), t); }
template<typename C, typename F> int count_if(C& c, F f) { return count_if(ALL(c), f); }
template<typename C, typename T> void erase(C& c, T t) { remove(ALL(c), t), c.end(); }
template<typename C> void remove(vector<C>& c, unsigned int index) { c.erase(c.begin()+index); }
template<typename C, typename T, typename U> void replace(C& c, T t, U u) { replace(ALL(c), t, u); }
template<typename C, typename F, typename U> void replace_if(C& c, F f, U u) { (ALL(c), f, u); }
template<typename C> void reverse(C& c) { reverse(ALL(c)); }
template<typename C> void sort(C& c) { sort(ALL(c)); }
template<typename C, typename Pred> void sort(C& c, Pred p) { sort(ALL(c), p); }
#pragma endregion

// ?????°
#pragma region CONST_VAL
constexpr int PI = (2*acos(0.0));
constexpr int EPS = (1e-9);
constexpr int MOD = (int)(1e9+7);
constexpr int INF = 100000000;
#pragma endregion

void solve(int N) {
    vector<pair<int, int> > nd(N);
    nd[0] = make_pair(210, 210);
    for(int i=1; i<N; ++i) {
        int n, d;
        cin >> n >> d;
        int x, y;
        tie(x, y) = nd[n];
        if(d == 0)
            x--;
        else if(d==1)
            y--;
        else if(d==2)
            x++;
        else
            y++;

        nd[i] = make_pair(x, y);
    }

    int xmax=0, ymax=0;
    int xmin=INF, ymin=INF;
    for(auto &&el: nd) {
        xmax = max(xmax, el.first);
        xmin = min(xmin, el.first);
        ymax = max(ymax, el.second);
        ymin = min(ymin, el.second);
    }

    cout << xmax - xmin + 1 << " " << ymax - ymin + 1 << endl;
}

int main()
{
    int n;
    while(cin >> n, n) solve(n);
    return 0;
}

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

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> p(N);
  for(int i = 0; i < N; i++){
    cin >> p.at(i);
  }
  sort(p.begin(), p.end());
  long long int ans = 0;
  for(int i = 0; i < K; i++){
    ans += p.at(i);
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;

const int N = 1e5 + 5;
vector< pair< int, int> > conn[N];

int dist[N];
bool seen[N];


void dfs(int a) {
    seen[a] = true;
    for(auto it: conn[a]) {
        int b = it.first, c = it.second;
        if(seen[b]) {
            if(dist[b] != dist[a] + c) {
                puts("No");
                exit(0);
            }
            continue;
        }
        dist[b] = dist[a] + c;
        dfs(b);
    }
}

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

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        conn[a].emplace_back(b, c);
        conn[b].emplace_back(a, -c);
    }

    for(int i = 1; i <= n; ++i) if(!seen[i]) {
        dfs(i);
    }

    puts("Yes");


}

Measured memory_bytes: 11136
N = int(input())
S = input()

newS = ""
for s in S.lower():
    s_to_num = ord(s) - 96
    if (s_to_num + N) % 26 != 0:
        new_s = chr( ( (s_to_num + N) % 26 ) + 96)
    else:
        new_s = chr( 26 + 96)
    newS += new_s
print(newS.upper())


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

signed main(void)
{
	vector<int> a(3);
	int sum, k;
	cin >> a[0] >> a[1] >> a[2] >> k;
	rep(i, k)
	{
		sort(a.rbegin(), a.rend());
		a[0] *= 2;
	}
	sum = 0;
	rep(i, 3) sum += a[i];
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
N,A,B = map(int,input().split())

TRUE_LIST = []

list_1 = list(range(0,N+1))

for i in range(len(list_1)):
  s = str(list_1[i])
  arr = list(map(int,s))
  t=sum(arr)
  if A <= t and t <= B:
    TRUE_LIST.append(list_1[i])

print(sum(TRUE_LIST))

Measured memory_bytes: 3572
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

#define rep(i, n) for(int i=0; i<(n); ++i)
#define max  200001

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
 
    char n[2];
    
    scanf("%s", n);

    if (n[0]=='9'||n[1]=='9') {
        printf("Yes");
    } else {
        printf("No");
    }
    
    return 0;
}



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

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

    ll A, B, K;
    cin >> A >> B >> K;

    if(A >= K) {
        cout << A - K << " " << B;

    }
    else {
        K -= A;
        if(B >= K) cout << 0 << " " << B - K;
        else cout << 0 << " " << 0;
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//AtCoder Beginner Contest 127
//C	Prison
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		sc.nextLine();
		List<Integer> Ls = new ArrayList<>();
		List<Integer> Rs = new ArrayList<>();
		for (int i = 0; i < M; i++) {
			Ls.add(sc.nextInt());
			Rs.add(sc.nextInt());
			sc.nextLine();
		}

		sc.close();

		int min = 0;
		int max = N;
		for (int i = 0; i < M; i++) {
			min = Math.max(min, Ls.get(i));
			max = Math.min(max, Rs.get(i));
		}

		System.out.println(Math.max(max - min + 1, 0));

	}
}


Measured memory_bytes: 155084
#include<bits/stdc++.h>
using namespace std;
int main ()
{
    int n;
    cin>>n;
    int A[n+5][3];
    int dp[n+5][3];
    for(int i=0; i<n; i++)
    {
        for(int k=0; k<3; k++)
            cin>>A[i][k];
    }
    for(int i=0; i<n; i++)
        for(int k=0; k<3; k++)
            dp[i][k] = 0;
    for(int i=0; i<1; i++)
        for(int k=0; k<3; k++)
            dp[i][k] = A[i][k];
    for(int i=0; i<n; i++)
    {
        for(int k=0; k<3; k++)
        {
            if(k==0)
            {
                dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k]+A[i+1][k+1]);
                dp[i+1][k+2] = max(dp[i+1][k+2],dp[i][k]+A[i+1][k+2]);

            }
            else if(k==1)
            {
                dp[i+1][k-1] = max(dp[i+1][k-1],dp[i][k]+A[i+1][k-1]);
                dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k]+A[i+1][k+1]);
            }
            else if(k==2)
            {
                dp[i+1][k-2] = max(dp[i+1][k-2],dp[i][k]+A[i+1][k-2]);
                dp[i+1][k-1] = max(dp[i+1][k-1],dp[i][k]+A[i+1][k-1]);
            }
        }
        //cout<<dp[i+1][0]<<" "<<dp[i+1][1]<<" "<<dp[i+1][2]<<endl;
    }
    int ans = -1;
    for(int i=n-1; i<n; i++)
    {
        for(int k=0; k<3; k++)
            ans = max(ans,dp[i][k]);
    }
    cout<<ans<<endl;
    return 0;


}



Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <map>
using namespace std;

const int divisor = 1000000007;

int main(){
	vector<int> ansvec;

	// 100000!までの数をdivisorで割った余りを格納しておく
	long long* factmodary = new long long[100001];
	long long fact = 1;
	for (int i = 1; i <= 100000; i++){
		fact *= i;
		fact %= divisor;
		factmodary[i] = fact;
	}

	for (;;){
		int N, R;
		cin >> N;
		if (N == 0) break;
		cin >> R;

		int* word = new int[N];
		for (int i = 0; i < N; i++) word[i] = i + 1; //まず0番目の単語を入れておく

		for (int i = 0; i < R; i++){
			int s, t;
			cin >> s >> t;
			/* swap */
			int tmp = word[s - 1]; word[s - 1] = word[t - 1]; word[t - 1] = tmp;
		}

		long long ans = 0;
		map<int, int> bubblehist;

		for (int i = 0; i < N; i++){
			int facttime = word[i] - 1;
			int bubblenum;
			map<int, int>::iterator it = bubblehist.find(word[i] - 1);

			if (it != bubblehist.end()){
				bubblenum = it->second + 1;
			}
			else {
				it = bubblehist.find(word[i] + 1);
				if (it != bubblehist.end()){
					bubblenum = it->second;
				}
				else{
					bubblenum = 0;
					for (int j = 0; j < i; j++){
						if (word[j] < word[i]) bubblenum++;
					}
				}
			}
			pair<int, int> p;
			p.first = word[i];
			p.second = bubblenum;
			bubblehist.insert(it, p);
			for (map<int, int>::iterator it2 = bubblehist.upper_bound(word[i]); it2 != bubblehist.end(); it2++) ++(it2->second);

			facttime -= bubblenum;
			if (facttime == 0) continue;
			ans += factmodary[N - (i + 1)] * facttime;
			ans %= divisor;
		}

		delete[] word;
		ansvec.push_back((int)ans);
	}

	for (vector<int>::iterator it = ansvec.begin(); it != ansvec.end(); it++){
		cout << *it << endl;
	}

	delete[] factmodary;
	return 0;
}

Measured memory_bytes: 6860
// C - Pyramid
#include <bits/stdc++.h>
using namespace std;
using TP = tuple<int,int,int>;//<x,y,h>
using VT = vector<TP>;//[i]<x,y,h>
#define rp(i,n) for(int i=0;i<(n);i++)
#define eb(x,y,h) emplace_back((x),(y),(h))
#define manhattan(x1,y1,x2,y2) (abs((x1)-(x2))+abs((y1)-(y2)))
#define XMAX 100
#define YMAX 100

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

	VT A;//h!=0
	VT B;//h==0
	VT C;//center candidate

	rp(i, N){
		int x,y,h; cin>>x>>y>>h;
		if(h != 0) A.eb(x,y,h);
		else B.eb(x,y,h);
	}

	rp(y0, YMAX+1){
		rp(x0, XMAX+1){
			bool exist = true;
			int x,y,h;
			tie(x,y,h) = A[0];
			int h0 = h + manhattan(x0,y0, x,y);//h0: hight of center candidate

			for(int i=1; i<A.size(); ++i){
				tie(x,y,h) = A[i];
				if(h0 != h + manhattan(x0,y0, x,y)){
					exist = false;
					break;
				}
			}

			if(exist) C.eb(x0,y0,h0);//set center candidate
		}
	}

	for(auto c:C){// hight zero check & output
		int x0,y0,h0; tie(x0,y0,h0) = c;

		bool exist = true;
		for(auto b:B){
			int x,y,h; tie(x,y,h) = b;
			if(h0 - manhattan(x0,y0, x,y) > 0){
				exist = false;
				break;
			}
		}

		if(exist) cout<<x0<<" "<<y0<<" "<<h0<<"\n";
	}

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 typedef long long ll;
 
int main() {
int n,k;
cin>>n>>k;
double ans=0.0000000000;
for(int i=1;i<=n;i++){
double a=1.0000000000/n;
int m=i;
int b=0;
while(m<k){
b++;
m*=2;
}
ans+=a*pow(0.5000,b);
}

cout<<fixed << setprecision(15)<<ans<<endl;

}

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

using namespace std;
#define REP(i, N) for(int i=0;i<N;i++)

int main() {
    int n;
    cin >> n;
    vector<int> p(n), q(n), a(n);
    REP(i, n) cin >> p[i];
    REP(i, n) cin >> q[i];

    REP(i, n) a[i] = i + 1;
    map<vector<int>, int> mp;
    do {
        mp[a]=mp.size();
    } while (next_permutation(a.begin(), a.end()));
    cout<<abs(mp[p]-mp[q])<<endl;
}

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

#define printl(s) cout << s << endl;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll = long long;

const ll modSeed = pow(10,9) + 7;
const int INF = 1'000'000'000;

template <typename T>
vector<T> getVector(ll num){
    vector<T> values(num);
    for(ll i=0;i<num;i++){
        cin >> values.at(i);
    }
    return values;
}

string S;
ll N,ans;

int main(){
  cin >> N;
  int maxCount = 0;
  ans = 1;
  for(int i=1;i<=N;i++){
    int val = i;
    int count =0;
    while(val%2==0){
      val /=2;
      count++;
    }
    if(count>maxCount){
      ans = i;
      maxCount = count;
    }
  }
  printl(ans);
}


Measured memory_bytes: 3624
#include <stdio.h>

int main(void)
{
	int go_round[8] = {1, 2, 1, 2, 1, 4, 1, 4};
	int client[8];
	int minimum[8], min, temp;
	int seisuu;
	int i, j;
	int temp_s;
	
	while (scanf("%d%d%d%d%d%d%d%d", &client[0], &client[1], &client[2], &client[3], &client[4], &client[5], &client[6], &client[7]) != EOF){
		
		
		for (i = 0; i < 8; i++){
			temp = temp_s = 0;
			for (j = 0; j < 8; j++){
				temp += (client[j] - go_round[(i + j) % 8] > 0) ? (client[j] - go_round[(i + j) % 8]) : 0;
				temp_s = temp_s * 10 + go_round[(i + j) % 8];
			}
			if (temp <= min || i == 0){
				if (temp == min && i != 0){
					if (temp_s < seisuu){
						min = temp;
						seisuu = temp_s;
						for (j = 0; j < 8; j++){
							minimum[j] = go_round[(i + j) % 8];
						}
					}
				}
				else {
					min = temp;
					seisuu = temp_s;
					for (j = 0; j < 8; j++){
						minimum[j] = go_round[(i + j) % 8];
					}
				}
			}
		}
		
		for (i = 0; i < 8; i++){
			if (i != 0){
				printf(" ");
			}
			printf("%d", minimum[i]);
		}
		
		printf("\n");
	}
	
	return (0);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int b[1000001];
main()
{
    int n,x;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        cin>>x;
        b[x]+=1;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<b[i]<<endl;
    }
}


Measured memory_bytes: 4404
#include <cstdio>

using namespace std;

int solve(int n, int s) {
  int ret = 0;
  for (int mask = 0; mask < 1<<10; mask++) {
    if (__builtin_popcountll(mask) == n) {
      int sum = 0;
      for (int i = 0; i < 10; i++) {
        if (mask & 1 << i)
          sum += i;
      }
      if (sum == s)
        ++ret;
    }
  }
  return ret;
}

int main(int argc, char *argv[])
{
  int n, s;
  while (~scanf(" %d %d", &n, &s)) {
    if (n == 0 && s == 0)
      break;
    int ret = solve(n, s);
    printf("%d\n", ret);
  }
  
  return 0;
}

Measured memory_bytes: 2584
import java.io.*;

public class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String N = br.readLine();
        String[] array = N.split("");
        int calc = 0;
        int[] num = new int[array.length];
        for(int i = 0;i<array.length;i++){
            num[i] = Integer.parseInt(array[i]);
            calc += num[i];
        }
        int Nn;
        Nn = Integer.parseInt(N);
        if(Nn%calc == 0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }


    }
}

Measured memory_bytes: 23124
A = int(input())
B = int(input())
C = int(input())
X = int(input())

ans = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if 500*a + 100*b + 50*c == X:
                ans += 1
                
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n,k;
	cin >> n >> k;
	int a;
	int count = 0;
	for(int i = 0; i < n; i++){
		cin >>a;
		if(a >= k)
			count++;
	}
	cout<<count;
}
int main(){
	
	solve();
	
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        FastReader s = new FastReader();
        long x = s.nextLong();
        ArrayList<Long> arr = new ArrayList<Long>();
        HashMap<Long,Long> map=new HashMap<>();
        for(long i=-4000;i<4000;i++)
            map.put(i,(long) Math.pow(i,5));
        for(long i=-4000;i<4000;i++){
            if(map.containsValue(map.get(i)-x)){
                long pos=0;
                for(long j=-4000;j<4000;j++){
                    if(map.get(j)==((map.get(i)-x))){
                        pos=j;
                        break;
                    }
                }
                System.out.println(i+" "+pos);
                break;
            }
        }

    }

    private static boolean isPrime(int n) {
        if (n == 2)
            return true;
        else if ((n % 2 == 0 && n > 2) || n < 2)
            return false;
        else {
            for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
                if (n % i == 0)
                    return false;
            }
            return true;
        }


    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}

Measured memory_bytes: 27532
n,q=(map(int,input().split()))
s=input()
count=0
c=[0]*n
for i in range(1,n):
        if s[i-1]=='A':
            if s[i]=='C':
               count+=1
        c[i]=count
for _ in range(q):
    l,r=(map(int,input().split())) 
    print(c[r-1]-c[l-1])

Measured memory_bytes: 6084
from collections import deque
def bfs(graph, N, start):
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = node + 1
                que.append(n)
    return visited

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda n: int(n) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)
print("Yes")
print(*bfs(graph, N, 0)[1:], sep="\n")

Measured memory_bytes: 37664
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s; cin >> s;
  if((s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3])) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

int main(void){
    int N,K;
    cin>>N>>K;
    ll ans=K;
    if (N!=1) {
        for (int i=1;i<N;i++){
            ans*=(K-1);
        }
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
if N == 0:
    print('0')
else:
    ans = ''
    for i in range(100):
        if N == 0:
            break
        if abs(N) % (2**(i+1)) != 0:
            ans += '1'
            N -= (-2)**i
        else:
            ans += '0'

    print(ans[::-1])


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

using namespace std;

#define ll long long
#define rep(i,n) for(ll i=1;i<=(n);i++)
#define rep0(i,n) for(ll i=0;i<(n);i++)

const ll INF=1e9+7;

int main()
{
	/*freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);*/
	int a,b,c;
	cin>>a>>b>>c;
	cout<<max(0,c-(a-b));
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) FOR(i,0,n)
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265

int N;

int main(){
  cin>>N;

  for(ll i=1;i<3501;i++){
    for(ll j=1;j<3501;j++){
      if(4*i*j-N*i-N*j<=0) continue;
      if((N*i*j)%(4*i*j-N*i-N*j)==0){
        cout<<i<<' '<<j<<' '<<(N*i*j)/(4*i*j-N*i-N*j)<<endl;
        goto ABC;
      }
    }
  }

  ABC:

  return 0;
}


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

const int maxn = 1 << 14, maxm = 200, mod = 998244353;
int n, m, lim, k, fact[maxn + 3], finv[maxn + 3], f[maxn + 3], g[maxn + 3];
int rev[maxn + 3], a[maxn + 3], b[maxn + 3];

int func(int x) {
	return x < mod ? x : x - mod;
}

int qpow(int a, int b) {
	if (b < 0) b += mod - 1;
	int c = 1;
	for (; b; b >>= 1, a = 1ll * a * a % mod) {
		if (b & 1) c = 1ll * a * c % mod;
	}
	return c;
}

void prework(int n) {
	fact[0] = 1;
	for (int i = 1; i <= n; i++) {
		fact[i] = 1ll * fact[i - 1] * i % mod;
	}
	finv[n] = qpow(fact[n], mod - 2);
	for (int i = n; i; i--) {
		finv[i - 1] = 1ll * finv[i] * i % mod;
	}
}

void dft(int a[], int n, int type) {
	for (int i = 0; i < n; i++) if (i < rev[i]) {
		swap(a[i], a[rev[i]]);
	}
	for (int k = 1; k < n; k <<= 1) {
		int x = qpow(3, (mod - 1) / (k << 1) * type);
		for (int i = 0; i < n; i += k << 1) {
			int y = 1;
			for (int j = i; j < i + k; j++, y = 1ll * x * y % mod) {
				int p = a[j], q = 1ll * a[j + k] * y % mod;
				a[j] = func(p + q), a[j + k] = func(p - q + mod);
			}
		}
	}
	if (type == -1) {
		int x = qpow(n, mod - 2);
		for (int i = 0; i < n; i++) {
			a[i] = 1ll * a[i] * x % mod;
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	prework(n + 2);
	for (lim = 1, k = 0; lim <= n * 2; lim <<= 1) k++;
	for (int i = 1; i < lim; i++) {
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
	}
	f[0] = 1;
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			a[j] = 1ll * f[j] * finv[j] % mod;
		}
		b[0] = 0;
		for (int j = 1; j <= n; j++) {
			b[j] = finv[j + 2];
		}
		fill(a + n + 1, a + lim, 0);
		fill(b + n + 1, b + lim, 0);
		dft(a, lim, 1), dft(b, lim, 1);
		for (int j = 0; j < lim; j++) {
			g[j] = 1ll * a[j] * b[j] % mod;
		}
		dft(g, lim, -1);
		for (int j = 0; j <= n; j++) {
			g[j] = (1ll * g[j] * fact[j + 2] + 1ll * f[j] * (j * (j + 1) / 2 + 1)) % mod;
		}
		for (int j = 0; j <= n; j++) {
			f[j] = g[j];
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		ans = (ans + 1ll * finv[i] * finv[n - i] % mod * f[i]) % mod;
	}
	ans = 1ll * ans * fact[n] % mod;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-8;
typedef long long ll;
#define equ(a,b) ((fabs((a)-(b)))<(eps))
#define more(a,b) (((a)-(b))>(eps))
#define less(a,b) (((a)-(b))<(-eps))
#define inf 0x3f3f3f3f

int main(){
    ll s;
    int n,a[200005];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    s=a[0];
    for(int i=1;i<n;i++){
        s^=a[i];
    }
    for(int i=0;i<n;i++){
        cout<<(s^a[i])<<" ";
    }
    return 0;
}

Measured memory_bytes: 4412
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<cmath>
#define int long long
using namespace std;
inline void read(int &x){
	x=0;int f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();	}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=f;
}
int a[60];
int n,sum;
signed main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            sum+=a[i]*a[j];
    
    printf("%lld",sum);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<int>
#define vvint vector<vint>
#define P pair<ll,ll>
#define INT_MAX 2147483647
#define MOD 998244353
#define PI 3.14159265358979323846
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;

#define MAX 1000000000000


int main(void) {
	int n; cin >> n;
	map<int,int> mp;
	ll ans = 0;
	rep(i, n) {
		int x;
		cin >> x;
		mp[x]++;
		ans += x;
	}
	int q; cin >> q;
	rep(i, q) {
		int b, c; cin >> b >> c;

		ans += (c - b) * mp[b];
		cout << ans << endl;

		mp[c] += mp[b];
		mp[b] = 0;
	}
	return 0;
}


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

int main(){
  int N,cnt,min;
  int X;
  min = 1000;
  cnt = 0;
  cin >> N;
  for(int i = 0;i < N;i++){
   	    cin >> X;
    	cnt = 0;
    	while(X%2 ==0){
        	X /= 2;
          	cnt++;
        }
		if(min > cnt){
        	min = cnt;
        }
    }
  cout << min << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using ll = long long int;

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

    ll a[200010], dp[200010][3] = { 0 };
    for (int i = 0; i < n; ++i)
    {
        std::cin >> a[i];
    }

    ll ans = -1e15;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            dp[i][j] = -1e15;
        }
        if (i < 3)
            dp[i][i] = a[i];

        if (i-2 >= 0)
        {
            dp[i][0] = std::max(dp[i][0], dp[i-2][0] + a[i]);
            dp[i][1] = std::max(dp[i][1], dp[i-2][1] + a[i]);
            dp[i][2] = std::max(dp[i][2], dp[i-2][2] + a[i]);
        }

        if (i-3 >= 0)
        {
            dp[i][1] = std::max(dp[i][1], dp[i-3][0] + a[i]);
            dp[i][2] = std::max(dp[i][2], dp[i-3][1] + a[i]);
        }

        if (i-4 >= 0)
        {
            dp[i][2] = std::max(dp[i][2], dp[i-4][0] + a[i]);
        }
    }

    if (n & 1)
    {
        ans = std::max(ans, dp[n-1][2]);
        ans = std::max(ans, dp[n-2][1]);
        ans = std::max(ans, dp[n-3][0]);
    }
    else
    {
        ans = std::max(ans, dp[n-1][1]);
        ans = std::max(ans, dp[n-2][0]);
    }

    std::cout << ans;
}


Measured memory_bytes: 9904
#include <iostream>
#include <string>
using namespace std;
int main() {
	int n,m;
	cin >>n;
	cin >>m;
	bool ans[m];
	for(int i=0;i<m;i++){
		ans[i] = true;
	}
	for(int i=0;i<n;i++){
		int cnt;
		cin >>cnt;
		bool tmp[m];
		for(int j=0;j<m;j++){
			tmp[j] = false;
		}
		for(int j=0;j<cnt;j++){
			int hoge;
			cin >>hoge;
			tmp[hoge-1] = true;
		}
		for(int j=0;j<m;j++){
			ans[j] = (ans[j] && tmp[j]); 
		}
	}
	int answer = 0;
	for(int i=0;i<m;i++){
		if(ans[i]){
			answer ++;
		}
	}
	cout <<answer <<endl;
	return 0;
}

Measured memory_bytes: 256
s = list(str(input()))

from collections import deque

ans = []
_x = s[0]
l = 1
for x in s[1:]:
    if x == _x:
        l += 1
    else:
        ans.append(l)
        _x = x
        l = 1
ans.append(l)
ans = deque(ans)

_ans = 0

def partsum(n):
    return n*(n+1)//2

if s[0] == '>':
    d = ans.popleft()
    _ans += partsum(d)

while len(ans)>1:
    a = ans.popleft()
    b = ans.popleft()
    _ans += partsum(max(a,b)) + partsum(min(a,b)-1)
if len(ans)==1:
    c = ans.popleft()
    _ans += partsum(c)

print(_ans)


Measured memory_bytes: 93660
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cmath>

using ll = long long;

using namespace std;

int main() {
    int n;
    cin >> n;
    ll rui[n+1];
    rui[0] = 0;
    for (int i=0; i<n; i++) {
        ll ai;
        cin >> ai;
        rui[i+1] = rui[i] + ai;
    }
    int h = lower_bound(rui, rui+n+1, rui[n] / 2) - rui;
    cout << min(abs(rui[n] - rui[h]*2), abs(rui[n] - rui[h-1]*2)) << '\n';
    return 0;
}

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

int main() {
  int a,b;
  cin >> a >> b;
if(a==1)a = 14;
if(b==1)b = 14;
if(a>b) cout << "Alice" << endl;
else if(b>a) cout << "Bob" << endl;
else cout << "Draw" << endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define ll long long
#define P pair<int, int>

using namespace std;

int N;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N;
  unordered_map<int, int> mp;

  rep(i, N) {
    int a;
    cin >> a;
    mp[a]++;
  }

  int ans = 0;
  for(auto e : mp) {
    if (e.second%2) {
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 4388
#include <bits/stdc++.h>
#define ll long long
const ll MOD=1e9+7;
using namespace std;

int main(){
  string S;
  vector<string> T={"dreameraser","dreamerase","dreamer","dream","eraser","erase"};
  vector<int> t={11,10,7,5,6,5};
  cin>>S;
  ll N=S.size();
  for(ll l=0;l<N;l++){
    for(int j=0;j<6;j++){
      if(S.substr(l,t[j])==T[j]){
        l+=t[j]-1;
        break;
      }else if(j==5){
        cout<<"NO"<<endl;
        return 0;
      }
    }
  }
  cout<<"YES"<<endl;
}


Measured memory_bytes: 512