akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long int A,B;
  int X;
  cin >> X;
  for(int i=0;i<=1000;i++){
    A=pow(i,5);
    for(int j=0;j<=1000;j++){
      B=pow(j,5);
      if(A-B==X){
        cout << i << " " << j <<  endl;
        return 0;
      }else if(A+B==X){
        cout << i << " " << -j <<  endl;
        return 0;
      }else if(-A+B==X){
        cout << -i << " " << -j <<  endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 3992
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}



template< typename T >
struct Compress {
    vector< T > xs;

    Compress() = default;

    Compress(const vector< T > &vs) {
        add(vs);
    }

    Compress(const initializer_list< vector< T > > &vs) {
        for(auto &p : vs) add(p);
    }

    void add(const vector< T > &vs) {
        copy(begin(vs), end(vs), back_inserter(xs));
    }

    void add(const T &x) {
        xs.emplace_back(x);
    }

    void build() {
        sort(begin(xs), end(xs));
        xs.erase(unique(begin(xs), end(xs)), end(xs));
    }

    vector< int > get(const vector< T > &vs) const {
        vector< int > ret;
        transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) {
                return lower_bound(begin(xs), end(xs), x) - begin(xs);
                });
        return ret;
    }

    int get(const T &x) const {
        return lower_bound(begin(xs), end(xs), x) - begin(xs);
    }

    const T &operator[](int k) const {
        return xs[k];
    }
};



template< typename T >
struct BIT {
    vector< T > data;

    BIT(int sz) {
        data.assign(++sz, 0);
    }

    T sum(int k) {
        T ret = 0;
        for(++k; k > 0; k -= k & -k) ret+=data[k];
        return (ret);
    }

    T get(int x,int y){

        return sum(y)-sum(x);
    }

    void add(int k, T x) {
        for(++k; k < data.size(); k += k & -k) data[k]+=x;
    }
};

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

    int n,d,a;
    cin>>n>>d>>a;

    vector<P> v(n);
    vi w(n);
    rep(i,n){
        cin>>v[i].F>>v[i].S;
        w[i]=v[i].F;
    }

    sort(all(v));

    Compress<int> com(w); 
    BIT<int> bit(n);
    com.build();

    int ans=0;

    rep(i,n){
        int it1=com.get(v[i].F);
        int h=v[i].S-bit.sum(it1);
        if(h<=0) continue;
        int c=(h+a-1)/a;

        //cout<<it1<<' '<<h<<' '<<c<<endl;
        //cout<<com.get(v[i].F+2*d)<<endl;
        ans+=c;
        bit.add(it1,a*c);
        bit.add(com.get(v[i].F+2*d+1),-a*c);
    }

    /*
    rep(i,n){
        cout<<bit.sum(i)<<endl;
    }
    */

    cout<<ans<<endl;

}

