akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define mod 1000000007
#define INF (ll)1e19
#define N 2000006

using namespace std;

int n, m, a[105][105], x[105], y[105], us[105], p, ans;
void dfs(int x) {
    p++;
    us[x] = 1;
    for (int i = 1; i <= n; i++)
        if (!us[i] && a[x][i]) dfs(i);
}
int main() {
    //freopen("txt.in", "r", stdin);
    //freopen("txt.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> x[i] >> y[i], a[x[i]][y[i]] = a[y[i]][x[i]] = 1;
    for (int i = 1; i <= m; i++) {
        a[x[i]][y[i]] = a[y[i]][x[i]] = 0;
        memset(us, 0, sizeof(us));
        p = 0;
        dfs(1);
        if (p != n) ans++;
        a[x[i]][y[i]] = a[y[i]][x[i]] = 1;
    }
    cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip()
na = lambda: list(map(int, stdin.readline().split()))
ni = lambda: int(ns())
sys.setrecursionlimit(200000)

(n,u,v)=na()
u -= 1
v -= 1

g = [[] for _ in range(n)]

for i in range(0, n-1):
    (a, b) = na()
    g[a-1].append(b-1)
    g[b-1].append(a-1)


dep1 = [0] * n
dep2 = [0] * n
def dfs(now, pre, d, dep):
    dep[now] = d
    for nex in g[now]:
        if pre == nex:
            continue
        dfs(nex,now,d+1,dep)


dfs(u, -1, 0, dep1)
dfs(v, -1, 0, dep2)

ret = 0
for i in range(n):
    if dep1[i] < dep2[i]:
        ret = max(ret, dep2[i]-1)
print(ret)


Measured memory_bytes: 105004
#include <cstdio>
#include <iostream>

#define WHITE '.'
#define BLACK '#'

using namespace std;

int main() {
	int white = 0, black = 0;
	int n;
	char c;
	cin >> n;
	char* s = new char[n];
	for (int i = 0; i < n; i++) {
		cin >> c;
		s[i] = c;
		if (c == WHITE)white++;
	}

	int min = n;
	int all;
	for (int i = 0; i < n; i++) {
		all = black + white;
		if (all <= min)min = all;

		if (s[i] == BLACK) {
			black++;
		}
		else {
			white--;
		}
	}

	all = black + white;
	if (all <= min)min = all;

	cout << min;

}

Measured memory_bytes: 1016
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define fi first
#define se second
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define go_t int t;cin>>t;for(int tt=1;tt<=t;tt++)
#define set_ar(arr,v) memset(arr,v,sizeof(arr))
#define trace2(x, y)             cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)       cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; // order_of_key
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const ll inf = 0x3f3f3f3f3f3f3f3fll;//4x10e18
const int maxx = 3000000;
#define PI 3.14159265
int n,m,k;
int main()
{
    fastio;
    cin>>n>>m;
    int a[n];
    int sum = 0;
    for(int i=0;i<n;i++){cin>>a[i];sum+=a[i];}
    sort(a,a+n);
    reverse(a,a+n);
    int num = a[m-1];
    if((num*4*m)<sum)
        cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#define FOR(i, l, r) for(int i = l; i <= r; ++i)

using namespace std;

int ans[110][110], a, b, l, r;

int main()
{
    scanf("%d%d", &a, &b);
    l = 51, r = 50;
    for(int tmp = b - 1, now = 100; tmp; --tmp)
    {
        if (now == 100) l -= 2, now = 2;
        ans[l][now] = 1; now += 2;
    }
    for(int tmp = a - 1, now = 100; tmp; --tmp)
    {
        if (now == 100) r += 2, now = 2;
        ans[r][now] = 1; now += 2;
    }
    --l, ++r;
    printf("%d 99\n", r - l + 1);
    FOR(i, l, 50)
    {
        FOR(j, 1, 99) if (ans[i][j]) printf("#"); else printf(".");
        puts("");
    }
    FOR(i, 51, r)
    {
        FOR(j, 1, 99) if (ans[i][j]) printf("."); else printf("#");
        puts("");
    }
    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int sec, min, hour;
        sec = sc.nextInt();

        hour = sec / 3600;
        min = (sec%3600) / 60;
        sec = sec % 60;

        System.out.println(hour+":"+min+":"+sec);
    }
}


Measured memory_bytes: 26300
def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)

if __name__ == "__main__":
    K = int(input())
    S = [1,2,3,4,5,6,7,8,9]
    for i in range(1,10):
        for k in range(3**i):
            a = base10to(k,3)
            a = "0"*(i-len(a))+a
            for j in range(1,10):
                s = str(j)
                state = 1
                j0 = j
                for l in a:
                    if int(l) == 0:
                        j0 -= 1
                        if j0<0:
                            state = 0
                            break
                        s = s + str(j0)
                    elif int(l) ==1 :
                        s = s+str(j0)
                    else:
                        j0 += 1
                        if j0 ==10:
                            state = 0
                            break
                        s = s + str(j0)
                if state:
                    S.append(int(s))
        S.sort()
    print(S[K-1])

Measured memory_bytes: 84144
from collections import defaultdict


def main():
    d = defaultdict(lambda: 0)
    n = int(input())
    for _ in range(n):
        a = input()
        d[a] += 1

    cnt = 0
    for key, value in sorted(d.items(), key=lambda x: x[1]):
        if value%2 == 1:
            cnt += 1
    print(cnt)
    

if __name__ == "__main__":
    main()

Measured memory_bytes: 23636
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
using namespace std;

struct Node{
    int key;
    Node *right, *left, *parent;
};

Node *root, *NIL;

