akhauriyash/Code-Regression huggingface dataset:
import Control.Arrow
import Data.List
main = getLine >>= main' . read
    where
        main' n = getLine >>= print . solve n . map (head &&& length) . group . sort . map read . words

solve :: Int -> [(Int, Int)] -> Int
solve n xxs@(x : xs)
    | odd n && fst x == 0 && snd x == 1 && check 2 xs = calc $ (n - 1) `div` 2
    | even n && fst x /= 0 && check 1 xxs = calc $ n `div` 2
    | otherwise = 0
    where
        check p ((y, yl) : ys)
            | p == y && yl == 2 = check (p + 2) ys
            | otherwise = False
        check _ _ = True

        calc 0 = 1
        calc 1 = 2
        calc p
            | odd p = 2 * calc (p - 1) `mod` 1000000007
            | otherwise = prev * prev `mod` 1000000007
            where
                prev = calc $ p `div` 2


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

int main() {
	int N;
	cin >> N;
	vector<pair<pair<string, int>, int>> vec(N);
	for (int i = 0; i < N; i++)
	{
		cin >> vec.at(i).first.first >> vec.at(i).first.second;
		vec.at(i).first.second *= -1;
		vec.at(i).second = i + 1;
	}
	sort(vec.begin(), vec.end());
	for (int i = 0; i < N; i++)
		cout << vec.at(i).second << endl;
}


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

int main()
{
  string s;
  cin >> s;
  sort(s.begin(), s.end());
  
  string t;
  cin >> t;
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  
  if (s < t)
  {
    printf("Yes");
  }
  else
  {
    printf("No");
  }
    
  return 0;
}

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

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

	int n;cin >> n;
	int m;cin >> m;
	ll k;cin >> k;
	vector<ll> a = vector<ll>(n);
	vector<ll> b = vector<ll>(m);
	vector<ll> asum = vector<ll>(n+1);
	vector<ll> bsum = vector<ll>(m+1);
	asum[0] = 0;
	bsum[0] = 0;

	for(int i = 0; i < n; i++){
		cin >> a[i];
		asum[i+1] = asum[i] + a[i];
	}
	for(int i = 0; i < m; i++){
		cin >> b[i];
		bsum[i+1] = bsum[i] + b[i];
	}

	int ans = 0;
	int bestj = m;
	for(int i = 0; i <= n; i++){
		for(int j = bestj; j > -1; j--){
			if(asum[i] + bsum[j] <= k){
				ans = max(ans,i+j);
				bestj = j;
				break;
			}
		}
	}

	cout << ans << endl;

	return 0;
}


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

#define reps(v, f, l) for (int v = (f), v##_ = (l); v < v##_; ++v)
#define rep(v, n) reps(v, 0, n)
#define lep(v, n) reps(v, 1, n + 1)
#define rreps(v, f, l) for (int v = (l), v##_ = (f); v >= v##_; --v)
#define rrep(v, n) rreps(v, 0, n - 1)
#define rlep(v, n) rreps(v, 1, n)
#define show_a(a, size) rep(a##_it, size) std::cout << a[a##_it] << " \n"[a##_it == a##_it_ - 1];
#define show_v(v) show_a(v, v.size())
#define debug(x) std::cerr << #x << " = " << (x) << "\n";

using namespace std;

typedef long long int lint;

static inline int in(){ int x; scanf("%d", &x); return x; }
static inline lint inl(){ lint x; scanf("%lld", &x); return x; }

int main()
{
    bool is_first = true;
    int n;
    while (~scanf("%d", &n)){
        if (is_first) is_first = false;
        else puts("");
        char snum[8];
        sprintf(snum, "%05d", n);
        rep(i, 5) printf("%c", " *"[snum[i] < '5']);
        puts("");
        rep(i, 5) printf("%c", "* "[snum[i] < '5']);
        puts("");
        puts("=====");
        rep(i, 5){
            rep(j, 5){
                printf("%c", " *"[i != (snum[j] - '0') % 5]);
            }
            puts("");
        }
    }
    return (0);
}

Measured memory_bytes: 1212
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <tuple>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include <string.h>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;

int gcd(int a, int b) {
    return b != 0 ? gcd(b, a % b) : a;
}

//逆元を求める関数
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
      fac[i] = fac[i-1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
      finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
//組み合わせ
long long COM (int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

void solve() {
	int n, m;
	cin >> n >> m;
	vector<long long> dp(n + 1);
	vector<int> ok_step(n + 1, true);
	for (int i = 0; i < m; ++i) {
		int a; cin >> a;
		ok_step[a] = false;
	}
	dp[0] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j <= min(n, i + 2); ++j) {
			if (ok_step[j]) {
				dp[j] += dp[i];
				dp[j] = dp[j] % MOD;
			}
		}
	}
	cout << dp[n] << endl;
    return;
}

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



Measured memory_bytes: 1408
// #define _CRT_SECURE_NO_WARNINGS
// #define _USE_MATH_DEFINES	// M_PI=3.1415...
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
#include <iomanip>	// 20桁出力 cout << setprecision(20) << double;
#include <queue>
#include <bitset>	// bitset<8> bs1(131uL); // 10000011 bs1[0]は1 01stringからビット集合生成可
#include <numeric>
#include <random>
#include <climits>  // A/Bを計算するときA==LLONG_MIN && B==-1のみ(1ull<<63)で代用
using namespace std;