Measured memory_bytes: 8176
def divi(x):
    d = []
    for i in range(1, int(x**0.5)+1):
        if x%i == 0:
            d.append(i)
            if i!=(x//i):
                d.append(x//i)
    return d
n = int(input())
ans = 0
for j in range(1, n+1, 2):
    if len(divi(j)) == 8:
        ans += 1
print(ans)

Measured memory_bytes: 3060
###############################################################################

from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * sy) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def main():
    n = intin()
    ablist = intinl(n-1)

    linklist = make_linklist(ablist)
    diameter = calc_tree_diameter(linklist)

    if diameter % 3 == 1:
        print('Second')
    else:
        print('First')


if __name__ == '__main__':
    main()


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

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

const int N = 100010;

void mul(int *a, int *b, int n)
{
	static int t[N], h[N];
	for (int i = 1; i <= n; ++i) t[i] = a[i], h[i] = b[i];
	for (int i = 1; i <= n; ++i) a[i] = t[h[i]];
}

void fpow(int *a, int n, long long k)
{
	static int t[N];
	for (int i = 1; i <= n; ++i) t[i] = i;
	for (; k; k >>= 1)
	{
		if (k & 1) mul(t, a, n);
		mul(a, a, n);
	}
	for (int i = 1; i <= n; ++i) a[i] = t[i];
}

int n;

long long x[N];

int m, a[N];

long long k;

int main()
{	
	gi(n);
	for (int i = 1; i <= n; ++i) gi(x[i]), a[i] = i;
	for (int i = n; i; --i) x[i] -= x[i - 1];
	gi(m);
	scanf("%lld", &k);
	for (int i = 1; i <= m; ++i)
	{
		int p;
		gi(p);
		swap(a[p], a[p + 1]);
	}
	fpow(a, n, k);
	for (int i = 1; i <= n; ++i)
	{
		//cerr << a[i] << " : " << x[a[i]] << endl;
		x[a[i]] += x[a[i - 1]];
		printf("%lld\n", x[a[i]]);
	}
	return 0;
}

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

int main() {
    int N ;
    cin >> N ;
    vector<int>C(N);
    vector<int>D(N);
    for( int i = 0; i<N; ++i ){
        cin >> C.at(i);
    }
    for( int i = 0; i<N; ++i){
        cin >> D.at(i);
    }
    int ans;
    ans = 0;
    for( int i = 0; i<N; ++i){
        if( C.at(i) > D.at(i)){
            ans += (C.at(i) - D.at(i));
        }
        else{

        }
    }
    cout << ans << endl ;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int a,b;
    cin >>a >> b;
    if (a==b){
        cout<<"Draw";
    }else{
        if (a==1){
            cout<<"Alice";
        }else if(b==1){
            cout<<"Bob";
        }else{
            if (a>b){
                cout<<"Alice";
            }else{
                cout<<"Bob";
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll h, w;
    cin >> h >> w;
    if(h == 1 || w == 1){
        cout << 1 << endl;
        return 0;
    }
    ll ans = (h*w+1) / 2;
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    long long n, k;
    vector <long long> v;
    cin >> n >> k;
    long long m = n;
    v.push_back(n);
    bool flag = 1;
    while (1) {
        if (n > k) n = n % k;
        else n = abs(n - k);
        m = min(n, m);
        for (int i = 0; i < v.size(); i++) {
            if (n == v[i]) flag = 0;
        }
        if (flag == 0) break;
        else v.push_back(n);
    }
    cout << m << endl;
}


    



Measured memory_bytes: 256
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)

N,M=map(int, input().split())
mx=0
uf = UnionFind(N+1)
for i in range(M):
	a,b = map(int, input().split())
	uf.union(a,b)
for i in uf.parents:
	mx = max(mx, uf.size(i))
if M == 0:
	mx = 1
print(mx)




Measured memory_bytes: 77328
n = gets.to_i
a = gets.split.map(&:to_i)

h = Hash.new {|h, k| h[k] = 0}
a.each do |x|
  h[x-1] += 1
  h[x] += 1
  h[x+1] += 1
end

puts h.each_value.max

Measured memory_bytes: 14212
#![allow(unused_imports)]

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

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

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

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

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

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

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

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

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

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

use std::cmp::{min, max};
use std::collections::{HashMap, HashSet, VecDeque, BinaryHeap};

fn main() {
    input!{
        x: usize,
        y: usize,
        z: usize
    }
    println!("{}", (x - z) / (y + z));
}


Measured memory_bytes: 4352
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int x[100], top = -1;				//top????????????????????°????????°
	char s[100];

	while (scanf("%s", s) != EOF) {		//????????????????????????
		if (s[0]=='+') {					//+?????´???
			x[top - 1] = x[top - 1] + x[top];
			top--;
		}
		else if (s[0]=='-') {			//????????´???
			x[top - 1] = x[top - 1] - x[top];
			top--;
		}
		else if (s[0]=='*') {			//???????´???
			x[top - 1] = x[top - 1] * x[top];
			top--;
		}
		else {							//??°????????´???
			x[top + 1] = atoi(s);
			top++;
		}
	}

	printf("%d\n", x[0]);

	return 0;
}

Measured memory_bytes: 548
h, w= map(int,input().split())
mass = [input() for i in range(h)]

ans = []

for row in mass:
  ans.append(list(row))
  
dxy = [(-1,-1),(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1)]

for y in range(h):
  for x in range(w):
    if mass[y][x] == '#':
      continue
    c = 0
    for dx,dy in dxy:
      if x + dx < 0 or x + dx > w - 1 or y + dy < 0 or y + dy > h - 1:
        continue
      if mass[y + dy][x + dx] == "#":
        c += 1
    ans[y][x] = c
    
for row in ans:
  print(''.join( list(map(str,row))))

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include<vector>
#include <queue>
#include <string>
using namespace std;
int main()
{
	int a, b, k;
	cin >> a >> b >> k;
	if (b - a + 1 <= 2 * k) {
		for (int i = a; i <= b; i++) {
			cout << i << endl;
		}
	}
	else {
		for (int i = a; i <= a+k-1; i++) {
			cout << i << endl;
		}
		for (int i = b-k+1; i <= b; i++) {
			cout << i << endl;
		}
	}
}

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

tmp = input()
a=[int(x) for x in tmp.split()]

b=abs(a[1]-a[0])+abs(a[2]-a[1])
c=abs(a[2]-a[0])+abs(a[1]-a[2])
d=abs(a[0]-a[1])+abs(a[2]-a[0])

print(min(b,c,d))

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node{
int key;
struct node *parent;
struct node *left;
struct node *right;
}node;
typedef node * NodePointer;
NodePointer root, nil;
NodePointer make(int key, NodePointer p){
NodePointer n;
n = malloc(sizeof(struct node));
n->key = key;
n->parent = p;
n->left = p;
n->right = p;
return n;
}

void insert(int key){
NodePointer n, x, z;
z = make(key, nil);
n = root;
x = nil;
while(n != nil){
x = n;
if(n->key < key) n = n->right;
else n = n->left;
}
z->parent = x;
if(x == nil) root = z;
if(x->key < z->key) x->right = z;
if(x->key > z->key) x->left = z;
}
void find(NodePointer T, int key){
if(T == nil){
printf("no\n");
return;
}
else if(T->key == key){
printf("yes\n");
return ;
}
else if(T->key < key) find(T->right, key);
else if(T->key > key) find(T->left, key);
return ;
}
NodePointer min(NodePointer x){
while(x->left != nil)
x = x->left;
return x;
}
NodePointer suc(NodePointer x){
NodePointer y;
if(x->right != nil)
return min(x->right);
y = x->parent;
while(y != nil && x == y->right){
x = y;
y = y->parent;
}
return y;
}
void delete(NodePointer T, int key){
NodePointer x, y;
while(T->key != key){
if(T->key < key) T = T->right;
else if (T->key > key) T = T->left;
}
if(T->left == nil || T->right == nil){
y = T;
}
else
y = suc(T);
if(y->left != nil) x = y->left;
else x = y->right;
if(x != nil) x->parent = y->parent;
if(y->parent == nil) root = x;
else if(y == y->parent->left) y->parent->left = x;
else y->parent->right = x;
if(y != T){
T->key = y->key;
T = y;
}

free(T);
}
void inorder(NodePointer T){
if(T->left->key != 0) inorder(T->left);
printf(" %d",T->key);
if(T->right->key != 0) inorder(T->right);
}
void preorder(NodePointer T){
printf(" %d",T->key);
if(T->left != nil) preorder(T->left);
if(T->right != nil) preorder(T->right);
}
void fre(NodePointer T){
free(T);
if(T->left != nil) fre(T->left);
if(T->right != nil) fre(T->right);
}
int main(){
int i ,n, key;
char s[20];
nil = make(0, nil);
root = make(0, nil);
root = nil;
scanf("%d",&n);
for(i = 0; i < n; i++){
scanf("%s", s);
if(s[0] == 'i'){
scanf("%d",&key);
insert(key);
}
else if(s[0] == 'd'){
scanf("%d",&key);
delete(root, key);
}
else if(s[0] == 'f'){
scanf("%d",&key);
find(root, key);
}
else if(s[0] == 'p'){
inorder(root);
printf("\n");
preorder(root);
printf("\n"); 
}
}
fre(root);
free(nil);
return 0;
}

Measured memory_bytes: 19364
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contruction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[x] = y

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


n = int(input())

uf = UnionFind(n)
xs = []
ys = []
x_dict = {}
y_dict = {}
for i in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)

    if x in x_dict:
        uf.unite(i, x_dict[x])

    if y in y_dict:
        uf.unite(i, y_dict[y])

    x_dict[x] = uf.find(i)
    y_dict[y] = uf.find(i)

# print(uf.par)
xi = defaultdict(list)
yi = defaultdict(list)
for i in range(n):
    xi[uf.find(x_dict[xs[i]])].append(xs[i])
    yi[uf.find(y_dict[ys[i]])].append(ys[i])

ans = 0
for k in xi.keys():
    ans += len(set(xi[k])) * len(set(yi[k])) - len(xi[k])

print(ans)


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

int main() {
  int n;
  cin>>n;
  n%=10;
  if(n==3) cout<<"bon"<<endl;
  else if((n==0 || n==1) || (n==6 || n==8)) cout<<"pon"<<endl;
  else cout<<"hon"<<endl;
}


Measured memory_bytes: 3636
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

inf = 10 ** 10
lis = [inf] * (N * 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
  x = s.pop()
  if x >= 0:
    vis[x] = 1
    euler.append(x)
    for y in e[x]:
      if vis[y]: continue
      s.append(~y)
      s.append(y)
  else: euler.append(x)

rollback = []
res = [0] * (N + 1)
for x in euler:
  if x >= 0:
    y = bl(lis, a[x])
    rollback.append((y, lis[y]))
    lis[y] = a[x]
    res[x] = bl(lis, inf)
  else:
    y, v = rollback.pop()
    lis[y] = v

for r in res[1: ]: print(r)


Measured memory_bytes: 168744
n = gets.chomp.to_i
a_arr = gets.chomp.split(" ").map(&:to_i)

a_arr.each do |a|
  if a % 2 == 0 then
    unless a % 3 == 0 || a % 5 == 0 then
      puts "DENIED"
      exit
    end
  end
end

puts "APPROVED"


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

int length;
char idS[11];
char idT[10];

int check = 0;

int main(void){

    scanf("%s", idS);
    scanf("%s", idT);

    length = strlen(idS);
    for(int i=0; i<length; i++){
        if(idS[i] != idT[i]){
            printf("No\n");
            check = 1;
            break;
        }
    }

    if(check == 0)printf("Yes\n");

    return 0;
}

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

template <typename InputIterator>
typename InputIterator::value_type summation(InputIterator first,
                                             InputIterator last) {
  return std::accumulate(first, last, typename InputIterator::value_type());
}
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int64_t combination(const int64_t n, const int64_t k) {
  int64_t ans = 1;
  for (int64_t i = 0; i < k; i++) {
    ans *= n - i;
    ans /= i + 1;
  }
  return ans;
}

class combination_cache {
 private:
  explicit combination_cache(const int64_t p)
      : mod(p), max(1), fac(2, 1), finv(2, 1), inv(2, 1) {}
  ~combination_cache() = default;
  const int64_t mod;
  int64_t max;

 public:
  combination_cache(const combination_cache &) = delete;
  combination_cache &operator=(const combination_cache &) = delete;
  combination_cache(combination_cache &&) = delete;
  combination_cache &operator=(combination_cache &&) = delete;

  std::vector<int64_t> fac;
  std::vector<int64_t> finv;
  std::vector<int64_t> inv;

  static const combination_cache &get(const int64_t n, const int64_t p) {
    static combination_cache instance(p);

    assert(p == instance.mod);
    if (instance.max < n) {
      instance.fac.reserve(n + 1);
      instance.finv.reserve(n + 1);
      instance.inv.reserve(n + 1);
      for (int64_t i = instance.max + 1; i <= n; i++) {
        instance.fac.push_back(instance.fac[i - 1] * i % p);
        instance.inv.push_back(p - instance.inv[p % i] * (p / i) % p);
        instance.finv.push_back(instance.finv[i - 1] * instance.inv[i] % p);
      }
      instance.max = n;
    }
    return instance;
  }
};

int64_t combination(const int64_t n, const int64_t k, const int64_t p) {
  if (n < k || n < 0 || k < 0) {
    return 0;
  }
  const auto &cache = combination_cache::get(n, p);
  return cache.fac[n] * (cache.finv[k] * cache.finv[n - k] % p) % p;
}

int main() {
  const int64_t mod = 1000000007;
  int64_t n, m, k;
  std::cin >> n >> m >> k;
  int64_t cost = 0;

  for (int64_t i = 1; i < n; i++) {
    cost += (n - i) * i * m * m;
    cost %= mod;
  }
  for (int64_t i = 1; i < m; i++) {
    cost += (m - i) * i * n * n;
    cost %= mod;
  }

  std::cout << (cost * combination(n * m - 2, k - 2, mod)) % mod << std::endl;
  return 0;
}


Measured memory_bytes: 4992
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES

#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <functional>
#include <utility>
#include <tuple>
#include <vector>
#include <string>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <bitset>
#include <complex>
#include <limits>
#include <random>


using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;

const double EPS = 1e-9;

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

	int N;
	int A;
	int ans = 0;
	
	cin >> N;
	int ma = -1;
	rep(i, 0, N)
	{
		cin >> A;
		chmax(ma, A);
		ans += ma - A;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i = 0; i < (n); ++i )
#define rep_rev(n,i) for(ll i = n; i >= 0; --i )
using namespace std;
using P = pair<int, int>;
const long long INF = 1LL << 60;

int main(){
  string s; cin >> s;
  int N = s.length();
  rep(i,(N-1)/2){
    if(s[i] != s[((N-1)/2) - 1 - i]) {
      cout << "No" << endl;
      return 0;
    }
  }
  for(int i = ((N+3)/2) - 1; i < N; ++i){
    if(s[i] != s[N-1-i]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


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

int main(){
  vector<ll> n(5);
  ll num = 10;
  ll id=0;
  rep(i,5){
    cin >> n.at(i);
    if( num > n.at(i)%10 &&  n.at(i)%10 != 0 ){
      num = n.at(i)%10;
      id = i;
    }
  }
  ll ans = 0;
  rep(i,5){
    if( i == id ) continue;
    ans += 10*(ceil((double)n.at(i)/10.0));
  }
  ans += n.at(id);
  cout << ans << endl;
    
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using f80 = __float80;
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define pb push_back
#define rng(a) a.begin(),a.end()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define sz(x) (i64)(x).size()
#define bit(n) (1LL<<(n))
#define fi first
#define se second
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef v(i64) vi;
typedef v(vi) vvi;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

i64 pow_mod(i64 n, i64 k, i64 m){
  i64 r = 1;
  for(;k;k>>=1){
    if(k&1) r=(r*n)%m;
    n=(n*n)%m;
  }
  return r;
}

struct uf{
  private:
    vi par, rank, size;
  public:
    uf(i64 n){ init(n); }
    void init(i64 n){
      par.resize(n);
      rank.resize(n,0);
      size.resize(n,1);
      rep(i,n) par[i] = i;
    }
    i64 root(i64 x){
      if(par[x] == x) return x;
      return par[x] = root(par[x]);
    }
    bool same(i64 x, i64 y){ return root(x) == root(y); }
    void unite(i64 x, i64 y){
      x = root(x), y = root(y);
      if(x==y) return;
      if(rank[x]==rank[y]) rank[x]++;
      if(rank[x]<rank[y]) swap(x,y);
      par[y] = x;
      size[x] += size[y];
    }
    i64 num(i64 x){ return size[root(x)]; }
};

void Main()
{
  i64 n[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  i64 k;
  cin >> k;
  cout << n[k-1] << endl;


}

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



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
char s[500005],cc;
int a[27][500005],c[27][500005],zan;
int shu,ll,rr;
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int z,int y)
{
	for(int i=x;i<=n;i+=lowbit(i))
	c[z][i]+=y;
}
int getsum(int x,int numb)
{
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i))
	ans+=c[numb][i];
	return ans;
}
int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
    {
        shu=s[i]-'a'+1;
        zan=lowbit(i);
        for(int j=i;j<=n;j=j+lowbit(j))c[shu][j]+=1;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&shu);
        if(shu==1)
        {
            scanf("%d %c",&zan,&cc);
            if(cc==s[zan])continue;
            else
            {
                int numb=s[zan]-'a'+1;
                add(zan,numb,-1);
                numb=cc-'a'+1;
                add(zan,numb,1);
                s[zan]=cc;
            }
        }
        else
        {
            scanf("%d%d",&ll,&rr);
            int dd=0;
            for(int w=1;w<=26;w++)
            {
                if(getsum(rr,w)-getsum(ll-1,w)>=1)dd++;

            }
            printf("%d\n",dd);
        }
    }
	return 0;
}


Measured memory_bytes: 52096
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
	public class QuestionA
	{
		public static void Main()
		{
			// 整数の入力
			int n = int.Parse(Console.ReadLine());

			List<int> S = new List<int>();
			for (int i = 0; i < n; ++i) {
				S.Add(int.Parse(Console.ReadLine()));
			}

			var sum = S.Sum();

			while (sum % 10 == 0) {
				var temp = S.Where(x => x % 10 != 0);
				if (temp.Any() == false) {
					if (sum % 10 != 10) {
						sum = 0;
					}
					break;
				}

				var min = temp.Min();
				sum -= min;
				S.Remove(min);
				if (S.Any() == false) {
					break;
				}
			}

			Console.WriteLine(sum);

		}

	}
}

Measured memory_bytes: 18628
// C++ 14
#include <bits/stdc++.h>
using namespace std;
template <typename T>  ostream& operator<<(ostream& os, const vector<T>& v)  {  os << "[";  for (int i = 0; i < v.size(); ++i) {  os << v[i];  if (i != v.size() - 1)  os << ", ";  }  os << "]";  return os;  }
template <typename T> void print(T v, string s = "\n") { cout << v << s; }
template <typename T> void in(T &v) { cin >> v; }
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

int G[500][500];
int ACC[500][501];

int main() {
  int n, m, q; in(n),in(m),in(q);
  loop(i,0,m) {
    int l, r; in(l),in(r);
    l--;r--;
    G[l][r]++;
  }
  
  loop(y,0,n) {
    loop(x,0,n+1) {
      if (x == 0) { ACC[y][x] = 0; continue; }
      ACC[y][x] = ACC[y][x-1] + G[y][x-1];
    }
  }
  
  // loop(y,0,n) {
  //   loop(x,0,n+1) {
  //     print(ACC[y][x], " ");
  //   }
  //   print("");
  // }
  
  loop(i,0,q) {
    int l,r; in(l),in(r); l--;r--;
    int cnt = 0;
    int len=r-l+1;
    loop(y,l,l+len) {
      // print(vector { y, l, r+1 });
      cnt += ACC[y][r+1]-ACC[y][l];
    }
    print(cnt);
  }
  return 0;
}


Measured memory_bytes: 5584
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <stack>


using namespace std;
typedef long long LL;
const int MaxN = 1e6 + 5;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double esp = 1e-6;

#define pi acos(-1.0)
int r;

int main(){
    cin >> r;
    double ans = 2 * pi * r;
    cout << ans << endl;

    return 0;
}

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

const int MAX = 100;
int main() {
	int N, x[MAX], y[MAX], h[MAX];
	cin >> N;
	for (int i = 0;i < N;++ i) cin >> x[i] >> y[i] >> h[i];
	for (int i = 0;i <= 100;++ i) {
		for (int j = 0;j <= 100;++ j) {
			int Hmin = h[0] == 0 ? 1 : h[0] + abs(y[0] - i) + abs(x[0] - j), Hmax = h[0] + abs(y[0] - i) + abs(x[0] - j);
			for (int k = 1;k < N;++ k) {
				if (h[k] != 0) Hmin = max(Hmin, h[k] + abs(y[k] - i) + abs(x[k] - j));
				Hmax = min(Hmax, h[k] + abs(y[k] - i) + abs(x[k] - j));
			}
			if (Hmin == Hmax) {
				cout << j << " " << i << " " << Hmin;
				return 0;
			}
		}
	}
	
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

答えを決め打つとO(XYN),10000N
*/

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
#include <iomanip>
#include <math.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60
const double PI = 3.14159265358979323846;

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

	int A, B, K; cin >> A >> B >> K;
	vector<int> V;
	for (int i = A; i < A + K; i++) V.push_back(i);
	for (int i = B - K + 1; i <= B; i++) V.push_back(i);
	sort(V.begin(), V.end());
	for (int i = 0; i < V.size(); i++) {
		if(A<=V[i] && V[i]<=B) cout << V[i] << endl;
		while (V[i] == V[i + 1]) i++;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));
    int ans = 1, sum = 0;
    rep(i, n - 1) sum += a[i];
    for (int i = n - 2; i >= 0; i--)
    {
        if (2 * sum >= a[i + 1])
            ans++;
        else
            break;
        sum -= a[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int k = scanner.nextInt();
        final int n = scanner.nextInt();

        final int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            final int tmp = scanner.nextInt();
            array[i] = tmp;
        }

        int min = array[n - 1] - array[0];
        for (int i = 0; i < array.length - 1; i++) {
            min = Math.min(min, k + array[i] - array[i + 1]);
        }

        System.out.println(min);
    }
}


