akhauriyash/Code-Regression huggingface dataset:
import sys

SENTINEL = 10 ** 9 + 1
cnt = 0


def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [SENTINEL]
    R = A[mid:right] + [SENTINEL]

    i, j = 0, 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


n = int(input())
A = list(map(int, sys.stdin.readline().split()))
merge_sort(A, 0, n)
print(*A)
print(cnt)



Measured memory_bytes: 61652
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        return root

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot: return
        if self.size[xroot] <= self.size[yroot]:
            self.parents[xroot] = yroot
            self.size[yroot] += self.size[xroot]
        else:
            self.parents[yroot] = xroot
            self.size[xroot] += self.size[yroot]

N, M = map(int, input().split())

uf = UnionFind(N)

for i in range(M):
    a, b = map(int, input().split())
    uf.unite(a - 1, b - 1)

print(max(uf.size))

Measured memory_bytes: 93980
#include<stdio.h>
int main()
{
    char *p,s[1003];
    scanf("%s", s);
 	p=s;
    while(*p++);
    p-=2;
    if(*p++ =='s'){
      *p++= 'e';
    }
    *p++ ='s';
    *p=0;
    printf("%s\n",s);
    return 0;
}

Measured memory_bytes: 1664
#include <stdio.h>
int main(void)
{
	int i, j, all, num, check[4][13] = {{0}};
	char s[4] = {'S', 'H', 'C', 'D'}, suit;
	scanf("%d", &all);
	while (scanf("%*c%c %d", &suit, &num) != EOF) {
		switch (suit) {
			case 'S' : check[0][num - 1] = 1; break;
			case 'H' : check[1][num - 1] = 1; break;
			case 'C' : check[2][num - 1] = 1; break;
			case 'D' : check[3][num - 1] = 1; break;
		}
	}
	for (i = 0; i < 4; i++)
		for (j = 0; j < 13; j++)
			if (check[i][j] == 0)
				printf("%c %d\n", s[i], j + 1);
	return 0;
}

Measured memory_bytes: 596
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
edge = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edge.append((a, b, -c))

inf = 10**18
score = [inf] * (N + 1)
score[1] = 0

for _ in range(N - 1):
    for a, b, c in edge:
        score[b] = min(score[b], score[a] + c)

goal = score[N]
for a, b, c in edge:
    score[b] = min(score[b], score[a] + c)


if goal != score[N]:
    print("inf")
else:
    print(-goal)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//using ll = long long;
using P = pair<int,int>;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=998244353;

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

template<long long mod = 1000000007>
struct modint{
	long long a;

	modint() : a(0){}
	modint(long long t){
		a = t % mod;
		if(a < 0) a += mod;
	}

	operator long long() const{ return a; }

	bool operator==(const modint &x) const{ return a == x.a; }
	bool operator!=(const modint &x) const{ return a != x.a; }

	modint operator-() const{ return modint(a ? (mod - a) : 0); }
	modint operator~() const{ return pow(mod - 2); }

	modint operator+(const modint &x) const{ return modint(*this) += x; }
	modint operator-(const modint &x) const{ return modint(*this) -= x; }
	modint operator*(const modint &x) const{ return modint(*this) *= x; }
	modint operator/(const modint &x) const{ return modint(*this) /= x; }

	modint &operator+=(const modint &x){
		a += x.a;
		if(a >= mod) a -= mod;
		return *this;
	}
	modint &operator-=(const modint &x){
		a -= x.a;
		if(a < 0) a += mod;
		return *this;
	}
	modint &operator*=(const modint &x){
		a = a * x.a % mod;
		return *this;
	}
	modint &operator/=(const modint &x){
		a = a * (~x).a % mod; 
		return *this;
	}

	friend ostream &operator<<(ostream &os,const modint &x){
		return os << x.a;
	}
	friend istream &operator>>(istream &is,modint &x){
		long long t;
		is >> t;
		x = modint(t);
		return is;
	}

	modint pow(long long x) const{
		modint ret = 1,tmp = a;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}
};

vector<vector<int>> divisorTable(int n){
	vector<vector<int>> ret(n + 1);
	for(int i = 1;i <= n;i++){
		for(int j = i;j <= n;j += i) ret[j].push_back(i);
	}
	return ret;
}

const int MAX_A = 1000000;

int n,a[200010];
modint<MOD> coef[MAX_A + 5];

