akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int N, K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i, 0, N) cin >> A[i];
    const int sum = accumulate(all(A), 0);
    vector<int> divisors;
    for (int i = 1; i * i <= sum; ++i)
    {
        if (sum % i != 0) continue;
        divisors.push_back(i);
        if (i * i != sum) divisors.push_back(sum / i);
    }
    sort(all(divisors), greater<int>());
    for (const int divisor : divisors)
    {
        vector<int> rs;
        rep(i, 0, N)
        {
            if (A[i] % divisor == 0) continue;
            rs.push_back(A[i] % divisor);
        }
        if (rs.empty())
        {
            cout << divisor << endl;
            return;
        }
        sort(all(rs));
        const int n = rs.size();
        vector<int> rsums(n + 1, 0);
        rep(i, 0, n) rsums[i + 1] = rsums[i] + rs[i];
        rep(i, 0, n)
        {
            if (rsums[i + 1] == 1LL * (n - i - 1) * divisor - (rsums[n] - rsums[i + 1]))
            {
                if (rsums[i + 1] <= K)
                {
                    cout << divisor << endl;
                    return;
                }
            }
        }
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
  int N;
  cin >> N;
  
  int ans = 0;
  int point = 0;
  
  vector<int>num(N,0);
  for(int i=0;i<N;i++){
    cin >> num[i];
  }
  
  sort(num.begin(),num.end());
  
  while(point < N){
    int c = num[point];
    int f = 0;
    while(point < N && num[point] == c){
      f++;
      point++;
    }
    ans += f % 2;
  }
  
  cout << ans << endl;
  
  return 0;
}

    


Measured memory_bytes: 640
#define DBG 0 //submission 0
#if DBG==1
    #include <algorithm>
    #include <ctime>
    #include <cstdlib>
    #include <string>
    #include <vector>
    #include <iostream>
#else
    #include <bits/stdc++.h>
#endif

using namespace std;

int main(){
    //long long ans = 0,sum = 0;
    //long long N,K; 
    int i,j,k,tmp=0;
    string S;
    cin >> S;
    
    for (i=1;i<4;i++){
        if(S[i]==S[i-1]){
            tmp = 1; 
            break;
        }
    }
    

    cout << (tmp?"Bad":"Good") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 1; i <= n; i++)
#define REP(i, n) for(int i = 0; i < n; i++)
#define MP make_pair
#define FI first
#define SE second
#define VI vector<int>
#define CLR(x) memset(x, 0, sizeof(x))
#define SZ(x) (x.size())
#ifdef QWERTIER
#define err(x) cerr<<x<<endl;
#else
#define err(x)
#endif
typedef long long LL;
typedef pair<int, int> pii;


#define N 200010

#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc (o<<1|1)
struct SegTree{
  pii minv[N<<2];
  void insert(int o, int l, int r, int p, int v) {
    if (l == r) {
      minv[o] = make_pair(v, l);
      return;
    }
    if (p <= mid)
      insert(lc, l, mid, p, v);
    else
      insert(rc, mid+1, r, p, v);
    minv[o] = min(minv[lc], minv[rc]);
  }
  pii query(int o, int l, int r, int L, int R) {
    if (L <= l && r <= R)
      return minv[o];
    if (L > r || R < l)
      return make_pair(1<<30, 0);
    return min(query(lc, l, mid, L, R), query(rc, mid+1, r, L, R));
  }
}t[2];

int n, a[N], pos[N];

struct Node {
  int x, y, l, r, px, py;
  Node(int _x, int _y, int _l, int _r, int _px, int _py) :x(_x), y(_y), l(_l), r(_r), px(_px), py(_py) {
  }
  bool operator<(const Node& rhs) const {
    return x > rhs.x;
  }
};


Node proc(int l, int r) {
  auto x = t[l%2].query(1, 1, n, l, r),
    y = t[r%2].query(1, 1, n, x.second+1, r);
  return Node(x.first, y.first, l, r, x.second, y.second);
}

typedef pair<pii, pii> pp;
int mark[N];
int main() {
#ifdef QWERTIER
  freopen("in.txt", "r", stdin);
#endif
  memset(t, 0x3f, sizeof(t));
  scanf("%d", &n);
  FOR (i, n) {
    scanf("%d", &a[i]);
    pos[a[i]] = i;
    t[i%2].insert(1, 1, n, i, a[i]);
  }
  priority_queue<Node> pq;
  pq.push(proc(1, n));
  while (!pq.empty()) {
    Node t = pq.top();
    pq.pop();
    printf("%d %d ", t.x, t.y);
    if (t.l < t.px-1)
      pq.push(proc(t.l, t.px-1));
    if (t.px+1 < t.py-1)
      pq.push(proc(t.px+1, t.py-1));
    if (t.py+1 < t.r)
      pq.push(proc(t.py+1, t.r));
  }
  return 0;
}


Measured memory_bytes: 16628
#include<iostream>
#include<tuple>
#include<queue>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

enum{Y,X};
enum{COST,SCROLL,I,J};
typedef tuple<int,int> Point;
typedef tuple<int,int,int,int> T;

bool range(int x, int first, int last){return first<=x && x<=last;}
int bitcount(int n){return n?(n&1)+bitcount(n>>1):0;}