Measured memory_bytes: 67256
unittest
{
	assert( [ "3 4", "ABC", "A L", "B L", "B R", "A R" ].solve == 2 );
	assert( [ "8 3", "AABCBDBA", "A L", "B R", "A R" ].solve == 5 );
	assert( [ "10 15", "SNCZWRCEWB", "B R", "R R", "E R", "W R", "Z L", "S R", "Q L", "W L", "B R", "C L", "A L", "N L", "E R", "Z L", "S L" ].solve == 3 );
	
	assert( [ "3 4", "ABC", "B L", "A L", "B R", "C R" ].solve == 0 );		// 追加ケース
}



import std.conv;
import std.format;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto q = 0L;
	input.front.formattedRead!"%s %s"( n, q );
	input.popFront;
	auto s = input.front.to!( dchar[] );
	auto tds = new dchar[ 2 ][ q ];
	foreach( ref td; tds )
	{
		input.popFront;
		auto as = input.front.to!( dchar[] );
		td = [ as[ 0 ], as[ 2 ] ];
	}
	
	// ゴーレムが残る範囲を判定
	s = "!!" ~ s ~ "!!";
	auto l = 2L;
	auto r = n + 1;		// 閉区間表現
	foreach_reverse( td; tds )
	{
		if( td[ 1 ] == 'R' )
		{
			if( s[ r     ] == td[ 0 ] ) r--;
			if( s[ l - 1 ] == td[ 0 ] ) l--;
		}
		else
		{
			if( s[ r + 1 ] == td[ 0 ] ) r++;
			if( s[ l     ] == td[ 0 ] ) l++;
		}
		if( r < l ) break;
	}
	return 1 + r - l;
}


