akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(1000001)

N = int(input())
D = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a].append((b, c))
    D[b].append((a, c))
Q, K = map(int, input().split())
DS = [-1] * (N + 2)


def dfs(c, p, d):
    DS[c] = d
    for r in D[c]:
        if r[0] == p:
            continue
        dfs(r[0], c, d + r[1])


def main():
    dfs(K - 1, -1, 0)
    for _ in range(Q):
        x, y = map(int, input().split())
        print(DS[x - 1] + DS[y - 1])


main()


Measured memory_bytes: 131632
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <random>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <deque>
//#include <bitset>
#include <math.h>
using namespace std ;
using ll = long long ;
using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
using vc = vector<char> ;
using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end()
ll mod = 1000000007 ;
//long double pie = acos(-1) ;
ll INF = 1e10 ;

void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
void fix_cout(){cout << fixed << setprecision(20) ;}
void chmax(ll &a,ll b){	if(a<b) a = b ;}
void chmin(ll &a,ll b){ if(a>b) a = b ;}

bool DFS(vvll &g,vll &color,int p,int c){
	color[p] = c ;
	bool res = true ;
	for(int i=0;i<g.size();i++){
		if(g[p][i]){
			if(color[i]==c) res = false ;
			else if(color[i]==-1) res &= DFS(g,color,i,c^1) ;
		}
	}
	return res ;
}

int main(){
	ll n ; cin >> n ;
	vvll g(n,vll(n)) ;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			char c ; cin >> c ;
			g[i][j] = c-'0' ;
		}
	}
	vll color(n,-1) ;
	if(DFS(g,color,0,0)){
		for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j&&g[i][j]==0) g[i][j] = INF ;
		for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) chmin(g[i][j],g[i][k]+g[k][j]) ;
		ll ans = 0 ;
		for(int i=0;i<n;i++) for(int j=0;j<n;j++) chmax(ans,g[i][j]) ;
		cout << ans+1 << endl ;
	}else{
		cout << -1 << endl ;
	}
}


Measured memory_bytes: 3960
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000;
struct node
{
	int x,y;
	double d;
}e[maxn];
bool cmp(node a,node b)
{
	return a.d<b.d;
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>e[i].x>>e[i].y;
		e[i].d=atan2(e[i].y*1.0,e[i].x*1.0);
	}
//	int nxt[1000];
//	for(int i=0;i<n-1;i++)
//		nxt[i]=i+1;
//	nxt[n-1]=0;
//	for(int i=0;i<n;i++)
//		cout<<nxt[i]<<' ';
	sort(e,e+n,cmp);
	ll ans=0;
	for(int i=0;i<n;i++)
	{
		ll dx=e[i].x,dy=e[i].y;
		ans=max(ans,(ll)dx*dx+dy*dy);
		for(int j=(i+1)%n;j!=i;j=(j+1)%n)
		{
			dx=dx+e[j].x;dy=dy+e[j].y;
			ans=max(ans,(ll)dx*dx+dy*dy);
		}
	}
	printf("%.15lf",sqrt(ans)); 
	return 0;
 } 

