akhauriyash/Code-Regression huggingface dataset:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


def get_int():
    return int(input())


def get_str():
    return input().strip()


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


def get_char_list():
    return list(input().strip())


def bit1l(i):
    assert i > 0
    return len(bin(i)) - 3


def count1(i, xs):
    return sum(bool(i & x) for x in xs)


def main():
    n, k = get_int_list()
    xs = get_int_list()

    if k == 0:
        print(sum(xs))
        return
    gains = []
    for i in range(bit1l(k) + 1):
        gains.append((i, (len(xs) - count1(1 << i, xs) * 2) * (1 << i)))
    gains.sort(key=lambda x: x[1], reverse=True)
    best = 0
    for i, gain in gains:
        if gain < 0:
            break
        if k < best + (1 << i):
            continue
        best += (1 << i)
    print(sum((x ^ best) for x in xs))


if __name__ == '__main__':
    main()


Measured memory_bytes: 69104
#include <iostream>
#include <queue>
#include <assert.h>   
#include <vector>
#include <algorithm>
#include <time.h>
#include <numeric>
#include <string>
#include <cstring>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <numeric>
#include <deque>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cmath>
#include <cstdio>
using namespace std;


//#define double long double
#define int long long
//#define int unsigned long long

#define ll long long
#define ld long double 
#define pi pair<int, int> 
#define pl pair<ll,ll>  
#define pd pair<ld,ld> 
#define str string  
#define mp make_pair
#define vi vector<int> 
#define vl vector<ll> 
#define vd vector<ld> 
#define vs vector<str> 
#define vpi vector<pi> 
#define vpl vector<pl> 
#define vpd vector<pd> 
#define si set<int> 
#define FF(i,j,n) for(signed i=j;i<=n;i++)  
#define DD(i,j,n) for(signed i=j;i>=n;i--) 
#define F(i,j,n) for(signed i=j;i<n;i++)   
#define D(i,j,n) for(signed i=j;i>n;i--) 
#define mem(a,b) memset(a,b,sizeof(a))
#define ndl cout << endl
#define ull unsigned long long 

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;


#define sz(x) (signed)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back() 
#define fi first
#define se second
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define SHOWVECTOR(v) {std::cerr << #v << "\t: ";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOWVECTOR2(v) {std::cerr << #v << "\t:\n";for(const auto& xxx : v){for(const auto& yyy : xxx){std::cerr << yyy << " ";}std::cerr << "\n";}}
//math


const int mod = 1e9 + 7;

ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 


//DEBUG, compile with -DLOCAL
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
  cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
  DBG(t...); }
#ifdef LOCAL 
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define HERE cout << "===GOTHERE===" << endl
#else
#define dbg(...) 42
#define HERE 42
#endif


 /* ============== END OF HEADER ============== */





const int maxn = 1e5*3+20;

int n,_,q,k;

int f[12][12];
int ans = 0;

void solve(){
	cin >> n; 
	FF(i,1,n) f[to_string(i)[0]-'0'][i%10]++;
	FF(i,1,n) ans += f[i%10][to_string(i)[0]-'0'];
	cout << ans << endl;

}

signed main(){
  //clock_t t1 = clock();  
	IOS
	solve();
  
  //cout << "THE ALGORITHM TOOK: " << (clock() - t1) * 1.0 / CLOCKS_PER_SEC * 1000 << "ms"<< endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <queue>
#define INF 50000000000
struct vertex{
	std::vector<int> edge_to;
	std::vector<int> edge_cost;
	bool done;
	long long int mincost;
};
std::vector<vertex> G(100000);
typedef std::pair<int,int> P;
void shortest_path(int v);
int V,E;
int r;
int main(void){
	std::cin>>V>>E>>r;
	for(int i=0;i<E;i++){
		int from,to,cost;
		std::cin>>from>>to>>cost;
		G[from].edge_to.push_back(to);
		G[from].edge_cost.push_back(cost);
//		G[to].edge_to.push_back(from);
//		G[to].edge_cost.push_back(cost);		
	}
	shortest_path(r);
	for(int i=0;i<V;i++){
		if(G[i].mincost!=INF){
			std::cout<<G[i].mincost<<std::endl;
		}else {
			std::cout<<"INF"<<std::endl;
		}	
	}
	return 0;
}
void shortest_path(int v){
	for(int i=0;i<V;i++){
		G[i].mincost=INF;
	}
	G[v].mincost=0;
	std::priority_queue<P,std::vector<P>, std::greater<P> > que;
	que.push(P(0,v));//first:cost,second vertex
	while(!que.empty()){
		P p=que.top();que.pop();
		int from=p.second;
		if(G[from].mincost<p.first){
			continue;
		}
		for(int i=0;i<G[from].edge_to.size();i++){
			int to=G[from].edge_to[i];
			int cost_to=G[from].edge_cost[i];
			if(G[to].mincost>G[from].mincost+cost_to){
				G[to].mincost=G[from].mincost+cost_to;
				que.push(P(G[to].mincost,to));
			}
		}
	}
}

Measured memory_bytes: 18272
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;
#define REP(i,n) for (int i = 0; i <(n); ++i)
//debug 
#ifdef _DEBUG
#define debug(var)  do{cout << #var << " :";view(var);}while(0)
#else
#define debug(...)
#endif
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vector<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vector<vector<T> >& vv){ for(const auto& v : vv){ view(v); } }


