akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define fi first
#define se second
#define co(a) cout<<a<<endl
#define sz size()
#define bgn begin()
#define en end()
#define pb(a) push_back(a)
#define pop pop_back
#define V vector
#define P pair
#define V2(a,b,c) V<V<int>> a(b,V<int>(c))
#define V2a(a,b,c,d) V<V<int>> a(b,V<int>(c,d))
#define incin(a) int a; cin>>a
//#define min min<int>
//#define max max<int>
template<class T>
 void cou(vector<vector<T>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}
/*template<>
 void cou(vector<vector<char>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}*/
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
 bool prime(int a){
   if(a<2)
     return false;
   else if(a==2)
     return true;
   else if(a%2==0)
     return false;
   double b=sqrt(a);
    for(int i=3;i<=b;i+=2){
      if(a%i==0){
        return false;
      }
    }
   return true;
 }
struct Union{
  vector<int> par;
  Union(int n){
	par= vector<int>(n, -1);
  }
  int find(int x){
    if(par[x]<0)
      return x;
    else
      return par[x]=find(par[x]);
  }
  bool same(int a,int b){
    return find(a)==find(b);
  }
  int Size(int a){
    return -par[find(a)];
  }
  void unite(int a,int b){
    a=find(a);
    b=find(b);
    if(a==b)
      return;
    if(Size(b)>Size(a))
      swap<int>(a,b);
    par[a]+=par[b];
    par[b]=a;
  }
};
int ketas(int a){
  string b=to_string(a);
  int c=0;
  fo(i,keta(a)){
    c+=b[i]-'0';
  }
  return c;
}
/*struct aa{
	vector<int> gt;
  aa(int n){
	gt= vector<int>(n, 1);
  }
	void c(V<int> d,int b){
	if(d[b]==0){
		gt[d[b]-1]++;
		gt[gt.sz-1]++;
	}
	else{
		gt[d[b]-1]++;
		c(d,d[d[b]]-1);
	}
}
void cok(int a){
	cout<<gt[a-1]<<endl;
	fo(i,a-1)
	cout<<gt[i]<<endl;
}
};
*/
signed main(){
	int a,b;
	cin>>a>>b;
	string c;
	cin>>c;
	c[b-1]+=32;
	cout<<c<<endl;
}


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

#define ll long long
#define ld long double
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define sz(x) ((int)(x).size())

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
int main()
{
    char alpha;
    cin >> alpha;
    char ans;
    ans = alpha + 1;
    cout << ans << endl;
}

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

