akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

#define MAX_N 100

using namespace std;

int n, steps = 0;
int numbers[MAX_N];

void swap(int &a, int &b) {
	int tmp = a;
	a = b;
	b = tmp;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i ++) cin >> numbers[i];

	bool flag = true;
	int i = 0;
	while (flag) {
		flag = false;
		for (int j = n - 1; j > i; j --) {
			if (numbers[j] < numbers[j - 1]) {
				swap(numbers[j], numbers[j - 1]);
				flag = true;
				steps ++;
			}
		}
	}

	for (int i = 0; i < n; i ++) if (i == 0) cout << numbers[i]; else cout << " " << numbers[i];
	cout << endl << steps << endl;

	return 0;
}


Measured memory_bytes: 3056
n, k = map(int, input().split())
ab = [0] * n
cnt = [0] * 100001
for i in range(n):
    a, b = map(int, input().split())
    cnt[a] += b
ans = 0
for num in range(1, 100002):
    ans += cnt[num]
    if ans >= k:
        print(num)
        break

Measured memory_bytes: 6516
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int x = sc.nextInt();
        
        for(int i=0; i<k*2-1; i++){
            System.out.print((x-(k-1))+i + " ");
        }
        
        // System.out.println();
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define int long long
using namespace std;

 main()
{
	int n;
	int ans = (int)1e18;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	for(int i = 1; i < n; i++){
		a[i] += a[i - 1];
	}
	int l = 0, r = 2;
	for(int i = 2; i < n - 1; i++){
		while(l <= i && abs(a[i - 1] - a[l] - a[l]) > abs(a[i - 1] - a[l + 1] - a[l + 1]))
            l++;
		while(r <= n - 2 && abs((a[n - 1] - a[r]) - (a[r] - a[i - 1])) > abs((a[n - 1] - a[r + 1]) - (a[r + 1] - a[i - 1])))
		    r++;
		int b, c, d, e;
		b = a[l];
		c = a[i - 1] - a[l];
		d = a[r] - a[i - 1];
		e = a[n - 1] - a[r];
		ans = min(ans, max({b, c, d, e}) - min({b, c, d, e}));
	}
	cout << ans << endl;
	
}


Measured memory_bytes: 1920
#include<iostream>
#include<cstdlib>
#include <cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

int canTriangle(long long a, long long b, long long c){
    
    if((a==b) || (b==c) || (c==a)) return 0;
    
    if(a+b <= c) return 0;
    if((a-b >= c) || (b-a >=c)) return 0;
    
    return 1;
}

int main()
{ 
    int N, ans=0;
    cin >> N;
    
    long long L[N];
    for(int i=0; i<N; i++){
        cin >> L[i];
    }
    
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            for(int k=j+1; k<N; k++){
                ans += canTriangle(L[i], L[j], L[k]);               
            }
        }
    }
    cout << ans << endl;
}


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

int main()
{
    int w, h, x, y, r;
    scanf("%d%d%d%d%d", &w, &h, &x, &y, &r);

    if (x - r >= 0 && x + r <= w && y - r >= 0 && y + r <= h)
        printf("Yes\n");
    else
        printf("No\n");
}


Measured memory_bytes: 3168
n, x = map(int, input().split())

nums = sorted(list(map(int, input().split())))

count = 0
for i, num in enumerate(nums):
    if (i < n-1 and num <= x) or (i == n-1 and num == x):
        count += 1
        x -= num        
    else:
        break

print(count)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
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;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> as(n);
  for(Int i=0;i<n;i++) cin>>as[i];
  set<Int> ss;
  for(Int a:as) ss.emplace(a);
  cout<<ss.size()<<endl;
  return 0;
}



Measured memory_bytes: 8316
#include<stdio.h>
int main(){
long long n,a,b,i,ans=0,min=100000000000;
scanf("%lld",&n);
for(i=0;i<n;i++){
scanf("%lld%lld",&a,&b);
if(a>b&&b<min)
min=b;
  ans+=a;
}
  if(min>=10000000000)
    printf("0\n");
  else
printf("%lld\n",ans-min);
return 0;
}


Measured memory_bytes: 128
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 1
ans = 0
inf = float("inf")

n = k()
a = l()

a.sort(reverse = True)

