akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

class MainClass
{
    static int[] dy = new int[2] {1,-1};
    static int[] dx = new int[2] {1,-1};
    static void Main()
    {
        string s = Console.ReadLine();
        var xy = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var ep = (8000 + xy[0], 8000 + xy[1]);
        int t = s.Count(_ => _ == 'T');
        var x = new bool[16001];
        var y = new bool[16001];

        y[8000] = true;
        
        int index = 0;
        int firstx = 8000;
        while(index<s.Length&&s[index] == 'F')
        {
            firstx++;
            index++;
        }
        x[firstx] = true;

        bool dir = false;
        while (index < s.Length)
        {
            while (index < s.Length && s[index] == 'T')
            {
                dir = !dir;
                index++;
            }

            int distance = 0;
            while (index < s.Length && s[index] == 'F')
            {
                distance++;
                index++;
            }
            if (dir)
            {
                var ny = new bool[16001];
                for(int i = 1; i < 16000; i++)
                {
                    if (y[i])
                    {
                        ny[i - distance] = true;
                        ny[i + distance] = true;
                    }
                }
                y = ny;
            }
            else
            {
                var nx = new bool[16001];
                for (int i = 0; i < 16000; i++)
                {
                    if (x[i])
                    {
                        nx[i + distance] = true;
                        nx[i - distance] = true;
                    }
                }
                x = nx;
            }
        }
        if (x[ep.Item1] && y[ep.Item2]) Console.WriteLine("Yes");
        else Console.WriteLine("No");
        /*
        for (int i = -2; i < 3; i++)
        {
            Console.WriteLine(x[ep.Item1 + i]);
            Console.WriteLine(y[ep.Item2 + i]);
        }
        //Console.WriteLine(x[ep.Item1-1]);
        //Console.WriteLine(y[ep.Item2+1]);
        */
    }
}

Measured memory_bytes: 46864
#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
  int K, A, B;
  cin >> K >> A >> B;

  for (int i = A; i <= B; ++i) {
    if (i % K == 0) {
      cout << "OK" << endl;
      return 0;
    }
  }

  cout << "NG" << endl;

  return 0;
}

Measured memory_bytes: 3596
// https://ynucpc.github.io/blog/2018/04/15/cp_vscode/
// http://www.atmarkit.co.jp/ait/articles/1509/08/news019.html

#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rep3(i,n,m) for(ll i=(n);i<(ll)(m);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b)) 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
int stoi (string s, int tmp=10){
	istringstream stm(s);
	int res;
	stm >> res;
	return res;
}
double stod(string s, int tmp=10){
	istringstream stm(s);
	double res;
	stm >> res;
	return res;
}


// 配列の総和
// greater


ll X[100000];
ll dX[100000];

int main(){	
	// ll A;
    // cin >> A;
	// cout << "hello" << endl;
	// cout << stoi("14") << endl;
	// cout << max({1,3}) << endl;
	ll N, M;
	cin >> N >> M;
	rep(i, M)cin>>X[i];
	sort(X, X+M);
	rep(i, M-1)dX[i] = X[i+1]-X[i];
	sort(dX, dX+M-1);
	ll ans=0;
	rep(i, M-N)ans += dX[i];
	cout << ans << endl;

}








Measured memory_bytes: 1792
import numpy as np

N = int(input())
for h in range(1, 3501):
  n = np.arange(1, 3501, dtype=np.int64)
  num = N*h*n
  den = 4*h*n - N*n - N*h
  n = n[(den>0) & (num%den == 0)]
  if len(n) > 0:
    n = n[0]
    w = N*h*n // (4*h*n - N*n - N*h)
    break
print(n, h, w)

Measured memory_bytes: 12512
using System;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            var NM = Console.ReadLine().Split(' ');
            int N = int.Parse(NM[0]);
            int M = int.Parse(NM[1]);

            int[] a = new int[N];

            for(var i = 0; i< M;i++)
            {
                var ab = Console.ReadLine().Split(' ');
                a[int.Parse(ab[0])-1]++;
                a[int.Parse(ab[1])-1]++;
            }

            for(var i = 0; i< N; i++)
            {
                Console.WriteLine(a[i]);
            }

            //Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
