akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
// using
using namespace std;
// typedef
typedef long long ll;
// define
#define FOR(i,a,b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define LB(c, x) lower_bound(c.begin(), c.end(), x)
#define UB(c, x) upper_bound(c.begin(), c.end(), x)
#define LI(c, x) distance(c.begin(), LB(c, x))
#define UI(c, x) distance(c.begin(), UB(c, x))

// functions
template <class T> T ceil(T a, T b) {
    return (a + b - 1) / b;
}
template <class T> T round(T a, T b) {
    return (a + b / 2) / b;
}
template <class T> T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}
template <class T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
template <class T> bool amax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X, Y, Z, K;
    cin >> X >> Y >> Z >> K;
    vector<ll> A(X), B(Y), C(Z);
    REP(i, X) {
        cin >> A[i];
    }
    REP(i, Y) {
        cin >> B[i];
    }
    REP(i, Z) {
        cin >> C[i];
    }
    vector<ll> S(X * Y);
    REP(i, X) {
        REP(j, Y) {
            S[i * Y + j] = A[i] + B[j];
        }
    }
    SORT(S), REVERSE(S);
    vector<ll> T(K * Z, 0);
    REP(i, min(X * Y, K)) {
        REP(j, Z) {
            T[i * Z + j] = S[i] + C[j];
        }
    }
    SORT(T), REVERSE(T);
    REP(i, K) {
        cout << T[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 31616
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int x = sc.nextInt();

        System.out.println(calc(a,b,c,x));
    }

    public static int calc(int a, int b, int c, int x) {
        int count = 0;
        int y1 = 0;
        int y2 = 0;
        int y3 = 0;
        for (int i=0;i<=a;i++) {
            y1 = i*500;
            for (int j=0;j<=b;j++) {
                y2 = j*100;
                for (int k=0;k<=c;k++) {
                    y3 = k*50;
                    if (y1+y2+y3 == x) {
                      count++;
                    }
                }
            }
        }
        return count;
    }
}


Measured memory_bytes: 35728
N = int(input())
S = input()
R = [0] * 10000
G = [0] * 10000
B = [0] * 10000
for i in range(N):
    R[N-i-1] = R[N-i]
    G[N-i-1] = G[N-i]
    B[N-i-1] = B[N-i]
    if S[N-i-1] == 'R':
        R[N-i-1] += 1
    elif S[N-i-1] == 'G':
        G[N-i-1] += 1
    else:
        B[N-i-1] += 1

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]:
            continue
        if S[i] != 'G' and S[j] != 'G':
            ans += G[j+1]
            if 2 * j - i < N and S[2 * j - i] == 'G':
                ans -= 1
        if S[i] != 'R' and S[j] != 'R':
            ans += R[j + 1]
            if 2 * j - i < N and S[2 * j - i] == 'R':
                ans -= 1
        if S[i] != 'B' and S[j] != 'B':
            ans += B[j + 1]
            if 2 * j - i < N and S[2 * j - i] == 'B':
                ans -= 1
print(ans)



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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

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

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

    int h, w;
    while (cin >> h >> w, h || w)
    {
        vector<string> v(h + 1);
        for (int i = 1; i <= h; i++)
        {
            cin >> v[i];
            v[i] = '$' + v[i];
        }
        vector<vector<P>> next(h + 2, vector<P>(w + 2));
        for (int i = 0; i <= h + 1; i++)
        {
            for (int j = 0; j <= w + 1; j++)
            {
                P p;
                if (i == 0)
                {
                    if (j == 0)
                        p = P(h, w);
                    else if (j == w + 1)
                        p = P(h, 1);
                    else
                        p = P(h, j);
                }
                else if (i == h + 1)
                {
                    if (j == 0)
                        p = P(1, w);
                    else if (j == w + 1)
                        p = P(1, 1);
                    else
                        p = P(1, j);
                }
                else if (j == 0)
                {
                    p = P(i, w);
                }
                else if (j == w + 1)
                {
                    p = P(i, 1);
                }
                else
                {
                    p = P(i, j);
                }
                next[i][j] = p;
            }
        }
        map<string, int> mp;
        vector<vector<bool>> used(h + 1, vector<bool>(w + 1, false));
        for (int i = 1; i <= h; i++)
        {
            for (int j = 1; j <= w; j++)
            {
                for (int k = 0; k < 8; k++)
                {
                    for (int p = 1; p <= h; p++)
                        for (int q = 1; q <= w; q++)
                            used[p][q] = false;
                    string tmp = "";
                    int x = i, y = j;
                    while (!used[x][y])
                    {
                        used[x][y] = true;
                        tmp += v[x][y];
                        if(tmp.length()>=2) mp[tmp]++;
                        x += dx[k];
                        y += dy[k];
                        P p = next[x][y];
                        x = p.first;
                        y = p.second;
                    }
                }
            }
        }
        string res = "";
        for (auto v : mp)
        {
            if (v.second < 2)
                continue;
            if (v.first.length() < res.length())
                continue;
            if (res.length() == v.first.length())
                res = min(res, v.first);
            else
                res = v.first;
        }
        if (res.length() < 2)
            cout << 0 << endl;
        else
            cout << res << endl;
    }
}



Measured memory_bytes: 37984
//#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
//#include <queue>
//#include <stack>
#include <cstring>
#include <cassert>

#include <cstdlib>

using namespace std;

#ifdef LOCAL_DEBUG
#include <local_debug.h>
#define DEBUG(...) DBG2::print(#__VA_ARGS__, __LINE__, __VA_ARGS__)
#else
#define DEBUG(...)
#endif

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

int N;
int X[15], Y[15], P[15];

const llong INF = 1e18;