signed main(){
	cin >> n;
	for(int i = 0;i < n;i++) cin >> a[i];
	for(int i = 2;i <= MAX_A;i++) coef[i] = -modint<MOD>(i - 1) / modint<MOD>(i);
	coef[1] = 1;
	for(int i = 2;i * 2 <= MAX_A;i++){
		for(int j = i * 2;j <= MAX_A;j += i) coef[j] -= coef[i];
	}
	vector<vector<int>> dt(MAX_A + 5);
	for(int i = 1;i <= MAX_A;i++){
		for(int j = i;j <= MAX_A;j += i) dt[j].push_back(i);
	}
	modint<MOD> cnt[MAX_A + 5] = {},ans = 0;
	for(int i = 0;i < n;i++){
		modint<MOD> tmp = 0;
		for(int d : dt[a[i]]){
			tmp += coef[d] * cnt[d];
			cnt[d] += a[i];
		}
		ans += tmp * modint<MOD>(a[i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 198272
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef unsigned int uint;

void solve(){
	int N, A, B; cin >> N >> A >> B;
	if(A > B) puts("0");
	else if(N == 1 && A != B) puts("0");
	else printf("%lld\n", (ll)(N - 2) * (B - A) + 1);
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

long long N, a[100000], x;
long long countCCCC;

void Cal(long long i) {
	if (a[i] + a[i + 1] > x) {
		long long diff = a[i] + a[i + 1] - x;
		a[i + 1] -= diff;
		countCCCC += diff;
		
		if (a[i + 1] < 0) {
			a[i + 1] = 0;
		}
	}
	if (i < N-2) {
		Cal(++i);
	}
	return;
}



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

	Cal(0);
	cout << countCCCC << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
// iteration and input/output stream
#define rep(i,a,b) for(int i = int(a);i<=int(b);i++)
#define srep(i, begin, end) for (__typeof(end) i = begin; i != end; i++)
#define printarr(x) rep(i,0,x.size()-1) cout<<x[i]<<" "; cout<<endl;
#define all(v) v.begin(),v.end()
 
#define si(x) int x; scanf("%d", &x)
#define sll(x) ll x; scanf("%lld", &x)
#define pi(x) printf("%d", x)
#define pll(x) printf("%lld", x)
#define nl printf("\n")
#define tr(cont,it) \
for(decltype(cont.begin()) it = cont.begin(); it!= cont.end() ; it++)
 
#define endl "\n"
#define tc() int t; cin >> t ; while (t--)
//STL shortcuts
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define F first
#define S second
#define MP make_pair
 
// Error detection
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
 
using namespace std;
 
typedef long long int ll; // 64 bit integer
typedef unsigned long long int  ull; // 64 bit unsigned integer
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<int,ll> pill;
 
inline void smax(int &x , int y) { x = max(x , y) ; }
inline void smin(int &x , int y) { x = min(x , y) ; }
 
#define MOD 1000000007
#define inf 4000000000000000000LL
#define SYNC std::ios::sync_with_stdio(false);  cin.tie(NULL);

vvi adj;
vi dp;
vi in_degree; 
vi out_degree;

int f(int v)
{
    if(dp[v]!=-1)
    {
        return dp[v];
    }
    else
    {
        // dp[i] = 0;
        int maxi = 0;
        if(out_degree[v]<1) return dp[v] = 0;
        for (int i = 0; i < adj[v].size(); i++)
        {
            int u = adj[v][i];
            maxi = max(maxi,f(u));
        }
        dp[v] = 1+ maxi;
        return dp[v];
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("err.txt","w",stderr);
    #endif
    SYNC
    int n,m;
    cin>>n>>m;
    adj.assign(n+1,vi());
    in_degree.assign(n+1,0);
    out_degree.assign(n+1,0);
    for (int i = 0; i < m; i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        in_degree[y]++;
        out_degree[x]++;
    }
    dp.assign(n+1,-1);// dp[i] = len(longest path starting at vertex i)
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if(dp[i]==-1)
        {
            dp[i] = f(i);
        }
        ans = max(ans,dp[i]);
    }
    // for (int i = 1; i <= n; i++)
    // {
    //     trace3(i,in_degree[i],out_degree[i]);
    // }
    cout<<ans<<"\n";


     return 0;
}

Measured memory_bytes: 11792
def main():
    n, k = map(int, input().split())
    a = list(map(lambda x: int(x)-1, input().split()))
    visited = [0]
    visited_set = {0}
    now = 0
    for i in range(2*n):
        now = a[now]
        if now in visited_set:
            break
        else:
            visited.append(now)
            visited_set.add(now)
    l = len(visited)
    v = visited.index(now)
    if k < v:
        print(visited[k]+1)
    else:
        k -= v
        k %= (l-v)
        k += v
        print(visited[k]+1)


main()

Measured memory_bytes: 126456
#include<stdio.h>
#include<string.h>
#define LEN 100005

// プロセスを表す構造体
typedef struct pp
{
  char name[100];
  int t;
} P;

P Q[LEN];
int head, tail, n;

void enqueue(P x){
  Q[tail] = x;
  tail = (tail+1) % LEN;
}

P dequeue(){
  P x = Q[head];
  head = (head + 1) % LEN;
  return x;
}

int min(int a, int b) { return a < b ? a : b; }

int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  // 全てのプロセスをキューに順番に追加する
  for(int i=1; i<=n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1; tail = n+1;

  // シュミレーション
  while(head != tail){
    u = dequeue();
    c = min(q, u.t);  // q または必要な時間 u.t だけ処理を行う
    u.t -= c;  // 残りの必要な時間を計算
    elaps += c;  // 経過時間を加算
    if(u.t > 0) enqueue(u);  // 処理が完了していなければキューに追加
    else printf("%s %d\n", u.name, elaps);
  }

  return 0;
}



Measured memory_bytes: 11852
def main():
    """
    2 * N, square
    N domino
    domino, 2 * 1 or 1 * 2

    [pattern 1]
    aabb
    ccdd
    (a, d) and (b, c) => 2 colors
    (a, d) and c and b => 3 colors
    (c, b) and a and d => 3 colors

    [pattern 2]
    aab
    ccb
    => 3 colors

    [pattern 3]
    abc
    abc
    2 or 3 colors

    このような塗り方が何通りあるかを
    mod 1000000007 で求めてください．
    """
    N = int(input())
    S1 = input()
    S2 = input()

    a = 1
    before = "f"
    # f irst
    # v ertical
    # h orizontal
    i = 0
    while i < N:
        if S1[i] == S2[i]:
            # v
            if before == "f":
                a *= 3
            elif before == "v":
                a *= 2
            else:
                pass
            before = "v"
            i += 1
        else:
            # h
            if before == "f":
                # 3 P 2
                a *= 6
            elif before == "v":
                a *= 2
            else:
                a *= 3
            before = "h"
            i += 2

    print(a % 1000000007)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(int, N);
  VEC(int, A1, N);
  VEC(int, A2, N);
  vi v1(N), v2(N);
  v1[0] = A1[0];
  v2[N - 1] = A2[N - 1];
  rep(i, 1, N) {
    v1[i] = v1[i - 1] + A1[i];
    v2[N - i - 1] = v2[N - i] + A2[N - i - 1];
  }
  ll ans = 0;
  rep(i, 0, N) {
    ans = max(ans, (ll)v1[i] + v2[i]);
  }
  print(ans);
}


Measured memory_bytes: 256
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    H, W, K = list(map(int, sysread().split()))
    C = []
    for i in range(H):
        C.append(input())
    ans = 0
    for i in range(0, 2 ** H):
        for j in range(0, 2 ** W):
            ret = 0
            selected = []
            for l in range(W):
                if not (j >> l) & 1:
                    selected.append(l)
            for k in range(H):
                if not (i >> k) & 1 :
                    for v in selected:
                        if C[k][v] == '#':ret += 1
            if ret == K:
                ans += 1
    print(ans)


if __name__ == "__main__":
    run()

Measured memory_bytes: 9228
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <bitset>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <cassert>
#include <functional>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main() {
  int N;

  cin >> N;

  cout << (N + 1) / 2 << endl;

  return 0;
}


Measured memory_bytes: 256
x, y = map( int, input().split())
a = [1, 3, 5, 7, 8, 10, 12]
b = [4, 6, 9, 11]
c = [2]

if(x in a and y in a):
    print("Yes")

elif(x in b and y in b):
    print("Yes")

elif(x in c and y in c):
    print("Yes")

else:
    print('No')

Measured memory_bytes: 3064
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
c = 1
ans = 0
for i in range(N-1):
  if A[i] == A[i+1]:
    c += 1
  else:
    if c % 2 == 1:
      ans += 1
    c = 1
if c % 2 == 1:
  ans += 1
print(ans)


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

int main(void){
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  const int dx = tx - sx, dy = ty - sy;

  // Path 1
  cout << string(dy, 'U') << string(dx, 'R');

  // Path 2
  cout << string(dy, 'D') << string(dx, 'L');

  // Path 3
  cout << 'L' << string(dy + 1, 'U') << string(dx + 1, 'R') << 'D';

  // Path 4
  cout << 'R' << string(dy + 1, 'D') << string(dx + 1, 'L') << 'U';

  // EndLine
  cout << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n,m;
ll a[100005];
ll ans;
int main(void){
    cin>>n>>m;
    priority_queue<ll,vector<ll>,less<ll>> q;
    for(int i=0;i<n;i++){
        cin>>a[i];
        q.push(a[i]);
    }
    for(int i=0;i<m;i++){
        ll t=q.top();
        q.pop();
        t=t/2;
        q.push(t);
    }
    for(int i=0;i<n;i++){
        ll k=q.top();
        q.pop();
        ans+=k;
    }
    cout<<ans<<endl;

}


Measured memory_bytes: 5092
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int field[30][30];
	for(int i=0; i<30; i++){
		for(int l=0; l<30; l++){
			field[i][l] = 0;
		}
	}
	for(;;){
		int x,y,size;
		if(scanf("%d,%d,%d",&x,&y,&size) == EOF){break;}
		field[x+10][y+10]++;
		field[x+10][y+9]++;
		field[x+9][y+10]++;
		field[x+10][y+11]++;
		field[x+11][y+10]++;
		if(size>1){
			field[x+9][y+9]++;
			field[x+9][y+11]++;
			field[x+11][y+9]++;
			field[x+11][y+11]++;
		}
		if(size>2){
			field[x+10][y+8]++;
			field[x+10][y+12]++;
			field[x+12][y+10]++;
			field[x+8][y+10]++;
		}
	}
	int max = 0, white = 0;
	for(int i=10; i<20; i++){
		for(int l=10; l<20; l++){
			if(field[i][l] == 0){white++;}
			if(max<field[i][l]){max = field[i][l];}
		}
	}
	cout <<white<<endl<<max<<endl;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define int long long
#define REP(i,a,n) for(int i=a;i<(n);i++)
#define REP_sz(i,s) for(int i=0;i<s.size();i++)
#define RE return
#define FILL(a,b) memset(a,b,sizeof(a))
#define SO(a) sort(all(a))
#define pb push_back
#define sz(a) a.size()
#define V vector
#define ld long double
#define viit(a) vector<int>::iterator a
#define msit1(a) map<string,int>::iterator a
#define miit(a) map<int,int>::iterator a
#define msit2(a) map<int,string>::iterator a
#define IT iterator
#define FOR(i,a,n) for(int i=a;i<=(n);i++)
#define B(s) s.back()
#define all(a) a.begin(),a.end()
#define ER1(a) a.erase(a.begin())
#define ER0(a) a.erase(a.end())
#define pii pair<int,int>
#define pause system("PAUSE")
#define cls system("CLS")
using namespace std;
signed main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	int n;
    cin>>n;
    V<int>a,b;
    REP(i,0,n){
    	int x,y;
    	cin>>x>>y;
    	a.pb(x+y);
    	b.pb(x-y);
	}
	SO(a);
	SO(b);
	cout<<max(a[n-1]-a[0],b[n-1]-b[0]);
    return 0;
}


Measured memory_bytes: 6656
import sys
n = int(input())


def calc(num):
    total = 0
    while num > 0:
        total += num % 10
        num = num // 10
    return total

minNum = sys.maxsize


for i in range(1, n):
    currNum = calc(i) + calc(n-i)
    if currNum < minNum:
        minNum = currNum

print(minNum)

Measured memory_bytes: 3060
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <cassert>
#define SIZE 605
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int to[SIZE];
int dp[SIZE][SIZE];
int dp2[SIZE][SIZE];
int fac[SIZE];

void make()
{
	fac[0]=1;
	for(int i=1;i<SIZE;i++)
	{
		fac[i]=(ll) fac[i-1]*(ll) (2*i-1)%MOD;
	}
}
int main()
{
	make();
	int n,m;
	scanf("%d %d",&n,&m);
	memset(to,-1,sizeof(to));
	for(int i=0;i<m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);a--,b--;
		to[a]=b;
		to[b]=a;
	}
	ll ret=0;
	for(int L=2;L<=2*n;L+=2)
	{
		for(int s=0;s+L<=2*n;s++)
		{
			int l=s,r=s+L-1,cnt=0;
			bool up=true;
			for(int j=l;j<=r;j++)
			{
				if(to[j]!=-1)
				{
					if(to[j]<l||to[j]>r)
					{
						up=false;
						break;
					}
				}
				else cnt++;
			}
			if(!up) dp[l][r]=dp2[l][r]=0;
			else
			{
				dp2[l][r]=fac[cnt/2];
				dp[l][r]=dp2[l][r];
				for(int j=l;j<r;j++)
				{
					dp[l][r]-=(ll) dp2[l][j]*(ll) dp[j+1][r]%MOD;
					if(dp[l][r]<0) dp[l][r]+=MOD;
				}
				ret+=(ll) dp[l][r]*(ll) fac[n-m-cnt/2]%MOD;
				if(ret>=MOD) ret-=MOD;
				//printf("%d %d: %d\n",l,r,dp[l][r]);
			}
		}
	}
	printf("%lld\n",ret);
	return 0;
}


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

typedef long long ll;
typedef long double ld;
#define pi 3.14159265359;
#define inf (1 << 21);
#define mod 1000000007;

int main() {
    int N; cin >> N;
    vector<int> p(N);
    int M = 0, ans = 0;
    for (int i = 0; i < N; i++) {
        cin >> p.at(i);
        M = max(M, p.at(i));
        ans += p.at(i);
    }
    ans -= M;
    M /= 2;
    ans += M;
    cout << ans << endl;
}

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

int main(){
        int n, m;
        scanf("%d %d", &n, &m);
        std::vector<int> links[n+m];
        for(int i=0; i<n; i++){
                int k;
                scanf("%d", &k);
                for(int j=0; j<k; j++){
                        int l;
                        scanf("%d", &l);
                        links[i].push_back(n+l-1);
                        links[n+l-1].push_back(i);
                }
        }

        std::vector<bool> used(n+m, 0);
        std::queue<int> que;
        que.push(0);
        while(!que.empty()){
                int from = que.front();
                que.pop();
                used[from] = true;
                for(int to: links[from]){
                        if(!used[to]) que.push(to);
                }
        }

        bool cant = false;
        for(int i=0; i<n; i++) if(!used[i]) cant = true;
        if(cant) puts("NO");
        else puts("YES");
        return 0;
}

Measured memory_bytes: 8824
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

bool kmp(int l, string s) {
    int z = 0;
    vector<int> a(s.length() + 1);
    for (int i = 1; i <= s.length(); i++) {
        int x = i - 1;
        while (x && a[x] != i - 1 && s[a[x]] != s[i - 1]) x = a[x];
        if (x) a[i] = a[x] + 1;
        if (a[i] == l) return true;
    }
    //for (int i = 0; i <= s.length(); i++) cout << a[i] << ' ';
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    int n, z = 0;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        int l = i, r = n;
        while (l + 1 < r) {
            int m = (l + r) >> 1;
            string t = s.substr(i, m - i) + '!' + s.substr(m, string::npos);
            //cout << t << ' ' << m - i << ' ' << kmp(m - i, t) << '\n';
            if (kmp(m - i, t)) l = m;
            else r = m;
        }
        //cout << l - i << '\n';
        z = max(z, l - i);
    }
    cout << z;
}


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

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 101;
bool ok[N];

int main(){
  fastIO;
  int n, k;
  cin >> n >> k;
  int d,x;
  for(int i = 1; i <= k ; i ++ ){
    cin >> d;
    for(int j = 0 ; j < d; j ++ ){
      cin >> x;
      ok[x]=true;
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i ++ )
    if(!ok[i])
      ans++;
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 3692
s = input()
if s[::-1] == s:
    fir = (len(s) - 1) // 2
    sec = (len(s) + 3) // 2
    if s[:fir] == s[:fir][::-1]:
        if s[sec-1:] == s[sec-1:][::-1]:
            print('Yes')
            exit()
print('No')


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

int main(){
int A,B,s,t,u,v,w;
  cin >> A >> B;
  s = A+B;
  t = A-B;
  u = A*B;
  v = max(s,t);
  w = max(v,u);
  cout << w << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#define N 1005
using namespace std;
typedef long long ll;
char s[15];
ll a[10];
int main()
{
    int n;
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    for(int i=1; i<=n; i++)
    {
        scanf("%s",s);
        if(s[0]=='M')
            a[1]++;
        if(s[0]=='A')
            a[2]++;
        if(s[0]=='R')
            a[3]++;
        if(s[0]=='C')
            a[4]++;
        if(s[0]=='H')
            a[5]++;
     }
     ll sum=0;
    for(int i=1;i<=5;i++)
     for(int j=i+1;j<=5;j++)
     {
         for(int k=j+1;k<=5;k++)
             sum=sum+a[i]*a[j]*a[k];
     }
     printf("%lld\n",sum);
     return 0;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {

	static FastScanner scan = new FastScanner();

	public static void main(String[] args) {
		PrintWriter out = new PrintWriter(System.out);

		int n = scan.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		int[] c = new int[n - 1];

		int result = 0;
		scan(a, n);
		scan(b, n);
		scan(c, n - 1);

		int before = -1;
		int next;

		for (int i = 0; i < n; i++) {
			next = a[i];
			result += b[next - 1];
			if (next - before == 1) {
				result += c[before - 1];
			}
			before = next;
		}

		out.println(result);
		out.flush();
	}

	public static void scan(int[] target, int cnt) {
		for (int i = 0; i < cnt; i++) {
			target[i] = scan.nextInt();
		}
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 23252
use proconio::input;

fn main() {
  input! {
    n: usize,
    s: String,
  }

  let mut si: Vec<i64> = Vec::new();
  let mut cnt : [i64; 3] = [0; 3];

  for c in s.chars() {
    match c {
      'R' => si.push(0),
      'G' => si.push(1),
      'B' => si.push(2),
      _ => si.push(3),
    }
    cnt[*si.last().unwrap() as usize] += 1;
  }
  let mut res : i64 = (cnt[0] * cnt[1] * cnt[2]) as i64;
  for i in 0..n as usize {
    for j in 0..i as usize {
      let k: usize = i + (i as i32 -j as i32).abs() as usize;
      if k >= n {
        continue;
      }
      let mut vec = vec![si[i], si[j], si[k]];
      vec.sort();
      if vec == vec![0, 1, 2] {
        res -= 1;
      }
    }
  }
  println!("{}", res);
}

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	k=II()


	q,r=divmod(k,50)

	N=[49+q+50-r+1]*r+[49+q-r]*(50-r)
	print(50)
	print(*N)




if __name__ == "__main__":
	main()


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

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);   cout.tie(nullptr);
    if (ifstream("test.inp"))
    {
        freopen("test.inp", "r", stdin);
        #ifdef CHECKING
            freopen(taskname".out", "w", stdout);
        #else
            freopen("test.out", "w", stdout);
        #endif //CHECKING
    }
    else if (ifstream(taskname".inp"))
    {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }


    string s;   getline(cin, s);
    s += (s[s.size() - 1] == 's')? "es" : "s";
    cout << s;
}


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

int main(){
  int N,i;
  int x[100000];
  cin >> N;
  
  for(i=0; i<N; i++){
    cin >> x[i];
  }
  
  sort(x,x+i);
  
  if(x[(N/2)-1] != x[N/2]){
    cout << x[N/2] - x[(N/2)-1]  << endl;
  }
  if(x[(N/2)-1] == x[N/2]){
    cout << "0" << endl;
  }
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main() {
	string str;
	int n;

	cin >> str >> n;

	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'a') {
			continue;
		}
		int diff = 'z' + 1 - str[i];
		if (n >= diff) {
			str[i] = 'a';
			n -= diff;
			if (n == 0) {
				break;
			}
		}
	}
	if (n != 0) {
		str[str.length() - 1] = ((str[str.length() - 1] - 'a') + n) % 26 + 'a';
	}
	cout << str << endl;
}


Measured memory_bytes: 576
#include<bits/stdc++.h>
using namespace std;
#define itn int
#define int int64_t
#define fi first
#define se second
signed main(){
  int n,sum=0;
  int p[100]={};
  while(true){
    cin>>n;
    if(n==0) break;
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
      p[i%n]++;
      if(s[i]=='L') p[i%n]+=sum,sum=0;
      else if(s[i]=='S') sum+=p[i%n],p[i%n]=0;
    }
    sort(p,p+n);
    for(int i=0;i<n;i++){
      cout<<p[i]<<" ";
      p[i]=0;
    }
    cout<<sum<<"\n";
    sum=0;
  }
}



Measured memory_bytes: 3180
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cstring>
#include <math.h>
#define ll long long
ll gcd(ll a,ll b){
    ll s=1,c;
    while(a&&b){
        if((~a&1)&&(~b&1))
            a>>=1,b>>=1,s<<=1;
        else if(~a&1)a>>=1;
        else if(~b&1)b>>=1;
        else if(a>b)a=a-b;
        else c=b-a,b=a,a=c;
    }
    if(!a)return b*s;
    if(!b)return a*s;
}
using namespace std;
int main()
{
	int n;
	cin>>n;
	if(n>=30)
		cout<<"Yes";
	else 
		cout<<"No";
	return 0;
}

Measured memory_bytes: 3672
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

const long long mod = 1000000007;

int main(void){
    int n;
    cin >> n;
    string s[2];

    cin >> s[0];
    cin >> s[1];
    long long p;
    bool flag;
    int i;
    if(s[0][0] == s[0][1]){ //横向き
        flag = false;
        p = 6;
        i=2;
    }else if(s[0][0] == s[1][0]){ //立て向き
        flag = true;
        p = 3;
        i=1;
    }
    while(i<n){
        if( s[0][i] == s[0][i+1] ){ //横が同じ
            if(flag == true){ // 前回が立て向き
                p = (p*2) % mod;
            }else if(flag == false){ //前回が横向き
                p = (p*3) % mod; 
            }
            flag = false;
            i += 2;
        }else if( s[0][i] == s[1][i] ){ //立てが同じ
            if(flag == true){ // 前回が立て向き
                p = (p*2) % mod;
            }else if( flag == false){ //前回が横向き
                p = (p*1) % mod;
            }
            i++;
            flag = true;
        }
    }

    cout << p << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef pair<double,double> PD;
typedef pair<int,P> ed;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N;
  cin >> N;
  vi a(N);
  rep(i,N) {
    cin >> a[i];
  }
  int s = 0;
  rep(i,N) {
    s ^= a[i];
  }
  if(!s) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 768
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        C solver = new C();
        solver.solve(1, in, out);
        out.close();
    }

    static class C {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int N = Integer.parseInt(in.next());
            int Y = Integer.parseInt(in.next());
            for (int a = 0; a <= N; a++) {
                for (int b = 0; b <= N - a; b++) {
                    int c = N - a - b;
                    int total = a * 10000 + b * 5000 + c * 1000;
                    if (total == Y) {
                        System.out.println(a + " " + b + " " + c);
                        return;
                    }
                }
            }

            System.out.println("-1 -1 -1");
        }

    }
}



Measured memory_bytes: 39440
#include<stdio.h>

int main(){
    int h, m, s;
    
    scanf("%d",&s);
    
    h=s/3600;
    m=s%3600/60;
    s=s%3600%60;
    
    printf("%d:%d:%d\n",h,m,s);
    
    return 0;
}


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

int main() {
int n;
cin>>n;
int a[n][3]={0},dp[n][3]={0};
int i=0,j;
for(i=0;i<n;i++)
{
    for(j=0;j<3;j++)
    {
    cin>>a[i][j];
    if(i==0)
    dp[i][j]=a[i][j];
    else
    {
        dp[i][j]=max(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3])+a[i][j];
    }
    }
}
cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));


