akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main()
{
    int n;
    cin >> n;
    vector<int> v(n+1), h(n+1, 0);
    for(int i=0; i<n; i++)
    {
        cin >> v[i];
        h[v[i]]++;
    }

    int totalCounts = 0;
    for(int i=1; i<=n; i++)
    {
        if(h[i] != 0)
            totalCounts += (h[i] * (h[i] - 1)) / 2;
    }

    for(int i=0; i<n; i++)
    {
        int cur = h[v[i]];
        int curSum = (cur * (cur - 1))/2;

        int cur2 = cur - 1;
        if(curSum != 0)
        {
            cout << totalCounts + ((cur2 * (cur2 - 1)) / 2) - (curSum) << endl;
        }
        else
        {
            cout << totalCounts << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 5760
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
using namespace std;

int main(){
	int N, K;
	string S;
	cin >> N >> S >> K;
	for(int i=0;i<N;i++){
		if(S[K-1] != S[i])S[i] = '*';
	}
	cout << S << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MN 300000
#define mod 1000000007
char s[MN+5];
int p[MN+5],f[MN+5][3][3];
inline void rw(int&a,int b){if((a+=b)>=mod)a-=mod;}
int main(){
	int n,i,j,k,ans=0;
	scanf("%s",s+1);n=strlen(s+1);
	for(p[n+1]=1,i=n;i;--i)p[i]=(p[i+1]<<(s[i]=='?'))%mod;
	for(f[0][0][0]=i=1;i<=n;++i)for(j=0;j<3;++j)for(k=0;k<3;++k){
		if(s[i]!='0')
			if(k)rw(f[i][j][k-1],f[i-1][j][k]);
			else if(j<2)rw(f[i][j+1][k],f[i-1][j][k]);
			else rw(ans,1LL*f[i-1][j][k]*p[i+1]%mod);
		if(s[i]!='1')rw(f[i][j][k<2?k+1:1],f[i-1][j][k]);
	}
	rw(ans,f[n][1][0]);
	rw(ans,f[n][2][1]);
	printf("%d",ans);
}

Measured memory_bytes: 12288
# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

N = int(input())
S = input()
#
# ans = 0
# pattern = []
# for x in range(N):
#     for y in range(x + 1, N):
#         if (S[x] + S[y]) not in pattern:
#             ans += len(set(S[y + 1:]))
#             pattern.append(S[x] + S[y])
#
# print(ans)
ans = 0
for i in range(1000):
    key = str(i).zfill(3)
    first = S.find(key[0])
    if first == -1 or first == N:
        continue
    second = S[first + 1:].find(key[1])
    if second == -1 or (first + second + 2) == N:
        continue
    third = S[first + second + 2:].find(key[2])
    if not third == -1:
        # print(first, first + second + 1, first + second + third + 2, key)
        ans += 1
print(ans)


Measured memory_bytes: 38512
//
//  main.cpp
//  C - Scc Puzzle
//
//  Created by teddywang on 2017/2/18.
//  Copyright © 2017年 teddywang. All rights reserved.
//

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long int n,m;
int main()
{
    while(cin>>n>>m)
    {
        long long int sum=0,t;
        t=n*2;
        if(m>=t)
        {
            sum+=n;
            m-=t;
            sum+=m/4;
        }
        else
        {
            sum+=m/2;
        }
        cout<<sum<<endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){

int a,b,c,B,C;

scanf("%d %d %d",&a,&b,&c);

if(a>b){  

B=b;  

b=a;  

a=B;

}  

if(a>c){  

C=c;  

c=a;  

a=C;  

}    

if(b>c){

C=c;    

c=b;    

b=C;    

}  

printf("%d %d %d\n",a,b,c);

return 0;

}
 

Measured memory_bytes: 596
# Problem B - Magic 2

# input
A, B, C = map(int, input().split())
K = int(input())

# B check
while B<=A:
    B = B * 2
    K -= 1

# C check
while C<=B:
    C = C * 2
    K -= 1

# output
if K>=0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9060
s=input()
num=len(s)-1
if num==0:
  print(int(s))
else:
  bit=2**num
  bitlist=[]
  sum=0
  for i in range(bit):
    num1=i
    bitsub=[]
    while num1!=0:
      bitsub.append(num1%2)
      num1//=2
    while len(bitsub)!=num:
      bitsub.append(0)
    bitlist.append(bitsub)
  for i in range(bit):
    sum1=0
    num2=s[0]
    for j in range(num):
      if bitlist[i][j]==0:
        num2+=s[j+1]
      else:
        sum1+=int(num2)
        num2=""
        num2+=s[j+1]
    sum1+=int(num2)
    sum+=sum1
  print(sum)

Measured memory_bytes: 3064
#ABC122-D We Like AGC
"""
条件を満たす文字列は、
xをACGTのいずれかとして
AGC
GAC
ACG
AxGC
AGxC
のいずれも文字列内に無い状態のことを言う。
上の条件から、末尾に文字を付け足そうとした時に、それに関与する文字列は
末尾3文字のみであり、それより前の状態は関係ない。
つまり、前3文字の結果を保存し続ければ3**4のdpテーブルを用いて求めることができる。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7

n = int(readline())

dic1 = {"A":0,"G":1,"C":2,"T":3}

#dp[i][j][k][l]:i文字目に3文字前がjで2文字前がkで1文字前がlである時のそこまでにあり得る通り数
#j,k,lにおいて、A,G,C,T=0,1,2,3と対応させる
dp = [[[[0]*4 for b in range(4)] for a in range(4)]for _ in range(n+1)]
dp[0][3][3][3] = 1

for i in range(n):
    for j in range(4):
        for k in range(4):
            for l in range(4):
                if dp[i][j][k][l] == 0:
                    continue
                for m in range(4):
                    if k == dic1["A"] and l == dic1["G"] and m == dic1["C"]: #AGC
                        continue
                    if k == dic1["G"] and l == dic1["A"] and m == dic1["C"]: #GAC
                        continue
                    if k == dic1["A"] and l == dic1["C"] and m == dic1["G"]: #ACG
                        continue
                    if j == dic1["A"] and l == dic1["G"] and m == dic1["C"]: #AxGC
                        continue
                    if j == dic1["A"] and k == dic1["G"] and m == dic1["C"]: #AGxC
                        continue
                    
                    dp[i+1][k][l][m] += dp[i][j][k][l] #次の状態に今を足す
                    dp[i+1][k][l][m] %= mod
                    


ans = 0
i = n
for j in range(4):
    for k in range(4):
        for l in range(4):
            ans += dp[i][j][k][l]

print(ans%mod)


Measured memory_bytes: 49648
import math
import bisect
 
n,d,a = map(int,input().split())
x = [0]*n
h = [0]*n
for i in range(n):
    x[i] , h[i] = map(int, input().split())
    
itv = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
    itv[i][0] = x[i]
    itv[i][1] = h[i]
itv.sort()
ans = 0

x.sort()
x.append(1145141919810)
h.append(0)

imos = [0]*(n+1)

atk = math.ceil(itv[0][1]/a)
imos[0] += atk * a
b = bisect.bisect(x,itv[0][0] + (2*d))
imos[b] -= atk * a
ans += atk
    
for i in range(1,n):
    atk = 0
    imos[i] += imos[i-1]
    if itv[i][1] > imos[i]:
        atk = math.ceil((itv[i][1]-imos[i])/a)
        imos[i] += atk * a
        b = bisect.bisect(x,itv[i][0] + (2*d))
        imos[b] -= atk * a
    ans += atk

print(ans)

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

using namespace std;

int A[10000];

int min(int n)
{
    if(n == 1)
        return A[0];
    int r = min(n-1);
    return A[n-1] > r ? r : A[n-1];
}
int max(int n)
{
    if(n==1)
        return A[0];
    int r = max(n-1);
    return  A[n-1] > r ? A[n-1] : r;
}
long long sum(int n)
{
    if(n==1)
        return A[0];
    return  A[n-1] + sum(n-1);
}

int main() {
    int n;
    cin >> n;
    for(int i = 0;i<n;i++)
        cin >> A[i];
    cout << min(n) << " " << max(n) << " " << sum(n) << endl;
    
    return 0;
}

Measured memory_bytes: 3284
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

ll N;
ll a[3001];
ll dp[3001][3001];


int main(){
    cin >> N;
    rep(i,N) cin >> a[i];


    // dp[i][j] := a[i],...,a[j]の範囲でゲームをしたときに先手X,後手YとしたときのX-Yの最大値
    for(int len=1;len<=N;len++){
        for(int i=0;i<N;i++){
            const int j = i + len - 1;
            if(j>=N) break;

            dp[i][j] = max(-dp[i+1][j]+a[i],-dp[i][j-1]+a[j]);
        }
    }

    cout << dp[0][N-1] << endl;
}


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

long long xorsum(long long x){//0からｘまでの排他的論理和を求める関数
    if(x%4 == 3){return 0;}//０になる
    if(x%4 == 1){return 1;}//１になる
    if(x%4 == 2){return (x^1);}//x^1はダメ,x+1==x^1は正しい
    if(x%4 == 0){return x;}//０とｘの排他的論理和になる
}
//A==0のときA-1==-1よりxorsumは何も返さない（０を返す）
//よって0^xorsum(B)を出力するのでＯＫ

int main (){
    long long A,B;
    cin >> A >> B;
    if(A == 0){
        cout << xorsum(B) << endl;
    }
    else{
    cout << (xorsum(A-1) ^ xorsum(B)) << endl;
    }
    //x^yは（）で囲うこと
    //A-1とBの排他的論理和
    //A==0の場合分け？
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j;bool b[52][52];char c;
int main(){
	cin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
			cin>>c;
			if(c=='#')
				b[i][j]=1;
		}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++)
			b[i][j]==1?printf("#"):printf("%d",b[i-1][j-1]+b[i-1][j]+b[i-1][j+1]+b[i][j-1]+b[i][j+1]+b[i+1][j-1]+b[i+1][j]+b[i+1][j+1]);
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
constexpr int INF = 0x3f3f3f3f; constexpr ll LLINF = 0x3f3f3f3f3f3f3f3f;
#define db(x) { cerr << #x << " = " << x << endl; }
template <typename T> void _dbarr(T* a, size_t sz){ for(int i = 0; i < sz; i++) cerr << a[i] << " \n"[i == sz-1]; }
template <typename T> void _dbarr(vector<T> a, size_t sz){ for(int i = 0; i < sz; i++) cerr << a[i] << " \n"[i == sz-1]; }
#define dbarr(x, n) {cerr << #x << ": "; _dbarr((x),(n));}
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define mpr make_pair
#define fs first
#define sn second

int main()
{
	cin.tie(0)->sync_with_stdio(0);
    string s;
    cin >> s;
    ll sum = 0;
    for(int i = 0 ;i < s.size(); i++)
    {
        sum += (s[i]-'0');
    }
    cout << (sum%9 == 0 ? "Yes\n" : "No\n");
}


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

int main () {
  string a, b;
  cin >> a >> b;
  
  int count = 0;
  for (int i = 0; i < 3; i++) {
    if (a.at(i) == b.at(i)) {
      count ++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
	int d, g;
	cin >> d >> g;
	pair<int, int> pa[11];
	for (int i = 0; i < d; i++) {
		cin >> pa[i].first >> pa[i].second;
	}
	bool ho[11];
	int ans = 1000000007;
	for (int bit = 0; bit < (1 << d); bit++) {
		for (int i = 0; i < d; i++) {
			if (bit & (1 << i)) {
				ho[i] = 1;
			}
			else {
				ho[i] = 0;
			}
		}
		int co = 0, co1 = 0;
		for (int i = 0; i < d; i++) {
			if (ho[i]) {
				co += ((i + 1) * 100) * pa[i].first + pa[i].second;
				co1 += pa[i].first;
			}
		}
		bool bo = true;
		for (int i = d - 1; i >= 0; i--) {
			if (co >= g && bo) {
				if (co1 < ans) {
					ans = co1;
					bo = false;
					break;
				}
			}
			if (ho[i] == false) {
				co1 += min(max(0,(g - co + ((i + 1) * 100) - 1) / ((i + 1) * 100)) , pa[i].first - 1);
				co += min(max(0, (g - co + ((i + 1) * 100) - 1) / ((i + 1) * 100)), pa[i].first - 1) * ((i + 1) * 100);
			}
		}
		if (co >= g && bo) {
			if (co1 < ans) {
				ans = co1;
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3548
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
            	
      	String kari = sc.next();
      	int num[] = new int[kari.length()];
      	int rt = 0;
      
      	for(int i = 0; i < kari.length(); i++) {
          num[i] = Integer.parseInt(kari.substring(i, i + 1));			
        }
            
      	for(int number : num) {
        	rt += number;
        }
      
      	if(rt % 9 == 0) {
      		System.out.println("Yes");
        } else {
      		System.out.println("No");
        }
    }
}

Measured memory_bytes: 50496
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
typedef long long lint;
#define rep(i, n) for (lint i = 0; i < (n); ++i)
#define repi(i, k, n) for (lint i = (k); i < (lint)(n); ++i)
typedef pair<lint, lint> P;
typedef vector<lint> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define V 100005
struct edge
{
    lint to;
    lint cost;
};
vector<vector<edge>> G;
vi d(V, LLONG_MAX);
void dijstra(lint s)
{
    priority_queue<P, vector<P>, greater<P>> que;
    d[s] = 0;
    que.push(P(d[s], s));
    while (!que.empty())
    {
        P q = que.top();
        que.pop();
        lint v = q.second;
        if (q.first > d[v])
        {
            continue;
        }
        rep(i, G[v].size())
        {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost)
            {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}
int main()
{
    lint n;
    cin >> n;
    G.resize(n);
    rep(i, n - 1)
    {
        lint a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    lint q, k;
    cin >> q >> k;
    k--;
    dijstra(k);
    rep(i, q)
    {
        lint x, y;
        cin >> x >> y;
        x--;
        y--;
        cout << d[x] + d[y] << endl;
    }
    return 0;
}

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

using namespace std;

int main() {
    ios_base::sync_with_stdio( 0 );
    cin.tie( NULL );
    int n;
    string a;
    cin >> a >> n;
    int i=0;
    while( n && i<a.size() ) {
        if( a[i] != 'a' && 'z'-a[i]+1 <= n ) {
            n-='z'-a[i]+1;
            a[i]='a';
        }
        i++;
    }
    n = n%26;
    for( int x=0; x<n; x++ ) {
        if( a[a.size()-1] == 'z' ) {
            a[a.size()-1] = 'a';
        } else
            a[a.size()-1]++;
    }
    cout << a;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#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() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
vector<P>list(n);
rep(i,n)
{int x,l;
cin >> x >>l;
P p;
  //firstに、アームを一番右側に伸ばしたときの数字
  p.first=x+l;
  //secondに、アームを一番左側に伸ばした時の数字(かぶってはいけないので)
  p.second=x-l;
  list.at(i)=p;
}
sort(list.begin(),list.end());

int nowx=-1e9;
int ans=0;
rep(i,n)
{P p=list.at(i);
  if(nowx<=p.second)
  {ans++; nowx=p.first;}
}

cout << ans << endl;



}
/*vector <int> a(3);
for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }*/

Measured memory_bytes: 1024
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main(void) {
	// your code goes here
	int n,a[100],i,j,max=0;
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d",&a[i]);
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			if(max<abs(a[i]-a[j])) max=abs(a[i]-a[j]);
		}
	}
	printf("%d\n",max);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
    int n,k;
    cin >> n >> k;
    if(n >= 10)cout << k;
    else 
    {
        cout << k + 100 * (10 - n);
    }

    return 0;
}

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


h,w,m = list(map(int, input().split()))
hw = []
hs = [0]*h
ws = [0]*w
for i in range(m):
    hh,ww = map(int, input().split())
    hh -= 1
    ww -= 1
    hw.append((hh,ww))
    hs[hh] += 1
    ws[ww] += 1
# from heapq import heappop as hpp, heappush as hp
hs = [(v,i) for i,v in enumerate(hs)]
ws = [(v,i) for i,v in enumerate(ws)]
hs.sort(reverse=True)
ws.sort(reverse=True)
lh = set()
lw = set()
vh = hs[0][0]
vw = ws[0][0]
for i in range(h):
    if hs[i][0]!=vh:
        break
    else:
        lh.add(hs[i][1])
for i in range(w):
    if ws[i][0]!=vw:
        break
    else:
        lw.add(ws[i][1])
ans = vh + vw
val = len(lh)*len(lw)
for ih, iw in hw:
    if ih in lh and iw in lw:
        val -= 1
if val==0:
    ans -= 1
print(ans)

Measured memory_bytes: 167032
import kotlin.comparisons.compareBy

fun main(args: Array<String>) {
    val lines: MutableList<List<Int>> = mutableListOf()
    while (true) {
        val str = readLine()
        if (str != null) {
            lines.add(str.split(" ").map { Integer.parseInt(it) })
        } else {
            break
        }
    }
    val n = lines[0][0]
    val m = lines[0][1]

    var switchList = (1..n).map { Switch() }
    val pp = lines.last()

    val lightList: MutableList<Light> = mutableListOf()
    (1..m).map {
        val light = Light(oe = pp[it-1])
        val line = lines[it]
        val k = line[0]
        (1..k).map { switchList[line[it]-1] }
                .forEach { it.connected.add(light) }
        lightList.add(light)
    }

    switchList = switchList.sortedWith(compareBy { it.connected.size })

    val case = 2 shl (n - 1)

    var count = 0
    (0 until case).forEach { cn ->
//        println("case: " + cn)
        (0 until n).forEach {
            switchList[it].switchTo((cn shr it) and 1)
        }
        if (lightList.all { it.on() }) count++
    }
    print(count)
}

data class Light(val oe: Int, var count: Int = 0) {
    fun on(): Boolean {
//        println(this)
        return count % 2 == oe
    }
}
data class Switch(val connected: MutableList<Light> = emptyList<Light>().toMutableList(), var state: Int = 0) {
    fun switchTo(state: Int) {
        if (state != this.state) {
            this.state = state
            this.connected.forEach {
                if (state == 0) {
                    it.count--
                } else {
                    it.count++
                }
            }
        }
    }
}


Measured memory_bytes: 38116
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)



int main(){
	long long n, ans=1;
	cin >> n;
	vector<long long> in(n);
	REP(i,n) cin >> in[i];
	REP(i,n){
		if(in[i] == (long long)0){
			cout << "0\n" ;
			return 0;
		}
	}
	REP(i,n){
		//long long tmp = in[i] * ans;
		
		if(ans >= LLONG_MAX/in[i]){
			cout <<"-1\n";
			return 0;
		}
		ans *= in[i];
		
		
		
	}
	
	if(ans > (long long)1e18 ){
		cout << "-1\n";
	}else{
		cout << ans << endl;
	}
		
	
	return 0;
}


Measured memory_bytes: 4048
import sys

M = 10 ** 9 + 7
N, K = map(int, input().split())

p_list = []
n_list = []
z_count = 0

for A in map(int, input().split()):
	if A < 0:
		n_list.append(A)
	elif A > 0:
		p_list.append(A)
	else:
		z_count += 1

p_list.sort()
n_list.sort()

#print(p_list)
#print(n_list)

if len(p_list) + len(n_list) < K:
	print(0)
else:
	values = []
	
	if len(p_list) + len(n_list) == K:
		values = p_list + n_list
		n_count = 0
		for v in values:
			if v < 0:
				n_count += 1
		if n_count % 2 == 1 and z_count > 0:
			values = [0]
	elif len(p_list) == 0 and K % 2 == 1:
		if z_count > 0:
			values = [0]
		else:
			for i in range(min(len(n_list), K)):
				values.append(n_list.pop())
	else:
		n_list.reverse()
		values_pair = []
		values_left = None
		values_left_count = 0
		if len(p_list) >= K:
			if K % 2 == 1:
				values_left = p_list.pop()
				values_left_count = 1
				p_count = K - 1
			else:
				p_count = K
			
			while len(values_pair) * 2 + values_left_count < K:
				v1 = p_list.pop()
				v2 = p_list.pop()
				values_pair.append((v1 * v2, v1, v2))
		
		else:
			if (K - len(p_list)) % 2 == 1 and len(p_list) > 0:
				p_count = len(p_list) - 1
			else:
				p_count = len(p_list)
			
			if p_count % 2 == 1:
				values_left = p_list.pop()
				values_left_count = 1
				p_count -= 1
			
			for i in range(0, p_count - 1, 2):
				v1 = p_list.pop()
				v2 = p_list.pop()
				values_pair.append((v1 * v2, v1, v2))
			
			while len(values_pair) * 2 + values_left_count < K:
				v1 = n_list.pop()
				v2 = n_list.pop()
				values_pair.append((v1 * v2, v1, v2))
		
		values_pair.sort()
		
#		print(values_pair)
		
		i = 0
		for i in range(len(values_pair)):
			if len(n_list) < 2:
				break
			elif values_pair[i][0] < n_list[-1] * n_list[-2]:
				v1 = n_list.pop()
				v2 = n_list.pop()
				values_pair[i] = (v1 * v2, v1, v2)
			else:
				break
		if values_left != None:
			values.append(values_left)
		
		for prod, v1, v2 in values_pair:
			values.append(v1)
			values.append(v2)
	
#	print(values)
	total = 1
	for v in values:
		total = (total * v) % M
#		total = (total * v)
	print(total)


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

int main(){
	int d;
	while(cin>>d&&d){
		int MAX_p=0,MAX_d=0;
		for(int p,d1,d2;d--;){
			cin>>p>>d1>>d2;
			if(MAX_d<d1+d2){
				MAX_d=d1+d2;
				MAX_p=p;
			}
		}
		cout<<MAX_p<<" "<<MAX_d<<endl;
	}
}

Measured memory_bytes: 864
/* ex 7_1
   kanon */

#include <stdio.h>
#include <stdlib.h>

typedef struct point
{
    int x_elem;
    int y_elem;
} point;

point shift_point(int x, int y, point point_)
{
    point new_point = point_;
    //元の頂点point_からx軸方向にx、y軸方向にyだけ移動した頂点を返す
    new_point.x_elem += x;
    new_point.y_elem += y;
    return new_point;
}

int main(void)
{
    //頂点の座標を入れる変数を宣言
    point point1, point2, point3, point4;
    int dif_x, dif_y;

    scanf("%d %d %d %d", &point1.x_elem, &point1.y_elem, &point2.x_elem, &point2.y_elem);

    //既知の頂点１と２のx座標y座標の差をとる
    dif_x = point2.x_elem - point1.x_elem;
    dif_y = point2.y_elem - point1.y_elem;

    //頂点３は頂点２の位置ベクトル＋ベクトル(-dif_y,dif_X)で求まる
    //頂点４は頂点１の位置ベクトル＋ベクトル(-dif_y,dif_X)で求まる
    point3 = shift_point(-dif_y, dif_x, point2);
    point4 = shift_point(-dif_y, dif_x, point1);

    printf("%d %d %d %d", point3.x_elem, point3.y_elem, point4.x_elem, point4.y_elem);
    return 0;
}

Measured memory_bytes: 1704
from bisect import*
class SqrtSet:
    def __init__(self,block_limit=201):
        self.key=[]
        self.child=[[]]
        self.block_limit=block_limit
    def search_lower(self,key):
        if not key:return None
        ret=None
        i=bisect_left(self.key,key)
        if i:ret=self.key[i-1]
        block=self.child[i]
        i=bisect_left(block,key)
        if i:ret=block[i-1]
        return ret
    def search_higher(self,key):
        if not key:return None
        ret=None
        i=bisect(self.key,key)
        if i<len(self.key):ret=self.key[i]
        block=self.child[i]
        i=bisect(block,key)
        if i<len(block):ret=block[i]
        return ret
    def insert(self,key):
        i=bisect(self.key,key)
        block=self.child[i]
        insort(block,key)
        if len(block)==self.block_limit:
            sep=self.block_limit//2
            self.key.insert(i,block[sep])
            self.child.insert(i+1,block[sep+1:])
            self.child[i]=block[:sep]
def main():
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    t=SqrtSet()
    t.insert(0)
    t.insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(t.search_higher(v)-v)*(v-t.search_lower(v))*i
        t.insert(v)
    print(c)
main()

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

score = []
for i in range(n):
    s, p = [l for l in input().split()]
    score.append([i+1, s, int(p)])

for i, s, p in sorted(sorted(score, key=lambda x:x[2], reverse=True), key=lambda x:x[1]):
    print(i)


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

template<typename T>
ostream& operator<<(ostream &os, vector<T> &v){
	string sep = " ";
	if(v.size()) os << v[0];
	for(int i=1; i<v.size(); i++) os << sep << v[i];
	return os;
}

template<typename T>
istream& operator>>(istream &is, vector<T> &v){
	for(int i=0; i<v.size(); i++) is >> v[i];
	return is;
}

#ifdef DBG
void debug_(){ cout << endl; }
template<typename T, typename... Args>
void debug_(T&& x, Args&&... xs){
	cout << x << " "; debug_(forward<Args>(xs)...);
}
#define dbg(...) debug_(__VA_ARGS__)
#else
#define dbg(...)
#endif

int main() {
	ios_base::sync_with_stdio(false);
	cout << setprecision(20) << fixed;

	int k; cin >> k;

	int x = 7 % k;
	for(int i=0; i<k+10; i++){
		if(x == 0){
			cout << i+1 << endl;
			return 0;
		}
		x = (10*x+7) % k;
	}

	cout << -1 << endl;

	return 0;
}


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

const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int SUMN = 1e5 + 2;
const int N = 1e2 + 2;

int n, w, sum;
int weight[N], value[N];
ll dp[SUMN];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	cin >> n >> w;

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

	for (int i = 1; i <= sum; ++i)
		dp[i] = INFLL;

	for (int i = 1; i <= n; ++i) {
		for (int j = sum; j >= value[i]; --j) {
			dp[j] = min(dp[j], dp[j-value[i]] + weight[i]);
		}
	}

	int ans = 0;
	for (int i = 0; i <= sum; ++i) {
		if (dp[i] <= w) {
			ans = max(ans, i);
		}
	}

	cout << ans << "\n";
	
	return 0;
}


Measured memory_bytes: 1024
# include<iostream>
# include<string.h>
# include<algorithm>
using namespace std;
struct node
{
    char s[10];
    friend bool operator < (node a, node b)
    {
        int i;
        for(i = 0; a.s[i] != '\0' && b.s[i] != '\0'; ++i)
            if(a.s[i] != b.s[i])
                return a.s[i] < b.s[i];
        return a.s[i] < b.s[i];
    }
} s1[300000];
int main(void)
{
    char s[5003];
    int k, i, j;
    cin >> s;
    cin >> k;
    int cnt = 0;
    for(i = 0; s[i] != '\0'; ++i)
    {
        s1[cnt].s[0] = s[i];
        s1[cnt++].s[1] = '\0';
        int q = 1;
        for(j = i + 1; s[j] != '\0' && q <= 5; ++j)
        {
            strcpy(s1[cnt].s, s1[cnt-1].s);
            s1[cnt].s[q] = s[j];
            s1[cnt++].s[++q] = '\0';
            //cout << "i=" << i<<"      "<<s1[cnt-1].s << endl;
        }
    }
    sort(s1, s1+cnt);
    if(k == 1)
    {
        cout << s1[0].s << endl;
        return 0;
    }
    i = 1;
    int q = 1;
    while(k)
    {
        if(strcmp(s1[i].s, s1[i-1].s) != 0)
        {
            q++;
            if(k == q)
            {
                cout << s1[i].s << endl;
                return 0;
            }
        }
        i++;
    }
    return 0;
}


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

int main()
{
	int n;
	cin >> n;
	if(n == 1)
	{
		cout << "Hello World" << endl;
	}
	else
	{
		int a, b;
		cin >> a >> b;
		cout << a + b << endl;
	}
	system("pause");
	return 0;
}

Measured memory_bytes: 504
#include<bits/stdc++.h>
using namespace std;
int main(){
  string a;
  cin>>a;
  int cnt[30]={};
  for(int i=0;i<a.size();i++)cnt[a[i]-'a']++;
  if(a=="zyxwvutsrqponmlkjihgfedcba")cout<<-1<<endl;
  else if(a.size()==26){
    int i=25;
    cnt[a[i]-'a']--;
    while(a[i-1]>a[i])cnt[a[i-1]-'a']--,i--;
    if(i==1){
    a[0]++;
    cout<<a[0]<<endl;
    }else{
      for(int j=0;j<i-1;j++)cout<<a[j];
      for(int j=a[i-1]-'a'+1;j<='z'-'a';j++){
	if(cnt[j]==0){
	  char s=j+'a';
	  cout<<s<<endl;
	  break;
	}
      }
       }
  }else{
    cout<<a;
    for(int i=0;i<26;i++)
      if(cnt[i]==0){
	char s=i+'a';
	cout<<s<<endl;
	return 0;
      }
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  long long x;
  cin >> n >> x;
  long long a[n];
  cin >> a[0];
  long long ans = 0;
  if(a[0] > x){
    ans += a[0]-x;
    a[0] = x;
  }
  for(int i = 1; i < n; i++){
    cin >> a[i];
    if(a[i]+a[i-1] > x){
      long long dif = a[i]+a[i-1]-x;
      ans += dif;
      if(a[i] >= dif) a[i] -= dif;
      else a[i] = 0;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_size=100000;//количество факториалов, которых посчитает прога
int n;
ll a[200000];
ll chet[200000];
ll suf[200000];
ll Q;
ll x;
int ind;
bool r;
bool funk1(int l,int k){
    if(ind+l+1>=n) return 1;
    if(ind-(k-l-1)<0) return 0;
    if(x-a[ind-(k-l-1)]>a[ind+l+1]-x) return 0;
 //   cout<<"lol";
    return 1;
} 
bool funk(int  k){
  //  if()
    ll mn=0;
    ll mx=k+1;
    ll md=(mn+mx)/2;
    while(mn+1<mx){
        if(funk1(md,k)==0){
            mn=md;
            md=(mn+mx)/2;
        }
        else{
            mx=md;
            md=(mx+mn)/2;
        }
   //     cout<<mn<<" "<<md<<" "<<mx<<endl;
    }
 //   cout<<funk1(1,2)<<" ";
 //   cout<<mn<<endl;
    if(funk1(mn,k)==1) mx=mn;
 //   cout<<mx<<" "<<ind<<" " <<k<<" "<<n<<endl;
    if(n>ind+mx+k){
        if(n>ind+mx+k+1){
            r=1;
        }
        else r=0;
        return 1;
    }
    else{
        return 0;
    }
}
int main() {
	ios_base::sync_with_stdio(false);
	cin>>n>>Q;
	for(int i=0;i<n;i++) cin>>a[i];
	a[n]=-1e17;
	n++;
	sort(a,a+n);
	chet[1]=a[1];
	for(int i=2;i<n;i++){
	    chet[i]=chet[i-2]+a[i];
	    
//	    cout<<chet[i]<<endl;
	}
	suf[n]=0;
	for(int i=n-1;i>-1;i--){
	    suf[i]=a[i]+suf[i+1];
//	    cout<<suf[i]<<endl;
	}
//	x=9;
//	ind=3;
//	cout<<funk(2);
//	return 0;
	for(int T=0;T<Q;T++){
	    cin>>x;
	    int mn1=0,mx1=n,md1;
	    md1=(mn1+mx1)/2;
	    while(mn1+1<mx1){
	        if(a[md1]<=x){
	            mn1=md1;
	            md1=(mn1+mx1)/2;
	        }
	        else{
	            mx1=md1;
	            md1=(mn1+mx1)/2;
	        }
	    }
	    ind=mn1;
	    int mn=0,mx=n,md;
	    md=(mn+mx)/2;
	    while(mn+1<mx){
	        if(funk(md)==1){
	            mn=md;
	            md=(mn+mx)/2;
	        }
	        else{
	            mx=md;
	            md=(mn+mx)/2;
	        }
	    }
	    ll ans=0;
	    if(r){
	       // cout<<suf[n-(mn+1)]<<" "<<n-(mn+1)<<"xxx";
	        //cout<<chet[n-(mn+1)*2-1]<<" "<<n-(mn+1)*2<<"xxx";
	        ans=suf[n-(mn+1)]+chet[n-(mn+1)*2-1];
	    }
	    else{
	      //  cout<<suf[n-mn]<<" "<<n-mn<<"xxx";
	      //  cout<<chet[n-2*mn-1]<<" "<<n-2*mn<<"xxx";
	        ans=suf[n-mn]+chet[n-2*mn-1];
	    }
	    cout<<ans<<'\n';
	}
	return 0;
}

Measured memory_bytes: 4992
#include <iostream>
using namespace std;
int main(void){
   int a,b,c,d,e,f,g,h,i,j;
   cin >> a >> b >> c >> d>> e >> f >> g >> h >> i >> j;
   cout << a+b+c+d+e+f+g+h+i+j << endl;
   return 0;
}


Measured memory_bytes: 3100
#include <stdio.h>

int main(void)
{
    int n;
    int a;
    int x;
    int i;
    int y;

    scanf("%d", &n);

    a = 0;

    for (x = n; x >= 1; x--){

        i = 0;
        
        if (x % 2 == 1){
            
            for (y = x; y >= 1; y--){
                
                if (x % y == 0){
                    i++;
                }
            }
        }
        if (i == 8){
            a++;
        }
    }

    printf("%d", a);

    return (0);
}


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

#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;


void solve()
{
	int n;
	cin >> n;
	int a[n];
	int xorr = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		xorr ^= a[i];
	}

	for (int i = 0; i < n; i++)
	{
		cout << (int)(xorr ^ a[i]) << " ";
	}
}

int main()
{

	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}




Measured memory_bytes: 4428
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<long long> a(N);
    for(int i=0; i<N; ++i) cin >> a[i];

    long long sum = 0;
    long long xorsum = 0;
    long long res = 0;
    int right = 0;


    for(int left=0; left<N; ++left){

        while(right <N && ((right == left) || (sum+a[right]) == (xorsum ^ a[right]) ) ){
            sum += a[right];
            xorsum = xorsum^a[right];
            right++;
        // int aa = sum+a[right];
        // int bb = xorsum ^ a[right];
        }


        res += right - left;
        sum -= a[left];
        xorsum = xorsum^a[left];

    }
    cout << res << endl;
}

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

using namespace std;

using ll = long long;
using ld = long double;

using data = pair<ll, pair<int, pair<int, int>>>;
using flag_data = pair<int, pair<int, int>>;

int main()
{
	int x, y, z;
	cin >> x >> y >> z;
	int k;
	cin >> k;
	vector<ll> a(x), b(y), c(z);
	for (int i = 0; i < x; ++i)
	{
		cin >> a[i];
	}
	for (int i = 0; i < y; ++i)
	{
		cin >> b[i];
	}
	for (int i = 0; i < z; ++i)
	{
		cin >> c[i];
	}
	sort(a.rbegin(), a.rend());
	sort(b.rbegin(), b.rend());
	sort(c.rbegin(), c.rend());
	priority_queue<data> q;
	q.push({a[0] + b[0] + c[0], {0, {0, 0}}});
	map<flag_data, int> mp;
	for (int i = 0; i < k; ++i)
	{
		auto m = q.top();
		q.pop();
		cout << m.first << endl;
		if (x > m.second.first + 1 && !mp[{m.second.first + 1, {m.second.second.first, m.second.second.second}}])
		{
			q.push({a[m.second.first + 1] + b[m.second.second.first] + c[m.second.second.second],
					{m.second.first + 1,
					 {m.second.second.first,
					  m.second.second.second}}});
			mp[{m.second.first + 1, {m.second.second.first, m.second.second.second}}] = 1;
		}
		if (y > m.second.second.first + 1 && !mp[{m.second.first, {m.second.second.first + 1, m.second.second.second}}])
		{
			q.push({a[m.second.first] + b[m.second.second.first + 1] + c[m.second.second.second],
					{m.second.first,
					 {m.second.second.first + 1,
					  m.second.second.second}}});
			mp[{m.second.first, {m.second.second.first + 1, m.second.second.second}}] = 1;
		}
		if (z > m.second.second.second + 1 && !mp[{m.second.first, {m.second.second.first, m.second.second.second + 1}}])
		{
			q.push({a[m.second.first] + b[m.second.second.first] + c[m.second.second.second + 1],
					{m.second.first,
					 {m.second.second.first,
					  m.second.second.second + 1}}});
			mp[{m.second.first, {m.second.second.first, m.second.second.second + 1}}] = 1;
		}
	}
}

Measured memory_bytes: 896
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
constexpr auto INF = 1000000000;
constexpr auto LLINF = 1LL << 62;
constexpr auto mod = 1000000007;
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; }

ll dp[2010][2010];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    VI s(n), t(m);
    dp[0][0] = 1;
    FOR(i, 0, n) {
        cin >> s[i];
        dp[i + 1][0] += dp[i][0];
    }
    FOR(i, 0, m) {
        cin >> t[i];
        dp[0][i + 1] += dp[0][i];
    }
    
    FOR(i, 0, n)FOR(j, 0, m) {
        if (s[i] == t[j])dp[i + 1][j + 1] += dp[i][j];
        dp[i + 1][j + 1] += dp[i][j + 1];
        dp[i + 1][j + 1] += dp[i + 1][j];
        dp[i + 1][j + 1] -= dp[i][j];
        dp[i + 1][j + 1] = (dp[i + 1][j + 1] + mod) % mod;
    }
    cout << dp[n][m] << endl;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
vector<pair<int,int>> E[101010];
int Q,K;
ll D[101010];

void dfs(int cur,int pre,ll d) {
	D[cur]=d;
	FORR(e,E[cur]) if(e.first!=pre) dfs(e.first,cur,d+e.second);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y>>j;
		E[x-1].push_back({y-1,j});
		E[y-1].push_back({x-1,j});
	}
	cin>>Q>>K;
	dfs(K-1,K-1,0);
	FOR(i,Q) {
		cin>>x>>y;
		cout<<D[x-1]+D[y-1]<<endl;
	
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 12800
import sys

def solve():
    N, W = map(int, input().split())
    v = [[] for i in range(4)]

    for i in range(N):
        wi, vi = map(int, input().split())

        if i == 0:
            base = wi
            v[0].append(vi)
        else:
            v[wi - base].append(vi)

    for i in range(4):
        v[i].sort(reverse=True)

    ans = 0

    for i in range(len(v[0]) + 1):
        for j in range(len(v[1]) + 1):
            for k in range(len(v[2]) + 1):
                for l in range(len(v[3]) + 1):
                    w = base*i + (base + 1)*j + (base + 2)*k + (base + 3)*l

                    if w > W:
                        continue

                    kakaku = sum(v[0][:i]) + sum(v[1][:j]) + sum(v[2][:k]) + sum(v[3][:l])

                    ans = max(ans, kakaku)

    print(ans)

if __name__ == '__main__':
    solve()

Measured memory_bytes: 3064
package main

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

func main() {
	s := readBytes()
	q := readInt()

	b := make([]byte, len(s)+2*q+10)
	start := q + 5
	end := start + len(s) - 1
	for i := range s {
		b[start+i] = s[i]
	}

	flipCnt := 0
	for i := 0; i < q; i++ {
		if readInt() == 1 {
			flipCnt++
			continue
		}

		f, c := readInt(), readBytes()[0]
		if (f == 1 && flipCnt%2 == 0) || (f == 2 && flipCnt%2 == 1) {
			start--
			b[start] = c
		} else {
			end++
			b[end] = c
		}
	}

	if flipCnt%2 == 0 {
		fmt.Println(string(b[start : end+1]))
	} else {
		for i := end; i >= start; i-- {
			fmt.Print(string(b[i]))
		}
	}
}

func main1() {
	s := readBytes()
	q := readInt()

	a := make([]int, len(s))
	for i := range s {
		a[i] = int(s[i])
	}

	flipCnt := 0
	for i := 0; i < q; i++ {
		if readInt() == 1 {
			flipCnt++
			continue
		}

		f, c := readInt(), int(readBytes()[0])
		if (f == 1 && flipCnt%2 == 0) || (f == 2 && flipCnt%2 == 1) {
			a = append([]int{c}, a...)
		} else {
			a = append(a, c)
		}
	}

	if flipCnt%2 == 1 {
		for i := 0; i < len(a)/2; i++ {
			a[i], a[len(a)-1-i] = a[len(a)-1-i], a[i]
		}
	}
	for i := range a {
		fmt.Print(string(byte(a[i])))
	}
}

func main0() {
	s := readBytes()
	q := readInt()

	flipCnt := 0
	for i := 0; i < q; i++ {
		log.Println(i, string(s), s)
		if readInt() == 1 {
			log.Println("t=1")
			flipCnt++
			continue
		}

		f, c := readInt(), readBytes()
		log.Println("t=2", f, c)
		if (f == 1 && flipCnt%2 == 0) || (f == 2 && flipCnt%2 == 1) {
			s = append(c, s...)
		} else {
			s = append(s, c...)
		}
		// log.Println(i, string(s))
	}
	log.Println(string(s), s)

	if flipCnt%2 == 0 {
		fmt.Println(string(s))
		return
	}
	for i := range s {
		fmt.Print(s[len(s)-1-i])
	}
}

var (
	readString func() string
	readBytes  func() []byte
)

func init() {
	log.SetFlags(log.Lshortfile)
	readString, readBytes = newReadString(os.Stdin)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Bytes()
	}
	return f1, f2
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readInt() int {
	return int(readInt64())
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func sum(a []int) int {
	var ret int
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumFloat64(a []float64) float64 {
	var ret float64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func gcd(m, n int) int {
	for m%n != 0 {
		m, n = n, m%n
	}
	return n
}

func lcm(m, n int) int {
	return m / gcd(m, n) * n
}


Measured memory_bytes: 5504
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

const int MaxN = 20000 + 5, MaxLen = 753 + 5;
const int Dig = 100000000;

struct bign {
	int len;
	int a[MaxLen];
};

inline std::istream& operator >> (std::istream& in, bign &x) {
	std::string str;
	std::cin >> str;
	x.len = (str.length() - 1) / 8 + 1;
	memset(x.a, 0, sizeof x.a);
	for (int i = 0; str[i] != '\0'; ++i) {
		int d = (str.length() - i - 1) / 8;
		x.a[d] = x.a[d] * 10 + str[i] - '0';
	}
	return in;
}

inline std::ostream& operator << (std::ostream& out, bign x) {
	if (x.len == 0) {
		printf("%d", 0);
		return out;
	}
	printf("%d", x.a[x.len - 1]);
	for (int i = x.len - 2; i >= 0; --i)
		printf("%08d", x.a[i]);
	return out;
}

inline void operator += (bign &x, const bign &y) {
	x.len = std::max(x.len, y.len);
	for (int i = 0; i < y.len; ++i)
		x.a[i] += y.a[i];
	for (int i = 0; i < x.len; ++i) {
		if (x.a[i] >= Dig) {
			x.a[i + 1]++;
			x.a[i] -= Dig;
		}
	}
	if (x.a[x.len] != 0) x.len++;
}

inline void operator -= (bign &x, const bign &y) {
	for (int i = 0; i < y.len; ++i)
		x.a[i] -= y.a[i];
	for (int i = 0; i < x.len; ++i) {
		if (x.a[i] < 0) {
			x.a[i] += Dig;
			x.a[i + 1]--;
		}
	}
	while (x.len > 0 && x.a[x.len - 1] == 0) x.len--;
}

inline bool operator == (const bign &x, const bign &y) {
	if (x.len != y.len) return false;
	for (int i = 0; i < x.len; ++i)
		if (x.a[i] != y.a[i]) return false;
	return true;
}

inline bool operator > (const bign &x, const bign &y) {
	if (x.len < y.len) return false;
	if (x.len > y.len) return true;
	for (int i = x.len - 1; i >= 0; --i) {
		if (x.a[i] > y.a[i]) return true;
		if (x.a[i] < y.a[i]) return false;
	}
	return false;
}

int N;
bign X;
bign _0, _1, _2, _3;
bign F[MaxN], G[MaxN];
bign ans, x;

void init() {
	scanf("%d", &N);
	std::cin >> X;

	_0.len = 0;
	_1.len = 1, _1.a[0] = 1;
	_2.len = 1, _2.a[0] = 2;
	_3.len = 1, _3.a[0] = 3;
}

void dfs(int n) {
	if (x == _0) {
		ans = _0;
		return;
	}
	if (n == 0) {
		ans = _1;
		return;
	}

	x -= _1;
	if (x > F[n - 1]) {
		x -= F[n - 1]; x -= _1;
		dfs(n - 1);
		ans += G[n - 1]; ans += _1;
	} else {
		dfs(n - 1);
	}
}

void solve() {
	F[0] = G[0] = _1;
	for (int i = 1; i <= N; ++i) {
		F[i] = F[i - 1];
		F[i] += F[i - 1]; F[i] += _3;
		G[i] = G[i - 1];
		G[i] += G[i - 1]; G[i] += _1;
	}

	x = X;
	dfs(N);
	std::cout << ans << std::endl;
}

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

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

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int main(){
	LL X;
	cin >> X;
	for(LL B=-100; B<=1000; B++){
		for(LL A=1; A<=1000; A++){
			if(pow(A,5)-pow(B,5)==X){
				cout << A << " " << B << endl;
				return 0;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 4068
#include <bits/stdc++.h>
#include <algorithm>
#include <utility>
using namespace std;
int main() {
	int H, W, h, w; 
	cin >> H >> W >> h >> w; 
	long long int A[510][510] = {}; 
	long long int sum = 0; 
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(i % h == 0 && j % w == 0){A[i][j] = (long long) 999999999;}
			if(i % h == h - 1 && j % w == w - 1){A[i][j] = (long long) (-1000000000);}
			sum += A[i][j]; 
		}
	}
	if(sum <= 0){cout << "No" << endl;}
	else{
        cout << "Yes" << endl; 
		for(int i = 0; i < H; i++){
			for(int j = 0; j < W; j++){
				cout << A[i][j] << " "; 
			}
			cout << endl; 
		}	
	}
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
#define x first
#define y second
#define iter iterator
#define riter reverse_iterator
#define y1 Lorem_ipsum_
#define tm dolor_sit_amet_
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int mxN = 5000;
const llong P = 1e9+7;
llong f[mxN+3][2],g[mxN+3][2],h[mxN+3][2];
int n,A,B;

void updsum(llong &x,llong y) {x+=y-P,x+=(x>>31)&P;}

int main()
{
	n = read(),A = read(),B = read(); if(A>B) {swap(A,B);}
	g[0][0] = 1ll;
	for(int i=1; i<=n; i++)
	{
		for(int j=A; j<=i; j++)
		{
			updsum(g[i][0],g[i-j][1]);
		}
		for(int j=1; j<=i; j++)
		{
			updsum(g[i][1],g[i-j][0]);
		}
	}
	for(int i=1; i<=n; i++)
	{
		if(i<A) {f[i][0] = 1ll;}
		if(i<B) {f[i][1] = (g[i][0]+g[i][1])%P;}
		for(int j=1; j<i&&j<B; j++)
		{
			updsum(f[i][1],f[i-j][0]*g[j][1]%P);
		}
		for(int j=1; j<i&&j<A; j++)
		{
			updsum(f[i][0],f[i-j][1]);
		}
	}
	llong tot = 1ll,ans = f[n][0];
	for(int i=1; i<=n; i++) {tot = tot*2ll%P;}
	for(int i=1; i<B; i++)
	{
		updsum(ans,f[n-i][0]*(g[i][0]+g[i][1])%P);
	}
	printf("%lld\n",(tot-ans+P)%P);
	return 0;
}

Measured memory_bytes: 3840