akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
	int n, m, in0, in1;
    cin >> n >> m;
    vector<vector<int>> ns(0, vector<int>(3));
    rep(i, m){
      cin >> in0 >> in1;
      ns.push_back({in0, in1, i});
    }
    sort(ns.begin(), ns.end());
    int memo = ns.at(0).at(0);
    int k = 0;
    rep(i, m){
      if(memo == ns.at(i).at(0)){
        k++;
      }else{
        k = 1;
      }
      ns.at(i).at(1) = k;
      memo = ns.at(i).at(0);
    }
    rep(i, m){
      memo = ns.at(i).at(0);
      ns.at(i).at(0) = ns.at(i).at(2);
      ns.at(i).at(2) = memo;
    }
    sort(ns.begin(), ns.end());
    rep(i, m){
      string st0, st1;
      st0 = "";
      st1 = "";
      while(ns.at(i).at(2) != 0){
        memo = ns.at(i).at(2)%10 + '0';
        st0 += memo;
        ns.at(i).at(2) /= 10;
      }
      while(ns.at(i).at(1) != 0){
        memo = ns.at(i).at(1)%10 + '0';
        st1 += memo;
        ns.at(i).at(1) /= 10;
      }
      memo = 6 - st0.size();
      rep(i, memo){
        st0 += '0';
      }
      memo = 6 - st1.size();
      rep(i, memo){
        st1 += '0';
      }
      reverse(st0.begin(), st0.end());
      reverse(st1.begin(), st1.end());
      cout << st0 << st1 << endl;
    }
    return 0;
}

Measured memory_bytes: 7344
import numpy as np

n,k=map(int,input().split())

a=np.array(input().split(),dtype=np.int64)
f=np.array(input().split(),dtype=np.int64)

a.sort()
f.sort()
f=f[::-1]
af=a*f

# r以下にするのに必要修行回数がk以内かどうか
def safe(r):
    return (np.maximum(0,(af-r+f-1)//f)).sum()<=k
    
m=-1
M=10**12

while m+1<M:
    pos=(m+M)//2
    if safe(pos):
        M=pos
    else:
        m=pos
print(M)

Measured memory_bytes: 37204
#include "bits/stdc++.h"
#include<assert.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
#define MRE assert(0);
const int inf = 20;
const int mod = 998244353;
typedef pair<int, int> P;
typedef pair<int, P> PP;

int popcnt(int x) {
	int res = 0;
	rep(i, 21) {
		if (x&(1 << i))res++;
	}
	return res;
}

vector<int>grey(int len) {//2^len
	vector<int>res;
	rep(i, 1 << len) {
		res.push_back(i ^ (i >> 1));
	}
	return res;
}

int reversebit(int x,int len) {
	int r = 0;
	while (len--) {
		r <<= 1;
		r |= (x & 1);
		x >>= 1;
	}
	return r;
}

vector<int>conv(int x, int y,int len) {//xからyへの変換
	vector<int>v1, v2;
	rep(i, len) {
		if (x&(1 << i))v1.push_back(i);
		if (y&(1 << i))v2.push_back(i);
	}
	if (v1.size() != v2.size())MRE;
	rep(i, len) {
		if ((x&(1 << i)) == 0)v1.push_back(i);
		if ((y&(1 << i)) == 0)v2.push_back(i);
	}
	vector<int>v3(len);
	rep(i, len) {
		v3[v1[i]] = v2[i];
	}
	return v3;
}

void disp(vector<int>V) {
	rep(i, V.size()) {
		if (i)cout << ' '; cout << V[i];
	}cout << endl;
}

signed main() {
	int n, a, b; cin >> n >> a >> b;
	int B = a^b;
	if (popcnt(B) % 2 == 0) {
		puts("NO"); return 0;
	}
	puts("YES");
	int N = 1 << n;
	vector<int>ans(N);
	int remcnt = popcnt(B), topbit = n-1, toppos = 0;
	int rev = 0;
/*
	ans = grey(1);
	rep(i, ans.size()) {
		cout << bitset<1>(reversebit(ans[i], 1)) << endl;
	}return 0;
*/
	while (remcnt) {
		vector<int>G;
		if (remcnt == 1) {
			G = grey(topbit + 1);
			rep(i, G.size())G[i]=reversebit(G[i], topbit + 1);

			if (rev&1)reverse(G.begin(), G.end());
			for (int i = toppos; i < N; i++)ans[i] += G[i - toppos];
			remcnt--;
		}
		else {
			int mi = toppos + N; mi /= 2;
			for (int i = mi; i < N; i++) {
				ans[i] += 1 << topbit;
			}
			G = grey(topbit);
			rep(i, G.size())G[i]=reversebit(G[i], topbit);

			if (rev&1)reverse(G.begin(), G.end());
			for (int i = toppos; i < mi; i++)ans[i] += G[i - toppos];
			toppos = mi;
			topbit--;
			remcnt--;
			rev++;
		}
		/*
		cout << remcnt << ' ' << topbit << ' ' << toppos << endl;
rep(i, N) {
		cout << bitset<n>(ans[i]) << endl;
}cout << endl;
*/
	}


	vector<int>con = conv(ans[N - 1], B, n);
	vector<int>ans2;
	rep(i, N) {
		int nxt = 0;
		rep(j, n) {
			int Z = (ans[i] & (1 << j));
			if (Z) {
				nxt += 1 << con[j];
			}
		}
		nxt ^= a;
		ans2.push_back(nxt);
	}
	disp(ans2);
}

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

int main() {
    int N;
    cin >> N;
    N %= 10;
    if(N == 2 || N == 4 || N == 5 || N == 7 || N == 9) {
        cout << "hon" << endl;
    } else if(N == 3) {
        cout << "bon" << endl;
    } else {
        cout << "pon" << endl;
    }
    return 0;
}

Measured memory_bytes: 3604
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <cstdlib>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()
#pragma endregion


int main()
{
	int x; cin >> x;
	for (ll a = 1; a <= 1000; ++a)
	{
		for (ll b = -1000; b <= a; ++b)
		{
			if (powl(a, 5) - powl(b, 5) == x)
			{
				cout << a << " " << b << endl;
				return 0;
			}
		}
	}
}

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

int main(){
  ll n;
  std::cin >> n;
  std::vector<ll> a(n);
  rep(i,n)std::cin >> a[i];


  ll ma=a[0];

  ll sum=0;
  for (ll i = 1; i < n; i++) {
    if(ma>a[i]){
      sum+=ma-a[i];
    }
    else ma=a[i];
  }

  std::cout << sum << '\n';




  return 0;
}


Measured memory_bytes: 4792
n=int(input())
a=list(map(int,input().split()))
total=sum(a)
x=0
ans=abs(max(a)-min(a))
for i in range(n-1):
    x+=a[i]
    if abs(2*x-total)<ans:
        ans=abs(2*x-total)
print(ans)


Measured memory_bytes: 24832
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define ln '\n'
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
typedef long long ll;
typedef unsigned long long ull; 
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
///////////////////////////////////////////////////////////////////////////////////////////////////

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
	return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
	return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
	return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
	return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
	a += rhs.a;
	if (a >= Modulus) {
	  a -= Modulus;
	}
	return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
	if (a < rhs.a) {
	  a += Modulus;
	}
	a -= rhs.a;
	return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
	a = a * rhs.a % Modulus;
	return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
	u64 exp = Modulus - 2;
	while (exp) {
	  if (exp % 2) {
		*this *= rhs;
	  }
	  rhs *= rhs;
	  exp /= 2;
	}
	return *this;
  }
};