int main(){
  int i,j,k,cnt;
  int n;
  cin>>n;
  int a[n],b[n];
  for(i=0;i<n;i++)cin>>a[i];
  for(i=0;i<n;i++)cin>>b[i];
  int ma=0,sum;
  for(i=0;i<n;i++){
    sum=0;
    for(j=0;j<=i;j++){
      sum+=a[j];
    }
    for(j=i;j<n;j++){
      sum+=b[j];
    }
    ma=max(ma,sum);
  }
  cout<<ma;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if ((A <= C && C <= B) || (B <= C && C <= A)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    if not (a % 3 and b % 3 and (a + b) % 3):
        print("Possible")
    else:
        print("Impossible")
    return

#B
def B():
    k, n = LI()
    l = LI()
    l.sort(reverse = True)
    print(sum(l[:n]))
    return

#C
def C():
    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    B()


Measured memory_bytes: 38512
// J'aime
// Chemise Blanche

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  int h, a;
  cin >> h >> a;
  cout << (h + a - 1) / a << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define zzz ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b){return (a*b)/gcd(a, b);}

int main()
{
    zzz;
    int n,d;
    cin>>n>>d;
    cout<< (n%(2*d+1)==0? n/(2*d+1) : n/(2*d+1) + 1);
}


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


int main(){
  int n;
  cin >> n;
  bool ans=false;
    for(int i=0;i<9;i++){
      for(int j=0;j<9;j++){
        if((i+1)*(j+1)==n){
          ans = true;
        }
      }
    }
  if(ans){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  
    
}
      


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <numeric>
using namespace std;

int abs(int num){
   if (num > 0)
      return num;
   else
      return -num;
}

int main(){
  string A,B;
  cin >> A >> B;
  cout << 'A' << B.at(0) << 'C' << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {

  string str;
  cin >> str;
  
  if(str.at(2)==str.at(3) && str.at(4)==str.at(5)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
int a[110][110],n,m;
int dx[8]={0,0,1,1,1,-1,-1,-1};
int dy[8]={1,-1,1,-1,0,1,-1,0};
int main()
{
	scanf("%d%d",&n,&m);
	if (n>m) swap(n,m);

	if (m<=2)
	{
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
			{
				int nx,ny;
				for (int k=0;k<8;k++)
					nx=i+dx[k],ny=j+dy[k],a[nx][ny]++;
			}
		int ans=0;
		for (int i=1;i<=n;i++)
		{
			for (int j=1;j<=m;j++) if ((a[i][j]&1)==0) ans++;
			//printf("%d ",a[i][j]+1);printf("\n");
		}
		printf("%d",ans);
		return 0;
	}
	if (n==1) printf("%d",m-2);
	else if (n==2) printf("%d",0);
	else printf("%lld",1ll*(n-2)*(m-2));
} 

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  int N; cin >> N; vector<int> D(N);
  for(int i = 0; i < N ; i++){
    cin >> D[i];}
  
  sort(D.begin(),D.end());
  int ite = 1; int cnt = 1;
  while( ite < N){
    if( ite < N && D[ite - 1] != D[ite]){cnt++;}
    ite++;}
  
  cout << cnt << endl;
  
  return 0;}


Measured memory_bytes: 256
import math
A, B = input().split()
A = int(A)

if A == 0 or B == '0.00':
    ans = 0
else:
    ans = A*int(B[0])*100 + A*int(B[2])*10 + A*int(B[3])
    ans = str(ans)
    if len(ans)-2 <= 0:
        ans = 0
    else:
        ans = ans[0:len(ans)-2]
print(ans)

Measured memory_bytes: 9192
#include <stdio.h>

void sorting(int *x, int *y){

	int temp;

	if(*x > *y){
		temp = *x;
		*x = *y;
		*y = temp;
	}
}

int main(void){

	int a, b, c;

	scanf("%d%d%d",&a,&b,&c);
	
	sorting(&a, &b);
	sorting(&b, &c);
	sorting(&a, &b);
	
	printf("%d %d %d\n", a, b, c);
	
	return 0;

}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int h,w;
  cin >> h >> w;
  vector<string> a(h);
  rep(i,0,h) cin >> a[i];
  vector<bool> r(h,false), c(w,false);
  rep(i,0,h) {
    rep(j,0,w) {
      if (a[i][j] == '#') r[i] = true;
    }
  }
  rep(j,0,w) {
    rep(i,0,h) {
      if (a[i][j] == '#') c[j] = true;
    }
  }
  rep(i,0,h) {
    if (!r[i]) continue;
    rep(j,0,w) {
      if (c[j]) cout << a[i][j];
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <utility>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
typedef long long int ll;

int main() {
  string S,T;
  cin>>S>>T;
  
  cout<<T+S<<endl;
}


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

#pragma region template


// -type-
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vs = vector<string>;


// -const-
const ll MOD = 1000000007;

const string YES = "No";

const string NO = "No";

const ll MAX = (ll)0x3f0000003f000000;
const double EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1},
          dy[] = {1, 0, -1, 0, 1, -1, -1, 1};


// -define-
#define F first
#define S second

#define reps(i, k, n) for (int i = (k), i##_len = (n); i < i##_len; ++i)
#define rep(i, n) reps(i, 0, n)
#define all(o) begin(o), end(o)
#define sz(a) ((int)(a).size())
#define debug(x) cerr << x << " (L:" << __LINE__ << ")" << '\n';


// -functions-

inline bool in(string s, string c) {
    return (s.find(c) != string::npos);
}
inline bool in(string s, char c) {
    return (s.find(c) != string::npos);
}

template <class T>
void print(T& x) {
    cout << x << '\n';
}

struct setup_main {
    setup_main() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(15);
    }
} setup_main_;

#pragma endregion

ll ans = 0;

signed main() {
    ll N;
    cin >> N;
    vl a(N, 0);
    for (auto&& i : a) {
        cin >> i;
        if (i % 2 == 0 and i % 3 != 0 and i % 5 != 0) {
            ans = 1;
        }
    }
    if (ans==1)
        cout << "DENIED" << endl;

    else
        cout << "APPROVED" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int ara[4][4];
int main()
{
    int a,b,c,i,j,t,flag=0;

    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            cin>>ara[i][j];
        }
    }
    cin>>t;
    int ara1[t];
    for(i=0;i<t;i++)
        cin>>ara1[i];
    for(int k=0;k<t;k++)
    {
     for(i=0;i<3;i++)
       {
        for(j=0;j<3;j++)
        {
          if(ara1[k]==ara[i][j])
          {
              ara[i][j]=-1;
          }
        }
    }
    }
    if(ara[0][0]==-1&&ara[0][1]==-1&&ara[0][2]==-1)
        flag=1;
    else if(ara[1][0]==-1&&ara[1][1]==-1&&ara[1][2]==-1)
        flag=1;
    else if(ara[2][0]==-1&&ara[2][1]==-1&&ara[2][2]==-1)
        flag=1;
    else if(ara[0][0]==-1&&ara[1][0]==-1&&ara[2][0]==-1)
        flag=1;
    else if(ara[0][1]==-1&&ara[1][1]==-1&&ara[2][1]==-1)
        flag=1;
    else if(ara[0][2]==-1&&ara[1][2]==-1&&ara[2][2]==-1)
        flag=1;
    else if(ara[0][0]==-1&&ara[1][1]==-1&&ara[2][2]==-1)
        flag=1;
    else if(ara[0][2]==-1&&ara[1][1]==-1&&ara[2][0]==-1)
        flag=1;
    //cout<<ara[0][0]<<" "<<ara[1][1]<<"\n";
    if(flag)
        cout<<"Yes"<<"\n";
    else
        cout<<"No"<<"\n";
return 0;
}


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

int main()
{
    int n, a[100];

    while( cin >> n )
    {
        if( n == 0 )
            break;
        for( int i = 0; i < n; i++ )
            cin >> a[i];

        int min = 10000000, max = -1, sum = 0;
        for( int i = 0; i < n; i++ )
        {
            if( min > a[i] )
                min = a[i];
            if( max < a[i] )
                max = a[i];
            sum += a[i];
        }
        cout << ( sum - min - max ) / ( n - 2 ) << endl;
    }
    return 0;
}



Measured memory_bytes: 3008
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#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 map<T,U>& mp){ os << "{"; for(auto& p : mp){ os << p << ","; } 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; }
using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int,int>;
using vi = std::vector<int>;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
//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};
/*}}}*/

int main(){
    int N; cin >> N;
    map<int,int> cnt;
    for(int i=2;i<=N;i++){
        auto v = i;
        for(int j=2;j<=v;j++){
            while(v%j==0){
                cnt[j]++;
                v /= j;
            }
        }
    }

    ll ans = 0;

    // 75
    for(const auto& p : cnt){
        if(p.second >= 74){
            ans++;
        }
    }

    // 3 x 25
    for(const auto& p1 : cnt){
        for(const auto& p2 : cnt){
            if(p1 == p2) continue;
            if(p1.second >= 2 && p2.second >= 24){
                ans++;
            }
        }
    }

    // 5 x 15
    for(const auto& p1 : cnt){
        for(const auto& p2 : cnt){
            if(p1 == p2) continue;
            if(p1.second >= 4 && p2.second >= 14){
                ans++;
            }
        }
    }

    // 3 x 5 x 5
    for(const auto& p1 : cnt){
        for(const auto& p2 : cnt){
            for(const auto& p3 : cnt){
                if(p1 == p2 || p1 == p3 || p2 == p3) continue;
                if(p2.first >= p3.first) continue;
                if(p1.second >= 2 && p2.second >= 4 && p3.second >= 4){
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

string s;

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> s;
	int n = s.size();
	for (int i = n/2-1; i >= 0; i--) {
		if (s.substr(0, i) == s.substr(i, i)) {
			cout << 2*i << endl;
			return 0;
		}
	}
	cout << 0 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 7, M =  998244353;
int n, m;
string a, b;
int main() {
	cin >> n >> m;
	cin >> a >> b;
	int g = __gcd(n, m);
	ll x = n * 1LL * m;
	x /= g;
	int add1 = x / m, add2 = x / n;
	int i = 0, j = 0;
	while (i < n && j < m) {
		if (a[i] != b[j]) {
			return puts("-1"), 0;
		}
		i += add1;
		j += add2;
	}
	cout << x << endl;


}

Measured memory_bytes: 512
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt();
		int m = stdIn.nextInt();
		if(n==m) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
		
		
		
		
	}

}


Measured memory_bytes: 21844
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader bfr= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(bfr.readLine());
		int R = Integer.parseInt(str.nextToken());
		double answer = 2*(3.141592)*R;
		System.out.println(answer);
	}

}


Measured memory_bytes: 33268
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy
 
## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))
 
N=int(input())
A= list(map(int, input().split()))

four = 0
two = 0
one = 0

for i in range(N):
    if A[i]%4 == 0:
        four += 1
    elif A[i]%2 == 0:
        two += 1
    else:
        one += 1

if one == 0:
    print('Yes')
elif two > 0:
    if four >= one:
        print('Yes')
    else:
        print('No')
else:
    if four >= one - 1:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 90980
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	int h, w;

	cin>>h>>w;

	rep(i, w+2){
		cout<<"#";
	}
	cout<<endl;

	rep(i, h){
		cout<<"#";
		rep(j, w){
			char s;
			cin>>s;
			cout<<s;
		}
		cout<<"#"<<endl;
	}

	rep(i, w+2){
		cout<<"#";
	}
	cout<<endl;

}

Measured memory_bytes: 256
N = int(input())
T,A = map(int,input().split())
best = float("inf")
bestidx = 1

H = [float(i) for i in input().split()]

index = 1
for i in H:
    cantidate = abs(A - (T - i * 0.006))
    if cantidate < best:
        bestidx = index
        best = cantidate
    index += 1
print(bestidx)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <iomanip>
#include <set>
using namespace std;

typedef long long ll;
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define SORT(s) sort((s).begin(),(s).end())

int main(){
    ll N; cin >> N;
    vector<ll> A(N); REP(i,N) cin >> A[i];

    ll ans = *max_element(A.begin(),A.end()) - *min_element(A.begin(),A.end());
    cout << ans << endl;
}


Measured memory_bytes: 3648
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
A.sort()
BC = []
for _ in range(M):
    BC.append(inpl())
BC.sort(key=lambda x: -x[1])
t = 0
S = 0
for B,C in BC:
    f = t
    t = f + B
    if t > N:
        t = N
    if f >= N:
        break
    if C >= A[t-1]:
        S += (t-f)*C
    else:
        for i in range(f,t):
            if C >= A[i]:
                S += C
            else:
                t = i
                break
        break
if t < N:
    S += sum(A[t:])
print(S)

Measured memory_bytes: 82456
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define FORSTEP(i, start, end, step) for (int i = start; i < end; i += step)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1000000007
typedef long long ll;
const int INF32 = 2147483647;
const ll INF64  = 9223372036854775807;
using namespace std;

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

    string S;
    int K;
    cin >> S >> K;

    REP(i, min((int)S.size(), K)) {
        if (S[i] > '1') {
            cout << S[i] << endl;
            return 0;
        }
    }

    cout << '1' << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#define M 5070721
#define NIL (-1)
#define L 14
typedef long long ll;
char H[M][L];

int getChar(char ch){
	if(ch=='A')return 1;
	else if(ch=='C')return 2;
	else if(ch=='G')return 3;
	else if(ch=='T')return 4;
	else return 0;
}

ll getKey(char str[]){
	ll sum=0,p=1,i;
	int len=strlen(str);
	for(i=0;i<len;i++){
		sum+=p*(getChar(str[i]));
		p*=5;
	}
	return sum;
}

int h1(int key){
	return key%M;
}

int h2(int key){
	return 1+(key%(M-1));
}

int find(char str[]){
	ll key,i,h;
	key=getKey(str);
	for(i=0;;i++){
		h=(h1(key)+i*h2(key))%M;
		if(strcmp(H[h],str)==0)return 1;
		else if(strlen(H[h])==0)return 0;
	}
	return 0;
}

int insert(char str[]){
	ll key,i,h;
	key=getKey(str);
	for(i=0;;i++){
		h=(h1(key)+i*h2(key))%M;
		if(strcmp(H[h],str)==0)return 1;
		else if(strlen(H[h])==0){
			strcpy(H[h],str);
			return 0;
		}
	}
	return 0;
}


int main(void){
	int n;
	char str[L],com[9];
	for(int i=0;i<M;i++){
		H[i][0]='\0';
	}
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%s %s",com,str);
		if(com[0]=='i'){
			insert(str);
		}else{
			if(find(str)){
				printf("yes\n");
			}else{
				printf("no\n");
			}
		}
	}
	return 0;
}



Measured memory_bytes: 72000
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <string>
#include <iostream>


using namespace std;
int main()
{
	long long n, m;
	cin >> n >> m;
	if (n < 2 && m < 2) {
		cout << 1 << endl;
		return 0;
	}

	if (n < 2 || m < 2) {
		int mx = max(n, m);
		cout << mx - 2 << endl;
		return 0;
	}

	cout << n * m - (2 * n + 2 * m - 4) << endl;
	return 0;
}


Measured memory_bytes: 256
a = list(input())
b = list(input())
c = list(input())
st = a.pop(0)
while True:
    if st == 'a':
        if a == []:
            print('A')
            break
        else:
            st = a.pop(0)
    elif st == 'b':
        if b == []:
            print('B')
            break
        else:
            st = b.pop(0)
    else:
        if c == []:
            print('C')
            break
        else:
            st = c.pop(0)

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

N, K = map(int, input().split())
h_list = [int(input()) for i in range(N)]

h_list.sort()
best = 1000000000
for i in range(N - K + 1):
    #diff = h_list[i:i+K][-1] - h_list[i:i+K][0]
    diff = h_list[i+K-1] - h_list[i]
    if diff < best:
        best = diff

print (best)

Measured memory_bytes: 7384
#include <iostream>
using namespace std;
int a[110];
int main(){
  int n,m;
  cin>>n>>m;
  int s=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
    s+=a[i];
  }
  int ans=0;
  for (int i=0;i<n;++i){
    if(a[i]*4*m>=s){
      ans+=1;
    }
  }
  
  if(ans>=m) cout<<"Yes";
  else cout<<"No";

  
  
      
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Stack;

class Main {

    public static void main(String[] args) {
        new Main().compute();
    }

    void compute() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N * (N + 1) / 2);
    }
}