int main()
{
  int W, H;
  string line;
  Point start, goal;
  vector<Point> scroll, holl;

  cin>>W>>H;

  vector< vector<int> > field(H, vector<int>(W, 1) );

  for(int i=0; i<H; i++){
    cin>>line;
    for(int j=0; j<W; j++){
      switch(line[j]){
      case 'S':
        start = Point(i,j);
        break;
      case 'G':
        goal = Point(i,j);
        break;
      case 'M':
        scroll.push_back( Point(i,j) );
        break;
      case '#':
        holl.push_back( Point(i,j) );
        for(int dy=-2; dy<=2; dy++){
          for(int dx=-2; dx<=2; dx++){
            int y=i+dy, x=j+dx;
            if(!range(y,0,H-1))continue;
            if(!range(x,0,W-1))continue;
            if(dy==-2 || dy==2 || dx==-2 || dx==2)field[y][x]=max(2,field[y][x]);
            else field[y][x]=3;
          }
        }
        break;
      case '.':
        break;
      default:
        break;
      }
    }
  }

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

  set<T> visited;
  priority_queue<T> q;
  q.push( T( 0, 0, get<Y>(start), get<X>(start) ) );
  while(!q.empty()){
    T now = q.top();
    q.pop();

    if( visited.count( T(0, get<SCROLL>(now), get<I>(now), get<J>(now)) ) )continue;
    visited.insert( T(0, get<SCROLL>(now), get<I>(now), get<J>(now)) );

    //    printf("cost=%d; scroll=%d; point=(%d, %d);   %d\n",get<COST>(now),get<SCROLL>(now),get<I>(now),get<J>(now),q.size());

    if(get<I>(now)==get<Y>(goal) && get<J>(now)==get<X>(goal)){
      if( bitcount( get<SCROLL>(now) ) == scroll.size() ){
        ans=-get<COST>(now);
        break;
      }
    }
    for(int j=0; j<scroll.size(); j++){
      if(get<I>(now)==get<Y>(scroll[j]) && get<J>(now)==get<X>(scroll[j])){
        if( (get<SCROLL>(now)>>j)&1 ){
          break;
        }else{
          get<SCROLL>(now) ^= (1<<j);
        }
      }
    }

    bool ok=true;
    for(int j=0; j<holl.size(); j++){
      if(get<I>(now)==get<Y>(holl[j]) && get<J>(now)==get<X>(holl[j]))ok=false;
    }
    if(!ok)continue;

    for(int i=0; i<4; i++){
      int y=get<I>(now)+dy[i], x=get<J>(now)+dx[i];
      if(!range(y,0,H-1))continue;
      if(!range(x,0,W-1))continue;
      q.push( T(get<COST>(now)-field[get<I>(now)][get<J>(now)], get<SCROLL>(now), y, x) );
    }
  }

  //  for(int i=0;i<H;i++,cout<<endl)for(int j=0;j<W;j++)cout<<" "<<field[i][j];
  cout<<ans<<endl;
}

Measured memory_bytes: 19620
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K;
  int S;
  cin >> K >> S;
  int count=0;
  for(int x=0;x<=K;x++){
    for(int y=0;y<=K;y++){
        if(0<=S-x-y && S-x-y<=K){
          count++;
      }
    }
  }
  cout << count << endl;
}
          


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int judge(int m,int n,char s[])
{
    m--;n--;
    int i,j;
    for(i=m,j=n;j>i;i++,j--)
        if(s[i]!=s[j]) return 0;
    return 1;

}

int main()
{
    char s[100];
    scanf("%s",s);
    int m=1,n=strlen(s);
    if(judge(m,n,s)*judge(m,(n-1)/2,s)*judge((n+3)/2,n,s)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

   return 0;
}


Measured memory_bytes: 256
#ifdef _DEBUG
#include ".vscode/debug_print.hpp"
#else
#define debug(...)
#endif
#include <bits/stdc++.h>

using ll = long long;
using ld = long double;
using namespace std;
constexpr int INF32       = 1050000000;
constexpr long long INF64 = 4000000000000000000;
constexpr int MOD7        = 1000000007;
constexpr int MOD53       = 998244353;
constexpr long double PI  = 3.14159265358979323846;
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;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
void scan() {}
template <class H, class... T> void scan(H &&head, T &&... args) {
    std::cin >> head;
    scan(std::forward<T>(args)...);
}
template <class T> void scan(std::vector<T> &v) {
    for (auto &&i : v) {
        scan(i);
    }
}

void vprint() { std::cout << '\n'; }
template <class H, class... T> void vprint(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << '\n';
    vprint(std::forward<T>(args)...);
}
template <class T> void vprint(std::vector<T> &v) {
    for (auto &&i : v) {
        std::cout << i << '\n';
    }
}

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

    ll N, K;
    scan(N, K);

    ll div = N / K;
    ll ans = min(abs(N - div * K), abs(N - (div + 1) * K));
    print(ans);

    return 0;
}

Measured memory_bytes: 3596
/**
  @date Time-stamp: <2019-05-26 21:27:28 tagashira>
  @file b.cpp
  @title B - Guidebook
  @brief https://atcoder.jp/contests/abc128/tasks/abc128_b
**/

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <sstream> // std::ostringstream
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef tuple<int, string, int> T;
bool tupleCompare(const T& first, const T& second) {
  if (std::get<1>(first) != std::get<1>(second)) return std::get<1>(first) < std::get<1>(second);
  return std::get<2>(first) > std::get<2>(second);
}