int main(){
  int n, d, x;
  cin >> n >> d >> x;
  vector<int> a(n);
  REP(i,n) cin >> a[i];
  int cnt = 0;

  REP2(i,1,d+1){
    REP(j,n){
      REP(k,121){
        if(i == a[j]*k + 1) {
          cnt++;
        }
      }
    }  
  }

  cout << cnt + x << endl;
  return 0;
}

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

int main(){
  int n,i;
  cin>>n;
  vector<int> v(n);
  for(i=0;i<n;i++){
    cin>>v.at(i);
  }
  sort(v.begin(),v.end());
  double ans=v.at(0);
  for(i=0;i<n;i++){
  ans=(ans+v.at(i))/2;
  }
  cout<<ans;
  return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> t(n);
  vector<int> b(n);
  for(int i = 0; i < n; i++) cin >> t.at(i);
  int bp = 0;
  for(int i = 0; i < n; i++){
    cin >> b.at(i);
    bp += b.at(i);
  }
  
  int ans = t.at(0) + bp;
  int tp = t.at(0);
  for(int i = 1; i < n; i++){
    tp += t.at(i);
    bp -= b.at(i - 1);
    int all;
    all = tp + bp;
    ans = max(ans, all);
  }
  
  cout << ans << endl;  
    
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        var array = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

        var M = array.Max();
        if ((3 * M - array.Sum()) %2 == 0)
        {
            Console.WriteLine((3 * M - array.Sum()) / 2);
        }
        else
        {
            Console.WriteLine((3 * M + 3 - array.Sum()) / 2);
        }
    }
}

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

using namespace std;

const int N = 1e4 + 5;

int n, x, ans = 0;
long long a[N], b[N];
vector <int> res;

bool check (int x) {
    if (x < 2) return false;
    if (x < 4) return true;
    for (int i = 2; i * i <= x; i++) if (x % i == 0) return false;
    return true;
}

bool check2 (int p) {
    long long temp = a[n];
    for (int i = 1; i <= n; i++) b[i] = 0;
    for (int i = n; i >= 1; i--) {
        if (i < p) {
            for (int j = i; j >= 1; j--) if ((a[j] - b[j]) % p) return false;
            return true;
        }

        temp = a[i] - b[i];
        b[i - p + 1] -= temp;
    }

    for (int i = n; i >= 1; i--) if ((a[i] - b[i]) % p) return false;
    return true;
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n + 1; i++) {
        scanf("%d", &x); a[n - i + 1] = x;
        ans = __gcd(ans, x);
    }

    ans = abs(ans);
    for (int i = 2; i <= n; i++) if (check(i) && check2(i) && a[0] % i == 0) res.push_back(i);
    for (int i = 1; i * i <= ans; i++) {
        if (ans % i == 0) {
            if (check(i)) res.push_back(i);
            if (check(ans / i)) res.push_back(ans / i);
        }
    }

    sort(res.begin(), res.end()); res.resize(unique(res.begin(), res.end()) - res.begin());
    for (auto i: res) printf("%d\n", i);
    return 0;
}


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

/*
a%bの値は, aからa*bまでで一周する. (a%bとa*(b+1)%bの値, 2a%bとa*(b+2)%bの値はそれぞれ同じ)
よって, aをb回足す過程で各回a%bとcの値を比較し, b回経ってもfalseならfalse.
*/

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  
  bool can = false;
  for (int i = 1; i <= b; i++) {
    if ((a*i) % b == c) can = true;
  }
  
  cout << (can ? "YES" : "NO") << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

template<typename tp> inline void read(tp &x) {
    x = 0; char c = getchar(); int f = 0;
    for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}

namespace {
	const int mo = 1e6 + 3;
	inline int add(int x, int y) { x += y; return x >= mo ? x - mo : x; }
	inline int sub(int x, int y) { x -= y; return x < 0 ? x + mo : x; }
	inline int mul(int x, int y) { return (lo) x * y % mo; }
	inline int power(int a, int k = mo - 2) {
		int ans = 1;
		for (; k; k >>= 1, a = mul(a, a))
			if (k & 1) ans = mul(ans, a);
		return ans;
	}
}
const int N = 2e6 + 233;
int fac[N], ifac[N];

int main(void) {
	fac[0] = 1;
	rep (i, mo - 1) fac[i] = mul(fac[i - 1], i);
	ifac[mo - 1] = power(fac[mo - 1]);
	for (int i = mo - 2; i >= 0; i--)
		ifac[i] = mul(ifac[i + 1], i + 1);
	int q;
	for (read(q); q--; ) {
		int x, d, n;
		read(x); read(d); read(n);
		if (!x) cout << 0 << "\n";
		else if (!d) cout << power(x, n) << "\n";
		else {
			int invx = mul(x, power(d));
			if (invx + n - 1 >= mo) cout << 0 << "\n";
			else {
				int ans = mul(fac[invx + n - 1], ifac[invx - 1]);
				ans = mul(ans, power(d, n));
				cout << ans << "\n";
			}
		}
	}
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;

int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	ll n;
	cin >> n;
	vector <ll> arr(n);
	ll count = 0;
	ll mini = LLONG_MAX;
	ll sum = 0;
	for (int z=0;z<n;z++){
		cin >> arr[z];
		sum += abs(arr[z]);
		mini = min(mini,abs(arr[z]));
		if (arr[z] < 0){
			count++;
		}
	}
	if (count % 2 == 1){
		sum -= 2*mini;
	}
	cout << sum << endl;
	cin >> n;
}