Measured memory_bytes: 7548
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
int main() {
  int n, k;
  cin >> n >> k;

  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p.at(i);
  }

  int maxs = 0;
  int right = 0;
  int sum = 0;
  int l, r;
  for (int left = 0; left < n; left++) {
    while (right < n && right < k + left) {
      sum += p.at(right);
      right++;
    }

    if (sum > maxs) {
      maxs = sum;
      l = left;
      r = right-1;
    }

    if (right == left) right++;
    else sum -= p.at(left);

  }

  double ans = 0;
  for (int i = l; i <= r; i++) {
    double a = (p.at(i)+1)/2.0;
    ans += a;
  }
  cout << fixed << setprecision(10) << ans << endl;

}

Measured memory_bytes: 1024
import sys
input = sys.stdin.readline
from collections import deque


def main():
    H, W = [int(x) for x in input().split()]
    A = [["" for i in range(W)] for j in range(H)]

    for j in range(H):
        S = input().strip()
        for i, s in enumerate(list(S)):
            A[j][i] = s

    ma = 0

    dj = [1, 0, -1, 0]
    di = [0, 1, 0, -1]

    for sj in range(H):
        for si in range(W):
            if A[sj][si] == "#":
                continue
            d = [[-1 for i in range(W)] for j in range(H)]
            q = deque([])
            q.append((sj, si))
            d[sj][si] = 0

            while q:
                p = q.popleft()
                for i in range(4):
                    nj = p[0] + dj[i]
                    ni = p[1] + di[i]

                    if 0 <= nj < H and 0 <= ni < W and A[nj][ni] != "#" and d[nj][ni] == -1:
                        q.append((nj, ni))
                        d[nj][ni] = d[p[0]][p[1]] + 1

            for gj in range(H):
                for gi in range(W):
                    ma = max(ma, d[gj][gi])

    print(ma)





    