typedef long long LL;
typedef pair<LL, LL> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VL;
typedef vector<VL> VVL;				// VVL v(100,VL(100,0));
typedef vector<pair<LL, LL> > VP;
typedef vector<string> VS;
typedef map<int, int> MAPII;
typedef multimap<int, char, greater<int> > MuMAPIC;
typedef multimap<int, string, greater<int> > MuMIS;
typedef pair<LL, pair<P, P> > PP;

#define INF 999999999999999997		// 少し加算したらオーバーフローする
#define MP make_pair
#define FAST_IO  cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORL(i,a,b) for(LL i=(a);i<(b);i++)
#define FOR_REV(i,a,b) for(int i=(a);i>=(b);i--)
#define foreach_it(type,it,c) for(type::iterator it=c.begin(),c_end=c.end();it!=c_end;++it)
#define FOR_ITR(d) for(auto itr=d.begin(),d_end=d.end();itr!=d_end;++itr)	// C++11
#define O(s) cout<<s<<endl;

#define DUMP_VVI(b) if(dbgF){FOR(i,0,b.size()){FOR(j,0,b[i].size())printf("%d ",b[i][j]);puts("");}}
#define D_OUT(str,value) if(dbgF){cout<<str<<" : "<<value<<endl;}

template<class T>T IN() { T d; cin >> d; return d; }

LL gcd(LL a, LL b) { return (b > 0) ? gcd(b, a%b) : a; } // 最大公約数（Greatest Common Divisor）
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; } // 最小公倍数（Least Common Multiple）
bool uruu(LL Y) { return (((Y % 4 == 0 && Y % 100 != 0) || Y % 400 == 0) ? true : false); } // うるう年判定
string Replace(string S, string from, string to) { auto p = S.find(from); while (p != string::npos) { S.replace(p, from.size(), to); p = S.find(from, p + to.size()); }return S; }

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int dxx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dyy[8] = { 1,1,0,-1,-1,-1,0,1 };

// -------------------------------------------------------------------------------

int main() {
	FAST_IO;
	bool dbgF = true; // for D_OUT(str, value)  ... cout<< str <<" : "<< value <<endl;

	LL a, b, x;
	cin >> a >> b >> x;

	string ans = "NO";
	FOR(i, 0, b) {
		if (a + i == x)ans = "YES";
	}
	O(ans);

	return 0;
}

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

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, A[101010];

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d", A + i);

	set<int> dif;
	for (int i = 0; i < N; ++i) {
		int waf = A[i] ^ (A[i] - 1);
		dif.insert(waf);
	}
	int tt = 0;
	for (int i = 0; i < N; ++i) tt ^= A[i];

	vector<int> cand;
	for (auto a : dif) cand.push_back(a);
	reverse(cand.begin(), cand.end());

	int ret = 0;
	for (auto a : cand) {
		if ((tt ^ a) < tt) {
			++ret;
			tt ^= a;
		}
	}
	if (tt) ret = -1;
	printf("%d\n", ret);
	return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
ifstream f("B.in");
typedef long long ll;

int main()
{
    int n,k;
    cin>>n>>k;
    int A[n+1],sum=0;
    for(int i=1;i<=n;i++) cin>>A[i];
    sort(A+1,A+n+1);
    for(int i=1;i<=k;i++) sum+=A[i];
    cout<<sum;

    return 0;
}


Measured memory_bytes: 3600
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

//解説ACをしてみよう
//写経

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

	//純粋な入力を保存しておく配列
	vector<vector<int>> ds(n);
	REP(i, n) {
		int t, d;
		cin >> t >> d;
		--t;
		ds[t].push_back(d);
	}

	//y1は種類aの寿司の中で最大のおいしさの寿司を保存する配列
	//y0はy1を取り除いた寿司の集まり
	vector<int> y0, y1;
	REP(i, n) {

		//種類iの寿司がなければ省く
		if (ds[i].size() == 0) continue;

		//美味しさで昇順ソートして
		sort(ds[i].begin(), ds[i].end());

		//一番後ろの要素(=一番美味しさの大きい要素)をy1にいれて
		y1.push_back(ds[i].back());

		//y1をds[i]から取り除いて
		ds[i].pop_back();

		//y1を取り除いた分を丸々y0に追加する
		y0.insert(y0.end(), ds[i].begin(), ds[i].end());
	}

	//y0,y1を降順ソート
	sort(y0.rbegin(), y0.rend());
	sort(y1.rbegin(), y1.rend());


	long long ans = 0;

	//k個とるときの種類数の最小値Y
	int Y = max(0, k - int(y0.size()));

	long long X = 0;

	//Y種類 y1からとったときの美味しさの基礎点
	//0～Y-1のY個
	REP(i, Y) X += y1[i];

	//上と合わせてk個になるようにy0からとる
	//0～k-Y-1のk-Y個
	REP(i, k - Y) X += y0[i];


	while (1) {
		//現在のX,Yで更新
		ans = max(ans, X + (long long)Y*Y);


		//終了条件
		//もう種類を増やせない
		//k種類に達した
		if (Y >= k || Y >= y1.size()) break;

		//種類を1個増やして
		X += y1[Y];

		//種類を増やさない集合の最小値を取り除く
		X -= y0[k - Y - 1];
		++Y;
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

using ll = long long;

const long long MOD = 1e9 + 7;
const int INF = 1e9 + 7;

ll fact(ll x) {
    if (x == 0) return 1L;
    return (x * fact(x - 1) % MOD) % MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int diff = abs(N - M);
    ll ans = 0;
    if (diff > 1) ans = 0;
    else if (diff == 1) ans = (fact(N) * fact(M)) % MOD;
    else ans = (fact(N) * fact(M) * 2) % MOD;
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define f(i,j,n) for(int i=j;i<=n;i++)
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a,b,c,t=0;
    cin>>a>>b>>c;
    f(i,a,b){
        if(i%c==0)
          t++;
    }
    cout<<t;
}   
  

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
#include <bitset>
#include <cmath>
#include <set>
#include <utility>
#include <sstream>

#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) x.begin(),x.end()
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

int main(){
    string s;
    cin >> s;
    int res = 0,max = 0;

    for(int i = 0;i < 3;i++){
        if(s.at(i) == 'R')
            res++;
        else if(s.at(i) == 'S'){
            if(max < res)
                max = res;
            res = 0;
        }
    }

    if(max < res)
        max = res;

    cout << max << endl;
}

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

#define LL long long

int k;
set<LL> lunlun;

void create(LL, LL, int);

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

	LL tanr=1;
	while(lunlun.size() < k){
		for(int i=1; i<10 && lunlun.size() < k; ++i){
			create(0, tanr, i);
		} tanr*=10;
	}

	set<LL>::iterator it;
	for(it=lunlun.begin(); --k;){
	//	printf("%lld ", *it);
		++it;
	}

	printf("%lld", *it);

	return 0;
}