inline int nearest_dist(int k, int V[], int pos) {
   int dist = 2000000001;
   /*
   int j = lower_bound(V, V+k, pos) - V;
   if (j < k)
      dist = min(dist, V[j]-pos);
   if (j > 0)
      dist = min(dist, pos-V[j-1]);
   */
   
   for (int i = 0; i < k; ++i) {
      int d = abs(pos - V[i]);
      if (dist > d)
         dist = d;
   }
   
   return dist;
}

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

   cin >> N;
   REP(i, N)
      cin >> X[i] >> Y[i] >> P[i];

   /*
   srand(123);
   for (int i = N-1; i > 0; --i) {
      int j = rand() % (i+1);
      if (i != j) {
         swap(X[i], X[j]);
         swap(Y[i], Y[j]);
         swap(P[i], P[j]);
      }
   }
   */

   int P3 = 1;
   for (int n = 1; n <= N; ++n)
      P3 *= 3;

   llong ans[16];
   FOR(k, 0, N)
      ans[k] = INF;

   int Vx[16], Vy[16];

   REP(mask, P3) {
      int kx = 1, ky = 1;
      Vx[0] = 0, Vy[0] = 0;
      for (int m = mask, i = 0; i < N; ++i) {
         switch (m % 3) {
            case 1:
               Vx[kx++] = X[i];
               break;
            case 2:
               Vy[ky++] = Y[i];
               break;
         }
         m /= 3;
      }

   // sort(Vx, Vx+kx);
   // sort(Vy, Vy+ky);

      int k = (kx-1) + (ky-1);
      llong cost = 0;
      REP(i, N) {
         int distx = nearest_dist(kx, Vx, X[i]);
         int disty = nearest_dist(ky, Vy, Y[i]);
         cost += min(distx, disty) * 1LL * P[i];
         if (ans[k] <= cost)
            break;
      }
      if (ans[k] > cost) {
         ans[k] = cost;
         FOR(kk, k, N) {
            if (ans[kk] <= ans[k])
               break;
            ans[kk] = ans[k];
         }
      }
   }

   FOR(k, 0, N)
      cout << ans[k] << '\n';

   return 0;
}


Measured memory_bytes: 3652
#include<stdio.h>

int main(void)
{
   int t,h,m,s;
   scanf("%d",&t);

   h=t/3600;
   m=(t-h*3600)/60;
   s=t-m*60-h*3600;
   printf("%d:%d:%d\n",h,m,s);


   return 0;
}


Measured memory_bytes: 2100
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>
#include <limits.h>

int main(void){
    int n,i;
    int a,b,c;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d%d%d",&a,&b,&c);
        if(a*a==b*b+c*c || b*b==c*c+a*a || c*c==a*a+b*b) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}



Measured memory_bytes: 1976
n=int(input())
s=str(input())
if n%2==1:
    print('No')
else:
    number=int(n/2)
    sf=[]
    sb=[]
    for i in range(0,number):
        sf.append(s[i])
    for j in range(number,n):
        sb.append(s[j])
    if sf==sb:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 3064
void main()
{
    long[] tmp = readln.split.to!(long[]);
    long h = tmp[0], w = tmp[1];
    long[][] c = new long[][](10);
    foreach (i; 0 .. 10)
    {
        c[i] = readln.split.to!(long[]);
    }

    foreach (i; 0 .. 10)
    {
        foreach (j; 0 .. 10)
        {
            foreach (k; 0 .. 10)
            {
                c[j][k] = min(c[j][k], c[j][i]+c[i][k]);
            }
        }
    }

    long[10] cnts;
    foreach (i; 0 .. h)
    {
        long[] a = readln.split.to!(long[]);
        foreach (x; a)
        {
            if (x == -1) continue;
            ++cnts[x];
        }
    }

    long mp;
    foreach (i; 0 .. 10)
    {
        mp += cnts[i] * c[i][1];
    }

    mp.writeln;
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 3580
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <deque>
#include <assert.h>
#include <random>
#include <bitset>
#include <string>
#include <cstring>
#include <memory.h>

using ll = long long;

//const int inf = 1e9;
const ll infll = 1e18;

using namespace std;

const int maxn = 2e5;
vector<int>g[maxn];
int dist1[maxn];
int dist2[maxn];
int p1[maxn];
int p2[maxn];

struct Solution {
	Solution() {
		int n, tak, aoki;
		cin >> n >> tak >> aoki;

		swap(tak, aoki);
		for (int i = 0; i < n - 1; i++) {
			int a, b;
			cin >> a >> b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		queue <int>q;
		q.push(aoki);
		memset(dist1, 63, sizeof(dist1));
		memset(dist2, 63, sizeof(dist2));
		int inf = dist2[0];
		dist1[aoki] = 0;
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (auto u : g[v]) {
				if (dist1[u] > dist1[v] + 1) {
					dist1[u] = dist1[v] + 1;
					p1[u] = v;
					q.push(u);
				}
			}
		}
		vector<int>path;
		int fin = tak;
		while (fin != aoki) {
			path.push_back(fin);
			fin = p1[fin];
		}
		path.push_back(aoki);
		reverse(path.begin(), path.end());
		int gg = path[(int)path.size() / 2 - 1];
		set<int>forbidden;
		for (int i = (int)path.size() / 2; i < path.size(); i++) {
			forbidden.insert(path[i]);
		}
		q.push(gg);
		dist2[gg] = 0;
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (auto u : g[v]) {
				if (dist2[u] > dist2[v] + 1 && forbidden.find(u)==forbidden.end()) {
					dist2[u] = dist2[v] + 1;
					q.push(u);
				}
			}
		}
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			if (dist2[i] != inf) {
				ans = max(ans, dist2[i]);
			}
		}
		cout << ans + path.size() / 2 - (!(path.size() % 2));
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	for (; t; t--) {
		Solution s;
	}
	return 0;
}

