akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 2000010;
 
// aのn乗を求める。計算量はO(logn)
ll modpow(ll a, ll n) {
    if(n == 0) {
        return 1;
    }
    if(n%2 == 1) {
        return (a * modpow(a, n-1))%mod;
    }
    return (modpow(a, n/2) * modpow(a, n/2))%mod;
}
 
ll inverse(ll a) {
    return modpow(a, mod-2);
}
 
ll fact[MAX_N];  // fact[i] : iの階乗のmod
ll invfact[MAX_N];
 
void init() {
    fact[0] = invfact[0] = 1;
    for(ll i = 1; i < MAX_N; i++) {
        fact[i] = (i*fact[i-1])%mod;
        invfact[i] = inverse(fact[i]);
    }
}
 
ll Comb(ll n, ll r) {
    if(r < 0 || n < 0 || n < r) {
        return 0;
    }
    ll res = fact[n];
    res = (res * invfact[r])%mod;
    res = (res * invfact[n-r])%mod;
    return res;
}
 
//--- main関数でinit()を呼び出すのを忘れるな ---//
int main() {
    ll r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
 
    init();
    
    ll ans = 0;
    exrep(i, r1, r2) {
        ans += (Comb(i+c2+1, i+1) + mod - Comb(i+c1, i+1))%mod;
        ans %= mod;
    }
    
    out(ans);
    re0;
}

Measured memory_bytes: 31488
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, k;
	string s;
	cin >> n >> k >> s;
	if (s[k-1] == 'A') s[k-1] = 'a';
	if (s[k-1] == 'B') s[k-1] = 'b';
	if (s[k-1] == 'C') s[k-1] = 'c';
	cout << s << endl;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;

#define M 1000000 
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define fill(a,x) memset(a,x,sizeof(a))
#define F first
#define S second
#define FOR(i,a,b) for(ll i = a; i<=b; ++i)
#define NFOR(i,a,b) for(ll i = a; i>=b; --i)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const ll INF = 1e18;
const ll mod = 1e9+7;
const ll N = 1e5 + 10;
inline ll add(ll x,ll y){
  x += y;
  if(x >= mod) x -= mod;
  return x;
}
inline ll mul(ll x,ll y){
  x = (1LL * x * y) % mod;
  return x;
}


int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}

int main()
{
	fast;

	int n,x;cin>>n>>x;
	int g = 0;
	FOR(i,1,n){
		int xi;cin>>xi;
		g = gcd(g,abs(xi-x));
	}

	cout << g;

	return 0;
}

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

int main() {
  int n,a1,a2,a3,a4;
  cin >> n;
  a1=n/1000;
  a2=(n/100)%10;
  a3=(n/10)%10;
  a4=n%10;
  if ( a2==a3 && (a1==a2 || a3==a4) ){
    cout << "Yes" << endl;
  } else {
	cout << "No" << endl;
  }
}


Measured memory_bytes: 256
program test 
implicit none
integer::n,i,ans
character(len=50)::s
read*,n, s
s=trim(s)
ans=0
do i=1,n-2
	if(s(i:i+2)=='ABC')then
    	ans=ans+1
    else 
    	ans=ans
    end if
end do
print*,ans
end program test
    

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define lim 2e9
#define on 100005
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
typedef long long int lo; 
typedef pair<int,int> PII;
int n,m,cev,a[100005],vis[on],cevv;
char c;
string s;
stack<int> st;
vector<int> v[200005];
int main(){
	cin>>s;
	for(int i=0;i<(int)s.size();i++){
		if(s[i]=='1')
			s[i]='9';
		else if(s[i]=='9')
			s[i]='1';
	}
	cout<<s;
	return 0;
}



Measured memory_bytes: 4992
n = int(input())
p = [int(x) for x in input().split()]
switch = 0
memory = 0

for i in range(n):
    if i+1 != p[i]:
        if switch == 2:
            print("NO")
            exit()
        
        if switch == 1:
            if memory == i+1:
                switch = 2
            else:
                print("NO")
                exit()
            
        else:
            switch = 1
            memory = p[i]