Measured memory_bytes: 1024
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split(" ");
	var a = parseInt(input[0], 10);
	var c = parseInt(input[1], 10);
	//出力
	console.log('%d',a+c/2);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

namespace A
{
    class Program
    {
        public static void Main(string[] args)
        {
            var a = ReadLineIntSpilit();
            //0 = L  2 = R

            var result = "Balanced";

            if (a[0] + a[1] > a[2] + a[3]) {
                result = "Left";
            }else if(a[0] + a[1] < a[2] + a[3]) {
                result = "Right";
            }

            Console.WriteLine(result);
            ReadLine();
        }

        public static string ReadLine()
        {
            return Console.ReadLine();
        }

        public static string[] ReadLineStringSplit(char a = ' ')
        {
            return ReadLine().Split(a).ToArray();
        }

        public static int[] ReadLineIntSpilit(char a = ' ')
        {
            return ReadLine().Split(a).Select(x => int.Parse(x)).ToArray();
        }
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
using ll = long long;
using ld = long double;

ll resolv(ll a, ll b, ll x){
    if(x < a && a < b){
        return b - x;
    }
    if(x < b && b < a){
        return a - x;
    }
    if(a < x && x < b){
        ll t1 = x - a + b -a;
        ll t2 = b - x + b -a;
        return (t1 < t2)? t1: t2;

    }
    if(b < x && x < a){
        ll t1 = x -b + a -b;
        ll t2 = a - x + a -b;
        return (t1 < t2)? t1: t2;

    }
    if(x > a && a > b){
        return x -b;
    }
    if(x > b && b > a){
        return x - a;
    }

    return 0;
}

int main() {
    ll A,B,Q;
    vector<ll> s,t,x;
    cin >> A >> B >> Q;
    for (int i = 0; i < A; ++i) {
        ll a;
        cin >> a;
        s.push_back(a);
    }
    for (int j = 0; j < B; ++j) {
        ll b;
        cin >> b;
        t.push_back(b);
    }
    for (int k = 0; k < Q; ++k) {
        ll c;
        cin >> c;
        x.push_back(c);
    }

    sort(s.begin(),s.end());
    sort(t.begin(),t.end());


    for (int k = 0; k < Q; ++k) {
        auto backS = lower_bound(s.begin(),s.end(),x[k]) - s.begin();
        ll a,b;
        ll a2 = -1;
        ll b2 = -1;
        if(backS == 0) {
            a = s[0];

        }else if(backS == A){
            a = s[s.size()-1];
        } else{
            a = s[backS];
            a2 = s[backS-1];
        }


        auto backT = lower_bound(t.begin(),t.end(),x[k]) - t.begin();
        if(backT == 0) {
            b = t[0];

        }else if(backT == B){
            b = t[t.size()-1];
        }else{
            b = t[backT];
            b2 = t[backT-1];
        }

        vector<ll> r;
        r.push_back(resolv(a,b, x[k]));
        if(a2 > -1){
            r.push_back(resolv(a2,b,x[k]));
        }
        if(b2 > -1){
            r.push_back(resolv(a,b2,x[k]));
        }
        if(a2 > -1 && b2 > -1){
            r.push_back(resolv(a2,b2,x[k]));
        }

        sort(r.begin(),r.end());
        cout << r[0] << endl;


    }

    return 0;
}

Measured memory_bytes: 3828
#include<iostream>
main(){int n,m,i,a,c[1000001];for(std::string s;std::cin>>n>>m>>s,n;printf("%d\n",a))for(a=0,i=m;--i;a+=c[i]>=n)c[i]=s.substr(i,3)=="IOI"?c[i+2]+1:0;}

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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100
const int MOD = 1000000007;

void solve() {
    int a, b;
    cin >> a >> b;

    vector<vector<char>> v(maxn, vector<char>(maxn));
    for (int i = 0; i < maxn; i++) {
        for (int j = 0; j < maxn; j++) {
            if (i < maxn / 2)v[i][j] = '#';
            else v[i][j] = '.';
        }
    }
    a--, b--;
    for (int i = 0; i < maxn and a; i += 2) {
        for (int j = 0; j < maxn and a; j += 2)v[i][j] = '.', a--;
    }
    for (int i = maxn - 1; i >= 0 and b; i -= 2) {
        for (int j = 0; j < maxn and b; j += 2)v[i][j] = '#', b--;
    }
    cout << maxn << " " << maxn << endl;
    for (auto x: v) {
        for (auto j : x)cout << j;
        cout << endl;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}


Measured memory_bytes: 256
while True:
    x, y, s = map(int , input().split())
    if x == 0 and y == 0 and s == 0:
        break
    else:
        l = []
        for i in range(1, s):
            for j in range(1, i + 1):
                p = i * (100 + x) // 100 + j * (100 + x) // 100
                if p == s:
                    l.append(i * (100 + y) // 100 + j * (100 + y) // 100)
        print(max(l))


Measured memory_bytes: 5604
#include <bits/stdc++.h>
#define int long long 
#define uint unsigned long long 
#define double long double 
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define sett(c) (c).resize(unique(all(c))-(c).begin())
#define sz(a) (int)(a).size()
#define hell 1000000007
#define pi pair<int,int>
#define vi vector<int> 
#define vb vector<bool> 
#define vpi vector<pair<int,int>> 
#define x first 
#define y second 
#define endl '\n'
#define forn(i,n) for(int i = 0 ; i < n ; i++ )
#define for1(i,n) for(int i = 1 ; i < n ; i++ )
#define fore(i,a,b) for(int i = a ; (a>b)?(i>=b):(i<=b) ; (a>b)?(i--):(i++) ) 
 
using namespace std;
const int MAX = 1e6;

long long binpow(long long a, long long b) {

    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a ;
        a = a * a ;
        b >>= 1;
    }
    return res;
}

bool comp(const pi& a , const pi& b ){
        return a.y < b.y;
}

void solve(){
        int n ; cin >> n ; 
        int a[n+1],m[n] ; 
        forn(i,n+1) cin >> a[i] ;
        forn(i,n) cin >> m[i] ;
        int ans = 0 ;
        forn(i,n){
                if(a[i] >= m[i]){
                        ans += m[i];
                }else{
                        if(a[i] + a[i+1] <= m[i] ){
                                ans += a[i]+a[i+1];
                                a[i+1]= 0 ;
                        }else{
                                ans += m[i];
                                a[i+1] -= m[i] - a[i] ;
                        }
                }
        }
        cout << ans << endl; 
}       

 
int32_t main(){
        
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        cout << fixed;
        cout.precision(10);
 
#ifdef LOCAL_DEFINE
        freopen("input.txt","rt",stdin);
        freopen("output.txt","w",stdout);
#endif
 
        int t = 1;
        //cin >> t ;
        while(t--){
                solve();
        }
#ifdef LOCAL_DEFINE
        cout << "Time elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
#endif
 
        return 0;
}


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

int main () {

    int N;
    cin >> N;

    vector<string> w(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i];
    }

    map<string, int> W;
    for (int i = 0; i < N; i++) {
        W[w[i]]++;
    }

    for (int i = 1; i < N; i++) {
        if (!(w[i-1][w[i-1].size()-1] == w[i][0] && W[w[i]] == 1)) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		String a = sc.next();
		String b = sc.next();
		String c = sc.next();
		
		// 計算
		String result = "NO";
		if(a.charAt(a.length()-1) == b.charAt(0) && b.charAt(b.length()-1) == c.charAt(0)) result = "YES";
		
		// 出力
		System.out.println(result);
	}
}


Measured memory_bytes: 21972
#include <stdio.h>
int main ()
{
	int n ,q, a,a1[10000],a2[100000],k=0;
	scanf("%d",&n);
	for(int i = 0;i<n;i++)
	{
		scanf("%d",&a1[i]);
	}
	scanf("%d",&q);
	for(int i=0;i<q;i++)
	{
		scanf("%d",&a2[i]);
		for(int j=0;j<n;j++)
		{
			if(a1[j]==a2[i])
			 {
			 k++;
			 break;
			 }
		}
	}
	printf("%d\n",k);
	return 0;
}








Measured memory_bytes: 2104
object Main extends App {
  var a = readLine.split(" ").map(_.toInt)
  var sum = 2020L
    if(a(1)-a(0)<2019){
      for(i<-a(0) until a(1); j<-i+1 to a(1)) {
            sum = Math.min(sum,((i%2019) * (j%2019))%2019)
      }
    } else {
      sum = 0
    }
  print(sum)
}

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

#define MOD (1000000000+7)

long long pow( long long x, int n )
{
	long long res = 1;
	while( n > 0 ) {
		if( n & 1 ) res = res * x % MOD;
		x = x * x % MOD;
		n >>= 1;
	}
	return res;
}

int main() {
	int N, M, K;

	cin >> N >> M >> K;

	vector<long long> fac( N * M - 1, 1 );
	vector<long long> ifac( N * M - 1, 1 );
	for( int i = 2; i < N * M - 1; i++ ) {
		fac[i] = fac[i - 1] * i % MOD;
	}
	for( int i = 1; i < N * M - 1; i++ ) {
		ifac[i] = pow( fac[i], MOD - 2 );
	}
	long long ans = 0;
	for( int dx = 1; dx < M; dx++ ) {
		long long a = (long long)N * N * (M - dx) % MOD;
		ans += a * dx % MOD;
		ans %= MOD;
	}
	for( int dy = 1; dy < N; dy++ ) {
		long long a = (long long)M * M * (N - dy) % MOD;
		ans += a * dy % MOD;
		ans %= MOD;
	}

	ans *= fac[N * M - 2] * ifac[K - 2] % MOD;
	ans %= MOD;
	ans *= ifac[N * M - K];
	ans %= MOD;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3328
package main

import (
	"fmt"
)

func main() {
	var a [3][3]int
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			fmt.Scanf("%d", &a[i][j])
		}
	}