void create(LL num, LL tanrigi, int inc){
	num+=tanrigi*inc;
	//printf("%lld %lld %d\n", num,tanrigi, inc);
	if(tanrigi!=1){
		if(inc<9)create(num, tanrigi/10, inc+1);
		create(num, tanrigi/10, inc);
		if(inc>0)create(num, tanrigi/10, inc-1);
	} else lunlun.insert(num);
}


Measured memory_bytes: 5504
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int hoge[1010];

int main() {
	int n,m;
	while(n=in(),m=in()){
		memset(hoge,0,sizeof(hoge));
		int potato=1;
		int i;
		for(i=0;i<n;i++){
			int k;
			for(k=0;k<m;){
				if(!hoge[potato]){k++;if(k==m)break;}
				potato++;
				if(potato>n)potato=1;
			}
			//cout<<potato<<endl;
			hoge[potato]=1;
		}
		cout<<potato<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e8
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    ll n, k; cin >> n>> k;
    map<ll, ll> m;
    rep(i,n){
        ll a, b; cin >> a >> b;
        m[a] += b;
    }
    for(auto num : m){
        if(k<=num.second){
            cout << num.first << endl;
            return 0;
        }
        k-=num.second;
    }

    return 0;
}

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

#define _GLIBCXX_DEBUG

//vector<int> A(M), B(M);
//vector<vector<char>> answer(N, vector<char>(N, '-'));

int main() {
  int a, b;
 
  cin >> a >> b;

  cout << a*b << endl;  
}


Measured memory_bytes: 3620
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
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; }
#define int long long

void solve() {
	int n; cin >> n;
    vector<int> d(n);
    multiset<int> se;
    rep(i, n) {
        cin >> d[i];
        se.insert(d[i]);
    }
    int m; cin >> m;
    vector<int> t(m);
    rep(i, m) {
        cin >> t[i];
        auto ite = se.find(t[i]);
        if(ite == se.end()) {
            cout << "NO" << endl;
            return;
        }
        se.erase(ite);
    }
    cout << "YES" << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(a) cout<<#a<<":"<<a<<endl;
const ll INF=0x3f3f3f3f;
const ll N=1e6+7;
const ll mod=1e9+7;
ll maxn,minn;
ll T,n,m,k;

ll f;
struct node{
    ll arr[100][100];
};

node mul(node x,node y){
    node ans;
    memset(ans.arr,0,sizeof(ans.arr));
     for(ll k = 1;k<=n;k++){
        for(ll i = 1;i<=n;i++){
            for(ll j = 1;j<=n;j++){
                ans.arr[i][j] = (ans.arr[i][j]+(x.arr[i][k]*y.arr[k][j])%mod)%mod;
            }
        }
    }
    return ans;
}
node ksm(node a,ll b){
    node ans;
    memset(ans.arr,0,sizeof(ans.arr));
    for(ll i=1;i<=f;i++)
        ans.arr[i][i]=1;
    while(b){
        if(b&1) ans=mul(ans,a);
        a=mul(a,a);	b>>=1;
    }
    return ans;
}


int main(){
	ll ans=0;
	node x,y;
	cin>>n>>k;
	f=n;
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=n;j++){
			scanf("%lld",&x.arr[i][j]);
		}
	}
	y=ksm(x,k);
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=n;j++){
			ans=(ans+y.arr[i][j])%mod;
		}
	}
	cout<<ans<<endl;
	
	
	

	return 0;
}





