akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long   // aaaaaaaaaaaaaaaaaa
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
template<typename T, typename U>ostream& operator << (ostream& os, pair<T, U>& pair_var)
{os << "(" << pair_var.first << ", " << pair_var.second << ")";return os;}
// head

int x,y,n,w,l,q,res;
int a[800][1000] = {};
int c[1000][1000] = {};
int dp[2020][2020] = {};
int yoko[1000][1008] = {};
string s;
vector<pair<char,int> > vec;
signed main() {
	std::cin >>x>>y;
	res += x+y/2;
	std::cout << res << '\n';
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <string>
#include <cmath>
#include <array>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
using vl = vector<ll>;  // long longの1次元の型に vl という別名をつける
using vvl = vector<vl>; // long longの2次元の型に vvl という別名をつける
int MOD = 1000000007; //10^9 + 7

// 無限大の値
const ll  lINF = 1LL << 60;
const int iINF = 1 << 29;

int main(void){
  int n;
  cin >> n;

  vi a(n);
  rep(i,n) cin >> a[i];

  sort(a.begin(), a.end());

  int i=0,ans=0;
  
  while(i <n){
    int now=a[i], flag=0;
    while(a[i]==now && i<n){
      i++;
      flag = 1 - flag; 
    }
    ans += flag;
  }

  cout << ans << endl;
  return 0;
}

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

pair<int, int> perse(string s) {
  int a = 0, b = 0;
  int i = 0;
  while (s[i] != ',') {
    int x = s[i] - '0';
    a = 10 * a + x;
    ++i;
  }
  // cerr << a << " ";
  ++i;
  while (i != s.size()) {
    int x = s[i] - '0';
    b = 10 * b + x;
    ++i;
  }
  // cerr << b << endl;

  return make_pair(a, b);
}

int main() {
  string s;
  int cnt[2][1001] = {};

  int idx = 0;
  while (getline(cin, s)) {
    if (s == "") {
      idx++;
      continue;
    }

    pair<int, int> data = perse(s);
    cnt[idx][data.first]++;

    // cerr << data.first << " " << data.second << endl;
  }
  for (int i = 1; i <= 1000; ++i) {
    if (cnt[0][i] && cnt[1][i]) cout << i << " " << cnt[0][i] + cnt[1][i] << endl;
  }
}

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

//int a[100001];

bool intersect (int l1, int r1, int l2, int r2) {
	if (l2 > r1 || r2 < l1) return 0;
	else return 1;
}
 
 main () {
	ios_base::sync_with_stdio (0);	
	cin.tie (0), cout.tie (0);
	int n;
	cin >> n;
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for (int i = 0;i < n;i ++) {
		int l1 = a + c * i;
		int r1 = a + d * i;
		int r2 = a - c * i;
		int l2 = a - d * i;
		int ll1 = b + c * (n - 1 - i);
		int rr1 = b + d * (n - 1 - i);
		int rr2 = b - c * (n - 1 - i);
		int ll2 = b - d * (n - 1 - i);
		if (intersect (l1, r1, ll1, rr1) || intersect (l1, r1, ll2, rr2) || intersect (l2, r2, ll1, rr1) || intersect (l2, r2, ll2, rr2)) {
			cout << "YES";
			return 0;
		}
	} 
	cout << "NO";
	return 0;
}

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

using namespace std;

bool dp[81][81][26000];
int a[81][81];
int b[81][81];

int main()
{
	int n=0,m=0;
	cin >> n >> m;
	for (int i=0; i<n; i++)
	{
		for (int j=0; j<m; j++)
		{
			cin >> a[i][j];
		}
	}		
	for (int i=0; i<n; i++)
	{
		for (int j=0; j<m; j++)
		{
			cin >> b[i][j];
		}
	}		
	dp[0][0][a[0][0]-b[0][0]+13000] = true;
	for (int i=0; i<n; i++)
	{
		for (int j=0; j<m; j++)
		{
			if (i==0 && j==0)
				continue;
			int d = a[i][j]-b[i][j];
			int d2 = b[i][j]-a[i][j];
			for (int k=0; k<26000; k++)
			{
				if (i-1>=0 && k-d>=0 && k-d<26000 && dp[i-1][j][k-d])
					dp[i][j][k] = true;	
				else 
				if (j-1>=0 && k-d>=0 && k-d<26000 && dp[i][j-1][k-d])
				{
					dp[i][j][k] = true;
				}
	
				if (i-1>=0 && k-d2>=0 && k-d2<26000 && dp[i-1][j][k-d2])
					dp[i][j][k] = true;	
				else 
				if (j-1>=0 && k-d2>=0 && k-d2<26000 && dp[i][j-1][k-d2])
				{
					dp[i][j][k] = true;
				}
			}
		}
	}	
	int Min = INT_MAX;
	for (int i=0; i<26000; i++)
	{
		if (dp[n-1][m-1][i])
		{
			Min = min(Min, abs(i-13000));
		}
	}
	cout << Min;
	return 0;
}



Measured memory_bytes: 164864
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

x = I()
if x>=30:
    print("Yes")
else:
    print("No")


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

int main(){
    int n;cin >> n;
    int k;cin >> k;
    string s;cin >>s;
    bool L = false;
    int count_s = 0;
    int count_o = 0;
    if(s[0] == 'L'){
        L  =true;
    }
    for(int i=1;i<s.size();i++){
        if(L){
            if(s[i] == 'L'){
                count_s++;
            }
            else{
                count_o++;
                L = false;
            }
        }
        else{
            if(s[i] == 'R'){
                count_s ++;
            }
            else{
                count_o++;
                L = true;
            }
        }
    }
    int ans = count_s;
    ans+= min(count_o,k*2);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.ComponentModel.Design;
using System.Globalization;
using System.IO.Compression;
using System.IO.Pipes;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var K = ReadInt();
            var S = Read();
            var Slength = S.Length;

            if (Slength <= K)
            {
                WriteLine(S);
            }
            else
            {
                for (int i = 0; i < K; i++)
                {
                    Write(S[i]);
                }
                WriteLine("...");
            }
        }
        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


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

int N,M,Q;
int a[50], b[50], c[50], d[50];

int ans = 0;
int A[12];

void dfs(int index) {
  if(index == (N+1)) {
    int score = 0;
    for(int i=0; i<Q; i++) {
      if(A[b[i]] - A[a[i]] == c[i]) score += d[i];
    }
    ans = max(ans, score);
    return;
  }

  for(int i=A[index-1]; i<=M; i++) {
    A[index] = i;
    dfs(index+1);
  }
}

signed main() {
  cin >> N >> M >> Q;
  for(int i=0; i<Q; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
  A[0] = 1;
  A[N+1] = M;
  dfs(1);
  cout << ans << endl;
}



Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define ALL(A) (A).begin(),(A).end()
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)

const ll mod = 1e9+7;
const ll INF = -1*((1LL<<63)+1);
const int inf = -1*((1<<31)+1);

using namespace std;

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N,M,V,P;
    cin >> N >> M >> V >> P;
    vector<ll> A(N);
    rep(i,N)cin >> A[i];
    sort(ALL(A),greater<>());
    ll ok = P-1;
    ll ng = N;
    while(abs(ok-ng)>1){
        ll mid = (ok+ng)/2;
        ll now = A[mid] + M; // 現在のmidの得点
        //midの得点が上から何番目になるかを数えたい
        ll big = V - (N - mid) - (P-1);//midよりも得点の大きい問題
        ll cnt = big * M;
        for(int i = mid-1;i>=P-1;i--){
            if(A[i]<now)cnt -= min(M,now-A[i]);
        }
        if(cnt>0){
            ng = mid;
            continue;
        }
        int p = -1;
        rep(i,N){
            if(now>=A[i]){
                p = i;
                break;
            }
        }
        if(p<P)ok = mid;
        else ng = mid;
    }
    cout << ok+1 << endl;
}