return 0;
}


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

bool dp[5010][5010];

int n,k;
int a[5010];



/* どちゃくそ楽な方法、実際にいい集合を作ってみた。
int ans;
int t;
int main(){

    cin >> n >> k;

    ans = n;
    t = 0;

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

    sort(a,a+n);

    for(int i=n-1; i!=-1; i--){
        if(t+a[i] < k){ //k以上の値はそれだけでいい集合()になるから省く
            t += a[i];
        }
        else{
            ans = min(ans,i);
        }
    }
    cout << ans << endl;

}*/


int main() {

    cin >> n >> k;

    for(int i=1; i<=n; i++){
        cin >> a[i];
    }

    sort(a+1,a+n+1);

    int my_left = 0,my_right = n+1;

    while(abs(my_left - my_right) > 1){

        int mid = (my_left + my_right)/2;

        for(int r=0; r<5010; r++){
            for(int w=0; w<5010; w++){
                dp[r][w] = false;
            }
        }

        dp[0][0] = true;

        bool need = false;

        for(int j=1; j<=n; j++){
            for(int t=0; t<=k; t++){
                if(dp[j-1][t]){
                    dp[j][t] = true;
                }
                if(mid!= j && t-a[j] >= 0){
                    if(dp[j-1][t-a[j]]) {
                        dp[j][t] = true;
                    }
                }

                /*if(dp[j][t] && k-a[mid] <=t && t < k){
                    need = true;
                }*/
            }
        }

        if(k>a[mid]) {
            for (int j = k - a[mid]; j < k; j++) {
                if (dp[n][j]) {
                    need = true;
                    break;
                }
            }
        }
        else{
            need = true;
        }

        if(need){
            my_right = mid;
        }
        else{
            my_left = mid;
        }
    }

    cout << my_left << endl;

    return 0;
}