Measured memory_bytes: 21972
s = input()
t = input()

max = 0

for i in range(len(s)-len(t)+1):
    count = 0
    for j in range(len(s[i:i+len(t)])):
        if s[i:i+len(t)][j] == t[j]:
            count+=1
    if max<count:
        max = count
print(len(t)-max)

Measured memory_bytes: 8928
if __name__ == "__main__":
    a = int(input())
    left = 0
    right = 1 << 50
    while (right - left > 1):
        med = (right + left) // 2
        if (med * (med + 1) >= 2 * a):
            right = med
        else:
            left = med
    print (right)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, INF = 0x3f3f3f3f;
inline int read() {
	int x = 0, f = 0; char ch = 0;
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
int head[N], tot = 0;
struct edge {
	int to, nxt;
}e[N];
int f[N], g[N], pre[N], suf[N], p[N], ans[N], m;
int n, x, y;
inline void addedge(int x, int y) {
    e[++tot].to = y, e[tot].nxt = head[x], head[x] = tot;
}
void dfs(int x, int fa) {
    int cnt = 0;
    f[x] = 1;
    for (int i = head[x]; i; i = e[i].nxt) {
    	int y = e[i].to;
    	if (y != fa) {
    		dfs(y, x); f[x] = f[x] * f[y] % m;
    	}
    }
    for (int i = head[x]; i; i = e[i].nxt) {
    	int y = e[i].to;
        if (y != fa) p[++cnt] = y;
    }
    f[x]++, f[x] %= m;
    pre[0] = suf[cnt + 1] = 1;
    for (int i = 1; i <= cnt; i++) pre[i] = pre[i - 1] * f[p[i]] % m;
    for (int i = cnt; i >= 1; i--) suf[i] = suf[i + 1] * f[p[i]] % m;
    for (int i = 1; i <= cnt; i++) g[p[i]] = pre[i - 1] * suf[i + 1] % m;
}
void dfs2(int x, int fa) {
    if (x == 1) ans[x] = 1;
    else ans[x] = (g[x] * ans[fa] + 1) % m;
    for (int i = head[x]; i; i = e[i].nxt) {
    	int y = e[i].to;
    	if (y != fa) dfs2(y, x);
    }
}
signed main() {
    n = read(), m = read();
    for (int i = 1; i < n; i++) {
    	int x = read(), y = read();
        addedge(x, y), addedge(y, x);
    }
    dfs(1, 0); dfs2(1, 0);
    for (int i = 1; i <= n; i++) printf("%lld\n", ans[i] * (m + f[i] - 1) % m);
    return 0;
}

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

int main() {
  int A[20][20];
  int B[20];
  int N, M, C;
  cin >> N >> M >> C;
  for (int j{}; j < M; ++j)
    cin >> B[j];
  int ans{};
  for (int i{}; i < N; ++i) {
    int sum{};
    for (int j{}; j < M; ++j) {
      cin >> A[i][j];
      sum += A[i][j] * B[j];
    }
    sum += C;
    if (sum > 0)
      ++ans;
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next();
		String t = sc.next();
		
		char[] S = s.toCharArray();
		char[] T = t.toCharArray();
		
		int c = 0;
		
 		for(int i = 0; i < s.length(); i++) {
 			if(S[i] != T[i]) c += 1;
		}
		
 		System.out.println(c);
	}
}

Measured memory_bytes: 32712
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n = ri()
a = [ri() for _ in range(n)]
idx = 1
cnt = 1
if a[0] == 2:
    print(1)
    exit()
while idx != -1:
    a[idx-1], idx = -1, a[idx-1]
    cnt += 1
    if a[idx-1] == 2:
        print(cnt)
        exit()
print(-1)












Measured memory_bytes: 30920
H,N = map(int, input().split())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

INF = float("inf")
dp = [[INF for _ in range(H+1)] for _ in range(N+1)]
dp[0][0] = 0

# 個数制限なしナップザック
for i in range(N):
    for j in range(H+1):
        if A[i] > j:
            # オーバーキルも可能なので。
            dp[i+1][j] = min(dp[i][j], B[i])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j - A[i]] + B[i])