int main(int argc, char* argv[]) {
  uint N;
  cin >> N;

  vector<tuple<int, string, int>> data;

  string tmpS;
  int P;
  for (uint i = 0; i < N; i++) {
    cin >> tmpS >> P;
    data.push_back(make_tuple(i+1, tmpS, P));
  }

  sort(data.begin(), data.end(), tupleCompare);

  string prev = "";
  for (uint i = 0; i < N; i++) {
    cout << get<0>(data[i]) << endl;
  }

  return 0;
}


Measured memory_bytes: 256
MOD = int(1e9) + 7

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    buf = input()
    buflist = buf.split()
    S = list(map(int, buflist))
    buf = input()
    buflist = buf.split()
    T = list(map(int, buflist))
    dp = []
    for i in range(N+1):
        dp.append([])
        for j in range(M+1):
            dp[i].append(1)
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]) % MOD
            else:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j]) % MOD
    print(dp[N][M])

if __name__ == '__main__':
    main()


Measured memory_bytes: 73948
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int A, B;

  std::cin >> A >> B;

  std::cout << (A <= 8 && B <= 8 ? "Yay!" : ":(") << std::endl;

  return 0;
}


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

int main()
{
    int N;
    cin>>N;
    vector<int> S(1<<N);
    for (int &s: S)
        cin>>s;

    sort(S.begin(), S.end());
    reverse(S.begin(), S.end());
    vector<int> U(1<<N, -1);
    U[0] = 0;
    for (int i=1; i<=N; i++)
    {
        int p = 0;
        for (int j=0; j<1<<N; j++)
            if (0<=U[j] && U[j]<i)
            {
                while (p<1<<N && (U[p]!=-1 || S[p]>=S[j]))
                    p++;
                if (p<1<<N)
                    U[p] = i;
            }
    }
    bool ans = true;
    for (int u: U)
        if (u==-1)
            ans = false;
    cout<<(ans ? "Yes" : "No")<<endl;
}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,d,c=0;
  cin>>n>>d;
  while(n--)
  {
    ll x,y;
    cin>>x>>y;
    if(sqrt((x*x)+(y*y))<=d)
      c++;
  }
  cout<<c;
}


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

constexpr int INF = 1e9;

int solve (int n) {
	int ans = -INF, sum = 0;
	for (int i = 0; i < n; i++) {
		int e; cin >> e;
		sum = max(sum + e, e);
		ans = max(ans, sum);
	}
	return ans;
}

int main() {
	int n;
	while (true) {
		cin >> n;
		if (n > 0) cout << solve(n) << '\n';
		else break;
	}
	return 0;
}


Measured memory_bytes: 3064
#include <iostream>
#include <string>
using namespace std;
 
int main() {
  int N;
  string S;
  cin >> N;
  cin >> S;
  int turn_e[N];
  int turn_w[N];
  int w;
  int e;
  int result=10000000;
  turn_e[0]=0;
  turn_w[N-1]=0;
  for(int i = 1; i < N; ++i) {
    w=0;
    e=0;
    if(S[i-1]=='W'){
      ++w;
    }
    if(S[N-i]=='E'){
      ++e;
    }
    turn_e[i] = turn_e[i-1] + w;
    turn_w[N-1-i] = turn_w[N-i] + e;
  }
  for(int i = 1; i <= N ; ++i) {
    result = min(result, (turn_e[i-1] + turn_w[i-1]));
  }
  cout << result << "\n";
  return 0;
}

  

Measured memory_bytes: 2948
#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include<vector>
#include <sstream>
#include <stdio.h>
#include <valarray>
#include <iomanip>
using namespace std;
vector<int> Data;