Measured memory_bytes: 24832
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>

using namespace std;

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

	int t = N;
	int c = 0;

	while (t > 0) {
		c += t % 10;
		t /= 10;
	}

	if (N % c == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
#define INF32 1'050'000'000
#define INF64 4'000'000'000'000'000'000
using ll = long long;
using namespace std;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

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

    int N, A, B;
    cin >> N >> A >> B;
    vector<int> P(N);
    for (auto &&i : P) {
        cin >> i;
    }
    SORT(P);

    int one   = upper_bound(ALL(P), A) - P.begin();
    int two   = upper_bound(ALL(P), B) - P.begin() - one;
    int three = N - (one + two);
    int ans   = min(one, min(two, three));
    std::cout << ans << '\n';

    return 0;
}

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

using namespace std;

typedef long long ll;
const int MAX = 100005;
const int MOD = 1000000007;

#define F first
#define S second


void solve()
{
	ll n,l;
	cin>>n>>l;
	ll sum=0,ans=1e9,neg=-1e9;
	for(int i=1;i<=n;i++)
	{
		sum+=(l+i-1);
		//cout<<l+i-1<<endl;
		if(l+i-1>0)
			ans=min(ans,l+i-1);
		else
			neg=max(neg,l+i-1);
	}
	//cout<<ans<<" "<<neg<<endl;
	if(ans==1e9)
	{
		cout<<sum-neg<<endl;
		return;
	}	
	if(neg==-1e9)
	{
		cout<<sum-ans<<endl;
		return;
	}
	if(abs(ans)>abs(neg))
		cout<<sum-neg<<endl;
	else
		cout<<sum-ans<<endl;

	return ;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

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


int main()
{
	int n;
	double m;
	cin >> n >> m;
	vector<double> a(n);
	double sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a.at(i);
		sum += a.at(i);
	}

	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());
	double border = sum / (4 * m);
	string ans = "Yes";
	for (int i = 0; i < m; i++) {
		if (a.at(i) < border) {
			ans = "No";
			break;
		}
	}

	cout << ans << endl;

}



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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	string s,t; cin>>s>>t;
	int m=s.length(),n=t.length();

	vector<int> na1(m+1),nb1(m+1);
	vector<int> na2(n+1),nb2(n+1);
	rep(i,m){
		na1[i+1]+=na1[i]+(s[i]=='A');
		nb1[i+1]+=nb1[i]+(s[i]=='B');
	}
	rep(i,n){
		na2[i+1]+=na2[i]+(t[i]=='A');
		nb2[i+1]+=nb2[i]+(t[i]=='B');
	}

	int q; scanf("%d",&q);
	rep(_,q){
		int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); a--; c--;
		int dif1=(na1[b]-na1[a])-(nb1[b]-nb1[a]);
		int dif2=(na2[d]-na2[c])-(nb2[d]-nb2[c]);
		puts((dif1-dif2)%3==0?"YES":"NO");
	}

	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int N;
