akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

int n, a[202000], ans;

stack<int>w, c, e;

bool ok(int aim){
    w=c=e;    
    for (int i=2;i<=n;++i){
        if (a[i]>a[i-1]) continue;
        while (w.size()&&w.top()>a[i]) w.pop(), c.pop();
        int p=a[i];
        while (w.size()&&w.top()==p&&c.top()==aim) w.pop(), c.pop(), --p;
        if (p==0) return 0;
        if (w.size()&&w.top()==p) c.top()++;
        else {
            if (aim==1) return 0;
            w.push(p), c.push(2);
        }
    }
    return 1;
}

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) cin>>a[i];
    int l=1, r=n;
    while (l<=r){
        int mid=l+r>>1;
        if (ok(mid)) r=mid-1, ans=mid;
        else l=mid+1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const long long INF = 1LL << 60;

// 入力
int N;
long long h[100010];

// DP テーブル
long long dp[100010];

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

    // 初期化 (最小化問題なので INF に初期化)
    for (int i = 0; i < 100010; ++i) dp[i] = INF;

    // 初期条件
    dp[0] = 0;

    // ループ
    for (int i = 0; i < N; ++i) {
        chmin(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
        chmin(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
    }

    // 答え
    cout << dp[N-1] << endl;
}

Measured memory_bytes: 5180
#include<stdio.h>

int c=0;
void sosucheck(int a){
  int i;
  for(i=2;i*i<=a;i++){
    if(a%i==0)return;
  }
  c++;
}
int main(){
  int i,j,n;
  scanf("%d",&n);
  int a[n];
  for(i=0;i<n;i++)scanf("%d",&a[i]);
  for(i=0;i<n;i++)sosucheck(a[i]);

  printf("%d\n",c);
    return 0;
}



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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16

#define MAX_V 500

struct edge{ ll to,cap,rev; };
vector<edge> G[MAX_V];
ll level[MAX_V];
ll iter[MAX_V];

void add_edge(ll from,ll to,ll cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}

void bfs(ll s){
  memset(level,-1,sizeof(level));
  queue<ll> que;
  level[s]=0;
  que.push(s);
  while(!que.empty()){
    ll v=que.front(); que.pop();
    for(ll i=0;i<G[v].size();i++){
      edge &e=G[v][i];
      if(e.cap>0&&level[e.to]<0){
        level[e.to]=level[v]+1;
        que.push(e.to);
      }
    }
  }
}

ll dfs(ll v,ll t,ll f){
  if(v==t)return f;
  for(ll &i=iter[v];i<G[v].size();i++){
    edge &e=G[v][i];
    if(e.cap>0&&level[v]<level[e.to]){
      ll d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
      }
    }
  }
  return 0;
}

ll max_flow(ll s,ll t){
  ll flow=0;
  while(1){
    bfs(s);
    if(level[t]<0)return flow;
    memset(iter,0,sizeof(iter));
    ll f;
    while((f=dfs(s,t,INF))>0){
      flow+=f;
    }
  }
}

ll n;
ll a[10101];

int main(){
  cin>>n;
  ll s=0;
  rep(i,n){
    cin>>a[i];
    s+=max(a[i],0LL);
  }
  ll source=n,sink=n+1;
  rep(i,n){
    if(a[i]<0)add_edge(source,i,-a[i]);
    else add_edge(i,sink,a[i]);
    repl(j,i+1,n){
      if((j+1)%(i+1)==0)add_edge(i,j,INF);
    }
  }
  cout<<s-max_flow(source,sink)<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int n, a, b, i, suma, sumb, s;
int sol[(1 << 17) + 5], p[(1 << 17) + 3];
int bit(int a, int ii){
    return (1 & (a >> ii) );
}
void solve(int m, int a, int b, int stb, int val){
    if(m == 1){
        sol[++s] = a;
        sol[++s] = b;
        return;
    }
    int i, ii, nr, x, j;
    for(ii = 0; ii < n; ii++){
        if(bit(a, ii) != bit(b, ii)){
            break;
        }
    }
    stb += (1 << ii);
    for(i = 0; i < (1 << m); i++){
        x = val;
        nr = 0;
        for(j = 0; j < n; j++){
            if(bit(stb, j) == 0){
                x += (1 << j) * bit(i, nr);
                nr++;
            }
        }
        if(p[x + (1 << ii) * bit(a, ii)] % 2 != p[a] % 2 && x + (1 << ii) * bit(a, ii) != a && x + (1 << ii) * bit(b, ii) != b){
            solve(m - 1, a, x + (1 << ii) * bit(a, ii), stb, val + (1 << ii) * bit(a, ii));
            solve(m - 1, x + (1 << ii) * bit(b, ii), b, stb, val + (1 << ii) * bit(b, ii));
            return;
        }
    }
}
int main(){
    cin>> n >> a >> b;
    for(i = 1; i < (1 << n); i++){
        p[i] = p[i / 2] + i % 2;
    }
    if(p[a] % 2 == p[b] % 2){
        cout<<"NO";
        return 0;
    }
    cout<<"YES\n";
    solve(n, a, b, 0, 0);
    for(i = 1; i <= s; i++){
        cout<< sol[i] <<" ";
    }
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define pb push_back
using namespace std;

const int N = 100005;
ll n, m, t, a[N], k, l[N], r[N], ans, tong;
ll b[N];
vector<pll> kq;
string s;
priority_queue< pii, vector<pii>, greater<pii> > pr;
void sol()
{
    cin >> n >> s;
    s = " " + s;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        l[i] = i - 1;
        r[i] = i + 1;
    }
    for(int i = 2; i <= n; i ++)
    {
        if(s[i-1] != s[i])
        {
            k = abs(a[i] - a[i-1]);
            pii u;
            u.fi = k;
            u.se.fi = i-1;
            u.se.se = i;
            pr.push(u);
        }

    }
    while(!pr.empty())
    {
        pii u = pr.top();
        pr.pop();
        ll x = u.se.fi, y = u.se.se;
        if(b[x] == 1 || b[y] == 1)continue;
        b[x] = 1;
        b[y] = 1;

        l[r[y]] = l[x];
        r[l[x]] = r[y];
        kq.pb({x, y});
        if(l[x] > 0 && r[y] <= n && s[l[x]] != s[r[y]])
        {
            pii v;
            v.fi = abs(a[l[x]] - a[r[y]]);
            v.se.fi = l[x];
            v.se.se = r[y];
            pr.push(v);
        }
    }
    cout << kq.size() <<'\n';
    for(pll u : kq)cout << u.fi <<" "<<u.se<<'\n';
}
ll random(ll minn, ll maxn)
{
    return minn + rand() % (maxn + 1 - minn);
}
priority_queue<ll> st;
ll uoc(ll a, ll b)
{
    while(b != 0)
    {
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}
void test()
{
   cin >> n >> k;
   ans = 0;
   for(int i = 1; i <= n; i++)cin >> a[i];
   sort(a+1, a+1+n);
   for(int i = 1; i <= k; i ++)ans += a[i];
   cout << ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    test();
}


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


using ll=long long;
using namespace std;

int main(){
   ll x,y;
    cin>>x>>y;
    int cnt =0;
  ll seki=x;
  while(seki <= y){
  seki *=2;
    cnt++;
    
  
  }
  cout << cnt <<endl;
}


Measured memory_bytes: 3640
#include <stdio.h>
void sort(double*v,int l,int r){
  int tmp;
  for(int i=l;i<=r;i++){
    for(int j=i+l;j<=r;j++){
      if(v[i]>v[j]){
        tmp=v[i];
        v[i]=v[j];
        v[j]=tmp;
      }
    }
  }

}

int main(void){
  int n;
  double v[1005];
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    scanf("%lf",&v[i]);
  }
  for(int k=1;k<=n-1;k++){
    sort(v,k,n);
    v[k+1]=(double) (v[k+1]+v[k])/2;
    v[k]=0;
  }
  printf("%f",v[n]);
  return 0;
}

Measured memory_bytes: 1756
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		String f = sc.next();
		// スペース区切りの整数の入力
		if(a % 2 == 0){
			if(f.substring(0,a / 2).equals(f.substring(a / 2,a))){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
		}else{
			System.out.println("No");
		}
		
		
		
	}
}

Measured memory_bytes: 35796
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	int n, a, b, c, d, e = 0; string s; 
	cin >> n >> a >> b >> c >> d >> s;
	for (int h = a - 1; h < max(c,d); h++) {
		if (s[h] == '#'&&s[h + 1] == '#') {
			cout << "No" << endl;
			cin >> n; return 0;
		}
	}
	for (int h = a - 1; h < d - 1; h++) {
		if (s[h] == '.'&&s[h + 1] == '.'&&s[h + 2] == '.') {
			if (h + 2 >= b && (h != a - 1 || h + 2 != b - 1)) {
				e++;
			}
		}
	}
	if (c > d && e == 0) {
		cout << "No" << endl;
		cin >> n; return 0;
	}
	cout << "Yes" << endl;
	cin >> n;
}