Measured memory_bytes: 896
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main()
{
    fastio;
    string S;
    cin >> S;
    unordered_set<char> ss(S.begin(), S.end());

    for (char ch = 'a'; ch <= 'z'; ++ch)
    {
        if (ss.find(ch) == ss.end())
        {
            cout << ch << endl;
            break;
        }
        if (ch == 'z')
        {
            cout << "None" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 1360
/*{{{*/
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB emplace_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
map<LL,LL>dp;
LL N,A,B,C,D;
LL f(LL x){
    if(x==1)return D;
    if(dp.count(x))return dp[x];
    LL ret=1e18;
    if(ret/D>=x)ret=x*D;
    ret=min(ret,f(x/2)+A+(x%2)*D);
    if(x&1)ret=min(ret,f(x/2+1)+A+D);
    if(x>=3)ret=min(ret,f(x/3)+B+(x%3)*D);
    if(x%3)ret=min(ret,f(x/3+1)+B+D*(3-x%3));
    if(x>=5)ret=min(ret,f(x/5)+C+(x%5)*D);
    if(x%5)ret=min(ret,f(x/5+1)+C+D*(5-x%5));
    return dp[x]=ret;
}
void solve(){
    R(N,A,B,C,D);
    dp.clear();
    W(f(N));
}
int main(){
    CASET{
        solve();
    }
    return 0;
}


Measured memory_bytes: 4516
#include <iostream>
#include <vector>
#include <string>
#include <cctype>
using namespace std;

int main(){
	string a;
	getline(cin, a);
	for (long i = 0; i < a.size(); i++){
		if (isupper(a[i])) a[i] = tolower(a[i]);
		else if (islower(a[i])) a[i] = toupper(a[i]);
	}
	cout << a << endl;

	return 0;
}

Measured memory_bytes: 1180
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100005],b[100005];
int ans;
int main(void){
	int n,m; cin>>n>>m;
	int l,r;
	for(int i=0;i<m;i++){
		cin>>l>>r;
		a[l]++; a[r+1]--;
	}
	for(int i=0;i<=n;i++){
		b[i+1]=b[i]+a[i+1];
		if(b[i+1]==m){
			ans++;
		}
	}
	cout<<ans<<endl;
	
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
#define out(a) cout<<fixed<<setprecision((a))


int main(){
	
	ll N;
	cin >> N;
	vector<P> BA(N);
	FOR(i,0,N)cin>>BA[i].second>>BA[i].first;
	SORT(BA);
	ll sum = 0;
	FOR(i,0,N)sum+=BA[i].second;

	REV(BA);
	FOR(i,0,N){
		if(sum>BA[i].first){
			cout << "No" << endl;
			return 0;
		}
		sum -= BA[i].second;
	}
	cout << "Yes" << endl;
}



Measured memory_bytes: 3328
#![allow(unused_mut)]
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(unused_imports)]
#![allow(dead_code)]
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    let mut next = || { iter.next().unwrap() };
    input_inner!{next, $($r)*}
  };
  ($($r:tt)*) => {
    let stdin = std::io::stdin();
    let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
    let mut next = move || -> String{
      bytes
        .by_ref()
        .map(|r|r.unwrap() as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect()
    };
    input_inner!{next, $($r)*}
  };
}
macro_rules! input_inner {
  ($next:expr) => {};
  ($next:expr, ) => {};

  ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($next, $t);
    input_inner!{$next $($r)*}
  };
}
macro_rules! read_value {
  ($next:expr, ( $($t:tt),* )) => {
    ( $(read_value!($next, $t)),* )
  };

  ($next:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
  };

  ($next:expr, chars) => {
    read_value!($next, String).chars().collect::<Vec<char>>()
  };

  ($next:expr, usize1) => {
    read_value!($next, usize) - 1
  };

  ($next:expr, $t:ty) => {
    $next().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  input!{
    X: u128,
  }

  let mut ans = 100;
  for i in 0..1000000 {
    ans += ans /100;
    if ans >= X {
      println!("{}", i+1);
      break;
    }
  }

}


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

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

    string s, t; cin >> s >> t;

    ll n = 0;

    //cout << s.size() << "\n";

    for (int i=0; i<s.size(); i++)
    {
        if (s[i] == t[i]) n += 1;
    }

    if (n == s.size()) cout << "Yes" << "\n";
    else cout << "No" << "\n";
    

    return 0;
}

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

#define faster  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define sq(x)   (x)*(x)
#define PI      acos(-1.0)
#define nl      '\n'

typedef long long int ll;
typedef unsigned long long int  llu;

int main()
{
    string t;
    cin>>t;
    if(t[1]=='R')
        cout<<"ABC"<<nl;
       else cout<<"ARC"<<nl;
    return 0;
}


Measured memory_bytes: 3592
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200_000)

def solve(N: int, u: "List[int]", v: "List[int]", w: "List[int]"):
    from collections import namedtuple
    Edge = namedtuple("Edge", "to cost")
    edges = [[] for _ in range(N)]
    for uu, vv, ww in zip(u, v, w):
        edges[uu-1].append(Edge(vv-1, ww))
        edges[vv-1].append(Edge(uu-1, ww))
    colors = [None] * N
    def dfs(n, c):
        if colors[n] is not None:
            return
        colors[n] = c
        for nn, w in edges[n]:
            dfs(nn, (c+w)%2)
    dfs(0, 0)
    return colors


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    w = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
        w[i] = int(next(tokens))
    print(*solve(N, u, v, w), sep="\n")

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


