akhauriyash/Code-Regression huggingface dataset:
#pragma comment (linker, "/STACK:256000000")
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>

using namespace std;
typedef string::const_iterator State;
const long double Ma_PI = 3.1415926535897932384626433832795028841971L;
#define eps 1e-7
#define LONG_INF 2000000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144*2
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long a = 0;a < b;++a)
#define ALL(x) (x).begin(),(x).end()
void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}
unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
typedef struct BigInt{
    string s = "0";
    BigInt operator +(BigInt obj) {
        string c;
        while (max(obj.s.length(), this->s.length()) + 1 > c.length()) {
            c.pb('0');
        }
        for (int q = 0; q < obj.s.length(); ++q) {
            c[c.length() - 1 - q] = obj.s[obj.s.length() - q - 1];
        }
        for (int q = 0; q < this->s.length(); ++q) {
            c[c.length() - 1 - q] += this->s[this->s.length() - 1 - q] - '0';
            if (c[c.length() - 1 - q] > '9') {
                c[c.length() - 2 - q]++;
                c[c.length() - 1 - q] -= 10;
            }
        }
        if (c.front() == '0') {
            c.erase(c.begin());
        }
        return BigInt{ c };
    }
    BigInt operator *(BigInt obj) {
        BigInt ans;
        for (int i = this->s.length() - 1; i >= 0; --i) {
            REP(q, this -> s[i] - '0') {
                ans = ans + obj;
            }
            obj.s.pb('0');
        }
        return ans;
    }
}BigInt;

#define int ll
void solve() {
    int n;
    cin >> n;
    vector<pair<string, int>> inputs;
    REP(i, n) {
        string a;
        int b;
        cin >> a >> b;
        inputs.pb(mp(a, b));
    }
    int ok = 0;
    int ans = 0;
    string s;
    cin >> s;
    REP(i, n) {
        ans += ok * inputs[i].second;
        if (s == inputs[i].first) {
            ok = 1;
        }
    }
    cout << ans << endl;
}
#undef int
int main() {
    init();
    solve();
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int, input().split()))

even_list = [i for i in A if i % 2 == 0]

special =[i for i in even_list if i % 3 == 0 or i % 5 ==0]

n_1=len(even_list)
n_2=len(special)

if n_1 == n_2:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[100005],a[100005],b[100005],x,y;
long long s;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
int find(int r){return fa[r]?fa[r]=find(fa[r]):r;}
int main(){
	n=read(),m=read();
	if(m==n-1) return 0*puts("0");
	if(m<n-m-2) return 0*puts("Impossible");
	for(int i=1;i<=n;++i) a[i]=read(),s+=a[i];
	for(int i=1;i<=m;++i){
		x=read(),y=read();
		x=find(x+1),y=find(y+1);
		s-=max(a[x],a[y]);
		b[i]=max(a[x],a[y]);
		if(a[x]>a[y]) fa[x]=y;else fa[y]=x;
	}
	sort(b+1,b+m+1);
	for(int i=1;i<=n-m-2;++i) s+=b[i];
	printf("%lld",s);
}
//既然输入的都是树，并且要求加的边的点权最小，不妨将每一棵树考虑成一棵根节点值最小的树
//显然最优的情况就是把每一棵树的顶点和剩下最小的n-m-2个点连接
//用并查集维护根最小，先把所有点加入sum，每次加入边的时候找它们所在树的根都，把大的点从sum里删除并并入小的点所在的树 
//最后剩下的sum一定是所有树的根的和
//排序一下剩下的点，取最小的n-m-2个点计入sum即为答案 

Measured memory_bytes: 1408
/**
    C - Unification
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
    int ceros=0, unos=0;
    char c;
    while(scanf("%c",&c),c!='\n'){
        if(c == '0')
            ceros++;
        else
            unos++;
    }
    printf("%d",(2*min(ceros,unos)));

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main () {
	int n;
	cin >> n;
	int x1 = floor(n/1.08);
	int x2 = ceil(n/1.08);
	if ((int)(x1*1.08)==n) {
		cout << x1; return 0;
	}
	if ((int)(x2*1.08)==n) {
		cout << x2; return 0;
	}
	cout << ":(";
	return 0;
} 

Measured memory_bytes: 3636
<?php
  $s = [];
  for($i=0;$i<3;$i++){
    $s[] = explode(" ", trim(fgets(STDIN)));
  }

  for($i=0;$i<=100;$i++){
    $a1=$i;
    $b1=$s[0][0]-$a1;
    if($b1<0) continue;
    $b2=$s[0][1]-$a1;
    if($b2<0) continue;
    $b3=$s[0][2]-$a1;
    if($b3<0) continue;
    $a2=$s[1][0]-$b1;
    if($a2<0) continue;
    if($a2!=$s[1][1]-$b2){
      continue;
    }
    if($a2!=$s[1][2]-$b3){
      continue;
    }
    $a3=$s[2][0]-$b1;
    if($a3<0) continue;
    if($a3!=$s[2][1]-$b2){
      continue;
    }
    if($a3!=$s[2][2]-$b3){
      continue;
    }
    echo "Yes";
    exit;
  }

  echo "No";

Measured memory_bytes: 16060
let readString() = stdin.ReadLine()
let readStringArray() = stdin.ReadLine().Split(' ');
let readInt() = readString() |> int
let readIntArray() = readStringArray() |> Array.map (fun x -> int x)

let x, a, b = readIntArray() |> fun x -> (x.[0], x.[1], x.[2])
if b - a <= 0 then 
    "delicious"
else if b - a >= x + 1 then 
    "dangerous"
else 
    "safe"
|> printfn "%s"

Measured memory_bytes: 11996
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

int N, R = -1, P[100001], L[100001], U[100001], INF = INT_MAX / 3, X[100001];
vi G[100001];

void f(int u, int p) {
    if(P[u] != -1)L[u] = U[u] = P[u];
    each(v, G[u])if(v != p) {
        f(v, u);
        smax(L[u], L[v] - 1);
        smin(U[u], U[v] + 1);
    }
}

void g(int u, int p, int x) {
    X[u] = x;
    each(v, G[u])if(v != p) {
        if(L[v] <= x + 1 && x + 1 <= U[v])g(v, u, x + 1);
        else if(L[v] <= x - 1 && x - 1 <= U[v])g(v, u, x - 1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> N) {
        rep(i, N + 1) {
            G[i].clear();
            L[i] = -INF;
            U[i] = INF;
            X[i] = INF;
        }
        rep(i, N - 1) {
            int a, b;
            cin >> a >> b;
            G[a].push_back(b);
            G[b].push_back(a);
        }

        MEM(P, -1);
        int K;
        cin >> K;
        while(K--) {
            int v, p;
            cin >> v >> p;
            P[v] = p;
            R = v;
        }

        f(R, -1);
        g(R, -1, P[R]);

        int ok = 1;
        FOR(i, 1, N + 1)ok &= X[i] != INF;

        if(!ok) {
            cout << "No" << endl;
            continue;
        }
        cout << "Yes" << endl;
        FOR(i, 1, N + 1)cout << X[i] << endl;
    }
}

Measured memory_bytes: 15744
#include<bits/stdc++.h>
#include<unistd.h>
using namespace std;
#define pb(x) push_back(x);
#define pi 3.141592653589793238;
typedef long long  int ll;
ll mod = 998244353;
ll hmaxii=0;
vector<ll>values[2*100000+1];
ll MAXN = 2*100000+1;
ll spf[2*100000+1];
//vector<ll>values[];
ll diff,x,y,z;
ll flag=1;ll price[1001][1001];

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }



void solution(){
    int a,b,h,m;
    cin>>a>>b>>h>>m;
     double theta = 3.141592653589793238*((( double)h/6.0+( double)m/360.0-( double)m/30.0));
     double ans = ( double)(a*a)+( double)(b*b)-( double)(2*a*b*cos(theta));
    cout<<setprecision(11)<<sqrt(ans)<<endl;
}


int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //sieve();
    /*ll powe[64];
    powe[0]=1;
    ll i=1;
    while(i<64){
        powe[i] = powe[i-1]*2;
        i++;
    }*/
    ll t;
    //cin>>t;
    t=1;
    while(t--){
        solution();
    }
    return 0;
}