#include <math.h>
#include <cmath>
#include <limits>
#include <iostream>
#include <assert.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=10000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	int x,y,cost;
};
int d[10]={};
int total=100000;
int main(){

	int n,k;
	cin>>n>>k;
	rep(i,k){
		int c;
		cin>>c;
		d[c]=1;
	}
	for(int i=n; i<100000; i++){
		int j=10000,f=0;
		int i2=i,i3=0;
		for(int l=1; l<6; l++){
			if(i>=j&&d[i2/j]==1)f=1;
			i3=i2%j;
			j/=10;
			i2=i3;
		}
		if(f==0)total=min(total,i);
	}
	cout<<total<<endl;
	return 0;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
int mae[33000][11],ushiro[33000][11];
signed main(){
    int n;cin >> n;
    string s;cin >> s;
    
    rep(i,n){
        if(!i)continue;
        mae[i][s[i-1] - '0']++;
        rep(j,10)mae[i][j]+= mae[i-1][j];
    }
    for(int i = n-2;i >= 0;i--){
        ushiro[i][s[i+1] - '0']++;
        rep(j,10)ushiro[i][j] += ushiro[i+1][j];
    }

    int ans = 0;
    rep(a,10)rep(b,10)rep(c,10){
        bool ok = false;
        rep(i,n){
            if(s[i] - '0' == b && mae[i][a] && ushiro[i][c])ok = true;

        }
        //if(ok)trace(a,b,c);
        ans += ok;

    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a=0, b=0, c=0,m=0;
	cin>>a;
	for(int i=1;i<n;i++) {
		cin>>b;
		if(b<=a) {
			c++;
		} 
		else{
			m=max(m,c);
			c= 0;
		}
		a=b;
	}
	m=max(m,c);
	cout <<m<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int a;
  char s[10];
  2800<=a,a<5000;
  scanf("%d",&a);
  scanf("%s",s);
  if(a>=3200)
    printf("%s",s);
  if(a<3200)
    printf("red");
  
  return 0;
}

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

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif




signed main() {
    char c;
    cin >> c;
    char ans = c+1;
    cout << ans << endl;
    
}


Measured memory_bytes: 256
#include <stdio.h>

#define N 15

int d[ N ] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2, 1 };

/** Application main entry point. */
int main (
  int     argc,
  char  * argv[ ]
  )
{
  int n;

  scanf ( "%d", &n );

  while ( n-- )
  {
    int a, b;

    scanf ( "%d%d", &a, &b );
    if ( a <= 5 && b < a )
    {
      a = 15 - a;
    }

    while ( d[ a ] != b )
    {
      printf ( "%d ", d[ a ] );
      a = ( a + 1 ) % N;
    }

    printf ( "%d\n", d[ a ] );
  }

  return ( 0 );
}

Measured memory_bytes: 0
//
// Created by satcl on 2020-05-04.
//

#include <bits/stdc++.h>
#include <unordered_set>
#include <stdio.h>

using namespace std;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define endl "\n"
#define PI 3.141592653589793
#define vi vector<int>
#define vll vector<long long>
#define p pair<int,int>
const int MOD = 1000000007;
inline double degcos(double ang) {return cos(ang*PI/180);}
inline double degsin(double ang) {return sin(ang*PI/180);}
#define rep(i,j,k,in) for (int i = j; i < k; i += in)


/*---END OF TEMPLATE---*/




int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    //ifstream fin("data.in");
    //ofstream fout("data.out");
    int h,w;
    cin >> h >> w;
    string arr[h];
    rep(i,0,h,1) cin >> arr[i];
    int dp[h][w];
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    rep(i,1,h,1) {
        if (arr[i][0] == '#') break;
        dp[i][0] = 1;
    }
    rep(i,1,w,1) {
        if (arr[0][i] == '#') break;
        dp[0][i] = 1;
    }
    rep(i,1,h,1) {
        rep(j,1,w,1) {
            if (arr[i][j] == '#') continue;
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
            dp[i][j] = dp[i][j] % MOD;
        }
    }
    cout << dp[h-1][w-1] << endl;

}

Measured memory_bytes: 5248
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, k**2):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if b%p == 0:
        if count[p] == 0:
          baisu.append(p)
        c = 0
        while b % p == 0:
          b //= p 
          c += 1 
        if c > count[p]:
          count[p] = c
    else:
      break
  if b != 1:
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)

product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod

print(ans)


Measured memory_bytes: 17968
a,b,c,d,n,*A=`dd`.split.map &:to_i;e=f=1;a>c&&(a,c,e=c,a,-1);b>d&&(b,d,f=d,b,-1);V=A.each_slice(2).select{|x,y|a<=x&&x<=c&&b<=y&&y<=d}.map{|x,y|[x*e,y*f]}.sort;D=[F=1e9]*s=V.size;V.map{|x,y|D[D.bsearch_index{|e|e>y}]=y};N=D.bsearch_index{|e|e>=F}||s;p 1e2*(c-a+d-b)-20*N+5*(N+(N>[c-a,d-b].min ? 1:0))*Math::PI

Measured memory_bytes: 40980
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<cassert>

using namespace std;

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

const int N = 20, T = (1<<N), H = 19, W = 15;

set<int> memo[T];
int board[H][W];
int stx,sty;

class Q{
public:
	int x,y,cnt,state;
	Q(int x,int y,int cnt, int state):x(x),y(y),cnt(cnt),state(state){}
};

void input(){
	string a[H];

	rep(i,H)cin>>a[i];
	int cnt = 0;
	rep(i,H){
		rep(j,W){
			board[i][j] = -1;
			if(a[i][j] == 'X'){
				board[i][j] = cnt;
				cnt++;
			}
			if(a[i][j] == 'O'){
				stx = j; sty = i;
			}
		}
	}
}


int zahyo(int x,int y){
	return x + y * W;
}

bool hasmemo(Q u){
	return memo[u.state].find(zahyo(u.x,u.y)) != memo[u.state].end();
}

void setmemo(Q u){
	memo[u.state].insert(zahyo(u.x,u.y));
}

bool hasbit(int state, int i){
	return (state&(1<<i))>0;
}

bool isblack(int x,int y,int state){
	int n = board[y][x];
	if(n<0)return false;
	return !hasbit(state,n);
}

bool isout(int x,int y){
	if(y<0)return true;
	if(y<H){
		if(x<0 || x>=W)return true;
	}
	return false;
}


bool isgoal1(int x,int y){
	if(y>=H) return true;
	return false;
}

bool isgoal2(int x,int y){
	if(y==H-1 && (x>=0 && x<=W-1))return true;
	return false;
}


int minblack(int x,int y,int state){
	int n = board[y][x];
	if(n<0)assert(0);
	if(hasbit(state,n))assert(0);

	return state + (1<<n);
}