Measured memory_bytes: 11512
#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define ll long long
#define db double
#define vi vector<int>
#define pb push_back
#define mod 998244353
#define fi first
#define pi pair<int, int>
#define se second
#define mp make_pair
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
// head
int cal(int a) {
	if (!a) return 0;
	return cal(a / 10) + a % 10;
}
int main() {
	int n;
	cin >> n;
	int ans = 1e9;
	for (int i = 1; i < n; i++)
		ans = min(ans, cal(i) + cal(n - i));
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <utility>
#include <algorithm>
#include <functional>
#include <vector>
#include <iostream>
typedef long long ll;
typedef int64_t in;
using namespace std;
#define INF 1000000007


int main() {
    while(1){
        int r0, w0, c, r;
        int p,q;
        cin >> r0 >> w0 >> c >> r;
        if(r0 ==0 && w0 == 0 && c == 0 && r == 0) break;
        if(w0*c - r0 < 0){
            cout << "0" << endl;
            continue;
        }
        p = (w0*c - r0) % r;
        if(p==0) q = (w0*c - r0) / r;
        else q = (w0*c - r0) / r + 1;
        cout << q << endl;
    }
}


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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

X = input()
N = len(X)

cnt = 0
s = 0
for i in range(N):
    if X[i] == 'S':
        s += 1
        cnt += 1
    elif X[i] == 'T':
        if s != 0:
            s -= 1
            cnt -= 1
        else:
            cnt += 1
print(cnt)


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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if ((a == 5 && b == 7 && c == 5) || 
        (a == 5 && b == 5 && c == 7) || 
        (a == 7 && b == 5 && c == 5)) {
            cout << "YES\n";
            return 0;
        } else {
            cout << "NO\n";
        }
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1ll<<59


int main(){
  ll i,j;
  ll n,x;
  cin>>n>>x;
  ll ans=0;
  ll po=0;
  for(i=0;i<n;i++){
    if(po<=x) ans++;
    ll l;
    cin>>l;
    po+=l;
  }
  if(po<=x) ans++;
  cout<<ans<<endl;
  return 0;
}

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

int main () {
int A1 , A2 , A3 ; cin >> A1 >> A2 >> A3 ;
int ans = max ({ A1 , A2 , A3 }) - min ({ A1 , A2 , A3 });
cout << ans << endl ;
  
}

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

using namespace std;

int main() {
    int R, D;
    long long int X, pX;
    cin >> R >> D >> X;

    pX = X;
    for (int i = 1; i <= 10; i++)
    {
        X = (R * pX) - D;
        cout << X << "\n";
        pX = X;
    }
}


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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


void solve(long long N, std::vector<long long> a){
    i64 ans = 0;
    rep(i, N) if(a[a[i] - 1] == i + 1) ++ans;
    cout << ans / 2 << endl;
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&a[i]);
    }
    solve(N, std::move(a));
    return 0;
}


Measured memory_bytes: 1024
(defun main ()
  (let* ((n (read))
         (k (read))
         (dp (make-array (list (1+ n) (1+ n)) :element-type 'integer
                                    :initial-element 0
                                    :adjustable t)))
    (dotimes (i (1+ n))
      (setf (aref dp i 0) 1))
    (loop for i from 1 upto n
          do (loop for j from 1 upto i
                   do (setf (aref dp i j) (rem (+ (aref dp (1- i) (1- j)) (aref dp (1- i) j)) 1000000007))))
;;    (format t "~A~%" dp)
    (loop for i from 1 upto k
          do (format t "~A~%" (rem (* (aref dp (1+ (- n k)) i) (aref dp (1- k) (1- i))) 1000000007)))))


(main)