ll L,T;
ll X[101010],W[101010],ans[101010];

int main(){
  cin>>N>>L>>T;
  int id=-1;
  L*=2;
  T*=2;
  rep(i,N){
    cin>>X[i]>>W[i];
    X[i]*=2;
    if(W[i]==1&&id==-1) id=i;
  }
  if(id==-1){
    rep(i,N){
      X[i]=((X[i]-T)%L+L)%L;
      cout<<X[i]/2<<endl;
    }
    return 0;
  }
  vector<ll> V(N);
  rep(i,N){
    if(W[i]==1) V[i]=(X[i]+T)%L;
    else V[i]=((X[i]-T)%L+L)%L;
  }
  sort(V.begin(),V.end());

  ll hit=0;
  rep(i,N) if(W[i]==2){
    ll dif=(i>id)?(X[i]-X[id]):(L+X[i]-X[id]);
    ll TT=T;
    if(dif/2<=TT){
      hit++;
      TT-=dif/2;
    }
    hit+=TT/(L/2);
  }
  ll tid=(id+hit)%N;
  ll TX=(X[id]+T)%L;
  for(int i=N-1;i>=0;i--) if(V[i]==TX){
    rep(j,N){
      ans[(tid+j)%N]=V[(i+j)%N]/2;
    }
    break;
  }
  rep(i,N) cout<<ans[i]<<endl;
  return 0;
}


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