int solve(){
	
	queue<Q> que;
	que.push(Q(stx,sty,0,0));

	while(!que.empty()){
		Q u = que.front(); que.pop();
		if(hasmemo(u))continue;
		setmemo(u);

		//printf("%d %d\n",u.x,u.y);

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

		rep(p,8){
			int st = u.state;
			reps(i,1,100){
				int nx = u.x + dx[p]*i;
				int ny = u.y + dy[p]*i;


				if(i==1){
					if(isout(nx,ny))break;
					if(isgoal1(nx,ny))break;
					if(!isblack(nx,ny,st))break;
				}
				if(i!=1){
					if(isout(nx,ny))break;
					if(isgoal1(nx,ny) || isgoal2(nx,ny))return u.cnt+1;
					if(!isblack(nx,ny,st)){
						que.push(Q(nx,ny,u.cnt+1,st));
						break;
					}
				}

				st = minblack(nx,ny,st);
			}
		}
	}
	return -1;
}

int main(){
	input();
	cout<<solve()<<endl;
}

Measured memory_bytes: 54284
#include <stdio.h>
#include <string.h>
#include <math.h>
#define rep(i,l,n) for(i=l;i<n;i++)

void print(char str[],int a,int b){
	int i;
	rep(i,a,b+1) printf("%c",str[i]);
	printf("\n");
}

void reverse(char str[],int a,int b){
	int i;
	char str2[1010];
	rep(i,0,b-a+1) str2[a+i]=str[b-i];
	rep(i,a,b+1) str[i]=str2[i];
}

void replace(char str[],int a,int b,char p[]){
	int i;
	rep(i,0,b-a+1) str[a+i]=p[i];
}

int main(void){
	char str[1010],od[10],p[1010];
	int q,i,a,b;
	
	scanf("%s",str);
	scanf("%d",&q);
	
	rep(i,0,q){
		scanf("%s",od);
		if(strcmp(od,"print")==0){
			scanf("%d %d",&a,&b);
			print(str,a,b);
		}else if(strcmp(od,"reverse")==0){
			scanf("%d %d",&a,&b);
			reverse(str,a,b);
		}else if(strcmp(od,"replace")==0){
			scanf("%d %d %s",&a,&b,p);
			replace(str,a,b,p);
		}
	}
	
	return 0;
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6;

set<int> st;
map<int, bool> mp, mp2;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		if (st.count(x)) mp[x] = true;
		st.insert(x);
	}
	int ans = 0;
	for (auto i : st) {
		if (mp2[i]) continue;
		for (int j = i + i; j <= MAXN; j += i)
			mp2[j] = true;
		ans += !mp[i] and !mp2[i];
	}
	cout << ans << "\n";
}