Node * find(Node *u, int k) {
    while(u != NIL && k != u->key) {
        if(k < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

void insert(int k){
    Node *y = NIL;
    Node *x = root;
    Node *z;

    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while(x != NIL){
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }

    z->parent = y;
    if(y == NIL){
        root = z;
    }else{
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}

void inorder(Node *u){
    if(u == NIL) return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}

void preorder(Node *u){
    if(u == NIL) return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

int main(){
    int n, i, x;
    string com;
    scanf("%d", &n);

    for(i = 0; i < n; i++){
        cin >> com;
        if(com == "find"){
            scanf("%d", &x);
            Node *t = find(root, x);
            if(t != NIL) printf("yes\n");
            else printf("no\n");
        }else if(com == "insert"){
            scanf("%d", &x);
            insert(x);
        }else if(com == "print"){
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}


Measured memory_bytes: 22016
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,s,n) for(int i = s; i < (int)(n); i++)

int main() {
  int n,ans = 0;
  cin >> n;
  vector<ll>x(n);
  vector<ll>y(n);
  rep(i,0,n) cin >> x[i] >> y[i];
  rep(i,0,n-1){
    rep(j,i+1,n){
      int cnt = 0;
      ll sx = x[i]-x[j];
      ll sy = y[i]-y[j];
      rep(k,0,n-1){
        rep(l,k+1,n){
          if((x[k]-x[l] == sx && y[k]-y[l] == sy)||(x[k]-x[l] == -sx && y[k]-y[l] == -sy)) cnt++;
        }
      }
      ans = max(ans,cnt);
    }
  }
  cout << n-ans << endl;
}

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

int a[10005];
int res[10005];

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int h,w;cin>>h>>w;
  int n;cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int p=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<a[i];j++){
      res[p++]=i+1;
    }
  }
  for(int y=0;y<h;y++){
    for(int x=0;x<w;x++){
      if(x>0)cout<<' ';
      int t = y*w;
      if(y%2==1){
        t+=(w-x-1);
      }else{
        t+=x;
      }
      cout<<res[t];
    }
    cout<<endl;
  }

  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <string.h>

using namespace std;

struct Node
{
	long long key;
	Node *next, *prev;
};

void insertNode(Node* head, long long key) {

	Node* temp = new Node;
	temp->key = key;
	temp->next = head->next;
	temp->prev = head;
	head->next->prev = temp;
	head->next = temp;
}

void deleteNode(Node* head, Node* n) {
	if (n == head) {
		return;
	}
	n->prev->next = n->next;
	n->next->prev = n->prev;
	delete n;
}

Node* searchNodeKey(Node* head, long long key) {
	Node* temp = head->next;
	while ( !(temp == head || temp->key == key) ) {
		temp = temp->next;
	}
	return temp;
}

void deleteNodeKey(Node* head, long long key) {

	deleteNode(head, searchNodeKey(head, key));
}

void deleteFirst(Node* head) {
	deleteNode(head, head->next);
}

void deleteLast(Node* head) {
	deleteNode(head, head->prev);
}

void displayList(Node* head) {

	Node* temp = head->next;
	bool first = true;
	while (temp != head) {
		if (first) {
			printf("%lld", temp->key);
			first = false;
		}
		else {
			printf(" %lld", temp->key);
		}
		temp = temp->next;
	}
	printf("\n");
}

int main() {

	int n; scanf("%d", &n);

	Node* head = new Node;
	head->next = head;
	head->prev = head;

	char cmd[20];
	long long key = 0;
	for (int i = 0; i < n; i++) {
		scanf("%s", cmd);
		if (strcmp("insert", cmd) == 0) {
			scanf("%lld", &key);
			insertNode(head, key);
		}
		else if (strcmp("delete", cmd) == 0) {
			scanf("%lld", &key);
			deleteNodeKey(head, key);
		}
		else if (strcmp("deleteFirst", cmd) == 0) {
			deleteFirst(head);
		}
		else if (strcmp("deleteLast", cmd) == 0) {
			deleteLast(head);
		}
	}

	displayList(head);

	return 0;
}



Measured memory_bytes: 34364
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, a, b) for(int i = (a); i <= (b); i++)
#define PER(i, a, b) for(int i = (a); i >= (b); i--)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define all(S) (S).begin(), (S).end()
#define pf push_front
#define pb push_back
#define mk make_pair
#define S second
#define F first
typedef long long ll;
typedef long double lf;
typedef pair<int, ll> il;
const int MAX = 1e5+5;
vector<int> adj[MAX];
int N, M, ans, h[MAX];

void solve(int u) {
	if(h[u]) return;
	h[u] = 1;
	rep(i, 0, adj[u].size()) {
		int v = adj[u][i];
		solve(v);
		h[u] = max(h[u], 1 + h[v]);
	}
	ans = max(ans, h[u]);
}

int main(int argc, char *argv[]) {
	int u, v;
	scanf("%d%d", &N, &M);
	rep(i, 0, M) {
		scanf("%d%d", &u, &v);
		adj[u].pb(v);
	}
	REP(i, 1, N) solve(i);
	printf("%d\n", ans-1);
	return 0;
}


Measured memory_bytes: 8192
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt64)
}

func readString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	s := readString()
	x, _ := strconv.Atoi(s)
	fx := 0
	for _, c := range s {
		v, _ := strconv.Atoi(string(c))
		fx += v
	}
	if x%fx == 0 {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 640
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << "\n";
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef uint64_t ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;

mt19937 rng(803);

void chmax(ll& x, ll y) {
    if (x < y) x = y;
}

const unsigned long long MOD = 100000007;


// Rolling hash
//template <unsigned long long mod>
//struct RollingHash {
//    vector<unsigned long long> hashed, power;
//
//    RollingHash(const string& s, const unsigned long long base = 10007) : hashed(s.size() + 1, 0), power(s.size() + 1, 0) {
//        power[0] = 1;
//        REP(i, s.size()) {
//            power[i + 1] = power[i] * base;
//            hashed[i + 1] = hashed[i] * base + s[i];
//        }
//    }
//
//    // [l, r)
//    unsigned long long get(int l, int r) {
//        return hashed[r] - hashed[l] * power[r - l];
//    }
//};

// 2^61-1 mod

struct RollingHash {
    const ull MOD = (1ULL << 61) - 1;
    ull base;
    vector<ull> power, hashed;

    ull mod(ull x) {
        ull xl = x >> 61, xr = x & ((1ULL << 61) - 1);
        ull ret = xl + xr;
        if (ret > MOD) ret -= MOD;
        return ret;
    }

    ull mul(ull a, ull b) {
        ull al = a >> 31, ar = a & ((1ULL << 31) - 1);
        ull bl = b >> 31, br = b & ((1ULL << 31) - 1);
        ull p = al * br + bl * ar;
        ull pl = p >> 30, pr = p & ((1ULL << 30) - 1);
        return al * bl * 2 + pl + (pr << 31) + ar * br; // never overflow
    }

    ull add(ull a, ull b) {
        return mod(a + b);
    }

    ull sub(ull a, ull b) {
        return mod(a + (MOD << 2) - b);
    }

    RollingHash(const string& s, ull base = 3083) : power(s.size() + 1), hashed(s.size() + 1) {
        power[0] = 1;
        hashed[0] = 0;
        REP(i, s.size()) {
            power[i + 1] = mul(power[i], base);
            hashed[i + 1] = add(mul(hashed[i], base), s[i]);
        }
    }

    // get hash of [l, r)
    ull get(int l, int r) {
        return sub(hashed[r], mul(hashed[l], power[r-l]));
    }
};


int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    string s, t; cin >> s >> t;

    if(t.size() > s.size()) {return 0;}

    RollingHash rhs(s), rht(t);

    REP(i, s.size() - t.size() + 1) {
        if (rhs.get(i, i + (int)t.size()) == rht.get(0, t.size())) {
            print(i);
        }
    }
}



Measured memory_bytes: 19720
n , a= map(int , input().split())
arr = list(map(int , input().split()))
dp = [ [[ 0 for j in range(0 , a*(n+2))] for k in range(0 , n+2)] for i in range(0,n+2)]
dp[0][0][0]=1
b=[0 for i in range(0 , n+1)]
for i in range(0 , n):
	b[i+1]=arr[i]
for i in range(1 , n+1):	# choosing only first i elements
	for j in range(0 , i+1):# choosing only j elements from first i elements
		for k in range(0 , a*(n)+2):# no of ways of forming a sum k taking j elements out of i elements
			if k<b[i]:
				dp[i][j][k]=dp[i-1][j][k]
			else:
				dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-b[i]]