namespace ProblemC
{
    class Program
    {
        static void Main(string[] args)
        {
            var read = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var A = read[0];
            var B = read[1];
            var H = read[2];
            var M = read[3];

            var MRatio = M / 60.0;
            var degH = 2 * Math.PI * (H + MRatio) / 12.0;
            var degM = 2 * Math.PI * MRatio;
            var deg = Math.Abs(degH - degM);

            var res = B * B + A * A - 2 * A * B * Math.Cos(deg);
            res = Math.Sqrt(res);
            Console.WriteLine(res);
            

        }
    }
}


Measured memory_bytes: 28756
#include <bits/stdc++.h>
#define pb push_back
#define m_p make_pair
#define X first
#define Y second
using namespace std;
typedef long long ll;
const int maxn=1e3+50,M=1e9+7;
ll dp[maxn][maxn];
int main(){
	int n,m;
	cin>>n>>m;
	string s[n];
	for(int i=0;i<n;i++){
		cin>>s[i];
	}
	dp[0][0]=(s[0][0]=='.');
	for(int i=1;i<m;i++){
		dp[0][i]=(s[0][i]=='.');
		dp[0][i]=min(dp[0][i],dp[0][i-1]);
	}
	for(int i=1;i<n;i++){
	        dp[i][0]=(s[i][0]=='.');
		dp[i][0]=min(dp[i][0],dp[i-1][0]);
	}
	for(int i=1;i<n;i++){
	        for(int j=1;j<m;j++){
		    dp[i][j]=dp[i-1][j]+dp[i][j-1];
		    dp[i][j]%=M;
		    if(s[i][j]=='#')dp[i][j]=0;
		    }
        }
	/*for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cerr<<dp[i][j]<<"\t";
		}
		cerr<<endl;
	}
	cerr<<endl;*/
	cout<<dp[n-1][m-1];
	return 0;
}