print(dp[-1][-1])


Measured memory_bytes: 293768
from heapq import heappush,heappop
V,E,r = map(int,input().split())
edges = [[] for _ in range(V)]
for _ in range(E):
    s,t,d = map(int,input().split())
    edges[s].append((t,d))
que = []
mindists = [float("inf")]*V
mindists[r] = 0
heappush(que,(0,r))
while que:
    ccost,cnode = heappop(que)
    if mindists[cnode] < ccost: continue
    for nnode,ncost in edges[cnode]:
        tcost = ccost+ncost
        if mindists[nnode] > tcost:
            mindists[nnode] = tcost
            heappush(que,(tcost,nnode))
print("\n".join(str(e) if e != float("inf") else "INF" for e in mindists))


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

}

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

int main(){
string A,B,ans;
cin>>A>>B;

int end = A.size();
if(A.size()>B.size())end--;
for(int i = 0;i<end;i++){
  ans.push_back(A.at(i));
  ans.push_back(B.at(i));
}
if(end!=A.size())ans.push_back(A.at(A.size()-1));


  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  int a,b;
  vector<int>ans(n);
  for(int i=0;i<m;i++){
    cin>>a>>b;
    ans[a-1]++;
    ans[b-1]++;
  }
  for(int i=0;i<n;i++){
    cout<<ans[i]<<endl;
  }
}
    

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vec vector <ll>
#define pa pair<ll,ll>
#define mp make_pair
#define pb push_back
int main()
{	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,x,y;
	cin>>n>>x>>y;
	vector<ll> arr;
	arr.resize(n+1);
	arr.assign(n,0);
	ll i,j;
	for(i=1;i<n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			ll val=min(j-i,abs(i-x)+1+abs(j-y));
			arr[val]++;
		}
	}
	for(i=1;i<=n-1;i++)
		cout<<arr[i]<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