Measured memory_bytes: 640
import java.util.Scanner;
	public class Main{
		public static void main(String args[]){
			Scanner sc = new Scanner(System.in);
			int sum = 0;
			int ave = 0;
			int count = 0;
			while(sc.hasNext()){
				String in = sc.nextLine();
				String[] get = in.split(",");
				int cost = Integer.parseInt(get[0]);
				int num = Integer.parseInt(get[1]);
				sum+=cost*num;
				ave+=num;
				count++;
			}
			System.out.println(sum);
			if(ave%count==0){
				System.out.println(ave/count);
			}else{
				System.out.println((ave/count)+1);
			}
		}
	}		

Measured memory_bytes: 25996
let split str delim =
  let rec doit s acc =
    match
      try Some (String.index s delim)
      with _ -> None
    with
    | None -> s :: acc
    | Some i ->
        let s1 = String.sub s 0 i in
        let s2 = String.sub s (i + 1) (String.length s - String.length s1 - 1) in
        doit s2 (s1 :: acc)
  in
  List.rev (doit str [])

let rec repl () =
  let l = read_line () in
  match List.map int_of_string (split l ' ') with
  | [] | [_] | _::_::[] -> exit 1
  | (-1) :: (-1) :: (-1) :: _ -> ()
  | m :: f :: r :: _ -> begin
      if m = (-1) || f = (-1) then Printf.printf "F\n"
      else begin
        let mf = m + f in
        if mf >= 80 then Printf.printf "A\n"
        else if mf >= 65 then Printf.printf "B\n"
        else if (mf >= 50) || (mf >= 30 && r >= 50) then Printf.printf "C\n"
        else if mf >= 30 then Printf.printf "D\n"
        else Printf.printf "F\n"
      end;
    repl ()
    end

let () =
  try repl () with End_of_file -> ()

Measured memory_bytes: 2192
#include <algorithm>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f, MOD = 1000000007;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*-----------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  string s; cin >> s;
  vector<int> cnt(26, 0);
  for (char c : s) {
    ++cnt[c - 'a'];
  }
  long long ans = 1;
  REP(i, 26) (ans *= cnt[i] + 1) %= MOD;
  --ans;
  cout << ans << '\n';
  return 0;
}


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

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, __VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

#define MOD 1000000007
#define INF 1000000000
#define MAX_N 2010

ll N, Z, W;
ll A[MAX_N];

