akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int MOD2 = MOD + 2; //1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(ll& a,ll val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(ll& a,ll val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

int main() 
{
   int n,k;
    cin>>n>>k;
    ll sum=0;
    FOR(i,k,n+2)
    {
      ll a,b;
      if(i%2==0){a=i/2;b=(i-1);}
      else {a=(i-1)/2;b=i;}
      ll mn=mult(a,b);
      ll mx=mult(i,n);
      submod(mx,mn);
      //cout<<i<<" "<<mx<<" "<<mn<<endl;
      addmod(sum,mx);
      submod(sum,(mn-1));
    }
    cout<<sum%MOD<<endl;
   return 0;
}

Measured memory_bytes: 3624
#include <iostream>

using namespace std;

int main(){
	int n;
	int many[210000];

	cin >> n;

	for(int i = 1; i <= n; i++){
		cin >> many[i];
	}

/*	for(int i = 1; i < n; i++){
		for (int f = i + 1; f <= n; f++){
			if (many[i] > many[f]){
				int tmp = many[i];
				many[i] = many[f];
				many[f] = tmp;
			}
		}
	}

	cout << many[n] - many[1] << "\n";*/

	int max = -1000000000;

/*	for(int i = 1; i <= n - 1; i++){
		for(int f = i + 1; f <= n; f++){
			if (max < many[f] - many[i])
				max = many[f] - many[i];
		}
	}*/

	/*for (int i = 1; i <= n - 1; i++){
		int max2 = -1000000000;
		for (int f = i + 1; f <= n; f++){
			if (many[f] > max2){
				max2 = many[f];
			}
		}
		if (max < max2 - many[i])
			max = max2 - many[i];
	}*/

	int minv = many[1];
	int maxv = -1000000000;
	int aaaaa;

	for(int i = 2; i <= n; i++){
		if (maxv < many[i] - minv){
			maxv = many[i] - minv;
			aaaaa = many[i];
		}
		if (minv > many[i])
			minv = many[i];
	}

	cout << maxv << "\n";
}


Measured memory_bytes: 3876
#include<bits/stdc++.h>
using namespace std;
int main(){
	long n,m;
	cin>>n>>m;
	vector<int> a(m);
	for(int i=0;i<m;i++)cin>>a.at(i);
	long sum=0;
	for(int i=0;i<m;i++)sum+=a.at(i);
	if(sum<=n){
		cout<<(n-sum)<<endl;
	}
	else cout<<"-1"<<endl;
}


Measured memory_bytes: 3640
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