Measured memory_bytes: 1024
read A
read B
read C
read X

count=0
for (( a = 0; a <= A; a++)); do
	for (( b = 0; b <= B; b++ )); do
    	for(( c = 0;c <= C; c++ )); do
        	(( a * 500 + b * 100 + c * 50 == X )) && (( ++count))
        done
    done
done

echo ${count}

Measured memory_bytes: 376
//---------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#include<algorithm>
//---------------------------------------------------------------
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define SIZE 100005
#define INF 1e18
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define vec vector
using pint = pair<int,int>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
//---------------------------------------------------------------
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const double pi = acos(-1);
const int mod = 1000000007;
struct mint {
int64_t x;
mint(int64_t x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod;return *this;}
mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}
mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
mint operator+(const mint a) const { return mint(*this) += a;}
mint operator-(const mint a) const { return mint(*this) -= a;}
mint operator*(const mint a) const { return mint(*this) *= a;}
mint pow(int64_t t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}
mint inv() const { return pow(mod-2);}
mint& operator/=(const mint a) { return *this *= a.inv();}
mint operator/(const mint a) {return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
//---------------------------------------------------------------

//↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓


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

    ll n,k;
    cin>>n>>k;
    vll a(n);
    rep(i,n) cin>>a[i];
    
    ll ans = 0;
    if(n == k) cout<<1<<endl;
    else{
        while(n>0){
            n -=k;
            n++;
            ans++;
            if(n==k){
                ans++;
                break;
            }
        }
        cout<<ans<<endl;
    }
    
    
}

Measured memory_bytes: 3940
#include <iostream>

using namespace std;
int main() {
    int n;
    string value;
    int c[4] = {0,0,0,0};
    cin>> n;
    while(n){
        cin>> value;
        if(value == "AC")
            c[0]+= 1;
        else if(value == "WA")
            c[1]+= 1;
        else if(value == "TLE")
            c[2]+= 1;
        else
            c[3]+= 1;
        n--;
    }
    cout<< "AC x "<< c[0] <<"\nWA x "<< c[1] <<"\nTLE x "<< c[2] << "\nRE x "<< c[3];
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  ll ans = 1;
  rep(i,n){
    ans *= i + 1;
    ans %= mod;
  }
  cout << ans << endl;
}

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

using namespace std;

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

int main(){
    int n;
    cin >> n;
    int a[n];
    rep(i, n) cin >> a[i];
    sort(a, a + n);
    int t = 1;
    int ans = 0;
    rep(i, n - 1){
        if (a[i+1] == a[i]){
            t ^= 1;
        }else{
            ans += t;
            t = 1;
        }
    }
    ans += t;
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a;cin >> a;
	cout << a * a << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){

  int N,M;
  cin >> N >> M;

  int M2 = 1;
  for(int i = 0;i < M;i++)M2 *= 2;

  long long int ans = 1900 * M * M2 + 100 * (N - M) * M2;

  cout << ans << endl;

  return 0;

}