tot = 0
for i in range(1 , n+1):
	tot = tot + dp[n][i][(i)*a]
print(tot)

Measured memory_bytes: 129212
#include<stdio.h>
int main()
{
    int x,y;
    scanf("%d%d",&x,&y);
    int a=(x+y);
    if(a%2==0)
    {
        printf("%d",a/2);
    }
    else
    {
        printf("IMPOSSIBLE");
    }
    return 0;
}


Measured memory_bytes: 128
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func blockCount(V []int) (int, int, int, int) {
	var vnum1, vcnt1, vnum2, vcnt2 int

	cnt, N := 1, len(V)
	for i := 1; i < N; i++ {
		if V[i] == V[i-1] {
			cnt++
		} else {
			if cnt >= vcnt1 {
				vnum2, vcnt2 = vnum1, vcnt1
				vnum1, vcnt1 = V[i-1], cnt
			} else if cnt >= vcnt2 {
				vnum2, vcnt2 = V[i-1], cnt
			}
			cnt = 1
		}
	}
	if cnt >= vcnt1 {
		vnum2, vcnt2 = vnum1, vcnt1
		vnum1, vcnt1 = V[N-1], cnt
	} else if cnt >= vcnt2 {
		vnum2, vcnt2 = V[N-1], cnt
	}

	return vnum1, vcnt1, vnum2, vcnt2
}