for i in range(1,n):
    ans += a[i//2]

print(ans)


Measured memory_bytes: 32900
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <string>
#include <bitset>
#include <fstream>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef vector<pii> vii;

#define INF 1000000007ll
#define PB push_back
#define MP make_pair
#define X first
#define Y second
#define Min(a,b) (((a) < (b))?(a):(b))
#define Max(a,b) (((a) > (b))?(a):(b))
#define Abs(a) (((a) > 0)?(a):(-1)*(a))
#define cil(a,b) ( ((a)%(b) == 0)?((a)/(b)):((a)/(b)+1) )
#define SIZE 0

char s[1002];
int main() {
   int n, sum = 0, mn = INF, b = 0, e = 0;
   cin >> n;
   scanf("%s", s + 1);
   for (int i = 1 ; i <= n ; ++i) {
      if (s[i] == ')') --sum;
      else ++sum;
      mn = Min (mn, sum);
   }
   if (mn >= 0) {
      if (sum != 0) e = sum;
   }
   else if (mn < 0) {
      b = -mn;
      e = sum + b;
   }
   while (b--) printf("(");
   printf("%s", s + 1);
   while (e--) printf(")");
   printf("\n");

   return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define F first
#define S second
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
using ll = long long;
using pi = pair<int,int>;
int main()
{
  ll n; cin >> n;
  vector<ll> l(n);
  rep(i,n) cin >> l[i];

  ll res = 0;
  rep(i,n) rep(j,n) rep(k,n) {
    if(l[i] == l[j] || l[i] == l[k] || l[j] == l[k]) continue;
    if(i < j && j < k) {
      if(2 * max({l[i], l[j], l[k]}) < l[i] + l[j] + l[k]) {
	res++;
      }
    }
  }
  cout << res << "\n";


  
  return 0;
}


Measured memory_bytes: 3648
using System;
using System.Text;
using System.Diagnostics;
using System.Numerics;
using System.Collections.Generic;

class Myon

{
    public Myon() { }
    public static int Main()
    {
        cin = new Scanner();
        new Myon().calc();
        return 0;
    }
    static Scanner cin;


    void calc()
    {
        int N = cin.nextInt();
        double[] x = new double[N];
        double[] y = new double[N];
        for (int i = 0; i < N; i++)
        {
            x[i] = cin.nextInt();
            y[i] = cin.nextInt();
        }

        double best = 1e9;
        double besty = 500;
        double bestx = 500;

        Random r = new Random();

        double dist = 1;
        for (int i = 0; i < 200000; i++)
        {
            dist *= 0.9999;
            double tempy = besty + dist * (r.Next(0, 1000) - 500);
            double tempx = bestx + dist * (r.Next(0, 1000) - 500);
            double now = 0;
            for (int j = 0; j < N; j++)
            {
                now = Math.Max(now, Math.Sqrt(p2(tempy - y[j]) + p2(tempx - x[j])));
            }
            if(now < best)
            {
                besty = tempy;
                bestx = tempx;
                best = now;
            }
        }
        Console.WriteLine("{0:0.0000000000000000}", best);


    }
    double p2(double a)
    {
        return a * a;
    }
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}


Measured memory_bytes: 13264
#include<iostream>
#include<math.h>
#include<cstdio>

#define PI 3.141592653589793

using namespace std;

int main(){
	int dis,deg;
	double x,y,rad;
	char con;
	x=y=0;
	rad+= 90 * PI / 180.0;;
	while(cin>>dis>>con>>deg,dis|deg){
		x+=dis*cos(rad);
		y+=dis*sin(rad);
		rad+= deg * PI / 180.0;;
	}
	cout<<-(int)x<<endl<<(int)y<<endl;
}

Measured memory_bytes: 1164
N,Q=map(int,input().split())
S=str(input())
AC_list=[0]*N
t=0
for i in range(1,N):
  if S[i]=='C' and S[i-1]=='A':
    t+=1
  AC_list[i]=t
ans=0
for i in range(Q):
  l,r=map(int,input().split())
  print(AC_list[r-1]-AC_list[l-1])

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

#define rep(i, x, n) for (int i = x; i < n; i++)
typedef long long ll;

const int INF = 1e9 + 7;

using namespace std;

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

	int n;
	cin >> n;

	vector<ll> A(n);
	rep (i, 0, n)
		cin >> A[i];

	ll res[n];
	ll tmp = 0;
	rep (i, 0, n)
		tmp += ((i % 2 == 0) ? 1 : -1) * A[i] * 2;

	res[0] = tmp / 2;
	res[n - 1] = (A[n - 1] * 2) - res[0];

	for (int i = n - 2; i >= 1; i--)
		res[i] = (A[i] * 2) - res[i + 1];

	rep (i, 0, n)
		cout << res[i] << " ";
	cout << "\n";

	return 0;
}

Measured memory_bytes: 2944
#include <stdio.h>

int main(void)
{
    int x;
    int y;
    int r;
    int tmp;
    
    scanf("%d %d", &x, &y);
    
    if ( x < y) {
        tmp = y;
        y = x;
        x = tmp;
    }
    
    while ( y > 0 ) {
        r = x % y;
        x = y;
        y = r;
    }
    
    printf("%d\n", x);
    
    return 0;
}


Measured memory_bytes: 2108
import java.util.Scanner;
public class Main {
	public static void main(String[ ] args) {
		Scanner sc = new Scanner(System.in);
			while(sc.hasNext()) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				if(a==0 && b==0) {
					break;
				}
				else {
					for(int i = 0; i < a; i++) {
						for(int j = 0; j < b; j++) {
							System.out.print("#");
						}
						System.out.println();
					}
				}
				System.out.println();
			}
}
}


Measured memory_bytes: 36548
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    vector<long long> a(3);
    cin >> a[0] >> a[1] >> a[2];
    int K;
    cin >> K;
    sort(ALL(a));
    cout << a[0] + a[1] + (pow(2, K)) * a[2] << endl;
    return 0;
}

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

typedef double du ;
typedef string st ;
typedef long long ll ;
typedef long double ld ;
typedef long long int lli ;