Measured memory_bytes: 8852
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define pb push_back

int rec(string s){
  //cout << "s==" << s << endl;
  if(s[0]!='[') return atoi(s.c_str())/2+(atoi(s.c_str())%2==0 ? 0:1); 
  vector<int> b;
  int a=0;
  string str;
  repi(i,1,s.size()-1){
    if(i==1 && s[i]!='['){
      b.pb(rec(s.substr(1,s.size()-2)));
      break;
    }
    if(s[i]=='[') a++;
    else if(s[i]==']') a--;
    
    str+=s[i];

    if(a==0) {
      b.pb(rec(str));
      str="";
    }
  }
  sort(b.begin(),b.end());
  int ans=0;
  rep(i,b.size()/2+(b.size()%2==0 ? 0:1)){
    ans+=b[i];
  }
  return ans;
}

int main(){
  int n;
  cin >> n;
  rep(i,n){
    string s;
    cin >> s;
    cout << rec(s) << endl;;
  }
  return 0;
}

Measured memory_bytes: 3184
import java.util.Arrays;
import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      if(n<1000){
        System.out.println("ABC");
      }else{
        System.out.println("ABD");
      }
    }
}


Measured memory_bytes: 21588
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
#define e_b emplace_back
#define all(x) (x).begin(),(x).end()
#define uniq(x) ((x).erase(unique(all(x)),(x).end()))
#define sz(x) ((int)(x).size())

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

#ifdef LOCAL//compile with -DLOCAL
#define debug(x) cerr<<"LINE"<<__LINE__<<" : "<<#x<<" = "<<(x)<<endl
#define debug_vec(x) cerr<<"LINE"<<__LINE__<<" : "<<#x<<" = ";\
  rep(i,sz(x)){cerr<<x[i]<<" ";}cerr<<endl
#define debug_mat(x) cerr<<"LINE"<<__LINE__<<" : "<<#x<<" = "<<endl;\
  rep(i,sz(x)){rep(j,sz(x[i])){cerr<<x[i][j]<<" ";}cerr<<endl;}cerr<<endl
#else
#define debug(x) void(0)
#define debug_vec(x) void(0)
#define debug_mat(x) void(0)
#endif

template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}