Measured memory_bytes: 39268
#include <bits/stdc++.h>
#define re register
#define SIZE 100005
using namespace std;
template <typename T>
inline void read(T &x)
{
	int f;char c;
	x=0,f=0,c=getchar();
	while(c<'0' && '9'<c)	f|=(c=='-'),c=getchar();
	while('0'<=c && c<='9')	x=(x<<3)+(x<<1)+c-48,c=getchar();
	x=f?-x:x;
}
int n,k;
int h[SIZE];
int dp[SIZE];
int main()
{
	read(n);read(k);
	for(re int i=1;i<=n;++i)
		read(h[i]);
	if(n==1)
	{
		printf("0\n");
		return 0;
	}
	memset(dp,0x3f3f3f,sizeof(dp));
	dp[1]=0;
	for(re int i=1;i<=n;++i)
	{
		for(re int j=1;j<=k;++j)
			if(i-j>=0)
				dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
			else
				break;
	}
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

#define FOR(to) for (int i = 0; i < to; i++)

void quick(long a[], int left, int right)
{
    int i, j;
    long s, t;

    if (left < right) {
        s = a[left];
        i = left; j = right + 1;

        while (1) {
            while (a[++i] < s)
                ;
            while (a[--j] > s)
                ;
            if (i >= j) break;
            t = a[i]; a[i] = a[j]; a[j] = t;
        }
        a[left] = a[j]; a[j] = s;
        quick(a, left, j - 1); quick(a, j + 1, right);
    }
}

int lower_bound(long val, long list[], int N)
{
    int low = 0;
    int upper = N - 1;
    int mid;
    if (list[N - 1] < val) return N;
    while (upper - low > 1) {
        mid = (low + upper) / 2;
        if (list[mid] < val) low = mid;
        else upper = mid;
    }
    if (list[low] < val) return upper;
    else return low;
}

int main(void)
{
    int N;
    scanf("%d", &N);
    long a[N], b[N];
    FOR(N) scanf("%ld", &a[i]);
    FOR(N) scanf("%ld", &b[i]);
    long ans = 0;
    long A[N], B[N];
    

    FOR(29) {
        int count = 0;
        long T = 1 << i;
        FOR(N) A[i] = a[i] % (2 * T);
        FOR(N) B[i] = b[i] % (2 * T);
        quick(B, 0, N - 1);
        // FOR(N) printf("%ld ", A[i]);
        // putchar('\n');
        // FOR(N) printf("%ld ", B[i]);
        // putchar('\n');
        
        FOR(N) {
            int a1 = lower_bound(T - A[i], B, N);
            int a2 = lower_bound(2 * T - A[i], B, N);
            int a3 = lower_bound(3 * T - A[i], B, N);
            int a4 = lower_bound(4 * T - A[i], B, N);
            // printf("a1 %d a2 %d a3 %d a4 %d\n", a1, a2, a3, a4);
            count += a2 - a1 + a4 - a3;
        }
        // printf("%d\n", count);
        if (count % 2) ans += T;
    }
    
    printf("%ld", ans);
}


Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define fi first
#define se second
#define pb push_back
#define forn(i,n) for(int i=0;i<(n);i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forr(i,n) for(int i=n;i>=0;i--)
#define all(x) x.begin(), x.end()
const int MAXN = 1e5 +5;
const LL mm = 1e9 + 7;

void fio(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}

LL po(LL a, LL b){
	if(b==0) return 1;
	LL an =po(a,b/2);
	an = (an*an)%mm;
	if(b&1) an = (an*a)%mm;
	return an;
}

int main(){
  fio();
  int n; cin>>n;
  map <pair<LL,LL>, LL> m;
  map <pair<LL,LL>, LL> vis;
  LL cnt = 0;
  LL cnta = 0; 
  LL cntb = 0;
  forn(i,n){
  	LL a, b; cin>>a>>b;
  	if(a==0 || b==0){
  		if(a==0 && b==0) {
  			cnt++;
  			continue;
  		}
  		if(a==0 && b!=0) cnta++;
  		if(b==0 && a!=0) cntb++;
  		continue;
  	}
    LL x = gcd(abs(a), abs(b));
  	a/=x, b/=x;
  	if(b<0){
  		b*=-1;
  		a*=-1;
  	}
  	m[{a,b}]++;
  } 
  LL an = 1;
  for(auto i:m){
  	 if(vis[i.fi]) continue;
     pair<LL,LL> zx = {-1*i.fi.se,i.fi.fi};
     if(zx.se<0){
       zx.fi*=-1;
       zx.se*=-1;
     }
     LL pp = 0;
     if(m.find(zx)==m.end()){
     	pp = 0;
     }
     else pp = m[zx];
 	 LL z = ((po(2,i.se)-1) + (po(2,pp) - 1) + 1 + mm)%mm; 
 	// cout<<z<<"--"<<endl;
     z = (z+mm)%mm;
 	 an = (an*z)%mm;
 	 vis[zx] = 1;
 	 vis[i.fi] = 1;
  }
  LL z = ((po(2,cnta)-1) + (po(2,cntb) - 1) + 1 + mm)%mm; 
  z = (z+mm)%mm;
  an = (an*z)%mm;
  an = (an + cnt - 1 + mm)%mm;
  cout<<an<<endl;
  return 0;
}



Measured memory_bytes: 41124
#include <iostream>
#include <string>

int main()
{
	int sx; std::cin >> sx;
	int sy; std::cin >> sy;
	int tx; std::cin >> tx;
	int ty; std::cin >> ty;

	std::string path1;
	for(int j=0; j<ty-sy; j++)
	{
		path1 += "U";
	}
	for(int i=0; i<tx-sx; i++)
	{
		path1 += "R";
	}
	
	std::string path2;
	for(int j=0; j<ty-sy; j++)
	{
		path2 += "D";
	}
	for(int i=0; i<tx-sx; i++)
	{
		path2 += "L";
	}

	std::string path3;
	path3 += "L";
	for(int j=0; j<ty-sy+1; j++)
	{
		path3 += "U";
	}
	for(int i=0; i<tx-sx+1; i++)
	{
		path3 += "R";
	}
	path3 += "D";

	std::string path4;
	path4 += "R";
	for(int j=0; j<ty-sy+1; j++)
	{
		path4 += "D";
	}
	for(int i=0; i<tx-sx+1; i++)
	{
		path4 += "L";
	}
	path4 += "U";


	std::cout << path1+path2+path3+path4 << std::endl;
	return 0;
}

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

#define dig(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;

const int mod = 1e9+7;
const int maxn = 105;
const int N = 85;

int T;
LL f[maxn];
vector<pair<LL, LL> > excel[maxn];

void Init()
{
	scanf("%d", &T);
	f[0] = 1;
	f[1] = 1;
	for (int i = 2; i <= N + 2; ++i) {
		f[i] = f[i - 1] + f[i - 2];
	}
}

int gcd_count(LL x, LL y)
{
	int cnt = 0;
	if (x > y) swap(x, y);
	while (x) {
		x ^= y ^= x ^= y %= x;
		++cnt;
	}
	return cnt;
}

void Prepare()
{
	vector<pair<LL, LL> >::iterator it, p;
	LL x, y;
	excel[1].push_back(make_pair(1, 2));
	excel[1].push_back(make_pair(1, 3));
	for (int i = 1; i < N; ++i) {
		for (p = excel[i].begin(); p != excel[i].end(); ++p) {
			x = (*p).first;
			y = (*p).second;
			for (int j = 1; j <= 2; ++j) {
				if (y * j + x > f[i + 3]) break;
				if (gcd_count(y, y * j + x) == i + 1) {
					excel[i + 1].push_back(make_pair(y, y * j + x));
				}
			}
		}
		sort(excel[i + 1].begin(), excel[i + 1].end());
		it = unique(excel[i + 1].begin(), excel[i + 1].end());
		excel[i + 1].resize(distance(excel[i + 1].begin(), it));
	}
	/*for (int i = 1; i <= N; ++i) {
		dig("%d\n", (int)excel[i].size());
		}*/
}

void Solve()
{
	LL X, Y, x, y;
	int ans;
	LL sum = 0;
	vector<pair<LL, LL> >::iterator it;
	while (T--) {
		cin >> X >> Y;
		if (X > Y) swap(X, Y);
		ans = 1;
		for (int i = 2; i <= N; ++i) {
			if (X >= f[i] && Y >= f[i + 1]) {
				ans = i;
			}
			else {
				break;
			}
		}
		sum = 0;
		if (ans == 1) {
			sum = (X % mod * Y % mod) % mod;
		}
		else {
			for (it = excel[ans - 1].begin(); it != excel[ans - 1].end(); ++it) {
				x = (*it).first;
				y = (*it).second;
				if (X >= y) {
					(sum += (Y - x) / y) %= mod;
				}
				if (Y >= y) {
					(sum += (X - x) / y) %= mod;
				}
			}
		}
		cout << ans << ' ' << sum << endl;
	}
}

int main()
{
	Init();
	Prepare();
	Solve();
	return 0;
}


Measured memory_bytes: 4096
// C.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
	while (true) {
		int n = -1, a;
		cin >> n;
		if (n <= 0) break;
		vector<int> order(n);
		for (int i = 0; i < n; ++i) {
			cin >> a;
			order[a - 1] = i;
		}
		for (int i = 0; i < n; ++i) {
			if (i) cout << " ";
			cout << (order[i] + 1);
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 1152
#include<cstdio>
#include<set>

using namespace std;

int main(){
	int n, t; scanf("%d %d", &n, &t);
	int a[100000];
	set<int> s;
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		if(i > 0) s.insert(a[i]);
	}
	int res = 1, max = 0;
	for(int i = 0; i < n - 1; i++){
		int r = *s.rbegin() - a[i];
		if(r == max) res++;
		if(r > max){ res = 1; max = r; }
		s.erase(a[i + 1]);
	}
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 5376
import java.util.*;


 
public class Main {

    public static void main(String args[])  {
    	Scanner sc = new Scanner(System.in);
    	String c =sc.nextLine();
      String b =c.substring(c.length() - 1);
    	if(b.equals("3")){
          System.out.println("bon");
        }else if(
        		b.equals("0")||
        		b.equals("1")||
        		b.equals("6")||
        		b.equals("8")){
        	System.out.println("pon");
        }else {
        	System.out.println("hon");
        }
    }
}

Measured memory_bytes: 35576
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
  for(int n;cin>>n,n;){
    vector<string> v;
    for(int i=0;i<n;i++){
      string s;
      cin>>s;
      v.push_back(s);
    }
    for(int i=v.size()-1;i>=0;i--){
      for(int j=0;j<v.size();j++){
	if(i!=j&&v[j].find(v[i])!=string::npos){
	  v.erase(begin(v)+i);
	  break;
	}
      }
    }
    int b[14][14];
    int d[14][14];
    for(int i=0;i<v.size();i++){
      for(int j=0;j<v.size();j++){
	for(int k=0;k<v[i].size()&&k<v[j].size();k++){
	  if(v[i].compare(v[i].size()-k,k,v[j],0,k)==0){
	    d[i][j]=v[j].size()-k;
	  }
	}
	b[i][j]=1<<j;
	string ns=v[i]+v[j].substr(d[i][j]);
	for(int k=0;k<v.size();k++){
	  b[i][j]|=(ns.find(v[k])!=string::npos)<<k;
	}
      }
    }
    static int dp[1<<14][14];
    fill(dp[0],dp[1<<14],1<<29);
    for(int i=0;i<v.size();i++){
      dp[1<<i][i]=v[i].size();
    }
    for(int i=1;i<1<<v.size();i++){
      for(int j=0;j<v.size();j++){
	for(int k=0;k<v.size();k++){
	  if(!(i>>k&1)){
	    int nb=i|b[j][k];
	    dp[nb][k]=min(dp[nb][k],dp[i][j]+d[j][k]);
	  }
	}
      }
    }
    cout<<*min_element(dp[(1<<v.size())-1],dp[1<<v.size()])<<endl;
  }
}


      

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

int N;

int main() {
    cin >> N;
    int p;
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        cin >> p;
        cnt += !(p == i + 1);
    }
    cout << (cnt == 0 || cnt == 2? "YES": "NO") << endl;
}


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

long long n, m, start, ans=0;
string grid[21];

long long coba(long long x1, long long y1, long long x2, long long y2){
	long long ret=-1;
	bool visit[21][21];
	memset(visit,0,sizeof visit);
	queue<pair<pair<long long, long long>,long long> >bfs;
	bfs.push({{x1,y1},0});
	while(!bfs.empty()){
		long long xnow=bfs.front().first.first;
		long long ynow=bfs.front().first.second;
		long long distnow=bfs.front().second;
		bfs.pop();
		if (xnow==x2 && ynow==y2){
			ret=distnow;
			break;
		}
		if (xnow<0 || xnow>=n || ynow<0 || ynow>=m || visit[xnow][ynow] || grid[xnow][ynow]=='#') continue;
		visit[xnow][ynow]=1;
		bfs.push({{xnow+1,ynow},distnow+1});
		bfs.push({{xnow-1,ynow},distnow+1});
		bfs.push({{xnow,ynow+1},distnow+1});
		bfs.push({{xnow,ynow-1},distnow+1});
	}
	return ret;
}

int main(){
	cin >> n >> m;
	for (int i=0;i<n;i++) cin >> grid[i];
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++){
			for (int k=0;k<n;k++){
				for (int l=0;l<m;l++){
					if (grid[i][j]=='.' && grid[k][l]=='.'){
						ans=max(ans,coba(i,j,k,l));
					}
				}
			}
		}
	}
	cout << ans << "\n";
}