func intMin(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func main() {
	sc.Split(bufio.ScanWords)

	N := scanInt()
	V1, V2 := make([]int, N/2), make([]int, N/2)
	for i := 0; i < N; i++ {
		if i%2 == 0 {
			V1[i/2] = scanInt()
		} else {
			V2[i/2] = scanInt()
		}
	}
	sort.Ints(V1)
	sort.Ints(V2)

	v1num1, v1cnt1, _, v1cnt2 := blockCount(V1)
	v2num1, v2cnt1, _, v2cnt2 := blockCount(V2)

	var ans int
	if v1num1 != v2num1 {
		ans = N - v1cnt1 - v2cnt1
	} else {
		ans = intMin(N-v1cnt1-v2cnt2, N-v1cnt2-v2cnt1)
	}
	fmt.Println(ans)
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
#ifdef _debug
#define dout(i) cout << #i << ' ' << i << ' '
#else 
#define dout(i) //
#endif
using ll = long long;
using ull = unsigned long long;
using ul = unsigned;
const int maxn = 101;
const int maxq = 1000000;
const int tomod = 1000000007;
int n, k;
ll dp[maxn][maxq];/*, pf[maxn][maxq];*/
int v[maxq], vn;
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	{
		set<int> val; 
		for(int i = 1;i * i <= n;++i)v[++vn] = i, v[++vn] = n/i;
		sort(v+1, v+1 + vn);
		// for(auto &i : val)v[++vn] = i;
	}
	fill(dp[0], dp[0] + maxq, 1);
	for(int i = 1;i <= k;++i){
		for(int j = 1;j <= vn;++j){
			dp[i][j] = ((v[j]-v[j-1]) * (dp[i-1][lower_bound(v+1, v+1+vn, n/v[j]) - v]) % tomod + dp[i][j-1]) % tomod;
		}
	}
	cout << dp[k][vn] << '\n';
}

Measured memory_bytes: 260608
ar = gets.split.map(&:to_i).sort

x = ar[2] - ar[0]
y = ar[2] - ar[1]

if x.even? && y.even?
  p (x / 2) + (y / 2)
elsif x.even? && y.odd?
  p (x / 2) + (y / 2 + 1) + 1
elsif x.odd? && y.odd?
  x -= 1
  y -= 1
  p (x / 2) + (y / 2) + 1
else
  p (y / 2) + (x / 2 + 1) + 1
end

Measured memory_bytes: 1788
n, m = map(int, input().split())

PS = {}
for _ in range(m):
    p, s = input().split()
    try:
        PS[int(p)].append(s)
    except KeyError:
        PS[int(p)] = [s]

a, b = 0, 0
for S in PS.values():
    if "AC" in S:
        for s in S:        
            if s == "AC":
                a += 1
                break
            if s == "WA":
                b += 1

print(a, b)

Measured memory_bytes: 28020
// Collatz Problem

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ios>
#include <iomanip>
#include <string>
#include <numeric>

using namespace std;

int s;

int main() {
    cin >> s;

    int count = 0;

    if (s == 1 || s == 2) {
        cout << 4 << endl;
        return 0;
    }

    int tmp;
    int i = 1;
    for (;; i++) {
        if (s == 1) {
            break;
        }
        if (s % 2 == 0) {
            s /= 2;
        } else {
            s = 3*s + 1;
        }
    }

    cout << i + 1 << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<random>

using namespace std;
typedef long long int I;
#define INF 2,147,483,646 //intの最大値-1

int keta(int a){
    int count=0;
    while(a!=0){
        a/=10;
        count++;
    }
    return count;
}

/*
https://atcoder.jp/contests/abc153/tasks/abc153_e
*/

int main(){
    int h,n;
    cin>>h>>n;
    vector<int> A(n),B(n);
    for(int i=0;i<n;i++){
        cin>>A[i]>>B[i];
    }

    int dp[100000];
    for(int i=0;i<pow(10,5);i++){
        dp[i]=pow(10,9);
    }
    dp[0]=0;

    for(int i=1;i<=h;i++){
        for(int j=0;j<n;j++){
            if(i-A[j]>=0){
                dp[i] = min(dp[i],dp[i-A[j]]+B[j]);
            }
            else{
                dp[i] = min(dp[i],B[j]);
            }
        }
    }
    cout<<dp[h]<<endl;


}//カモンAC







/*もらうdp
int main(){
    long long int n,h;
    bool flag=false;
    int m=0;
    int dp[100000];
    for(int i=0;i<100000;i++){
        dp[i]=pow(10,9);
    }
    dp[0]=0;

   
    cin>>h>>n;
    vector<int> A(n),B(n);
    for(int i=0;i<n;i++){
        cin>>A[i]>>B[i];
        m=max(m,B[i]);
    } //A->AT, B->MP

    for(int i=0;i<=h;i++){
        for(int j=0;j<n;j++){
            dp[i+A[j]] = min(B[j]+dp[i], dp[i+A[j]]);
        }
    }
    int ans=dp[h];
    for(int i=h;i<h+m;i++){
        ans=min(ans,dp[i]);
    }
    
    cout<<ans<<endl;
   
    return 0;
} //カモンAC
*/

Measured memory_bytes: 640
#include <iostream>
#include <cstdint>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <tuple>
#include <cassert>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

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

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 (b<a) { a=b; return 1; } return 0; }

template <LL MOD=1000000007> class MODLL {
public:
  LL x;
  MODLL(const LL _x) : x(_x % MOD) {};
  MODLL operator+(const MODLL rhs) const { return MODLL(*this) += rhs; }
  MODLL operator-(const MODLL rhs) const { return MODLL(*this) -= rhs; }
  MODLL operator*(const MODLL rhs) const { return MODLL(*this) *= rhs; }
  MODLL operator/(const MODLL rhs) const { return MODLL(*this) /= rhs; }
  MODLL& operator+=(const MODLL rhs) { x += rhs.x; x %= MOD; return *this; }
  MODLL& operator-=(const MODLL rhs) { x -= rhs.x; x %= MOD; if(x<0) x += MOD; return *this; }
  MODLL& operator*=(const MODLL rhs) { x *= rhs.x; x %= MOD; return *this; }
  MODLL inv() const {
    if(x == 0) { throw "does not have inverse"; }
    LL a = x, b = MOD, u = 1, v = 0;
    while (b) {
      long long t = a / b;
      a -= t * b; swap(a, b);
      u -= t * v; swap(u, v);
    }
    u %= MOD;
    if (u < 0) u += MOD;
    return MODLL(u);
  }
  MODLL& operator/=(const MODLL rhs) { (*this) *= rhs.inv(); return *this; }
  MODLL pow(ULL n) const {
    MODLL res = 1;
    MODLL a = x;
    while (n > 0) {
      if (n & 1) res *= a;
      a = a * a;
      n >>= 1;
    }
    return res;
  }
};

typedef MODLL<> ML;


void test() {
  {
    ML x = 3;
    assert(x.pow(45).x == 644897553);
  }
  {
    for(int i=1; i<13; i++) {
      MODLL<13> x = i;
      assert( (x.inv().x * i) % 13 == 1 );
    }
  }
}


int main() {
  LL N, Q;
  cin >> N >> Q;

  typedef std::tuple<LL,LL,LL> T;
  std::vector<T> blocks;
  for(LL i=0; i<N; i++) {
    LL s,t,x;
    cin >> s >> t >> x;
    blocks.emplace_back( std::make_tuple(x,s-x,t-x) );
  }
  std::sort( blocks.begin(), blocks.end() );  // sort by x

  typedef std::pair<LL,LL> P;
  std::set<P> queries;  // sort by D
  for(LL i=0; i<Q; i++) {
    LL d;
    cin >> d;
    queries.insert( std::make_pair(d,i) );
  }

  std::vector<LL> ans(Q,-1);
  for(const T b: blocks) {
    LL x = std::get<0>(b);
    LL s = std::get<1>(b);
    LL t = std::get<2>(b);
    auto it = queries.lower_bound( std::make_pair(s,-1) );
    while( it != queries.end() ) {
      LL d = it->first;
      if( d >= t ) break;
      LL i = it->second;
      ans[i] = x;
      queries.erase(it++);
    }
  }

  for(LL a: ans) {
    std::cout << a << std::endl;
  }

  return 0;
}



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

int64_t	count_2_5(int N, int P, string S)
{
	int64_t	count = 0;
	for (int i = 0; i < N; ++i) {
		if (!((S.at(i) - '0') % P))
			count += (i + 1);
	}
	return count;
}

int64_t	count_other(int N, int P, string S)
{
	int64_t	count = 0;
	unordered_map<int, int64_t>	count_map;
	int	mod;
	int	digit_mod = 1;
	for (int i = N - 1; i >= 0; --i) {
		if (i == N - 1) {
			mod = (S.at(i) - '0') % P;
		} else {
			digit_mod *= 10;
		   	digit_mod %= P;
			mod += digit_mod * (S.at(i) - '0');
			mod %= P;
		}
		if (mod == 0)
			++count;
		if (count_map.count(mod)) {
			count += count_map.at(mod);	
			++count_map[mod];
		} else {
			count_map[mod] = 1;
		}
	}
	return count;
}

int	main()
{
	int	N, P;
	cin >> N >> P;
	string	S;
	cin >> S;
	int64_t	count;
	if (P == 2 || P == 5)
		count = count_2_5(N, P, S);
	else
		count = count_other(N, P, S);
	cout << count << endl;
}


Measured memory_bytes: 1028
#include <stdio.h>

int main(void)
{
	int a,b,c;
	scanf("%d %d",&a,&b);
	if(a<b){
		c=b-a;
	}
	else if(a>b){
		c=a-b;
	}
	else{
		c=0;
	}
	printf("%d\n",c);
		
	
	return 0;
}


Measured memory_bytes: 2112
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define SZ(x) ((int)x.size())
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
const int N = 404000,mo=1e9+7,inf=0x3f3f3f3f;
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
int n;Pii a[N],s[N];
int qzmx[N],hzmn[N],v[N];
bool cmp(Pii x, Pii y){return x.se!=y.se?x.se<y.se:x.fi>y.fi;}
inline void modify(int p, int x){p++;while(p<=n+1)add(v[p],x),p+=p&-p;}
inline int query(int p){p++;int res=0;while(p)add(res,v[p]),p-=p&-p;return res;}
inline void solve(int n, Pii *s, int m){//s[1..m]
	static int p[N],f[N];rep(i,0,n)p[i]=0,f[i]=0;
	for(int i=m,j=n;i>=1;i--){
		while(j>s[i].se)p[j--]=s[i].fi;
	}
	f[0]=1;modify(0,f[0]);
	rep(i,1,n){
		f[i]=query(i-1)-(p[i]-1>=0?query(p[i]-1):0);
		f[i]=(f[i]+mo)%mo;modify(i,f[i]);
	}
	int res=query(n)-(s[m].fi-1>=0?query(s[m].fi-1):0);
	printf("%d\n",(res+mo)%mo);
}
int main(){
	
	scanf("%d",&n);
	rep(i,1,n)scanf("%d%d",&a[i].fi,&a[i].se);
	sort(a+1,a+n+1);
	qzmx[0]=-inf;rep(i,1,n)qzmx[i]=max(qzmx[i-1],a[i].se);
	hzmn[n+1]=inf;per(i,n,1)hzmn[i]=min(hzmn[i+1],a[i].se);
	rep(i,1,n){
		int L=1,R=i-1,pos=i;
		while(L<=R){
			int mid=(L+R)>>1;
			if(a[i].se<=qzmx[mid])pos=mid,R=mid-1;else L=mid+1;
		}
		s[i].fi=pos;
		L=i+1,R=n,pos=i;
		while(L<=R){
			int mid=(L+R)>>1;
			if(a[i].se>=hzmn[mid])pos=mid,L=mid+1;else R=mid-1;
		}
		s[i].se=pos;
	}
	sort(s+1,s+n+1,cmp);int len=1;
	rep(i,2,n)if(s[i].fi>s[len].fi)s[++len]=s[i];
	solve(n,s,len);
//	rep(i,1,n)printf("[%d %d]\n",s[i].fi,s[i].se);
	return 0;
}

Measured memory_bytes: 12544
#include <iostream>
#include<cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

long T;
int x = 0;
string a = "3";
string b = "5";
string c = "7";

void upnumber(long n)
{
	if (n <= T)
	{
		string N = to_string(n);
		if (N.find(a) != string::npos && N.find(b) != string::npos && N.find(c) != string::npos)
		{
			x++;
		}
		upnumber(n * 10 + 3);
		upnumber(n * 10 + 5);
		upnumber(n * 10 + 7);
	}
}

int main()
{
	cin >> T;
	upnumber(0);
	cout << x;

}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int n, nOdd = 0;
    int temp;

    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> temp;
        if(temp % 2 == 1) nOdd++;
    }

    if(nOdd % 2 == 1) cout << "NO" << endl;
    else cout << "YES" << endl;

    return 0;
}

        
        

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