#define vi vector <lli>
#define loop(num) for (lli i = 0 ; i < num ; i ++ )
#define loop2(num) for (lli j = 0 ; j < num ; j ++ )
#define loopcin(num , ar ) for (lli i = 0 ; i < num ; i ++ ) {cin >> ar [i] ;}
#define loopcout(num , ar) for (lli i = 0 ; i < num ; i ++ ) {cout << ar [i] << ' '; }
#define looppu(num , ar) for (lli i = 0 ; i < num ;  i++) {lli x ; cin >> x ; ar . push_back (x) ;}
#define loopin(num , ar) for (lli i = 0 ; i < num ;  i++) {lli x ; cin >> x ; ar . insert (x) ;}

#define forr(num1 , num2) for (lli i = num1 ; i < num2 ; i ++ )
#define forrcin(num1 , num2 , ar ) for (lli i = num1 ; i < num2 ; i ++ ) {cin >> ar [i] ;}
#define forrcout(num1 , num2 , ar) for (lli i = num1 ; i < num2 ; i ++ ) {cout << ar [i] << ' '; }

#define D2forrcin(num1_1 , num1_2 , num2_1 , num2_2 , A ) for (lli i = num1_1 ; i < num1_2 ; i ++){ for (lli j = num2_1 ; j < num2_2 ; j++){cin >> A[i][j] ;}}
#define D2forrcout(num1_1 , num1_2 , num2_1 , num2_2 , A ) for (lli i = num1_1 ; i < num1_2 ; i ++){ for (lli j = num2_1 ; j < num2_2 ; j++){cout << A[i][j] << ' ' ;}cout << endl ;}

#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

#define F first
#define S second
#define pb push_back
#define pf push_front
#define pob pop_back ()
#define pof pop_front ()

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

signed main ()
{
    fastio
    ll num , m = 0 , sum = 0 ;
    cin >> num ;
    while (num --){
        ll x ;
        cin >> x ;
        m = max (m , x) ;
        sum += x ;
    }
    cout << sum - m / 2 << endl ;

    return 0 ;
}

/*___________________________________________________________________functions___________________________________________________________________________*/



Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n;
    cin >> n;
    
    cout << n * (n-1) / 2 << endl;
    
    return 0;
}


Measured memory_bytes: 256
import sys
import numpy as np

n = int(sys.stdin.readline().rstrip())
x = []
y = []
for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    xy = [sys.stdin.readline().split() for _ in range(a)]
    if not xy:
        x.append(None)
        y.append(None)
        continue
    xi, yi = np.array(xy, np.int64).T
    x.append(xi-1)
    y.append(yi)

def main():

    ans = 0
    for comb in range(2 ** n):
        cnt = 0
        for i in range(n):
            if not comb >> i & 1:
                continue
            if x[i] is None:
                cnt += 1
                continue
            if np.count_nonzero(comb >> x[i] & 1 ^ y[i]):
                break
            cnt += 1
        else:
            ans = max(ans, cnt)
    return ans
                