Measured memory_bytes: 9472
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define fi first
#define se second
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> PlP;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    ll N,X,T;
    string S;
    cin >> N >> X >> T;
    ll ans = (N+X-1)/X;
    ans *= T;
    cout << ans << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
int main (){
  int n;
  cin >> n;
  string ans = "No";
  int n0 = n / 100;
  int n1 = (n - (n0*100)) /10;
  int n2 = n - (n0*100) - (n1 * 10);

  if(n0 == 7 || n1 == 7 || n2 == 7) ans = "Yes";

  cout << ans << endl;
}


Measured memory_bytes: 3624
#include<stdio.h>
int main(void){
    int n,x,y;
    scanf("%d",&n);
    int a[n];
    for(x=0;x<n;x++){
        scanf("%d",&a[x]);
    }
    for(y=n-1;y>0;y--){
                printf("%d ",a[y]);}
    printf("%d\n",a[0]);
return 0;
}

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

using namespace std;

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

	int zero, one;
	zero = one = 0;

	for (int i = 0; (size_t) i < s.size(); i++) {
		if (s[i] == '0') {
			zero++;
		} else {
			one++;
		}
	}
	cout << min(zero, one) * 2 << endl;
	return 0;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
#include <set>

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}

template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}


signed main(void) {
	int n, m, x;
	cin >> n >> m >> x;
	int smaller = 0;
	rep(i, m) {
		int tmp;
		cin >> tmp;
		if (tmp < x)smaller++;
	}
	if (smaller > m - smaller)print(m - smaller);
	else print(smaller);
}