int main()
{
    unsigned long long a, b, x;
    cin >> a >> b >> x;
    if (a == 0)
    {
        cout << b / x + 1;
        return 0;
    }
    cout << b / x - (a - 1) / x;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;

int main() {
	string S;
	cin >> S;
  for(auto e:S){
		cout << "x";
	}
	cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;i++)
#define ALL(x) x.begin(),x.end()
#define LL long long int

int mod = pow(10,9) +7;
const int inf = 2e9;
const LL linf = 2e18;
const double eps = 1e-9;

/////////////////////////////////////////////

const int N = 3e3+100;
LL arr[N];
LL dp[N][N];

LL total(LL x,LL y , bool c ){
    // trace(x,y,c);
    if(dp[x][y] != -1LL) return dp[x][y] ;
    if(x > y ) return 0;
    if(c == 0) return  dp[x][y ]=  max( arr[x] + total(x+1,y,!c) , arr[y] + total(x,y-1,!c) );
    else return dp[x][y] =  min(total(x+1,y,!c) -arr[x],total(x,y-1,!c) -arr[y]);
} 


int solve(int x, int y,int c){
    if(x == y){
        return arr[x];
    }
    int mini = min(arr[x] + solve(x+1,y,c^1),arr[y] + solve(x,y-1,c^1));
    int maxi = min(arr[x] + solve(x+1,y,c^1),arr[y] + solve(x,y-1,c^1));

    int play1 = min( arr[x] + solve(x+1,y,1) - solve(x+1,y,0) ,arr[y] +  solve(x,y-1,1) - solve(x,y-1,0) );
    int play2 = min( arr[x] + solve(x+1,y,1) - solve(x+1,y,0) ,arr[y] +  solve(x,y-1,1) - solve(x,y-1,0) );
    if(c == 0){
        return play1;
    }else{
        return play2;
    }
}


int main()
{
    
    LL n;
    cin >> n;
    forn(i,n) forn(j,n) dp[i][j] = -1LL;
    forn(i,n) cin >> arr[i];
    cout << total(0,n-1,0) << endl;
}


Measured memory_bytes: 74112
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<double>v(N);
  for(int i=0;i<N;i++){
    cin>>v.at(i);
  }
  sort(v.begin(),v.end());
  double sum=v.at(0);
  for(int i=1;i<N;i++){
    sum=(sum+v.at(i))/2;
  }
  cout<<fixed<<setprecision(10)<<sum<<endl;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(void){

    int n, i, j, k, l;

    cin >> n;

    int b[n], f[n], r[n], v[n]; 

    for(i = 0;i < n;i++){

        cin >> b[i] >> f[i] >> r[i] >> v[i];

    }//??\?±??????±?????\?????????

    int N[4][3][10] = {0};

    for(i = 0;i < n;i++){

        N[b[i] - 1][f[i] - 1][r[i] - 1] =  N[b[i] - 1][f[i] - 1][r[i] - 1] + v[i];

    }//??¨??\?±??????±????????£?????????????????¨?±?????????°????????????

    for(k = 0;k < 4;k++){

        for(j = 0;j < 3;j++){

            for(i = 0;i < 10;i++){

                cout << ' ' << N[k][j][i];

            }

            cout << endl;

        }

        if(k != 3)for(l = 0;l < 20;l++){cout << '#';};

        if(k != 3) cout << endl;

    }

return 0;

}

Measured memory_bytes: 1164
def solve():
    x = int(input())
    s = str(x)
    if x < 100:
        return print(0)
    s2s = ''.join(([s[-2],s[-1]]))
    s2 = int(s2s)
    # print(s2)

    x1 = s2 // 5
    # print(x1)
    if s2 % 5 == 0:
        n = x1
    else:
        n = x1+1
    # print(n)
    if 100*n > x:
        print(0)
    else:
        print(1)
solve()


Measured memory_bytes: 3060
import sys
input = sys.stdin.buffer.readline


n = int(input())
A = [int(i) for i in input().split()]

_min = 10**9 + 1
flag = False  # if minus integers is odd, flag is True
_sum = 0

for a in A:
    _sum += abs(a)
    _min = min(_min, abs(a))
    if a < 0:
        flag = not flag

if flag:
    _sum -= _min * 2
print(_sum)


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

int main ( void )
{
	char a[100000];
	while(fgets(a, 100000, stdin))
	{
		if ( a[0] == '0')
		{
			break;
		}
		int sum = 0;
		for(int i = 0; a[i] != '\n'; i++)
		{
			sum += a[i] - '0';
		}	
		cout << sum << endl;		
	}
	return 0; 
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
using namespace std;
typedef long long int ll;
int main(){
    ll X,Y;
    cin>>X>>Y;
    int cnt=0;
    while(X<=Y){
        X*=2;
        cnt++;
    }
    cout<<cnt<<"\n";
}

Measured memory_bytes: 256
#!/usr/bin/env run-cargo-script

#![allow(unused_imports)]

use std::cmp;
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::fmt::{Debug, Display};
use std::io::{self, Read};
use std::str::{self, FromStr};


fn solve(n: u32) -> bool {
    n.to_string().chars().find(|&c| c == '9').is_some()
}


fn main() {
    let stdin = io::stdin();
    let mut sc = Scanner::new(stdin.lock().bytes());
    print_yesno(solve(sc.next()), "Yes", "No");
}


struct Scanner<R: Read> {
    buf: Vec<u8>,
    bytes: io::Bytes<R>,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(bytes: io::Bytes<R>) -> Self {
        Scanner {
            buf: Vec::with_capacity(256),
            bytes: bytes,
        }
    }

    fn next<T: FromStr>(&mut self) -> T
    where
        <T as FromStr>::Err: Debug,
    {
        self.buf.clear();
        for c in self.bytes
            .by_ref()
            .map(|c| c.unwrap())
            .skip_while(|&c| c == ' ' as u8 || c == '\n' as u8)
            .take_while(|&c| !(c == ' ' as u8 || c == '\n' as u8))
        {
            self.buf.push(c);
        }
        str::from_utf8(&self.buf).unwrap().parse().unwrap()
    }

    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        (0..n).map(|_| self.next()).collect()
    }

    fn pairs<A: FromStr, B: FromStr>(&mut self, n: usize) -> Vec<(A, B)>
    where
        <A as FromStr>::Err: Debug,
        <B as FromStr>::Err: Debug,
    {
        (0..n).map(|_| (self.next(), self.next())).collect()
    }

    fn trios<A: FromStr, B: FromStr, C: FromStr>(&mut self, n: usize) -> Vec<(A, B, C)>
    where
        <A as FromStr>::Err: Debug,
        <B as FromStr>::Err: Debug,
        <C as FromStr>::Err: Debug,
    {
        (0..n)
            .map(|_| (self.next(), self.next(), self.next()))
            .collect()
    }

    fn mat<T: FromStr>(&mut self, m: usize, n: usize) -> Vec<Vec<T>>
    where
        <T as FromStr>::Err: Debug,
    {
        (0..n).map(|_| self.vec(m)).collect()
    }
}


#[allow(dead_code)]
fn print_yesno(x: bool, yes: &'static str, no: &'static str) {
    println!("{}", if x { yes } else { no });
}


#[allow(dead_code)]
fn print_foreach<T: Display, I: IntoIterator<Item = T>>(xs: I) {
    for x in xs.into_iter() {
        println!("{}", x);
    }
}


#[allow(dead_code)]
fn print_or<T: Display>(x: Option<T>, or: &'static str) {
    if let Some(x) = x {
        println!("{}", x);
    } else {
        println!("{}", or);
    }
}


Measured memory_bytes: 4352
s = set(input())

if "S" not in s and "N" in s:
	print("No")
elif "S" in s and "N" not in s:
	print("No")
elif "W" not in s and "E" in s:
	print("No")
elif "W" in s and "E" not in s:
	print("No")
else:
	print("Yes")

Measured memory_bytes: 2940
#include<stdio.h>

#define MAX 100
#define INF 2000000000
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, cost[MAX][MAX];

int prim(void);

int main(){
  int i, j, x;

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      scanf("%d", &x);
      if(x == -1){
        cost[i][j] = INF;
      }else{
        cost[i][j] = x;
      }
    }
  }

  printf("%d\n", prim());

}