using mint = modint<MOD>;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
	string S; cin >> S;
	int N = S.size();

	vector<mint> A(N+1),B(N+1),C(N+1);
	mint Q = 1;
	rep(i,N) {
		A[i+1] += A[i];
		B[i+1] += B[i];
		C[i+1] += C[i];
		if (S[i] == 'A') A[i+1] += Q;
		if (S[i] == 'B') B[i+1] += A[i];
		if (S[i] == 'C') C[i+1] += B[i];
		if (S[i] == '?') {
			A[i+1] += Q;
			B[i+1] += A[i];
			C[i+1] += B[i];
			A[i+1] += A[i]*2;
			B[i+1] += B[i]*2;
			C[i+1] += C[i]*2;
			Q *= 3;
		}
		//cout << A[i+1].a << " " << B[i+1].a << " " << C[i+1].a << ln;
	}

	cout << C[N].a << ln;
}


Measured memory_bytes: 2896
#define _LIBCPP_DEBUG 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9+7;

int main() {

    while(true){
        int dansu;
        cin>>dansu;
        if(dansu==0) break;

        vector<double> dp(31, 0);
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for (int i = 2; i <= dansu; ++i) {
            dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
        cout<<ceil(dp[dansu]/10/365)<<endl;
    }

    return 0;
}


Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
int main()
{
    ll K;
    cin >> K;
    if(K%2 == 0 || K%5 == 0){
        cout << -1 << endl;
    }
    else{
        ll c = 1;
        ll a = 7;
        while(true){
            if(a % K == 0){
                cout << c << endl;
                return 0;
            }
            else{
                a *= 10;
                a += 7;
                a %= K;
                c++;
            }
        }
    }
}

Measured memory_bytes: 3632
import heapq

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

sa = 0
sb = 0
hf = []
hb = []
la = [[0]*2 for i in range(n+1)]
for i in range(n):
    sa += A[i]
    heapq.heappush(hf,A[i])
for i in range(2*n,3*n):
    sb += A[i]
    heapq.heappush(hb,-A[i])
la[0][0] = sa
la[-1][-1] = sb
for i in range(n,2*n):
    now = A[i]
    now2 = A[-1-i]
    heapq.heappush(hf,now)
    heapq.heappush(hb,-now2)
    h1 = heapq.heappop(hf)
    h2 = -heapq.heappop(hb)
    sa += now-h1
    sb += now2 -h2
    la[i-n+1][0] = sa
    la[-i+n-2][1] = sb

ans = -float("INF")
for i,j in la:
    ans = max(ans,i-j)
print(ans)


Measured memory_bytes: 125856
using System;
using System.Linq;
using System.Collections.Generic;

class Test
{
    static void Main()
    {
        string[] r = Console.ReadLine().Split();
        int n = int.Parse(r[0]);
        int q = int.Parse(r[1]);

        PriorityQueue[] Q = new PriorityQueue[n];
        for (int i = 0; i < n; i++)
        {
            Q[i] = new PriorityQueue(); ;
        }

        for (int i = 0; i < q; i++)
        {
            int[] array = Console.ReadLine().Split().Select(int.Parse).ToArray();

            switch (array[0])
            {
                case 0:
                    Q[array[1]].Insert(array[2]);
                    break;
                case 1:
                    if (Q[array[1]].pq.Count != 0) Console.WriteLine(Q[array[1]].GetMax());
                    break;
                case 2:
                    if (Q[array[1]].pq.Count != 0) Q[array[1]].DeleteMax();
                    break;
            }
        }
    }
}

class PriorityQueue
{
    public List<int> pq;

    public PriorityQueue()
    {
        pq = new List<int>();
    }

    public void Insert(int x)
    {
        pq.Add(x);
        int child = pq.Count - 1;
        int parent = (child - 1) / 2;
        while (child != 0)
        {
            if (pq[child] > pq[parent])
            {
                int temp = pq[child];
                pq[child] = pq[parent];
                pq[parent] = temp;
            }
            child = parent;
            parent = (child - 1) / 2;
        }
    }

    public int GetMax()
    {
        return pq[0];
    }

    public void DeleteMax()
    {
        pq[0] = pq[pq.Count - 1];

        pq.RemoveAt(pq.Count - 1);

        int parent = 0;
        int child = 0;
        while (parent * 2 + 1 <= pq.Count - 1 || parent * 2 + 1 <= pq.Count - 1)
        {
            int child1 = parent * 2 + 1;
            int child2 = parent * 2 + 2;
            if (child2 > pq.Count - 1) child = child1;
            else child = pq[child1] > pq[child2] ? child1 : child2;
            if (pq[parent] < pq[child])
            {
                int swap = pq[parent];
                pq[parent] = pq[child];
                pq[child] = swap;
            }
            parent = child;
        }
    }
}




Measured memory_bytes: 25108
def kaibun(S):
    for i in range(len(S)):
        if S[i] != S[-(i+1)]:
            break
    else:
        return True
    return False
S = input()
if kaibun(S) and kaibun(S[:int((len(S)-1)/2)]) and kaibun(S[int((len(S) + 3)/2-1): ]):
    print("Yes")
else:
    print("No")


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

int main(){
    int h,a;
    cin >> h >> a;
    int ans;
    if (h%a==0){
        ans=h/a;
    }
    else{
    ans=h/a+1;
    }
    cout << ans << endl;
    

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int a, b;
	cin >> a >> b;
	for(int i=1; i<=1000; ++i) {
		int a2=i*8/100, b2=i*10/100;
		if(a2==a&&b2==b) {
			cout << i;
			return 0;
		}
	}
	cout << -1;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<queue>
#include<vector>
#define nmax 1001
using namespace std;
typedef struct{
    int dist;
    vector<int> root;
}Node;
int n,m;
int main(void){
    cin >> n >> m;
    vector< vector<int> > g(n);
    for(int i=0;i<m;i++){
        int a, b; cin >> a >> b;
        g[a-1].push_back(b-1);
    }int shortest = nmax; int init=0;
    vector <int> ans;
    for(int i=0;i<n;i++){
        Node used[nmax]={0};
        queue<int> que;
        for(int j=0;j<g[i].size();j++){
            que.push(g[i][j]);
            used[g[i][j]].dist = 1;
            used[g[i][j]].root.push_back(g[i][j]);
        }
        while(!que.empty()){
            int x = que.front(); que.pop();
            if(x==i){//ゴール
                if(shortest>used[x].dist){
                    init = i;
                    shortest = used[x].dist;
                    ans = used[x].root;
                }
            }else{
                for(int j=0;j<g[x].size();j++){
                    if(used[g[x][j]].dist==0){
                        used[g[x][j]].dist = used[x].dist + 1;
                        used[g[x][j]].root = used[x].root;
                        used[g[x][j]].root.push_back(g[x][j]);
                        que.push(g[x][j]);
                    }
                }
            }
        }
    }
    //cout << init+1 << "," << shortest << endl;
    if(shortest!=nmax){
        cout << ans.size() << endl;
        for(int i=0;i<ans.size();i++){
            cout << ans[i]+1 << endl;
        }
    }
    else cout << -1 << endl;
}


Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define pb push_back
#define fi first
#define se second


int main(){
    ll i,j;
    string s;
    cin>>s;
    ll l=s.size();

    string aa="keyence";

    ll f=1;
    ll mae=0;
    ll usiro=0;

    for(i=0;i<7;i++){
        if(s[i]==aa[i]&&f==1) mae++;
        else f=0;
    }
    f=1;
    for(i=0;i<7;i++){
        if(s[l-1-i]==aa[7-1-i]&&f==1) usiro++;
        else f=0;
    }

    string ans="NO";
    if(mae+usiro>=7) ans="YES";
    cout<<ans<<endl;
    return 0;
    
}


Measured memory_bytes: 256
from collections import defaultdict


def main():
    w = input()
    d = defaultdict(int)
    for c in w:
        d[c] += 1
    ans = 'Yes'
    for cnt in d.values():
        if cnt & 1 == 1:
            ans = 'No'
            break
    print(ans)

if __name__ == '__main__':
    main()


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

// @@ !! LIM(mod)
// --> f:gcd mod
// ---- inserted function gcd from util.cc
// g = eGCD(a, b, s, t)  --->  sa + tb = g
ll eGCD(ll a, ll b, ll& s, ll& t) {
  if (a == 0) {
    s = 0;
    t = 1;
    return b;
  }
  ll u = 0;
  ll g = eGCD(b % a, a, t, u);
  s = u - (b / a) * t;
  return g;
}

// gcd(0, x) = x, gcd(-x, y) = gcd(x, y)
ll gcd(ll a, ll b) {
  ll dummy1 = 0;
  ll dummy2 = 0;
  return eGCD(abs(a), abs(b), dummy1, dummy2);
}
// ---- end gcd
// ---- inserted library file mod.cc

ll MOD = 1e9 + 7;
// ll MOD = 998244353;

struct Fp {
  ll val;

  Fp(ll t = 0) {
    if      (t >= MOD)  val = t % MOD;
    else if (t >= 0)    val = t;
    else if (t >= -MOD) val = t + MOD;
    else {
      ll v = t % MOD;
      if (v == 0) val = 0;
      else        val = v + MOD;
    }
  }

  Fp& operator +=(const Fp& t) {
    val += t.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }

  Fp& operator -=(const Fp& t) {
    val -= t.val;
    if (val < 0) val += MOD;
    return *this;
  }

  Fp& operator *=(const Fp& t) {
    val = (val * t.val) % MOD;
    return *this;
  }

  Fp inv() const {
    if (val == 0) {
      cerr << "inv() is called for zero." << endl;
      exit(1);
    }
    ll u = 0;
    ll v = 0;
    eGCD(val, MOD, u, v);
    return Fp(u);
  }

  Fp& operator /=(const Fp& t) {
    return (*this) *= t.inv();
  }

  Fp operator +(const Fp& t) const { return Fp(val) += t; }
  Fp operator -(const Fp& t) const { return Fp(val) -= t; }
  Fp operator *(const Fp& t) const { return Fp(val) *= t; }
  Fp operator /(const Fp& t) const { return Fp(val) /= t; }
  Fp operator -() const { return Fp(-val); }

  bool operator ==(const Fp& t) const { return val == t.val; }
  bool operator !=(const Fp& t) const { return val != t.val; }
  
  operator ll() const { return val; }

};

class Comb {
  int nMax;
  vector<Fp> vFact;
  vector<Fp> vInvFact;
public:
  Comb(int nm) : nMax(nm), vFact(nm+1), vInvFact(nm+1) {
    vFact.at(0) = 1;
    for (int i = 1; i <= nMax; i++) vFact.at(i) = i * vFact.at(i-1);
    vInvFact.at(nMax) = vFact.at(nMax).inv();
    for (int i = nMax; i >= 1; i--) vInvFact.at(i-1) = i * vInvFact.at(i);
  }
  Fp fact(int n) { return vFact.at(n); }
  Fp comb(int n, int r) {
    return vFact.at(n) * vInvFact.at(r) * vInvFact.at(n-r);
  }
  // The number of permutation extracting r from n.
  Fp perm(int n, int r) {
    return vFact.at(n) * vInvFact.at(n-r);
  }
};

// ---- end mod.cc
// @@ !! LIM  -- end mark --

ll solve() {
  ll N; cin >> N;
  vector<ll> v(N);
  for (ll i = 0; i < N; i++) {
    ll x; cin >> x;
    v.at(x)++;
  }
  Fp ans = 1;
  if (N % 2 == 0) {
    for (ll i = 1; i <= N-1; i+= 2) {
      if (v.at(i) != 2)  return 0;
      ans *= Fp(2);
    }
  }else {
    if (v.at(0) != 1) return 0;
    for (ll i = 2; i <= N-1; i+= 2) {
      if (v.at(i) != 2) return 0;
      ans *= Fp(2);
    }
  }
  return (ll)ans;

}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);
  cout << solve() << endl;

  return 0;
}