if __name__ == '__main__':
    main()



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

typedef long long ll;
#define vec vector<int>
#define vecll vector<ll>
#define vpair vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n)   for(int i=(int)0; i<(int)n; i++)
#define llrep(i,n)   for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n) for(int i=(int)m; i<(int)n; i++)
#define all(var)     (var).begin(), (var).end()
#define prt(var)     cout << var << endl
#define prt_dbl(i,var) cout<<fixed<<setprecision(i)<<var<<endl;
template <typename Val>
Val gcd(Val a, Val b) {
//use ll or int for gcd
    if (b==0) return a;
    else return gcd(b, a%b);
}
template <typename Val>
Val vec_max(vector<Val> v){
  return *max_element(v.begin(),v.end());
}
template <typename Val>
Val vec_min(vector<Val> v){
  return *min_element(v.begin(),v.end());
}




//---------------------------------------------------------------

int main(){
  int N,Q;
  string S;
  cin>>N>>Q;
  cin>>S;
  vector<pair<int,int>>M;
  rep(i,Q){
    int l,r;
    cin>>l>>r;
    M.emplace_back(l,r);
  }

  vector<int>R(N,0);

  int s=0;
  rep(i,N-1){
    int t = 0;
    if(S.at(i)=='A'&&S.at(i+1)=='C'){
      R.at(i+1)++;
    }
    R.at(i+1)+=R.at(i);
  }
  //R.at(N-1)+=R.at(N-2);

/*
  cout<<endl;
  rep(i,N){
    cout<<R.at(i)<<endl;
  }
  cout<<endl;
*/

  rep(i,Q){
    int ans;
    ans = R.at(M.at(i).second-1)-R.at(M.at(i).first-1);
    cout<<ans<<endl;
  }

// cout<<ans<<endl;
}