int prim(){
  int i, u, min, v, sum = 0;
  int d[MAX], p[MAX], color[MAX];

  for(int i = 0; i < n; i++){
    d[i] = INF;
    p[i] = -1;
    color[i] = WHITE;
  }
  d[0] = 0;

  while(1){
    min = INF;
    u = -1;
    for(i = 0; i < n; i++){
      if(min > d[i] && color[i] != BLACK){
        u = i;
        min = d[i];
      }
    }
    if(u == -1) break;
    color[u] = BLACK;
    sum += min;
    for(v = 0; v < n; v++){
      if(color[v] != BLACK && cost[u][v] != INF){
        if(d[v] > cost[u][v]){
          d[v] = cost[u][v];
          p[v] = u;
          color[v] = GRAY;
        }
      }
    }
  }

  return sum;
}



Measured memory_bytes: 2104
n=int(input())
sp=[0]*n
for i in range(n):
    s,p=input().split()
    sp[i]=[s,int(p),i+1]
sp = sorted(sp, key=lambda x: x[1],reverse=True)
sp = sorted(sp, key=lambda x: x[0])
for i in range(n):
    print(sp[i][2])

Measured memory_bytes: 3060
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

const int N=2*1e5+5;

ll l,r,L[N],cnt[N][26];
int n,tot,nxt[N];
char st[N];