Measured memory_bytes: 384
n,W=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
m=sum([a[i][1] for i in range(n)])
dp=[[float('inf') for _ in range(m+1)] for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    weight,value=a[i]
    for j in range(m+1):
        dp[i+1][j]=min(dp[i][j],dp[i+1][j])
        if j+value<=m:
            dp[i+1][j+value]=min(dp[i][j+value],dp[i][j]+weight)
for i in range(m+1):
    if dp[-1][-i-1]<=W:
        print(m-i)
        break

Measured memory_bytes: 261328
#include <iostream>

using namespace std;

unsigned long long total;
string s;

#define conv(c) (c - '0')

void visit(unsigned long long sum, unsigned long long accum, int idx, bool putsign) {
  if (putsign) {
    sum += accum;
    accum = 0;
  } else {
    accum *= 10;
  }
  accum += conv(s[idx]);

  if (idx + 1 == s.size()) {
    total += sum + accum;
    return;
  }

  visit(sum, accum, idx + 1, true);
  visit(sum, accum, idx + 1, false);
}

int main() {
  cin >> s;
  visit(0, 0, 0, true);
  cout << total << endl;
}



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

int main() {
  string S;
  int K;
  int64_t Q=998244353;
  cin>>S>>K;
  K=min(300,K);
  vector<int> p;
  int a=0,P=0,V=S.size();
  for(int i=0;i<V;i++){
    if(S.at(i)=='1'){
      a++;
      P++;
    }
    else{
      p.push_back(a);
      a=0;
    }
  }
  int N=p.size();
  vector<vector<vector<int64_t>>> dp(K+1,vector<vector<int64_t>>(K+1,vector<int64_t>(N+1)));
  vector<vector<vector<int64_t>>> yr(K+1,vector<vector<int64_t>>(K+1,vector<int64_t>(N+1)));
  vector<vector<vector<int64_t>>> tr(K+1,vector<vector<int64_t>>(K+1,vector<int64_t>(N+1)));
  dp.at(0).at(0).at(0)=1;
  for(int i=0;i<N;i++){
    for(int j=0;j<=K;j++){
      yr.at(0).at(j).at(i)=dp.at(0).at(j).at(i);
      tr.at(j).at(0).at(i)=dp.at(j).at(0).at(i);
      for(int k=0;k<K;k++){
        yr.at(k+1).at(j).at(i)=(yr.at(k).at(j).at(i)+dp.at(k+1).at(j).at(i))%Q;
        tr.at(j).at(k+1).at(i)=(tr.at(j).at(k).at(i)+dp.at(j).at(k+1).at(i))%Q;
      }
    }
    int b=p.at(i);
    for(int j=0;j<=K;j++){
      for(int k=0;k<=j;k++){
        int64_t X=0,Y=0;
        if(k-b-1>=0){
          X=tr.at(j).at(k-b-1).at(i);
        }
        if(j-P+b-1>=0){
          Y=yr.at(j-P+b-1).at(k).at(i);
        }
        dp.at(j).at(k).at(i+1)=(tr.at(j).at(k).at(i)+yr.at(j).at(k).at(i)-dp.at(j).at(k).at(i)-X-Y+3*Q)%Q;
      }
    }
  }
  int64_t Z=0;
  for(int j=0;j<=K;j++){
    for(int i=j;i<=min(K,j+a);i++){
      Z+=dp.at(i).at(j).at(N);
      Z%=Q;
    }
  }
  cout<<Z<<endl;
}


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

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

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

    int n, k;
    cin >> n >> k;
    vector <int> a (n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int step = 0; step < min (k, 43); step++) {
        vector <int> b (n + 1, 0);
        for (int i = 1; i <= n; i++) {
            int l = i - a[i];
            int r = i + a[i];
            l = max (0, l);
            if (r + 1 <= n)
                b[r + 1]--;
            b[l]++;
        }
        for (int i = 1; i <= n; i++)
            b[i] += b[i - 1];
        a = b;
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << "\n";
    return 0;
}


Measured memory_bytes: 4988
#include <iostream>
using std :: cin;
using std :: cout;
using std :: endl;
#define int long long
int a[100010], n, ans, cur;
#undef int
int main() {
	cin >> n;
	for(int i = 0; i <= n; i ++ ) {
		cin >> a[i];
		if(!a[i]) ans += cur >> 1, cur = 0;
		else cur += a[i];
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long INF = 9999999999999999;
using ll = long long;
int main(){
  int K,A,B;
  cin>>K>>A>>B;
  if(A%K == 0 || B%K == 0){
    cout << "OK" << endl;
  }
  else{
    if(A/K != B/K){
      cout << "OK" << endl;
    }
    else{
      cout << "NG" << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<int, pair<int, int>> PP;
typedef pair<P, int> PPi;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

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

    int x;
    cin >> x;
    ll ans = 0;
    ans += (ll)x / 500 * 1000;
    x %= 500;
    ans += (ll)x / 5 * 5;
    cout << ans << endl;
}

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

#define REP(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

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

	int h, ans;
	REP(i, n){
		cin >> h;
		if(h >= k) ans++;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
using namespace std;
int n,q,t,k,d,ans;
map <char,char> mp,mp2;
int num[1000];
bool vis[1000];
int main(){
    string a;
    string b;
    memset(num,-1,sizeof(num));
    cin>>a>>b;
    for(int i=0;i<a.size();i++)
    {
        if(num[a[i]]==-1)
        {
            num[a[i]]=b[i];
        }
        else
        {
            if(num[a[i]]!=b[i])
            {
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    memset(num,-1,sizeof(num));
    for(int i=0;i<a.size();i++)
    {
        if(num[b[i]]==-1)
        {
            num[b[i]]=a[i];
        }
        else
        {
            if(num[b[i]]!=a[i])
            {
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    cout<<"Yes"<<endl;
    return 0;
	}

Measured memory_bytes: 776
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int N, C, K;
  cin >> N >> C >> K;
  vector<int> vec(N);
  for(int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  
   sort(vec.begin(), vec.end());
 
 int ans = 0, r = 0, l = 0;
    while(r < N) {
        int cnt = 0;
        while (vec[r] - vec[l] <= K && cnt < C && r < N) {
            r += 1;
            cnt += 1;
        }

        ans += 1;
        l = r;
    }

    cout << ans << endl;
    
}

Measured memory_bytes: 640
#include<cstdio>
#include<map>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

using namespace std;

int main(){
	int x,t;cin>>x>>t;
	if(x<=t){
		cout<<"0"<<endl;
		return 0;
	}
	else cout<<x-t<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int dp[1001][1001];

int Lcs(string X, string Y) {
    X = ' ' + X;
    Y = ' ' + Y;
    for (int i = 0; i < X.length(); ++i) {
        dp[i][0] = 0;
    }
    for (int i = 0; i < Y.length(); ++i) {
        dp[0][i] = 0;
    }

    int ans = 0;
    for (int i = 1; i < X.length(); ++i) {
        for (int j = 1; j < Y.length(); ++j) {
            if (X[i] == Y[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }

            ans = max(ans, dp[i][j]);
        }
    }

    return ans;
}

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

    for (int i = 0; i < n; ++i) {
        string X, Y;
        cin >> X >> Y;
        cout << Lcs(X, Y) << endl;
    }

    return 0;
}


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

long long dp[110][100010];

int main()
{
	int n,m;
	int v[110], w[110];
	cin >> n >> m;
	for(int i=1; i<=n ; i++)
		cin >> w[i] >> v[i];
		
	for(int i=1; i<=n ; i++)
	{
		for(int j=1; j<=m ; j++)
		{
			dp[i][j] = dp[i-1][j];
			if(w[i] <= j)
				dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
			
		}
	}
	cout << dp[n][m];
}

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

using namespace std;
int a[3001][3001]={-1};

int main()
{
    string s,t,u;
    cin>>s>>t;
    int n=s.size(),m=t.size();
    for(int i=0;i<n+1;i++)
        for(int j=0;j<m+1;j++)
         if(i==0 || j==0)
            a[i][j]=0;

   for(int i=1;i<n+1;i++)
        for(int j=1;j<m+1;j++)
        {
            if(s[i-1]==t[j-1])
                a[i][j]=1+a[i-1][j-1];
            else
                a[i][j]=max(a[i-1][j],a[i][j-1]);
        }

   while(m>0 && n>0)
        {
            if(s[n-1]==t[m-1])
             {u.push_back(s[n-1]);
               n--;
               m--;}
            else
            {
                if(a[n-1][m]>a[n][m-1])
                  n--;
                else
                    m--;

            }

        }
        reverse(u.begin(),u.end());
        cout<<u;

}


Measured memory_bytes: 38800
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
#define F first
#define S second

struct TreeNode{
    TreeNode* parent;
    vector<TreeNode*> children;
    int height, dist;
};


const int sz = 1e5+5;
int n, u, v;
int vis[sz];
vector<int> adj[sz];
TreeNode* t;

TreeNode* makeTree(int node, TreeNode* parent){
    vis[node] = true;
    TreeNode* tn = new TreeNode();
    tn->parent = parent;
    for(int next : adj[node]){
        if(!vis[next]) tn->children.push_back(makeTree(next, tn));
    }

    if(node == u) t = tn;
    return tn;
}

int getHeight(TreeNode* node){
    if(node->children.empty()){
        node->height = 0;
        return 0;
    }

    int height = -1;
    for(TreeNode* next : node->children){
        height = max(height, 1+getHeight(next));
    }

    node->height = height;
    return height;
}

void setDist(TreeNode* node, int dist){
    node->dist = dist;
    for(TreeNode* next : node->children){
        setDist(next, dist+1);
    }
}

void solve(){
    cin >> n >> u >> v;
    --u, --v;
    for(int i = 0; i < n-1; ++i){
        int a, b;
        cin >> a >> b;
        --a, --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    TreeNode* root = makeTree(v, NULL);
    getHeight(root);
    setDist(root, 0);

    int ans = 0, dist = t->dist, turns = 0;
    while(t != root){
        if(dist <= 0) break;
        ans = max(ans, t->height + dist - 1 + turns);

        t = t->parent;
        dist -= 2;
        turns++;
    }

    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            int[] student_x = new int[N];
            int[] student_y = new int[N];

            for (int i = 0; i < N; i++)
            {
                string[] ab = Console.ReadLine().Split(' ');
                student_x[i] = int.Parse(ab[0]);
                student_y[i] = int.Parse(ab[1]);
            }

            int[] point_x = new int[M];
            int[] point_y = new int[M];

            for(int i = 0; i < M; i++)
            {
                string[] cd = Console.ReadLine().Split(' ');
                point_x[i] = int.Parse(cd[0]);
                point_y[i] = int.Parse(cd[1]);
            }

            string ans = null;

            for (int i = 0; i < N; i++)
            {
                int min_index = int.MaxValue;
                int min_root = int.MaxValue;
                int from_x = student_x[i];
                int from_y = student_y[i];

                for (int j = 0; j < M; j++)
                {
                    int to_x = point_x[j];
                    int to_y = point_y[j];
                    if(Math.Abs(from_x - to_x)+ Math.Abs(from_y - to_y) < min_root)
                    {
                        min_index = j;
                        min_root = Math.Abs(from_x - to_x) + Math.Abs(from_y - to_y);
                    }
                }

                ans += (min_index+1).ToString() + "\n";
            }

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13140
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
//const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};

struct Node {
    int parent = -1, depth = 0;
    vector<int> children;
};
int d[100000];
Node node[100000];
void depth(int i, int now, int dep) {
    //cout << i << " " << now << " " << dep << endl;
    if (node[now].parent == -1) {
        d[i] = dep;
        return;
    }
    if (dep > 100) return;
    depth(i, node[now].parent, dep + 1);
    
}
int main() {
    int n; cin >> n;
    
    rep(i, n) {
        int id, k; cin >> id >> k;
        rep(j, k) {
            int c; cin >> c; //child
            node[id].children.push_back(c);
            node[c].parent = id;
        }
    }
    rep(i, n) {
        depth(i, i, 0);
        //cout << d[i] << endl;
    }
    rep(i, n) {
        cout << "node " << i << ": parent = " << node[i].parent <<
        ", depth = " << d[i] << ", ";
        if (node[i].parent == -1) cout << "root";
        else if (node[i].children.size() == 0) cout << "leaf";
        else cout << "internal node";
        cout << ", [";
        rep(j, node[i].children.size()) {
            cout << node[i].children[j];
            if (j != node[i].children.size() - 1) {
                cout << ", ";
            }
        }
        cout << "]" << endl;
    }
}



Measured memory_bytes: 7372
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  int a[N];
  for(int i=0;i<N;i++){
    cin>>a[i];
  }
  int count=0;
  for(int i=0;i<N-1;i++){
    if(a[i]==a[i+1]){
      a[i+1]=N+1;
      count++;
    }
  }
  for(int i=0;i<N;i++){
  }
  cout<<count<<endl;
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define mod 1000000007
#define ll long long
#define cases ll t;cin>>t;while(t--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)


int main()
{
    fast;
    ll i,j,n,m,k;
    string s;
    cin>>s;
    if(s[2]==s[3] && s[4]==s[5]) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define show(x) for(auto i: x){cout << i << " ";}
#define showm(m) for(auto i: m){cout << m.x << " ";}
typedef long long ll;
typedef pair<int, int> P;
ll gcd(ll x, ll y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


template<class X> void factorization(X input, set<X>& Pnumber){
    for(X i = 2; i*i <= input; i++)
    {
        if (input % i == 0){
            while (input % i == 0){
                input /= i;
                Pnumber.insert(i);
            }
        }
    }
    if (input != 1) Pnumber.insert(input);
}

int main()
{
    ll a, b;
    cin >> a >> b;
    ll num = gcd(a, b);

    set<ll> pnum;
    factorization(num, pnum);

    cout << pnum.size() + 1 << endl;
}



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


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

using namespace std;

int main()
{
    int N;
    cin >> N;
    while (N--) {
        int Y, M, D, day = 0, cnt = 0;
        cin >> Y >> M >> D;
        while (Y != 1000 || M != 1 || D != 1) {
            D++; cnt++;
            if (Y % 3 == 0 || M % 2 == 1) {
                day = 20;
                if (D > day) {
                    D = 1;
                    M++;
                }
            } else {
                day = 19;
                if (D > day) {
                    D = 1;
                    M++;
                }
            }
            if (M > 10) {
                Y++; M = 1;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

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

#define ntest 0

using namespace std;
long long h, w, m, x, y, res, mxX, mxY;
const long long k = 1e6;
set<long long> st;
long long r[300005], c[300005];
long long  getH(long long x, long long y) {
    return x * k + y;
}
void solve() {
    cin >> h >> w >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y;
        r[x]++;
        c[y]++;
        st.insert(getH(x,y));
    }
    for (int i = 1; i <= h; ++i) mxX = max(mxX, r[i]);
    for (int i = 1; i <= w; ++i) mxY = max(mxY, c[i]);
    res = mxX + mxY - 1;
    vector<int> candidateX, candidateY;
    for (int i = 1; i <= h; ++i) if (r[i] == mxX) candidateX.push_back(i);
    for (int i = 1; i <= w; ++i) if (c[i] == mxY) candidateY.push_back(i);
    for (auto &i : candidateX)
    for(auto &j :candidateY) {
        if (!st.count(getH(i,j))) {
            ++res;
            cout << res << '\n';
            return;
        }
    }
    cout << res << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    if(ntest){
        int t;
        cin >> t;
        while(t--) solve();
    } else {
        solve();
    }

}




Measured memory_bytes: 26052
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
long long a[100010];
int main() {
#define int long long
	int n;
	deque<int> que;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	int co = 0;
	que.push_back(a[0]);
	co++;
	int co1 = 2, co2 = 2;
	while (co < n) {
		que.push_front(a[n - co1]);
		co++;
		if (co == n) {
			break;
		}
		que.push_back(a[n - co1 + 1]);
		co++;
		if (co == n) {
			break;
		}
		co1 += 2;
		que.push_front(a[0 + co2 - 1]);
		co++;
		if (co == n) {
			break;
		}
		que.push_back(a[0 + co2]);
		co++;
		if (co == n) {
			break;
		}
		co2 += 2;
	}
	deque<int> que1;
	que1.push_back(a[n - 1]);
	co = 0, co1 = 2, co2 = 2;
	co++;
	while (co < n) {
		que1.push_front(a[0 + co2 - 2]); 
		co++;
		if (co == n) {
			break;
		}
		que1.push_back(a[0 + co2 - 1]);
		co++;
		if (co == n) {
			break;
		}
		co2 += 2;
		que1.push_front(a[n - co1]);
		co++;
		if (co == n) {
			break;
		}
		que1.push_back(a[n - co1 - 1]);
		co++;
		if (co == n) {
			break;
		}
		co1 += 2;
	}
	long long ans = que.back(), ans2 = que1.back();
	que.pop_back();
	que1.pop_back();
	long long ans1 = 0, ans3 = 0;
	while (!que.empty()) {
		ans1 += abs(ans - que.back());
		ans3 += abs(ans2 - que1.back());
		ans = que.back();
		ans2 = que1.back();
		que.pop_back();
		que1.pop_back();
	}
	cout << max(ans1,ans3) << endl;
	return 0;
}

Measured memory_bytes: 2816
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define inv(x) (ksm(x, P - 2))

using namespace std;

const int maxn = 4e3 + 5;
const int P = 924844033;

int n, k, f[maxn][maxn], fac[maxn], ifac[maxn], vis[maxn], a[maxn], tot, sum[maxn];

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

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int ksm(int x, int k, int rnt = 1) {
	for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
	return rnt;
}

const int inv2 = inv(2);

inline int C(int n, int m) { return 1ll * fac[n] * ifac[n - m] % P * ifac[m] % P; }

int main() {
	n = read(); k = read(); fac[0] = 1; int N = n;
	rep(i, 1, N) fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[N] = inv(fac[N]);
	dep(i, N - 1, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	rep(i, 1, n) rep(o, 0, 1) if(!vis[i + o * n]) {
		int con = 0;
		for(int j = i, ty = o; !vis[j + ty * n] && j <= n; j += k, ty ^= 1) con++, vis[j + ty * n] = 1;
		a[++tot] = con - 1;
	}
	f[0][0] = 1;
	rep(i, 1, tot) sum[i] = sum[i - 1] + (a[i] + 1 >> 1);
	rep(i, 1, tot) rep(j, 0, sum[i - 1]) rep(k, 0, (a[i] + 1) / 2)
		f[i][j + k] = pls(f[i][j + k], 1ll * f[i - 1][j] * C(a[i] - k + 1, k) % P);
	int ans = 0;
	rep(i, 0, n) if(i & 1) ans = dec(ans, 1ll * f[tot][i] * fac[n - i] % P);
		else ans = pls(ans, 1ll * f[tot][i] * fac[n - i] % P);
	cout << ans << endl;
	return 0;
}
/*
*/

Measured memory_bytes: 60544
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include<iomanip>
#include<functional>

using namespace std;
typedef long long ll;

// a と b の最大公約数を返す関数
long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

int main() {
	int K; cin >> K;
    ll ans = 0;
    for (int i = 1; i <= K; i++)
        for (int j = 1; j <= K; j++)
            for (int k = 1; k <= K; k++)
                ans += GCD(GCD(i, j), k);
    cout << ans << endl;
}


Measured memory_bytes: 3628
/*Practice hard*/
#include <bits/stdc++.h>
using namespace std;

//_______MACROS_______//
#define   fast  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define   int   long long int
#define   pb    push_back
#define   f     first
#define   s     second
#define   PI    3.1415926535898


int k , a , b;
void input()
{
    cin >> k >> a >> b;
}
void solve()
{
    for (int i = min(a,b) ; i <= max(b,a) ; i++)
    {
        if (i%k == 0)
        {
            cout << "OK" << endl;
            return ;
        }
    }
    cout << "NG" << endl;
}
signed main()
{
    input();
    solve();
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <deque>
using namespace std;
int main() {
	int num, count, input;
	deque<int> dq;
	cin >> num;
	count = 0;
	while (cin >> input) {
		if (count % 2 == 0) {
			dq.push_back(input);
		} else {
			dq.push_front(input);
		}
		count++;
	}
	if (num % 2 == 0) {
		cout << dq.front();
		dq.pop_front();
		while (dq.size() > 0) {
			cout << " " << dq.front();
			dq.pop_front();
		}
	} else {
		cout << dq.back();
		dq.pop_back();
		while (dq.size() > 0) {
			cout << " " << dq.back();
			dq.pop_back();
		}
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int f(ll n)
{
    if(n<3) return 0;
    return 1+f((n-1)/2);
}

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

    ll l=0, r=1LL<<44;
    while(r-l>1)
    {
        ll m = (l+r)/2;
        if(f(m)<=x) l=m;
        else r=m;
    }
    cout << l << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
using namespace std;

char A[500050]; int F[500050];
bool cut[500050];

int main()
{
	scanf("%s", A);
	int l = 0; while (A[l]) l++;
	int k = -1; F[0] = -1;
	for (int i=1;i<l;i++){
		while (k >= 0 && A[k+1] != A[i]) k = F[k];
		if (A[k+1] == A[i]) k++;
		F[i] = k;
	}

	if (F[l-1] == l-2) printf("%d\n1\n", l);
	else if (F[l-1] == -1 || l % (l-1 - F[l-1]) != 0) printf("1\n1\n");
	else{
		int ans = 0;
		for (int i=1;i<l;i++) if (F[i] != -1){
			int p = i - F[i];
			if ((i + 1) % p == 0) cut[i+1] = 1;
		}

		reverse(A, A+l);
		int k = -1; F[0] = -1;
		for (int i=1;i<l;i++){
			while (k >= 0 && A[k+1] != A[i]) k = F[k];
			if (A[k+1] == A[i]) k++;
			F[i] = k;
		}
		for (int i=1;i<l;i++) if (F[i] != -1){
			int p = i - F[i];
			if ((i + 1) % p == 0) cut[l-i-1] = 1;
		}

		for (int i=1;i<l;i++) if (!cut[i]) ans++;
		printf("2\n%d\n", ans);
	}
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  vector<int> v(N);
  for (int i = 0; i < N; i++) {
    cin >> v.at(i);
  }
  
  sort(v.begin(), v.end());
  double a =  (double)((v.at(0) + v.at(1)) * 1.0/ 2);
  
  for (int i = 2; i < N; i++) {
    a = (a + v.at(i)) / 2;
  }
  cout << a << endl;
}

  
    
    
 




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
using Graph = vector<vector<int>>;
pair<int, int> visit(int from, int node, const Graph& g)
{
    pair<int, int> r = {0, node};
    for (int next : g[node]) if (next != from) {
        pair<int, int> t = visit(node, next, g);
        t.first += 1;
        if (r.first < t.first) r = t;
    }
    return r;
}
int main()
{
    int N; cin >> N;
    Graph G(N);
    for (int i = 0; i < N-1; i++) {
        int a, b; cin >> a >> b; a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    auto p = visit(-1, 0, G);
    auto q = visit(-1, p.second, G);
    int diameter = q.first;
    cout << ((diameter % 3 != 1) ? "First" : "Second") << '\n';
    return 0;
}

Measured memory_bytes: 26752
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>

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

using namespace std;
const int inf = 1001001000;
const long long int Inf = 1001001001001001000;

void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}


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

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<' ';
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int p[5] = {0,1,2,3,4};
    vector<double> m(5);
    rep(i,5)cin>>m[i];
    double ans = inf;
    do{
        double tmp = 0;
        rep(i,4)tmp += 10*ceil(m[p[i]]/10.0);
        ans = min(ans,tmp+m[p[4]]);
    }while(next_permutation(p,p+5));
    cout<<ans<<endl; return 0;
}


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

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

int wa[100001] = {};

int main() {
    int N, M;
    cin >> N >> M;
    int p;
    string S;
    int ac = 0, pena = 0;
    for (int i=0; i<M; ++i) {
        cin >> p >> S;
        if (S == "AC" && wa[p] != -1) {
            ac ++;
            pena += wa[p];
            wa[p] = -1;
        } else if (S == "WA" && wa[p] != -1) {
            wa[p] ++;
        }
    }
    cout << ac << " " << pena << endl;

    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include <cmath>
using namespace std;

#define mod 1000000007
#define ten5 100005
#define ten52 200005
#define ten6 1000005
#define PI 3.1415926
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define mkpr(x1,x2) make_pair(x1,x2)
typedef long long int ll;


//stack<char> stk;
//set<ll> sll;
//map<string,ll> mp,mp1;
//map<pair<ll,ll>,ll>::iterator iter;
//map<ll,ll> mp;
//deque<char> deq;
//vector<ll> vll;
ll num[ten52];
ll path[ten52];

int main(void)
{
    long long int m,n,i;
    long long int a1;
    string s;
    cin>>s;
    for(i=0;i<3;i++) cout<<s[i];

    return 0;
}





Measured memory_bytes: 3628
my ($n, $m) = split(/\s/, <STDIN>);
my @array = ();

for (my $i=0; $i<$m; $i++) {
    my ($p, $y) = split(/\s/, <STDIN>);
    my %e = ( n=>$i+1, p=>$p, y=>$y );
    push @array, \%e;
}

@array = sort { $a->{y} <=> $b->{y} } @array;
my @city = ();

for (my $i=0; $i<$m; $i++) {
    my $e = $array[$i];
    $e->{x} = ++$city[$e->{p}];
}

@array = sort { $a->{n} <=> $b->{n} } @array;

for (my $i=0; $i<$m; $i++) {
    my $e = $array[$i];
    printf "%06d%06d\n", $e->{p}, $e->{x};
}


Measured memory_bytes: 56052
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;


vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

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

    auto div = divisor(n);

    lint ans = 1e18;
    for(auto x : div) {
        lint y = n / x;
        ans = min(ans, x + y - 2);
    }

    cout << ans << endl;
}

Measured memory_bytes: 384
def mp():return map(int,input().split())
def lmp():return list(map(int,input().split()))

n,m = mp()
h = lmp()
edge = []
for i in range(n+1):
    edge.append([])
for i in range(m):
    a,b = mp()
    edge[a].append(b)
    edge[b].append(a)

ans = 0
for i in range(1, n+1):
    tar = edge[i]
    height = h[i-1]
    flag = True
    for j in range(len(tar)):
        if h[tar[j]-1] >= height:
            flag = False
    if flag:
        ans += 1
print(ans)



Measured memory_bytes: 93000
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int H = sc.nextInt();
            int W = sc.nextInt();
            if (H == 0 && W == 0) {
                break;
            }

            for (int h = 0; h < H; h++) {
                for (int w = 0; w < W; w++) {
                    if (w == 0 || h == 0 && w != (W - 1) || h == (H - 1) && w != (W - 1)) {
                        System.out.print("#");
                    } else if (w == (W - 1)) {
                        System.out.println("#");
                    } else {
                        System.out.print(".");
                    }
                }
            }
            System.out.println();
        }
    }
}



Measured memory_bytes: 33960
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <utility>
 
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;    
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    if(s=="SAT") cout<<1;
    if(s=="MON") cout<<6;
    if(s=="TUE") cout<<5;
    if(s=="WED") cout<<4;
    if(s=="THU") cout<<3;
    if(s=="FRI") cout<<2;
    if(s=="SUN") cout<<7;
    cout<<'\n';
    
    
    return 0;
}


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

using namespace std;
using ll = long long;

#ifdef LOCAL 
    #include "_/debug.h"
#else 
    #define out(...) 69;
#endif

const int N = 2e5 + 5;

vector<int> g[N];
deque<int> ord;
int vis[N];
ll k;

bool found = false;

void dfs(int u, ll cnt = 0LL) {
    if (cnt == k) {
        found = true;
        cout << u << '\n';
        return;
    }
    if (vis[u]) {
        while (ord.front() != u) ord.pop_front();
        k -= cnt;
        return;
    }
    vis[u] = 1;
    ord.push_back(u);
    for (int v : g[u]) {
        dfs(v, cnt + 1LL);
    }
}

int main() { 
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    int n;
    cin >> n >> k;
    for (int u = 1; u <= n; u++) {
        int v;
        cin >> v;
        g[u].push_back(v);
    }    
    dfs(1);
    if (found) return 0;
    int node = k % (ll) ord.size();
    cout << ord[node] << '\n';
}

Measured memory_bytes: 25676
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

H, W = mi()
C = li2(10)
A = li2(H)

## ワーシャルフロイド法
for k in range(10):
    for j in range(10):
        for i in range(10):
            C[i][j] = min(C[i][j], C[i][k]+C[k][j])

## 各要素における最小コストを合計
ans = 0
for i in range(H):
    for j in range(W):
        if abs(A[i][j]) != 1:
            ans += C[A[i][j]][1]

print(ans)

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

int count_bomb(vector<string> &S,int H,int W,int x,int y){
  const int dx[8]={0,0,1,1,1,-1,-1,-1};
  const int dy[8]={1,-1,0,1,-1,0,1,-1};
  int count=0; 
  for(int i=0;i<8;i++){
    int nx=x+dx[i];
    int ny=y+dy[i];
    if(nx<0||nx>=H||ny<0||ny>=W)continue;
    if(S.at(nx).at(ny)=='#')count++;
  }
  return count;
}

int main(){
  int H,W;
  cin >> H >> W;
  vector<string> S(H);
  for(int i=0;i<H;i++){
    cin >> S.at(i);
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(S.at(i).at(j)=='#')continue;
      else{
        int s=count_bomb(S,H,W,i,j);
        S.at(i).at(j)=char(s+'0');
      }
    }
  }
  for(int i=0;i<H;i++){
      cout << S.at(i) << endl;
  }
}

Measured memory_bytes: 256
'''
INPUT SHORTCUTS
N, K = map(int,input().split())
N ,A,B = map(int,input().split())
string = str(input())
arr = list(map(int,input().split()))
N = int(input())
'''
n , m = map(int,input().split())
dp = [-1 for _ in range(n)]
flag = True 
for _ in range(m):
	i , val =  map(int,input().split())
	if dp[i-1] == -1:
		dp[i-1]=val
	elif dp[i-1]!=val:
		flag = False
		# print(dp[i-1])
		break
if dp[0]==0 and n>1:
	flag = False
if flag:
	for i in range(n):
		if dp[i]==-1:
			dp[i]=0
	if dp[0]==0 and n>1:
		dp[0]=1
	for x in dp:
		print(str(x),end="")
else:
	print("-1")

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define fre freopen("C:\\in.txt", "r", stdin)
#define _for(i,a,b) for(int i=a; i< b; i++)
#define _rep(i,a,b) for(int i=a; i<=b; i++)
#define lowbit(a) ((a)&-(a))
#define inf 0x3f3f3f3f
#define endl "\n"
using namespace std;
typedef long long ll;
template <class T>
void read(T &x)
{
    char c; bool op=0;
    while(c=getchar(), c<'0'||c>'9') if(c=='-') op=1;
    x=c-'0';
    while(c=getchar(), c>='0'&&c<='9') x=x*10+c-'0';
    if(op) x=-x;
}

const int mod=1e9+7;

int main()
{
    int n, k;
    read(n), read(k);
    vector<ll> a(n);
    for(auto &val: a) read(val);
    sort(a.begin(), a.end());
    ll ans=1; int ok=0;
    if(k%2) ans*=a[--n], k--;
    if(ans<0) ok=1;
    int l=0, r=n-1;
    while(k){
        ll x=a[r]*a[r-1], y=a[l]*a[l+1];
        if(ok || x>y)
            ans=x%mod*ans%mod, r-=2;
        else ans=y%mod*ans%mod, l+=2;
        //cout<<l<<" "<<r<<" "<<ans<<endl;
        k-=2;
    }
    printf("%lld\n", (ans+mod)%mod);
    return 0;
}


Measured memory_bytes: 4764
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M;
    cin >> N >> M;
    vec<ll> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    sort(A.begin(),A.end());
    
    auto calc = [&](ll x){
        ll res = 0;
        for(int i=0;i<N;i++){ 
            ll id = lower_bound(A.begin(),A.end(),x-A[i])-A.begin();
            res += N-id;
        }
        return res;
    };
    
    ll l = 0,r = 1e11;
    while(l+1<r){
        ll m = (l+r)>>1;
        (calc(m)<=M? r:l) = m;
    }

    cerr << r << endl;
    vec<ll> S(N+1);
    for(int i=0;i<N;i++) S[i+1] = S[i]+A[i];
    ll ans = 0;
    for(int i=0;i<N;i++){
        ll id = lower_bound(A.begin(),A.end(),r-A[i])-A.begin();
//        cerr << i << " " << id << " " << S[id] << endl;
        ans += (N-id)*A[i]+(S[N]-S[id]);
    }

    ll c = calc(r);
    l = 0;
    while(l+1<r){
        ll m = (l+r)>>1;
        (calc(m)<c? r:l) = m;
    }
    ans += l*(M-c);
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<stdio.h>
int main(){
  int x[10000];
  int i,count=0;
  for(i=0;i<10000;i++){
    scanf("%d",&x[i]);
    if(x[i]==0) break;
    count++;
  }
  for(i=0;i<count;i++){
    printf("Case %d: %d\n",i+1,x[i]);
  }
  return 0;
}

Measured memory_bytes: 632
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector as V
import           Data.Char
import           Data.Ratio

readIntN :: Int -> IO (V.Vector Int)
readIntN n = V.unfoldrN n (B.readInt . B.dropWhile isSpace) <$> B.getLine

main :: IO ()
main = do
  n <- readLn
  as <- readIntN n
  print $ solve n as

solve :: Int -> V.Vector Int -> Int
solve n as = V.head $ V.elemIndices True _idx
  where
    _ave = (V.sum as) % n
    _abs = V.map abs $ V.map (\a -> (a % 1) - _ave) as
    _min = V.minimum _abs
    _idx = V.map ((==) _min) _abs


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

class Program
{
    public static void Main()
    {
        var s = Console.ReadLine().Split(' ');
        var N = int.Parse(s[0]);
        var M = int.Parse(s[1]);

        int l = M / N;
        for (int i = l ; i > 0 ; i--)
        {
            if (M % i == 0)
            {
                Console.WriteLine(i);
                break;
            }
        }
    }
}

Measured memory_bytes: 13140
import numpy as np

N = int(input())
A = []

for i in range(N):
    A.append(int(input()))

B = np.array(A)
C = B.argsort()[::-1]

fuji_i = C[0]
kita_i = C[1]
fuji = A[C[0]]
kita = A[C[1]]

for i in range(N):
    if i != fuji_i:
        print(fuji)
    else:
        print(kita)

Measured memory_bytes: 24780
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
typedef long long ll;
const ll MOD=1000000007;
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }

int main(void){
    // Your code here!
    int n,k;cin >> n >> k;
    int ans =0;
    while (n) {
        ans++;
        n/=k;
    }
    cout << ans << endl;
}


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

using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
using ll = long long;
using Pair = pair<int, int>;
const ll mod = 1e9 + 7;


template<class T>
T gcd(T a, T b)
{
  if(a && b) {
    return gcd(min(a, b), max(a, b) % min(a, b));
  } else {
    return a;
  }
}

template<class T>
T lcm(T a, T b)
{
  return a / gcd(a, b) * b;
}

ll power(ll base, ll exponent, ll module)
{
  if(exponent % 2) {
    return power(base, exponent - 1, module) * base % module;
  } else if(exponent) {
    ll root_ans = power(base, exponent / 2, module);
    return root_ans * root_ans % module;
  } else {
    return 1;
  }
}

struct combination
{
  vector<ll> fact, inv;
  combination(int sz) : fact(sz + 1), inv(sz + 1)
  {
    fact[0] = 1;
    for(int i = 1; i <= sz; i++) {
      fact[i] = fact[i - 1] * i % mod;
    }
    inv[sz] = power(fact[sz], mod - 2, mod);
    for(int i = sz - 1; i >= 0; i--) {
      inv[i] = inv[i + 1] * (i + 1) % mod;
    }
  }
  ll Pair(int n, int r)
  {
    if(r < 0 || n < r) return 0;
    return (fact[n] * inv[n - r] % mod);
  }
  ll C(int p, int q)
  {
    if(q < 0 || p < q) return 0;
    return (fact[p] * inv[q] % mod * inv[p - q] % mod);
  }
};

template<typename T>
void print_vec(vector<T>& v)
{
  for(const auto& e: v) {
    cout << e << " ";
  }
  cout << endl;
}
template<typename T>
void print_2dvec(vector<vector<T>>& m)
{
  for(const auto& v: m) {
    for(const auto& e: v) {
      cout << e << " ";
    }
    cout << endl;
  }
}

const int INF = 1001001001;

vector<vector<int>> dp;

int main(int argc, char const* argv[])
{
  int h, n;

  cin >> h >> n;

  vector<int> dummy(h+1, INF);
  dp.push_back(dummy);
  dp.at(0).at(0) = 0;
  REP(i, n) {
    dp.push_back(dummy);
    int a, b;
    cin >> a >> b;
    REP(j, h+1) {
      int tmp = j-a > 0 ? j-a : 0;
      dp.at(i+1).at(j) = min(dp.at(i).at(j), dp.at(i+1).at(tmp) + b);
    }
  }

  cout << dp.at(n).at(h) << endl;

  return 0;
}

Measured memory_bytes: 39808
a, b, c = map(int, input().split())
total = 0
for i in range(1, a + 1):
  d = str(i)
  e = list(d)
  sum = 0
  for j in e:
    sum += int(j)
  if ((sum >= int(b)) & (sum <= int(c))):
    total += i
print(total)

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

int main()
{
  	long long int n, k, res;
  	cin>>n>>k;
  	long long int s = 0;
  	map<long long int, long long int>mp;
  	for(long long int i = 0; i < n; i++)
    {
    	long long int a, b;
      	cin>>a>>b;
      	mp[a] += b;
    }
  	for(auto i = mp.begin(); i != mp.end(); i++)
    {
    	s += i -> second;
      	if(s >= k)
        {
        	res = i -> first;
          	break;
        }
    }
  	cout<<res;
	return 0;
}

Measured memory_bytes: 4224
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int arr[] = new int[N+1];
    int srt[] = new int[N+1];
    for(int i = 1; i<=N; i++){
      arr[i] = sc.nextInt();
      srt[i] = arr[i];
    }
    Arrays.sort(srt);
    for(int i = 1; i<=N; i++){
      if(arr[i] >= srt[N/2+1]){
        System.out.println(srt[N/2]); 
      }
      else{
        System.out.println(srt[N/2+1]); 
      }
    }
  }

}


/*

pre[i] = arr[1] + arr[2] + arr[3] + arr[4] + ... + arr[i]
The question for some l and r
arr[l] + arr[l+1] + arr[l+2] + ... + arr[r]
= 
pre[r] - pre[l-1]

pre[r]   = arr[1] + arr[2] + ... + arr[l-1] + arr[l] + arr[l+1] + ... + arr[r]
-
pre[l-1] = arr[1] + arr[2] + ... + arr[l-1]

*/


Measured memory_bytes: 65072