Measured memory_bytes: 2292
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 10005;
int main(void){
    int a,b;
    while(true){
    scanf("%d%d",&a,&b);
    if(a == 0 && b == 0) break;
    if(a > b)printf("%d %d\n",b,a);
    else
        printf("%d %d\n",a,b);
    }

    return 0;
}


Measured memory_bytes: 3188
#include<cstdio>
#define MAX_SET_SIZE 100000

bool is_find_by_binary_search(int source[], int source_size, int target) {
  int headIndex = 0, tailIndex = source_size;

  while(headIndex < tailIndex) {
    int midIndex = (headIndex + tailIndex) / 2;

    if(source[midIndex] == target) {
      return true;
    }

    if(target < source[midIndex]) {
      tailIndex = midIndex;
    } else {
      headIndex = midIndex + 1;
    }
  }

  return false;
}

int main() {
  int S[MAX_SET_SIZE];
  int size_s;
  int size_t;

  scanf("%d", &size_s);
  for(int i = 0; i < size_s; i++) {
    scanf("%d", &S[i]);
  }

  scanf("%d", &size_t);
  int t_elem;
  int included_count = 0;
  for(int i = 0; i < size_t; i++) {
    scanf("%d", &t_elem);

    if(is_find_by_binary_search(S, size_s, t_elem)) {
      included_count++;
    }
  }

  printf("%d\n", included_count);
}



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