int main()
{
    cin >> N >> Z >> W;
    REP(i, N) {
        cin >> A[i];
    }
    ll ans;
    ll cur = abs(Z - W);
   // if(abs(A[N-1] - W) > cur) {
   //     ans = abs(A[N-1] - W);
   // } else if(abs(A[N-1] - W) == cur) {
   //     ans = max(cur, abs(A[N-2] - A[N-1]));
   // } else {
   if(N == 1) {
        ans = abs(A[N-1] - W);
   } else {
        ans = max(abs(A[N-1] - W), abs(A[N-2] - A[N-1]));
   }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  vector<pair<int, int> > R(N);
  vector<pair<int, int> > B(N);
  
  int a, b;
  for ( int i = 0; i < N; i++ ) {
    cin >> a >> b;
    R[i] = make_pair(a, b);     //赤い点
  }
  
  int c, d;
  for ( int i = 0; i < N; i++ ) {
    cin >> c >> d;
    B[i] = make_pair(c, d);     //青い点
  }
  sort(B.begin(), B.end());
  
  int ans = 0;
  for ( int i = 0; i < N; i++ ) {
    int max = -1;
    int k = 0;
    for ( int j = 0; j < R.size(); j++ ) {
      if ( R[j].first < B[i].first && R[j].second < B[i].second ) {
        if ( R[j].second > max ) {
          max = R[j].second;
          k = j;
        }
      }
    }
    if ( max != -1 ) {
      R.erase(R.begin() + k);
      ans++;
    }
  }
  
  cout << ans << endl;
  
  return 0;
  
}

Measured memory_bytes: 3520
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ff first
#define ss second
#define ll long long
#define vi vector<int>
#define vii vector<vi>
#define vs vector<string>
#define vss vector<vs>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define repr(i, a, n) for (int i = (n); i >= (a); --i)
using namespace std;
const int INF(1 << 30);
const ll LLINF(1LL << 55LL);
const int pi = 3.1415926536;
const int MOD = 1000000007;
const int MAX = 510000;

void Main() {
  int r, g, b;
  cin >> r >> g >> b;
  cout << (((r * 100 + g * 10 + b) % 4 == 0) ? "YES" : "NO") << endl;
}

int main() {
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // SとS++の入出力出力を非同期
  std::cout << std::fixed << std::setprecision(15);  // 小数を10進数表示
  Main();
}

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

#define mk(a,b) make_pair(a,b)
#define se second
#define fi first

typedef pair<int,int> pii;

int H,W;
char fid[2020][2020] = {0};
int dx[] = {0,1,0,1},dy[] = {0,0,1,1};
int mem[2020][2020] = {0}; // true
int ans;