if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 12496
function main(input) {
  const args = input.split(' ').map(n => parseInt(n, 10));
  const A = args[0],
        B = args[1],
        C = args[2];
  
  if (A * C <= B) {
    console.log(C);
  } else {
    console.log(Math.floor(B / A));
  }
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm(a, b) (a)/__gcd((a),(b))*(b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

const int dx[] = {0, -1, 1, 0};
const int dy[] = {-1, 0, 0, 1};

vector<int> Div(int n) {
    vector<int> ret;
    for(int i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);

            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

void aoki_dfs(int pos, int d);
void takahashi_dfs(int pos, int d);

vector<int> tree[SIZE];
int aoki_d[SIZE];
int takahashi_d[SIZE];
bool visit[SIZE];

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

    int n;
    int aoki, takahashi;
    cin >> n >> takahashi >> aoki;
    int m = n - 1;
    while(m--) {
        int a, b;
        cin >> a >> b;
        tree[a].pb(b);
        tree[b].pb(a);

    }
    aoki_dfs(aoki, 0);
    for(int i = 1; i <= n; ++i) {
        visit[i] = false;
        takahashi_d[i] = -1;

    }
    takahashi_dfs(takahashi, 0);

    int res = 0;
    for(int i = 1; i <= n; ++i) {
        if(takahashi_d[i] != -1) {
            res = max(res, aoki_d[i]);

        }

    }
    cout << res - 1 << endl;
    return 0;
}

void aoki_dfs(int pos, int d) {
    if(visit[pos]) return;
    visit[pos] = true;

    aoki_d[pos] = d;
    for(int i = 0; i < tree[pos].size(); ++i) {
        aoki_dfs(tree[pos][i], d + 1);

    }

    return;
}

void takahashi_dfs(int pos, int d) {
    if(visit[pos]) return;
    visit[pos] = true;
    if(d > aoki_d[pos]) return;
    takahashi_d[pos] = d;

    for(int i = 0; i < tree[pos].size(); ++i) {
        takahashi_dfs(tree[pos][i], d + 1);

    }

    return;
}


Measured memory_bytes: 12800
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define ll long long
#define INF 1<<31-1
#define LNF 9223372036854775807
#define PI 3.14159265358979
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
//#define MOD 998244353
#define NUM 200010
 
void swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
int abs(int a){if(a<0)return -a;return a;}
int dup(int a,int d){if(a%d==0)return a/d;else return a/d+1;}
int mod(int a,int m){if(a<0)return a%m+m;else return a%m;}

void swapl(ll* a,ll* b){ll tmp=*a;*a=*b;*b=tmp;}
ll absl(ll a){if(a<0)return -a;return a;}
ll dupl(ll a,ll d){if(a%d==0)return a/d;else return a/d+1;}
ll modl(ll a,ll m){if(a<0)return a%m+m;else return a%m;}

ll GCD(ll a,ll b){ll c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
ll LCM(ll a,ll b){return a*b/GCD(a,b);}

ll factorial(ll n, ll m) {return n < m ? 1 : n*factorial(n-1, m);}

int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

// ll dp[]

int main(){
  int r;

  scanf("%d", &r);

  printf("%f", 2.0*PI*(float)r);

  return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    ll n,k;
    cin>>n>>k;
    ll a=n%k;
    cout<<min(a,k-a)<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int b[] = new int[n - 1];
		for ( int i = 0; i < n - 1; i++ ) {
			b[i] = in.nextInt();
		}

		int sum = 0;
		sum += b[0];
		sum += b[n - 2];
		
		for(int i = 1; i <= n-2; i++) {
			sum += Math.min(b[i], b[i-1]);
		}
		
		System.out.println(sum);

		in.close();

	}
}

Measured memory_bytes: 23124
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
using namespace std;
#define MK make_pair
#define F first
#define S second
#define ege pair<int,pair<int,int>> //w,s,t
const int MX=1e9+7;






int main(){
    int v,e,r;
    vector<ege> E;
    int dis[10000];
    fill(dis,&dis[10000],MX);
    cin>>v>>e>>r;
    dis[r]=0;
    for(int i=0;i<e;i++){
        int s,t,d;
        cin>>s>>t>>d;
        E.push_back({d,{s,t}});
    }
    for(int i=0;i<e;i++){
        for(int t=0;t<e;t++){
            ege s=E[t];
            if(dis[s.S.F]==MX){continue;}
            dis[s.S.S]=min(dis[s.S.S],dis[s.S.F]+s.F);
        }
    }
    bool j=false;
    for(int t=0;t<e;t++){
        ege s=E[t];
        if(dis[s.S.F]==MX){continue;}
        if(dis[s.S.S]>dis[s.S.F]+s.F){j=true; break;}
    }
    if(j){cout<<"NEGATIVE CYCLE"<<endl;}
    else{
        for(int i=0;i<v;i++){
            if(dis[i]==MX){cout<<"INF"<<endl; continue;}
            cout<<dis[i]<<endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 3144
#!/usr/bin/python3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def main():
    N = int(inp())
    print(N ** 3)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
var lines: string[] = [];
var reader: any = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on("line", function(line: string) {
  lines.push(line);
});

reader.on("close", function() {
  var valueN: number = Number(lines[0].split(" ")[0]);

  var listA: number[] = lines[1]
    .split(" ")
    .map(function(value: string): number {
      return Number(value);
    });
  var sortedList: number[] = new Array();
  listA.forEach(x => {
    sortedList.push(x);
  });

  sortedList.sort((n1, n2) => n1 - n2);
  //.filter((x, i, self) => {
  //  self.indexOf(x) === i;
  //});
  var minDiff: number = 1000000000;
  var minDiffNum: number = 0;
  var tmpDiff: number = 0;
  for (var i = 0; i < sortedList.length - 1; i++) {
    tmpDiff = Math.abs(sortedList[sortedList.length - 1] / 2 - sortedList[i]);
    if (tmpDiff < minDiff) {
      minDiff = tmpDiff;
      minDiffNum = sortedList[i];
    }
  }
  console.log(sortedList[sortedList.length - 1], minDiffNum);
});


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

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

ll modPow(long long a, long long n, long long p) {
  if (n == 0) return 1; // 0乗にも対応する場合
  if (n == 1) return a % p;
  if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
  long long t = modPow(a, n / 2, p);
  return (t * t) % p;
}

ll factorual(ll n){
    ll ans = 1;
    for (ll i = 1; i <= n; i++){
        ans *= i;
        ans %= MOD;
    }
    ans %= MOD;
    return ans;

    //階乗を出力
    //入力:ll
    //出力:ll
}

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

    ll s;
    cin >> s;
    ll ans = 0;
    
    for (ll i = 1; i <= s/3; i++){
        ll n = s-(2*i)-1;
        ll k = i-1;

        ll c = factorual(n);

        ll x = factorual(k) * factorual(n-k);
        x %= MOD;

        c = c * modPow(x, MOD-2, MOD);
        c %= MOD;

        ans += c;
        ans %= MOD;

    }

    ans %= MOD;

    cout << ans << endl;
    
}

Measured memory_bytes: 3552
//かなしいなぁ
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int dm = 1 << 21;
char dn[dm], * di = dn, dt;
inline void putint(int X) {
	int keta = 0;
	char C[10];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}

const int K = 19;
const int KM = 1 << (K - 1);
int laz[1 << K];
int zero = 2e9;
void update(int L, int R, int X, int A, int l, int r) {
	if (r <= L || R <= l) return;
	if (L <= l && r <= R) {
		laz[A] = min(laz[A], X);
		return;
	}
	update(L, R, X, A * 2, l, (l + r) / 2);
	update(L, R, X, A * 2 + 1, (l + r) / 2, r);
}

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


	int N = getint(), Q = getint();
	int S[200000], T[200000], X[200000];
	rep(i, N) {
		S[i] = getint();
		T[i] = getint();
		X[i] = getint();
	}
	int D[200002];
	D[0] = -zero;
	D[Q + 1] = zero;
	rep1(i, Q) D[i] = getint();
	rep(i, 1 << K) laz[i] = zero;

	rep(i, N) {
		int L = lower_bound(D, D + Q + 2, S[i] - X[i]) - D;
		int R = lower_bound(D, D + Q + 2, T[i] - X[i]) - D;
		if (L < R) update(L, R, X[i], 1, 0, KM);
	}
	rep1(i, KM - 1) {
		laz[i * 2] = min(laz[i * 2], laz[i]);
		laz[i * 2 + 1] = min(laz[i * 2 + 1], laz[i]);
	}
	rep1(i, Q) {
		if (laz[KM + i] == zero) {
			*di++ = '-';
			*di++ = '1';
			*di++ = '\n';
		}
		else putint(laz[KM + i]);
	}

	fwrite(dn, 1, di - dn, stdout);

	Would you please return 0;
}

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

int main()
{
    string s , t;
    int n;
    cin>>n>>s>>t;
    
    for (int l = n; l >= 0; l--)
    {
        if ( s.substr(n-l) == t.substr(0,l) )
        {
            cout<<2*n-l<<endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
use std::str::FromStr;
use std::io::*;
use std::cmp::*;
use utils::*;

pub fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}

fn run<R: BufRead, W: Write>(i: R, o: &mut W) {
    let mut i = AtRead::from(i);
    let (n, a) = i.read2::<usize, usize>();
    let x = i.read_vec::<usize>(n);

    writeln!(o, "{}", solve(a, &x)).unwrap();
}
fn solve(a: usize, x: &[usize]) -> usize {
    let lower: Vec<_> = x.iter().filter(|&&x| x < a).map(|&x| a - x).collect();
    let upper: Vec<_> = x.iter().filter(|&&x| x > a).map(|&x| x - a).collect();
    let mids = x.iter().filter(|&&x| x == a).count();

    fn to_counts(x: &[usize]) -> Vec<usize> {
        let sum: usize = x.iter().sum();
        let mut t = vec![0; sum + 1];
        let mut c = 1;
        t[0] = 1;
        for &x in x {
            for i in (0..c).rev() {
                t[i + x] += t[i];
            }
            c += x;
        }
        t
    }
    let lower = to_counts(&lower);
    let upper = to_counts(&upper);

    let mut result: usize = 0;
    for i in 0..min(lower.len(), upper.len()) {
        result += lower[i] * upper[i];
    }
    result * (2 as usize).pow(mids as u32) - 1
}

mod utils {
    use super::*;

    pub struct AtRead<R: BufRead> {
        r: R,
        s: String,
    }

    macro_rules! fn_read {
        {$f:ident($($v:ident: $t:ident),*)} => {
            pub fn $f<$($t: FromStr),*>(&mut self) -> ($($t),*) {
                let i = &mut self.read_line().split(' ');
                $(
                    let $v = next(i);
                )*
                ($($v),*)
            }
        };
    }

    impl<R: BufRead> AtRead<R> {
        pub fn from(r: R) -> Self {
            AtRead {
                r: r,
                s: String::new(),
            }
        }
        pub fn read_line(&mut self) -> &str {
            self.s.clear();
            self.r.read_line(&mut self.s).unwrap();
            self.s.trim()
        }

        fn_read! { read2(v1: T1, v2: T2) }

        pub fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            self.read_line()
                .split(' ')
                .take(n)
                .map(|x| x.parse().ok().unwrap())
                .collect()
        }
    }

    fn next<'a, T: FromStr, I: std::iter::Iterator<Item = &'a str>>(i: &mut I) -> T {
        i.next().unwrap().parse().ok().unwrap()
    }

}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()
#define MOD 1000000007

int K[2010];

int main() {
	int N, X, Y;
	cin >> N >> X >> Y;
	for (int i = 0;i < 2010;i++)K[i] = 0;
	for (int i = 1;i <= N;i++) {
		for (int j = i + 1;j <= N;j++) {
			K[min({ j - i, abs(j - Y) + abs(i - X) + 1,abs(j - X) + abs(i - Y) + 1 })]++;
		}
	}
	for (int i = 1;i < N;i++) {
		cout << K[i] << endl;
	}
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>
#include <numeric>
#include <iomanip>
using namespace std;
int A[18];
int B[18];
int dp[1 << 18][18];

bool in_bit(int bit_set, int ind){
  if(((bit_set >> ind) & 1) == 1){
    return true;
  }
  return false;
}

int add_bit(int bit_set, int ind){
  return bit_set ^ (1 << ind);
}

int bit_set_size(int bit_set, int N){
  int ans = 0;
  for(int i = 0; i < N; i++){
    if(((bit_set >> i) & 1) == 1){
      ans ++;
    }
  }
  return ans;
}

int get_swap(int bit_set, int ind, int N){
  int ans = 0;
  for(int i = 0; i < N; i++){
    if(((bit_set >> i) & 1) == 1){
      if(i > ind){
        ans ++;
      }
    }
  }
  return ans;
}
int get_card_num(int ind, int org_ind){
  if(ind % 2 == org_ind % 2){
    return A[org_ind];
  }
  return B[org_ind];
}

int main(){
  int N;
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  for(int i = 0; i < N; i++){
    cin >> B[i];
  }

  for(int i = 0; i < (1 << N); i++){
    for(int j = 0; j < N; j++){
      dp[i][j] = INT_MAX;
    }
  }
  for(int i = 0; i < N; i++){
    dp[0][i] = 0;
  }

  for(int bit_set = 0; bit_set < (1 << N) - 1; bit_set ++){
    for(int i = 0; i < N; i++){
      if(dp[bit_set][i] != INT_MAX){
        for(int j = 0; j < N; j++){
          if(i == j){
            continue;
          }
          if(!in_bit(bit_set, j)){
            int cur_ind = bit_set_size(bit_set, N) + 1;
            int cur_card_num = get_card_num(cur_ind, j);
            int prev_card_num = get_card_num(cur_ind - 1, i);
            if(prev_card_num <= cur_card_num){
              int next_bit_set = add_bit(bit_set, i);
              dp[next_bit_set][j] = min(dp[next_bit_set][j], dp[bit_set][i] + get_swap(next_bit_set, j, N));
            }
          }
        }
      }
    }
  }

  int ans = INT_MAX;
  for(int i = 0; i < N; i++){
    int tmp = ((1 << N) - 1) ^ (1 << i);
    ans = min(ans, dp[tmp][i]);
  }

  if(ans == INT_MAX){
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 18688
import java.util.Scanner

object Main {

  def main(args: Array[String]): Unit = println {
    val sc = new Scanner(System.in)
    val (n, m) = (sc.nextInt(), sc.nextInt())
    val studentXs, studentYs = Array.fill(n)(0)
    val checkpointXs, checkpointYs = Array.fill(m)(0)
    for (i <- 0 until n) {
      studentXs(i) = sc.nextInt()
      studentYs(i) = sc.nextInt()
    }
    for (i <- 0 until m) {
      checkpointXs(i) = sc.nextInt()
      checkpointYs(i) = sc.nextInt()
    }
    solve(n, m, studentXs, studentYs, checkpointXs, checkpointYs)
  }

  def solve(n: Int, m: Int,
            studentXs: Array[Int], studentYs: Array[Int],
            checkpointXs: Array[Int], checkpointYs: Array[Int]): String = {
    val results = Array.fill(n)(0)
    for (i <- 0 until n) {
      val (x1, y1) = (studentXs(i), studentYs(i))
      var (result, longestDist) = (0, Int.MaxValue)
      for (j <- 0 until m) {
        val (x2, y2) = (checkpointXs(j), checkpointYs(j))
        val d = math.abs(x1 - x2) + math.abs(y1 - y2)
        if (d < longestDist) {
          result = j
          longestDist = d
        }
      }
      results(i) = result + 1
    }
    results.mkString("\n")
  }
}


Measured memory_bytes: 27304
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int
#define ulli unsigned long long int
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define loopl(i,a,b) for(lli i=a;i<b;i++) 
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(v) v.begin(), v.end()
#define mod 1000000007
#define mod2 1000000006
#define inf 1000000000000000000
#define lld long double
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<lli>
#define vii vector<int>
#define is indexed_set
#define eps 0.000001
#define endl '\n'
#define mo 998244353
#define pi 3.141592653589793
#define fi first
#define se second
using namespace std ;
typedef tree<pll,null_type,less<pll>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
void solve()
{
		string s;
		cin>>s;
		lli tem=0;
		lli n=s.size();
		for(lli i=0;i<n;i++){
			tem=(tem+s[i]-'0')%9;

		}
		if(tem==0)cout<<"Yes";
		else cout<<"No";

}
 
int main()
{
/////////////////////////////////////
    fastio;
   
/////////////////////////////////////  
    lli t,m;
    //cin>>t;
    t=1;
    m=1;
    while(t--)
    {
    	//cout<<"Case #"<<m<<":"<<endl;
    	solve();  
    	m++;  
    }
}

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

alp = [float("inf")]*200

for i in range(n):
    S = input()
    tmp = [0]*200
    for s in S:
        tmp[ord(s)] += 1
    for ind in range(200):
        alp[ind] = min(alp[ind],tmp[ind])

ans = ""
for i in range(200):
    ans += chr(i)*alp[i]
    
print(ans)

Measured memory_bytes: 65024
ans (0:_) = []
ans (n:xs) =
  let m = n `div` 4
      s = sum $ take m xs
      r = drop m xs
  in
    s:(ans r)

main = do
  c <- getContents
  let i = map read $ lines c :: [Int]
      o = ans i
  mapM_ print o

Measured memory_bytes: 3972
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> p;
typedef pair<p,p> pp;

int main() {
    int H, W;
    cin >> H >> W;
    int a[500][500];
    for(int i=0; i<H; ++i) {
        for(int j=0; j<W; ++j) cin >> a[i][j];
    }

    queue<pp> ope;
    int x = 0, y = 0;
    bool toright = true;
    for(int i=0; i + 1 < H * W; ++i) {
        int nx, ny;
        if(toright) {
            if(y + 1 != W) {nx = x; ny = y+1;}
            else {nx = x+1, ny = y; toright = false;}
        } else {
            if(y != 0) {nx = x; ny = y - 1;}
            else {nx = x+1, ny = y; toright = true;}
        }
        if(a[x][y] % 2) {
            --a[x][y]; ++a[nx][ny];
            ope.push(pp(p(x,y), p(nx,ny)));
        }
        x = nx; y = ny;
    }

    cout << ope.size() << endl;
    while(!ope.empty()) {
        pp tmp = ope.front(); ope.pop();
        cout << tmp.first.first + 1 << " ";
        cout << tmp.first.second + 1 << " ";
        cout << tmp.second.first + 1 << " ";
        cout << tmp.second.second + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 5120
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1001001001
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
using namespace std;
ll n,m;




//注意

vector<set<ll>> s(300000);
vector<pair<ll ,bool>> f(3000000);
deque<ll> q;


void search(){

   // cout<<endl;
    search();
}

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

    ll c,d,maxi=0,mini=INF,sum=0;
    string str;
    cin>>n>>m;
    vector<ll> a(m);
    vector<ll> b(m);
    s.resize(n);
    f.resize(n);
    rep(i,n) f[i].second=false;
    rep(i,m){
        cin>>c>>d;
        c--;
        d--;
        s[c].insert(d);
        s[d].insert(c);
    }
    q.push_back(0);
    while(!q.empty()){
    if(q.size()==0) continue;;
    ll num=q.front();
    q.pop_front();
    //if(f[num].second==true) return;
    //cout<<"num= "<<num<<" ";
    for(auto itr=s[num].begin();itr!=s[num].end();++itr){
        //cout<<*itr<<" ";
        if(f[*itr].second==false){
            f[*itr].second=true;
            f[*itr].first=num;
            q.push_back(*itr);
        }
    }
    }    ll flag=1;
    rep(i,n){
        if(f[i].second==false) flag=0;
    }
    if(flag==0) No;
    else{
        Yes;
        for(ll i=1;i<n;i++){
            cout<<f[i].first+1<<endl;
        }
    }

    return 0;
}


Measured memory_bytes: 86876
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	
	public static void main(String[] args) throws IOException {
		final Scanner sc = new Scanner(System.in);
		
		final int N = sc.nextInt();
		int[] arr = new int[N];
		for(int i = 0; i < N; i++){
			arr[i] = sc.nextInt();
		}
		
		long min = Integer.MAX_VALUE;
		for(int p = -100; p <= 100; p++){
			long sum = 0;
			
			for(int i = 0; i < N; i++){
				sum += (arr[i] - p) * (arr[i] - p);
			}
			
			min = Math.min(min, sum);
		}
		
		System.out.println(min);
	}
 
	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;
 
		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}	
 
		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}
 
		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}
 
		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public void close() throws IOException {
			br.close();
		}
	}
}

Measured memory_bytes: 8020
#include<cstdio>
char ch[10000];

int main(){
    scanf("%s", ch);
    for(int i = 1; ch[i] != '\0'; i ++)
        if(ch[i-1] == 'A' && ch[i] == 'C'){
            printf("Yes");
            return 0;
        }
    printf("No");
    return 0;
}


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

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int memo[1000000];
int res(int n) {
  if(n == 0) return 0;
  if(memo[n] != -1) return memo[n];
  int ans = n;
  for(int i = 1; i <= n; i *= 6) {
    ans = min(ans, res(n - i) + 1);
  }

  for(int i = 1; i <= n; i *= 9) {
    ans = min(ans, res(n - i) + 1);
  }

  return memo[n] = ans;
}

int main() {
  ll N, M;
  cin >> N >> M;
  ll ans = 0;
  if(N == 1 && M == 1) { cout << 1; return 0; } 
  if(N == 1 || M == 1) { ans = max(N, M) - 2; cout << ans; return 0;}

  ans = N * M - 2 * N - 2 * ( M - 2);

  cout << ans; 

  return 0;
}

Measured memory_bytes: 256
def friendships(N: int, K: int)->list:
    MAX = (N-1)*(N-2)//2
    if K > MAX:
        return []

    res = []
    for v in range(2, N+1):
        res.append((1, v))

    u = 2
    v = 3
    for _ in range(K, MAX):
        res.append((u, v))
        if v == N:
            u += 1
            v = u + 1
        else:
            v += 1

    return res


if __name__ == "__main__":
    N, K = map(int, input().split())

    ans = friendships(N, K)
    if ans:
        print(len(ans))
        for u, v in ans:
            print(u, v)
    else:
        print(-1)


Measured memory_bytes: 3956
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto abc = readln.split.to!(long[]);
    auto A = abc[0];
    auto B = abc[1];
    auto C = abc[2];

    writeln((A+B >= C ? C : A+B+1) + B);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define ull unsigned long long
#define N 100005
#define mod 1000000007
//#define mod 1e18
#define boost ios_base::sync_with_stdio(false);cin.tie(0)
#define prec(n) fixed<<setprecision(n)

#define tr(it,c) for(it = c.begin() ; it!=c.end() ; it++)
int inf = INT_MAX ;
ll modulo(ll num,ll MOD=mod){ return ((num%MOD)+MOD)%MOD;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),MOD-2,MOD); }
ll gcd(ll a,ll b){ return ((b==0) ? a:gcd(b,a%b));}
ll fac[2*N];

ll sub(ll a,ll b){
	return (a-b+mod)%mod;
}

ll mul(ll a,ll b){
	return (a*b)%mod;
}

ll binomial(ll a,ll b){
	if(a<0||b<0||b>a)
		return 0;
	
	ll temp = (fac[a]*inv(fac[b]))%mod;
	temp = (temp*inv(fac[a - b]))%mod;
	return temp;
}

ll f(ll a,ll b){
	return binomial(a+b,b);
}

int main(){
	boost;
	fac[0] = 1;
	for(int i = 1;i<2*N;i++){
		fac[i] = (fac[i-1]*i)%mod;
	}
	
	ll h,w,n;
	cin>>h>>w>>n;
	vector<pair<int,int>> v;
	
	for(int i = 0;i<n;i++){
		ll a,b;
		cin>>a>>b;
		v.push_back(make_pair(a,b));
	}
	
	v.push_back(make_pair(h,w));
	sort(v.begin(),v.end(),[&](pair<int,int> a,pair<int,int> b){
		return a.first + a.second < b.first + b.second;
	});
	
	debug() << imie(v);
	vector<int> dp(n+1);
	
	for(int i = 0;i<n+1;i++){
		ll ans = binomial(v[i].first + v[i].second - 2, v[i].first - 1);
		debug()<< imie(ans);
		for(int j = i-1;j>=0;j--){
			if(v[j].first<=v[i].first&&v[j].second<=v[i].second)
				ans = sub(ans,mul(dp[j],f(v[i].first - v[j].first, v[i].second - v[j].second)));
		}
		dp[i] = ans;
	}
	debug() << imie(dp);
	cout<<dp[n]<<endl;
	return 0;
}



Measured memory_bytes: 5260
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n = ir()
f0 = []
f1 = []
for i in range(n):
    x,y = lr()
    f0.append(x-y)
    f1.append(x+y)
print(max(max(f0)-min(f0), max(f1)-min(f1)))

Measured memory_bytes: 102620
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x)) 
    