typedef long long LL;
typedef double DB;

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

const int MOD   = 1e9+7;
const int MAXN  = 1010;


int main() {
#ifdef LOCAL
    freopen("sample.in","r",stdin);
#endif
    ios::sync_with_stdio(false);
    int n,k,Max=0,Min=0x7f7f7f;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>k;
        Max=max(Max,k);
        Min=min(Min,k);
    }
    cout<<Max-Min<<endl;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define ld long double
#define vi vector<vector<ll> >
using namespace std;
const int MOD=1000000007;
const int MOD2=15000007;
const ll MAX=9187201950435737471;
const int N=100005;
const int INF=1e17;
const long double PI=acos(-1);

ll n;

ll f(ll x){
    //cout<<x<<"\n";
    if(x<=1){
        return 0;
    }
    ll ret=0;
    ret+=(f(x/2)+1)*2;
    return ret;
}

void solve(int T){
    cin>>n;
    cout<<f(n)+1;
}

int main() {
    fastio
    int T=1;
    //cin>>T;
    for(int i=1;i<=T;i++){
        solve(i);
        //if(i<T)cout<<"\n";
    }
    return 0;
}




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

int cmp_ko(const void *a, const void *b) {
    return *(char*)a - *(char*)b;
}

int cmp_sho(const void *a, const void *b) {
    return *(char*)b - *(char*)a;
}

void debug(char string[]) {
    int i;
    for(i = 0; i < 8; i++ ) {
        printf("%c ",string[i]);
    }
}

int main(void) {
    int i, j, n, length, max, min, count = 0;
    char strnum[9];
    scanf("%d",&n);
    for(j = 0; j < n; j++ ) {
        count = 0;
        scanf("%s",strnum);
        qsort(strnum, 8, sizeof(char), cmp_sho);
//                debug(strnum);
        max = atoi(strnum);
        qsort(strnum, 8, sizeof(char), cmp_ko);
 //              debug(strnum);
        for(i = 0; i < 8; i++ ) {
            if(strnum[i] == '0') {
                count++;
            }
        }
        if(count) {
            for(i = 0; i < 9 - count; i++ ) {
                strnum[i] = strnum[i + count];
            }
            for(;i < 9; i++ ) {
                strnum[i] = 0;
            }
        }
        min = atoi(strnum);       
        printf("%d\n",max - min);
    }
    return 0;
}

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