template< typename Monoid >
struct SegmentTree{
  using F = function< Monoid(Monoid, Monoid) >;
  
  int sz;
  vector< Monoid > seg;

  const F f;
  const Monoid M1;

  //SegmentTree(n,f,M1):サイズnの初期化，fは2つの苦汗の要素をマージする二項演算，M1はモノイドの単位元
  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1){
    sz = 1;
    while(sz < n) sz<<=1;
    seg.assign(2*sz,M1);
  }

  //set(k,x):k番目の要素にxを代入
  void set(int k, const Monoid &x){
    seg[k+sz] = x;

  }
  
  //build():segTreeの構築
  void build(){
    for(int k = sz-1; k>0; --k){
      seg[k] = f(seg[2*k+0], seg[2*k+1]);
    }
  }

  //update(k,x):k番目の要素をxに変更
  void update(int k, const Monoid &x){
    k += sz;
    seg[k] = x;
    while(k>>=1) seg[k] = f(seg[2*k+0],seg[2*k+1]);
  }

  //区間[a,b)のMonoidを計算
  Monoid query(int a, int b){
    Monoid L = M1, R = M1;
    for(a += sz, b+=sz; a < b; a>>=1, b>>=1){
      if(a&1) L = f(L,seg[a++]);
      if(b&1) R = f(seg[--b],R);
    }
    return f(L,R);
  }

  //operator[k]:k番目の要素を返す
  Monoid operator[](const int &k) const{
    return seg[k+sz];
  }

};