int main(void)
{
	int a, b, c;
	cin >> b >> c >> a;
	cout << a <<" "<< b << " " << c << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <tuple>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for (int i = (int)(k); i <(int)(n); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rREP(i,k,n) for (int i = (int)(n)-1; i >= k; i--)

int main(){
    string s;
    cin >> s;
    int lc[500100]={};
    int rc[500100]={};
    int cn = 0;
    rep(i,s.size()){
        lc[i] = cn;
        if(s[i]=='<') cn++;
        else cn = 0;
    }
    lc[s.size()]=cn;
    cn = 0;
    rrep(i, s.size())
    {
        rc[i+1] = cn;
        if (s[i] == '>')
            cn++;
        else
            cn = 0;
    }
    rc[0] = cn;
    ll sn = 0;
    rep(i,s.size()+1){
        sn += max(lc[i],rc[i]);
    }
    cout << sn << endl;
    return 0;
}


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

int main() {

    //
    ll N, X, Y;
    cin >> N >> X >> Y;

    //
    vector<ll> k(N-1,0);
    // k[0] = N;

    //
    for (ll i=1; i<=N-1; i++) {
        for (ll j=i+1; j<=N; j++) {

            if (i<X and j<=X) {
                k[j-i-1]++;
            }

            else if (Y<=i and Y<j) {
                k[j-i-1]++;
            }

            else if (i<=X and Y<=j) {
                k[(j-Y)+(X-i)]++;
            }

            else {
                ll a = min(j-i,abs(Y-j)+abs(X-i)+1);
                k[a-1]++;
            }
            /*
            else if (i<=X and X<j and j<Y) {
                ll a = min(j-i,(Y-j)+(X-i)+1);
                k[a-1]++;
            }

            else if (X<=i and i<Y and X<j and j<=Y) {
                ll a = min(j-i,(Y-j)+(i-X)+1);
                k[a-1]++;
            }

            else if (X<i and i<Y and Y<=j) {
                ll a = min(j-i,(j-Y)+(i-X)+1);
                k[a-1]++;
            }
            */
        }
    }

    for (int i=0; i<N-1; i++) {
        cout << k[i] << endl;
    }
}

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

using std::cin;
using std::cout;



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

  int N;
  cin >> N;

  std::vector<int> A(N);
  std::vector<int> B(N);

  for (auto& ai : A)
  {
    cin >> ai;
  }
  for (auto& bi : B)
  {
    cin >> bi;
  }

  long long need = 0;
  int res = 0;
  std::vector<int> extra; extra.reserve(N);
  for (int i = 0; i < N; ++i)
  {
    if (A[i] < B[i])
    {
      need += B[i] - A[i];
      ++res;
    }
    else
    {
      extra.push_back(A[i] - B[i]);
    }
  }

  std::sort(extra.begin(), extra.end());
  int ex = extra.size() - 1;
  while (need > 0 && ex >= 0)
  {
    need -= extra[ex];
    --ex;
    ++res;
  }

  if (need > 0) res = -1;

  cout << res <<  "\n";

  return 0;
}


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

using namespace std;

int main()
{
    int num[5] = {};

    for (int i = 0; i < 3; i++) {
        int a, b;

        cin >> a >> b;
        num[a]++;
        num[b]++;
    }

    for (int i = 1; i < 5; i++) {
        if (num[i] == 3) {
            cout << "NO" << endl;
            return (0);
        }
    }
    cout << "YES" << endl;
}


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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
#define MOD 1000000007

template<int mod>
struct ModInt{
	int x;
	ModInt():x(0){}
	ModInt(long long y):x(y>=0?y%mod:(mod-(-y)%mod)%mod){}
	ModInt &operator+=(const ModInt &p){
		if((x+=p.x)>=mod)x-=mod;
		return *this;
	}
	ModInt &operator-=(const ModInt &p){
		if((x+=mod-p.x)>=mod)x-=mod;
		return *this;
	}
	ModInt &operator*=(const ModInt &p){
		x=(int)(1LL*x*p.x%mod);
		return *this;
	}
	ModInt &operator/=(const ModInt &p){
		*this*=p.inverse();
		return *this;
	}
	ModInt &operator^=(long long p){
		ModInt res = 1;
		for (; p; p >>= 1) {
			if (p & 1) res *= *this;
			*this *= *this;
		}
		return *this = res;
	}
	ModInt operator-()const{return ModInt(-x);}
	ModInt operator+(const ModInt &p)const{return ModInt(*this)+=p;}
	ModInt operator-(const ModInt &p)const{return ModInt(*this)-=p;}
	ModInt operator*(const ModInt &p)const{return ModInt(*this)*=p;}
	ModInt operator/(const ModInt &p)const{return ModInt(*this)/=p;}
	ModInt operator^(long long p)const{return ModInt(*this)^=p;}
	bool operator==(const ModInt &p)const{return x==p.x;}
	bool operator!=(const ModInt &p)const{return x!=p.x;}
	explicit operator int() const { return x; }						   // added by QCFium
	ModInt operator=(const int p) {x = p; return ModInt(*this);} // added by QCFium
	ModInt inverse()const{
		int a=x,b=mod,u=1,v=0,t;
		while(b>0){
			t=a/b;
			a-=t*b;
			std::swap(a,b);
			u-=t*v;
			std::swap(u,v);
		}
		return ModInt(u);
	}
	friend std::ostream &operator<<(std::ostream &os,const ModInt<mod> &p){
		return os<<p.x;
	}
	friend std::istream &operator>>(std::istream &is,ModInt<mod> &a){
		long long x;
		is>>x;
		a=ModInt<mod>(x);
		return (is);
	}
};
typedef ModInt<MOD> mint;

struct MComb {
	std::vector<mint> fact;
	std::vector<mint> inversed;
	MComb(int n) { // O(n+log(mod))
		fact = std::vector<mint>(n+1,1);
		for (int i = 1; i <= n; i++) fact[i] = fact[i-1]*mint(i);
		inversed = std::vector<mint>(n+1);
		inversed[n] = fact[n] ^ (MOD-2);
		for (int i = n - 1; i >= 0; i--) inversed[i]=inversed[i+1]*mint(i+1);
	}
	mint ncr(int n, int r) {
		return (fact[n] * inversed[r] * inversed[n-r]);
	}
	mint npr(int n, int r) {
		return (fact[n] * inversed[n-r]);
	}
	mint nhr(int n, int r) {
		assert(n+r-1 < (int)fact.size());
		return ncr(n+r-1, r);
	}
};

MComb com(2000001);
mint rect(int h, int w) {
	mint res = 0;
	for (int i = 0; i < h; i++) res += com.ncr(i + w - 1, i);
	for (int i = 1; i < w; i++) res += com.ncr(i + h - 1, i);
	return res;
}

int main() {
	int x0 = ri(), y0 = ri();
	int x1 = ri() + 1, y1 = ri() + 1;
	mint res = rect(x1, y1) - rect(x0, y1) - rect(x1, y0) + rect(x0, y0);
	std::cout << res << std::endl;
  	return 0;
}


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

int main() {
    size_t K;
    std::string S;
    std::cin >> K >> S;

    if (S.size() <= K) {
        std::cout << S << std::endl;
    } else {
        std::cout << S.substr(0, K) << "..." << std::endl;
    }

    return 0;
}


Measured memory_bytes: 3600
A = gets.to_i
B = gets.to_i
C = gets.to_i
X = gets.to_i
count = 0

(0..A).each do |g_h|
  coin_500 = g_h * 500
  (0..B).each do |h|
    coin_100 = h * 100
    (0..C).each do |g_j|
      coin_50 = g_j * 50
      if coin_500 + coin_100 + coin_50 == X
        count += 1
      end
    end
  end
end

p count

Measured memory_bytes: 14272
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <utility>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) loop(i,0,b)
#define each(e,c) for(auto&e:c)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#ifdef DEBUG
#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<(DUMP(),__VA_ARGS__).str()<<" ["<<__LINE__<<"]"<<endl)
struct DUMP:ostringstream{template<class T>DUMP &operator,(const T&t){if(this->tellp())*this<<", ";*this<<t;return *this;}};
#else
#define dump(...)
#endif
template<class T> ostream& operator<<(ostream& os, vector<T> const& v){
    rep(i,v.size()) os << v[i] << (i+1==v.size()?"":" ");
    return os;
}