print("YES")

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main(){
  int n;
  long y;
  cin >> n >> y;
  for(int i = 0;i<=n;i++){
    for(int j = 0;j<=n;j++){
      if(n-i-j>=0 && (n-i-j)*10000+j*5000+i*1000 == y){
        cout << n-i-j << " " << j << " " << i << endl;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
import operator
import itertools

def op(op_str):
    funcs = {
            "+":operator.add,
            "-":operator.sub
            }
    return funcs[op_str]

def solve(A,B,C,D):
    for o in itertools.product(["+","-"], repeat = 3):
        ret = op(o[0])(A,B)
        ret = op(o[1])(ret,C)
        ret = op(o[2])(ret,D)
        if ret == 7:
            print("{0}{1}{2}{3}{4}{5}{6}=7".format(A,o[0],B,o[1],C,o[2],D))
            return


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    S = input()
    L = [int(c) for c in S]
    
    solve(*L)

if __name__ == '__main__':
    main()


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

int main(){
  string s,t;
  cin >> s >> t;
  int ans=0;
  for(int i=0;i<s.size();i++)
    if(s.at(i)!=t.at(i))
      ans++;
  cout << ans << endl;
  return 0;
}

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

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define SIZE(c) (int) (c).size()
#define FORE(i,c) FOR(i,0,SIZE(c)-1)
#define FORDE(i,c) FORD(i,SIZE(c)-1,0)

#define pb push_back
#define mp make_pair
#define st first
#define nd second


using namespace std;

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

typedef vector <int> VI;
typedef vector <bool> VB;
typedef vector <pii> VP;
typedef vector <ll> VL;
typedef vector <pll> VPL;

typedef vector <VI> VVI;
typedef vector <VL> VVL;
typedef vector <VB> VVB;
typedef vector <VP> VVP;

const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000000000000001LL;


/*************************************************************************/

int main() {
    ios_base::sync_with_stdio(0);
    
    int n;
    cin >> n; n *= 3;
    
    VI a(n);
    FOR(i,0,n-1) {
        cin >> a[i];
    }
    
    sort(a.begin(), a.end(), greater <int> ());
    
    int k = n / 3;
    
    ll ans = 0;
    FOR(i,0,k-1) {
        ans += a[2 * i + 1];
    }
    
    cout << ans;

    return 0;
}

/*************************************************************************/


Measured memory_bytes: 1408
#include <iostream>                                             
#include <cstdio>                                               
#include <cstring>                                              
using namespace std;                                            
                                                                
int main() {                                                    
  int r, c;                                                     
  cin >> r >> c;                                                
  int rc[r+1][c+1];                                             
  memset(rc,0,sizeof(rc));                                      
  for (int i=0; i<r; i++) {                                     
    for (int j=0; j<c; j++) {                                   
      cin >> rc[i][j];                                          
    }                                                           
  }                                                             
  for (int i=0; i<r; i++) {                                     
    for (int j=0; j<c; j++) {                                   
      rc[i][c] += rc[i][j];                                     
      rc[r][j] += rc[i][j];                                     
    }                                                           
    rc[r][c] += rc[i][c];                                       
  }                                                             
  for (int i=0; i<r+1; i++) {                                   
    for (int j=0; j<c+1; j++) {                                 
      cout << ((i>=0 && j==0)?"":" ") << rc[i][j] << flush;     
    }                                                           
    printf("\n");                                               
  }                                                             
  return 0;                                                     
}                                                               
                                                                
                                                                
                                                                
                                                                
                              

Measured memory_bytes: 3100
#include <cstdio>
#include <algorithm>
using namespace std;
const int Maxn=200000;
int a[Maxn+5];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n);
	for(int i=1;i<n;i++){
		if(a[i]==a[i+1]){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);

#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define FOR(i,s,n)	for(int i=s;i<(int)n;++i)

#define FIRST "First"
#define SECOND "Second"

string s;

int main(int argc, char **argv) {
	cin >> s;
	if ((s[0] == s[s.length() - 1]) == (s.length() % 2 == 0)) {
		cout << FIRST << endl;
	}
	else {
		cout << SECOND << endl;
	}
	return 0;
}


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

// [i, n)の最大値
int max_e[100005];
int dif[100005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    
    int m = 0;
    for(int i = n-1; i >= 0; --i){
        m = max(m, a[i]);
        max_e[i] = m;
    }
    
    int m_ele = 0;
    for(int i = 0; i < n-1; ++i){
        dif[i] = max_e[i+1] - a[i];
        m_ele = max(m_ele, dif[i]);
    }
    
    int cnt = 0;
    for(int i = 0; i < n-1; ++i){
        if(dif[i] == m_ele)     ++cnt;
    }
    
    cout << cnt << endl;
}

Measured memory_bytes: 1408
import java.util.*;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static int M = 10;
	public static void main(String[] args) {
		int i,j,k;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		int[] f = new int[n];
		for (i = 0; i < n; i++) {
			for (j = 0; j < M; j++) {
				f[i] += parseInt(sc.next())<<j;
			}
//			out.printf("%x%n", f[i]);
		}
		int[][] p = new int[n][M+1];;
		for (i = 0; i < n; i++) {
			for (j = 0; j <= M; j++) {
				p[i][j] = parseInt(sc.next());
			}
		}
		sc.close();
		int max = -1000000000 - 1;
		for (i = 1; i < 1024; i++) {
			int tmp=0;
			for (j = 0; j < n; j++) {
				tmp += p[j][bitCount(f[j]&i)];
			}
			if(tmp>max)max=tmp;
		}
		out.println(max);
	}
}


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

/**
 * @brief 0からxまでの排他的論理和を計算する。<br>
 * BからAまでの範囲なら、xorial(B) ^ xorial(A-1)で求まる。
 */
template<typename T>
T xorial(T x) {
  T result = 0;
  for (T i = x - x % 4; i <= x; ++i) {
    result ^= i;
  }
  return result;
}

int main() {
  long A, B;
  cin >> A >> B;

  cout << (xorial(B) ^ xorial(A - 1)) << endl;
  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

s=input()
n=len(s)
if n%2==0:
    s=s[0:n-2]
else:
    s=s[0:n-1]

def checkss(str):
    ntemp=int(len(str)/2)
    a=str[0:ntemp]
    b=str[ntemp:]
    if a==b:
        return ntemp*2
    else:
        return -1

while True:
    ans=checkss(s)
    if ans>0:
        print(ans)
        break
    else:
        s=s[0:len(s)-2]


Measured memory_bytes: 3064
from collections import deque

H,W,K = map(int,input().split())
src = [input() for i in range(H)]
sx = sy = None
for i,row in enumerate(src):
    if 'S' in row:
        sy = i
        sx = row.index('S')

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
visited = [[0]*W for i in range(H)]
visited[sy][sx] = 1
q = deque([(0,sx,sy)])
mindist = H+W
while q:
    d,x,y = q.popleft()
    if d > K: break
    dist = min(x, W-x-1, y, H-y-1)
    mindist = min(dist, mindist)
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if src[ny][nx] == '#': continue
        if visited[ny][nx]: continue
        q.append((d+1,nx,ny))
        visited[ny][nx] = 1

ans = -(-mindist//K) + 1
print(ans)

Measured memory_bytes: 61916
import java.util.Scanner;

// https://atcoder.jp/contests/abc144/tasks/abc144_b
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		sc.close();

		boolean flag = false;

		if(N>81) {

		}else {
			for(int i=1;i<=9;i++) {
				if(N%i==0&&N/i<10) {
					flag = true;
					break;
				}
			}
		}

		if(flag) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}



//		int[] array = new int[N];
//		for(int i=0;i<N;i++) {
//			array[i]=sc.nextInt();
//		}
//		sc.close();
	}
}


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

signed main(){
  int H,W,N;
  cin>>H>>W>>N;
  std::vector<int> X(N),Y(N);
  for(int i=0;i<N;i++)cin>>X[i]>>Y[i];
  int ans=H;
  typedef pair<int,int> P;
  std::vector<P> v(N);
  for(int i=0;i<N;i++)v[i]=P(X[i],Y[i]);
  sort(v.begin(),v.end());
  map<int,int> m;
  m[1]=1;
  m[0]=-1e7;
  int x,y;
  for(int i=0;i<N;i++){
    x=v[i].first;y=v[i].second;
    //cout<<y-x<<" "<<(--m.upper_bound(x))->second-1<<endl;
    if(y-x>(--m.lower_bound(x))->second-1)continue;
    if(y-x==(--m.lower_bound(x))->second-1)m[x]=y-x;
    else{ans=x-1;break;}
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 8064
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define ll long long
#define p pair<ll,ll>
#define fcout cout << fixed << setprecision(20)
using namespace std;

int main() {
    ll startx, starty, goalx, goaly;
    cin >> startx >> starty >> goalx >> goaly;
    int n;
    cin >> n;
    vector<p > v;
    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        if (min(startx, goalx) <= x && x <= max(startx, goalx) &&
            min(starty, goaly) <= y && y <= max(starty, goaly))
            v.push_back(p(abs(startx - x), abs(starty - y)));
    }

    sort(v.begin(), v.end());
    vector<ll> LIS(v.size(), 1145141919);
    for (int i = 0; i < v.size(); i++) {
        *upper_bound(LIS.begin(), LIS.end(), v[i].second) = v[i].second;
    }

    double ret = (abs(startx - goalx) + abs(starty - goaly)) * 100;
    ret -= (lower_bound(LIS.begin(), LIS.end(), 1145141919) - LIS.begin()) * (20.0 - 5.0 * M_PIl);
    if (lower_bound(LIS.begin(), LIS.end(), 1145141919) - LIS.begin() ==
        min(abs(startx - goalx), abs(starty - goaly)) + 1)
        ret += 5.0 * M_PIl;

    fcout << ret << endl;
    return 0;
}

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

using namespace std;

list<int> CreatePrimes(int N) {
  list<int> Numbers(N - 1);
  iota(Numbers.begin(), Numbers.end(), 2);
  list<int> PrimeList;
  auto prime = Numbers.front();
  const int rtn = (int)sqrt(N);
  while (prime <= rtn) {
    PrimeList.push_back(prime);
    Numbers.erase(
        remove_if(Numbers.begin(), Numbers.end(),
                  [=](const auto Number) { return Number % prime == 0; }),
        Numbers.end());
    prime = Numbers.front();
  }
  PrimeList.splice(PrimeList.end(), move(Numbers));
  return PrimeList;
}

array<int, 100> table;

int main() {
  int n;
  cin >> n;
  auto primes = CreatePrimes(n);
  for (int i = 1; i <= n; ++i) {
    for (auto p : primes) {
      int j = i;
      while (j % p == 0) {
        ++table[p];
        j /= p;
      }
    }
  }
  int ans = 0;
  for (auto p1 : primes) {
    for (auto p2 : primes) {
      for (auto p3 : primes) {
        if (p1 == p2 || p1 == p3 || p2 == p3)
          continue;
        if (table[p1] >= 2 && table[p2] >= 4 && table[p3] >= 4)
          ++ans;
      }
    }
  }
  ans /= 2;
  for (auto p1 : primes) {
    if (table[p1] >= 74)
      ++ans;
    for (auto p2 : primes) {
      if (p1 == p2)
        continue;
      if (table[p1] >= 14 && table[p2] >= 4)
        ++ans;
      if (table[p1] >= 24 && table[p2] >= 2)
        ++ans;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
def gcd(a, b):
	if a < b:
		tmp = a
		a = b
		b = tmp
	
	r = a % b
	while r != 0:
		a = b
		b = r
		r = a % b

	return b

if __name__ == '__main__':
	l = list(map(int, input().split()))
	x = l[0]
	y = l[1]

	ans = gcd(x, y)
	print(ans)

Measured memory_bytes: 7744
import java.io.*;
import java.util.*;
public class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
		String s=reader.readLine();
		char[] in=s.toCharArray();
		for(int i=in.length-1;i>=0;i--)System.out.print(in[i]);
		System.out.println();
	}
}

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

using namespace std;

inline int ctoi(char c) { if(c < '0' || '9' < c) throw invalid_argument("ctoi error"); return c - '0'; }
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for(int i = (int)(k); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

template <typename T>
inline T gcd(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("gcd error: x <= 0 or y <= 0");
	
	if(x < y) swap(x, y);
	T r = x % y;

	while(r != 0){
		x = y;
		y = r;
		r = x % y;
	}

	return y;
}
template <typename T>
inline T lcm(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("lcm error: x <= 0 or y <= 0");

	return x * y / gcd(x, y);
}

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

	vector<int> miss;
	vector<bool> AC;

	long long int ans = 0;
	long long int wrong = 0;

	rep(i, n){
		miss.push_back(0);
		AC.push_back(false);
	}

	rep(i, m){
		int a;
		string s;
		cin >> a >> s;

		// for(auto a : AC) cout << a << " ";
		// cout << endl;

		if(s == "WA" && AC[a - 1] == false){
			miss[a - 1]++;;
		}
		else if(s == "AC" && AC[a - 1] == false){
			AC[a - 1] = true;
		}
	}

	rep(i, n){
		if(AC[i] == true){
			ans++;
			wrong += miss[i];
		}
	}

	cout << ans << " " << wrong;

	return 0;
}

Measured memory_bytes: 1020
#line 2 "codes/header.hpp"

//%snippet.set('header')%
//%snippet.fold()%
#ifndef HEADER_H
#define HEADER_H

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

// varibable settings
const long long INF = 1e18;
template <class T> constexpr T inf = numeric_limits<T>::max() / 2.1;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define _rrep(i, n) rrepi(i, 0, n)
#define rrepi(i, a, b) for (ll i = (ll)((b)-1); i >= (ll)(a); --i)
#define r_rep(...) _overload3(__VA_ARGS__, rrepi, _rrep, )(__VA_ARGS__)
#define each(i, a) for (auto &&i : a)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(...) make_tuple(__VA_ARGS__)
#define ub upper_bound
#define lb lower_bound
#define lpos(A, x) (lower_bound(all(A), x) - A.begin())
#define upos(A, x) (upper_bound(all(A), x) - A.begin())
template <class T> inline void chmax(T &a, const T &b) { if ((a) < (b)) (a) = (b); }
template <class T> inline void chmin(T &a, const T &b) { if ((a) > (b)) (a) = (b); }
template <typename X, typename T> auto make_table(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto make_table(X x, Y y, Z z, Zs... zs) { auto cont = make_table(y, z, zs...); return vector<decltype(cont)>(x, cont); }

#define cdiv(a, b) (((a) + (b)-1) / (b))
#define is_in(x, a, b) ((a) <= (x) && (x) < (b))
#define uni(x) sort(all(x)); x.erase(unique(all(x)), x.end())
#define slice(l, r) substr(l, r - l)

typedef long long ll;
typedef long double ld;
using vl = vector<ll>;
using vvl = vector<vl>;
using pll = pair<ll, ll>;

template <typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;
void check_input() { assert(cin.eof() == 0); int tmp; cin >> tmp; assert(cin.eof() == 1); }

#if defined(PCM) || defined(LOCAL)
#else
#define dump(...) ;
#define dump_1d(...) ;
#define dump_2d(...) ;
#define cerrendl ;
#endif

#endif /* HEADER_H */
//%snippet.end()%
#line 2 "codes/solve.cpp"
template<class T=ll> using vec = vector<T>;
struct Fast { Fast() { std::cin.tie(0); ios::sync_with_stdio(false); } } fast;


int solve() {
    int n;cin>>n;
    vector<ll> a(n);
    int x = 0;
    rep(i, n) {
        cin>>a[i];
        x ^= a[i];
    }
    dump(a);

    vec<int> ans(n);
    rep(i, n){
        ans[i] = x ^ a[i];
    }
    rep(i, sz(ans)) cout << ans[i] << (i!=sz(ans)-1 ? " " : "\n");

    // int s = 1;
    // rep(i, 0, n){
    //     if (i!=1)
    //     s ^= ans[i];
    // }
    // dump(s);

    return 0; 
}


int main(){/*{{{*/
    solve();
    check_input();
    return 0;
}/*}}}*/


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

void Main() {
  int a, b, c;
  cin >> a >> b >> c;
  if ((a == b && b != c) || (a == c && a != b) || (b == c && a != b)) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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


Measured memory_bytes: 256
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: i32,
        m: usize,
        a: [i32; m],
    }
    let sum: i32 = a.iter().sum();
    let diff = if n >= sum { n - sum } else { -1 };
    println!("{}", diff);
}


Measured memory_bytes: 2232
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
using namespace std;
const int mod = 1000000007;
#define ll long long

int a[510][510], b[510][510];
int main()
{
	int H, W;
	cin >> H >> W;
	int ans = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> a[i][j];
			b[i][j] = a[i][j];
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W - 1; j++) {
			if (b[i][j] % 2 == 1) {
				ans++;
				b[i][j]--;
				b[i][j + 1]++;
			}
		}
	}
	for (int i = 0; i < H - 1; i++) {
		if (b[i][W - 1] % 2 == 1) {
			ans++;
			b[i][W - 1]--;
			b[i + 1][W - 1]++;
		}
	}
	cout << ans << endl;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W - 1; j++) {
			if (a[i][j] % 2 == 1) {
				a[i][j]--;
				a[i][j + 1]++;
				cout << i + 1 << " " << j + 1 << " " << i + 1 << " " << j + 2 << endl;
			}
		}
	}
	for (int i = 0; i < H - 1; i++) {
		if (a[i][W - 1] % 2 == 1) {
			a[i][W - 1]--;
			a[i + 1][W - 1]++;
			cout << i + 1 << " " << W << " " << i + 2 << " " << W  << endl;
		}
	}
}