	var n, b int
	fmt.Scanf("%d", &n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &b)
		for i := 0; i < 3; i++ {
			for j := 0; j < 3; j++ {
				if a[i][j] == b {
					a[i][j] = 0
				}
			}
		}
	}
	if a[0][0]+a[0][1]+a[0][2] == 0 ||
		a[1][0]+a[1][1]+a[1][2] == 0 ||
		a[2][0]+a[2][1]+a[2][2] == 0 ||
		a[0][0]+a[1][0]+a[2][0] == 0 ||
		a[0][1]+a[1][1]+a[2][1] == 0 ||
		a[0][2]+a[1][2]+a[2][2] == 0 ||
		a[0][0]+a[1][1]+a[2][2] == 0 ||
		a[0][2]+a[1][1]+a[2][0] == 0 {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using ll=long long;
using namespace std;
#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //降
#define d_sort_vll(v) sort((v).begin(), (v).end(), greater<long long>()); //降
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順
#define say(t) cout << (t) << endl;
#define sum_vi(v) accumulate((v).begin(), (v).end(), 0);
#define sum_vll(v)accumulate((v).begin(), (v).end(), 0LL);

ll gcd(ll a, ll b) { return b?gcd(b, a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a, b)*b;}
const int IINF=(1<<30);
const ll LLINF = 1LL<<60;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
//   int x;
//   cin >> x;
//   cout << x*x*x << endl;
  double y;
  cin >> y;
  cout << int(pow(y, 3.0)) << endl;
}


Measured memory_bytes: 3388
#pragma region macro
#include <bits/stdc++.h>
using i64 = int_fast64_t;
#define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define rep(i, n) repeat(i, 0, n)

namespace std {
template <typename A, typename B>
string to_string(pair<A, B> p);

string to_string(const string &s) {
    return '"' + s + '"';
}

string to_string(const char *s) {
    return to_string((string)s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for(int i = 0; i < static_cast<int>(v.size()); i++) {
        if(!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for(size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
};  // namespace std
#pragma endregion

void solve() {
    int x, y, a, b, c;
    std::cin >> x >> y >> a >> b >> c;
    std::vector<int> p(a), q(b), r(c);
    rep(i, a) std::cin >> p[i];
    rep(i, b) std::cin >> q[i];
    rep(i, c) std::cin >> r[i];
    sort(p.begin(), p.end(), std::greater<>());
    sort(q.begin(), q.end(), std::greater<>());
    sort(r.begin(), r.end(), std::greater<>());
    p.resize(x);
    q.resize(y);
    std::vector<int> ans(x + y + r.size());
    std::copy(p.begin(), p.end(), ans.begin());
    std::copy(q.begin(), q.end(), ans.begin() + x);
    std::copy(r.begin(), r.end(), ans.begin() + x + y);
    std::sort(ans.begin(), ans.end(), std::greater<>());
    std::cout << std::accumulate(ans.begin(), ans.begin() + x + y, 0LL) << std::endl;
}

int main() {
    // std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}

Measured memory_bytes: 2560
#include<iostream>

int main(){
    int A[100][100];
    int b[100];
    int c[100];
    int i,j,k,l,n,m;

    std::cin>>n>>m;

    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            std::cin>>A[i][j];
        }
    }

    for(i=0;i<m;i++){
        std::cin>>b[i];
    }

    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            c[i]+=A[i][j]*b[j];
        }
        std::cout<<c[i]<<std::endl;
    }

    return 0;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

#define MAX_N 100000

typedef long long ll;
typedef pair<int,int> pii;

const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

template<class TYPE>
struct edge{
    TYPE to,cost; 
    edge(TYPE t,TYPE c){
        to = t;
        cost = c;
    }
};

int main(){
    int N;
    cin >> N;
    map<int,int> m;
    for(int i = 0; i < N; i++){
        int a;
        cin >> a;
        m[a] = m[a] + 1;
    }
    int count = 0;
    for(auto ite = m.begin(); ite != m.end(); ite++){
        if(ite -> first > ite -> second) count += ite -> second;
        if(ite -> first < ite -> second) count += ite -> second - ite -> first;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 4736
import core.stdc.stdio;
import std.range;
import std.algorithm;

void main(){
	int[] buf_p = new int[1001];
	int[] buf_d = new int[1001*500];
	while(1){
	
	int n,m;
	scanf("%d%d",&n,&m);
	if(n==0&&m==0)
		break;
	int[] p = buf_p[0..++n];
	foreach(ref v;p[1..$])
		scanf("%d",&v);
	p[0]=0;
	int[] d=buf_d[0..n*(n-1)/2];
	int c=0;
	foreach(i;0..n)
		foreach(j;i+1..n)
			d[c++] = p[i]+p[j];
	sort(d);
	int ans;
	foreach(v;d){
		if(v*2>m)
			break;
		auto lb = d.assumeSorted.lowerBound(m+1-v);
		if(!lb.empty)
			ans=max(ans,v+lb[$-1]);
	}
	printf("%d\n",ans);
	
	}
}

Measured memory_bytes: 3920
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
using vi = vector<int>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;

int main(){
    int n,m;cin>>n>>m;
    vi a(m);
    rep(i,m) cin>> a[i];
    sort(a.begin(),a.end());
    //cout << a[0] << " " << a[m-1] << endl;
    int lg = abs(a[0]-a[m-1]);
    if(m==1){
        cout << 0 << endl;
        return 0;
    }
    //cout << lg << endl;
    vi b(m-1);
    rep(i,m-1){
        b[i] = abs(a[i] - a[i+1]);
    }
    sort(b.begin(),b.end(),greater<int>());
    //cout << b[0] << endl;
    int cnt=0;
    while(cnt<n-1 && cnt<m-1){
        lg -= b[cnt];
        cnt++;
    }
    cout << lg << endl;
}

Measured memory_bytes: 1024
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# 初項s, 交差dのn個の数列の和
def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    r = int(input())
    print(3 * r * r)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3944
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();


    let mut ans: usize = 0;

    let mut stack = "".to_string();
    for cube in buf.chars() {
        if cube == '\n' {
            break;
        }

        if stack.len() == 0 {
            stack.push(cube);
            continue;
        }

        let prev = stack.chars().last().unwrap();
        if prev != cube {
            stack.pop();
            ans += 2;
            continue;
        }
        stack.push(cube);
    }
    println!("{}", ans);
}


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

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

#ifdef __WIN32
#define LLFORMAT "I64"
#define Rand() ((rand() << 15) + rand())
#else
#define LLFORMAT "ll"
#define Rand() (rand())
#endif

using namespace std;

const int maxn = 3e5 + 10, mod = 1e9 + 7;

int n, dp[maxn][6], way[maxn], ans;
char s[maxn];

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	way[n + 1] = 1;
	for (int i = n; i; --i) {
		way[i] = way[i + 1];
		if(s[i] == '?') {
			way[i] = (way[i] << 1) % mod;
		}
	}
	dp[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		char &c = s[i];
		if(c != '1') {
			for (int t, j = 0; j < 6; ++j) {
				if(t = dp[i - 1][j]) {
					int k = j + 1;
					if(k == 3 || k == 6) {
						k -= 2;
					}
					dp[i][k] = (dp[i][k] + t) % mod;
				}
			}
		}
		if(c != '0') {
			for (int t, j = 0; j < 6; ++j) {
				if(t = dp[i - 1][j]) {
					if(j != 3) {
						int k = j - 1;
						if(!j) {
							k = 3;
						}
						dp[i][k] = (dp[i][k] + t) % mod;
					}
					else {
						ans = ((long long) t * way[i + 1] + ans) % mod;
					}
				}
			}
		}
	}
	printf("%d\n", (ans + dp[n][3]) % mod);
	return 0;
}



Measured memory_bytes: 8704
#include<stdio.h>

int n,m;
int data[100001];	//data[i]は宿場町1〜iまでの距離である(宿場町1からにしたのはO(mn)をO(m+n)に改善するため)

int abs(int x){
	return x>=0?x:-x;
}
int main(){
	int i,pos = 1,sum = 0;
	int len[2] = {0};
	int c;
	data[1] = 0;
	scanf("%d%d",&n,&m);
	for(i = 2;i < n+1;i++){
		scanf("%d",len);
		len[1] += len[0];
		data[i] = len[1];
	}
	for(i = 0;i < m;i++){
		scanf("%d",&c);
		sum += abs(data[pos+c]-data[pos]);
		sum %= 100000;
		pos += c;
	}
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 1412
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (ll i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define MAX (500000)
#define pii pair<int, int>

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

class XY{
public:
  ll x, y;
  XY() {x = y = 0;}
  XY(ll u, ll v) {x = u; y = v;}
};

template<typename T1, typename T2>
void chmin(T1 &a, T2 b) {if(a > b) a = b;}
template<typename T1, typename T2>
void chmax(T1 &a, T2 b) {if(a < b) a = b;}

template<typename T1, typename T2>
ll mypow(T1 a, T2 n){
  if(n == 0) return 1;
  if(n == 1) return a;
  if(n % 2) return a * mypow(a, n - 1);
  ll tmp = mypow(a, n / 2);
  return tmp * tmp;
}

template<typename T>
int BS(vector<T> &V, int left, int right, T key){
  int mid = (left + right) / 2;
  if(V[mid] <= key) left = mid;
  else right = mid;
  if(right - mid == 1) return left;
  else return BS(V, left, right, key);
}

ll comb(ll n, ll r){
	ll res = 1;
  rep(i, 0, r){
    res *= n - i;
    res /= i + 1;
  }
  return res;
}

template<typename T>
T euclid(T a, T b){
  if(b == 0) return a;
  else return euclid(b, a % b);
}

vector<ll> fact(MAX, 0), fact_inv(MAX, 0);

ll pow_mod(ll a, ll b){
	ll res = 1;
	while(b > 0){
		if(b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}

void prepare_comb_mod(ll n){
	fact[0] = 1LL;
	for(ll i = 0; i < n; i++) fact[i+1] = fact[i] * (i + 1) % MOD;
	fact_inv[n] = pow_mod(fact[n], MOD - 2);
	for(ll i = n - 1; i >= 0; i--) fact_inv[i] = fact_inv[i + 1] * (i + 1) % MOD;
}

ll comb_mod(ll n, ll r){
	return (fact[n] * fact_inv[r]) % MOD * fact_inv[n - r] % MOD;
}

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

void Main() {
  string S; cin >> S;
  int N = S.size() + 1;
  S = ">" + S + "<";
  vector<int> A(N, 0);
  rep(i, 0, S.size() - 1){
    if(S[i] == '>' && S[i + 1] == '<'){
      A[i] = 0;
      int cur = 1;
      int n = 1;
      while(true){
        if(i + n == N || S[i + n] == '>') break;
        chmax(A[i + n], cur);
        n++;
        cur++;
      }
      cur = 1;
      n = 1;
      while(true){
        if(i - n == -1 || S[i - n + 1] == '<') break;
        chmax(A[i - n], cur);
        n++;
        cur++;
      }
    }
  }
  ll res = 0;
  rep(i, 0, N){
    res += A[i];
    //cout << A[i];
  }
  //cout << endl;
  cout << res << endl;
}

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

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

  Main();
}


Measured memory_bytes: 10672
#![allow(unused_imports)]
#![allow(dead_code)]
use proconio::input;
use proconio::fastout;
use proconio::marker::*;

fn type_of<T>(_: T) -> String{
    let a = std::any::type_name::<T>();
    return a.to_string();
}

#[fastout]
fn main() {
    input! {
        a:i32,b:i32,
    }
    println!("{}",if a*b%2==0{"Even"}else{"Odd"});
}

Measured memory_bytes: 2148
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    if(n==2)    cout<<1;
    else
    {
        long long m=n-1;
    long long ans1=0;
    for(long long i=2;i<=sqrt(m);i++)
    {
        if(m%i==0)
        {
            ans1+=2;
        }
        if(i*i==m) ans1--;
    }
    for(long long i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            long long p=n;
            while(p%i==0)
            {
                p/=i;
            }
            if((p-1)%i==0)  ans1++;
        }
    }
    ans1++;
    cout<<ans1+1;
    }
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl;
// *min_element(c + l, c + r) *max_element(c + l, c + r)
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// struct Edge {
//   int to, id;
//   Edge(int to, int id): to(to), id(id) {}
// };

int main() {
  int N,K,C;cin>>N>>K>>C;
  string S;cin>>S;
  vector<P> issame(K);
  int i = 0,cnt = 0;
  while(cnt < K) {
    if(S[i] == 'o') {
      issame[cnt].first = i;
      i += C + 1;
      cnt++;
    } else {
      i++;
    }
  }
  reverse(S.begin(),S.end());
  cnt = 0;
  i = 0;
  while(cnt < K) {
    if(S[i] == 'o') {
      issame[K - cnt - 1].second = N - i -1;
      i += C + 1;
      cnt++;
    } else {
      i++;
    }
  }
  for(auto pir : issame) {
    //    cout << pir.first << " " << pir.second << endl;
    if(pir.first == pir.second) {
      cout << pir.first + 1 << endl;
    }
  }
}


Measured memory_bytes: 5164
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
    int a,b;
    cin >> a >> b;
    if(a + b < 10) cout << a + b << endl;
    else cout << "error" << endl;
}

Measured memory_bytes: 764
#include <iostream>
#include <string>
#include <stack>

bool balance(std::string &input) {
  std::stack<char> sc;
  for (auto ch : input) {
    if (ch == '[' || ch == '(') sc.push(ch);
    else if (ch == ']' || ch == ')') {
      if (!sc.empty()) {
        char p = sc.top();
        sc.pop();
        if ((ch == ']' && p != '[') || (ch == ')' && p != '(')) return false;
      } else return false;
    }
  }
  return sc.empty();
}

int main()
{
  std::string input;
  while (std::getline(std::cin, input) && input != ".") {
    if (balance(input)) std::cout << "yes";
    else std::cout << "no";
    std::cout << std::endl;
  }
  return 0;
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(){
    string T,ans;

    cin >> T;

    ans = "";
    for (char i : T){
        if(i == '?'){
            ans += 'D';
        }
        else{
            ans += i;
        }
    }

    printf("%s\n", ans.c_str());



}



Measured memory_bytes: 3868
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll

int a[1234];
int repr[1234],found[1234];
int addit(int val){
	int i;
	fd(i,62,0){
		if((1LL<<i)&val){
			if(found[i]){
				val^=repr[i];
			}
			else{
				found[i]=1;
				repr[i]=val;
				return 0;
			}
		}
	}
	return 0;
}

int checkit(int val){
	int i;
	fd(i,62,0){
		if((1LL<<i)&val){
			if(found[i]){
				val^=repr[i];
			}
			else{
				return 1;
			}
		}
	}
	return 0;
}

main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
    	int n;
    	cin>>n;
    	int i;
    	rep(i,n){
    		cin>>a[i];
    	}
    	string s;
    	cin>>s;
    	rep(i,100){
    		found[i]=0;
    	}
    	int flag=0;
    	fd(i,n-1,0){
    		if(s[i]=='0'){
    			addit(a[i]);
    		}
    		else{
    			int val=checkit(a[i]);
    			if(val==1){
    				flag=1;
    			}
    		}
    	}
    	cout<<flag<<endl;
    }
    return 0;   
}


Measured memory_bytes: 3628
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
def main():
	while True:
		try:
			form = [float(x) for x in input().split(" ")] 
		except:
			return
		else:
			if form[0] == 0:
				y = form[2] / form[1]
				x = (form[5] - y * form[4]) / form[3]
			else:
				b = form[1] / form[0]
				c = form[2] / form[0]
				e = form[4] - form[3] * b
				f = form[5] - form[3] * c
				y = f / e
				x = (form[2] - y * form[1]) / form[0] 
			print("{:.3f} {:.3f}".format(x,y))
			
if __name__ == '__main__':
  main()

Measured memory_bytes: 7432
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PLL = pair<ll, ll>;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repn(i,n) for(int i = 0; i <= (int)(n); i++)
#define srep(i,l,n) for(int i = l; i < (int)(n); i++)
#define srepn(i,l,n) for(int i = l; i <= (int)(n); i++)
#define drep(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define drepn(i,n) for(int i = (int)(n); i >= 0; i--)
#define size(s) (int)s.size()
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
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<class T = int> using V = vector<T>;
template<class T = int> using VV = vector<V<T>>;
bool isIn(int i, int j, int h, int w) {return i >= 0 && i < h && j >= 0 && j < w;}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void err() {cout << -1 << endl;}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ep emplace_back

const int MOD = 1000000007;
const int INF = 1e9;

#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    V<> c(n);
    rep(i, n) cin >> c[i];
    V<ll> dp(n+1, 0);
    dp[0] = 1;
    V<> pos[200001];
    rep(i, n) pos[c[i]].push_back(i);
    rep(i, n) {
        dp[i+1] += dp[i];
        dp[i+1] %= MOD;
        if(i > 0 && c[i] == c[i-1]) continue;
        int col = c[i];
        int it = lower_bound(all(pos[col]), i) - pos[col].begin();
        if(it > 0) {
            int j = pos[col][it-1] + 1;
            dp[i+1] += dp[j];
            dp[i+1] %= MOD;
        }
    }
    cout << dp[n] << endl;
}

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

using namespace std;
string reverse(string a)
{
string b="";
int n=a.length();int i;
for(i=n-1;i>=0;i--)
b+=a[i];
return b;	
}
int main () {
	string s;
	cin>>s;
	int i,j;
	int n=s.length();
	if(n%2 == 0)
	cout<<"No"<<endl;
	string k=reverse(s);
	//cout<<k<<endl;
	int x=s.compare(k);
	if(x==0)
	{
		
		int c=(n-1)/2;
		int d=(n+3)/2;
		string u,v;u=v="";
		for(i=0;i<c;i++)
		u+=s[i];
		for(i=d-1;i<n;i++)
		v+=s[i];
		string p,q;
		//cout<<u<<endl;
		//cout<<v<<endl;
		p=reverse(u);
		q=reverse(v);
		int g,f;
		g=p.compare(u);
		f=q.compare(v);
		if(g==0 && f==0)
		cout<<"Yes"<<endl;
		else
		cout<<"No"<<endl;
		
	}
	else
	cout<<"No"<<endl;
}



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

int main(){
	int a,b,ans=0;
	cin >> a >> b;
	vector<int> an(3);
	an[0]=a+b;
	an[1]=a-b;
	an[2]=a*b;
	
	ans = an[0];
	
	if(an[2]>an[1] && ans < an[2])
		  ans = an[2];
	else if(an[2]<an[1] && ans < an[1])
		  ans = an[1];
		
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <functional>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

void solve()
{
	string T, P;
	cin >> T >> P;
	int size = T.size() - P.size() + 1;
	for (int i = 0; i < size; ++i)
	{
		if (T[i] == P[0])
		{
			bool isSame = true;
			for (int j = 0; j < P.size(); ++j)
			{
				if (T[i + j] != P[j])
				{
					isSame = false;
					break;
				}
			}
			if (isSame)
			{
				cout << i << endl;
			}
		}
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define erep(i,a,n) for(int i = a;i<=n;i++)
typedef long long ll;
#define int long long
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>:
#define vbool vector<bool>
#define INF 1101010101010101010
#define MOD 1000000007
#define P = pair<int,int>;
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; }

signed main(){
  string s,t;
  cin >> s >> t;
  int n = s.size();
  int m = t.size();
  vvint is(26);
  rep(i,0,n) is[s[i] - 'a'].push_back(i);
  rep(i,0,n) is[s[i] - 'a'].push_back(i+n);
  int ans = 0;
  int p = 0;
  rep(i,0,m){
    int c = t[i] - 'a';
    if(is[c].size() == 0){
      cout << -1 << endl;
      return 0;
    }
    p = *lower_bound(is[c].begin(),is[c].end(),p)+1;
    if(p >= n){
      p -= n;
      ans += n;
    }
    // cout << ans << endl;
  }
  ans += p;
  cout << ans << endl;
}

Measured memory_bytes: 2800
#include <stdio.h>
int main(){
  int a,b,c,d,e;
  scanf("%d %d",&a,&b);
  c= a+b;
  d=a-b;
  e=a*b;
  if(c>=d && c>=e){
    printf("%d",c);
  }
  else if(d>=c && d>=e){
    printf("%d",d);
  }
  else if (e>=c && e>=d){
    printf("%d",e);
  }
  return 0;
}
  


Measured memory_bytes: 128
# include <bits/stdc++.h>
/// my holy template
# define F first    
# define S second
# define mp make_pair
# define pii pair<int,int>         
/// eveything goes according to my plan
# define long long long  
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector
/// countdown BEGAN. 10 , 9 , 8 ...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right
/// dzyn dzyn dzyn   
const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const long MXLL = 9223372036854775807;
const int Sz = 1110111;

using namespace std;

inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm("rdtsc" : "=A"(seed));
  srand(seed);
}
int n;          

int p[101][101];

int a[101][101];

int c[101];

int f[101][101][3];
                              
int main() 
{
  Read_rap ();  
  cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= 5; j++)
      for (int k = 1; k <= 2; k++)
        cin >> f[i][j][k];
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= 10; j++)
      cin >> p[i][j];   
            
  int ans = -MX;
  for (int mask = 1; mask < (1<<10); mask++) {
    memset (a, 0, sizeof a);
    memset (c, 0, sizeof c);
    for (int i = 0; i < 10; i++) {  
      if (mask & (1<<i)) {
        int x = i/2, y = (i & 1);
        a[x + 1][y + 1] = 1;
      }
    }               
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= 5; j++)
        for (int k = 1; k <= 2; k++) {
          if (f[i][j][k] && a[j][k]) {  
            c[i] ++;
          }
        }      
    int profit = 0;             
    for (int i = 1; i <= n; i++)
      profit += p[i][c[i]];
    ans = max (ans, profit);
  }             
  cout << ans;

  return 0;
} 










// Coded by Z...

Measured memory_bytes: 512
//90A
#include <bits/stdc++.h>
using namespace std;
int main(void){
   vector <string> L(3, " ");
   for (int i=0; i <3; i++){
       cin >> L[i];
   }
   for (int i=0; i <3; i++){
       cout << L[i][i];
   }
}

Measured memory_bytes: 256