Measured memory_bytes: 3496
#include <stdio.h>

int main(void){
  int a[100][100],r,c,i,j,sum = 0,SUM[100];
  scanf("%d %d",&r,&c);
  for(i = 0; i < r; i++){
    for(j = 0; j < c; j++){
      scanf("%d",&a[i][j]);
    }
  }
  for(i = 0; i < r; i++){
    for(j = 0; j < c; j++){
      printf("%d ",a[i][j]);
      sum += a[i][j];
      SUM[j] += a[i][j];
    }
    printf("%d\n",sum);
    sum = 0;
  }
  for(j = 0; j < c; j++){
    printf("%d ",SUM[j]);
    sum += SUM[j];
  }
  printf("%d\n",sum);
  return 0;
}


Measured memory_bytes: 2048
import java.util.*;

class UnionFind {
    private int parent[];
    private int height[];

    public UnionFind(int size) {
        parent = new int[size];
        height = new int[size];
        for (int i = 0; i < size; i++)
            parent[i] = i;
    }

    public int set(int p) {
        if (parent[p] == p)
            return p;
        parent[p] = set(parent[p]);
        return parent[p];
    }

    public void union(int p, int q) {
        if (set(p) == set(q))
            return;

        p = set(p);
        q = set(q);

        if (height[p] < height[q]) {
            union(q, p);
            return;
        }

        if (height[p] == height[q])
            height[p]++;

        parent[q] = p;
    }

    public boolean same(int p, int q) {
        return set(p) == set(q);
    }

    public String toString() {
        return Arrays.toString(parent);
    }
}

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

        UnionFind uf = new UnionFind(n);

        for (int i = 0; i < q; i++) {
            int cmd = in.nextInt();
            int a = in.nextInt();
            int b = in.nextInt();
            if (cmd == 0)
                uf.union(a, b);
            if (cmd == 1)
                System.out.println(uf.same(a, b) ? 1 : 0);
        }
    }
}



Measured memory_bytes: 101760
#include <bits/stdc++.h>
using namespace std ;
#define An setprecision(16) 
int main(){
    int r,D,x;
    cin >> r >> D >> x;
    for(int i=1;i<=10;i++){
        x = r*x-D;
        cout << x << endl;
    }
    
}

Measured memory_bytes: 3572