Measured memory_bytes: 59912
/*
[abc133] F - Colorful Tree
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int MAX_N = 1e5;
const int MAX_Q = 1e5;

const int MAX_V = MAX_N;
const int MAX_LOG_V = 18;

struct edge {
    int d;
    int c;
    int to;
};

int N, Q;
vector<edge> g[MAX_N];
unordered_set<int> req[MAX_N];
int X[MAX_Q], Y[MAX_Q], U[MAX_Q], V[MAX_Q];
int W[MAX_Q];
int dist[MAX_N];
int cur_num[MAX_N], cur_sum[MAX_N];
unordered_map<int, int> num[MAX_N], sum[MAX_N];

int par[MAX_LOG_V][MAX_V];
int dep[MAX_V];

void dfs(int v, int p = -1, int d = 0) {
    par[0][v] = p;
    dep[v] = d;
    for (auto& e : g[v]) {
        if (e.to == p) {
            continue;
        }
        dfs(e.to, v, d + 1);
    }
}

int lca(int u, int v) {
    if (dep[u] > dep[v]) {
        swap(u, v);
    }
    for (int k = 0; k < MAX_LOG_V; k++) {
        if (((dep[v] - dep[u]) >> k) & 1) {
            v = par[k][v];
        }
    }
    if (u == v) {
        return u;
    }
    for (int k = MAX_LOG_V - 1; k >= 0; k--) {
        if (par[k][u] != par[k][v]) {
            u = par[k][u];
            v = par[k][v];
        }
    }
    return par[0][u];
}

void init() {
    dfs(0);
    for (int k = 1; k < MAX_LOG_V; k++) {
        for (int v = 0; v < N; v++) {
            par[k][v] = (par[k - 1][v] < 0) ? -1 : par[k - 1][par[k - 1][v]];
        }
    }
}

void dfs2(int v, int par = -1) {
    for (int c : req[v]) {
        num[v][c] = cur_num[c];
        sum[v][c] = cur_sum[c];
    }

    for (auto& e : g[v]) {
        if (e.to == par) {
            continue;
        }
        dist[e.to] = dist[v] + e.d;
        cur_num[e.c]++;
        cur_sum[e.c] += e.d;
        dfs2(e.to, v);
        cur_num[e.c]--;
        cur_sum[e.c] -= e.d;
    }
}

int calc(int v, int x, int y) { return dist[v] - sum[v][x] + y * num[v][x]; }

void solve() {
    init();
    for (int i = 0; i < Q; i++) {
        W[i] = lca(U[i], V[i]);
        req[U[i]].insert(X[i]);
        req[V[i]].insert(X[i]);
        req[W[i]].insert(X[i]);
    }

    dfs2(0);

    for (int i = 0; i < Q; i++) {
        int ans = calc(U[i], X[i], Y[i]) + calc(V[i], X[i], Y[i]) -
                  2 * calc(W[i], X[i], Y[i]);
        cout << ans << endl;
    }
}

int main() {
    cin >> N >> Q;
    for (int i = 0; i < N - 1; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--, c--;
        g[a].push_back((edge){d, c, b});
        g[b].push_back((edge){d, c, a});
    }
    for (int i = 0; i < Q; i++) {
        cin >> X[i] >> Y[i] >> U[i] >> V[i];
        X[i]--, U[i]--, V[i]--;
    }

    solve();

    return 0;
}


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

int main(){
	string str;
	cin >> str;
	
    int count=0;

    for(int i=0;i<str.size();i++){
        for(int j=0;j<str.size();j++){
            if(!(i==j)){
                if(str.at(i)==str.at(j)){
                    count++;
                }
            }
        }
    }
	
    if(count==0){
        cout << "yes" << endl;
    }
    else{
        cout << "no" << endl;
    }
	
}


Measured memory_bytes: 256
# 1. 最大公約数を求める(ユークリッドの互除法)
# 2. 最大公約数を素因数分解する。
# 3. 2.の結果に含まれる素数＋１が答え

import itertools
from fractions import gcd
from math import ceil

def main():
  a, b = map(int, input().split())
  fac = facto(gcd(a,b))
  print(len(fac))  
  
def facto(n):
  fac = [1]
  if n == 1:
    return [1]
  elif n % 2 == 0:
    fac = [1, 2]
    while n % 2 == 0:
      n = n // 2
  
  max_n = ceil(n ** 0.5) + 1
  
  is_prime = [True for x in range(max_n)]
  for cursor in range(3, max_n, 2):
    if is_prime[cursor]:
      if n % cursor == 0:
        fac.append(cursor)
        while n % cursor == 0:
          n = n // cursor
        if n == 1:
          break
      for i in range(cursor, max_n, cursor):
        is_prime[i] = False
  if n != 1:
    fac.append(n)
  return fac

if __name__ == "__main__":
  main()


Measured memory_bytes: 118248
#include<bits/stdc++.h>
using namespace std;
const int Max = 1e5+5;
vector<int> edges[Max];
int in_degree[Max],dist[Max];
bool visited[Max];

void dfs(int a){
    visited[a] = true;
    for(int x : edges[a]){
        dist[x] = max(dist[x],dist[a]+1);
        --in_degree[x];
        if(in_degree[x]==0)
            dfs(x);
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        edges[a].push_back(b);
        ++in_degree[b];
    }

    for(int i = 1;i<=n;i++){
        if(!visited[i] && in_degree[i] == 0){
            dfs(i);
        }
    }
    int ans = 0;
    for(int i = 1;i<=n;i++)
        ans = max(ans,dist[i]);
    cout<<ans<<endl;



}


Measured memory_bytes: 9728
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    P = [0] + list(map(int, input().split()))
    ans = 0
    for i in range(1, N):
        if i == P[i]:
            P[i + 1] = P[i]
            ans += 1
    if N == P[N]: ans += 1
    print(ans)



if __name__ == "__main__":
    main()


Measured memory_bytes: 85540
use std::io;
use std::str::FromStr;

fn input_i32_vec() -> Vec<i32> {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.split_whitespace().map(|s| s.parse().unwrap()).collect()
}

fn main() {
    let len = input_i32_vec();
    let mut max = 0;
    for l in &len {  
        if *l > max {
            max = *l;
        }
    }
    let mut sum = 0;
    for l in &len {
        sum += *l;        
    }
    println!("{}", sum - max);
}


Measured memory_bytes: 4352
#include<stdio.h>
int main(void){
  int n;
  int i;
  int A,B;
  int a,b;

  while(1){
    scanf("%d",&n);
    if(n==0) break;
    A = 0;
    B = 0;
    for(i=0; i<n; i++){
      scanf("%d %d",&a,&b);
      if(a<b) B += a+b;
      else if(a>b) A += a+b;
      else{
	A += a;
	B += b;
      }
    }
    printf("%d %d\n",A,B);
  }
  

  return 0;
}

Measured memory_bytes: 600
import scala.collection.mutable
import scala.io.Source.stdin

/**
  * AOJ
  */
object Main {

  val alphabet = "abcdefghijklmnopqrstuvwxyz"

  def main(args: Array[String]): Unit = {

    val alphabetMap = read()

    for(c <- alphabet){
      println(c + " : " + alphabetMap(c).toString)
    }
  }

  def read(): mutable.Map[Char,Int] = {

    var alphabetMap = mutable.Map.empty[Char, Int]

    for (c <- alphabet) {
      alphabetMap += c -> 0
    }

    for (line <- stdin.getLines(); c <- line.toLowerCase) {
      if (line.length == 0) {
        return alphabetMap
      }
      if (alphabetMap.contains(c)) {
        alphabetMap(c) += 1
      }
    }
    alphabetMap
  }
}

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

int main(){
  int S = 0;
  string ope;
  cin >> ope;
  
  for(int i = 0; i < 4; i++){
    if(ope[i] == '+')
      S++;
  	else
      S--;
  }
  cout << S << endl;
}

Measured memory_bytes: 3608
y,x=gets.split(' ').map(&:to_i)
a=[]; b=[]
y.times{|i| a << gets.split(' ').map(&:to_i)}
x.times{|i| b << gets.to_i}
a.each do |vs|
  puts vs.each_with_index.map{|v,i| v*b[i]}.inject(&:+)