void kmp() {
	int k=0;
	fo(i,2,n) {
		while (k&&st[k+1]!=st[i]) k=nxt[k];
		nxt[i]=k+=st[k+1]==st[i];
	}
}

ll calc(ll n,int c) {
	int id=0;
	fd(i,tot,1) if (L[i]<=n) {id=i;break;}
	if (!id) {
		ll res=0;
		fo(i,1,n) if (st[i]-'a'==c) res++;
		return res;
	}
	return cnt[id][c]+calc(n-L[id],c);
}

int main() {
	scanf("%s",st+1);n=strlen(st+1);
	n/=2;kmp();
	L[0]=n-nxt[n];fo(i,1,n-nxt[n]) cnt[0][st[i]-'a']++;
	L[1]=n;fo(i,1,n) cnt[1][st[i]-'a']++;
	scanf("%lld%lld",&l,&r);
	for(tot=1;L[tot]<r;) {
		tot++;
		L[tot]=L[tot-1]+L[tot-2];
		fo(j,0,25) cnt[tot][j]=cnt[tot-1][j]+cnt[tot-2][j];
	}
	fo(c,0,25) printf("%lld ",calc(r,c)-calc(l-1,c));
	return 0;
}

Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int L,R;
  cin >> L >> R;
  int ans = 2019;
  int n;
  
  if(R - L < 2019) {
    for (int i = L; i < R; i++) {
      for (int j = i+1; j < R+1; j++) {
        int ii = i % 2019;
        int jj = j % 2019;
        n = ii * jj;
        n %= 2019; 
        ans = min(ans,n);
      }
    }
  } else ans = 0;
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define debug(x) cerr << "\n" \
                      << #x << " = " << x << ".\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define print(xx) cout << (xx) << endl
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vint;
const int INF = ((1LL << 30) + (1LL << 29));
const ll MOD = 1000000007;

/* 

*/
const int MAX = 200001;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// comb
// 二項係数計算
long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

//================== INPUT ========================
int N, M, K;
//=================================================
void input()
{
    cin >> N >> M >> K;
}

//=================================================
void solve()
{
    COMinit();

    int xsum = 0;
    int ysum = 0;
    rep(i,M){
        xsum += i * (M-i) * N * N;
    }
    xsum %= MOD;
    xsum *= COM(N*M-2, K-2);
    rep(i,N){
        ysum += i * (N-i) * M * M;
    }
    ysum %= MOD;
    ysum *= COM(N*M-2, K-2);

    cout<<(xsum+ysum)%MOD<<endl;
}

//=================================================
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define lp(n) for(int i = 0; i < n; i++)
using namespace std;
typedef struct n {
  int u;
  int a[101];
} node;
int main(){
  int n;
  node g[101];
  cin >> n;
  lp(n) {
    int t;
    cin >> t;
    cin >> g[t].u;
    for(int j = 0; j < 101; j++) g[t].a[j] = 0;
    for(int j = 0; j < g[t].u; j++) {
      int t2;
      cin >> t2;
      g[t].a[t2] = 1;
    }
  }
  lp(n) {
    cout << g[i+1].a[1];
    for(int j = 2; j <= n; j++)
      printf(" %d", g[i+1].a[j]);
    cout << endl;
  }
  return 0;
}


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

int main(){
  int r, d;
  vector<int> x(20);
  cin >> r >> d >> x[0];
  for(int i = 1; i <= 10; i++) x[i] = r * x[i-1] - d;
  for(int i = 1; i <= 10; i++) cout << x[i] << endl;
  return 0;
}

Measured memory_bytes: 3588
def ok(x,y)
  [x,y].include?(nil) || (x-y).abs<=1
end

ans=[0]
gets.to_i.times do
  10.times do |i|
    ans[i]=0 unless ans[i]
    ans[i]+=1
    next unless ans[i]<=9 && ok(ans[i],ans[i+1])
    (i-1).downto(0) do |j|
      ans[j]=[ans[j+1]-1,0].max
    end
    break
  end
end
puts ans.join.reverse