Measured memory_bytes: 256
a, b = input().split()
a = int(a)
b = int(b)
ans = -1
for i in range(1000000000000000000):
    if a % b == 0:
        break
    if a*i > 1000000000000000000:
        break
    if (a * i) % b != 0:
        ans = a * i
        break
print(ans)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    int a[5]={0};
    for(int i=0;i<5;i++)
        cin>>a[i];
    for(int i=0;i<5;i++)
        if(!a[i])
        cout<<i+1;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include<vector>
int main() {
	int n;
	int b;
	std::cin >> n >> b;
	std::vector<int> v(b);
	for (int i = 0; i < b; ++i) {
		int x, y;
		int a = 0;
		std::cin >> x >> y;
		a = std::min(n - x, std::min(n - y, std::min(x-1, y-1)));
		v[i] = a % 3;
	}
	for (int i = 0; i < b; ++i) {
		if (v[i] == 0) {
			std::cout << v[i] + 1 << std::endl;
		}
		if (v[i] == 1) {
			std::cout << v[i] + 1 << std::endl;
		}
		if (v[i] == 2) {
			std::cout << v[i] + 1 << std::endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll a, b;
  cin >> a >> b;
  ll ans = 0;
  rep2(i, a, b + 1) {
    string s = to_string(i);
    if(s[0] == s[4] && s[1] == s[3]) ans++;
  }
  cout << ans << endl;
}

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

int main(){
  int h, w;
  cin >> h >> w;

  int c[10][10];
  int a[10];
  for (int i = 0; i < 10; i++){
    a[i] = 0;
  }
  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      scanf("%d", &c[i][j]);
    }
  }
  for (int i = 0; i < h; i++){
    for (int j = 0; j < w; j++){
      int k;
      scanf("%d", &k);
      if (k == -1) continue;
      a[k]++;
    }
  }

  for (int i = 0; i < 10; i++){
    for (int j = 0; j < 10; j++){
      for (int k = 0; k < 10; k++){
        c[j][k] = min(c[j][i] + c[i][k], c[j][k]);
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < 10; i++){
    ans += a[i] * c[i][1];
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<map>
#include<cassert>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 500001

using namespace std;

map<string,int> getIndex;
int t,s;
bool found;
int T[MAX],S[MAX];
string type[12] = {"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};
int dc[] = {+0,+1,-1};
int dx[] = {-1,-2,+1};

void dfs(int cur_t,int cur_s)
{
  if(cur_s < 0)
    {
      if(cur_t == -1)found = true;
      return;
    }

  rep(i,3)
    {
      int music = (T[cur_t] + dc[i] + 12)%12;
      if(t <= cur_t+dx[i])continue;

      if(music == S[cur_s])dfs(cur_t+dx[i],cur_s-1);
    }
}

bool compute()
{
  found = false;
  dfs(t-1,s-1);
  if(!found)dfs(t-2,s-1);
  return found;
}

int main()
{
  rep(i,12)getIndex[type[i]] = i;
  int N;
  while(cin >> N)
    {
      while(N--)
	{

	  cin >> t >> s;
	  string input;
	  rep(i,t)
	    {
	      cin >> input;
	      T[i] = getIndex[input];
	    }
	  rep(i,s)
	    {
	      cin >> input;
	      S[i] = getIndex[input];
	    }
	  cout << (compute()?"Yes":"No") << endl;
	}
    }
  return 0;
}

Measured memory_bytes: 4736
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>  // min, max
#include <fstream>  // ifstream
#include <iomanip>  // setprecision
using namespace std;
typedef long long ll;

int main(void)
{
#ifdef FILE_DEBUG
    ifstream inputFile("data/input.txt");
    cin.rdbuf(inputFile.rdbuf());
#endif
    // これより下にコードを書く

    int N;
    cin >> N;

    if (N % 2 == 0)
        cout << N << endl;
    else
        cout << N*2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>

#define REP(i,n) for(i=0; i < (n); i++)
#define REPONE(i, n) for(i=1; i <= (n); i++)
#define LOOP(n) for(int loopCount=1; loopCount <= (n); loopCount++)
#define ITER(c) __typeof((c).begin())
#define EACH(c,it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define SZ(c) ((int) (c).size())
#define ALL(c) c.begin(), c.end()
#define SUM(c) accumulate(ALL(c), 0)
#define EXIST(c,v) (find(ALL(c), (v)) != (c).end())
#define PB push_back
#define MP make_pair
#define fs first
#define sc second

using namespace std;
static const double EPS = 1e-9;
static const double PI = 3.141592653589793238462643383279;
typedef long long ll;

int main(){
    int i, n, w, d, p, s, cnt;
    while(scanf("%d%d%d",&n,&w,&d)){
        if(!(n||w||d)) break;
        multiset< pair<pair<int, int>, pair<int, int> > > ps;
        ITER(ps) itr;
        ps.insert(MP(MP(-1,w*d),MP(w,d)));

        REP(i,n){
            scanf("%d%d",&p,&s);
            itr = ps.begin();
            advance(itr,p-1);
            pair< pair<int, int>, pair<int, int> > t = *itr;
            ps.erase(itr);
            s %= t.sc.fs + t.sc.sc;
            if(s < t.sc.fs){
                ps.insert(MP(MP(i,s*t.sc.sc),MP(s,t.sc.sc)));
                ps.insert(MP(MP(i,(t.sc.fs-s)*t.sc.sc), MP(t.sc.fs-s,t.sc.sc)));
            }
            else{
                s -= t.sc.fs;
                ps.insert(MP(MP(i,s*t.sc.fs),MP(t.sc.fs, s)));
                ps.insert(MP(MP(i,(t.sc.sc-s)*t.sc.fs), MP(t.sc.fs,t.sc.sc-s)));
            }
        }

        priority_queue<int, vector<int>, greater<int> > Q;
        EACH(ps,it){
            Q.push(it->fs.sc);
        }

        cnt = 0;
        while(!Q.empty()){
            printf("%d",Q.top());
            Q.pop();
            if(cnt++<n)printf(" ");
            else printf("\n");
        }
    }
    return 0;
}

Measured memory_bytes: 0
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct icpclog{
    int number, time, id;
    int submit_status[10 + 1];

    int compare(const icpclog& o) const {
        if(number != o.number) return o.number - number;
        return time - o.time;
    }

    bool operator <(const icpclog& o) const {
        int res = compare(o);
        if(res != 0) return res < 0;
        return o.id - id < 0;
    }
};

int main() {
    int contest_time, team_n, question_n, submit_n;
    while(cin >> contest_time >> team_n >> question_n >> submit_n, contest_time|team_n|question_n|submit_n){
        vector<icpclog> logs(team_n + 1);
        REP(i, logs.size()) logs[i].id = i;
        REP(i, submit_n){
            int time, team, question, judge;
            cin >> time >> team >> question >> judge;
            if(judge != 0)
                logs[team].submit_status[question]++;
            else{
                logs[team].time += time;
                logs[team].time += logs[team].submit_status[question] * 20;
                logs[team].number++;
            }
        }

        logs.erase(logs.begin());
        SORT(logs);

        cout << logs[0].id;
        FOR(i, 1, logs.size()){
            cout << (logs[i-1].compare(logs[i]) == 0 ? "=" : ",") << logs[i].id;
        }
        cout << endl;
    }
}

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

using namespace std;

int n;
bool graph[51][51];
bool vec[51];

void dfs(int x){
    if(vec[x])return;

    vec[x]=true;

    for(int i=0;i<n;i++){
        if(graph[x][i])
            dfs(i);
    }
}

int main(){
    int m;
    cin>>n>>m;
    vector<int> a(m),b(m);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];
        --a[i];--b[i];
        graph[a[i]][b[i]]=graph[b[i]][a[i]]=true;
    }

    int ans = 0;
    for(int i=0;i<m;i++){
        graph[a[i]][b[i]]=graph[b[i]][a[i]]=false;
        for(int j=0;j<n;j++)vec[j]=false;
        dfs(0);

        bool conn =false;
        for(int k=0;k<n;k++){
            if(!vec[k])conn=true;
        }
        if(conn)
            ans++;

        graph[a[i]][b[i]]=graph[b[i]][a[i]]=true;
    }
    cout<<ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0; i<(n); ++i)
#define REPR(i,n,m) for (int i=(n); i>=(m); --i)
using namespace std;
using LL = signed long long;
using LD = long double;
using PLL = pair<long long, long long>;
using PLD = pair<long double, long double>;
using VLL = vector<long long>;
using VLD = vector<long double>;
using VPLL = vector<PLL>;
using VPLD = vector<PLD>;

const int INF = numeric_limits<int>::max();

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

    LL n, d; cin >> n >> d;
    LL ans = 0;
    VPLL p(n);
    REP(i,n){
        cin >> p[i].first >> p[i].second;
        if (sqrt(pow(p[i].first,2) + pow(p[i].second, 2))<=d) ans++;
    }

    cout << ans << endl;



    return 0;
}


Measured memory_bytes: 6368
n = gets.to_i
a = gets.split.map(&:to_f)
b = gets.split.map(&:to_f)
c = Array.new(n)

for j in 0..(n-1)
c[j] = (a[j]-b[j]).abs
end

d = c.max

for e in 1..3

sum = 0
for j in 0..(n-1)
sum += c[j]**e
end

puts sum**(1.0/(e.to_f))

end

puts d



Measured memory_bytes: 8988
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_B main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif


int main_B() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int X; cin >> X;

    vi a;
    a.push_back(1);
    for (int b = 2; b < 32; b++) {
        int n = b*b;
        while(true) {
            if (n > X) break;
            a.push_back(n);
            n *= b;
        }
    }
    sort(a.begin(), a.end());

    int ans = a.back();

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main() {
    int in;
    cin >> in;
    double num=3.0;
    double one=in/num;

        /*if(in%3==2){
            cout << (in/3)*(in/3+1)*(in/3*1) << endl;
        }
        else if(in%3==1){
            cout << (in/3) * (in/3) * (in/3+1) << endl;
        }
        else{
            cout << (in/3)*(in/3) * (in/3) << endl;
        }*/
        cout << fixed << setprecision(12);
        cout << one*one*(in-one*2LL) << endl;
}

Measured memory_bytes: 256
/*بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم*/

#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <climits>
#include <map>
#include <cmath>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <vector>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <utility>
#include <queue>

#define ll long long
#define pb  push_back
#define mod  1000000007
#define inf  1000000000000000000
#define pi  acos(-1.0)
#define maxn  1000009
#define sorted(s)  sort(s.begin(),s.end())
#define slc(n) scanf("%I64d", &n)
#define sl(n)  scanf("%lld", &n)
#define sf(n)  scanf("%lf", &n)
#define si(n)  scanf("%d", &n)
#define sch(n)  scanf(" %c", &n)
#define ss(n)  scanf("%s", n)
#define pii  pair <int, int>
#define pll  pair <ll, ll>
#define plp  pair <int, pll >
#define pb  push_back
#define fr first
#define sc second
#define all(a)  a.begin(),a.end()

using namespace std;
ll a, b;

int main()
{
      cin>>a>>b;
      if(a%3==0 || b%3==0 || (a+b)%3==0)
            cout << "Possible\n";
      else
            cout << "Impossible\n";

      return 0;
}

/**look out for SPECIAL CASES**/

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

//Sport Meet
public class Main{

	static class T implements Comparable<T>{
		int id, t;
		public T(int id, int t) {
			this.id = id;
			this.t = t;
		}
		public int compareTo(T o) {
			return t-o.t;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			T[] t = new T[n];
			for(int i=0;i<n;i++){
				int id = sc.nextInt();
				int s = 0;
				for(int j=0;j<4;j++)s += sc.nextInt()*60+sc.nextInt();
				t[i] = new T(id, s);
			}
			Arrays.sort(t);
			System.out.println(t[0].id+"\n"+t[1].id+"\n"+t[n-2].id);
		}
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	ll n, m;
	cin >> n >> m;
	bool ans[n+1];
	memset(ans, 0, sizeof(ans));
	ll pena[n+1];
	memset(pena, 0, sizeof(pena));
	ll p;
	string s;
	rep(i, 1, m){
		cin >> p >> s;
		if(s == "AC"){
			ans[p] = true;
		}
		else{
			if(!ans[p]){
				pena[p]++;
			}
		}
	}
	
	ll anssum = 0;
	ll penasum = 0;
	rep(i, 1, n){
		//print(ans[i])
		//print(pena[i])
		if(ans[i]){
			anssum++;
		}
		if(ans[i]){
			penasum += pena[i];
		}
	}
	cout << anssum << " " << penasum << endl;
	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <iomanip>
#include <cmath>
#include <functional>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <boost/range/irange.hpp>
#include <boost/container/static_vector.hpp>
#include <boost/utility/string_ref.hpp>

template <class Integer>
auto boost_irange(Integer last) { return boost::irange(static_cast<Integer>(0), last); }
template <class Integer>
auto boost_irange(Integer first, Integer last) { return boost::irange(first, last); }

class input
{
    std::istream& cin;

public:
    input() : cin(std::cin)
    {
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
    }

    template <class T>
    inline input& operator>>(T& var)
    {
        cin >> var;
        return *this;
    }
    template <class T>
    inline input& operator,(T& var)
    {
        cin >> var;
        return *this;
    }

    template <class T>
    inline T read()
    {
        T var;
        cin >> var;
        return var;
    }

    template <class InputIterator>
    inline void read(InputIterator head, std::size_t n)
    {
        for (std::size_t i = 0; i < n; ++i) {
            cin >> *head;
            ++head;
        }
    }

    template <class T, class F>
    inline void online(std::size_t n, F&& f)
    {
        T var;
        for (std::size_t i = 0; i < n; ++i) {
            cin >> var;
            f(var);
        }
    }
};
template <class T, std::size_t n>
std::istream& operator>>(std::istream& in, std::array<T, n>& var)
{
    for (std::size_t i = 0; i < n; ++i) {
        in >> var[i];
    }
    return in;
}

class output
{
    std::ostream& cout;

public:
    class proxy
    {
        std::ostream& cout;

    public:
        proxy() : cout(std::cout) {}
        ~proxy() { cout << std::endl; }
        template <class T>
        proxy& operator,(T&& val)
        {
            cout << ' ' << val;
            return *this;
        }
    };

public:
    output() : cout(std::cout)
    {
        cout << std::fixed << std::setprecision(15);
    }

    template <class T>
    proxy operator<<(T&& val)
    {
        cout << val;
        return {};
    }
};

int main()
{
    input in;
    output out;

    std::string s, t;
    in >> s, t;
    std::vector<std::vector<std::size_t>> table('z' - 'a' + 1);
    for (std::size_t i = 0; i < s.size(); ++i) {
        table[s[i] - 'a'].push_back(i);
    }

    std::uint64_t i = 0;
    std::uint64_t loop = 0;
    for (auto ch : t) {
        auto& index = table[ch - 'a'];
        if (index.empty()) {
            out << -1;
            return 0;
        }
        auto it = std::lower_bound(index.begin(), index.end(), i);
        if (it == index.end()) {
            it = index.begin();
            ++loop;
        }
        i = *it + 1;
        if (!(i < s.size())) {
            i %= s.size();
            ++loop;
        }
    }
    out << loop * s.size() + i;

    return 0;
}


Measured memory_bytes: 1736
n=int(input())
l=[list(input()) for _ in range(n)]
dic_l={}
cnt=0
ans_lst=[]
for i in range(n):
  l[i].sort()
  l[i]=str(l[i])
  if l[i] not in dic_l:
    dic_l[l[i]]=1
  else:
    dic_l[l[i]]+=1
for j in dic_l.values():
  if j>=2:
    ans_lst.append(j)
    cnt += int(j*(j-1)/2)
print(cnt)

Measured memory_bytes: 29072
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int n = 0;
		for (int i = 1; i <= a; i++) {
			n += i;
		}
		System.out.println(n);
	}

}


Measured memory_bytes: 21844
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define mod 1000000007

string solve() {
	int n;cin>>n;
	string s; cin >> s;
	if(n&1) {
		return "No";
	}

	for(int i=0;i<n/2;++i) {
		if(s[i]!=s[i+n/2]) return "No";
	}

	return "Yes";
}


int main() {
	ios_base::sync_with_stdio(false);

	cout <<  solve();
	return 0;
} 


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

#define ll long long
#define rep(A,B,C) for(A=B;A<C;++A)
#define repd(A,B,C) for(A=(ll)C-1;A>=B;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>
template<typename T>
void mxin(T& a,T b){if(a<b)a = b;}
template<typename T>
void mnin(T& a,T b){if(a>b)a = b;}
using namespace std;

/////////////////////////////////////////////////////
#define MOD 998244353
#define MXN 333

char S[333];
ll N,K;
ll dp[MXN][MXN], odp[MXN][MXN];
ll i, j, k, l;

int main(){
    scanf("%s%lld", S, &K);
    N = strlen(S);
    K = min(N, K);

    dp[0][0] = 1;
    ll pi = N;
    for (i = N - 1; i >= 0;--i)
    {
        if(S[i]=='1')
            continue;
        rep(j,0,MXN){
            rep(k,0,MXN){
                odp[j][k] = dp[j][k];
                dp[j][k] = 0;
            }
        }
        ll a = pi - i;
        pi = i;
        rep(j,0,K+1){
            ll b = 0;
            for(k = j; k >= 0;--k){
                (b += odp[j][k]) %= MOD;
                (dp[j][k] += b) %= MOD;
                if(odp[j][k]==0)
                    continue;
                rep(l,1,a){
                    (dp[j + l][k + l] += odp[j][k]) %= MOD;
                }
            }
        }
        //printf("\n%lld:\n", i);
        /*
        rep(j,0,N+1){
            rep(k,0,j+1){
                printf("%lld ", dp[j][k]);
            }
            printf("\n");
        }*/
    }
    ll ans = 0;
    rep(i,0,K+1){
        rep(j,0,i+1){
            (ans += dp[i][j]) %= MOD;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

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

int main(){
    long long a, b;
    cin >> a >> b;
    map<long long, bool> mp;
    for (int i = 1; (long long)i * i <= a; i++){
        if (a % i == 0){
            mp[i] = true;
            if ((long long)i * i != a) mp[a / i] = true;
        }
    }
    vector<long long> num;
    for (int i = 1; (long long)i * i <= b; i++){
        if (b % i == 0){
            if (mp[i]) num.push_back(i);
            if ((long long)i * i != b) {
                if(mp[b / i]) num.push_back(b / i);
            }
        }
    }
    sort(num.begin(), num.end());
    vector<bool> ans(num.size(), true);
    for (int i = 1; i < num.size(); i++){
        if (!ans[i]) continue;
        for (int j = i + 1; j < num.size(); j++){
            if (num[j] % num[i] == 0) ans[j] = false;
        }
    }
    int cnt = 0;
    for (int i = 0; i < ans.size(); i++) if (ans[i]) cnt++;
    cout << cnt << endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;

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

	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int x = c - a, y = d - b;
	cout << c - y << " " << d + x << " " << a - y << " " << b + x << endl;

}


Measured memory_bytes: 256
#include <cstdio>

using namespace std;

int a[100];

int main() {
	int n, ans = 0, i;
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++) scanf("%d", &a[i]);
	
	for (i = 1; i < n; i++) {
		if (a[i] == a[i - 1]) {
			ans++;
			a[i] = -1;
		}
	}
	
	printf("%d\n", ans);
	
	return 0;
}


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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> h(n);
  rep(i, n) cin >> h[i];
  sort(h.begin(), h.end());
  int mn = h[k - 1] - h[0];
  for (int i = k; i < n; i++) {
    mn = min(mn, h[i] - h[i - k + 1]);
  }
  cout << mn << endl;
  return 0;
}

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

using namespace std;
#define sint(a) scanf("%d",&a)
#define sint2(a,b) scanf("%d %d",&a,&b)
#define sll(a) scanf("%lld",&a)
#define sll2(a,b) scanf("%lld %lld",&a,&b)
#define pb push_back
#define ll long long
const int maxn=2e5+10;
const int mod=1e9+7;
const double pi=-acos(-1);

int a[maxn];
int main()
{
    ll n,k;
    cin>>n>>k;
    ll sum=0;
    int ma=0,m=0;
    for(int i=1; i<=k; i++)
    {
        sint(a[i]);
        if(a[i]-a[i-1]>ma)
            ma=a[i]-a[i-1],m=i;
    }
    sum+=n-a[k]+a[1]-a[0];
    if(n-a[k]+a[1]-a[0]>ma)
        cout<<n-(n-a[k]+a[1]-a[0])<<endl;
    else
        cout<<n-(a[m]-a[m-1])<<endl;
    return 0;
}


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

int main(){
    int n,x;
    while(1) {
        cin >> n >> x;
        if(n==0&&x==0) break;
        int way = 0;
        for (int i = 1; i <= n - 2; i++) {
            for (int j = i + 1; j <= n - 1; j++) {
                for (int k = j + 1; k <= n; k++) {
                    if (i + j + k == x) {
                        way++;
                    }
                }
            }
        }
        cout << way << endl;
    }
    return 0;
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define INF (1ll << 62)
#define pb push_back
#define ii pair<int,int>
#define OK cerr <<"OK"<< endl
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define endl '\n'

typedef tree<
ii,
null_type,
less<ii>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int MOD = (int)1e9 + 7;

int mod(int n) {
    return (n % MOD + MOD) % MOD;
}

int pa(int n) {
    return n*(n + 1) / 2;
}

vector<int> cnt(vector<int> &arr) {

    ordered_set os;
    vector<int> ans(arr.size());
    for(int i = 0; i < arr.size(); i++) {
        ans[i] = os.order_of_key(ii(arr[i], -1));
        os.insert(ii(arr[i], i));
    }

    return ans;
}

signed main () {
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, k;

  cin >> n >> k;


  vector<int> arr(n);

  for(int &x: arr)
    cin >> x;

  vector<int> pref = cnt(arr);
  reverse(arr.begin(), arr.end());
  vector<int> suf = cnt(arr);
  reverse(arr.begin(), arr.end());
  reverse(suf.begin(), suf.end());


  ordered_set os;

  int it = 0;
  int ans = 0;
  for(int i = 0; i < n; i++) {

    ans += mod(mod(mod(suf[i] * mod(pa(k)))) + mod(pref[i] * mod(pa(k - 1))));
    ans = mod(ans);

  }


  cout << ans << endl;

}

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

int main()
{
    long long a,b,c,d,x,y,z,t;
    cin>>a>>b>>c>>d;
    x=a*c;
    y=a*d;
    z=b*c;
    t=b*d;
    cout<<max(x,max(y,max(z,t)));
}

Measured memory_bytes: 3632
//#pragma comment(linker,"/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define sf scanf
#define pf printf
#define cls(a) memset(a,0,sizeof a)
#define _cls(a) memset(a,-1,sizeof a)

using namespace std;
typedef long long LL;

struct Edge_t{
	int to,next,cap,cost;
}edge[50000];
int head[10010],et;
int dis[10010][2];
int vis[10010];
int path[10010];

inline void adde(int u,int v,int _cap,int _cost){
	edge[et].to=v;edge[et].cap=_cap;edge[et].cost=_cost;edge[et].next=head[u];head[u]=et++;
}

inline void Init(){
	_cls(head);et=0;_cls(path);
}

inline int dfs(int u){
	int ret=0,e,v;
	for(e=head[u];e!=-1;e=edge[e].next){
		if(path[v=edge[e].to]==u){
			ret+=edge[e].cost;
			ret+=dfs(v);
		}
	}
	//pf("%d %d\n",u,ret);
	return ret;
}



inline void spfa(int n){
	queue<int >q;
	q.push(1);int i,e,u,v;
	for(i=0,cls(vis);i<=n;++i)
		dis[i][0]=dis[i][1]=INT_MAX;
	dis[1][0]=0;dis[1][1]=0;
	while(!q.empty()){
		u=q.front();q.pop();
		//pf("u=%d\n",u);
		for(e=head[u],vis[u]=0;e!=-1;e=edge[e].next){
			if(dis[v=edge[e].to][0]>dis[u][0]+edge[e].cap){
				dis[v][0]=dis[u][0]+edge[e].cap;
				dis[v][1]=dis[u][1]+edge[e].cost;
				path[v]=u;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
					
				}
			}else if(dis[v][0]==dis[u][0]+edge[e].cap){
				//puts("@@");
				int tmp=dfs(1),pa=path[v];
				path[v]=u;
				if(dfs(1)<tmp){
					dis[v][1]=dis[u][1]+edge[e].cost;
					path[v]=u;
					if(!vis[v]){
						q.push(v);
						vis[v]=1;
					}
				}else path[v]=pa;
			}
		}
	}
}



int main(){
	int n,m;
	int u,v,d,c;
	while(~sf("%d%d",&n,&m),n||m){
		Init();
		while(m--){
			sf("%d%d%d%d",&u,&v,&d,&c);
			adde(u,v,d,c);
			adde(v,u,d,c);
		}
		spfa(n);
		cls(vis);vis[1]=1;
		int ret=0,i;/*
		for(i=1;i<=n;++i)
			pf("%d %d %d\n",path[i],dis[i][0],dis[i][1]);
		puts("");*/
		ret=dfs(1);
		pf("%d\n",ret);
	}
	return 0;
}
/*
5 10
1 2 32 10
1 3 43 43
1 4 12 52
1 5 84 23
2 3 58 42
2 4 86 99
2 5 57 83
3 4 11 32
3 5 75 21
4 5 23 43

5 10
1 5 84 23
1 4 12 52
1 3 43 43
1 2 32 10
2 3 58 42
2 4 86 99
2 5 57 83
3 4 11 32
3 5 75 21
4 5 23 43

*/

Measured memory_bytes: 2052
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<utility>
#include<iomanip>
#include<string>
using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
#define setp(n) fixed<<setprecision(n)
int main(){
    int n;
    cin>>n;
    vector<pair<int, int>> a;
    int b;
    bool f=0;
    rep(i, n){
        cin>>b;
        a.push_back(make_pair(b, i));
    if(b==1)
        f=1;
    }
    if(f==0){
        cout<<-1<<endl;
        return 0;
    }
    int c=1, d=0;
    rep(i, n){
        if(a[i].first!=c)
            d++;
        else
            c++;
    }
    cout<<d<<endl;
    return 0;
}

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

int main() {
	int n;
	cin >> n;
	int score_1 = 0,score_2 = 0;
	while (n--) {
		string card_1,card_2;
		cin >> card_1 >> card_2;
		if (card_1 == card_2) {
			++score_1;
			++score_2;
		} else if (card_1 > card_2) {
			score_1 += 3;
		} else {
			score_2 += 3;
		}
	}
	cout << score_1 << " " << score_2 << endl;
}

Measured memory_bytes: 3136
#include <iostream>
#include <string>
using namespace std;
int main() {
	long long int a, b;
	cin >> a >> b;
	if (a <= 0 && b >= 0) {
		cout << "Zero" << endl;
	}
	if (b < 0) {
		if ((b - a + 1) % 2 == 0) {
			cout << "Positive" << endl;
		}
		else {
			cout << "Negative" << endl;
		}
	}
	if (a > 0) {
		cout << "Positive" << endl;
	}
}

Measured memory_bytes: 256
n=STDIN.gets.to_i
s=STDIN.gets
max=-1000001
min= 1000001
ar=s.split
sum=0
0.upto(n-1){|i| n=ar[i].to_i;
max = n if n > max
min = n if n < min
sum += n
}
puts sprintf("%d %d %d\n",min,max,sum)

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

using namespace std;

int main() {
  int n; cin >> n;
  for (int i = 1; i <= 9; i++) {
    if (n % i == 0 && n / i <= 9) {
      cout << "Yes\n";
      return 0;
    }
  }
  cout << "No\n";
  return 0;
}

Measured memory_bytes: 256
K = int(input())
A, B = (int(x) for x in input().split())
if A == B:
  if A%K == 0:
    print("OK")
  else:
    print("NG")
else:
  for i in range(A, B+1):
    if i%K == 0:
      print("OK")
      quit()
  print("NG")



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

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cerr << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const int maxn = 100010;
const ll inf = -TEN(18);

ll dp[maxn][3];

int main() {
	rep(i, maxn) rep(j, 3) {
		dp[i][j] = inf;
	}

	dp[0][0] = 0;

	int N; cin >> N;
	rep(i, N) {
		bool neg = 0;
		if (i > 0) {
			string s; cin >> s;
			if (s == "-") {
				neg = 1;
			}
		}
		int x; cin >> x;

		ll tmp[3];
		rep(j, 3) tmp[j] = dp[i][j];

		for (int j = 1; j >= 0; --j) { //close
			chmax(tmp[j], tmp[j+1]);
		}

		rep(j, 3) if (tmp[j] != inf) {
			tmp[j] += ((j + neg) % 2 == 1) ? -x : x;
		}

		if (neg) {
			for (int j = 1; j >= 0; --j) { //open
				chmax(tmp[j+1], tmp[j]);
			}
		}

		rep(j, 3) dp[i+1][j] = tmp[j];
	}

	cout << max({dp[N][0], dp[N][1], dp[N][2]}) << endl;

	return 0;
}

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

struct edge{int from, to, cost;};

const int MAX_N = 1e5 + 5, MAX_M = 2e5 + 5;
int N, M, dist[MAX_N], used[MAX_N];
vector<edge> E[MAX_N];

bool bfs(int s){
    queue<int> q;
    dist[s] = 0; q.push(s); used[s] = 1;

    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto it : E[u]){
            if(!used[it.to]){
                dist[it.to] = dist[it.from] + it.cost; used[it.to] = 1;
                q.push(it.to);
            }
            else if(dist[it.from]+it.cost != dist[it.to]) return false;
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> N >> M;
    for(int i=0;i<M;i++){
        edge e; cin >> e.from >> e.to >> e.cost; E[e.from].push_back(e);
        swap(e.from, e.to); e.cost *= -1; E[e.from].push_back(e);
    }
    for(int i=1;i<=N;i++){
        if(!used[i] && !bfs(i)){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 11648
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
    int connected[100010];
    int n, m;
    vector<int> path[100010];

void visit(int position, int group)
{
    connected[position] = group;
    for(int i = 0; i < path[position].size(); i++){
        if(connected[path[position][i]] == -1){
            visit(path[position][i], group);
        }
    }
}

int main() {
    cin >> n >> m;
    int p[100010];
    for(int i = 1; i <= n; i++){
        cin >> p[i];
    }
    for(int i = 0; i <= n; i++){
        connected[i] = -1;
    }
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        path[x].push_back(y);
        path[y].push_back(x);
    }
    for(int i = 1; i <= n; i++){
        if(connected[i] != -1){
            continue;
        }
        visit(i, i);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(connected[i] == connected[p[i]]){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 9472