Measured memory_bytes: 256
A,B,C,X,Y=map(int,input().split())
cost=0
pizza_rem=0

#C買いまくってAを満たす場合(2C<A)
if 2*C<=A:
    cost+=2*C*X
    pizza_rem=Y-X
    if pizza_rem<=0:
        print(cost)
    else:
        cost+=min(2*C,B)*pizza_rem
        print(cost)

#C買いまくってBを満たす場合(2C<B)
elif 2*C<=B:
    cost+=2*C*Y
    pizza_rem=X-Y
    if pizza_rem<=0:
        print(cost)
    else:
        cost+=min(2*C,A)*pizza_rem
        print(cost)

#min(X,Y)枚Cを買う場合(A,B<2C<A+B)
elif 2*C<A+B:
    cost+=2*C*min(X,Y)
    pizza_rem=abs(X-Y)
    if X<Y:
        cost+=B*pizza_rem
        print(cost)
    else:
        cost+=A*pizza_rem
        print(cost)
        
#AとBをバラバラで買ったほうが安い場合
else:
    cost+=A*X+B*Y
    print(cost)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
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>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
int main() {
    int x;
    cin >> x;
    cout << (x >= 30 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3644
import java.util.*;
import static java.lang.System.out;

public class Main {
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		new Main().AOJ0008();
	}
	
	void AOJ0008(){	//Sum of 4 Integers
		while(sc.hasNext()){
			int ans=0, n=sc.nextInt();
			for(int a=0; a<10; a++){
				for(int b=0; b<10; b++){
					for(int c=0; c<10; c++){
						for(int d=0; d<10; d++){
							if((a+b+c+d)==n)	ans++;
						}
					}
				}
			}
			out.println(ans);
		}
	}
	
	void AOJ0055(){	// Sequence
		while(sc.hasNext()){
			double last=sc.nextDouble(), ans=last;
			for(int i=2; i<=10; i++){
				ans+= i%2==0? last*2: last/3;
				last = i%2==0? last*2: last/3;
				// out.println(last);
			}
			out.println(ans);
		}
	}
}

Measured memory_bytes: 12000
#include<stdio.h>
int main()
{
char s[12];
char t[12];
int i;
int flagone=1;
int flagtwo=0;


scanf("%s",s);
scanf("%s",t);

for(i=0;s[i]!='\0';i++){
if(s[i]!=t[i]){flagone=0;break;}
}

if(flagone==1){
if(t[i]!='\0'){flagtwo=1;}
}

if(flagtwo==1){
printf("Yes");
}else{
printf("No");
}

return 0;
}

Measured memory_bytes: 2112
N, a, b = map(int,input().split())

if (b-a) % 2 == 0:
    print((b-a) // 2)
else:
    c = (N-b+1 + ((N - (a + (N-b+1))) // 2)) 
    d = (a + ((b - a - 1) // 2))
    print(min(c,d))

Measured memory_bytes: 3060
object Main {
  def main(args: Array[String]): Unit = {
    solve
  }

  def solve(): Unit = {
    val sc = new java.util.Scanner(System.in)
    val h, w, n = sc.nextInt

    val num = math.max(h, w)
    println(if(n % num == 0) n / num else n / num +1)
  }

}


Measured memory_bytes: 27336
#include<bits/stdc++.h>
#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 fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int A[3][3], N;
bool punched[3][3];
//---------------------------------------------------------------------------------------------------
void _main() {
	rep(y, 0, 3) rep(x, 0, 3) cin >> A[y][x];
	cin >> N;
	rep(i, 0, N) {
		int b; cin >> b;
		rep(y, 0, 3) rep(x, 0, 3) if (A[y][x] == b) punched[y][x] = true;
	}

	bool ans = false;

	// 横
	rep(y, 0, 3) {
		int cnt = 0;
		rep(x, 0, 3) if (punched[y][x]) cnt++;
		if (cnt == 3) ans = true;
	}

	// 縦
	rep(x, 0, 3) {
		int cnt = 0;
		rep(y, 0, 3) if (punched[y][x]) cnt++;
		if (cnt == 3) ans = true;
	}

	// ななめ
	if (punched[0][0] && punched[1][1] && punched[2][2]) ans = true;
	if (punched[2][0] && punched[1][1] && punched[0][2]) ans = true;

	if (ans) cout << "Yes" << endl;
	else cout << "No" << endl;
}







Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)
//#define INF (1LL<<59)

int main(){
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            cout<<i<<"x"<<j<<"="<<i*j<<endl;
        }
    }
}

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

#define int long long
using ll = long long;
using ld = long double;
using intpair = pair<int, int>;
const int MOD = 1e9 + 7;
inline int mod (ll a, int m = MOD) { return (a % m + m) % m; }
//struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) ((ll)((a) + (b) - 1)/(ll)(b))

int pow2[13];

signed main() {
    pow2[0] = 1;
    rep(i, 12) pow2[i+1] = pow2[i] * 2;
    
    int n, m;
    cin >> n >> m;
    
    vector<int> keys(pow2[n], INT_MAX);
    rep(i,m){
        int a, b;
        cin >> a >> b;
        int k = 0;
        rep(j,b){
            int c; cin >> c;
            k += pow2[c-1];
        }
        keys[k] = min(keys[k], a);
    }
    
    rep(_,n){
        rep(i,pow2[n])reps(j,i+1,pow2[n]-1){
            int merged = i | j;
            keys[merged] = min(keys[merged], keys[i] + keys[j]);
        }
    }
    
    if(keys[pow2[n]-1] == INT_MAX){
        cout << -1 << endl;
    }else{
        cout << keys[pow2[n]-1] << endl;
    }
}

Measured memory_bytes: 3628
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define Pint pair<int, int>
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
/* -- template -- */

int main() {
    int N, M; cin >> N >> M;
    vector<vector<int>>G(N);
    deque<int> Q;
    vector<bool>visited(N, false);
    rep(i, M) {
        int a, b; cin >> a >> b;
        G[--a].pb(--b);
        G[b].pb(a);
        if(i == 0) {
            Q.push_back(a);
            Q.push_back(b);
            visited[a] = visited[b] = true;
        }
    }
    bool checkflg = true;
    while(checkflg) {
        checkflg = false;
        bool flg = true;
        int i = Q.front();
        for(int v : G[i]) {
            if(visited[v] == false) {
                checkflg = true;
                if(flg) {
                    Q.push_front(v);
                    flg = false;
                    visited[v] = true;
                    break;
                }
            }
        }
        flg = true;
        int j = Q.back();
        for(int v : G[j]) {
            if(visited[v] == false) {
                checkflg = true;
                if(flg) {
                    Q.push_back(v);
                    flg = false;
                    visited[v] = true;
                    break;
                }
            }
        }
    }
    cout << Q.size() << endl;
    rep(i, Q.size()) {
        cout << Q[i] + 1 << ' ';
    }
}


Measured memory_bytes: 6656
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
 
const int maxn=2e5+5,pps=1e9+7;
 
bool vis[maxn];
int n,x,y,tot,ans=1,top;
int fac[maxn],inv[maxn],sta[maxn],insta[maxn];
int sum[maxn],now[maxn],pre[maxn<<2],son[maxn<<2],color[maxn];
 
int read() {
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return x*f;
}
 
struct Ball {
	int c,w,id;
}b[maxn];
 
int quick(int a,int b) {
	int sum=1;
	while(b) {
		if(b&1)sum=1ll*sum*a%pps;
		a=1ll*a*a%pps,b>>=1;
	}
	return sum;
}
 
bool cmp1(Ball a,Ball b) {
	if(a.c==b.c)return a.w<b.w;
	return a.c<b.c;
}
 
bool cmp2(Ball a,Ball b) {
	if(a.w==b.w)return a.c<b.c;
	return a.w<b.w;
}
 
void add(int a,int b) {
	pre[++tot]=now[a];
	now[a]=tot,son[tot]=b;
}
 
void work1() {
	int lst=0;
	for(int i=1;i<=n;i++) {
		if(b[i].c!=b[lst].c) {
			lst=i;continue;
		}
		if(b[i].w+b[lst].w<=x) {
			add(b[i].id,b[lst].id);
			add(b[lst].id,b[i].id);
		}
	}
}
 
void work2() {
	int fake;b[n+1].w=1e9;
	for(fake=2;fake<=n;fake++)
		if(b[fake].c!=b[1].c)break;
	for(int i=2;i<=n;i++)
		if(b[i].c!=b[1].c) {
			if(b[i].w+b[1].w>y)break;
			add(b[i].id,b[1].id);
			add(b[1].id,b[i].id);
		}
		else if(b[i].w+b[fake].w<=y) {
			add(b[i].id,b[fake].id);
			add(b[fake].id,b[i].id);
		}
}
 
void prepare() {
	fac[0]=inv[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=1ll*fac[i-1]*i%pps;
	inv[n]=quick(fac[n],pps-2);
	for(int i=n-1;i;i--)
		inv[i]=1ll*inv[i+1]*(i+1)%pps;
}
 
void dfs(int u) {
	vis[u]=1;
	int c=color[u];
	if(!insta[c]) {
		sta[++top]=c;
		insta[c]=top;
		sum[top]=1;
	}
	else sum[insta[c]]++;
	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
		if(!vis[v])dfs(v);
}
 
void calc() {
	int cnt=0;
	while(top) {
		ans=1ll*ans*inv[sum[top]]%pps;
		cnt+=sum[top],insta[sta[top]]=0,sta[top]=0,sum[top]=0,top--;
	}
	ans=1ll*ans*fac[cnt]%pps;
}
 
signed main() {
	n=read(),x=read(),y=read(),prepare();
	for(int i=1;i<=n;i++)
		color[i]=b[i].c=read(),b[i].w=read(),b[i].id=i;
	sort(b+1,b+n+1,cmp1);work1();
	sort(b+1,b+n+1,cmp2);work2();
	for(int i=1;i<=n;i++)
		if(!vis[i])dfs(i),calc();
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 24448
import java.util.Arrays;
import java.util.Scanner;
 
public class Main{
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
        	int n = Integer.parseInt(sc.nextLine());
        	if(n == 0) break;
        	String vote = sc.nextLine();
        	int[] kouho = new int[26];
        	int[] sokuhou = new int[26];
        	boolean flag = true;
        	for(int i = 0; i < n; i++) {
        		char c = vote.charAt(2 * i);
        		kouho[c - 'A'] += 1;
        		for(int j = 0; j < 26; j++) {
        			sokuhou[j] = kouho[j];
        		}
        		Arrays.sort(sokuhou);
        		if(sokuhou[25] > sokuhou[24] + (n - i - 1)) {
        			int k = 0;
        			while(kouho[k] != sokuhou[25]) {
        				k++;
        			}
        			System.out.printf("%c %d\n", 'A' + k, i + 1);
        			flag = false;
        			break;
        		}
        		
        	}
        	if(flag) {
        		System.out.println("TIE");
        	}
        }
    }
}



Measured memory_bytes: 45528
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
D = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
T = list(map(int, sys.stdin.readline().split()))

counts = defaultdict(int)
for d in D:
    counts[d] += 1
for t in T:
    counts[t] -= 1

ok = True
for c in counts.values():
    ok &= c >= 0
if ok:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 51464
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
import           Data.List  (find)
import           Data.Maybe (fromMaybe)

main :: IO ()
main = do
  s' <- getLine
  t <- getLine
  putStrLn . fromMaybe "UNRESTORABLE" $ solve s' t

solve :: String -> String -> Maybe String
solve s' t = fillWithA <$> matchRight s' t

fillWithA :: String -> String
fillWithA = map (\c -> if c == '?' then 'a' else c)

matchRight :: String -> String -> Maybe String
matchRight s' t = concat3 <$> find match (reverse $ substrs s' (length t)) where
  match (x, y, z) = and $ zipWith (\c d -> c == d || c == '?') y t
  concat3 (x, _, z) = x ++ t ++ z

substrs :: String -> Int -> [(String, String, String)]
substrs s n = go [] s where
  go p s
    | length xs < n = []
    | otherwise     = (p, xs, ys) : go (p ++ [head s]) (tail s)
    where (xs, ys) = splitAt n s


Measured memory_bytes: 508
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <iomanip>
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;

using namespace std;

int main()
{
	int n, a, b;
	cin >> n >> a >> b;
	

	
  cout << min(n * a, b);
	return 0;
}


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

using namespace std;

int sum = 0;

void vanish(int h,int stone[10][6]) {
	for (int i = 1; i < h; ++i) {
		for (int j = 0; j < 5; ++j) {
			if (stone[i][j] == 0) {
				for (int k = 0; k < i; ++k) stone[i - k][j] = stone[i - (k + 1)][j];
				stone[0][j] = 0;
			}
		}
	}
}

void puzzle(int h,int stone[10][6]) {
	int num = 1, flag = 0;
	int w;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < 5; ++j) {
			if (stone[i][j] == stone[i][j + 1] && stone[i][j] != 0) {
				if (num == 1) w = j;
				num++;
			} else if (num >= 3) {
				sum += num * (stone[i][w]);
				for (int k = 0; k < num; ++k) stone[i][w + k] = 0;
				num = 1;
				flag++;
			} else num = 1;
		}
	}
	if (flag != 0) {
		vanish(h, stone);
		puzzle(h, stone);
	}
}