Measured memory_bytes: 1024
n, x, m = gets.split(' ').map(&:to_i)
a = x
seen = {}
sum = 0

i = 0
start = nil
nums = []
while i < n
  nums << a
  if seen[a]
    start = seen[a]
    break
  end
  sum += a
  seen[a] = i
  i += 1
  a = (a * a) % m
end
if i == n
  puts sum
  exit
end
len = i - start

rangesum = 0
(start...i).each do |j|
  rangesum += nums[j]
end

slots = (n - i) / len
r = (n - i) % len
total = sum + rangesum * slots
r.times do
  total += a
  a = (a * a) % m
end

puts total


Measured memory_bytes: 17060
/*
  ∧,,∧
( 'ω' )つ ＜WA,またお前か！！　
（m9 ＼ 　　
　 ＼　 ＼
　 　 ) ) ＼
　 ／／ ＼ ＼
　 (＿） 　 (＿)
*/

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

#define all(x) (x).begin(),(x).end()

typedef long long LL;
typedef long double LD;

bool compare_by_a(pair<int, int> a, pair<int, int> b)
{
    if (a.first != b.first) {
        return a.first < b.first;
    } else {
        return a.second < a.second;
    }
}

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

ostringstream oss_global;
string s_global = oss_global.str();

int main()
{
    string S;
    cin >> S;
    vector<int> seq(4, 0);
    for (int i = 0; i < 4; i++)
        seq[i] = S[i] - '0';

    string ans;
    int first, second = 0;
    int A, B;
    A = B = 0;
    first = 10*seq[0] + seq[1];
    second = 10*seq[2] + seq[3];

    if (first >= 1 && first <= 12) A = 1;
    if (second >= 1 && second <= 12) B = 1;

    if (A && B) ans = "AMBIGUOUS";
    else if (A) ans = "MMYY";
    else if (B) ans = "YYMM";
    else ans = "NA";

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <set>

using namespace std;

const int N = 100005;

int n , a[N];
int b[N], c[N];

set < pair<int, int> > q1, q2;
set < pair<int, int> >::iterator it1 , it2;

int main() {
	cin >> n;
	int mxb = 0 , mxc = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		if (i % 2) {
			q1.erase(make_pair(b[a[i]], a[i]));
			b[a[i]]++;
			q1.insert(make_pair(b[a[i]], a[i]));
		}
		else {
			q2.erase(make_pair(c[a[i]], a[i]));
			c[a[i]]++;
			q2.insert(make_pair(c[a[i]], a[i]));
		}
	}
	q1.insert(make_pair(0, n + 5));
	q2.insert(make_pair(0, n + 5));
	it1 = q1.end();
	it2 = q2.end();
	--it1;
	--it2;

	if ((*it1).second != (*it2).second) {
		cout << n - (*it1).first - (*it2).first << endl;
	}
	else {
		--it1;
		int pat = n - (*it1).first - (*it2).first;
		++it1;
		--it2;
		pat = min(pat, n - (*it1).first - (*it2).first);
		cout << pat << endl;
	}
	return 0;
}