#include <deque>

int main(){
    int n; cin >> n;
    rep(x,n){
        string op, s_; cin >> op >> s_;
        reverse(all(op));
        deque<char> s(all(s_));
        for(char c : op){
            if(c == 'C'){
                s.pb(s.front());
                s.pop_front();
            } else if(c == 'J'){
                s.push_front(s.back());
                s.pop_back();
            } else if(c == 'E'){
                rep(i,s.size()/2){
                    swap(s[i], s[i+(s.size()+1)/2]);
                }
                // cout << string(all(s)) << endl;
                // while(1);
            } else if(c == 'A'){
                reverse(all(s));
            } else if(c == 'M'){
                for(char & d : s){
                    if(isdigit(d)){
                        d++;
                        if(!isdigit(d)) d='0';
                    }
                }
                // cout << string(all(s)) << endl;
                // while(1);
            } else if(c == 'P'){
                for(char & d : s){
                    if(isdigit(d)){
                        d--;
                        if(!isdigit(d)) d = '9';
                    }
                }
                // cout << string(all(s)) << endl;
                // while(1);
            }
        }
        for(char c : s){
            cout << c;
        }
        cout << endl;
    }
}

Measured memory_bytes: 1216
N,D=map(int,input().split())
X=[]
Y=[]
for i in range(N):
    x,y=map(int,input().split())
    X.append(x)
    Y.append(y)
ans=0    
for i in range(N):
    if X[i]**2+Y[i]**2 <= D**2:
        ans += 1

print(ans)


Measured memory_bytes: 24800
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long k = sc.nextInt();
        long[] a = new long[n + 1];
        for (int i = 0; i < n; i++) {
            a[i + 1] = a[i] + sc.nextLong();
        }
        long[] b = new long[m + 1];
        for (int i = 0; i < m; i++) {
            b[i + 1] = b[i] + sc.nextLong();
        }

        int best = m;
        int res = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > k) {
                break;
            }
            while (b[best] > k - a[i]) {
                best--;
            }
            res = Math.max(res, i + best);
        }
        
        System.out.println(res);

        sc.close();
    }
}

Measured memory_bytes: 63528
#include <iostream>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <limits>
#include <vector>
#define ll long long
#define rep(i,n) for(int i = 0;i < n;i++)
#define pb push_back
#define mp make_pair

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    int tmp = 0;
    rep(i,n){
        cin >> tmp;
        tmp--;
        a[i] = tmp;
    }
    int ans = 0;
    for(int i = 0;i < n;i++){
        if(a[a[i]] == i){
            ans++;
        }
    }
    cout << ans/2 << endl;
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 100100
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,m;
int a[MAX<<1],b[MAX<<1];
bool check(int mid)
{
	for(int i=1;i<=m;++i)b[i]=a[i]>=mid;
	for(int i=0;i<n;++i)
	{
		if(b[n-i]==b[n-i-1])return b[n-i];
		if(b[n+i]==b[n+i+1])return b[n+i];
	}
	return b[1];
}
int main()
{
	n=read();m=n+n-1;
	for(int i=1;i<=m;++i)a[i]=read();
	int l=1,r=m,ret;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))ret=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ret);
	return 0;
}