Measured memory_bytes: 105224
#include <stdio.h>
int main (void)
{
   
	int a,b,c;
	
	
	scanf("%d %d %d",&a,&b,&c);

	if(a<b)
	{
		if(b<c)
		{
			printf("%d %d %d\n",a,b,c);
		}
		else
		{
			if(a<c)
			{
				printf("%d %d %d\n",a,c,b);
			}
			else
			{
				printf("%d %d %d\n",c,a,b);
			}
		}

	}
	else
	{
		if(c<b)
		{
			printf("%d %d %d\n",c,b,a);
		}
		else
		{
			if(a<c)
			{
				printf("%d %d %d\n",b,a,c);
			
			}
			else
			{
				printf("%d %d %d\n",b,c,a);
			}
		}
	}
	
	
     
	return 0;
}

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


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

int main()
{
	int i, j, k;

	int n;
	cin >> n;

	string a, b, c;
	cin >> a >> b >> c;
	int result = 0;
	int temp;

	for (i = 0; i < n; i++)
	{
		temp = 0;

		if (a[i] == b[i])
		{
			temp = 1;

			if (a[i] == c[i])
			{
				temp = 2;
			}
		}
		else
		{
			if (a[i] == c[i])
			{
				temp = 1;
			}
			else
			{
				if (b[i] == c[i])
				{
					temp = 1;
				}
			}
		}

		if (temp == 0)
		{
			result += 2;
		}
		else
			if (temp == 1)
			{
				result++;
			}
	}

	printf("%d", result);

	return 0;
}


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

#define FOR(i, m, n) for(int (i) = (m); (i) < (n); (i)++)
#define rep(i, n) FOR(i, 0, n)
#define co(n) cout << (n) << endl
#define cosp(n) cout << (n) << ' '
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
typedef long long ll;
typedef pair<int, int> P;

const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;

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

	ll ans = LINF;
	for(ll i = 1; i*i <= n; i++){
		if(!(n%i)){
			ans = min(ans, i+n/i);
		}
	}

	co(ans-2);

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
	
int main(){
 
  string S;
  cin >> S;
  if(S.at(1)=='S') {
	  if(S.at(0)=='R'||S.at(2)=='R') {
		  cout << '1' << endl;
	  }else {
		  cout << '0' << endl;
	  }
	   
	}else if(S.at(0)=='R'){
	   if(S.at(2)=='R'){
		   cout << '3' << endl;
	   }else cout << '2' << endl;
	}else if(S.at(2)=='R'){
		cout << '2' << endl;
	   }else cout << '1' << endl;
}

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

int main() {
  int m,k;
  cin >> m >> k;
  if (m <= 1) {
    if (m == 0 && k == 0) {
      cout << "0 0" << endl;
    } else if (m == 1 && k == 0) {
      cout << "0 0 1 1" << endl;
    } else {
      cout << "-1" << endl;
    }
  } else {
    if ((1<<m) <= k) cout << -1 << endl;
    else {
      rep(i,0,1<<m) {
        if (i == k) continue;
        cout << i << " ";
      }
      cout << k << " ";
      revrep(i,(1<<m)-1,0) {
        if (i == k) continue;
        cout << i << " ";
      }
      cout << k << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3656
#include<stdio.h>
int main(void)
{
  int a,b,c;
  scanf("%d%d%d", &a, &b, &c);
  if(a == b && a != c && b != c)
    printf("Yes\n");
  else if(a == c && a != b && b != c)
    printf("Yes\n");
  else if(b == c && b != a && c != a)
    printf("Yes\n");
  else
    printf("No\n");
  return 0;
}

Measured memory_bytes: 1660
#include<cstdio>
#include<vector>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main(){
	ll N;
	ll K;
	scanf("%lld %lld", &N, &K);
	ll destination[N];
	for (ll i = 0; i < N; ++i){
		scanf("%lld", destination + i);
		destination[i]--;
	}
	bool has_been_visited[N];
	for (ll i = 0; i < N; ++i){
		has_been_visited[i] = false;
	}
	ll now = 0, moves = 0;
	vector<ll> path;
	ll first_visit[N];
	while(!has_been_visited[now]){
		has_been_visited[now] = true;
		path.push_back(now);
		first_visit[now] = moves;
		moves++;
		now = destination[now];
	}
	ll ans;
	ll beginning_of_loop = first_visit[now];
	if(K < beginning_of_loop) ans = path[K] + 1;
	else ans = path[beginning_of_loop + (K - beginning_of_loop)%(moves - beginning_of_loop)] + 1;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 8164
// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <cstdlib>
#include <vector>
#include <bitset>
using namespace std;
int main()
{
    vector<int> seg  {0b0111111,0b0000110,0b1011011,0b1001111,0b1100110,0b1101101,0b1111101,0b0100111,0b1111111,0b1101111};
      int n;
    while(true){
        cin>>n;
        if(n==-1){
        break;
        }
    vector<int> vec(n);
    for(int i=0;i<n;i++){
    cin>>vec.at(i);
    }
    cout<<bitset<7>(seg.at(vec.at(0)))<<endl;
   for(int i=1;i<n;i++){
       cout<<bitset<7>(seg.at(vec.at(i))^seg.at(vec.at(i-1)))<<endl;
   }
    }
    
}

// GCC reference:
//   https://gcc.gnu.org/

// C++ language references:
//   https://cppreference.com/
//   https://isocpp.org/
//   http://www.open-std.org/jtc1/sc22/wg21/

// Boost libraries references:
//   https://www.boost.org/doc/




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

using namespace std;
using ll = long long;

#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define RS(N) resize(N)
#define CINV(v, N) do {\
	v.RS(N);\
	rep(i, N) cin >> v[i];\
} while (0);
#define RCINV(v, N) do {\
	v.RS(N);\
	rrep(i, N) cin >> v[i];\
} while (0);

#define MOD 1000000007

void init();
void solve();

signed main()
{
	init();
	solve();
}

vector<ll> P, A;
ll N, X;

ll saiki(int lev, ll pos = -1)
{
	ll res;
	if (lev < 0) res = 0;
	else if (pos < 0) {
		res = P[lev];
	}
	else if (lev == 0 && pos == 1) res = 1;
	else if (lev == 0) res = 0;
	else if (pos == 1) res = 0;
	else {
		ll S = A[lev-1] + 2;
		if (pos < S) {
			res = saiki(lev-1, pos-1);
		}
		else if (pos == S) {
			res = saiki(lev-1, pos-2) + 1LL;
		}
		else {
			pos = min(pos, A[lev]-1);
			res = 1LL + saiki(lev-1) + saiki(lev-1, pos - A[lev-1] - 2);
		}
	}
	return res;
}


void init()
{
	cin >> N >> X;
	A.RS(N+1);
	P.RS(N+1);
	A[0] = P[0] = 1;
	rep(i, N) {
		A[i+1] = A[i] * 2 + 3;
		P[i+1] = P[i] * 2 + 1;
	}
}

void solve()
{
	cout << saiki(N, X) << endl;
}


Measured memory_bytes: 256
function Main(input) {
  input = input.split("\n");
  tmp= input[0].split(" ");
  var a = tmp[0];
  var b = tmp[1];
  var s;
  if(a==b){
    s="H";

  console.log('%s', s);
  }else{
    s="D";

  console.log('%s', s);
  }

}
  
// "実行する"ボタンを押した時に実行される関数 (デバッグ用)
function debug(){
  var input = document.getElementById("input").value;
  Main(input);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner s=new Scanner(System.in);
    String a=s.next();
    boolean cintinuity=false;
    for(int i=0;i<a.length()-1;i++)if(a.charAt(i)==a.charAt(i+1))cintinuity=true;
    if(cintinuity)System.out.println("Bad");
    else System.out.println("Good");
  }
}

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