int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N;
  cin >> N;
  vector<ll> A(N);
  rep(i,N)  cin >> A.at(i);

  ll ans=0;
  ll now=A.at(0);
  rep(i,N){
    if(now<A.at(i)){
      now=A.at(i);
    }
    else{
      ans+=now-A.at(i);
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4780
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    while(true){
        string s1;
        cin >> s1;
 
        if(s1==".")
            break;
 
        string s2;
        cin >> s2;
 
        if(s1==s2){
            cout << "IDENTICAL" << endl;
            continue;
        }
 
        string t1 = s1;
        string t2 = s2;
 
        while(true){
            size_t d1b = t1.find('\"');
            if(d1b==string::npos)
                break;
            t1.replace(d1b, 1, "@");
 
            size_t d1e = t1.find('\"');
            t1.replace(d1e, 1, "@");
 
            size_t d2b = t2.find('\"');
            if(d2b==string::npos)
                break;
            t2.replace(d2b, 1, "@");
 
            size_t d2e = t2.find('\"');
            t2.replace(d2e, 1, "@");
 
            string u1 = s1;
            u1.replace(d1b+1, d1e-d1b-1, "");
            string u2 = s2;
            u2.replace(d2b+1, d2e-d2b-1, "");
 
            if(u1==u2){
                t1 = u1;
                t2 = u2;
                break;
            }
        }
 
        if(t1==t2){
            cout << "CLOSE" << endl;
        }
        else{
            cout << "DIFFERENT" << endl;
        }
    }
 
    return 0;
}


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

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> a(2, vector<int>(n));
    rep(i, 2) {
        rep(j, n) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    rep(i, n) {
        int sum = 0;
        rep(j, i + 1) {
            sum += a[0][j];
        }
        repl(j, i, n) {
            sum += a[1][j];
        }
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}


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

int main()
{
	int N, M, C;
	cin >> N >> M >> C;
	int B[M];
	int A[N][M];
	int ans = 0;
	int qq = 0;
	for(int i = 0; i < M; ++i)
	{
		cin >> B[i]; 
	}
	for(int i = 0; i < N; ++i)
	{
		for(int j = 0; j < M; ++j)
		{
			 cin >> A[i][j];
		} 
	}
	for(int i = 0; i < N; ++i)
	{
		qq = 0;
		qq += C;
		
		for(int j = 0; j < M; ++j)
		{
			qq += B[j] * A[i][j];
		} 
		if(qq > 0)
		{
			ans += 1;
		}
		
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
arr = list(map(int,input().split()))
c = 1000
ans = 0
for i in range(1, len(arr)):
    if arr[i] > arr[i-1]:
        st = c//arr[i-1]
        rem = c%arr[i-1]
        c = st*(arr[i]) + rem
print(c)

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

template <class T> using V = vector<T>;
template <class S, class T> using P = pair<S, T>;
template <class... T> using TP = tuple<T...>;

using ll = long long;
using db = double;
using ldb = long db;
using str = string;
using vll = V<ll>;
using vvll = V<V<ll>>;
using pll = P<ll,ll>;
using tpll = TP<ll,ll,ll>;
using vpll = V<pll>;
using vst = V<str>;
using vch = V<char>;

#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(b);i>(ll)(a);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __lcm(a,b)
#define co(a) cout<<a<<endl
#define pb(a) push_back(a)
#define pob pop_back()
#define mp make_pair
#define mt make_tuple
#define pbmp(a,b) push_back(mp(a,b))
#define subs(a,b) substr(a,b)
#define INF 1e16
#define mod 1e9+7


int main(){
  ll n,k;
  cin>>n>>k;
  co(n-k+1);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    string d[4] = {"dream", "erase", "eraser", "dreamer"};
    string s;
    cin >> s;
    int len = s.size();

    while(len != 0){
        for(int i=0;i<4;i++){
            int di_len = d[i].size();
            string tmp = "";
            if(len < di_len){
                continue;
            }
            tmp = s.substr(len - di_len,di_len);
            if (tmp.compare(d[i])==0){
                s = s.substr(0,len-di_len);
                len = len - di_len;
                goto loop;
            }
        }
        printf("NO\n");
        return 0;
        loop:;
    }
    printf("YES\n");
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>

using namespace std;

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

	int l = 1, r = N;
	for (int i = 0; i < M; ++i) {
		int L, R;
		cin >> L >> R;
		l = max(l, L);
		r = min(r, R);
	}
	cout << max(0, r - l + 1) << endl;
}


Measured memory_bytes: 256
S=input()
if S[0]=="A":
    if "C"in S[2:-1]:
        if S[2:-1].count("C")==1:
            S=S.replace("A","")
            S=S.replace("C","")
            
            if S.islower():print("AC")
            else:print("WA")
        else:print("WA")
    else:print("WA")

else:print("WA")
            


Measured memory_bytes: 2940
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
using namespace std;

struct Info{
	int small,big;
};


int main(){

	Info info[6];
	int left,right;

	for(int i = 0; i < 6; i++){
		scanf("%d %d",&left,&right);

		if(left <= right){
			info[i].small = left;
			info[i].big = right;
		}else{
			info[i].small = right;
			info[i].big = left;
		}
	}

	for(int i = 1; i <= 5; i++){
		for(int k = 5; k >= i; k--){
			if((info[k].small < info[k-1].small) ||
					(info[k].small == info[k-1].small && info[k].big < info[k-1].big)){
				swap(info[k],info[k-1]);
			}
		}
	}

	if(info[0].small == info[1].small && info[0].big == info[1].big &&
			info[2].small == info[3].small && info[2].big == info[3].big &&
			info[4].small == info[5].small && info[4].big == info[5].big &&
			info[0].small == info[2].small ){
		//Do nothing
	}else{
		printf("no\n");
		return 0;
	}


	if(info[0].big > info[2].big){
		if(info[0].big == info[4].big && info[2].big == info[4].small){
			printf("yes\n");
		}else{
			printf("no\n");
		}
	}else{
		if(info[0].big == info[4].small && info[2].big == info[4].big){
			printf("yes\n");
		}else{
			printf("no\n");
		}
	}

    return 0;
}

Measured memory_bytes: 2692
#include<bits/stdc++.h>
#define mo 1000000007
#define ny 499122177
#define maxn 1000000000000000000LL
#define pi 3.1415926535898
#define eps 1e-9 
using namespace std;
long long read(){
    long long xx=0,flagg=1; 
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
int n,i,x,y,max1,max2,zhan[100005],book[100005],flag,du[100005];
int top,nex[200005],to[200005],fir[100005],sum,ans[100005];
void lj(int u,int v){
	top++;
	nex[top]=fir[u];
	fir[u]=top;
	to[top]=v;
}
void ss(int u,int v,int w){
	if(w>=max1){
		max1=w;
		max2=v;
	}
	for(int top1=fir[v];top1;top1=nex[top1])
		if(to[top1]!=u)
			ss(v,to[top1],w+1);
}
void ss2(int u,int v){
	if(flag==1)
		return;
	top++;
	zhan[top]=v;
	if(v==y){
		for(i=1;i<=top;i++)
			book[zhan[i]]=1;
		flag=1;
		return;
	}
	for(int top1=fir[v];top1;top1=nex[top1])
		if(to[top1]!=u)
			ss2(v,to[top1]);
	if(flag==1)
		return;
	zhan[top]=0;
	top--;
}
int main(){
	n=read();
	for(i=1;i<n;i++){
		x=read();y=read();
		lj(x,y);
		lj(y,x);
		du[x]++;
		du[y]++;
	}
	ss(1,1,0);
	x=max2;
	max1=0;
	ss(max2,max2,0);
	y=max2;
	
	du[x]++;
	du[y]++;
	top=0;
	ss2(x,x);
	for(i=1;i<=n;i++){
		flag=book[i];
		for(int top1=fir[i];top1;top1=nex[top1])
			if(book[to[top1]]==1)
				flag=1;
		if(flag==0){
			pus(-1,2);
			return 0;
		}
	}
	for(i=1;i<=top;i++)
		du[zhan[i]]-=2;
	for(i=1;i<=top/2;i++)
		if(du[zhan[i]]>du[zhan[top-i+1]]){
			for(i=1;i<=top/2;i++)
				swap(zhan[i],zhan[top-i+1]);
		}
		else if(du[zhan[i]]<du[zhan[top-i+1]])
			break;
	sum=0;
	for(i=1;i<=top;i++){
		ans[sum+du[zhan[i]]+1]=sum+1;
		for(int j=sum+1;j<=sum+du[zhan[i]];j++)
			ans[j]=j+1;
		sum+=du[zhan[i]]+1;
	}
	for(i=1;i<=n;i++)
		pus(ans[i],1);
	cout<<endl;
    return 0;
}

Measured memory_bytes: 8960
from numpy import*
def main():
  _,a,b,*h=map(int,open(0).read().split())
  h=int32(h)
  i,j=0,2**30
  while~i+j:
    k=(j+i)//2
    t=(b*k-h)//(a-b)
    if-k>sum(t[t<0]):i=k
    else:j=k
  print(j)
main()

Measured memory_bytes: 23116
#include <stdio.h>
#include<vector>
#include<math.h>
#include<string>

typedef long long ll;
typedef unsigned short int unsi;
typedef unsigned int uni;
typedef unsigned long int unli;

using namespace std;

unsi gojoho(unsi A, unsi B) {
	unsi R = 1;
	if (A > B) {
		while (R!=0) {
			R = A % B;
			A = B;
			B = R;
		}
		return A;
	} else {
		while (R != 0) {
			R = B % A;
			B = A;
			A = R;
		}
		return B;
	}
}

uni gojoho(uni A, uni B) {
	uni R = 1;
	if (A > B) {
		while (R != 0) {
			R = A % B;
			A = B;
			B = R;
		}
		return A;
	} else {
		while (R != 0) {
			R = B % A;
			B = A;
			A = R;
		}
		return B;
	}
}

unli gojoho(unli A, unli B) {
	unli R = 1;
	if (A > B) {
		while (R != 0) {
			R = A % B;
			A = B;
			B = R;
		}
		return A;
	} else {
		while (R != 0) {
			R = B % A;
			B = A;
			A = R;
		}
		return B;
	}
}

int gojoho(int A, int B) {
	int R = 1;
	if (A > B) {
		while (R != 0) {
			R = A % B;
			A = B;
			B = R;
		}
		return A;
	} else {
		while (R != 0) {
			R = B % A;
			B = A;
			A = R;
		}
		return B;
	}
}



int main(){
	int N, M;
	int L_in;
	int R_in;
	int L_max = 0;
	int R_min = 100000;

	scanf("%d%d", &N, &M);
	
	for (int i = 1; i <= M; i++) {
		scanf("%d%d", &L_in, &R_in);
		if (L_in > L_max) {
			L_max = L_in;
		}
		if (R_in < R_min) {
			R_min = R_in;
		}
	}

	if (R_min < L_max) {
		printf("%d", 0);
	}else {
		printf("%d", R_min - L_max + 1);
	}
	
}


Measured memory_bytes: 128
//diff string通过set筛选
//但是如果i和j任意选一定超时
//单调选
//
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
char str[MAXN];
int alp[27];
long long ans;
int main()
{
    scanf("%s",str+1);
    int n=strlen(str+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=25;j++)
        {
            if(j==(str[i]-'a'))
            {
                continue;
            }
            else
            {
                ans+=alp[j];
            }
        }
        alp[str[i]-'a']++;
    }
    printf("%lld\n",ans+1);
}


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

string s;
long long int x,ans,a,b;

int main(){
    cin>>x;
    for(int i=-1000;i<1000;i++){
        for(int u=-1000;u<1000;u++){
            if(pow(i,5)-pow(u,5)==x){
                cout<<i<<" "<<u<<endl;
                return 0;
            }
        }
    }

}


Measured memory_bytes: 4100
n = int(input())
l =list(map(int, input().split()))
ans = 0
for i in range(n):
        for j in range(i+1, n):
                for k in range(j+1, n):
                        if j > n-2 or k > n-1:
                                continue
                        if l[i] == l[j] or l[j] == l[k] or l[k] == l[i]:
                                continue
                        if abs(l[j] - l[k]) < l[i] < l[j] + l[k]:
                                ans += 1
print(ans)

Measured memory_bytes: 9192
#include <bits/stdc++.h>
 
using namespace std;
 
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 924844033ll
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl
ll n,f[2005],k;
int dp[2][4005][4005];
ll rec(ll i,ll j,ll z)
{
	if(i>n)
		i++;
	if(i>n&&i%(2*k)==1%(2*k))
		return j==0;
	if(i>n)
	{
		i%=(2*k);
		if(i==0)
			i=2*k;
		if(i-k>=1&&i-k<=n)
			z=0;
		else
			z=1;
	}
	if(dp[z][i][j]!=-1)
		return dp[z][i][j];
	ll an=0;
	an=(an+rec(i+2*k,j,0))%MOD;
	if(i+k<=n&&j)
		an=(an+rec(i+2*k,j-1,1))%MOD;
	if(z==0&&j&&i-k>=1&&i-k<=n&&i<=n)
		an=(an+rec(i+2*k,j-1,0))%MOD;
	return dp[z][i][j]=an;
}
int main()
{	
	memset(dp,-1,sizeof dp);
	f[0]=1;
	for(int i=1;i<=2000;i++)
		f[i]=(f[i-1]*i)%MOD;
	SPEED;
	cin>>n>>k;
	ll m=1,ans=0;
	for(int i=0;i<=n;i++,m*=-1)
		ans=(ans+f[n-i]*m*rec(1,i,1)+MOD*MOD)%MOD;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 125824
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int m,d;
	while (cin>>m>>d)
	{
		int sum=0;
		for (int i=2;i<=9;i++)
		{
			for (int j=2;j<=9;j++)
			{
				int t=i*10+j;
				if (t<=d&&(i*j<=m))
				{
					sum++;
				}
						
			}		
		}	
		cout<<sum<<endl;
	}
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n;
	string s="";
	cin>>n;
	while(n!=0)
	{
		if(n%26)
		{
			s=(char)(96+n%26)+s;
		}
		else
		{
			s='z'+s;
			n-=26;
		}
		n/=26;
	}
	cout<<s;
	return 0;
}

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

int main(){
    int N,f=0,max=0;
    cin >> N;
    int A[2][N];
    for (int i=0;i<2;i++){
        for (int j=0;j<N;j++){
            cin >> A[i][j];
        }
    }

    for (int i=0;i<N;i++){
            int sum=0;
            f=0;
        for (int j=0;j<N;j++){
        if (f==0 && i==j){
            sum = sum + A[0][j] + A[1][j];
            f = 1;
        }else if(f==0){
            sum = sum + A[0][j];
        }else{
            sum = sum + A[1][j];
        }
        }
        if (max < sum){
            max = sum;
        }
    }
    cout << max << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
    
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    /*-----------------Code Begins Here------------------*/
    
    char ch;
    cin>>ch;
    if('a'<=ch && ch<='z') cout<<'a';
    else cout<<'A';
    
    /*------------------Code Ends Here-------------------*/
    
    return 0;
}

Measured memory_bytes: 3684
#include <iostream>
#include <stdlib.h>

using namespace std;

int main(int argc, char **argv)
{
	int *l, *r;
	float left, right;
	
	l = (int *)calloc(4, sizeof(int));
	r = (int *)calloc(4, sizeof(int));
	
	while(cin >> left >> right){
		if(left < 0.2){
			l[3]++;
		} else if(left < 0.6){
			l[2]++;
		} else if(left < 1.1){
			l[1]++;
		} else {
			l[0]++;
		}
		
		if(right < 0.2){
			r[3]++;
		} else if(right < 0.6){
			r[2]++;
		} else if(right < 1.1){
			r[1]++;
		} else {
			r[0]++;
		}
	}
	
	for(int i = 0; i < 4; i++){
		cout << l[i] << " " << r[i] << endl;
	}
	
	free(l);
	free(r);
	
	return 0;
}

Measured memory_bytes: 0
n=int(input())
s=input()
t=input()
if s==t:
    print(len(s))
    exit()
ans=s

for i in range(0,n):
    if s[i]==t[0]:
        flag=True
        for j in range(0,n-i):
            if not s[i+j]==t[0+j]:
                flag=False
        if flag:
            tmp=n-i
            ans+=t[tmp:]
            print(len(ans))
            exit()
g=True
if g:
    print(len(s+t))


Measured memory_bytes: 3064
n = int(input())
p = [int(s) for s in input().split()]
q = [int(s) for s in input().split()]
pp = []
qq = []
for i in range(n):
    pp.append(0)
    qq.append(0)
for i in range(n-1):
    for j in range(n-i-1):
        if(p[i]>p[j+i+1]):
            pp[i]=pp[i]+1
        if(q[i]>q[j+i+1]):
            qq[i]=qq[i]+1
a = 0
b = 0
x = 1
for i in range(n-1):
    a = a + pp[n-i-2]*x
    b = b + qq[n-i-2]*x
    x = x*(i+2)
if (a>=b):
    print(int(a-b))
else:
    print(int(b-a))

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

//D

int main() {
  
  int N; cin >> N;
  string S; cin >> S;
  
  int64_t R=0, G=0, B=0;
  for(int i=0; i<N; i++){
    if(S.at(i) == 'R') R++;
    if(S.at(i) == 'G') G++;
    if(S.at(i) == 'B') B++;
  }
  
  long long ans = 0;
  
  ans += R*G*B;
  
  for(int i=0; i<N-1; i++){
    for(int d=1; i+2*d<N; d++){
      if(S.at(i) != S.at(i+d) && S.at(i+d) != S.at(i+2*d) && S.at(i+2*d) != S.at(i)){
        ans--;
      }
    }
  }
  
  cout << ans << endl;
  
}

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

int main() {
  string a,b,c;
  int    d,e;
  cin >> a >> b >> c;
  d=a.size()-1;
  e=b.size()-1;
  if(a.at(d)==b.at(0) && b.at(e)==c.at(0)){
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

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

int main(){
        int N, W;
    cin >> N >> W;
    vector<vector<long long>> dp(101, vector<long long>(1e5 + 1, 1e10));
    vector<int> w(N + 1);
    vector<int> v(N + 1);
    dp[0][0] = 0;
    w[0] = 0;
    v[0] = 0;
    for(int i = 1;i < N + 1;++i){
        cin >> w[i] >> v[i];
    }
    for(int i = 1;i < N + 1;++i){
        for(int j = 0;j < 1e5 + 1;++j){
            if(j - v[i] < 0){
                dp[i][j] = dp[i - 1][j];
            }else{
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
            } 
        }
    }   
    for(int j = (int)1e5;j > -1;--j){
        if(dp[N][j] <= W){
            cout << j << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 80256
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<string>
#include<cstdio>
#include<queue>
#include<functional>
#include<tuple>
#include<iomanip>
#include<stack>
#include<cmath>
#define int long long
#define INF 1<<40
#define N 100
using namespace std;
int n;
void dfs(string s,char c) {
	if (s.length() == n) cout << s << endl;
	else {
		for (char i = 'a'; i <= c; ++i) {
			dfs(s + i, (i == c ? c + 1 : c));
		}
	}
}
signed main() {
	cin >> n;
	dfs("", 'a');
	return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repR(i, n) for(int i = n; i >= 0; ++i)
#define FDS(i, n) for(ll i = 0; i < n; ++i)
#define FDSR(i, n) for(int i = n; i >= 0; ++i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define FORR(i, m, n) for(int i = m;i >= n;--i)
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define itn int
#define ednl endl
using namespace std;
typedef long long ll;
int main(){
	string S,T;
	cin>>S>>T;
	int N=S.size();
	vector<char> s(N);
	vector<char> t(2*N);
	FDS(i,N){
		s[i]=S.at(i);
		t[i]=T.at(i);
		t[i+N]=T.at(i);
	}
	int sub=0;
	int f=0;
	FDS(i,N){
		FDS(j,N){
			if(s[j]==t[j+i]){
				sub++;
			}
		}
		if(sub==N){
			f++;
			break;
		}
		else{
			sub=0;
		}
	}
	if(f){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main() {
	int h,m,s,t;
	cin >> t;

	s = t % 60;
	m = (t / 60) % 60;
	h = (t / 3600) % 24;

	cout << h << ":" << m << ":" << s << endl;
	
	return 0;

}


Measured memory_bytes: 3108
N, K = map(int, input().split())


def solve(N, K):
    edge = [(1, i+2) for i in range(N-1)]
    max_num = (N - 1) * (N - 2) // 2
    now = 2
    check = 1
    for i in range(max_num - K):
        if now + check > N:
            now += 1
            check = 1
        edge.append((now, now + check))
        check += 1
    return edge


if (N - 1) * (N - 2) // 2 < K:
    print(-1)
else:
    ans = solve(N, K)
    print(len(ans))
    for i in range(len(ans)):
        print('{} {}'.format(ans[i][0], ans[i][1]))


Measured memory_bytes: 44264
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}


template<lint mod>
struct Int_{
  unsigned x;
  unsigned mpow(Int_ a,unsigned k){
    Int_ res=1;
    while(k){
      if(k&1) res=res*a;
      a=a*a;
      k>>=1;
    }
    return res.x;
  }
  unsigned inverse(Int_ a){
    return mpow(a,mod-2);
  }
  Int_(): x(0) { }
  Int_(long long sig) {
    int sigt=sig%mod;
    if(sigt<0) sigt+=mod;
    x=sigt;
  }
  unsigned get() const { return (unsigned)x; }
  
  Int_ &operator+=(Int_ that) { if((x += that.x) >= mod) x -= mod; return *this; }
  Int_ &operator-=(Int_ that) { if((x += mod - that.x) >= mod) x -= mod; return *this; }
  Int_ &operator*=(Int_ that) { x = (unsigned long long)x * that.x % mod; return *this; }
  Int_ &operator=(Int_ that) { x=that.x; return *this;}
  Int_ &operator/=(Int_ that) { x=(unsigned long long) x * inverse(that.x)%mod; return *this;}
  bool operator==(Int_ that) const { return x==that.x; }
  bool operator!=(Int_ that) const { return x!=that.x; }

  Int_ operator-() const { return Int_(0)-Int_(*this);}
  Int_ operator+(Int_ that) const { return Int_(*this) += that; }
  Int_ operator-(Int_ that) const { return Int_(*this) -= that; }
  Int_ operator*(Int_ that) const { return Int_(*this) *= that; }
  Int_ operator/(Int_ that) const { return Int_(*this) /= that; }

};

namespace std{
  template<lint mod>
  ostream &operator <<(ostream& out,const Int_<mod>& a){
    out<<a.get();
    return out;
  }
  template<lint mod>
  istream &operator >>(istream& in,Int_<mod>& a){
    in>>a.x;
    return in;
  }
};

typedef Int_<1000000007> Int;
//const int INF=5e8;
int n,k;

Int dp[2005][2005];

Int fact[4000005],inv[4000005];
Int C(int a,int b){
  return fact[a]*inv[b]*inv[a-b];
}

int main(){
  const int M=4000000;
  fact[0]=1;
  REP(i,M) fact[i+1]=fact[i]*(i+1);
  Int one=1;
  REP(i,M) inv[i]=one/fact[i];
  cin>>n>>k;
  if(n==1 || k==1){
    puts("1");
    return 0;
  }
  dp[0][0]=1;
  REP(i,n+1) REP(j,n+1) if(dp[i][j].x && i>=j){
    if(i<n){
      dp[i+1][j]+=dp[i][j];
    }
    if(j<n){
      dp[i][j+1]+=dp[i][j]*C((n-j)*(k-1)+(n-i)-1,k-2)*(n-j);
    }
  }
  Int res=dp[n][n];
  cout<<res<<endl;
  return 0;
}




Measured memory_bytes: 47232
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    int t[10010];
    memset(t,0,sizeof(t));
    for(int i=1;i<=101;i++)
        for(int j=1;j<=101;j++)
        for(int k=1;k<=101;k++)
    {
        int sum=i*i+j*j+k*k+i*j+i*k+j*k;
        if(sum<10010)
            t[sum]++;
    }
    for(int i=1 ;i <=n;i++)
        printf("%d\n",t[i]);
    return 0;
}


Measured memory_bytes: 3824
#include <iostream>
#include <vector>
#include <algorithm>

#define REP(i,a,b) for(int i=int(a);i<int(b);i++)

using namespace std;

typedef long long int lli;

int main () {
    int N;
    cin >> N;
    vector<vector<int>> C(N, vector<int>(N));
    REP (i, 0, N) REP (j, 0, N) cin >> C[i][j];
    lli ans = 0;
    REP (i, 1, N) REP (j, 0, i) ans += min(C[i][j], C[j][i]);
    cout << ans << endl;
    return 0;
}

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

#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
#define ldb long double 
#define db double
#define int long long

#define fr first
#define se second
#define lb lower_bound 
#define ub upper_bound 
#define pb push_back
#define mpr make_pair

#define pi pair<int,int>
#define pdb pair<db,db>
#define pldb pair<ldb,ldb>

#define vi vector<int>
#define vdb vector<db>
#define vldb vector<ldb>
#define vpi vector< pi >

#define mi map<int,int>
#define mdb map<db,db>
#define mldb map<ldb,ldb>


#define forr(a,b) for (int i = (a); i < (b); ++i)
#define rrof(a,b) for (int i = (b)-1; i >= (a); --i)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int md = 1e9+7;
const int MX = 2e5+5;
const int INF = 1e18; 
const ldb PI = 4*atan((ldb)1);

int power_md(int a,int n)
{
 int res=1;
 while(n)
{
 if(n%2)
  res=(res%md*a%md)%md;
  a=(a%md*a%md)%md;
  n/=2;
}
res%=md;
return res;
}

int power(int a,int n)
{
 int res=1;
 while(n)
{
 if(n%2)
  res*=a;
  a=a*a;
  n/=2;
}
return res;
}

int abst(int a)
{
 return ((a<0)?(-1*a):(a));
}

class cmp_set{
public:
	bool operator() (int a, int b){
		return a > b;
	}
};

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

int32_t main()
{
   int arr[3];
    cin>>arr[0]>>arr[1]>>arr[2];
    sort(arr,arr+3);
    int res=(arr[0]*arr[1])/2;
    cout<<res<<"\n";
    return 0; 
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) std::cerr<< #x <<": "<<x<<"\n"
#define debug2(x,y) std::cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<"\n"
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv=vector<vector< T > >;

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size(); s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  s << "\n"; return s;
}

// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) { s << vv[i]; }
  return s;
}

int main() {
  int n, m, q;
  scanf("%d %d %d", &n, &m, &q);
  vvi imos(n+2, vi(n+1, 0));
  vvi lr(m, vi(2, 0));
  rep (i, m) {
    scanf("%d %d", &lr[i][0], &lr[i][1]);
    imos[lr[i][0] + 0][lr[i][1] - 0] += 1;
  }
  vvi pq(q, vi(2, 0));
  rep (i, q) {
    scanf("%d %d", &pq[i][0], &pq[i][1]);
//    pq[i][2] = i;
  }
//  vvi accum(n+1, vi(n+1, 0));
  for (int i = n; i >= 1; --i) {
    for (int j = 1; j <= n; ++j) {
      imos[i][j] = imos[i][j-1] + imos[i][j];
    }
  }
  for (int j = 1; j <= n; ++j) {
    for (int i = n; i >= 1; --i) {
      imos[i][j] = imos[i+1][j] + imos[i][j];
    }
  }

  rep (i, q) {
    printf("%d\n", imos[pq[i][0]][pq[i][1]]);
  }

  return 0;
}


Measured memory_bytes: 18304
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = list(map(int, input().split()))
u = 998244353

if A[0]!=0:
    print(0)
    exit()
dp = {}

for i in range(1,N):
    d = A[i]
    if d==0:
        print(0)
        exit()
    if d in dp:
        dp[d] +=1
    else:
        dp[d] = 1

M = max(A)
ans = 1
pre = 1
for i in range(1,M+1):
    if not i in dp:
        print(0)
        exit()
    k = dp[i]
    now = pre**k
    ans *= now
    ans %= u
    pre = k
print(ans)

Measured memory_bytes: 19552
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var myOut = main();
if(myOut !== undefined)console.log(myOut);

function main(){
  var n = next();
  var a = nexts(n);
  var s0 = 0, s1 = 0, p0 = [], p1 = [];
  for(var i = 0; i < n; i += 2)if(a[i] > 0)s0 += a[i], p0.push(i);
  for(var i = 1; i < n; i += 2)if(a[i] > 0)s1 += a[i], p1.push(i);
  if(s0 === 0 && s1 === 0)return minus(n,a);
  console.log(Math.max(s0,s1));
  if(s0 > s1)return solve(n,p0);
  return solve(n,p1);
}

function solve(n,p){
  var l = p.length-1, res = [];
  for(var i = n; i--;){
    if(l === 0){
      if(p[l] > i)res.push(1);
      else if(p[l] < i)res.push(i+1);
    }else{
      if(p[l] < i)res.push(i+1);
      else if(p[l]-2 === p[l-1]){
        res.push(p[l]);
        l--, i = p[l];
      }else{
        res.push(p[l]-1);
        p[l] -= 2;
        i = p[l];
      }
    }
  }
  console.log(res.length);
  return res.join("\n");
}

function minus(n,a){
  var id = 0, mx = a[0];
  for(var i = 1; i < n; i++){
    if(mx < a[i])mx = a[i], id = i;
  }
  var ans = [mx,n-1];
  for(var i = n; i--;){
    if(i === id)continue;
    if(i < id)ans.push(1);
    else ans.push(i+1);
  }
  return ans.join("\n");
}

Measured memory_bytes: 7884
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n,x = [int(i) for i in readline().split()]
n = int(input())
d = [[int(i) for i in readline().split()] for i in range(n)]
e = []
for i in range(n):
    for j in range(i+1,n):
        e.append((d[i][j],i,j))

e.sort()

ans = 0
for c,i,j in e:
    eq = 0
    for k in range(n):
        dk = d[k][i] + d[k][j]
        if dk < c:
            print(-1)
            exit()
        elif dk == c and k != i and k != j:
            eq = 1
    if eq: continue
    else: ans += c

            
print(ans)
    














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

string s;
long long n, q, k;
long long cnt[1000005][2] = {0};

long long solve();

int main() {
  cin >> n >> s >> q;
  for(long long i = 0; i < n; ++i) {
    if(i != 0) {
      cnt[i][0] = cnt[i - 1][0];
      cnt[i][1] = cnt[i - 1][1];
    }
    if(s[i] == 'D') ++cnt[i][0];
    if(s[i] == 'M') ++cnt[i][1];
  }
  for(long long i = 0; i < q; ++i) {
    cin >> k;
    cout << solve() << endl;
  }
  return 0;
}
long long solve() {
  long long now = 0, ans = 0;
  for(long long i = 0; i < n; ++i) {
    if(s[i] == 'M') {
      if(i != 0) now += cnt[i - 1][0];
      if(i >= k) now -= cnt[i - k][0];
    }
    if(s[i] == 'C') ans += now;
    if(i >= k - 1 && s[i - k + 1] == 'D') {
      if(i != 0) now -= cnt[i][1];
      now += cnt[i - k + 1][1];
    }
  }
  return ans;
}


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

int main() {
  int a,b;
  cin >> a >> b;
  int x = (a+b)/2;
  int y = (a+b)%2;
  if (y==0) {
    cout << x << endl;
  }
  else {
    cout << x+1 << endl;
  }
}

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

struct Edge{
	int a,b,cost;
	bool operator <(const Edge &a)const{
		return cost<a.cost;
	}
};

int par[100],rank_[100];

void init(int n){
	for(int i=0;i<n;i++) par[i] = i, rank_[i] = 1;
}

int find(int x){
	if(par[x]==x) return x;
	return par[x] = find(par[x]);
}

bool unite(int a_,int b_){
	int a = find(a_), b = find(b_);
	if(a==b) return false;
	if(rank_[a]<rank_[b]){
		par[a] = b;
	}
	else{
		par[b] = a;
		if(rank_[a]==rank_[b]) rank_[a]++;
	}
	return true;
}

int main(){
	int N,M;
	Edge e[10000];
	while(cin>>N>>M,N||M){
		init(N);
		for(int i=0;i<M;i++) cin>>e[i].a>>e[i].b>>e[i].cost;
		sort(e,e+M);
		int ans = 0;
		for(int i=0;i<M;i++){
			if(unite(e[i].a,e[i].b)) ans += e[i].cost;
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    int p = a, q = c;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    sort(v.begin(), v.end(), greater<>());
    for (int i = 0; i < n; ++i) {
        if(p*v[i] >= q*b) p += b, q += v[i];
        else break;
    }
    cout << q/p << "\n";
    return 0;
}



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

int main(){

    int n,sum=0;
    char s[9]={};

    cin>>s;

    n=atoi(s);
    for(int i=0;i<9;i++) if(s[i]>='0'&&s[i]<='9') sum+=s[i]-'0';

    if(n%sum==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;







    return 0;
}

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

int card[5];

int c[13];

void solve(){
	memset(c,0,sizeof(c));
	REP(i,5){
		c[card[i]-1]++;
	}
	bool f1=false,f2=false;
	REP(i,13){
		if (c[i]>=4){
			f1=true;
		}
	}
	if (f1){
		cout<<"four card"<<endl;
		return;
	}
	REP(i,13){
		if (c[i]==3){
			f1=true;
		}else if (c[i]==2){
			f2=true;
		}
	}
	if (f1 && f2){
		cout<<"full house"<<endl;
		return;
	}
	f1=f2=false;
	REP(i,10){
		bool f=true;
		REP(j,5){
			if (c[(i+j)%13]!=1){
				f=false;
			}
		}
		if (f){
			f1=true;
		}
	}
	if (f1){
		cout<<"straight"<<endl;
		return;
	}
	REP(i,13){
		if (c[i]==3){
			f1=true;
		}
	}
	if (f1){
		cout<<"three card"<<endl;
		return;
	}
	int k=0;
	REP(i,13){
		if (c[i]==2){
			k++;
		}
	}
	if (k==2){
		cout<<"two pair"<<endl;
	}else if (k==1){
		cout<<"one pair"<<endl;
	}else{
		cout<<"null"<<endl;
	}
}

int main(){
	while (scanf("%d,%d,%d,%d,%d",card,card+1,card+2,card+3,card+4)!=EOF){
		solve();
	}
	return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int H, W, K;
ll MOD = 1000000007;
ll dp[101][9];
ll twotothe[101];
ll fib[101];

int main() {
    twotothe[0] = 1;
    for (int i = 1; i < 101; i ++) {
        twotothe[i] = (twotothe[i - 1] * 2) % MOD;
    }
    fib[0] = 0, fib[1] = 1;
    for (int i = 2; i < 101; i ++) {
        fib[i] = (fib[i-1] + fib[i-2]) % MOD;
    }
    cin >> H >> W >> K;
    
    dp[0][1] = 1;
    for (int k = 2; k <= W; k ++) dp[0][k] = 0;

    for (int h = 1; h <= H; h ++) {
        for (int k = 1; k <= W; k ++) {
            if (k == 1) {
                dp[h][1] = (dp[h-1][1] * fib[W] % MOD + dp[h-1][2] * fib[W-1] % MOD) % MOD;
            } else if (k == W) {
                dp[h][W] = (dp[h-1][W] * fib[W] % MOD + dp[h-1][W-1] * fib[W-1] % MOD) % MOD;
            } else {
                dp[h][k] = 
                      (dp[h-1][k] * fib[k] % MOD * fib[W-k+1] % MOD
                     + dp[h-1][k-1] * fib[k-1] % MOD * fib[W-k+1] % MOD
                     + dp[h-1][k+1] * fib[k] % MOD * fib[W-k] % MOD) % MOD;
            }
        }
    }
    cout << dp[H][K] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ft first
#define sc second
#define pt(sth) cout << sth << "\n"
#define moca(a, s, b) a=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
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;}
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;


//for(i=0; i<N; i++) cin >> a[i];


int main(void) {
  ll i, j, k;
  
  ll N;
  cin >> N;
  
  
  ll ans=0;
  for(i=1; i<=N; i++) {
    ll c=N/i;
    ans+=i*c*(c+1)/2;
  }
  
  pt(ans);
}


Measured memory_bytes: 3648