Measured memory_bytes: 4096
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    map<int, int> mp;
    int N;
    cin >> N;
    
    for(int n=0; n<N; n++) {
        int a;
        cin >> a;
        mp[a]++;
        mp[a-1]++;
        mp[a+1]++;
    }
    
    int ans=0;
    for(auto itr=mp.begin(); itr!=mp.end(); itr++) {
        ans = max(ans, itr->second);
    }
    
    cout << ans << endl;


    return 0;
    
}

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

int main()
{
	int n, j, count = 0;
	cin >> n;
	int *p = new int[n];

	for (int i = 0; i < n; i++) cin >> p[i];

	for (int i = 0; i < n - 1; i++) {
		int min = i;
		for (int j = i + 1; j < n; j++) {
			if (p[j] < p[min]) min = j;
		}
		if (min != i) {
			swap(p[i], p[min]);
			count++;
		}
	}
	for (j = 0; j < n - 1; j++)
		cout << p[j] << " ";
	cout << p[j] << "\n" << count << "\n";

	delete[] p;
	return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};
int dx9[9]={0,1,0,-1,1,-1,1,0,-1};
int dy9[9]={0,1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;
// << fixed << setprecision
// --------------------------------------
int h, w, k;
#include <cassert>
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

bool check(int x) {
  bool f = true;
  REP(i, w - 2) {
    bool l = 1 << i & x;
    bool r = 1 << (i + 1) & x;
    if(l & r) f = false;
  }
  return f;
}

mint dp[105][10];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> h >> w >> k;
  dp[0][0] = 1;

  REP(i, h) REP(j, w) {
    REP(k, 1 << (w - 1)) if(check(k)) {
      if((j != w - 1) && ((1 << j) & k)) {
        dp[i + 1][j + 1] += dp[i][j].x;
      } else if(j && ((1 << (j - 1)) & k)) {
        dp[i + 1][j - 1] += dp[i][j].x;
      } else {
        dp[i + 1][j] += dp[i][j].x;
      }
    }
  }

  cout << dp[h][k - 1] << endl;
}


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