int main() {
    ll N, K;
    cin >> N >> K;

    ll output = 0;

    for (ll i = K; i <= N + 1; i++) {
        ll min = (i - 1) * i / 2;
        ll max = (2 * N - i + 1) * i / 2;
        min %= 1000000007;
        max %= 1000000007;
        ll tmp = max - min + 1;
        tmp %= 1000000007;
        output += tmp;
        output %= 1000000007;
    }
    if (output < 0) {
        output += 1000000007;
    }

    cout << output << endl;

    return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

int main(void){
    string s;
    cin >> s;

    rrep(i, s.size() - 1, 0){
        if(i - 4 >= 0 && s[i-4] == 'd' && s[i-3] == 'r' && s[i-2] == 'e' && s[i-1] == 'a' && s[i] == 'm'){
            i -= 4;
        }else if(i - 6 >= 0 && s[i-6] == 'd' && s[i-5] == 'r' && s[i-4] == 'e' && s[i-3] == 'a' && s[i-2] == 'm' && s[i-1] == 'e' && s[i] == 'r'){
            i -= 6;
        }else if(i - 4 >= 0 && s[i-4] == 'e' && s[i-3] == 'r' && s[i-2] == 'a' && s[i-1] == 's' && s[i] == 'e'){
            i -= 4;
        }else if(i - 5 >= 0 && s[i-5] == 'e' && s[i-4] == 'r' && s[i-3] == 'a' && s[i-2] == 's' && s[i-1] == 'e' && s[i] == 'r'){
            i -= 5;
        }else{
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 512
X, Y, Z, K = map(int, input().split())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
ab=sorted(s+t for t in B for s in A)[-1:-K-1:-1]
abc=sorted(i+x for i in ab for x in C)[-1:-K-1:-1]
print(*abc,sep="\n")

Measured memory_bytes: 161472
#include<bits/stdc++.h>
using namespace std;
#define bolt ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
typedef long long ll;
typedef long double ld;
const ll mod = 1000000007;
bool isprime(ll n){for(ll i=2;i*i<=n;++i){if(n%i==0){return false;}}return true;}
ll factorial(ll n){return (n==1 || n==0) ? 1:n*factorial(n-1);}
ll power(ll x,ll y){ll res=1;x=x%mod;while(y>0){if(y&1)res=((res%mod)*(x%mod))%mod;y=y>>1;x=((x%mod)*(x%mod))%mod;}return res;}
ll ncr(ll n,ll r){ll res=1;if(r>n)return 0;if(r>n-r)r=n-r;for(ll i=0;i<r;i++){res=((res%mod)*((n-i)%mod))%mod;res=((res%mod)*(power(i+1,mod-2))%mod)%mod;}return res;}
ll gcd(ll a,ll b){if (a==0)return b;return gcd(b%a,a);}
ll lcm(ll a,ll b){return (a/gcd(a,b)*b);}
ll max(ll a,ll b){ll sol=a>b?a:b;return sol;}
ll min(ll a,ll b){ll sol=a<b?a:b;return sol;}
int main()
{
   bolt;
   ll h,a;
   cin>>h>>a;
   cout<<ceil(1.0*h/a);

}


Measured memory_bytes: 256
//C++14 (Clang 3.8.0)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#define rp(i,a,b) for(int (i)=(int)(a);i<(int)(b);++i)

using namespace std;

typedef long long ll;
/*
struct aInt{
    int index;
    long long value;
    aInt(int i, int v){
        index = i;
        value = v;
    }
    bool operator<( const aInt& right ) const {
        return value == right.value ? index < right.index : value < right.value;
    }
};
*/
int main(){
    int N,y=0;
    ll x;
    ll ans = 1LL<<62;;
    vector<ll> a;
    vector<ll>a_c;
    cin>>N>>x;
    rp(i,0,N){ll A;cin>>A;a.push_back(A);a_c.push_back(A);}
    rp(i,0,N){
        ll tmp=0;
        rp(j,0,N) {
            //cout<<(j+N-i)%N<<endl;
            a_c[j] = min(a_c[j],a[(j+N-i)%N]);
            tmp+=a_c[j];
        }
        ans = min(ans,tmp + x*i);
    }
    cout<<ans<<endl;



        return 0;
};


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

N, M, Q = map(int, input().split())
ans = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    l, r = map(int, input().split())
    ans[l][r] += 1

for i in range(1, N+1):
    for j in range(N):
        ans[i][j+1] += ans[i][j]

for _ in range(Q):
    l, r = map(int, input().split())
    res = 0
    for i in range(l, r+1):
        res += ans[i][r]
    print(res)


Measured memory_bytes: 59100
from collections import deque
N = int(input())
P = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    P[a-1].append((b-1, i))
    P[b-1].append((a-1, i))
ans = [0] * N
q = deque()
q.append((0, 0))
colmax = 0
while q:
    u, pcol = q.popleft()
    icol = 1
    for v, i in P[u]:
        if ans[i] != 0:
            continue
        if icol == pcol:
            icol += 1
        ans[i] = icol
        q.append((v, icol))
        colmax = max(colmax, icol)
        icol += 1

print(colmax)
for i in range(N-1):
    print(ans[i])


Measured memory_bytes: 72480
import numpy as np
H, W = map(int, input().split())
A = np.array([list(map(int, input().split())) for _ in range(H)])
B = np.array([list(map(int, input().split())) for _ in range(H)])

C = abs(A - B)
# print (C)

D = 80 * (H + W + 1) + 10
D2 = D * 2

dp = [[0] * (W) for _ in range(H)]

dp[0][0] = 1 << (D - int(C[0][0]))
# print (dp[0][0])
dp[0][0] |= 1 << (D + int(C[0][0]))
# print ((dp[0][0]))



# print (dp[0][0])
dp = np.array(dp)

for h in range(H):
    for w in range(W):
        tmp = int(C[h][w])
        if h:
            dp[h][w] |= dp[h - 1][w] << tmp
            dp[h][w] |= dp[h - 1][w] >> tmp
        if w:
            dp[h][w] |= dp[h][w - 1] << tmp
            dp[h][w] |= dp[h][w - 1] >> tmp

        
ans = D2
# print (ans)
tmp = dp[H - 1][W - 1]
for i in range(D2):
    if (tmp >> i) & 1:
        ans = min(ans, abs(i - D))

print (ans)



Measured memory_bytes: 29844