using namespace std;

const int MOD = 998244353;

inline void add(int &x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
}

inline void sub(int &x, int y) {
	x -= y;
	if(x < 0) x += MOD;
}
   
int main() {
#if 0
    ifstream cin("C.in");
    ofstream cout("C.out");
#endif
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

	string str;
	cin >> n >> str;
	for(i = 0; i < n; i++) {
		str[i] -= '0';
	}

	vector <int> pw(n + 1, 1);
	for(i = 1; i <= n; i++) {
		pw[i] = (pw[i - 1] * 2) % MOD;
	}

	vector < pair <int, int> > divi(1);
	divi[0] = {2 * n, 1};
	for(i = 0; i < n; i++) {
		if(str[i] == 1)
			add(divi[0].second, pw[n - i - 1]);
	}

	int ans = 0;
	for(int k = 2; k < 2 * n; k += 2) {
		if((2 * n) % k > 0 || ((2 * n) / k) % 2 == 0) continue;

		bool bad = 0;
		for(i = 0; i < n; i++) {
			if(i < n - k && str[i] != str[i + k]) bad = 1;
			if(i >= n - k && str[i] == str[(i + k) % n]) bad = 1;
		}
		
		vector <bool> vis(n), need(n);
		int num = __gcd(n, k);
		int cnt = 1 - bad, ok = 0;
		
		for(i = 0; i < n; i++) {
			if(vis[i] && need[i] > str[i]) {
				break;
			}
			if(vis[i] && need[i] < str[i]) {
				add(cnt, pw[num]);
				break;
			}
			if(vis[i]) continue;
			
			int j = i, cur = str[i];
			while(vis[j] == 0) {
				vis[j] = 1, need[j] = cur;
				if(j + k >= n) 
					cur ^= 1;
				j = (j + k) % n;
			}

			num--;	
			if(str[i] == 1) {
				add(cnt, pw[num]);
			}
		}
		
		divi.push_back({k, cnt});
		//cerr << k << " " << cnt << "\n";
	}

	sort(divi.begin(), divi.end());

	for(auto &a : divi) {
		for(auto &b : divi) {
			if(a.first != b.first && a.first % b.first == 0) {
				sub(a.second, b.second);
			}
		}
		ans = (ans + 1LL * a.second * a.first) % MOD;
		//cerr << a.first << " " << a.second << "\n";
	}

	cout << ans;
            
	return 0;
}

Measured memory_bytes: 1428