Measured memory_bytes: 1920
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	// 標準入力読み取り
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	//1行
	str := scanner.Text()

	t := strings.Split(str, " ")
	a, _ := strconv.Atoi(t[0])
	b, _ := strconv.Atoi(t[1])
	c, _ := strconv.Atoi(t[2])

	judge := make([]int, 10)
	judge[a]++
	judge[b]++
	judge[c]++
	for _, j := range judge {
		if j == 2 {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")
	return

}


Measured memory_bytes: 640
///  author:Kissheart  ///
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#define INF 0x3f3f3f3f
#define FAST_IO ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e5+10;
const int mod=1e9+7;
typedef long long ll;
using namespace std;
#define gcd(a,b) __gcd(a,b)
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
inline ll inv1(ll b){return qpow(b,mod-2);}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}
//freopen( "in.txt" , "r" , stdin );
//freopen( "data.txt" , "w" , stdout );
int main()
{
    int a[5];
    for(int i=1;i<=4;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+4);
    if(a[1]==1 && a[2]==4 && a[3]==7 && a[4]==9)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}


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

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

  int a, b, c, d;
  a = N / 1000;
  b = (N - a * 1000) / 100;
  c = (N - a * 1000 - b * 100) / 10;
  d = N % 10;
  if (b == c) {
    if (a == b || c == d) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define bug(x) cout << #x << " = " << x << endl
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define reset(x) memset(x,0,sizeof(x))
#define up(i,l,r) for(int i=l;i<=r;i++)
#define down(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
string s,Ti;
int main(){
    ios_base::sync_with_stdio(0);
    cin>>s;
    if(s.size()<4) cout<<"No\n";
    else{
        Ti=s.substr(0,4);
        if(Ti=="YAKI") cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n,i,j,m,a=0;
  while(1){
    a=0;
    cin >> n;
    if(n==0)break;
    m=1000-n;
    while(m>0){
      if(m%500==0){
	a++;
	m=m-500;
      }
      else if(m%100==0){
	a++;
	m=m-100;
      }
      else if(m%50==0){
	a++;
	m=m-50;
      }
      else if(m%10==0){
	a++;
	m=m-10;
      }
      else if(m%5==0){
	a++;
	m=m-5;
      }
      else if(m%1==0){
	a++;
	m=m-1;
      }
    }
    cout << a << endl;
  }
}

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

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a,b,c;
  string s,t;
  cin >>a;
  cout <<a*a;
}

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

int main()
{
    int N;
    cin >> N;
    vector<string> s(N);
    for (int i = 0; i < N; i++)
    {
        cin >> s.at(i);
    }

    int xabx = 0, bxxa = 0, xxxa = 0, bxxx = 0;
    for (int i = 0; i < N; i++)
    {
        string si = s.at(i);
        for (int j = 0; j < si.size() - 1; j++)
        {
            if (si.at(j) == 'A' && si.at(j + 1) == 'B')
            {
                xabx++;
            }
        }
        if (si.at(si.size() - 1) == 'A' && si.at(0) == 'B')
        {
            bxxa++;
        }
        else if (si.at(si.size() - 1) == 'A')
        {
            xxxa++;
        }
        else if (si.at(0) == 'B')
        {
            bxxx++;
        }
    }
    int res;
    if (xxxa > 0 || bxxx > 0)
    {
        res = xabx + min(xxxa + bxxa, bxxx + bxxa);
    }
    else if (bxxa > 0)
    {
        res = xabx + bxxa - 1;
    }
    else
    {
        res = xabx;
    }
    cout << res << endl;
}

Measured memory_bytes: 768
def test():
    w,h,x,y = map(int,input().split())
    if x == w/2 and y == h/2:
        print("{:.7f}".format(w*h*(1/2)),"1")
    else:
        print("{:.7f}".format(max((h/2)*w,(w/2)*h)),"0")


if __name__ == "__main__":
    test()


Measured memory_bytes: 2940
/* "It's okay if you hate me. I hate me too." */

#include <bits/stdc++.h>

using namespace std;

char s[202];

int main() {
	scanf(" %s", s);
	int n = strlen(s);
	for (int i = (n-1)/2; i > 0; --i) {
		bool isTrue = true;
		for (int j = 0; j < i; ++j)
			if (s[j] != s[j+i]) {
				isTrue = false;
				break;
			}
		if (isTrue) {
			printf("%d\n", i*2);
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    solve(java.util.Scanner(System.`in`))
}

fun solve(sc: java.util.Scanner) {
    val N = sc.nextInt()
    val M = sc.nextInt()

    println(M * (M - 1) / 2 + N * (N - 1) / 2)
}


Measured memory_bytes: 31520
#include<iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[n];
    int num=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        num^=a[i];
    }
    
    for(int i=0;i<n;i++)
        cout<<(num^a[i])<<" ";
    
    return 0;
}

Measured memory_bytes: 4384
#include "bits/stdc++.h"
using namespace std;
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define pb push_back
#define nl cout<<"\n"
#define endl "\n"
#define ll long long
#define ld long double
#define all(c) (c).begin(),(c).end()
#define trav(a,x) for(auto a = x.begin() ; a != x.end() ; a++)
#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define f first
#define s second

inline ll max(ll a,ll b) {return ((a>b)?a:b);}
inline ll min(ll a,ll b) {return ((a>b)?b:a);}
inline ll gcd(ll a ,ll b) {if(b==0) return a; a%=b;return gcd(b,a);}
ll power(ll x, ll y){if(y == 0) return 1; ll a = power(x,y/2);if (y % 2 == 0) return a * a; else return x * a * a; }
ll powermod(ll x, ll ex , ll md) {ll ans = 1ll;while (ex > 0) {if (ex & 1ll) ans = (ans * x) % md; ex >>= 1ll;x = (x * x) % md;}return ans;}

const ll inf = 1e18 + 9;
const ll mod = 1e9 + 7;
const ld PI = acos(-1);
const ld eps = 1e-9;

const ll N = 1e5 + 1;

void solve(){
    ll n;
    cin >> n;
    cout << n + n*n + n*n*n << endl;
}
int main(){
    IOS;
    cout << fixed << setprecision(20);
    ll NTC=1;
    // cin>>NTC;
    ll PTC=0;
    while(PTC++<NTC){
        // cout<<"Case #"<<PTC<<":"<<' ';
        solve();
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}


Measured memory_bytes: 3796
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

x = 0
for i in range(n):
    for j in range(i+1, n):
        if a[i] > a[j]:
            x += 1

y = 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            y += 1

mod = 10**9 + 7
ans1 = (x*k) % mod
ans2 = ((k*(k-1)*y) // 2) % mod
print((ans1 + ans2) % mod)




Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stdio.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
#include <fstream>
#include <functional>
#include <list>
#include <iomanip>
#include <cctype>
#include <math.h>

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

using namespace std;


int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int a,b,c,d,e;
    cin >> a>> b;
    
    c = a+b;
    d = a-b;
    e = a*b;
    
    cout << max({c,d,e}) << endl;
 
    
}
    




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n; cin>>n; vector<int> v(n+1,0);
  for(int i=1;i<=n;i++){
      for(int j=i;j<=n;j+=i){
          v[j]++;
      }
  }
  long long int ans=0;
  for(int i=0;i<=n;i++) ans+=(long long)i*v[i];
  cout<<ans;
  return 0;
}
  
  
  


Measured memory_bytes: 42280
from math import factorial
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


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


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


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


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


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = False
show_flg = True


def main():
    N = I()
    X = LI()
    mi = 10**19

    for p in range(1, 101):
        temp = 0
        for i in range(N):
            temp += (X[i] - p) ** 2
        mi = min(temp, mi)

    print(mi)


if __name__ == '__main__':
    main()


Measured memory_bytes: 39404
using System;
using System.Collections.Generic;
using System.Text;

namespace AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            var inputLine = Console.In.ReadLine();
            var inputChars = inputLine.ToCharArray();

            var outputChars = new char[inputChars.Length];

            for (int i = 0; i < inputChars.Length; ++i)
            {
                var c = inputChars[i];
                if (char.IsUpper(c))
                {
                    c = char.ToLower(c);
                }
                else if (char.IsLower(c))
                {
                    c = char.ToUpper(c);
                }
                outputChars[i] = c;
            }

            var outputLine = string.Join("", outputChars);
            Console.Out.WriteLine(outputLine);
        }
    }
}