int main()
{
    scanf("%d%d",&H,&W);
    ans = max(H,W);
    for(int i = 0; i < H; i++)scanf("%s",fid[i]);
    for(int i = 0; i < H - 1; i++)
    {
        for(int j = 0; j < W - 1; j++)
        {
            int y = i,x = j;
            int sum = 0;
            for(int k = 0; k < 4; k++)
            {
                x = j + dx[k],y = i + dy[k];
                if(fid[y][x] == '#')sum++;
            }
            if(sum % 2)mem[i + 1][j + 1] = -1;
        }
    }
    for(int i = 1; i < H; i++)
    {
        for(int j = 1; j < W; j++)
        {
            if(mem[i][j] == -1)mem[i][j] = 0;
            else mem[i][j] = mem[i][j - 1] + 1;
        }
    }
    for(int i = 1; i < W; i++)
    {
        stack<pii> S;
        for(int j = 1; j <= H; j++)
        {
            if(S.size() == 0)S.push(mk(j,mem[j][i]));
            else
            {
                if(S.top().se < mem[j][i])S.push(mk(j,mem[j][i]));
                else if(S.top().se > mem[j][i])
                {
                    int now1 = j;
                    while(S.size() && S.top().se >= mem[j][i])
                    {
                        pii now2 = S.top();
                        S.pop();
                        ans = max(ans,(now2.se + 1) * (j - now2.fi + 1));
                        now1 = now2.fi;
                    }
                    S.push(mk(now1,mem[j][i]));
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 20096
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>
#include <queue>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << endl;
#else
	#define DBG(X)
	#define endl '\n'
#endif
 
using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF  = (ll)(2e18);

const int NIL = -1;
static mt19937 _g(time(nullptr));

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for(auto el: v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline void goodbye(const T& val) { cout << val << endl; exit(0); }

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

	vector<int> a(n);
	
	for(auto& x: a)
		cin >> x;

	auto ord = a;
	sort(ord.begin(), ord.end());
	vector<int> answ(n, NIL);

	for(int i = 0; i < n; ++i) 
	{
		int pos = upper_bound(ord.begin(), ord.end(), a[i]) - ord.begin();
		answ[pos - 1] = i + 1;
	}

	cout << answ << endl;
}

int main()
{
	fast_io();
	solve();

	return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl "\n"
#define rep(i,n) for(ll i=0; i<(n); i++)
typedef vector<ll> vl;
typedef vector<vector<ll>> matrix;//matrix A(n, vl(m)); //n*m行列
typedef vector<string> vs;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sortup(V) sort(V.begin(), V.end())
#define sortdown(V) sort(V.rbegin(), V.rend())
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;}
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007 //998244353


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

    // solution comes here

    ll N;
    cin >> N;
    vl A(N+10);
    rep(i, N) cin >> A[i+1];

    ll ans = abs(A[1]) + abs(A[N]);
    for(ll i=1; i<=N-1; i++) ans += abs(A[i]-A[i+1]);

    for(ll i=1; i<=N; i++) cout << ans -abs(A[i-1]-A[i]) -abs(A[i]-A[i+1]) +abs(A[i-1]-A[i+1]) << nl;
}


Measured memory_bytes: 2048
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <iterator>
#define loop(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 debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;

int main() {
    int a, b; cin >> a >> b;
    if ((a == 1 && b == 2) || (a == 2 && b == 1)) {
        cout << 3 << endl;
    } else if ((a == 2 && b == 3) || (a == 3 && b == 2)) {
        cout <<  1 << endl;
    } else {
        cout << 2 << endl;
    }
}


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

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}

#define MAX_PN  110000

bool PN[MAX_PN+2];

void huga(int t, int x){
	if(PN[t]) return;
	for(int i = t*t; i <= x; i+=t)
		PN[i] = true;
}

void Sieve_of_Eratosthenes(int x){
	PN[0]=PN[1]=PN[4]=true;
	for(int i = 6; (i-1)*(i-1) <= x; i+=6)
		huga(i-1,x),huga(i+1,x);
	for(int i = 6; i <= x; i+=6)
		PN[i]=PN[i+2]=PN[i+3]=PN[i+4]=true;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	vector<int> con(MAX_PN);
	Sieve_of_Eratosthenes(MAX_PN);
	
	int Q;
	
	for(int i = 1; i < MAX_PN; i++){
		if(i%2){
			if(PN[i] == false && PN[(i+1)/2] == false){
				con[i] += 1;
			} 
			
		} else {
		}
		
		
		con[i] += con[i-1];
	}
	cin>>Q;
	
	for(int i = 0; i < Q; i++){
		int l, r;
		
		cin>>l>>r;
		
		cout<<con[r] - con[l-1]<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

const int n=1e6;


int main(){
  int N;
  cin >> N;
  int a[N];
  rep(i,N) cin >> a[i];
  sort(a,a+N);
  cout << a[N-1] - a[0] << endl;

  return 0;

}


Measured memory_bytes: 256
class Matrix {
    constructor(w, h, init) {
        this.d = new Array(w);
        for (let i = 0; i < w; ++i) {
            this.d[i] = new Array(h).fill(init);
        }
    }

    get width() {
        return this.d.length;
    }

    get height() {
        if (this.d.length === 0) {
            return 0;
        }
        return this.d[0].length;
    }

    submatrix(x1, x2, y1, y2) {
        const rvalue = new Matrix(x2 - x1, 0, 0);
        for (let i = 0; i < rvalue.width; ++i) {
            rvalue.d[i] = this.d[x1 + i].slice(y1, y2);
        }
        return rvalue;
    }

    flip_h() {
        for (let i = 0, j = this.width - 1; i < j; ++i, --j) {
            [this.d[i], this.d[j]] = [this.d[j], this.d[i]];
        }
        return this;
    }

    flip_v() {
        for (let i = 0, j = this.height - 1; i < j; ++i, --j) {
            for (let k = 0; k < this.width; ++k) {
                [this.d[k][i], this.d[k][j]] = [this.d[k][j], this.d[k][i]];
            }
        }
        return this;
    }

    add(m) {
        const rvalue = new Matrix(Math.max(this.width, m.width), Math.max(this.height, m.height), 0);
        for (let i = 0; i < rvalue.width; ++i) {
            for (let j = 0; j < rvalue.height; ++j) {
                if (i < this.width && j < this.height) {
                    rvalue.d[i][j] += this.d[i][j];
                }
                if (i < m.width && j < m.height) {
                    rvalue.d[i][j] += m.d[i][j];
                }
            }
        }
        return rvalue;
    }
}

new Promise(function(resolve, reject) {
    let cin = "";
    process.stdin
        .on("data", chunk => { cin += chunk; })
        .on("end", () => { resolve([cin, process.stdout]) });
}).then(function([cin, cout]) {
    const sc = cin.split(/[ \n]/).map(elt => parseInt(elt))[Symbol.iterator]();
    for (;;) {
        let n = sc.next().value;
        let m = sc.next().value;
        const t = sc.next().value;
        const p = sc.next().value;
        if (n === 0 && m === 0 && t === 0 && p === 0) break;
        let a = new Matrix(n, m, 1);
        for (let i = 0; i < t; ++i) {
            const d = sc.next().value;
            const c = sc.next().value;
            if (d === 1) {
                a = a.submatrix(0, c, 0, a.height).flip_h().add(a.submatrix(c, a.width, 0, a.height));
            } else {
                a = a.submatrix(0, a.width, 0, c).flip_v().add(a.submatrix(0, a.width, c, a.height));
            }
        }
        for (let i = 0; i < p; ++i) {
            const x = sc.next().value;
            const y = sc.next().value;
            cout.write(`${a.d[x][y]}\n`);
        }
    }
});



Measured memory_bytes: 22024
#include <bits/stdc++.h>
using namespace std;
// (setq-default c-basic-offset 2)

int main() {
  int n;
  cin >> n;
  vector<int> l(n);
  for (int& li : l) cin >> li;

  int ret = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      for (int k = j + 1; k < n; ++k) {
        int a = l[i];
        int b = l[j];
        int c = l[k];
        if ((a == b) or (a == c) or (b == c)) continue;
        vector<int> v = {a, b, c};
        sort(v.begin(), v.end());
        if (v[0] + v[1] > v[2]) ++ret;
      }
    }
  }
  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 3640
import java.util.Scanner;
class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		int count = 0;
		for(int i = 0; i < s.length(); i++){
			if(s.charAt(i) == '1'){
				count++;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 22996
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try{
			int week = Integer.parseInt(br.readLine());
			System.out.println(calcAfterDebt(100000, week));
		}
		catch(Exception e){
			return;
		}
		finally{
			try {
				br.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				return;
			}
		}
	}
	
	private static int calcAfterDebt(int base,int week)
	{
		int result = base;
		for(int i=0;i<week;i++){
			result = (int) (result*1.05);
			if(result % 1000 > 0){
				result = cutThousand(result) + 1000;
			}
		}
		return result;
	}

	private static int cutThousand(int money){
		String str = Integer.toString(money);
		String str2 = str.substring(0, str.length() - 3);
		while(str2.length() < str.length()){
			str2 += "0";
		}
		
		return Integer.parseInt(str2);
	}
}

Measured memory_bytes: 9260
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<int> P(N);
  for(int i=0;i<N;i++){
    cin >> P.at(i);
  }
  
  int count = 0;
  for(int k=1;k<N-1;k++){
    if((P.at(k)-P.at(k-1))*(P.at(k+1)-P.at(k))>0){
      count++;
    }
  }
  
  cout << count <<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
typedef pair<LL,int> LP;
const int INF=1<<30;
const LL MAX=1e9+7;

void array_show(int *a,int n,char middle=' '){
	for(int i=0;i<n;i++)printf("%d%c",a[i],(i!=n-1?middle:'\n'));
}
void array_show(LL *a,int n,char middle=' '){
	for(int i=0;i<n;i++)printf("%lld%c",a[i],(i!=n-1?middle:'\n'));
}

int check(int a,int k){
	if(a<k)return 0;
	int b=a/k+1,c=a%k;
	c%=b;
	if(c==0)return a/k;
	a=(a/k)*k+c;
	return check(a-b,k);
}

int main(){
	int n;
	int s=0;
	int a,b,c;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a>>b;
		s^=check(a,b);
	}
	if(s!=0)cout<<"Takahashi"<<endl;
	else cout<<"Aoki"<<endl;
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var r, d, x2000 int
	fmt.Scan(&r)
	fmt.Scan(&d)
	fmt.Scan(&x2000)

	x := make([]int, 11)
	x[0] = x2000

	for i := 1; i <= 10; i++ {
		x[i] = r*x[i-1] - d
		fmt.Println(x[i])
	}
}


Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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 ll INF=1e18;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    string s;
    cin>>s;
    int ans=0;
    int n=s.size();
    rep(i,n){
        if(s[i]=='?'){
            s[i]='D';
        }
    }
    cout<<s<<endl;
}
//ペナルティ出しても焦らない　ACできると信じろ！！！
//どうしてもわからないときはサンプルで実験　何か見えてくるかも
//頭で考えてダメなら紙におこせ！！
/*
V,P(大文字)使用不可
乗算などの際にオーバーフローに注意せよ！
(適切にmodをとれ　にぶたんで途中で切り上げろ)
制約をよく読め！
{
    ・全探索できるなら全探索しろ
    ・異常な制約ならそこに注目
}
stringの計算量(扱い)注意
コーナー注意！(特に数値が小さいものについては要検証)
N行出力のときは'¥n'
グリッド上では行先が範囲内におさまるかif文で確認(RE注意)
if文ではちゃんと比較演算子==を使え('='でもエラー出ない)
配列(vector)の大きさが0か1以上かで場合分けせよ(RE注意)
(vector<int> a(m)でm==0というものはできない)
modはなるべく最後に取れ！
doubleを扱うときには(abs)ではなく'fabs'!!!
*/

Measured memory_bytes: 3748
import java.util.*;

public class Main {
    static double distance(double r,double g,double b){
        return Math.sqrt(r*r+g*g+b*b);
    }
   
   public static void main(String[] args) throws Exception {
       Scanner sc = new Scanner(System.in);
       String [] colors = {"000black","001blue","010lime","011aqua","100red","101fuchsia","110yellow","111white"};
       while(sc.hasNextLine()){
           String str = sc.nextLine();
           if(str.equals("0")) break;
           int r0 = Integer.parseInt(str.substring(1,3),16);
           int b0 = Integer.parseInt(str.substring(3,5),16);
           int g0 = Integer.parseInt(str.substring(5,7),16);
           
           String ans = "";
           double min = 450.0;
           
           for(String c:colors){
               int r = (c.charAt(0)-'0')*255;
               int b = (c.charAt(1)-'0')*255;
               int g = (c.charAt(2)-'0')*255;
               
               double d = distance(r-r0,g-g0,b-b0);
               if(d<min){
                   min=d;
                   ans=c.substring(3);
               }
           }
           System.out.println(ans);
       }

   }
}


Measured memory_bytes: 31188
#include <iostream>
using namespace std;
#include<bits/stdc++.h> 
#define ll long long int
#define read(a) long long int a; cin>>a;
#define readstr(s) string s; cin>>s;
#define readarr(a,l) long long int a[l]={0}; for(ll i=0;i<l;i++) cin>>a[i];
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define ff first
#define ss second
#define readmtrx(i,j,a,b) ll arr[a][b]={0};for(ll i=0;i<a;i++)for(ll j=0;j<b;j++) cin>>arr[i][j];
#define v(pi) vector<ll>pi
#define vp(pi) vector<pair<ll,ll>>pi
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define pb(p) push_back(p)
#define mp make_pair
#include <cmath>
int main() {
	fast;
	read(a) 
	cout<<a*(a-1)/2<<endl;
	return 0;
}

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

int n;
int is_sq[1<<16];

int rec(int sum,int dep,int last){
  if(sum == 0)return 1;
  if(sum < last * last)return 0;
  if(dep == 3)return is_sq[sum];

  int res = 0;
  for(int i=last;i*i<=sum;i++){
    res += rec(sum-i*i,dep+1,i);
  }

  return res;
}

int main(){
  for(int i=0;i<=(1<<15);i++)is_sq[i] = 0;
  for(int i=0;i*i<=(1<<15);i++)is_sq[i*i] = 1;

  while(cin >> n,n)cout << rec(n,0,1) << endl;
}

Measured memory_bytes: 1292
import java.io.*
import java.util.*

fun solve(N: Int, A: LongArray){
    A.sort()
    val MOD = 1000000007L
    var ans = 0L
    for (i in 0..60){
        val bitSum = A.map{ it shr i and 1 }.sum().toLong()
        val comb = ((N.toLong() - bitSum) * bitSum) % MOD
        ans += (comb * ((1L shl i) % MOD)) % MOD
    }
    println(ans % MOD)
    return
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val N = sc.next().toInt()
    val A = LongArray(N)
    for (i in 0 until N) {
        A[i] = sc.next().toLong()
    }
    solve(N, A)
}



Measured memory_bytes: 106580
#include<iostream>
using namespace std;
int main(){
  int chk = 0;
  string s;
  cin >> s;
  if(s[0] == s[1]){
    if(s[2] == s[3]){
      chk = 1;
    }
  }else if(s[0] == s[2]){
    if(s[1] == s[3]){
      chk = 1;
    }
  }else if(s[0] == s[3]){
    if(s[1] == s[2]){
      chk = 1;
    }
  }
  if(s[0] == s[1] && s[0] == s[2] && s[0] == s[3])
    chk = 0;
  if(chk == 1){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}
        


Measured memory_bytes: 256
s = gets.chomp
s = s.split(',').join(' ')
s = s.split('.').join(' ')
ar = s.split(' ')
ls = []
for i in 0...ar.length
  t = ar[i]
  ls.push(t) if 3<=t.length && t.length<=6
end
print ls[0]
for i in 1...ls.length
  print " ",ls[i]
end
print "\n"

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

using namespace std;

#define pii pair<int,int>
#define ll long long
#define s second
#define f first

const int MAX_N=3005;
const ll MOD=1000000007;
int n;
ll ans,dp[MAX_N][MAX_N],p[MAX_N][MAX_N];
string s;

int main(){
  cin >> n;
  cin >> s;
  dp[1][1]=1;
  p[1][1]=1;
  for(int i=2;i<=n;++i){
    for(int j=1;j<=i;++j){
        if(s[i-2]=='>'){
            /*for(int z=n;z>=j;--z){
                dp[i][j]+=dp[i-1][z];
                dp[i][j]%=MOD;
            }*/
            dp[i][j]=p[i-1][i-1]-p[i-1][j-1];
            dp[i][j]%=MOD;
        }else{
           /*for(int z=1;z<j;++z){
            dp[i][j]+=dp[i-1][z];
            dp[i][j]%=MOD;
           }*/
           dp[i][j]=p[i-1][j-1];
           dp[i][j]%=MOD;
        }
        p[i][j]=p[i][j-1]+dp[i][j];
        p[i][j]%=MOD;

    }
    /*for(int j=i+1;i<=n;++i){
        p[i][j]=p[i][j-1];*/

  }
  if(p[n][n]<0){
    p[n][n]+=MOD;
  }
  cout << p[n][n];
  return 0;
}

Measured memory_bytes: 139648
#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
typedef long long ll;

int n,a[maxn];

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

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007


int main(){

  int n;
  cin >> n;
  vector<ll> v(n,0);
  rep(i,n){
    int x;cin >> x;
    v[x]++;
  }
  ll res = 1;
  bool is = true;
  if(n & 1){
    if(v[0] != 1)is = false;
    for(int i = 1;i < n;i++){
      if(i & 1){
        if(v[i] != 0)is = false;
      }else{
        if(v[i] != 2)is =false;
        else (res *= 2)%= MOD;
      }
    }
  }else{
    rep(i,n){
      if(i & 1){
        if(v[i] != 2)is = false;
        else (res *= 2)%= MOD;
      }else{
        if(v[i] != 0)is = false;
      }
    }
  }
  is ? cout << res << endl : cout << 0 << endl;
  




  return 0;
}

Measured memory_bytes: 1024
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define umap unordered_map
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
    if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
    }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる




//———————UnionFind木   UF uf(n);——————————————————————————

struct UF {
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    UF(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void reset(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    bool unite(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool same(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

//—————————————————————————————————————————————————

using Graph = vector<vector<int>>;


int main() {
  ll n;
  cin >>n;
  
  UF uf(2*n);    
    
  rep(i,n-1){
  ll a,b,c;
  cin>>a>>b>>c;
    if(c%2==0) {
      uf.unite(2*a-2,2*b-2);
      uf.unite(2*a-1,2*b-1);
    }
    if(c%2==1) {
      uf.unite(2*a-2,2*b-1);
      uf.unite(2*a-1,2*b-2);
    } 
  }
  
  cout << 0 << endl;
  repo(i,n){
    if(uf.same(0,2*i)) cout << 0 << endl;
    else cout << 1 << endl;
  }
  
}

Measured memory_bytes: 3584
import java.util.Scanner;
 
class Main {
    public static void main(String[] arg){
        Scanner in = new Scanner(System.in);
        for (int i= 1;;++i){
            int a = in.nextInt();
            if (a == 0) break;
            System.out.println("Case "+i+": "+a);
        }
    }   
}

Measured memory_bytes: 32976
N = int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for i in range(N)]
all = [list(format(i,'b').zfill(10)) for i in range(1,1025)]
ans = -100000000000000000000000

for i in range(1024):
    cnt = []
    gokei = 0
    for j in range(N):

        z = 0
        for a,b in zip(all[i],F[j]):
            if int(a)+b==2:
                z += 1
        cnt.append(z)
    for m in range(N):
        gokei += P[m][cnt[m]]

    ans = max(ans, gokei)

print(ans)






Measured memory_bytes: 3316
N,M = [int(s) for s in input().split()]
lst=[]
for i in range(N):
  lst.append([int(s) for s in input().split()])
# lst = sorted(pre_lst, key=lambda x: x[0])
lst.sort()
count=0
cost=0
for e in lst:
  count+=e[1]
  cost+=e[0]*e[1]
  if(count>=M):
    cost-=e[0]*(count-M)
    break
print(cost)


Measured memory_bytes: 21616
#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9+10;
const int mod=1e9+7;
const int maxn=1e5+10;
int n,m,q,L;
typedef pair<int,int> pii;
vector<pii>g[310];
int ans[310][310],f[310][310];
struct ppo{
    int u,v,cos;
    bool operator<(const ppo &r)const{
        if(cos==r.cos) return v<r.v;
        return cos>r.cos;
    }
};
void bfs(int st){
    priority_queue<ppo>q;
    q.push(ppo{st,L,0});
    while(!q.empty()){
        int u=q.top().u;q.pop();
        for(pii x:g[u]){
            int v=f[st][u];
            int cost=ans[st][u];
            if(v<x.second) v=L-x.second,cost++;
            else v-=x.second;
            if(cost<ans[st][x.first]||(cost==ans[st][x.first]&&v>f[st][x.first])){
                ans[st][x.first]=cost;
                f[st][x.first]=v;
                q.push(ppo{x.first,v,cost});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>n>>m>>L;
    for(int i=1,a,b,c;i<=m;i++){
        cin>>a>>b>>c;
        if(c>L) continue;
        g[a].pb(pii(b,c));
        g[b].pb(pii(a,c));
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) ans[i][j]=inf;
    }
    for(int i=1;i<=n;i++){
        ans[i][i]=0,f[i][i]=L,bfs(i);
    }
    cin>>q;
    while(q--){
        int s,t;
        cin>>s>>t;
        if(ans[s][t]==inf) ans[s][t]=-1;
        cout<<ans[s][t]<<'\n';
    }
    return 0;
}


Measured memory_bytes: 2432
def get_four_data():
    four_data = input().split()
    return four_data

def change_era_name(four_data):
    era, year, month, day = four_data
    year = int(year)
    month = int(month)
    if year >31 or (year >= 31 and month >= 5):
        era = "?"
        year -= 30
    return era, year, month, day

if __name__ == "__main__":
    while True:
        four_data = get_four_data()
        if four_data[0] == "#":
            break
        era, year, month, day = change_era_name(four_data)
        print(era, year, month, day)





Measured memory_bytes: 5604
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <limits.h>
#include <algorithm>

#define Int long long
#define rep(i, n) for (Int i = 0; i < n; i++)
#define in(params) cin >> params;
#define p(params) cout << params << endl;
#define mod 1000000007LL

using namespace std;

int main()
{
    Int N;
    in(N);

    Int c = 0;
    string s;
    for (Int i = 1; i <= N; i++)
    {
        s = to_string(i);

        if ( (s.length() % 2) == 1)
        {
            c++;
        }
    }

    p(c);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using std::min;
using std::max;
using std::sort;
using std::swap;
using std::reverse;
using std::lower_bound;
using namespace std; 
 
#define Pr(f,...) //printf(f,##__VA_ARGS__),fflush(stdout)
 
 
typedef long double ldb;
const ldb PI=acos(-1.0);
const int N=2e5+50,oo=0x3f3f3f3f;
 
int a[N],n,q,xx1,yy1,xx2,yy2;
struct P { int x,y; } p[N],z[N];
bool operator<(P a,P b){return a.x<b.x;}
ldb ans;
int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	freopen("dat.in","r",stdin);
	freopen("my.out","w",stdout);
#endif
	scanf("%d%d%d%d%d",&xx1,&yy1,&xx2,&yy2,&n);
	rep(i,1,n)scanf("%d%d",&p[i].x,&p[i].y);
	if(xx1>xx2)swap(xx1,xx2),swap(yy1,yy2);
	Pr("%d,%d,%d,%d\n",xx1,yy1,xx2,yy2);
	int yr=max(yy1,yy2),yl=min(yy1,yy2);
	rep(i,1,n){
		if(xx1<=p[i].x&&p[i].x<=xx2&&yl<=p[i].y&&p[i].y<=yr){
			z[++q]=p[i];
		}
	}
	sort(z+1,z+q+1);
	if(yy1>yy2)reverse(z+1,z+q+1);
	rep(i,1,q)Pr("(%d,%d)\n",z[i].x,z[i].y);
	memset(a,0x3f,sizeof(a));
	rep(i,1,q){
		*lower_bound(a+1,a+q+1,z[i].y)=z[i].y;
	}
	rep(i,1,q+1)if(a[i]==oo){
		if (i-1==min(abs(xx2-xx1)+1,abs(yy2-yy1)+1)&&i-1){
			ans+=PI*5;
			Pr("Spec Hit\n"); 
		}
		Pr("i=%d\n",i);
		ans+=-20*(i-1)+PI*5*(i-1);
		break;
	}
	ans+=100.0*(abs(xx1-xx2)+abs(yy1-yy2));
	cout << setprecision(14) << fixed << ans << endl;
	return 0; 
}

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

const int nm = 1e5;
int n, m, ans[nm];
vector<int> g[nm];

bool visited[nm] = { 1 };
auto c = greater<pair<int, int>>();
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(c)> q(c);

int main() {
	cout << "Yes" << endl;
	cin >> n >> m;
	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		a--, b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	q.emplace(0, 0);
	while (!q.empty()) {
		int d = q.top().first, v = q.top().second;
		q.pop();
		for (int nv : g[v]) {
			if (visited[nv])
				continue;
			visited[nv] = 1;
			ans[nv] = v + 1;
			q.emplace(d + 1, nv);
		}
	}
	for (int i = 1; i < n; i++)
		cout << ans[i] << endl;
}


Measured memory_bytes: 10852
#include <stdio.h>
#include <math.h>

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		long long a,b,c,d,e;
		scanf("%lld%lld",&a,&b);
		if(a==b)
			printf("%lld\n",2*a-2);
		else
		{
			d=a>b?a:b;
			e=a<b?a:b;
			if(d-e==1)
				printf("%lld\n",2*e-2);
			else
			{
				for(c=sqrt(a*b+0.5);c*c<a*b;c++);
				c--;
				if(c*(c+1)>=b*a)
					printf("%lld\n",2*c-2);
				else
					printf("%lld\n",2*c-1);
			}
		}
	}
	return 0;
 } 

Measured memory_bytes: 128
N = int(input())
li_a = list(map(int, input().split())) #町にいるモンスターの数
li_b = list(map(int, input().split())) #勇者が倒せるモンスターの数
ans = 0
for i in range(N):
  if li_a[i] >= li_b[i]:
    ans += li_b[i]
    #li_a[i+1] += li_a[i] - li_b[i]
  else:
    ans += min(li_a[i] + li_a[i+1], li_b[i])
    li_a[i+1] = max(0, li_a[i] + li_a[i+1] - li_b[i])
print(ans)

Measured memory_bytes: 18624
#include<stdio.h>

int main(void){


  int a,b,c,i;


  int count;


scanf("%d %d %d\n",&a,&b,&c);


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


    if(c%i == 0)count ++;


  }


  printf("%d\n",count);


return 0;


}

Measured memory_bytes: 600
n, k = [int(i) for i in input().split()]
s = [0,1] + [int(i) for i in list(input())] + [1,0]
down = [i for i in range(n+3) if s[i] == 1 and s[i+1] == 0]
up = [i for i in range(n+3) if s[i] == 0 and s[i+1] == 1]
#print(s)
#print(down)
#print(up)
ans = 1
if k >= len(up):
  ans = n
else:
  if down[k] - up[0] - 1 > ans:
    ans = down[k] - up[0] - 1
  for i in range(1,len(up)-k-1):
    if down[i + k] - up[i] > ans:
      ans = down[i + k] - up[i]
  if down[len(up)-1] - up[len(up)-k -1] - 1 > ans:
    ans = down[len(up)-1] - up[len(up)-k -1] - 1
print(ans)

Measured memory_bytes: 8072
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000+5;
int visits[100000+5];
int dp[100000+5];

void dfs(int node,vector<int> v[]){
	visits[node] = true;
	for(int i=0; i<v[node].size(); i++){
		if(!visits[v[node][i]]){
			dfs(v[node][i], v);
		}
		dp[node] = max(dp[node], dp[v[node][i]] + 1);
	}
}

int main(int argc, char const *argv[])
{
	int N, M;
	while(cin >> N >> M) {
		vector<int> v[100000+5];
		int big = 0;
		memset(dp, 0, sizeof(dp));
		for(int i=0; i<M; i++){
			int place1, place2;
			cin >> place1 >> place2;
 			v[place1].push_back(place2);
		}
		for(int i=1; i<=N; i++){
			if(!visits[i]){
				dfs(i, v);
			}
		}
		for(int i=1; i<=N; i++){
			big = max(big, dp[i]);
		}
		cout << big << endl;
	}
	return 0;
}

Measured memory_bytes: 13036
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const ll MOD = 1e9 + 7;
static const ll INF = (ll)1 << 62;

static const ll MAX_N = 100001;
static const ll MAX_M = 200001;

int main() {
	ll n, k; cin >> n >> k;
	ll x[50] = {};
	ll y[50] = {};
	rep(i, 0, n)cin >> x[i] >> y[i];

	ll minV = INF;
	rep(a, 0, n) {
		rep(b, 0, n) {
			rep(c, 0, n) {
				rep(d, 0, n) {
					ll cnt = 0;
					rep(e, 0, n) {
						if (x[b] <= x[e] && x[e] <= x[a] && y[d] <= y[e] && y[e] <= y[c]) {
							cnt++;
						}
					}
					if (cnt >= k) {
						minV = min(minV, (x[a] - x[b])*(y[c] - y[d]));
					}
				}
			}
		}
	}

	cout << minV << endl;
	return 0;
}

Measured memory_bytes: 256
A,B,C,K = map(int,input().split())
if A >= K :
    print(K)
elif A < K and B >= K - A :
    print(A + (K-A)*0 )
elif A < K and B < K - A  :
    print(A + (K-A)*0 +(K-A-B)*(-1))

Measured memory_bytes: 9156
import fractions
 
N = int(input())

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

A_s = LI()
mod = 10**9 + 7

#l = lcm_list(A_s)
l = 1
for num in A_s:
    l = l * num // fractions.gcd(l,num)

count = 0
for a in A_s:
  count+=l//a
  
print(count % mod)


Measured memory_bytes: 6108
#include<bits/stdc++.h>
using namespace std;
long long unit = 1;
long long moder = 1000000007;
int main(){
	int n;
	cin>>n;
	long long bit[61]={0};
	for(int i=0; i<n; i++){
		long long num;
		cin>>num;
		for(int j=0; j<=60; j++){
			if((unit<<j)&num) bit[j]++;
		}
	}
	long long ret = 0;
	for(int i=0; i<=60; i++){
		long long total = bit[i]*(n-bit[i]);
		total%=moder;
		long long val = (unit<<i);
		val%=moder;
		ret+=total*val;
		ret%=moder;
	}
	cout<<ret;
}

Measured memory_bytes: 3496
from collections import*
from bisect import*
p=[1]
for _ in range(30):p+=p[-1]*2,
n,*a=map(int,open(0).read().split())
d=Counter(a)
c=0
for i,b in enumerate(sorted(a)[::-1]):
  if d[b]<1:continue
  d[b]-=1
  x=p[bisect(p,b)]-b
  if d[x]:
    d[x]-=1
    c+=1
print(c)

Measured memory_bytes: 33752
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int a,b,c;
    cin >> a >> b >> c;
    if(a%2 == 0 || b%2 == 0 || c%2 == 0)
        cout << 0 << '\n';
    else{
        long long int temp = a/2;
        cout << min(b*c,min(a*b,c*a)) <<'\n';
    }
    return 0;
}


Measured memory_bytes: 256