Measured memory_bytes: 6144
using System;

public class Test
{
	public static void Main()
	{
		string line = System.Console.ReadLine();
   		string[] ab = line.Split(' ');
   		int a = Convert.ToInt32(ab[0]);
		int b = Convert.ToInt32(ab[1]);
   		Console.WriteLine("{0} {1}",a*b,2*(a+b));
	}
}

Measured memory_bytes: 9280
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>
#include <numeric>
#include <cassert>
#ifdef DEBUG
#include "./Lib/debug.hpp"
#else
#define dump(...)
template<class T>inline auto d_val(T a, T b) { return a; }
#endif

/* (=＾o＾=) */
#define int ll

/* macro */
#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define REPI2(it,b,e) for(auto it = (b); it != (e); ++it)
#define REPI(it,c) REPI2(it, (c).begin(), (c).end())
#define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend())
#define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);)
#define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end())
#define ALL(x) (x).begin(),(x).end()
#define cauto const auto&
/* macro func */
#define SORT(x) do{sort(ALL(x));}while(false)
#define RSORT(x) do{sort((x).rbegin(),(x).rend());}while(false)
#define UNIQUE(v) do{v.erase( unique(v.begin(), v.end()), v.end() );}while(false)
#define MAX(x,y) do{x = std::max(x,y);}while(false)
#define MIN(x,y) do{x = std::min(x,y);}while(false)
#define BR do{cout<<"\n";}while(false)