struct edge{ int f,t; ll c;};
bool comp(const edge& l, const edge& r){
  return l.f < r.f;
}
const int VMAX = 1e5+10;
const int MMAX = 1e5+10;
const ll INF = 1e15;
int V,M;

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cin >> V >> M;
  vector<edge> v(M);
  rep(i,M) cin >> v[i].f >> v[i].t >> v[i].c;
  sort(all(v),comp);
  SegmentTree< ll > minseg(V+1, [](ll a, ll b){ return min(a,b); }, INF);
  minseg.set(1,0);
  minseg.build();
  rep(i,M){
    ll c = minseg.query(v[i].f,v[i].t);
    minseg.update(v[i].t,min(minseg[v[i].t],c+v[i].c));
  }
  if(minseg[V]==INF)cout << -1 << endl;
  else cout << minseg[V] << endl;
  return 0;
}


Measured memory_bytes: 3840
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring>
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//2-dim:vector<vector<Type>> vv(n, vector<Type>(m, d));
//3-dim:vector<vector<vector<Type>>> vvv(n, vector<vector<Type>>(m, vector<Type>(l, d)));

signed main(){
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    int d,t,s; cin >> d >> t >> s;
    if(d<=s*t) cout << "Yes" << endl;
    else cout << "No" << endl;
}




Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<int> v1(n);
    vector<int> v2(n);
    for(int i=0;i<n;i++){
        cin>>v1[i];
    }
    for(int i=0;i<n;i++){
        cin>>v2[i];
    }
    reverse(v2.begin(),v2.end());
    int c=-1;
    int l=0;
    int r=0;
    for(int i=0;i<n;i++){
        if(v1[i]==v2[i]){
          c=v1[i];
          l=i;
          break;
        }
    }
    for(int i=n-1;i>=0;i--){
         if(v1[i]==v2[i]){
           r=i;
           break;
        }
    }
    for(int i=0;i<n;i++){
       if(v1[i]!=c && v2[i]!=c && l<=r){
           swap(v2[i],v2[l]);
           l++;
       }
    }
    if(l<=r){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
         for(int i=0;i<n;i++){
            cout<<v2[i]<<" ";
        }
    }


}


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

const int MAX_M = 21;

int n, m;
vector<int> G[MAX_M];
bool used[MAX_M];
vector<int> path;

void dfs(int idx){
  used[idx] = true;
  for(int i = 0 ; i < (int)G[idx].size() ; i++){
    if(!used[G[idx][i]]) dfs(G[idx][i]);
  }
  path.push_back(idx);
}