Measured memory_bytes: 15900
#include <bits/stdc++.h>
#define log(x) cout<<x<<endl
#define pb push_back
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;

int gcd(lint x, lint y){
  return y==0 ? x:gcd(y,x % y);
}

int digsum(int n) {
  int res = 0;
  while(n > 0) {
    res += n%10;
    n /= 10;
  }
  return res;
}

int dignum(int n) {
  int res = 0;
  while(n > 0) {
    res++;
    n /= 10;
  }
  return res;
}

int stringcount(string s, char c) {
  return count(s.cbegin(), s.cend(), c);
}

int lcm(lint x, lint y){
  return x/ gcd(x, y) * y;
}

int combi(int n, int r){
  int num = 1;
  for(int i = 1; i <= r; i++){
    num = num * (n - i + 1) / i;
  }
  return num;
}

int main(){
  int n;
  cin>>n;
  vector<pair<int,int>> l;
  rep(i,n){
    pair<int,int> e;
    cin>>e.first;
    e.second=i;
    l.pb(e);
  }
  sort(all(l));
  reverse(all(l));
  rep(i,n){
    int num=0;
    if(l[num].second!=i) cout<<l[num].first<<endl;
    else cout<<l[num+1].first<<endl;
  }

}

Measured memory_bytes: 3312
n=int(input())
p=input().split()
p=[int(s) for s in p]

#print(n,p)
count=0

for i in range(1,len(p)-1):
    if p[i]>=p[i-1] or p[i]>=p[i+1]:
        if p[i]<=p[i-1] or p[i]<=p[i+1]:
            count+=1

print(count)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int ,int>;
const int INF = 1e9;
const int MOD = 1e9+7;

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

    int k, a, b; cin >> k >> a >> b;
    FOR(i, a, b+1) {
        if (i%k==0) {
            puts("OK");
            return 0;
        }
    }
    puts("NG");
}

Measured memory_bytes: 3656
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<time.h>
#include<ctype.h>
#include<limits.h>
#define eps 1e-9
#define clear(vis,i) memset(vis,i,sizeof(vis))
#define INF (ll)1e18;
#define MOD (1e9+7)
#define ll long long int 
#define N 250000
char in[N];
char in1[N];
char gen[N];
int valid(char *q,char *s){
   int cnt=0;
   while(*q && *s){
      if(*q != *s)
         return 0;
      q++;
      s++;
      cnt++;
   }
   return cnt;
}
int main(){
   int a,b,c;
   scanf("%d",&a);
   getchar();
   gets(in);
   gets(in1);
   int len = a;
   int max=0;
   for(int w=0;w<a;w++){
     if(valid(in+w,in1) > max)
        max=valid(in+w,in1);
   }
   printf("%d",len + a-max);
}

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

constexpr int INF = 1e9;

int main() {
    int n, k;
    while(cin >> n >> k, n) {
        vector<vector<int>> d(n, vector<int>(n, INF));
        for(int i=0; i<n; ++i) {
            d[i][i] = 0;
        }
        for(int i=0; i<k; ++i) {
            int a;
            cin >> a;
            if(a == 0) {
                int b, c;
                cin >> b >> c;
                b--; c--;
                cout << (d[b][c] == INF ? -1 : d[b][c]) << endl;
            } else {
                int b, c, e;
                cin >> b >> c >> e;
                b--; c--;
                if(d[b][c] <= e) {
                    continue;
                }
                for(int j=0; j<n; ++j) {
                    for(int l=0; l<n; ++l) {
                        d[j][l] = min(d[j][l], min(d[j][b] + d[c][l], d[j][c] + d[b][l]) + e);
                    }
                }
            }
        }
    }
}