/* type define */
using ll = long long;
using PAIR = std::pair<ll, ll>;
using VS = std::vector<std::string>;
using VL = std::vector<long long>;
using VVL = std::vector<VL>;
using VVVL = std::vector<VVL>;
using VD = std::vector<double>;
template<class T>
using V = std::vector<T>;

/* using std */
using std::cout;
constexpr char endl = '\n';
using std::cin;
using std::sort;
using std::pair;
using std::string;
using std::stack;
using std::queue;
using std::vector;
using std::list;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::set;
using std::unordered_set;
using std::unordered_multiset;
using std::multiset;
using std::bitset;
using std::priority_queue;

/* constant value */
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;

/* Initial processing  */
struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing;

/* Remove the source of the bug */
signed pow(signed, signed) { assert(false); return -1; }

/* define hash */
namespace std { template <>	class hash<std::pair<ll, ll>> { public:	size_t operator()(const std::pair<ll, ll>& x) const { return hash<ll>()(1000000000 * x.first + x.second); } }; }

/* input */
template<class T> std::istream& operator >> (std::istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; }

//=============================================================================================

signed main() {
	ll n, k, q;
	cin >> n >> k >> q;
	VL v(q);
	cin >> v;

	VL hu(n);
	REPC(x, v) {
		++hu[x - 1];
	}

	REPC(x, hu) {
		if (q - x >= k) {
			cout << "No" << endl;
		} else {
			cout << "Yes" << endl;
		}
	}
}

Measured memory_bytes: 2176
N, K = map(int, input().split())
P = list(map(int, input().split()))

E = []
for p in P:
    e = ((p * p + p) / 2) * (1 / p)
    E.append(e)

memo = sum(E[:K])
ans = memo
for i in range(0, N - K):
    memo = memo - E[i] + E[i + K]
    ans = max(ans, memo)

print(ans)


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

using namespace std;

typedef long long ll;

ll f(ll x) {
  ll ans = 0;
  for(ll i = 1; i <= x; ++i) {
    if(x % i == 0) ++ans;
  }
  return ans;
}

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

  ll n;
  cin >> n;
  ll ans = 0;
  /*
  for(int i = 1; i <= n; ++i) {
    ans += i * f(i);
    cout << i << " -> " << ans << endl;
  }
  */
  ll sum = 0;
  for(ll i = 1; i <= n; ++i) {
    sum += ((i) * (n / i) * (1 + n / i)) / 2;
    ans += sum;
    //cout << i << ": " << sum << " " << ans << endl;
  }
  cout << sum << '\n';
  return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
	int n, k;
	cin >> n;
	cin >> k;
	int curr = 1;
 
	for(int i = 0; i < n;i++){
		if(curr < k) curr *= 2;
		else curr += k;
	}
 
	cout << curr << endl;
 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> void Max(T &m, const T q) { if (m < q) m = q; }