int main(){
  cin >> m >> n;
  
  int a, b;
  bool isroot[MAX_M];
  memset(isroot, true, sizeof(isroot));
  
  for(int i = 0 ; i < n ; i++){
    cin >> a >> b;
    a--, b--;
    G[a].push_back(b);
    isroot[b] = false;
  }
  
  for(int i = 0 ; i < m ; i++){
    if(isroot[i]) dfs(i);
  }
  
  for(int i = m-1 ; i >= 0 ; i--){
    cout << path[i]+1 << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define Phuong_ ios_base::sync_with_stdio(0); cin.tie(0);

/// easy access -------------
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
typedef pair<int,int> pi;
typedef tuple<int, int, int> tp;
///-------------------------

int main()
{
    Phuong_; /// <3333
    int n;
    cin >> n;
    int ans=0;
    for(int i=1; i<=n; ++i){
        int u;
        cin >> u;
        if (i&1 && u&1) ans++;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3544
# -*- coding: utf-8 -*-
"""
A - Day of Takahashi
https://abc096.contest.atcoder.jp/tasks/abc096_a

"""
import sys
from sys import stdin
input = stdin.readline


def calc_day_of_takahashi(m, d):
    if d >= m:
        return m
    else:
        return m - 1


def main(args):
    a, b = map(int, input().split())
    ans = calc_day_of_takahashi(a, b)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


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

typedef long long int lli;
#define int lli
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<lli> vli;
typedef vector<pii> vii;

const int MOD   = 1e9 + 7;
const double PI = acos(-1.0);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
const int INF   = 1e18;

#define fastio            ios_base::sync_with_stdio(false);cin.tie(0)
#define sz(a) int((a).size())
#define rsz resize
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define f first
#define s second
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define endl "\n"
#define spc " "
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template <typename T> T lcm(T a, T b){return (a*b)/gcd(a,b); }

void solve(){

    int n, q;
    cin >> n >> q;
    
    set<pair<int, int>> se[2];
    se[0].insert({n, n});
    se[1].insert({n, n});
    long long ans = 1LL * (n - 2) * (n - 2);
    while (q--) {
        int ty, i; cin >> ty >> i;
        ty--;
        auto it = se[ty].lower_bound({i, -1});
        int k = (*it).second;
        ans -= k - 2;
        se[ty ^ 1].insert({(k - 1), i});
    }
    cout << ans << '\n';
}

signed main(){
    fastio;

    solve();

    return 0;
}



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

int main(){
  int a , b;
  char op;
  while(1){
    cin >> a >> op >> b;
    if (op == '?') break;
    if (op == '+'){
      cout << a + b << endl;
    } else if (op == '-') {
      cout << a - b << endl;
    } else if (op == '*'){
      cout << a * b << endl;
    } else if (op == '/') {
      cout << a / b << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3100
K = int(input())
if K == 7 or K == 1:
    print(1)
else:
    if K % 7 == 0:
        K //= 7
    r = 1
    for i in range(1,K+1):
        if r == 0:
            print(i)
            break
        r += pow(10,i,K)
        #print(r)
        r %= K
    else:
        print(-1)

Measured memory_bytes: 63560
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    vector<int>num(n+1,0);
    for(int i=0;i<n+1;i++){
        num[i]=i;
    }
    ll ans=0;
    for(ll i=k;i<n+2;i++){
        ll minn=i*(i-1)/2;
        ll maxn=(2*n-i+1)*i/2;
        ans+=maxn-minn+1;
        ans%=1000000007;
    }
    
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 4048
# coding: utf-8
# Your code here!

N = int(input())

s = []
t = []
for i in range(N):
    a, b = input().split()
    s.append(a)
    t.append(int(b))
X = input()

ans = 0
flg = False
for i in range(N):
    if flg:
        ans += t[i]
    if s[i] == X:
        flg = True
print(ans)

Measured memory_bytes: 3060
#include<cstdio>
#include <iostream>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
double X[25],Y[25],Z[25];
double map[25][25];
double ans;
int line[25];
int n,m;
double dd(double x,double y)
{
    if(x>y) return x-y;
    else return y-x;
}
void dfs(int x,int y)
{
    if(x>n&&y!=m) return;
    if(y==m)
    {
        double tmp=0.0;
        for(int i=1;i<m;i++)
        {
            for(int j=i+1;j<=m;j++)
            {
                tmp+=(X[line[i]]-X[line[j]])*(X[line[i]]-X[line[j]])+(Y[line[i]]-Y[line[j]])*(Y[line[i]]-Y[line[j]])+(Z[line[i]]-Z[line[j]])*(Z[line[i]]-Z[line[j]]);
            }
        }
        if(ans<tmp) ans=tmp;

        /*printf("%lf\n",tmp);*/
        return ;
    }
    line[y+1]=x;
    dfs(x+1,y+1);
    dfs(x+1,y);
    return ;
}
int main()
{

    while(~scanf("%d%d",&n,&m))
    {
        ans=0.0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf",&X[i],&Y[i],&Z[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                map[i][j]=dd(X[i],X[j])+dd(Y[i],Y[j])+dd(Z[i],Z[j]);
            }
        }
        dfs(1,0);
        printf("%lf\n",ans);
    }
    return 0;
}

Measured memory_bytes: 888
N, K = map(int,input().split())
S = input()

lst_s = list(S)
if lst_s[K-1] == 'A':
    lst_s[K-1] = 'a'
elif lst_s[K-1] == 'B':
    lst_s[K-1] = 'b'
else:
    lst_s[K-1] = 'c'

S = ''.join(lst_s)
print(S)

Measured memory_bytes: 3060
#include <stdio.h>
#include <map>
#include <utility>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
bool cmp(pair<string,int> a,pair<string,int> b){
    if(a.F.length()!=b.F.length())return a.F.length()<b.F.length();
    int now=0;
    while(true){if(a.F[now]!=b.F[now])return a.F[now]<b.F[now];
        now++;
    }
}
int main(){
    int n,temp;
    map<string,int> m;
    vector<pair<string,int>>ans;
    string s;
    scanf("%d",&n);
    while(n--){
        cin>>s>>temp;
        if(m.find(s)!=m.end())m[s]+=temp;
        else m.insert(MP(s,temp));
    }
    for(auto u:m)ans.PB(u);
    sort(ans.begin(),ans.end(),cmp);
    for(int i=0;i<ans.size();i++)cout<<ans[i].F<<" "<<ans[i].S<<endl;
}


Measured memory_bytes: 3284
object Main extends App {
    
    val sc = new java.util.Scanner(System.in)
    val _ = sc.nextInt
	val str = sc.next
    
    var left_cnt = 0
    var right_cnt = 0
    
    for (s <- str) {
        if (s == '(') {
            left_cnt = left_cnt + 1
        } else {
            if (left_cnt > 0) {
                left_cnt = left_cnt - 1
            } else {
                right_cnt = right_cnt + 1
            }
        }
    }
    
    for (_ <- 0 until right_cnt) {
        print("(")
    }
    print(str)
    for (_ <- 0 until left_cnt) {
        print(")")
    }

    println("")
}

Measured memory_bytes: 27072
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int W, a, b;
int main() {
	cin >> W >> a >> b;
	cout << max((a > b ? a - b : b - a) - W, 0) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int dp[30][512810];
int dbl[512810][30];
string s;int n;
int cal(int i,int j,int ne){
	if(dp[i][j]>ne){
		dp[i][j]=ne;return 1;
	}
	return 0;
}
int main()
{
	int q,x,y,inf=512810;
	cin>>s;
	n=s.size();
	//memset(dp,-1,sizeof(dp));memset(dbl,-1,sizeof(dbl));
	rep(i,30) rep(j,inf-10) dp[i][j]=dbl[j][i]=inf;
	for(int j=n-1;j>=0;j--){
		rep(k,1919){
			int f=0;
			rep(i,27){
				if(s[j]==('a'+i)){
					f|=cal(i,j,j+1);//dp[i][j]=j+1;
				}
				if(i>0 && dp[i-1][j]<inf){
					f|=cal(i,j,dp[i-1][dp[i-1][j]]);//dp[i][j]=min(dp[i-1][dp[i-1][j]],dp[i][j]);
				}
				if(i<26 && dp[26][j]<inf){
					f|=cal(i,j,dp[i][dp[26][j]]);//dp[i][j]=min(dp[i][dp[26][j]],dp[i][j]);
				}
				//if(dp[i][j+1]>=0) cout<<i<<' '<<j+1<<' '<<dp[i][j+1]<<endl;
			}
			if(f<1) break;
		}
	}
	rep(i,n+10){
		dbl[i][0]=dp[26][i];
		//if(i<=n) cout<<i<<' '<<dp[26][i]<<endl;
	}
	rep(i,26) rep(j,n+10){
		if(dbl[j][i]<inf) dbl[j][i+1]=dbl[dbl[j][i]][i];
		//if(i<4 && j<=n) cout<<i<<' '<<j<<' '<<dbl[j][i]<<endl;
	}
	cin>>q;
	rep(i,q){
		cin>>x>>y;x--;
		for(int i=22;i>=0;i--){
			if(dbl[x][i]<=y) x=dbl[x][i];
			//cout<<x<<endl;
		}
		if(y==x) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}


Measured memory_bytes: 121476
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

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

  vector<ll> ans(n);

  reps1(x, ll(sqrt(n))) {
    reps1(y, ll(sqrt(n))) {
      reps1(z, ll(sqrt(n))) {
        ll tmp = x*x + y*y + z*z + x*y + y*z + z*x;
        if (tmp > n) continue;
        ans[tmp]++;
      }
    }
  }

  reps1(i, n+1) cout << ans[i] << endl;

  /*

  reps1(i, n+1) {
    ll ans = 0;
    reps1(x, ll(sqrt(i))) {
      reps1(y, ll(sqrt(i))) {
        ll judge = (x+y)*(x+y) - 4 * (x*x + y*y + x*y - i);
        // cout << i << " " << x << " " << y << " " << judge << endl;
        if (ll(sqrt(judge)) * ll(sqrt(judge)) != judge) continue;
        // cout << "a";
        if (-(x+y)*(x+y) + judge <= 0) continue;
        // cout << "b";
        // cout << -(x+y)*(x+y) + judge << endl;
        if ((-(x+y)*(x+y) + judge) % 2 != 0) continue;
        // cout << "c" << endl;
        ans++;

      }
    }
    cout << ans << endl;
  }
  */

  return 0;
}


Measured memory_bytes: 3688