#if DEBUG
template <typename T>
void debug(const T& value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(const T& value, const Ts&... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                        \
  do {                                  \
    cerr << #__VA_ARGS__ << ": ";       \
    debug(__VA_ARGS__);                 \
    cerr << " (L" << __LINE__ << ")\n"; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define rd(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << '\n';
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define wt(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;


template <typename T, class DS>
class Mo {
 public:
  Mo(DS& ds) : ds_(ds) {}
  void AddQuery(int begin, int end) {
    int index = queries_.size();
    queries_.push_back({begin, end, index});
  }
  std::vector<T> ProcessQueries() {
    int bin = sqrt(queries_.size());
    sort(queries_.begin(), queries_.end(),
         [&bin](const Query& a, const Query& b) {
           int c = a.begin / bin, d = b.begin / bin;
           if (c != d) return c < d;
           if (c % 2 == 0) {
             return a.end < b.end;
           }
           return a.end > b.end;
         });
    std::vector<T> ret(queries_.size());
    Query p = {0, 0, 0};
    for (std::size_t i = 0; i < queries_.size(); ++i) {
      const Query& c = queries_[i];
      Add(c.begin, p.begin);
      Del(p.begin, c.begin);
      Add(p.end, c.end);
      Del(c.end, p.end);
      ret[c.index] = ds_.Get();
      p = c;
    }
    return ret;
  }

 private:
  struct Query {
    int begin, end, index;
  };
  void Add(int begin, int end) {
    for (int i = begin; i < end; ++i) {
      ds_.Add(i);
    }
  }
  void Del(int begin, int end) {
    for (int i = begin; i < end; ++i) {
      ds_.Del(i);
    }
  }
  DS& ds_;
  std::vector<Query> queries_;
};

using namespace std;

struct DS {
  DS(int n) : c(n), kinds(n), unique_kinds(0) {}
  void Add(int i) {
    if (kinds[c[i] - 1]++ == 0) {
      ++unique_kinds;
    }
  }
  void Del(int i) {
    if (--kinds[c[i] - 1] == 0) {
      --unique_kinds;
    }
  }
  int Get() const { return unique_kinds; }
  V<int> c;
  V<int> kinds;
  int unique_kinds;
};

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

  rd(int, n, q);
  DS ds(n);
  rep(i, n) cin >> ds.c[i];

  Mo<int, DS> mo(ds);
  rep(i, q) {
    rd(int, l, r);
    mo.AddQuery(l - 1, r);
  }

  for (int ans : mo.ProcessQueries()) {
    wt(ans);
  }
}


Measured memory_bytes: 15508
#include <iostream>
#include <vector>
#include <queue>
int main()
{
    long long v, e, r;
    std::cin >> v >> e >> r;
    std::vector<std::vector<std::pair<long long, long long>>> edges(v);
    for (long long i = 0; i < e; ++i) {
        long long s, t, d;
        std::cin >> s >> t >> d;
        edges[s].push_back(std::make_pair(d, t));
    }

    const long long inf = 1000000000;
    std::vector<long long> dist(v, inf);

    std::priority_queue<
        std::pair<long long, long long>,
        std::vector<std::pair<long long, long long>>,
        std::greater<std::pair<long long, long long>>>
        q;
    q.push(std::make_pair(0, r));
    while (!q.empty()) {
        std::pair<long long, long long> hoge = q.top();
        long long d = hoge.first;
        long long t = hoge.second;
        q.pop();
        if (d < dist[t]) {
            dist[t] = d;
            for (auto huga : edges[t]) {
                long long l = huga.first;
                long long u = huga.second;
                if (dist[u] > d + l) {
                    q.push(std::make_pair(d + l, u));
                }
            }
        }
    }

    for (long long d : dist) {
        if (d == inf)
            std::cout << "INF" << std::endl;
        else
            std::cout << d << std::endl;
    }
}


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

int main() {
    string s;
    cin >> s;
    int change = 0;
    for (size_t i = 1; i < s.length(); i++) {
        if (s.at(i - 1) != s.at(i)) {
            change++;
        }
    }
    cout << change << endl;
    return 0;
}


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

int main(){
  int A , B , C , D ;
  cin >> A >> B >> C >> D ;
  
  if ( A + B > C + D ){
    cout << "Left" << endl;
  }
  else if ( A + B == C + D ){
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int s_int(string s){
    return atoi(s.c_str());
}
int main(){
    cout << fixed << setprecision(10);
    string s,t;
    cin >> s >> t;
    rep(i, s_int(s+t)){
        if(i*i == s_int(s+t)){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3580
#include <stdio.h>
#include <string.h>

int is_substr(char s[], char t[], int i){
    int flag = 1;

    if(s[i] == '\0') flag = 0;

    for(int j = 0; j < strlen(t); ++j, ++i){
        if(s[i] != t[j]){
            flag = 0;
            break;
        }
    }

    return flag;
}

int main(){
    char s[100010];
    int dp[100010] = {0};
    char t[4][8]={"dream","dreamer","erase","eraser"};

    scanf("%s", s);

    dp[0] = 1;
    for(int i = 0; i < strlen(s); ++i){
        if(dp[i] == 0) continue;
        for(int j = 0; j < 4; ++j){
#if 0
            int k = 0;
            int flag = 1;
            while(t[j][k] != '\0'){
                if(s[i + k] != t[j][k]){
                    flag = 0;
                    break;
                }
                k++;
            }
#endif
            if(is_substr(s, t[j], i) == 1) dp[i + strlen(t[j])] = 1;
        }
    }

    puts(dp[strlen(s)] ? "YES" : "NO");

    return 0;
}

Measured memory_bytes: 2148
/* author   : mpily :-()
    title : Competing.cpp
    time :Fri Apr 10 17:19:34 2020
     
    */
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll mod = 1e9+7;
    int dp[4002][3];//dp[i][0] = number of R.. [i][1] number of B...[i][2] number of G
    int main(){
    	ios_base::sync_with_stdio(0);
    	cin.tie(0);
    	int n;
    	string s;
    	map<char,int>nums;
    	nums['R'] = 0;
    	nums['B'] = 1;
    	nums['G'] = 2;
    	cin >> n >> s;
    	dp[0][0] = 0;
    	dp[0][1] = 0;
    	dp[0][2] = 0;
    	for(int i = 0; i < n; ++i){
    		if(i){
    			dp[i][0] = dp[i-1][0];
    			dp[i][1] = dp[i-1][1];
    			dp[i][2] = dp[i-1][2];
    		}
    		dp[i][nums[s[i]]]+=1;
    	}
    	long long ans = 0;
    	for(int i = 0; i < n; ++i){
    		for(int j = i+1; j < n; ++j){
    			if(s[i] == s[j])continue;
    			int tot = 'R'+'G'+'B';
    			tot-=s[i];
    			tot-=s[j];
    			char a = tot;
    			ans+=(dp[n-1][nums[a]] - dp[j][nums[a]]);
    			if(j + j-i< n &&  s[j+j-i] == a)ans-=1;
    		//	cout<<"at position "<<i<<" "<<s[i]<<" "<<s[j]<<" :: "<<a<<" "<<dp[n-1][nums[a]] - dp[j][nums[a]]<<"\n";
    		}
    	}
    	cout<<ans<<"\n";
    	return 0;
    }

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

#define debug(x) cout << #x << " = " << x << endl;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define FOR(it, b, e) for (typeof(b) it = (b); it != (e); ++it)
#define MSET(c, v) memset(c, v, sizeof(c))

const int INF = 0x3F3F3F3F; 
const int NEGINF = 0xC0C0C0C0;
const int NULO = -1;
const double EPS = 1e-10;
const ll mod = 1e9 + 7;

inline int cmp(double x, double y = 0) 
{  
  if(fabs(x - y) < EPS)
    return 0;
  return x > y ? 1 : -1;
}

pair<ll, ll> fix(ll A,ll B)
{
	if(A == 0)
    return {0,1};
	if(B == 0)
    return {1,0};
	
	ll g = __gcd(abs(A),abs(B));
	A /= g;
	B /= g;
	
  if(B < 0)
  {
		A *= -1;
		B *= -1;
	}
	return {A,B};
}


const int maxn = 2e5 + 10;
ll poww[maxn];
ll a[maxn], b[maxn];
map<pair<ll,ll>, int>mapa;



int main()
{
  ios::sync_with_stdio(0);
  poww[0] = 1;
  for(int i = 1; i < maxn; i++)
  {
    poww[i] = (2*poww[i-1]) % mod;
  }

  int n;
  cin >> n;
  int justZeros = 0;
  
  for(int i = 1; i <= n ; i++)
  {
    cin >> a[i] >> b[i];
    if(a[i] == 0 && b[i] == 0)
    {
      justZeros++;
    }
    else
    {
      mapa[fix(a[i], b[i])]++;
    }
  }
  
  ll ans = 1; 
  for(auto &p : mapa)
  {
    auto complement = fix(-p.first.second, p.first.first);
    if(!mapa.count(complement))
    {
      ans = (ans * poww[p.second]) % mod;
    }
    else if(p.first <= complement)
    {
      ll val = (poww[mapa[complement]] + poww[p.second] - 1) % mod;
      ans = (ans * val) % mod;
    }
  }
  ans += justZeros;
  ans--;
  ans += mod;
  ans %= mod;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 20708
#include <stdio.h>

#define MAX(x,y) (((x)>(y))?(x):(y))
#define MIN(x,y) (((x)<(y))?(x):(y))

int a[100000];
long long int max;

int main(){
  int n, k, i;
  long long int ac, bc, z;
  scanf("%d%d", &n, &k);
  for(i=0;i<n;i++){
    scanf("%d", a+i);
    max += MAX(a[i], 0);
  }

  ac = bc = 0;
  for(i=0;i<k;i++){
    ac+=MAX(a[i], 0);
    bc+=a[i];
  }

  z = ac-MAX(bc, 0);
  for(;i<n;i++){
    ac+=MAX(a[i], 0) - MAX(a[i-k], 0);
    bc+=a[i] - a[i-k];
    z = MIN(z, ac - MAX(bc, 0));
  }

  printf("%lld\n", max - z);

  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 998244353;

vector<long long int> inverse;
vector<long long int> f, f_inverse;

void factorial_Initialize(int max){
    vector<long long int> a(max+1,1);
    inverse = a;
    f = a;
    f_inverse = a;

    for (int i=2; i<=max; i++){
        inverse[i]   = MOD - inverse[MOD % i] * (MOD / i) % MOD;
        f[i]         = f[i-1]         * i          % MOD;
        f_inverse[i] = f_inverse[i-1] * inverse[i] % MOD;
    }
}

long long int nCr(int n, int r){
    if(n < r || r < 0) return 0;
    if (n >= f.size()){
        factorial_Initialize(n);
    }
    return f[n] * f_inverse[r] % MOD * f_inverse[n-r] % MOD;
}

long long int modpow(long long int b, long long int p){
    long long int num = 1, power = b;
    for(int i=0; i<=30; i++){
        if((p>>i) & 1){
            num *= power;
            num %= MOD;
        }

        power *= power;
        power %= MOD;
    }
    return num;
}

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

    vector<pair<int,int>> d(n);
    vector<long long int> depth(n);
    for(int i=0; i<n; i++){
        cin >> d[i].first;
        d[i].second = i;
        depth[d[i].first] += 1;
    }
    sort(d.begin(),d.end());
    //for(int i=0; i<n; i++) cout << d[i].first << " " << d[i].second << endl;

    if(d[0].first != 0 || d[0].second != 0 || d[1].first == 0){
        cout << 0 << endl;
        return 0;
    }

    bool flag = true;
    long long int ans = 1;
    for(int i=1; i<n; i++){
        if(flag == false && depth[i] != 0){
            cout << 0 << endl;
            return 0;
        }
        ans *= modpow(depth[i-1], depth[i]);
        ans %= MOD;
        if(depth[i] == 0) flag = false;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int n; cin >> n;
    map<string,int> mp;
    rep(i,n){
        string s; cin >> s;
        mp[s]++;
    }
    int Max = 0;
    for(auto itr=mp.begin();itr!=mp.end();++itr){
        Max = max(Max,itr->second);
    }
    for(auto itr=mp.begin();itr!=mp.end();++itr){
        if(itr->second == Max){
            cout << itr->first << endl;
        }
    }
    return 0;
}

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

int main() {
  int N;
  cin >> N ;
  if ((N / 1000) == ((N % 1000) / 100) && ((N % 1000) / 100) == (((N % 1000) % 100) / 10) || ((N % 1000) / 100) == (((N % 1000) % 100) / 10) && (((N % 1000) % 100) / 10) == (((N % 1000) % 100) % 10)){
    cout << "Yes" << endl;
  }else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,A;
  
  cin >> N;
  N--;
  vector<int> num(N);
  for (int i = 0 ; i < N; i++) cin >> num.at(i);
  cin >> A;
  
  vector<vector<uint64_t>> dp(N + 1, vector<uint64_t>(21, 0));
  dp.at(1).at(num.at(0)) = 1;
  
  for (int i = 1; i < N; i++) {
    int n = num.at(i);
    for (int j = 0; j <= 20; j++) {
      if (j - n >= 0) {
        if ( dp.at(i).at(j-n) ) {
          dp.at(i+1).at(j) += dp.at(i).at(j-n);
        }
      }
      if (j + n <= 20) {
        if ( dp.at(i).at(j+n) ) {
          dp.at(i+1).at(j) += dp.at(i).at(j+n);
        }
      }
    }
  }
  cout << dp.at(N).at(A) << endl;
  
  return 0;
}


Measured memory_bytes: 3100
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<list>
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int,int> P;
#define S second
#define F first
struct Rect{
  int x1,y1,x2,y2;
  Rect(){}
  Rect(int x1,int y1,int x2,int y2) : x1(x1),y1(y1),x2(x2),y2(y2) {}
  bool operator < (const Rect& oth)const{
    if(y2 == oth.y2){
      return y1 < oth.y1;
    }
    return y2 < oth.y2;
  }
};
struct Act{
  int up,down;
  Act(){}
  Act(int up,int down) : up(up),down(down) {}
};
int N,R;
Rect S[10002];
vector<Act> A[10002];
int main(){
  while(1){
    scanf("%d %d",&N,&R);
    if(!N && !R) break;
    int minx=100000,maxx=0;
    for(int i=0;i<N;i++){
      scanf("%d %d %d %d",&S[i].x1,&S[i].y1,&S[i].x2,&S[i].y2);
      minx = min(S[i].x1,minx); maxx = max(S[i].x2,maxx);
    }
    sort(S,S+N);
    for(int i=N-1;i>-1;i--){
      //      printf("%d %d %d %d\n",S[i].x1,S[i].y1,S[i].x2,S[i].y2);
      for(int x = S[i].x1; x < S[i].x2; x++){
	if(A[x].empty()){
	  A[x].push_back(Act(S[i].y2,S[i].y1));
	} else {
	  int dw = A[x].back().down;
	  if(dw > S[i].y2){
	    A[x].push_back(Act(S[i].y2,S[i].y1));
	  } else if ( dw > S[i].y1 )
	    A[x].back().down = S[i].y1;
	}
      }
    }
    int res1=0;
    int res2=0;
    int sump=0;
    for(int i=0;i<(int)A[minx].size();i++){
      res1 += (A[minx][i].up - A[minx][i].down);
      res2 += (A[minx][i].up - A[minx][i].down);
    }
    sump = res2;
    res2 += (int)A[minx].size() * 2;
    for(int i=minx+1; i<=maxx; i++){
      int l=0;
      int sumk=0;
      int sumn=0;
      //      printf("%d %d\n",res1,res2);
      for(int j=0;j<(int)A[i].size();j++){
	res1 += (A[i][j].up - A[i][j].down);
	sumn += (A[i][j].up - A[i][j].down);
	bool f=false;
	do{
	  f=false;
	  if(A[i-1][l].up == A[i][j].up){
	    if(A[i-1][l].down >= A[i][j].down){
	      sumk += (A[i-1][l].up - A[i-1][l].down);
	      f=true;
	    }else{
	      sumk += (A[i][j].up - A[i][j].down);
	    }
	  } else if(A[i-1][l].up > A[i][j].up && A[i][j].up > A[i-1][l].down){
	    if(A[i-1][l].down == A[i][j].down){
	      sumk += (A[i][j].up-A[i][j].down);
	      f=true;
	    }else if(A[i-1][l].up > A[i][j].down && A[i][j].down > A[i-1][l].down){
	      sumk += (A[i][j].up - A[i][j].down);
	    } else{
	      sumk += (A[i][j].up - A[i-1][l].down);
	      f=true;
	    }
	  } else if(A[i][j].up > A[i-1][l].up && A[i-1][l].up > A[i][j].down){
	    if(A[i-1][l].down == A[i][j].down){
	      sumk += (A[i-1][l].up - A[i-1][l].down);
	      f=true;
	    }else if(A[i][j].up > A[i-1][l].down && A[i-1][l].down > A[i][j].down){
	      sumk += (A[i-1][l].up - A[i-1][l].down);
	      f=true;
	    } else {
	      sumk += (A[i-1][l].up - A[i][j].down);
	    }
	  } else if(A[i-1][l].down >= A[i][j].up) f=true;
	  if(f) l++;
	} while(f && l < (int)A[i-1].size());
      }
      res2 += (sump - sumk);
      res2 += (sumn - sumk);
      res2 += (int)A[i].size()*2;
      sump = sumn;
    }
    printf("%d\n",res1);
    if(R==2) printf("%d\n",res2);

    for(int i=minx; i<=maxx; i++) A[i].clear();
  }
}


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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
 
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
 
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
 
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(long long N, long long K, std::string S){
    if(S[K-1] == 'A') S[K-1] = 'a';
    if(S[K-1] == 'B') S[K-1] = 'b';
    if(S[K-1] == 'C') S[K-1] = 'c';

    cout << S << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::string S;
    std::cin >> S;
    solve(N, K, S);
    return 0;
}


Measured memory_bytes: 256
S=str(input())
Q=int(input())
which=0
front=""
back=""
for i in range(Q):
    a=list(map(str,input().split()))
    if a==["1"]:
        which+=1
        which%=2
        continue
    else:
        if which==0:
            if a[1]=="1":
                front=a[2]+front
            if a[1]=="2":
                back+=a[2]
        if which==1:
            if a[1]=="1":
                back+=a[2]
            if a[1]=="2":
                front=a[2]+front
S=front+S+back
if which==1:
    print(S[::-1])
if which==0:
    print(S)

Measured memory_bytes: 4640
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

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

fn main() {
    input! {
        a: i32,
        b: i32
    }
    let ans = std::cmp::max(a - b * 2, 0);
    println!("{}", ans);
}


Measured memory_bytes: 4352