int main() {
	int h;
	while (cin >> h && h != 0) {
		int stone[10][6] = {};
		for (int i = 0; i < h; ++i)
			for (int j = 0; j < 5; ++j)
				cin >> stone[i][j];
		puzzle(h, stone);

		cout << sum << endl;
		sum = 0;
	}

	return 0;
}


Measured memory_bytes: 3008
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 標準入力からデータを読み込む準備
try (Scanner sc = new Scanner(System.in)) {
String line = sc.nextLine();
String answer = "";
int length = line.length();
for (int i = 0; i < length; i++) {
char ch = line.charAt(i); // 文字列(line)からi番目の文字を取り出す
// Character.isLowerCase で小文字かどうか判断可能
// Character.toUpperCase, Character.toLowerCase で変換
// 記号は上記メソッドで変換にかけても変化しない
if(Character.isLowerCase(line.charAt(i))){
     answer += Character.toUpperCase(line.charAt(i));
} else {
     answer += Character.toLowerCase(line.charAt(i));
}
}
System.out.println(answer);
}
}
}


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

using namespace std;

int main(){
  int n,k = -1,origin;
  cin >> n;
  map<pair<int,int>,int> edge;
  vector<vector<int>> v(n);
  vector<vector<int>> cc(n);
  pair<int,int> c[n-1];
  for(int i = 0;i < n-1;i++){
    int a,b;cin >> a >> b;
    a--,b--;
    c[i] = {a,b};
    edge[{a,b}] = -1;edge[{b,a}] = -1;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for(int i = 0;i < n;i++){
    k = max(k,(int)v[i].size());
    if(k == v[i].size())origin = i;
  }
  queue<int> que;
  que.push(origin);
  while(!que.empty()){
    int ov = que.front();que.pop();
    int color = 1;
    for(auto nv : v[ov]){
      if(edge[{ov,nv}] != -1 || edge[{nv,ov}] != -1)continue;
      for(auto ocolor : cc[ov]){
        if(color == ocolor)color++;
        if(color > k)color = 1;
      }
      cc[nv].push_back(color);
      edge[{nv,ov}] = color;edge[{ov,nv}] = color++;
      que.push(nv);
    }
  }
  cout << k << endl;
  for(int i = 0;i < n-1;i++){
    cout << edge[{c[i].first,c[i].second}] << endl;
  }
  return 0;
}

Measured memory_bytes: 24832
n, x = map(int, input().split())
l = list(map(int, input().split()))

count = 1
dis = 0

for i in range(n):
  dis += l[i]
  count += 1
  if dis == x:
    print(count)
    break
  elif dis > x:
    print(count-1)
  elif count == (n+1):
    print(count)
  else:
    continue
  break


Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
using namespace std;
long long s,n;
string st;
int main()
{
	cin>>st;n=st.size();
	for(int i=0;i<n-1;i++)
	{
		if(st[i]!=st[i+1])s++;
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 512
def main():
    N = int(input())
    S = input()
    left = 0
    right = S[1:].count('E')
    ans = right
    for n in range(1, N):
        if S[n - 1] == 'W':
            left += 1
        if S[n] == 'E':
            right -= 1
        ans = min(ans, left + right)
    print(ans)


main()


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

int main(void){
	int32 N;
	cin >> N;
	REP(i, N){
		string s;
		set<string> st;
		cin >> s;
		REP(i, s.size()-1){
			string u = s.substr(0, i+1), v = s.substr(i+1, s.size()-i-1);
			st.insert(u+v);
			st.insert(v+u);
			reverse(all(u));
			st.insert(v+u);
			st.insert(u+v);
			reverse(all(v));
			st.insert(u+v);
			st.insert(v+u);
			reverse(all(u));
			st.insert(u+v);
			st.insert(v+u);
		}
		cout << st.size() << endl;
	}
	
}



Measured memory_bytes: 3192