end

Measured memory_bytes: 9004
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
    int N, L;
    cin >> N >> L;
    vector<int>apple(N);
    for (int i = 0; i < N; ++i) {
        apple[i] = L + i;
    }
    int a = 100000;
    for (int i = 0; i < N; ++i) {
        if(abs(a) > abs(apple[i])) a = apple[i];
    }
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += apple[i];
    }
    ans -= a;
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
N, Q = map(int, input().split())
S = list(input())
ans_lst = []
cum = []
tmp = 0
for i in range(1, N):
    if (S[i-1] == "A" and S[i] == "C"):
        tmp += 1
    cum.append(tmp)

# cum = [1 if (S[i] == "A" and S[i+1] == "C") else 0 for i in range(N-1)]
for i in range(Q):
    l, r = map(int, input().split())
    if l != 1:
        num = cum[r-2] - cum[l-2]
    else:
        num = cum[r-2]
    ans_lst.append(num)

for ans in ans_lst:
    print(ans)


Measured memory_bytes: 10980
def comb(n, r, mod):
    r = min(r, n-r)
    mol = 1
    for i in range(n-r+1, n+1):
        mol = (mol * i) % mod
    deno = 1
    for i in range(1, r+1):
        deno = (deno * i) % mod
    ret = mol * pow(deno, mod-2, mod) % mod
    return ret

n,a,b = map(int,input().split())

P = 10**9+7

nCa = comb(n, a, P)
nCb = comb(n, b, P)

ans = (pow(2,n,P) -1 - nCa - nCb + 2*P)%P
print(ans)


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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> h(n);
  rep(i, n) cin >> h[i];

  vector<ll> dp(n, 1e12);
  dp[0] = 0;
  rep(i, n) rep(j, k) {
    if (i+j+1 < n) dp[i+j+1] = min(dp[i+j+1], dp[i] + abs(h[i] - h[i+j+1]));
  }
  cout << dp[n-1] << endl;
  return 0;
}

Measured memory_bytes: 4432
import java.util.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);    
    StringBuilder sb = new StringBuilder(sc.next());
    int price = 700;
    for(int i = 0; i < sb.length(); i++){
      price += (sb.charAt(i) == 'o' ? 100 : 0);
    }
    System.out.println(price);
  }
}


Measured memory_bytes: 21972
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <math.h>
#include <queue>
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<ll> l(n);
    rep(i,n) cin >> l[i];
    sort(l.begin(),l.end());
    int cnt=0;
    rep(i,n-2) {
        for (int j=i+1; j<n-1; ++j) {
            for (int k=j+1; k<n; ++k) {
                if(l[i]+l[j]>l[k]&&l[i]!=l[j]&&l[i]!=l[k]&&l[k]!=l[j]) cnt++;
            }
        }
    } 
    cout << cnt << endl;
    return 0;
}

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

const int INF = 1000000000;
 
int c[10][1000];
 