Measured memory_bytes: 14268
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
class UnionFind {
public:
    vector < ll > par; // 各元の親を表す配列
    vector < ll > siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    UnionFind tree(n + 1);
    vector<int> fr[n + 1];
    vector<int> bl[n + 1];
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        tree.merge(a, b);
        fr[a].push_back(b);
        fr[b].push_back(a);
    }
    for (int i = 1; i <= k; i++) {
        int c, d;
        cin >> c >> d;
        bl[c].push_back(d);
        bl[d].push_back(c);
    }
    for (int i = 1; i <= n; i++) {
        int ret = tree.size(i) - 1 - fr[i].size();
        for (int j = 0; j < bl[i].size(); j++) {
            if (tree.issame(bl[i][j], i)) {
                ret--;
            }
        }
        cout << ret << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 15836
// https://atcoder.jp/contests/abc094/tasks/arc095_a

#include <algorithm>
#include <cmath>
#include <iostream>
#include <regex>
#include <set>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

#define EPS (1e-7)
#define INF (1e9)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOREACH(x, a) for (auto &(x) : (a))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

// long gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// long lcm(long a, long b) { return a * b / gcd(a, b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> v, w;
    v.resize(n);
    w.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    copy(v.begin(), v.end(), w.begin());
    sort(ALL(w));

    for (int i = 0; i < n; i++) {
        if (v[i] < w[n / 2]) {
            cout << w[n / 2] << endl;
        } else {
            cout << w[n / 2 - 1] << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3840
#include <cstdio>

using namespace std;

int main()
{
	int in[10];
	int i = 0;

	while (scanf("%d", &in[i]) != EOF){
		if (in[i] == 0){
			i--;
			printf("%d\n", in[i]);
		}
		else {
			i++;
		}
	}
}

Measured memory_bytes: 1028
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <cmath>
using namespace std;

int main() {
	int N; cin >> N;
	int ans = 0;
	vector<int>P(N), Q(N);
	for (int i = 0; i < N; i++) {
		Q.at(i) = i + 1;
		cin >> P.at(i);
		if (Q.at(i) != P.at(i)) ans++;
	}

	if (ans > 2) cout << "NO" << endl;
	else cout << "YES" << endl;
}

Measured memory_bytes: 256
[<AutoOpen>]
module Program

open System

let read f = stdin.ReadLine() |> f
let reads f = stdin.ReadLine().Split() |> Array.toList |> List.map f

let f s xs =
    let d = List.head xs - List.last xs
    if d < s then d else s

[<EntryPoint>]
let main _ =
    let [n;k] = reads int
    let hs = Array.map (fun _ -> read int) [|1..n|]
    let xs = Array.sortDescending hs
    [
        for i = 0 to n - k do
            let j = i + (k - 1)
            yield xs.[i] - xs.[j]
    ]
    |> List.min
    |> printfn "%i"
    0

Measured memory_bytes: 23380
# include <bits/stdc++.h>
#define flash ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define endl '\n'
#define ll long long int
#include <tr1/unordered_map>
#define ld long double
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define f(i,a,b)  for(long long i=a;i<b;i++)
#define all(c) (c).begin(),(c).end()
#include <map>

using namespace std;

 

int main()
{




     flash;
     ///////////////////////////////////////////////////////////////////////////////////////



int x;
cin>>x;
if(x==0)
{
  cout<<1<<endl;

}
else
{
  cout<<0<<endl;
}




    ///////////////////////////////////////////////////////////////////////////////////////

     return 0;

}


Measured memory_bytes: 3644
n=int(input())
store=[]
for i in range(n):
    store.append(list(map(int,input().split())))
score=[]
for i in range(n):
    score.append(list(map(int,input().split())))

A=[]
for i in range(1,2**10):
    ans=0
    for s in range(n):
        count=0
        for j in range(10):
            if ((i>>j)&1) and store[s][j]==1:
                count+=1
        ans+=score[s][count]
    A.append(ans)
print(max(A))
    

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define tam 100010
#define mod 1000000007

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef pair <ll, ll> dl;
typedef pair <int, int> ii;
typedef vector <ii> vii;
typedef vector <vii> graph;

bool comp(int a, int b) {
	return a > b;
}

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

	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	int l, r;
	int ac[n];
	ac[0] = 0;
	for (int i = 1; i < n; ++i)
	{
		ac[i] = ac[i - 1];
		if (s[i] == 'C' && s[i - 1] == 'A') ac[i]++;
	}
	for (int i = 0; i < q; ++i)
	{
		cin >> l >> r;
		cout << ac[r - 1] - ac[l - 1] << "\n";
	}
	return 0;
}


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

int main() {
  int n,ans=0;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  for(int i=0;i<n;i++) {
    if(i%2==0) ans+=a[i];
    else ans-=a[i];
  };
  cout << ans << endl;
}

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

int main()
{
  int a,b,c;
  cin>>a>>b>>c;
  for(int i=1;i<=200;i++)
  {
    if((a*i)%b==c)
      {
        cout<<"YES\n";
        return 0;
      }
  }
  cout<<"NO\n";

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<numeric>
using namespace std;
using ll = long long;
int main(){
  int n, k;
  cin >> n >> k;
  ll ans = 0;
  if(k == 0){
    ans -= n;
  }
  for(int i = k + 1; i <= n; i++) {
    ll r = n % i;
    ll p = (n - r) / i;
    ans += p * max(0, i - k);
    ans += max((ll)0, r - k + 1);
  }
  
  cout << ans << endl;
  return 0;
}

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

int main () {
  int n,x;
  cin>>n;
  vector<int> v(n);
  for(int i=1;i<=n;i++) {
    cin>>x;
    v[x-1]=i;
  }
  for(int i=0;i<n;i++)
  cout<<v[i]<<" ";
  return 0;
}

Measured memory_bytes: 1152
import sys
input = sys.stdin.readline

def main():

    n = int(input())
    s = input()

    r = s.count("R")
    g = s.count("G")
    b = s.count("B")

    ans = r*g*b

    for i in range(n):
        for diff in range(n):
            j = i + diff
            k = i + diff*2
            if k < n:
                if s[i] != s[j]:
                    if s[i] != s[k]:
                        if s[j] != s[k]:
                            ans -= 1
            else:
                break
    print(ans)

main()

Measured memory_bytes: 9208