int main()
{
    int a,i,j,f=0;
    scanf("%d",&a);
    for(i=1;i<=9;i++)
        for(j=1;j<=9;j++)
            if(i*j==a)
                f=1;
    if(!f)
        printf("No");
    else
        printf("Yes");
    return 0;
}


Measured memory_bytes: 128
N,W = gets.split.map(&:to_i)
V = N*10**3
dp = [10**12]*(V+1)
dp[0] = 0
N.times do
  w,v = gets.split.map(&:to_i)
  V.downto(v) do |i|
    a,b=dp[i-v]+w,dp[i]
    dp[i] = a if a < b
  end
end
ans = V
#p dp
while dp[ans] > W
  ans-=1
end
p ans

Measured memory_bytes: 2556
//#include"stdc++.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define cases ll t;cin>>t;while(t--)
#define f1(a,n) for(int i=a;i<n;i++)
#define f2(b,n) for(int j=b;j<n;j++)
#define md 1000000007
#define pb push_back
#define MAX 1000000005
int main() {
    fast
    ll n;
    cin>>n;
    ll dp[n+1][3];
    dp[0][0]=0;
    dp[0][1]=0;
    dp[0][2]=0;
    
    f1(1,n+1)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        dp[i][0]=a+max(dp[i-1][1],dp[i-1][2]);
        dp[i][1]=b+max(dp[i-1][2],dp[i-1][0]);
        dp[i][2]=c+max(dp[i-1][0],dp[i-1][1]);
    }
    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]))<<endl;
    return 0;
}


Measured memory_bytes: 2560
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;

struct Node{
	int key;
	Node *right,*left,*parent;
};
Node *root,*NIL;

void insert(int k){
	Node *y=NIL;
	Node *x=root;
	Node *z;
	
	z=(Node *)malloc(sizeof(Node));
	z->key=k;
	z->left=NIL;
	z->right=NIL;
	
	while(x!=NIL){
		y=x;
		if(z->key < x->key){
			x=x->left;
		}
		else{
			x=x->right;
		}
	}
	z->parent=y;
	if(y==NIL){
		root=z;
	}
	else{
		if(z->key<y->key){
			y->left=z;
		}
		else{
			y->right=z;
		}
	}
}
void inorder(Node *u){
	if(u==NIL)return;
	inorder(u->left);
	printf(" %d",u->key);
	inorder(u->right);
}
void preorder(Node *u){
	if(u==NIL)return;
	printf(" %d",u->key);
	preorder(u->left);
	preorder(u->right);
}
int main(){
	int n,i,x;
	string com;
	scanf("%d",&n);
	
	for(i=0;i<n;i++){
		cin>>com;
		if(com=="insert"){
			scanf("%d",&x);
			insert(x);
		}
		else if(com=="print"){
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}
	}
	return 0;
}