int main() {
  int h, w, k;
  cin >> h >> w >> k;
  
  vector<string> s(h);
  rep(i, h) cin >> s[i];
  
  int res = INF;
  
  rep(d, 1<<(h-1)){
    int g = 0;
    vector<int> id(h);
    rep(i, h){
      id[i] = g;
      if(d>>i & 1) ++g;
    } 
    ++g;
    
    rep(i, h) rep(j, w) c[i][j] = 0;
    rep(i, h) rep(j, w) c[id[i]][j] += (s[i][j] - '0');
    
    int cut = g-1;
    vector<int> n(g);
    
    auto add = [&](int j){
      rep(i, g) n[i] += c[i][j];
      rep(i, g) if(n[i] > k) return false;
      return true;
    };
    
    rep(j, w){
      if(!add(j)){
        ++cut;
        n = vector<int>(g);
        if(!add(j)){
          cut = INF;
          break;
        }
      }
    }
    res = min(res, cut);
  }
  
  cout << res << endl;
    
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int maxn = 1e5;
int n, x;
ll ans, tot, sum[maxn + 10];

struct node {
	int b, l, u;
	ll w;

	bool operator < (const node &t) const {
		return w > t.w;
	}
}a[maxn + 10];

ll chk(ll v) {
	ll cnt, r;
	if (v < n * x) {
		cnt = v / x, r = v % x;
	} else {
		cnt = n - 1, r = x;
	}
	ll w;
	for (int i = 1; i <= n; ++i) {
		if (i <= cnt) w = sum[cnt + 1] - a[i].w;
		else w = sum[cnt];
		if (r < a[i].b) w += a[i].l * (r - a[i].b) + a[i].l * a[i].b;
		else w += a[i].u * (r - a[i].b) + a[i].l * a[i].b;
		if (w >= tot) return 1;
	}
	return 0;
}

signed main() {
	scanf("%lld%lld", &n, &x);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld%lld", &a[i].b, &a[i].l, &a[i].u);
		tot += a[i].l * a[i].b;
		a[i].w = a[i].u * (x - a[i].b) + a[i].l * a[i].b;
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++i)
		sum[i] = sum[i - 1] + a[i].w;
	ll l = 0, r = 1e18;
	while (l != r) {
		ll mid = (l + r) >> 1;
		if (chk(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%lld", l);
}


Measured memory_bytes: 4096
ABCK = list(map(int, input().split()))
A = ABCK[0]
B = ABCK[1]
C = ABCK[2]
K = ABCK[3]

if A>K:
    print(K)
elif A+B > K:
    print(A)
else:
    print(A-(K-(A+B)))

Measured memory_bytes: 9188
#include <cstdio>
#include <algorithm>
using namespace std;

long long int X(long long int d) {
    return d*(d+1) / 2;
}

long long int get_value(long long int len, long long int l) {
    long long int r = l + len;
    return X(r) - X(l);
}

int main() {
    long long int B;
    while(scanf("%lld", &B), B) {
        for(int len=50000; len>=1; len--) {
            if(X(len) > B) continue;

            long long int ub = B+10, lb = -1;
            while(ub - lb > 1) {
                long long int mid = (ub + lb) / 2;

                if(get_value(len, mid) >= B) ub = mid;
                else lb = mid;
            }

            if(get_value(len, ub) == B) {
                printf("%lld %d\n", ub+1, len);
                break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 2724
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;

int dp[305][305];
string dp2[305][305];

int main(void){
	while(1){
		string str;
		cin >> str;
		if(str=="#END")break;
		int res=0,id=0;
		for(int k=1;k<(int)str.size();k++){
			string str1=str.substr(0,k);
			string str2=str.substr(k);
			memset(dp,0,sizeof(dp));
			for(int i=0;i<str1.size();i++){
				for(int j=0;j<str2.size();j++){
					if(str1[i]==str2[j]){
						dp[i+1][j+1]=dp[i][j]+1;
					}else{
						dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
					}
				}
			}
			if(res<dp[str1.size()][str2.size()]){
				res=dp[str1.size()][str2.size()];
				id=k;
			}
		}
		string str1=str.substr(0,id);
		string str2=str.substr(id);
		for(int i=0;i<=str1.size();i++){
			for(int j=0;j<=str2.size();j++){
				dp2[i][j]="";
			}
		}
		for(int i=0;i<str1.size();i++){
			for(int j=0;j<str2.size();j++){
				if(str1[i]==str2[j]){
					dp2[i+1][j+1]=dp2[i][j]+str1[i];
				}else{
					if(dp2[i][j+1].size()<=dp2[i+1][j].size())dp2[i+1][j+1]=dp2[i+1][j];
					if(dp2[i][j+1].size()>dp2[i+1][j].size())dp2[i+1][j+1]=dp2[i][j+1];
				}
			}
		}
		cout << dp2[str1.size()][str2.size()] << endl;
	}
	return 0;
}

Measured memory_bytes: 4856
/*  -*- coding: utf-8 -*-
 *
 * b.cc: B - Contests
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  int n, a, b;
  scanf("%d%d%d", &n, &a, &b);

  int c1 = 0, c2 = 0, c3 = 0;
  for (int i = 0; i < n; i++) {
    int ai;
    scanf("%d", &ai);

    if (ai <= a) c1++;
    else if (ai <= b) c2++;
    else c3++;
  }

  printf("%d\n", min(min(c1, c2), c3));
  return 0;
}


Measured memory_bytes: 256
// Created by arvybhatt

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define p_b push_back
#define m_p make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)

using namespace std;
using ll = long long;

int main()
{
    fast;
	ll a,b,c;cin>>a>>b>>c;
	ll k;cin>>k;
	ll ans=0;
	ll x=min(a,k);
	k-=x;
	ans+=x*1;
	x=min(b,k);
	k-=x;
	x=min(c,k);
	k-=x;
	ans+=x*-1;
	cout<<ans;

    return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>

int main()
{
	int aj,as,ar,ae;
	int bj,bs,br,be;
	int S,T;
	
	scanf("%d %d %d %d",&aj,&as,&ar,&ae);
	scanf("%d %d %d %d",&bj,&bs,&br,&be);
	S=aj+as+ar+ae;
	T=bj+bs+br+be;
	
	if(S>T)printf("%d\n",S);
	else   printf("%d\n",T);
}

Measured memory_bytes: 1800
"""
AtCoder :: M-Solutions Programming Contest 2020 :: Kyu in AtCoder
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_a
"""
import sys


def solve(rating):
    """Solve puzzle."""
    if 400 <= rating and rating <= 599: 
        return 8
    elif 600 <= rating and rating <= 799: 
        return 7
    elif 800 <= rating and rating <= 999: 
        return 6
    elif 1000 <= rating and rating <= 1199: 
        return 5
    elif 1200 <= rating and rating <= 1399:
        return 4
    elif 1400 <= rating and rating <= 1599: 
        return 3
    elif 1600 <= rating and rating <= 1799: 
        return 2
    elif 1800 <= rating and rating <= 1999: 
        return 1


def main():
    """Main program."""
    rating = int(sys.stdin.readline())
    print(solve(rating))


if __name__ == '__main__':
    main()


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

int main() {
  int count = 0;
  string s;
  cin >> s;
  
  for (int i = 1; i < s.size()-1; i++) {
    count++;
  }
  cout << s[0] + to_string(count) + s[s.size()-1] << endl;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
MOD = 10 ** 9 + 7

ans = 0
cnt = [0] * (k + 1)
for num in range(1, k + 1)[::-1]:
    cnt[num] = pow((k // num), n, MOD)
    tmp = 2 * num
    while True:
        if tmp >= k + 1:
            break
        cnt[num] -= cnt[tmp]
        cnt[num] % MOD
        tmp += num
        
for num in range(1, k + 1):
    ans += cnt[num] * num
    ans %= MOD
print(ans % MOD)

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



void solve(int T){
    ld a,b,h,m;
    cin>>a>>b>>h>>m;
    ld c=PI*2.0*(h/12.0+(m/60.0)/12.0 - m/60.0);
    ld ans=a*a + b*b - 2.0*a*b*(ld)cos(c);
    cout<<fixed<<setprecision(10)<<sqrt(ans);
}

int main() {
    //fastio

    int T=1;
    //cin>>T;
    for(int i=1;i<=T;i++){
        solve(i);
    }
	return 0;
}


Measured memory_bytes: 4140
int main()
{
	int N, C, p, S;
	int ans;

	scanf("%d%d", &N, &C);
	for (S = 0; C; C--) {
		scanf("%d", &p);
		S += p;
	}
	ans = S / (N + 1);
	if (S % (N + 1)) {
	    ans++;
	}
	printf("%d\n", ans);
	
	return 0;
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< int, int >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace std;
string repeat(string s, int n) {
    string s1 = "";
    for (int i=0; i<n;i++)
        s1+=s;
    return s1;
}
string getString(char x) {
    string s(1, x);
    return s;
}

void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int gcd(int a, int b){
    if (a == 0)  return b;
    return gcd(b % a, a);
}
void  solve(){
  int n;
  cin>>n;
  vector<int> dp(n+1,INT_MAX);
  dp[0]=0;
  rep(j,0,n){
    dp[j+1]=min(dp[j+1],dp[j]+1);
    int num=j+6,c=6;
    for(;num<=n;num=j+c*6,c=c*6) dp[num]=min(dp[num],dp[j]+1);

    num=j+9,c=9;
    for(;num<=n;num=j+c*9,c=c*9) dp[num]=min(dp[num],dp[j]+1);
  }
  cout<<dp[n]<<endl;
}
int main(){
    optimizeIO();
    // tc
    { solve();
    }
}


Measured memory_bytes: 3696
n,x = map(int,input().split())
li = list(map(int,input().split()))
cnt = 0
total = 0
for i in li:
    total += i
    cnt += 1
    if total > x:
        break
if sum(li) <= x:
    print(len(li) + 1)
else:
    print(cnt)

Measured memory_bytes: 3060
def main():
  n = int(input())
  a = list(input_list())
  ac = collections.Counter(sorted(a))
  aa = []
  hw = []
  for v, count in ac.items():
    if count >= 2:
      aa.append(v)
    if count >= 4:
      hw.append(v)
      
  sa = sorted(aa, reverse=True)
  shw = sorted(hw, reverse=True)
  if len(shw) > 0:
    if len(sa) < 2:
      print(shw[0]*shw[0])
    else:
      print(max(shw[0]*shw[0], sa[0]*sa[1]))
    exit()
  
  if len(sa) < 2:
    print(0)
    exit()
  
  print(sa[0]*sa[1])
    
    
  
def input_list():
  return map(int, input().split())

def input_list_str():
  return map(str, input().split())

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c 

import math
import fractions
import collections
from functools import reduce
main()

Measured memory_bytes: 21100
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <cmath>
#include <iomanip>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int n; std::cin >> n;
    std::vector<int> r(n);

    for(int i=0; i<n; i++) r[i] = i+1;

    std::vector<int> p(n), q(n);
    for(int i=0; i<n; i++) std::cin >> p[i];
    for(int i=0; i<n; i++) std::cin >> q[i];

    int cnt = 0, a = 0, b = 0;
    do
    {
        cnt++;
        for(int i=0; i<n; i++)
        {
            if(r[i]!=p[i]) break;
            if(i==n-1) a = cnt;
        }

        for(int i=0; i<n; i++)
        {
            if(r[i]!=q[i]) break;
            if(i==n-1) b = cnt;
        }

        if(a!=0 && b!=0) break;
    } while (std::next_permutation(r.begin(), r.end()));


    std::cout << abs(a-b) << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;

  int sz;
  vector< Monoid > seg;

  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }
};

int main(){

  int n;
  cin >> n;
  ll h[n];
  rep(i,n){
    cin >> h[i];
    h[i]--;
  }
  ll a[n];
  rep(i,n) cin >> a[i];

  SegmentTree<ll> seg(n, [](ll a, ll b){return max(a,b);}, 0LL);
  rep(i,n){
    ll t=seg.query(0,h[i]);
    seg.update(h[i],t+a[i]);
  }
  cout << seg.query(0,n) << endl;
  

  return 0;

}


Measured memory_bytes: 7424
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<string> vs;
typedef vector<bool> vb;

const ll mod=1e9+7;
const ll inf=1e16;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m-1;i>=n;i--)
#define fi first
#define se second
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define eb(x) emplace_back(x)
#define all(x) x.begin(),x.end()
#define gll greater<ll>()


void solve(){
ll t;
  cin >> t;
  while(t--){
   ll a,b,c,d;
    cin >> a >> b >> c >> d;
    if((b>a)||(b>d)) {
      cout << "No" << endl;
      continue;
    }
    ll g=__gcd(b,d);
   cout << (b-g+(a%g)>c?"No":"Yes") << endl;
    
  }
}
int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);
  solve();
}  


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
	int H, W, height, bottom;
	scanf("%d %d", &H, &W);
	while (H != 0 && W != 0)
	{
		for (height = 1; height <= H; height++)
		{
			for (bottom = 1; bottom <=W ; bottom++)
			{
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
		scanf("%d %d", &H, &W);
	}
	return 0;
}


Measured memory_bytes: 2052
// E - Colorful Hats 2
#include <bits/stdc++.h>

using namespace std;

#define	MOD	1000000007

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	vector<long long> dp(n), c(n);
	c[0] = 3;
	for (int i = 0; i < n; i++) {
		int x = a[i];
		dp[i] = (i == 0 ? 1LL : dp[i - 1]) * c[x] % MOD;
		c[x]--;
		c[x + 1]++;
	}

	cout << dp[n - 1] << endl;

	return 0;
}


Measured memory_bytes: 2176
A, B = gets.split.map(&:to_i)

a = A%4
b = B%4

# p [a, b]

# p xor(3, 2)

if a  == 0
  if b == 0
    p B
  elsif b == 1
    p 1
  elsif b == 2
    p B+1
  else
    p 0
  end
elsif a == 1
  if b == 0
    p (A-1)^B
  elsif b == 1
    p A
  elsif b == 2
    p A^B
  else
    p A-1
  end
elsif a == 2
  if b == 0
    p B + 1
  elsif b == 1
    p 0
  elsif b == 2
    p B
  else
    p 1
  end
else
  if b == 0
    p A^B
  elsif b == 1
    p A-1
  elsif b == 2
    p (A-1)^B
  else
    p A
  end
end



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

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define MOD 1000000007
#define mm(arr) memset(arr, 0, sizeof(arr))
#define F first
#define S second

int main(){
    FAST
    int k, a, b;
    cin >> k >> a >> b;
    int c = 1;
    while(k*c <= b){
        if(k*c >= a && k*c <= b){
            cout << "OK";
            return 0;
        }
        c++;
    }
    cout << "NG";
    return 0;
}


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

int main() {
  int N;
  cin>>N;
  int a[]={1,2,4,8,16,32,64,128};
  for (int i=0;i<7;i++){
    if(a[i]<=N&&N<a[i+1]) cout<<a[i]<<endl;
  }
}
  
  



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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

template<typename T>
constexpr T inf = static_cast<T>(pow(10, static_cast<int>(log10(numeric_limits<T>::max())))) + 7;
constexpr llong mod = 1e9+7;

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

  bool ok = true;
  string s = S.substr(0, S.size());
  string t = S.substr(0, (S.size()-1)/2);
  string r = S.substr((S.size() + 3)/2 - 1, S.size() - (S.size() + 3)/2 + 1);
  cerr << s << endl << t << endl << r << endl;

  for (int i = 0; i < s.size(); ++i) {
    ok &= s[i] == s[s.size()-i-1];
  }
  for (int i = 0; i < t.size(); ++i) {
    ok &= t[i] == t[t.size()-i-1];
  }
  for (int i = 0; i < r.size(); ++i) {
    ok &= r[i] == r[r.size()-i-1];
  }

  cout << (ok?"Yes":"No") << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;cin>>n;
  	vector<vector<int>> t(n,vector<int>(3));
  	for(int i=0;i<n;i++){
    	cin>>t[i][0]>>t[i][1]>>t[i][2];
    }
  	long long d[3];
  	d[0]=t[0][0];//A
  	d[1]=t[0][1];//B
  	d[2]=t[0][2];//C
  	long long a,b,c;
  	for(int i=1;i<n;i++){
  		a=max(d[1]+t[i][0],d[2]+t[i][0]);
      	b=max(d[0]+t[i][1],d[2]+t[i][1]);
        c=max(d[0]+t[i][2],d[1]+t[i][2]);
      	d[0]=a;d[1]=b;d[2]=c;
    }
  	cout<<max(d[0],max(d[1],d[2]))<<endl;
}


Measured memory_bytes: 5760
n = int(input())
li = list(map(int,input().split()))
count=0
for i in range(n-2):
  if(li[i+2]>li[i+1] and li[i+1]>li[i]):
    count+=1
  if(li[i+2]<li[i+1] and li[i+1]<li[i]):
    count+=1

print(count)

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

const int INF = 101;

vector<vector<int>> GetAdjacencyMatrix(int n)
{
	vector<vector<int>> am(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		int u, k;
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; j++) {
			int v;
			cin >> v;
			am[u][--v] = 1;
		}
	}
	return am;
}

void BFS(int startNode, int n, const vector<vector<int>>& am, vector<int>& minDistances)
{
	queue<int> q;
	q.push(startNode);
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		for (int i = 0; i < n; i++) {
			if (am[node][i] == 0) continue;
			if (minDistances[i] != INF) continue;
			q.push(i);
			int distance = minDistances[node] + 1;
			minDistances[i] = min(minDistances[i], distance);
		}
	}
}

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> am = GetAdjacencyMatrix(n);
	vector<int> minDistances(n, INF);
	minDistances[0] = 0;
	BFS(0, n, am, minDistances);
	for (int i = 0; i < n; i++) {
		if (minDistances[i]==INF) cout << i + 1 << " " << -1 << endl;
		else cout << i + 1 << " " << minDistances[i] << endl;
	}
}



Measured memory_bytes: 3152
N = int(input())
li = list(map(int,input().split()))
HPmin = 0
sum = 0
while sum != N-1 :
    li.sort()
    for i in range(sum + 1,N) :
        li[i] %= li[sum]
    HPmin = li[0]
    sum = 0
    for i in range(N) :
        if li[i] == 0 :
            sum+=1
li.sort()
print(li[N-1])

Measured memory_bytes: 14252