template<typename T> void Min(T &m, const T q) { if (m > q) m = q; }
template<typename T1, typename T2> pair<T1, T2> operator+(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

int N;
vector<lint> A;

int main()
{
    cin >> N;
    A.resize(N);
    cin >> A;
    lint ans = 0, tmp = 0;
    for (auto v : A)
    {
        if (v == 0) tmp = 0;
        else
        {
            tmp += v;
            ans += tmp / 2;
            tmp %= 2;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#define MOJI 48
using namespace std;
int multiple(string a,string b);
char c[111111];
int main(){
  int n;
  string a,b;
  while(cin >> n){
    for(int i=0;i<n;i++){
      cin >> a;
      cin >> b;
      int k = multiple( a , b );
      if(k>80){
	cout << "overflow" << endl;
      }else {
	for(int i=k-1;i>=0;i--){
	  printf("%d",c[i]);
	}
	cout << endl;
      }
    }
  }
}
int multiple(string a,string b){
  int a_size,b_size,w=0;
  char k = 0; // 桁上げ
  a_size = a.size();
  b_size = b.size();
  while(a_size>0 || b_size>0 || k == 1){
    if(a_size>0 && b_size>0){
      c[w] = (a[a_size-1] - MOJI + b[b_size-1] - MOJI + k) % 10;
      k = (k + (a[a_size-1]-MOJI) + (b[b_size-1]-MOJI)) / 10;
    }
    else if(a_size>0 && b_size<=0){
      c[w] = ((a[a_size-1]-MOJI) + k) % 10;
      k = (a[a_size-1]-MOJI + k) / 10;
    }
    else if(a_size<=0 && b_size>0){
      c[w] = (b[b_size-1] - MOJI + k) % 10;
      k = (k + b[b_size-1] - MOJI) / 10;
    }else {
      c[w] = k;
      k = 0;
    }
    a_size--;
    b_size--;
    w++;
  }
  return w;
}

Measured memory_bytes: 1236
#include <iostream>

using namespace std;

int main(){
	int N, A, B;
	cin >> N >> A >> B;
	int sum = 0;
	for (int top = 0; top <= 1; ++top){
		for (int i = 0; i <= 9; ++i){
			for (int j = 0; j <= 9; ++j){
				for (int k = 0; k <= 9; ++k){
					for (int l = 0; l <= 9; ++l){
						if ((top * 10000) + (i * 1000) + (j * 100) + (k * 10) + l > N) goto END;
						else if (top + i + j + k + l >= A && top + i + j + k + l <= B) {
							sum += (top * 10000) + (i * 1000) + (j * 100) + (k * 10) + l;
						}
					}
				}
			}
		}
	}
END:
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n");
  const [n, k] = lines.shift().split(' ').map(Number);
  const w = lines.map(Number);

  const canAllStack = (p) => {
    let cnt = 0, sum = 0;
    for (let i = 0; i < k; i++) {
      for (sum = 0; sum + w[cnt] <= p;) {
        sum += w[cnt++];
        if (cnt === n) return n;
      }
    }
    return cnt;
  };

  let mid, left = 0, right = 1e9;
  while (right - left > 1) {
    mid = (right + left) / 2;
    if (canAllStack(mid) >= n) right = mid;
    else left = mid;
  }
  console.log(Math.floor(right));
})();



Measured memory_bytes: 29216
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
p = list(map(lambda x: int(x)-1, input().split()))
c = list(map(int, input().split()))
seen = [None]*n
vs = []
ans = -float("inf")
def sub(v, num):
    if num==0:
        return 0
    v = v+v
    n = len(v)
    val = sum(v[:num])
    ans = val
    for i in range(num,n):
        val = val + v[i] - v[i-num]
        ans = max(ans, val)
    return ans
for i in range(n):
    if seen[i]:
        continue
    v = []
    s = i
    seen[s] = True
    while True:
        s = p[s]
        seen[s] = True
        v.append(c[s])
        if s==i:
            break
    ss =sum(v)
    val1 = -float("inf")
    if ss>=1 and k>=len(v):
        val1 = ss*(k//len(v))
        tmp = max(sub(v,i) for i in range((k%len(v))+1))
        val1 += tmp
        val0 = ss*(k//len(v)-1)
        val0 += max(sub(v,i) for i in range((len(v))+1))
        val1 = max(val0, val1)
    val2 = -float("inf")
    for i in range(1,min(k,len(v))+1):
        val2 = max(val2, sub(v, i))
        
    val = max(val1, val2)
#     print(val1, val2, val, v, i, ss, k, len(v))

    ans = max(ans, val)
print(ans)

Measured memory_bytes: 93176
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F(i,a,b) for(int i = a ; i <=b ; i++)
#define R(i,a,b) for(int i = a ; i >= b ; i--)
#define pb push_back
#define speed ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ub(a,x) upper_bound(a.begin(),a.end(),x)-a.begin()
#define lb(a,x) lower_bound(a.begin(),a.end(),x)-a.begin()
#define ALL(v)   v.begin(),v.end()
bool comp(pair<pair<string,int> , int> a, pair<pair<string,int> , int> b )
{
	if(a.first.first  != b.first.first)
		return a.first.first < b.first.first;
	else
		return a.first.second >  b.first.second;
}
int main()
	{
		int n,m;
		cin >> n >> m;
		vector<int> vec[m], arr(m);
		for(auto &a : vec)
		{
			int i;
			cin >> i;
			for(int x=0;x <i;x++)
			{
				int j;
				cin >> j;
				j--;
				a.pb(j);
			}
		}
		for(auto &a : arr)
		{
			cin >> a;
		}
		int ans = 0;

		for(int x=0; x< pow(2,n);x++)
		{
			vector<int> index(n);
			int x1 = x;
			for(auto &a : index)
			{
				a = x1 % 2;
				x1/=2;
			}
			int g = 0;
			for(int y =0; y <m; y++)
			{
				int g1 =0;
				for(auto t : vec[y])
				{
					if(index[t] == 1)
						g1++;
				}
				if(g1 % 2 != arr[y])
					g=1;
			}
			if(!g)ans++;
		}
		cout << ans;

		
}



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

#define int long long 

using namespace std;


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

    map < int , int > odd, even;
    for(int i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        if(i%2)
        {
            odd[temp]++;
        }
        else
        {
            even[temp]++;
        }
    }
    
    vector < pair < int , int >  > a, b;
    
    for(auto it=odd.begin();it!=odd.end();it++)
    {
        a.push_back({ it->second, it->first});
    }

    for(auto it=even.begin();it!=even.end();it++)
    {
        b.push_back({it->second, it->first});
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    n/=2;
    int n1 = a.size();
    int m1 = b.size();
    if(a[n1-1].second!=b[m1-1].second)
    {
        cout<<n-a[n1-1].first+n-b[m1-1].first<<endl;
        return 0;
    }
    
    int ans = n - max(b[m1-1].first, a[n1-1].first)+ n;
    if(n1 >= 2)
    {
        ans = min(ans, n - a[n1-2].first + n - b[m1-1].first);
    }

    if(m1>=2)
    {
        ans = min(ans, n- a[n1-1].first + n - b[m1-2].first);
    }
    cout<<ans<<endl;
    return 0;
}


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

int main(){
    vector<int> G;
    G = {0,1,3,1,2,1,2,1,1,2,1,2,1};

    //入力
    int x,y;
    cin >> x >> y;
    //出力
    if(G.at(x)==G.at(y)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    
}

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

items = V[:]

items = sorted(items, reverse=True)
sub_items = items[:A]
ave = sum(sub_items)/len(sub_items)
rest_items = items[A:]

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if ave != sub_items[0]:
    # nCr
    r = sub_items.count(sub_items[-1])
    n = rest_items.count(sub_items[-1]) + r
    pattern = combinations_count(n, r)
else:
    n = items.count(ave)
    pattern = 0
    for r in range(A, min(n+1, B+1)):
        pattern += combinations_count(n, r)


print(ave)
print(pattern)



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

int rt(vector<int> &uf,int i)
{
  return uf[i]<0?i:uf[i]=rt(uf,uf[i]);
}

int con(vector<int> &uf,int a,int b)
{
  int ret;
  if(-uf[a]<-uf[b]){
    uf[a]=b;
    ret=b;
  }
  else if(-uf[a]>-uf[b]){
    uf[b]=a;
    ret=a;
  }
  else{
    uf[a]=b;
    uf[b]--;
    ret=b;
  }
 return ret;
}

int main()
{
  int n;
  scanf("%d",&n);
  vector<int> pr(2*n,-1);
  vector<int> uf(n,-1);
  vector<int> X(n);
  for(int i=0;i<n;i++)X[i]=i;
  int N=n;
  vector<long long> S(2*n,0);
  vector<pair<long long,pair<int,int> > > E(n-1);
  for(int i=0;i<n-1;i++){
    int a,b;
    long long c;
    scanf("%d%d%lld",&a,&b,&c);
    a--,b--;
    E[i]=make_pair(c,make_pair(a,b));
  }
  sort(E.begin(),E.end());
  for(int t=n-2;t>=0;t--){
    long long c=E[t].first;
    int a=E[t].second.first,b=E[t].second.second;
    int Ra=rt(uf,a),Rb=rt(uf,b);
    int ra=X[Ra],rb=X[Rb];
    int Rc=con(uf,Ra,Rb);
    //printf("%d %d %d\n",rt(uf,a),rt(uf,b),Rc);
    //printf("%d %d %d %d\n",a+1,b+1,ra,rb);
    X[Rc]=N;
    pr[N]=pr[ra]+pr[rb];
    S[ra]+=-pr[rb]*c;
    S[rb]+=-pr[ra]*c;
    pr[ra]=N;
    pr[rb]=N;
    N++;
  }
  for(int i=N-1;i>=0;i--){
    //printf("%d %d\n",i,pr[i]);
    if(pr[i]>=0){
      S[i]+=S[pr[i]];
    }
  }
  for(int i=0;i<n;i++){
    printf("%lld\n",S[i]);
  }
  return 0;
}


Measured memory_bytes: 6400
a, b, k = map(int, input().split())
ans = []
for i in range(a, min(a+k, b)):
    ans.append(i)
for i in range(max(b-k+1, a), b+1):
    ans.append(i)
ans = sorted(list(set(ans)))
for i in ans:
    print(i)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N=1000005;
#define M 1000000007
#define double long double
#define BINF 10000000000001
#define init(arr,val) memset(arr,val,sizeof(arr))
#define MAXN 15000001
const int LG = 22;


#undef int 
int main() { 
#define int long long int 
 
ios_base::sync_with_stdio(false); 
cin.tie(0); 
cout.tie(0); 


	int n,l;
	cin >> n >> l;
	int a[n + 1] = { 0 };
	int s = 0;
	for(int i = 1; i <= n; i++)
		a[i] = l + i - 1, s += a[i];
	//sort(a,a + n + 1);

	int diff = BINF, ans = 0;
	for(int i = 1; i <= n; i++){
		int lol = s - a[i];
		
		if(abs(lol - s) < diff){
			diff = abs(lol - s);
			ans = lol;
		}
	}

	cout << ans ;



return 0;
}

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

using ll = long long;
using namespace std;
const int INFint = 1e9+1;
const ll INFll = (ll)1e18+1;
ll MOD=1e9+7;


int main(){
  int l,r,d;
  cin>>l>>r>>d;
  int cnt(0);
  for(int i(l);i<=r;i++){
    if(i%d==0) cnt++;
  }
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 3628
import sys
import numpy as np

read = sys.stdin.read

N, *x = map(int, read().split())
mod = 10 ** 9 + 7
'''
x_(i+1)が選ばれる前にx_iが選ばれれば, x_(i+1)-x_iを加算
(N-1)!通りの中でこのような状況はsum (N-i)! i=2toN-1

x_(i+n)が選ばれる前、かつx_(i+1)からx_(i+n-1)が選ばれた後にx_iが選ばれれば, x_(i+n)-x_iを加算

'''
inv = [0] * N
for i in range(1, N):
    inv[i] = pow(i, mod - 2, mod)

for i in range(2, N):
    inv[i] = (inv[i] + inv[i - 1]) % mod

fact = 1
for i in range(1, N):
    fact *= i
    fact %= mod

x = np.array(x, np.int64)
X = x[1:] - x[:-1]
inv = np.array(inv[1:], np.int64)

answer = X * inv % mod * fact % mod
print(answer.sum() % mod)


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

int main()
{
  int H,W,K;
  char A[320][320]={0};
  cin>>H>>W>>K;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++) cin>>A[i][j];
  }
  int B[320][320]={0};
  int memo=0;
  int used=0;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(A[i][j]=='#'){
        B[i][j]=used+1;
        used+=1;
        if(memo==0)memo=used;
      }
      else if(j>=1){
        B[i][j]=B[i][j-1];
      }
    }
    for(int j=0;j<W;j++){
      if(B[i][j]==0)B[i][j]=memo;
    }
    memo=0;
  }
  for(int j=0;j<W;j++){
    memo=B[0][j];
    for(int i=0;i<H;i++){
      if(i>=1&&B[i][j]==0)B[i][j]=B[i-1][j];
      else if(B[i][j]!=0&&memo==0)memo=B[i][j];
    }
    for(int i=0;i<H;i++){
      if(B[i][j]==0)B[i][j]=memo;
    }
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cout<<B[i][j]<<" ";
    }
    cout<<endl;
  }
}

Measured memory_bytes: 1280
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
  lll ii,jj,kk;
  vector<int> ret;

  int n,q,t,x,c,s;

  cin >> n >> q;

  list<int> l[n];  
  list<int>::iterator it;
  for(ii=0;ii<q;ii++){
    cin >> c;

    switch(c){
    case 0:
      cin >> t >> x;
      l[t].push_back(x);
      break;
    case 1:
      cin >> t;
      it = l[t].begin();
      while(it != l[t].end()){
        cout << *it;
        it++;
        if(it != l[t].end()){
          cout << " ";
        }
      }
      cout << endl;
      //list<int>::iterator itt = l[t].begin();
      //for(jj=0;jj<l[t].size();jj++){
      //  if(jj == l[t].size()-1){
      //    cout << l[t][jj] ;
      //  }
      //  else{
      //    cout << l[t][jj] << " ";
      //  }
      //}

      break;
    case 2:
      cin >> s >> t;
      //for(jj=0;jj<l[s].size();jj++){
      //  l[t].push_back(l[s][jj]);
      //}
      //l[t].insert(l[t].end(),l[s].begin(),l[s].end());
      l[t].splice(l[t].end(),move(l[s]));
      l[s].clear();
      break;
    }
  }

  return 0;
}



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

int n, m;
vector<int> edge[100004];
int dp[100004];
bool visited[100004] = {0,};
int dfs(int here){
	visited[here] = true;
	int& ret = dp[here];
	if(ret != -1)	return ret;
	ret = 0;
	for(int there : edge[here]){
		ret = max(ret,dfs(there)+1);
	}
	return ret;
}
int main() {
	cin>>n>>m;
	memset(dp,-1,sizeof(dp));
	int x,y;
	for(int i = 0 ; i<m;i++){
		cin>>x>>y;
		edge[x].push_back(y);
	}
	int ans = 0;
	for(int i = 1;i<=n;i++)
		ans = max(ans,dfs(i));
	cout<<ans;
	return 0;
}

Measured memory_bytes: 7552
n=int(input())

arr = [[0 for i in range(n)] for j in range(n)]
#for i in arr:
    #print(' '.join(map(str, i)))

#print(arr)

for i in range(0,n):
    l=raw_input().split()
    if(int(l[1])>=1):
        x=int(l[0])
        y=int(l[1])
        p=len(l)
        d=0
        while(2+d<p):
            z=int(l[2+d])
            #print(x,y,z)
            arr[x-1][z-1]=1
            #print(arr)
            d=d+1

#print(arr)
for i in arr:
    print(' '.join(map(str, i)))



Measured memory_bytes: 4708
N=int(input())
A=list(map(int,input().split()))
X=[0]*(N + 1)

for i in A:
    X[i] += 1

cnt=0
for i in X:
    cnt += (i * (i - 1)// 2)

for i in A:
    print(cnt - (X[i] - 1))


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

int main(){
    int N;
    cin >> N;
    if(65 <= N && N <= 90)cout << 1 << endl;
    else if(97 <= N && N <= 122)cout << 2 << endl;
    else{
        cout << 0 << endl;
    }
}


Measured memory_bytes: 3076
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

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

int main() {
    int fans = 1012345678;
    vector<int> menus(5);
    vector<int> order = {0, 1, 2, 3, 4};
    rep(i, 5) scanf("%d", &menus[i]);

    while (next_permutation(order.begin(), order.end())) {
        int ans = 0;
        rep(i, menus.size()) {
            while (ans % 10 != 0) ans++;
            ans += menus[order[i]];
        }
        fans = min(fans, ans);
    }

    printf("%d\n", fans);
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF 999999999

int n,W,H;

bool solve(vector<int> vy,vector<int> vx){
    bool a=true,b=true;
    rep(i,H){
        if(vy[i]<=0)a=false;
    }
    rep(i,W){
        if(vx[i]<=0)b=false;
    }
    
    if(!a && !b)return false;
    return true;
}

int main(){
    cin>>n>>W>>H;
    
    
    vector<int> vx(100001,0),vy(100001,0);
    
    rep(i,n){
        int x,y,w;
        cin>>x>>y>>w;
        vx[ max(0,x-w) ]++;
        vx[ min(W,x+w) ]--;

        vy[ max(0,y-w) ]++;
        vy[ min(H,y+w) ]--;
    }
    
    
    rep(i,H)vy[i+1] += vy[i];
    rep(i,W)vx[i+1] += vx[i];

    
    if( solve(vy,vx) )  cout<<"Yes"<<endl;
    else                cout<<"No"<<endl;
}

Measured memory_bytes: 2592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lb;
#define REP(i,j,n) for (int i=j;i<(n);i++)
#define RREP(i,n) for (int i = n; 0<i;i--)
#define print(out) cout<< out  << "\n";
#define mod 1000000007
const int INF = 1e8;
typedef pair<int,int> P;

int main(){
  int N;cin>>N;
  vector<double> v(N,0);
  REP(i,0,N)cin>>v[i];
  REP(i,0,N-1){
    sort(v.begin(),v.end());
    v[0]=(v[0]+v[1])/2;
    v[1]=1001;
  }
  print(setprecision(8)<<v[0])


}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
public static void main(String[]  args){
  Scanner stdIn = new Scanner(System.in);
   int n = stdIn.nextInt();
   int x = stdIn.nextInt();
   int t = stdIn.nextInt();
  
  if(n%x == 0){System.out.println(t*(n/x));}
  else {System.out.println(t*(n/x + 1));}
  
}
}

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll llINF = 1LL << 60;
const int iINF = 1e8;

//---main---------------------------------------------
int main(){
    //main
    int N,K;
    cin >> N >> K;
    vector<int> P(N),C(N);
    rep(i,N) cin >> P[i];
    rep(i,N) cin >> C[i];

    ll ans = - llINF;



    rep(s,N){
        vector<ll> sa(N+4);
        int mas = s+1;
        for(int move=1;move <=N; move++){
            mas = P[mas-1];
            sa[move] = sa[move-1]+ll(C[mas-1]);
            chmax(ans,sa[move]);
            if(move>=K) break;
            if(mas == s+1 && sa[move]>0){
                rep(ss,move+1)
                chmax(ans, sa[ss]+sa[move]*ll(((K-ss)/move)));
                break;
            }
            //cout << s+1 << ":" << move <<"," << sa << endl;
        }
    }
    cout << ans << endl;
    

    return 0;
}

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

int main() {
    string S;
    cin >>S;
  vector<string> divide = {"dream", "dreamer", "erase", "eraser"};
  reverse(S.begin(), S.end());
  for (int i = 0; i < 4; ++i) reverse(divide[i].begin(), divide[i].end());
   
  bool can = true;
   for (int i = 0; i < S.size();) {
     bool can2 = false; // 4 個の文字列たちどれかで divide できるか
     for (int j = 0; j < 4; ++j) {
       string d = divide[j];
       if (S.substr(i, d.size()) == d) { // d で divide できるか
       can2 = true;
       i += d.size(); // divide できたら i を進める
      }
    }
   if(!can2){
     can = false;
     break;
   }
  }
  if(can) cout << "YES" << endl;
  else cout << "NO" << endl;
}

      
  

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int r; cin >> r;
    cout << r * r << endl;

    return 0;
}


Measured memory_bytes: 256