int main() {
    int n, m; cin >> n >> m;
    vector<int> a(m);
    REP(i, m) cin >> a[i];
    // dp[i][j] : i番目まででjを作るときの最小
    vector<vector<ll>> dp(m+1, vector<ll>(n+1, LLINF));
    dp[0][0] = 0;
    REP(i,m) {
        REP(j, n + 1) {
            if (j - a[i] >= 0) {
                dp[i+1][j] = min({dp[i][j], dp[i+1][j - a[i]] + 1, dp[i][j - a[i]] + 1});
            }
            else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}


Measured memory_bytes: 11572
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
typedef long long ll;
//HとWがおおきいので3*3ますの左上のマスに注目
//色の塗りつぶしたときにそのマスを含む各マスを左上のマスで判別する
//マスがでできた回数 = そのマスに含まれる黒マスの回数
//すべて白マスになる３＊３マスは最大(H-2)*(W-2)こある
int main(){
    ll H,W,N;
	cin >> H >> W >> N;
	map<pair<ll,ll>,ll> m;
	rep(i,N){
        ll a,b;
		cin>>a>>b;
		rep(j,3){
			rep(k,3){
				ll na = a - j, nb = b - k;
                if(na < 1 || nb < 1 || na > H-2 || nb > W-2)continue;
                m[{na,nb}]++;//左上のマスを数え上げる
			}
		}
	}
    vector<ll> res(10,0);
	for(auto e : m){
		res[e.second]++;
	}
    ll sub = 0;
	rep(i,10) sub += res[i];
	res[0] = (H-2)*(W-2) - sub;//黒マスを含む数引く
	for(auto ans : res){
        cout << ans << endl;
    }
}

Measured memory_bytes: 56448
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) a.begin(),a.end()

int main(){
	int N;cin>>N;
	vector<pair<long,long>> T(N);
	rep(i,0,N) cin>>T[i].second>>T[i].first;
	sort(range(T));
	long sum=0;bool flag=true;
	rep(i,0,N){
		sum+=T[i].second;
		if(sum>T[i].first) flag=false;
	}if(flag){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
}


Measured memory_bytes: 3456
list1 = list(input())

a = int("".join(list1[:2]))
b = int("".join(list1[2:]))

def func(i):
    if 0 < i < 13:
        return True

if func(a):
    if func(b):
        print("AMBIGUOUS")
        exit()
    else:
        print("MMYY")
        exit()
elif func(b):
    print("YYMM")
    exit()

print("NA")

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define SZ(n) (int)(n).size()
#define ALL(n) (n).begin(), (n).end()
using namespace std;
typedef long long LL;
typedef vector<int> VI;

int main() {
	string s;
	cin >> s;
	string ns;
	REP(i, SZ(s)) {
		if (i % 2 == 0) ns += s[i];
	}
	cout << ns << endl;
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
using namespace std;
int main(){
int a,b,c,x,i;
cin>>a>>b>>c;
i=a;
x=0;
while(1){
if(i>b)break;
if(c%i == 0){
x++;
}
i++;
}
cout<<x<<endl;
return 0;
}





Measured memory_bytes: 3092
#include<iostream>
#include<string>

using namespace std;

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

int main(){
    string s;
    cin >> s;
    int a[2] = {0, 0};
    rep(i, 3){
        if(s[i] == 'A'){
            a[0]++;
        }else if(s[i] == 'B'){
            a[1]++;
        }
    }
    if(a[0] != 0 && a[1] != 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define pb push_back
#define nl cout<<"\n"
#define db(x) cout<<x<<" "
#define fi(a,b) for(int i=a;i<b;i++)
#define fj(a,b) for(int j=a;j<b;j++)
#define fk(a,b) for(int k=a;k<b;k++)
#define F first
#define S second
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
#define mxsize (int)1e6
ll fastexp(ll a,ll n,ll nod){
	if(nod==0)	nod=LLONG_MAX;
	ll ans=1;
	while(n){
		if(n&1)
			ans=(ans*a)%nod;
		a=(a*a)%nod;
		n>>=1;
	}
	return ans;
}
void fun(){
	ll n,capacity;
	cin>>n>>capacity;
	ll w[n],v[n];
	fi(0,n){
		cin>>w[i]>>v[i];
	}
	ll dp[n+1][capacity+1];
	fi(0,n+1){
		dp[i][0]=0;
	}
	fi(0,capacity+1){
		dp[0][i]=0;
	}
	fi(1,n+1){
		fj(1,capacity+1){
			if(w[i-1]<=j){
				dp[i][j]=max(dp[i-1][j],v[i-1]+dp[i-1][j-w[i-1]]);
			}
			else{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	cout<<dp[n][capacity]<<"\n";
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen("/ATOM/input.txt", "r", stdin);
		freopen("/ATOM/output.txt", "w", stdout);
	#endif
	int t=1;
	// cin>>t;
	while(t--){
		fun();
	}
}

Measured memory_bytes: 82512
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,q = map(int,input().split())
E = [tuple(map(int,input().split())) for i in range(q)]
A = list(itertools.combinations_with_replacement(range(1,m+1),n))
for comb in A:
  tmp = 0
  for a,b,c,d in E:
    a-=1;b-=1
    if comb[b]-comb[a] == c:
      tmp += d
  ans = max(ans,tmp)
print(ans)

Measured memory_bytes: 85176
/*  -*- coding: utf-8 -*-
 *
 * c.cc: C - Different Strokes
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MAX_N = 100000;

/* typedef */

typedef long long ll;
typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int,int> pii;

/* global variables */

int cs[MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);

  ll bsum = 0;
  for (int i = 0; i < n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    cs[i] = a + b;
    bsum += b;
  }
  sort(cs, cs + n);

  ll csum = 0;
  for (int i = n - 1; i >= 0; i -= 2) csum += cs[i];
  printf("%lld\n", csum - bsum);
  return 0;
}


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

template<int MOD> struct modint{
    int val;
    constexpr modint(int v): val(v % MOD){
        if(val < 0) val += MOD;
    }
    constexpr int getmod(){
        return MOD;
    }
    constexpr modint operator-(){
        return val? MOD - val : 0; 
    }

    constexpr modint operator+(const modint& r){
        return modint(*this) += r;
    }
    constexpr modint operator-(const modint& r){
        return modint(*this) -= r;
    }
    constexpr modint operator*(const modint& r){
        return modint(*this) *= r;
    }
    constexpr modint operator/(const modint& r){
        return modint(*this) /= r;
    }


    constexpr modint& operator+=(const modint &r){
        val += r.val;
        if(val >= MOD) val -= MOD;
        return *this;
    }
    constexpr modint& operator-=(const modint& r){
        val -= r.val;
        if(val < 0) val += MOD;
        return *this;
    }
    constexpr modint& operator*=(const modint& r){
        val = (val * r.val) % MOD;
        return *this;
    }
    constexpr modint& operator/=(const modint& r){
        // ax + bz = a, ay + bw = b からスタートして
        // 右辺について互除法して係数を変えていく
        // (x, y) -> (y, x-y*(a/b)), (z, w) -> (w, z-w*(a/b))
        // 最終的に ax + bz = gcd(a, b) となるので a, b が互いに素なら x が逆元
        // z と w を覚えておく必要はない
        int a = r.val, b = MOD, x = 1, y = 0;
        while(b){
            x -= y * (a/b); swap(x, y);
            a -= b * (a/b); swap(a, b);
        }
        val = (val * x) % MOD;
        if(val < 0) val += MOD;
        return *this;
    }

    constexpr bool operator==(const modint& r){
        return val == r.val;
    }
    constexpr bool operator!=(const modint& r){
        return val != r.val;
    }

    constexpr modint modpow(int e){
        modint ans = 1, n = *this;
        while(e){
            if(e & 1) ans *= n;
            n *= n;
            e /= 2;
        }
        return ans;
    }

    friend constexpr ostream& operator<<(ostream &os, const modint<MOD>& x){
        return os << x.val;
    }
};

const int MOD = 998244353;
using mint = modint<MOD>;

signed main(){
    // cout << fixed << setprecision(10) << flush;


    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    vector<mint> dp(s+1, 0);
    dp[0] = 1;
    for(int i=0; i<n; i++){
        for(int j=s; j>=a[i] && j>=0; j--){
            // 荷物 i を追加するパターンとしないパターンがある
            dp[j] = dp[j-a[i]] + dp[j] * 2;
        }
        for(int j=min(a[i]-1, s); j>=0; j--){
            // 荷物 i は追加できない
            dp[j] *= 2;
        }
    }

    cout << dp[s] << endl;


    return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<string>> vvs;
typedef vector<vector<char>> vvc;
typedef vector<vector<bool>> vvb;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define vrep(v,n) for(int i=0;i<n;i++){cin >> v.at(i);} 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repn(i, n) for (int i = 0; i <= (int)(n); i++)
#define srep(i, l, n) for (int i = l; i < (int)(n); i++)
#define srepn(i, l, n) for (int i = l; i <= (int)(n); i++)
#define pb push_back 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int mod = 1000000007;
const int inf = 1e9;
#define PI 3.14159265369;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    ll n, q;
    cin >> n;
    vector<set<ll>> w(26);
  	vector<char> pos(500005);
  	for(int i = 0; i < n; i++){
        char c;
        cin >> c;
        w[(int)(c-'a')].insert(i);
        pos[i] = c;
    }
    cin >> q;
    while(q--){
        int i;
        cin >> i;
        if(i==1){
            ll t;
            char c;
            cin >> t >> c;
            t--;
            w[(int)(pos[t]-'a')].erase(t);
            w[(int)(c-'a')].insert(t);
            pos[t] = c;
        }else if(i==2){
            ll l,r;
            cin >> l >> r;
            l--;r--;
            ll ans = 0;
            for(int c = 0; c < 26; c++){
                auto itr = w[c].lower_bound(l);
                if(itr!=w[c].end()&&*itr <= r) ans++;
            }
            cout << ans << endl;
        }
    }

}

Measured memory_bytes: 24192
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(int i = n-1; i >= 0; i--)
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> graph;
const long long mod = 1000000007LL;

int n, m;
int ans;

void dfs(int v, vi vec, vector<bool> seen, graph &g) {
  if(seen[v]) return;
  if(vec.size()==n) {
    ans++;
    return;
  }
  seen[v] = true;
  vec.push_back(v);
  for(auto to : g[v]) {
    vector<bool> seen2 = seen;
    dfs(to,vec,seen2,g);
  }
}

int main() {
  cin >> n >> m;
  ans = 0;
  graph g(n);
  rep(i,m) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<bool> seen(n,false);
  dfs(0,{0},seen,g);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
 int N;
 cin >> N ;
 
 
  
  for(int i = 1;i < 10 ; i++){
   if (N/i <10 && N%i ==0){
    cout << "Yes" << endl;
    break;
    }
    if(i==9){
    cout << "No" << endl;
    break;
    }
    
   
    
   }
  }
   

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N;

    cin>>N;

    char c[N];
    rep(i,N) cin>>c[i];

    int l=0,r=N-1;
    int ans=0;
    rep(i,N){
        if(c[i]=='W'){
            while(true){
                if(c[r]=='R'){
                    ans++;
                    r--;
                    break;
                }else if(i>=r){
                    break;
                }
                else r--;
            }
        }

        if(i>=r)break;
    }
    cout << ans << endl;



    



}


Measured memory_bytes: 3844
#include <iostream>
#include <string>

using namespace std;

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

    ans = "";

    for (int i = 0; i < N; ++i) {
        char sc = s[i];
        char tc = t[i];
        string ss = {sc};
        string ts = {tc};
        ans += ss + ts;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
/* ****GT_18**** */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define N  100005

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		ll i,j,k,l,m,n;
		cin>>n;
		vi v(n+1);
		rep(i,1,n+1)
		{
			cin>>v[i];
		}
		vi cost(n+1,0);
		cost[0]=0;
		cost[1]=0;
		cost[2]=abs(v[2]-v[1]);
		for(i=3;i<=n;i++)
		{
			cost[i]=min((cost[i-1]+abs(v[i]-v[i-1])),(cost[i-2]+abs(v[i]-v[i-2])));
		}
		cout<<cost[n];
	}
	return 0;
}

Measured memory_bytes: 1792
n, x = map(int, input().split())

while n != 0 or x != 0:
	cnt = 0
	i = 1
	while i <= n - 2:
		j = i + 1
	#	if i >= x:
	#		break
		while j <= n - 1:
			k = j + 1
	#		if i + j >= x:
	#			break
			while k <= n:
	#			if i + j + k > x:
	#				break
				if i + j + k == x:
					cnt += 1
				k += 1
			j += 1
		i += 1
	print(cnt)
	n, x = map(int, input().split())


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

int main(){

int N;
cin >> N;

vector<int> v;
v.reserve(20000);

for(int i=0; i<N; ++i){
int a;
cin>>a;
v.push_back(a);
}

sort(v.begin(), v.end());

int expected = N&1 ? 0 : 1;
int nextup = N&1 ? 1 : 0;
for(int i=0; i<N; ++i){
if(v[i] != expected){
cout << 0;
return 0;
}else{
expected += nextup*2;
nextup = !nextup;

}
}

int ans = 1;
for(int i=0; i<N/2; ++i){
ans = (ans*2) % 1000000007;
}
cout << ans << endl;

}

Measured memory_bytes: 992
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main {
	public static void main(String args[]) {
		FastScanner sc = new FastScanner(System.in);
		long mod = 1000000007;
		int n = sc.nextInt();
		int q = sc.nextInt();
		int[] a = new int[n];
		for(int i=0; i<n; i++) {
			a[i] = sc.nextInt();
		}
		long dp[][] = new long[n][n];
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(a[i] > a[j])
					dp[i][j] = 1;
			}
		}
		long half = inverse(2,mod);

		for(int i=0; i<q; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			for(int j=0; j<n; j++) {
				if(j!=y-1 && j!=x-1) {
					dp[y-1][j] = dp[x-1][j] = (half * dp[x-1][j] % mod + half * dp[y-1][j] % mod)%mod;
					dp[j][x-1] = dp[j][y-1] = (half * dp[j][x-1] % mod + half * dp[j][y-1] % mod)%mod;
				}
				dp[y-1][x-1] = dp[x-1][y-1] = (half * dp[y-1][x-1] % mod + half * dp[x-1][y-1] % mod)%mod;
			}

		}

		long expectation = 0;
		for(int i=0; i<n; i++) {
			for(int j=i+1; j<n; j++) {
				expectation = (expectation + dp[i][j]) %mod;
			}
		}
		System.out.println(expectation*bin_exp(2,q,mod)%mod);
	}
	
	public static long bin_exp(long base, long exp, long mod) {
		if(exp == 0)
			return 1;
		return bin_exp(base*base%mod, exp/2, mod) * (exp%2 == 1? base : 1) % mod;
	}
	
	public static long inverse(long a, long mod) {
		return bin_exp(a,mod-2,mod);
	}
}

class FastScanner{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    
    public FastScanner(InputStream stream)
    {
        this.stream = stream;
    }
    
    int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars){
            curChar = 0;
            try{
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }
    
    boolean isSpaceChar(int c)
    {
        return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
    }
    
    boolean isEndline(int c)
    {
        return c=='\n'||c=='\r'||c==-1;
    }
    
    int nextInt()
    {
        return Integer.parseInt(next());
    }
    
    long nextLong()
    {
        return Long.parseLong(next());
    }
    
    double nextDouble()
    {
        return Double.parseDouble(next());
    }
    
    String next(){
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isSpaceChar(c));
        return res.toString();
    }
    
    String nextLine(){
        int c = read();
        while (isEndline(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isEndline(c));
        return res.toString();
    }
}




Measured memory_bytes: 134508
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, K;
  cin >> N >> K;
  int sum;
  sum = 0;
  for(int i = 0; i < N; i++){
    int x;
    cin >> x;
    if(x < K - x){
      sum += x * 2;
    }
    else sum += (K - x) * 2;
  }
  cout << sum << endl;

}

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

int main(){
    int r,g,b,n;
    cin >> r >> g >> b >> n;
    int count = 0;
    int rmax = n / r;
    int gmax = n / g;
    int bmax = n / b;
    for(int i = 0; i <= rmax; i++){
        for(int j = 0; j <= (n - r * i) / g; j++){
            if((n - r * i - g * j) % b == 0) count++;
        }
    }

    cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
double pi=acos(-1);
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
// #define mp make_pair
#define pq priority_queue
const ll mod=1000000007;
#define f first
#define s second
#define pii pair< ll, ll >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace boost::multiprecision;
using namespace std;
void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int N=1000005;
ll fact[N],invfact[N];
ll power(ll x,ll y){
  if(y<=0) return 1LL;
  ll z=power(x,y/2);
  if(y%2) return (((z*z)%mod)*x)%mod;
  return (z*z)%mod;
}

void pre(){
  fact[0]=invfact[0]=invfact[1]=fact[1]=1;
  rep(i,2,N) fact[i]=(i*fact[i-1])%mod;
  rep(i,2,N) invfact[i]=(invfact[i-1]*power(i,mod-2))%mod;
}
ll nCr(ll n,ll k){ return (((fact[n]*invfact[n-k])%mod)*invfact[k])%mod; }



const int N1=1e6+1;
vector<int> isprime(N1,1),prime;
void seive(){
  rep(i,2,sqrt(N1)+1){
      if(isprime[i]){
        for(int j=i*i;j<N1;j+=i) isprime[j]=0;
        prime.pb(i);
      }
  }
  rep(i,sqrt(N1)+1,N1) if(isprime[i]) prime.pb(i);
}



struct dsu {
    vector<int> par, rank;
    dsu(int n): par(n+1), rank(n+1) {
        for (int i = 0; i <= n; i++) {
            par[i] = i;
            rank[i]= 1;
        }
    }
    int root(int a) {
        if (a == par[a]) return a;
        return par[a] = root(par[a]);
    }
    void merge(int a, int b) {
        a = root(a);
        b = root(b);
        if (a == b) return;
        if (rank[a] > rank[b]) swap(a, b);
        par[b] = a;
    }
    set<int> parent(int n){
        set<int> s;
        for(int i=1;i<=n;i++){
            s.insert(root(i));
        }
        return s;
    }
};

void solve(){
  int n,x;
  cin>>n;
  set<int> s1;
  rep(i,0,n){cin>>x;s1.insert(x);}
  cout<<s1.size()<<endl;
}

int main(){
    optimizeIO();
    int r=1;
    {solve();}
}


Measured memory_bytes: 6996
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   main.cpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: monoue <marvin@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/22 12:30:15 by monoue            #+#    #+#             */
/*   Updated: 2020/04/30 14:20:25 by monoue           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <bits/stdc++.h>

/* #include <boost/multi_array.hpp> */
/* #include <boost/optional.hpp> */
/* #include <boost/range/irange.hpp> */
/* #include <boost/range/algorithm.hpp> */
/* #include <boost/range/adaptors.hpp> */
/* #include <boost/multiprecision/cpp_int.hpp> */
/* #include <boost/algorithm/string/classification.hpp> // is_any_of */
/* #include <boost/algorithm/string/split.hpp> */
/* #include <boost/algorithm/string/join.hpp> */
/* #include <boost/algorithm/string/replace.hpp> */
/* #include <boost/math/tools/minima.hpp> */
/* namespace adaptor = boost::adaptors; */
/* using boost::math::tools::brent_find_minima; */
/* using boost::irange; */
/* using boost::algorithm::join; */
/* using boost::algorithm::split; */
/* using boost::algorithm::replace_all; */
/* using boost::multiprecision::cpp_int; */

#define MOD 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

// TOP
void	Main()
{
	string	sa, sb;
	cin >> sa >> sb;
	sa = ' ' + sa;
	sb = ' ' + sb;
	int	la, lb;
	la = sa.size();
	lb = sb.size();
	string	s;
	vector<vector<int>>	V(la, vector<int>(lb));
	rep2(i, 1, la)
	{
		rep2(j, 1, lb)
		{
			if (sa.at(i) == sb.at(j))
				V.at(i).at(j) = V.at(i - 1).at(j - 1) + 1;
			else
				V.at(i).at(j) = max(V.at(i - 1).at(j), V.at(i).at(j - 1));
		}
	}
	int i, j;
	i = la - 1;
	j = lb - 1;
	while (V[i][j])
	{
		while (j >= 1 && V[i][j] == V[i][j - 1])
			j--;
		while (i >= 1 && V[i][j] == V[i - 1][j])
			i--;
		s = sa.at(i) + s;
		i--;
		j--;
	}
	cout << s << endl;
}
// END

int		main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


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

#define ll long long
#define endl '\n'
#define REP(i, a, n) for(int i=a; i<n; ++i)
#define pb push_back
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const double PI = 3.141592653589793238460;
const ll mod = 1e9 + 7;

void FAST(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

int main(){
  FAST();

  int n, i;
  cin >> n;
  vi x(n);
  int sum1 = 0, sum2 = 0, ans1 = 0, ans2 = 0;

  REP(i, 0, n){
      cin >> x[i];
      sum1 += x[i];
  }

  if(sum1 % n == 0){
    sum1 = sum2 = sum1/n;
  }
  else{
    sum1 = sum1/n;
    sum2 = sum1 + 1;
  }
  int ans = 0;

  REP(i, 0, n){
    ans1 += (sum1 - x[i]) * (sum1 - x[i]);
    ans2 += (sum2 - x[i]) * (sum2 - x[i]);
  }

  cout << min(ans1, ans2) << endl;

  return 0;
}


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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if( a + b > c + d){
    cout << "Left" << endl;
  }
  else if( a + b == c + d){
    cout << "Balanced" << endl;
  }
  else{
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define ull unsigned long long
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; } value
#define yesorno(a) printf(a?"yes\n":"no\n")
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define YESorNO(a) printf(a?"YES\n":"NO\n")
using namespace std;


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ushi,tapu,niki,akun;
  cin >> ushi >> tapu >> niki >> akun;
  if(akun == 1) cout <<"1" << endl;
  else cout << "0" << endl;
 }


Measured memory_bytes: 256
a = input()

c = len(a) // 2
if len(a) % 2 == 0:
    x = a[:c]
    y = a[c :]
    z = y[::-1]

else:
    x = a[:c]
    y = a[c + 1:]
    z = y[::-1]

ans = 0

for i in range(len(a)//2):
    if x[i] != z[i]:
        ans += 1

print(ans)


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

char str[2000050];

int main() {
    scanf("%s", str);
    int idx = 0;
    while (str[idx] != 'A') idx++;
    int idx2 = strlen(str) - 1;
    while (str[idx2] != 'Z') idx2--;
    printf("%d\n", idx2 - idx + 1);
    return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
cin>>n;
int a[200000];
for(int i=0;i<n;i++)
cin>>a[i];
int k=0;
int i,j;
for(i=0,j=1;i<n;i++)
{
if(a[i]==j)
j++;
}
if(j==1)
cout<<"-1"<<endl;
else
cout<<n-j+1<<endl;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

vector<int> v[123456];

int main(void){
	int n,m,p[123456],y[123456],t,i;
	cin >> n >> m;
	for(i=0; i<m; ++i){
		cin >> p[i] >> y[i];
		v[p[i]-1].push_back(y[i]);
	}
	for(i=0; i<n; ++i){
		if(v[i].l_ength()){
			sort(v[i].begin(),v[i].end());
		}
	}
	for(i=0; i<m; ++i){
		t = (int)(upper_bound(v[p[i]-1].begin(),v[p[i]-1].end(),y[i])-(v[p[i]-1].begin()));
		printf("%06d%06d\n",p[i],t);
	}
	return 0;
}


Measured memory_bytes: 8320
#include<iostream>
#include<cstdio>
#include<cctype>
using namespace std;
int main(){
    char name[1001];
    int a=0;
    int sum=0;
    while(1){
        scanf("%s", name);
        if(name[0]=='0') break;
        else{
            while(name[a]!='\0'){
                sum=sum+name[a]-48;
                a+=1;
            }printf("%d\n",sum);
            a=0;
            sum=0;
        }
    }
}



Measured memory_bytes: 3188
#include<stdio.h>
#include<stdlib.h>

void CountingSort(int);
int n;
int A[2000001], B[2000001];

int main(){
  int i;
  int Amax=0;

  scanf("%d", &n);
  if(n < 1 || 2000000 < n)
    exit(0);

  for(i = 1; i <= n; i++){
    scanf("%d", &A[i]);
    if(A[i] < 0 || 10000 < A[i])
      exit(1);
    if(Amax < A[i])
      Amax = A[i];
  }

  CountingSort(Amax);

  for(i = 1; i <= n; i++){
    if(i == n)
      printf("%d\n", B[i]);
    else
      printf("%d ", B[i]);
  }

  return 0;
}

void CountingSort(int k){
  int i, j;
  int C[2000001];

  for(i = 0; i <= k; i++)
    C[i] = 0;
  
  for(j = 1; j <= n; j++)
    C[A[j]]++;

  for(i = 1; i <= k; i++)
    C[i] += C[i-1];

  for(j = n; 1 <= j; j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }

}

Measured memory_bytes: 16264
#include<iostream>
#include<algorithm>
#include <iostream> 
#include <algorithm> 
#include<string>
#include<queue>
#include<utility>
#include<fstream>
#include<queue>
#include<set>
#include<stack>
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define I(a) scanf("%d",&a)
#define I2(a,b) scanf("%d%d",&a,&b)
#define I3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define L(a) scanf("%lld",&a)
#define L2(a,b) scanf("%lld%lld",&a,&b)
#define L3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define PI(a) printf("%d",a)
#define PL(a) printf("%lld",a)
#define PT(t) printf("Case %d: ",t)
#define PB push_back
#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define SC scanf
#define PC printf
#define NL printf("\n")
#define SET(a) memset(a,0,sizeof a)
#define SETR(a) memset(a,-1,sizeof a)
#define SZ(a) ((int)a.size())-1
#define f(i,a,b) for(int i=a;i<=b; i++)
#define fr(i,a,b) for(int i=a;i<=b; i++)
#define frr(i,a,b) for(int i=a;i>=b; i--)
#define frv(i,a)  for(int i=0;i<a.size();i++)
#define pi 2.0*acos(0.0)
#define R(a) freopen(a, "r", stdin);
#define W(a) freopen(a, "w", stdout);
#define CB(x) __builtin_popcount(x)
#define STN(a) stringtonumber<ll>(a)
#define lol printf("BUG\n")
#define Endl "\n"
#define mk make_pair
using namespace std;
template <class T> inline T BM(T p, T e, T M)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a, T b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}
template <class T> inline T mdINV(T a, T M)
{
    return BM(a, M - 2, M);
}
template <class T> inline T PW(T p, T e)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p);
        p = (p * p);
    }
    return (T)ret;
}
 
 
template <class T>bool ISLEFT(T a, T b, T c)
{
    if(((a.xx - b.xx) * (b.yy - c.yy) - (b.xx - c.xx) * (a.yy - b.yy)) < 0.0)return 1;  //Uporer dike //A,b,c, x okkher ordera sorted
    else return 0;
}
 
 
typedef pair<int,int >P;
//////////////////////////
/////////////////////////
//

int main(){

 int n;
 I(n);

 ll ar[n+2];
 ll dp[n+2];
 memset(dp,0,sizeof dp);

 for(int i=1;i<=n;i++){
     L(ar[i]);
     dp[i] = gcd(dp[i-1],ar[i]);
 }
 ll dp1[n+2];
 SET(dp1);
 ll res = 0;
 for(int i=n;i>=1;i--){
     dp1[i] = gcd(dp1[i+1], ar[i]);
     res = max(res, gcd(dp[i-1],dp1[i+1]));
 }
 cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 2560
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
xy = []
for i in range(N):
	A = INT()
	xy.append([LIST() for _ in range(A)])

ans = 0
for i in range(1<<N):
	i = "{:b}".format(i).zfill(N)
	flag = 0
	for j in range(N):
		if i[j] == '1': # 正直者
			for x, y in xy[j]:
				if y != int(i[x-1]):
					flag = 1
					break
		if flag == 1:
			break
	else:
		tmp = sum(map(int, list(i)))
		ans = ans if ans >= tmp else tmp
print(ans)


Measured memory_bytes: 5712
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

struct before_main{before_main(){cin.tie(0); ios::sync_with_stdio(false);}} before_main;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

template<class T, class U, class Compare>
void pair_sort(vector<T>& a, vector<U>& b, Compare comp) {
  vector<pair<T, U>> v;
  rep(i, a.size()) v.emplace_back(a[i], b[i]);
  sort(v.begin(), v.end(), comp);
  rep(i, a.size()) tie(a[i], b[i]) = v[i];
}
template<class T, class U>
void pair_sort(vector<T>& a, vector<U>& b) {
  pair_sort(a, b, std::less<pair<T, U>>());
}

typedef long long ll;
int const inf = 1e9;

int T, N;
int t[33];
int M[111];
int dp[111][33];

int solve() {

  rep(i, 111) rep(j, 33) dp[i][j] = inf;

  dp[0][T-1] = 0;
  REP(i, 1, 101) {
    rep(j, T) {
      if(t[(j+1)%T] <= M[i]) {
        minimize(dp[i][(j+1)%T], dp[i-1][j]);
        minimize(dp[i][T-1], dp[i-1][j] + 1);
      }
    }
  }

  return *min_element(dp[100], dp[100] + T);
}

int main() {

  for(; cin >> T && T;) {
    rep(i, T) cin >> t[i];
    cin >> N;
    rep(i, 111) M[i] = inf;
    rep(i, N) {
      int d, m; cin >> d >> m;
      minimize(M[d], m);
    }
    cout << solve() << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3136
N = int(input())
a = list(map(int, input().split()))

ma = a[0]
mi = a[0]
maN = 0
miN = 0
for i in range(N):
  if a[i] > ma:
    ma = a[i]
    maN = i
  elif a[i] < mi:
    mi = a[i]
    miN = i

if abs(ma) > abs(mi):
  t = maN + 1
  f = 1
else:
  t = miN + 1
  f = -1

print(N * 2 - 1)
for i in range(1, N + 1):
  print(t, i)

if f == 1:
  for i in range(1, N):
    print(i, i + 1)
else:
  for i in range(N, 1, -1):
    print(i, i - 1)

Measured memory_bytes: 3064
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    N,M=pin()
    cond=M<N
    print(["unsafe","safe"][cond])
#%%submit!
resolve()

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

#define INF INT_MAX

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

int main(void){
 	cin.tie(0);
    ios::sync_with_stdio(false);
	string s;
	cin >> s;
	string ans;
	int a = (s[0] - '0')*10 + (s[1] - '0');
	int b = (s[2] - '0')*10 + (s[3] - '0');
	if(1 <= a && a <= 12){
		if(1 <= b && b <= 12){
			ans = "AMBIGUOUS";
		}else if(0 == b || 12 < b){
			ans = "MMYY";
		}else{
			ans = "NA";
		}
	}else if(0 == a || 12 < a){
		if(1 <= b && b <= 12){
			ans = "YYMM";
		}else if(0 == b || 12 < b){
			ans = "NA";
		}
	}else{
		ans = "NA";
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
n,m = map(int,input().split())
a = set()
b = set()
for i in range(m):
    c,d = map(int,input().split())
    if c == 1:
        b.add(d)
    elif d == n:
        a.add(c)
if len(a&b)>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 19024
import numpy as np

N = int(input())

B = np.array([0]*N)

l = input().split()

for i in range(N):
    B[i] = int(l[i]) - (i+1)
    
B = np.sort(B)

if N % 2 == 1:
    b_mid = B[int(N/2)]
else:
    mid = int(N/2) - 1
    b_mid = int( (B[mid] + B[mid+1])/2 )

dif = B - b_mid

print(np.sum(abs(dif)))

Measured memory_bytes: 31344
#include <iostream>
using namespace std;
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
void solve(){
	
}
int main() {
	int n;
	cin>>n;
	set<string>p;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		p.insert(s);
	}
	cout<<p.size();
	return 0;
}

Measured memory_bytes: 19260
n,k=map(int,input().split())
L=[0]*n
for i in range(k):
    d=int(input())
    A=list(map(int,input().split()))
    for j in range(d):
        if L[A[j-1]-1]==0:
            L[A[j-1]-1]+=1
print(n-sum(L))
            

Measured memory_bytes: 9196
#include<iostream>
using namespace std;
int main(){
  int k,s;
  cin >> k >> s;
  int res = 0;
  for(int a=0; a < k+1; a++){
    for(int b=0; b < k+1; b++){
      int total = a + b;
      if(0 <= s - total && s - total <= k)++res;
    }
  }
  cout << res << endl;
  return 0;
}
    


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main() {
	int n, i;
	long long a[1000]{ 0 }, b[1000]{ 0 }, aa[1000]{ 0 }, bb[1000]{ 0 }, c, d;
	double ab = 0, nab = 0;

	cin >> n;

	for (i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}

	aa[0] = a[0];
	bb[0] = b[0];
	ab = a[0] / b[0];

	//cout << aa[0] << " " << bb[0] << endl;

	for (i = 1; i < n; i++) {
			c = aa[i - 1] / a[i];
			d = bb[i - 1] / b[i];
			if (c < d) {
				if ((bb[i - 1] % b[i]) != 0) d++;
				c = d;
			}
			else {
				if ((aa[i - 1] % a[i]) != 0) c++;
			}
		
		ab = nab;
		aa[i] = a[i] * c;
		bb[i] = b[i] * c;
		while (-1) {
			if (aa[i] < aa[i - 1] || bb[i] < bb[i - 1]) {
				aa[i] += a[i];
				bb[i] += b[i];
				//cout << "add ";
			}
			else break;
		}
		//cout << aa[i] << " " << bb[i] << endl;
	}

	cout << aa[n - 1] + bb[n - 1] << endl;

	return 0;

}



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

int main(){
  
  long long N, M, i, Sum=1;
  cin>>N>>M;
  
  for(i=1; i<=N; i++){
    Sum*=i;
    if(Sum>1000000007) Sum%=1000000007;
  }
  for(i=1; i<=M; i++){
    Sum*=i;
    if(Sum>1000000007) Sum%=1000000007;
  }
  cout<<(Sum*max(2-abs(N-M), 0ll))%1000000007<<endl;
  return 0;
}

Measured memory_bytes: 3612
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))

DIV = 10 ** 9 + 7
ans = 0
cur = 0
for i in range(1, N):
  cur += A[i - 1]
  ans += A[i] * cur
  ans %= DIV
  
print(ans)

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

const int INF = 2e9;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    map<ll,ll> mp;
    rep(i,n){
        cin >> a[i];
        mp[a[i]]++;
    }
    ll sum = 0;
    rep(i,n){
        sum += (mp[i+1] * (mp[i+1] - 1))/2;
    }
    rep(i,n){
        ll ans = sum;
        ans -= (mp[a[i]] * (mp[a[i]] - 1)/2 - (mp[a[i]] - 1) * (mp[a[i]] - 2)/2);
        cout << ans << endl;
    }
}

Measured memory_bytes: 16640
#include <stdio.h>

int main(void){
  int i,n,a[100]={0};
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  for(i=n-1;i>0;i--){
    printf("%d ",a[i]);
  }
  printf("%d\n",a[0]);
  return 0;
}

Measured memory_bytes: 596
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;

int main()
{
    std::string s;
    std::cin >> s;

    int n;
    std::cin >> n;

    for (int i = 0; i < s.length(); i += n) {
        std::cout << s[i];
    }
    putchar('\n');
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define llint long long
#define inf 1e18
#define mod 1000000007

using namespace std;

llint n;
vector<llint> G[200005];
llint size[200005], par[200005];
llint p[200005], q[200005];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

llint dfs(llint v, llint p)
{
	size[v] = 1, par[v] = p;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == p) continue;
		size[v] += dfs(G[v][i], v);
	}
	return size[v];
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	llint u, v;
	for(int i = 1; i <= n-1; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, -1);
	
	llint inv2 = modpow(2, mod-2);
	for(int i = 1; i <= n; i++){
		p[i] = 1 - modpow(inv2, i) + mod, p[i] %= mod;
		q[i] = p[i] * modpow((1-p[i]+mod)%mod, mod-2) % mod;
	}
	
	llint ans = 0;
	for(int i = 1; i <= n; i++){
		vector<llint> vec;
		for(int j = 0; j < G[i].size(); j++){
			if(G[i][j] != par[i] && size[G[i][j]] > 0) vec.push_back(size[G[i][j]]);
		}
		if(i != 1 && n-size[i] > 0) vec.push_back(n-size[i]);
		if(vec.size() < 2) continue;
		
		llint tmp = 0, mul = 1;
		for(int i = 0; i < vec.size(); i++) mul *= (1-p[vec[i]]+mod)%mod, mul %= mod;
		tmp += mul, tmp %= mod;
		for(int i = 0; i < vec.size(); i++){
			tmp += mul * q[vec[i]] % mod, tmp %= mod;
		}
		tmp = 1 - tmp + mod, tmp %= mod;
		tmp *= inv2, tmp %= mod;
		ans += tmp, ans %= mod;
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 24448
// Author: getharshkumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll a, b;
    cin >> a >> b, a += b;
    if (a % 2)
        cout << "IMPOSSIBLE";
    else
        cout << a / 2;
    return 0;
}

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

#define rep(i, n)  for (int i = 0; i < (int) (n); i++)
#define Rrep(i, n) for (int i = ((int) n - 1); i >= 0; i--)
#define all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
#define INF 2e15
#define MOD 10e9 + 7

typedef vector <int> vint;
typedef long long    ll;



int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    int n, m;
    cin >> n >> m;
    if (n == m) { cout << "Yes" << endl; }
    else { cout << "No" << endl; }

    return 0;
}


Measured memory_bytes: 256
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.System.exit;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static void solve() throws Exception {
		String s = scanString();
		long ans = 0;
		int ca = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == 'A') {
				++ca;
			} else if (i + 1 < s.length() && s.charAt(i) == 66 && s.charAt(i + 1) == 'C') {
				ans += ca;
				++i;
			} else {
				ca = 0;
			}
		}
		out.print(ans);
	}

	static int scanInt() throws IOException {
		return parseInt(scanString());
	}

	static long scanLong() throws IOException {
		return parseLong(scanString());
	}

	static String scanString() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	public static void main(String[] args) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			exit(1);
		}
	}
}

Measured memory_bytes: 25940
#include<stdio.h>
#include<string.h>
main(){
  char str[85];
  int l,i;
  while(fgets(str,81,stdin)!=NULL){
    l=strlen(str);
    while(1){
      if(strstr(str,"the ")!='\0'||strstr(str,"this ")!='\0'||strstr(str,"that ")!='\0'){
    break;
      } else {
    for(i=0;i<l;i++){
      if(str[i]>='a'&&str[i]<='y')str[i]+=1;
      else if(str[i]=='z') str[i]='a';
    }
      }
    }
    printf("%s",str);
  }
  return 0;
}


Measured memory_bytes: 1980