Measured memory_bytes: 26728
def main():
    from operator import itemgetter

    N = int(input())
    a = map(int, input().split())

    *ea, = enumerate(a, 1)

    ea.sort(key=itemgetter(1), reverse=True)

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    # dp[left][right]:=活発な幼児から順に左端からleft,右端からright並べた際の最大うれしさ

    for i, (p, x) in enumerate(ea, 1):
        for left in range(i + 1):
            right = i - left
            if left > 0:
                dp[left][right] = max(
                    dp[left][right],
                    dp[left - 1][right] + x * (p - left)
                )
            if right > 0:
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][right - 1] + x * (N - right + 1 - p)
                )

    ans = max(dp[i][N - i] for i in range(N + 1))
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 97496
class Mint:
    MOD = 1000000007  # Must be a prime
    CACHE_FACTORIALS = [1, 1]

    def __init__(self, v):
        if self.__isally(v):
            self.v = v.v % self.MOD
        else:
            self.v = v % self.MOD

    @property
    def inv(self):
        return Mint(self.__minv(self.v))

    @classmethod
    def factorial(cls, v):
        for i in range(len(cls.CACHE_FACTORIALS), int(v) + 1):
            cls.CACHE_FACTORIALS.append(cls.CACHE_FACTORIALS[-1] * i % cls.MOD)
        return Mint(cls.CACHE_FACTORIALS[int(v)])

    @classmethod
    def perm(cls, n, r):
        if n < r or r < 0:
            return 0
        return cls.factorial(n) // cls.factorial(n - r)

    @classmethod
    def comb(cls, n, r):
        if n < r or r < 0:
            return 0
        return cls.perm(n, r) // cls.factorial(r)

    @classmethod
    def __isally(cls, v) -> bool:
        return isinstance(v, cls)

    @classmethod
    def __minv(cls, v) -> int:
        return pow(v, cls.MOD - 2, cls.MOD)

    @classmethod
    def __mpow(cls, v, w) -> int:
        return pow(v, w, cls.MOD)

    def __str__(self):
        return str(self.v)
    __repr__ = __str__

    def __int__(self):
        return self.v

    def __eq__(self, w):
        return self.v == w.v if self.__isally(w) else self.v == w

    def __add__(self, w):
        return Mint(self.v + w.v) if self.__isally(w) else Mint(self.v + w)
    __radd__ = __add__

    def __sub__(self, w):
        return Mint(self.v - w.v) if self.__isally(w) else Mint(self.v - w)

    def __rsub__(self, u):
        return Mint(u.v - self.v) if self.__isally(u) else Mint(u - self.v)

    def __mul__(self, w):
        return Mint(self.v * w.v) if self.__isally(w) else Mint(self.v * w)
    __rmul__ = __mul__

    def __floordiv__(self, w):
        return Mint(self.v * self.__minv(w.v)) if self.__isally(w) else \
            Mint(self.v * self.__minv(w))

    def __rfloordiv__(self, u):
        return Mint(u.v * self.__minv(self.v)) if self.__isally(u) else \
            Mint(u * self.__minv(self.v))

    def __pow__(self, w):
        return Mint(self.__mpow(self.v, w.v)) if self.__isally(w) else \
            Mint(self.__mpow(self.v, w))

    def __rpow__(self, u):
        return Mint(self.__mpow(u.v, self.v)) if self.__isally(u) else \
            Mint(self.__mpow(u, self.v))


n, m = map(int, input().split())
x = [int(s) for s in input().split()]
y = [int(s) for s in input().split()]
dx = [x[i+1] - x[i] for i in range(n-1)]
dy = [y[i+1] - y[i] for i in range(m-1)]
dp = [Mint(0)] * n
for i, d in enumerate(dx):
    dp[i + 1] = dp[i] + (i + 1) * d
sx = sum(dp)
dp = [Mint(0)] * m
for i, d in enumerate(dy):
    dp[i + 1] = dp[i] + (i + 1) * d
sy = sum(dp)
print(sx * sy)


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

using namespace std;

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

using int64 = long long;
const int64 INF = 1LL << 60;

int main()
{
  string s;
  cin >> s;
  for(int i = 0; i < s.size(); i += 2) {
    cout << s[i];
  }
  cout << endl;

}


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

using namespace std;

int n, a, x;
long long f[maxn][maxn][maxn * maxn], ans;

int main(){
	scanf("%d%d", &n, &a);
	f[0][0][0] = 1;
	for(int i = 1;i <= n;i++){
		scanf("%d", &x);
		for(int j = 0;j <= i;j++){
			for(int k = 0;k < maxn * maxn;k++){
				f[i][j][k] = f[i - 1][j][k];
				if(j && k - x >= 0) f[i][j][k] += f[i - 1][j - 1][k - x];
			}
		}
	} 
	for(int i = 1;i <= n;i++) ans += f[n][i][i * a];
	printf("%lld", ans);
}

Measured memory_bytes: 35324
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;



int main() {
	int h, w;
	cin >> h >> w;
	int h1, w1;
	cin >> h1 >> w1;

	cout << (h - h1) * (w - w1) << endl;
}


Measured memory_bytes: 3524
using static System.Math;
using static System.Console;
using System.Collections.Generic;
using System.Linq;
using System;
using System.Collections;