Measured memory_bytes: 3008
#pragma GCC optimize("O2") 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x"=" << x << endl;
typedef long long LL;

int main(){
//	freopen("in.txt","r",stdin);    
	ios::sync_with_stdio(0); cin.tie(0);
	string s;
	cin >> s;
	bool ok = false;
	for(int i = 1; i < 4; ++i) {
		if(s[i] == s[i-1]) {
			ok = true;
			break;
		}
	}
	cout << (ok ? "Bad" : "Good") << endl;
	return 0;
}

Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double EPS = 1e-9;
const double INF = 2147483647;
#define rep(i, n) REP(i, 0, n)
#define rep2(i, n) REP(i, 1, n+1)
#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rrep(i, n) RREP(i, 0, n)
#define RREP(i, x, n) for(int i = (int)(n) - 1 - (int)(x); i >= 0; i--)

void printv(vector<int> v) {
    for(auto it = v.begin(); it != v.end(); it++){
        cout << *it << ",";
    }
    cout << endl;
}

int main() {
    ll A,B,N;
    cin>>A>>B>>N;
    if (N<=B-1) cout<<floor(A*N/B);
    else cout<<floor(A*(B-1)/B);
}

Measured memory_bytes: 3756
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class TaskA {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int h = in.nextInt();
            int a = in.nextInt();
            int ans = (h + a - 1) / a;
            out.println(ans);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 21460
n = int(input())
ans = list(input())
for i in range(n - 1):
    t = list(input())
    j = 0
    while j < len(ans):
        k = 0
        while k < len(t):
            if ans[j] == t[k]:
                del t[k]
                break
            else:
                k += 1
        else:
            del ans[j]
            j -= 1
        j += 1
ans.sort()
print("".join(ans))


Measured memory_bytes: 3060
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<string> maze;
int row,col;
#define ll long 
#define mod 1000000007
vector<vector<int> > dp;
ll solve(int x,int y){
    
    if(x==row-1 and y == col-1){
        return 1;
    }
    
    if(dp[x][y]!=-1) return dp[x][y]%mod;
    
    ll ans = 0;
    
    if(x+1<row and maze[x+1][y]!='#'){
        ans = solve(x+1,y)%mod;
    }
    
    if(y+1<col and maze[x][y+1]!='#'){
        ans = (ans+solve(x,y+1))%mod;
    }
    
    return dp[x][y] = ans%mod;
    
}

int main() {
	
	cin>>row>>col;
	maze.resize(row);
	dp.resize(row, vector<int> (col,-1));
	for(int i=0;i<row;i++){
	    cin>>maze[i];
	}
	ll ans = solve(0,0);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 5376
#include <iostream>
#include <cstdio>
using namespace std;
 
int main(){
    int t;
    while(cin >> t && t){
        int n;
        cin >> n;
        int s = 0;
        for(int i = 0 ; i < n; i++){
            int a,b;
            cin >> a >> b;
            s += b-a;
        }
        if( s >= t ){
            cout << "OK" << endl;
        }else{
            cout << t - s << endl;
        }
    }
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define P pair<ll,ll>
#define ALL(a) (a).begin(),(a).end()
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll k;cin>>k;
  queue<ll> q;rep(i,9) q.push(i+1);
  for(ll cnt=1;cnt<k;++cnt) {
    ll v=q.front(),w=v%10,x=v*10;q.pop();
    if(w!=0) q.push(x+w-1);
    q.push(x+w);
    if(w!=9) q.push(x+w+1);
  }
  print(q.front());
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include<math.h>
using namespace std;

int main()
{
    int a=0,b=0,c=0;
    cin >> a;
    cin >> b;
    cin >> c;
    if((a<=b) && (a<=c) && (b<=c)){
        cout << a << ' ' << b << ' ' << c << endl;//abc
    }
    else if((a<=b) && (a<=c) && (c<=b)){
        cout << a << ' ' << c << ' ' << b << endl;//acb
    }
    else if((b<=a) && (b<=c) && (a<=c)){
        cout << b<< ' '  << a << ' ' << c << endl;//bac
    }
    else if((b<=a) && (b<=c) && (c<=a)){
        cout << b << ' ' << c << ' ' << a << endl;//bca
    }
    else if((c<=a) && (c<=b) && (a<=b)){
        cout << c << ' ' << a << ' ' << b << endl;//cab
    }
    else {
        cout << c << ' ' << b << ' ' << a << endl;//cba
    }

}

Measured memory_bytes: 1160
import re

# Input
words = list(input().split(' '))

# Loops
new = []
for word in words:
    new_word = ''
    for ch in word:
        if re.match('[a-z]', ch):
            new_word = new_word + ch.upper()
        elif re.match('[A-Z]', ch):
            new_word = new_word + ch.lower()
        else:
            new_word = new_word + ch
    new.append(new_word)

# Output
for i in range(len(new)-1):
    print(new[i], end=' ')
print(new[-1])



Measured memory_bytes: 6552