class Program
{
    #region Reader
    static string ReadStr => Console.ReadLine();
    static string[] ReadStrs => Console.ReadLine().Split(' ');
    static int ReadInt => Convert.ToInt32(Console.ReadLine().Trim());
    static int[] ReadInts => Console.ReadLine().Trim().Split(' ').Select(s => Convert.ToInt32(s)).ToArray();
    static long ReadLong => Convert.ToInt64(Console.ReadLine().Trim());
    static long[] ReadLongs => Console.ReadLine().Trim().Split(' ').Select(s => Convert.ToInt64(s)).ToArray();
    #endregion
    #region Method
    const int mod = 1000000007;
    public static int Mod(int a, int mod) { return a % mod >= 0 ? a % mod : a % mod + mod; }
    public static long Mod(long a, long mod = mod) { return a % mod >= 0 ? a % mod : a % mod + mod; }
    #endregion

    static void Main()
    {

        long[] AS = ReadLongs;

        long X = Abs(AS[0]);
        long K = AS[1];
        long D = AS[2];

        if (X/D >K) WriteLine(X - K * D);
        else
        {
            K -= X / D;

            X -= (X / D)*D;


            WriteLine(K%2==0 ? Abs(X) : Abs(X-D));

        }

    }
}


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

#define ll long long
#define ARR_SIZE 510000
#define MOD ((ll)1e9 + 7)

ll modpow(ll n, ll r){
    ll res = 1;
    while(r>0){
        if(r%2==1) res = res*n%MOD;
        n = n*n%MOD;
        r /= 2;
    }
    return res;
}

ll modinv(ll n){
    return modpow(n, MOD-2);
}

ll fact[ARR_SIZE] = {1, 1};
ll factinv[ARR_SIZE] = {1, 1};

ll comb(ll n, ll r){
    return (fact[n] * factinv[r] %MOD) * factinv[n-r] %MOD;
}

ll perm(ll n, ll r){
    return fact[n] * factinv[n-r] %MOD;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    // end input

    for(int i=2;i<ARR_SIZE;i++){
        fact[i] = fact[i-1]*i%MOD;
    }
    for(int i=0;i<ARR_SIZE;i++){
        factinv[i] = modinv(fact[i]);
    }

    ll ans = 0;
    for(int i=0;i<=n;i++){
        ll t1 = comb(n,i)*perm(m,i)%MOD;
        ll t2 = modpow(perm(m-i, n-i), 2);
        ans += t1*t2%MOD * modpow(-1, i);

        ans = (ans%MOD + MOD)%MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 9680
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> mypair;
#define eps 1e-6
#define equals(a,b) (fabs( (a) - (b) )< EPS )
#define EPS eps
typedef struct point{
	double x,y;
	point(){};
	point(double x ,double y):x(x),y(y){};
	point operator + (point &p){ return point(x+p.x,y+p.y);	}
	point operator - (point &p){ return point(x-p.x,y-p.y);	}
	point operator * (point &p){ return point(x*p.x-y*p.y,x*p.y+y*p.x) ;}
	point operator * (double a){ return point(x*a,y*a);	}
	point operator / (double a){ return point(x/a,y/a);	}
	
	double abs() { return sqrt(norm()); }
	double norm() { return x*x+y*y; }
	
	bool operator < (const point &p) const { return x!=p.x ? x<p.x : y<p.y; }
	bool operator == (const point &p) const { return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS; }
}point;

double cross(point a,point b){ return a.x*b.y - a.y*b.x ; }//ﾂ外ﾂ静・zﾂ青ｬﾂ閉ｪ)ﾂ　aﾂ×b
bool isparallel(point a,point b){ return equals(cross(a,b),0.0); }
double dot(point a,point b){ return a.x*b.x+a.y*b.y ; } //ﾂ禿ﾂ静渉　aﾂ・b
point make(){ 
	double x,y; cin>>x>>y;
       	return point(x,y);
}
int dfs(int now,int m,int ans,vector<vector<point > > &ang,vector<bool>&used){
	if(now == m-1)return ans;
	if(!used[now]) return dfs(now+1,m,ans,ang,used);
	used[now] = false;
	int tmp = ans;
       for(int i = 0;i< m;i++) if(used[i]){
	used[i] = false;
	int count = 1;
	vector<int> convert;
	convert.push_back(i);
	point tmpang = ang[now][i] ;
		for(int j = 0;j<m;j++){
			if(used[j] )for(int k = j+1;k<m;k++){
				if(used[k]){
					if(isparallel(tmpang,ang[j][k])){
					used[j] =false;
					used[k] = false;
					convert.push_back(j);
					convert.push_back(k);
					count++;
					break;	
					}		
				}	
			}
		}
		
		//	cout<<endl<<"debug"<<now<<' '<<i<<' '<<count<<' '<<count*(count-1)/2<<endl;
		tmp = max(tmp,dfs(now+1,m,ans+(count*(count-1))/2,ang,used));
		for(int j=0;j<convert.size();j++){
			used[convert[j]]  = true;
		//	cout<<convert[j]<<' ';
       		}
	}
	used[now] = true;
	return tmp;	
}

int main(){
	int m;
	cin>>m;
	vector<point> p(m);
	for(int i=0;i<m;i++){
	p[i] = make();
	}
	vector<vector<point> > ang(m,vector<point> (m) );
	for(int i=0;i<m;i++){

		for(int j=0;j<m;j++){
			ang[i][j] = p[i]-p[j];
		}
	}
	vector<bool> used(m,true);
	cout<<dfs(0,m,0,ang,used)<<endl;

	return 0;
}



Measured memory_bytes: 3276