akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

int main() {
    int a, b, c; cin >> a >> b >> c;
    
    for(int i=1; i<=b; i++){
        if((a*i)%b==c){
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


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


    int n;
    cin >> n;
    vector<int> W(n);
    for (int i = 0; i < n; ++i) {
        cin >> W[i];
    }

    vector<vector<int>> graph(n);
    for (int i = 0; i + 1 < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    int rt = 0;

    vector<int> res(n, 1);
    const int INF = 1e9 + 123;
    vector<int> mins(n + 1, INF);
    mins[0] = 0;
    function<void(int,int,int)> dfs = [&](int u, int p, int d) {
        int x = W[u];
        auto it = lower_bound(mins.begin(), mins.end(), x);
        int len = it - mins.begin();
        int bk = mins[len];
        mins[len] = x;
        it = lower_bound(mins.begin(), mins.end(), INF);
        int ans = it - mins.begin();
        res[u] = ans - 1;
        for (auto v : graph[u]) {
            if (v == p) {
                continue;
            }
            dfs(v, u, d + 1);
        }
        mins[len] = bk;
    };
    dfs(rt, -1, 0);

    for (int i = 0; i < n; ++i) {
        cout << res[i] << '\n';
    }

    return 0;
}

Measured memory_bytes: 36708
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const ll MOD=1e9+7;
vector<int> tree[100001];
ll dp[100001][2];// dp[i][j] no of ways to paint tree rooted at i with j constraint
// if j is 0 it means root i is under no constraint it can be black or white
// if i is 0 it means root i is allowed to color black only
int visited[100001];
ll solve(int i,int constraint,int pr){
	if(tree[i].size()==0 and constraint==0)
		return 2;
	if(tree[i].size()==0 and constraint==1)
		return 1;
	if(dp[i][constraint]!=-1){
		return dp[i][constraint];
	}
	ll w1=1;
	ll ans=0;
	for(int child:tree[i]){
		if(child!=pr)
		    w1=(w1*solve(child,0,i))%MOD;
	}
	ans+=w1;
	if(constraint==0){
	    ll w2=1;
	    for(int child:tree[i]){
		    if(child!=pr){
			    w2=(w2*solve(child,1,i))%MOD;
		    }
		}
		ans+=w2;
	}
	return dp[i][constraint]=ans%MOD;
}

int main()
{
    memset(dp,-1,sizeof(dp));
	int n=0;cin>>n;
	int s=0;int d=0;
	for(int i=0;i<n-1;++i)
	{
		cin>>s>>d;
		tree[s].push_back(d);
		tree[d].push_back(s);
	}
	cout<<solve(1,0,-1)%MOD<<'\n';
	return 0;
}

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

typedef long long ll;

ll N;
vector<pair<ll, ll>> BA, AI;

bool solve() {
  for (ll i = 0; i < N; ++i) {
    if (AI[i].first > BA[i].first) return false;
  }
  for (ll i = 0; i + 1 < N; ++i) {
    if (AI[i + 1].first <= BA[i].first) return true;
  }
  ll cnt = 0;
  for (ll i = 0; cnt == 0 || i != 0; ++cnt) {
    i = AI[i].second;
  }
  return cnt != N;
}
int main() {
  cin >> N;
  BA.resize(N);
  for (ll i = 0; i < N; ++i) cin >> BA[i].second;
  for (ll i = 0; i < N; ++i) cin >> BA[i].first;
  sort(BA.begin(), BA.end());
  AI.resize(N);
  for (ll i = 0; i < N; ++i) AI[i] = make_pair(BA[i].second, i);
  sort(AI.begin(), AI.end());
  cout << (solve() ? "Yes" : "No") << endl;
  return 0;
}


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

int main()
{
  vector<int> a(3);
  for(int i=0;i<3;i++) cin>>a[i];
  sort(a.begin(),a.end());
  for(int i=0;i<3;i++){
    if(i) cout<<' ';
    cout<<a[i];
  }
  cout<<endl;
}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;

int f(int n) {
    if (n % 2 == 0) {
        return n / 2;
    } else {
        return 3 * n + 1;
    }
}

int main() {
    int s; cin >> s;
    int cnt = 1;
    int n = s;
    
    if (n == 1) {
        cout << 4 << endl;
    } else if (n == 2) {
        cout << 4 << endl;
    } else {
        while (n != 4) {
            cnt++;
            n = f(n);
        }
    
        cout << cnt + 3 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    // それぞれの地点からスタート、mapで（現在位置、スタート）を保持
    // multisetで横移動の長さを保持
    int H, W;
    cin >> H >> W;

    map<int, int> mp;
    rep(i, W) mp[i] = i;
    multiset<int> vals;
    rep(i, W) vals.insert(0);

    rep(i, H) {
        int l, r;
        scanf("%d%d", &l, &r);
        --l;
        auto it = mp.lower_bound(l);
        int edge = -1; // lとrの中でスタートの右端
        while (it != mp.end() && it->first <= r) {
            edge = max(edge, it->second);
            int x = it->first - it->second;
            mp.erase(it++);
            vals.erase(vals.find(x));
        }
        if (edge >= 0 && r < W) {
            vals.insert(r-edge);
            mp[r] = edge;
        }
        if (vals.empty()) puts("-1");
        else {
            int ans = *vals.begin() + i + 1;
            printf("%d\n", ans);
        }        
    }
    return 0;
}


Measured memory_bytes: 22488
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod



signed main(){

    int N; cin >> N;
    vec A(N); cin >> A;

    int ans = 0;
    map<int, int> cnt;
    REP(i, N){
        ans += cnt[i - A[i]];
        cnt[i + A[i]] += 1;
    }
    Out(ans);

    return 0;
}


Measured memory_bytes: 27400
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define LINF 1e18
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
//typedef tuple<ll, ll, ll> T;

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


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


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double N,K;
    cin>>N>>K;
    double tmp=1/N;
    double cnt=0;
    double num=1;


    double ans=0;
    for(int i=1;i<=N;i++){
        if(i>=K){
            ans+=1/N;
            continue;
        }
        int num=i;
        int cnt=0;
        while(1){
            num*=2;
            cnt++;
            if(num>=K)break;
        }
        ans+=(1/N)*(double)(pow(0.5,cnt));
        //cout<<ans<<endl;
    }
    printf("%.13lf\n",ans);
}

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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
#define INF 1000000000000
#define MOD 1000000007
using ll = long long;

int main(){
  int N; cin >> N;
  double res = 0;
  if(N%2==0)res=0.5000;
  else{
    double odd = (N+1)/2;
    res = odd/N;
  }
  cout<<setprecision(10)<<res<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,d,x;
  cin>>n>>d>>x;
  int count=0;
  for(int i=0;i<n;i++){
      int a;
      int b=d;
      cin>>a;
      b--;
      count++;
      while(b>=a){
          b-=a;
          count++;

      }
  }
  cout<<count+x<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vll = vector<vl>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const ll INF = 2e15;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

ll evaluate(int contest,int date,vector<ll>&last,vector<ll>&c,vll&s){
  ll point_today = 0;
  point_today += s[date][contest];
  ll minus = 0;
  for (ll j=1; j <= 26;j++){
    minus += c[contest] * (date - last[contest]);
  }
  point_today -= minus;
  return point_today;
}

int main(){
  ll d;
  cin >> d;//全日数
  vl c(27);
  for(ll i=1;i<=26;i++){//c_i==c[i]
    cin >> c[i];
  }
  vll s(d + 1, vl(27)); //s_d,i==s[d][i]
  for (ll i = 1; i <= d; i++){
    for (ll j = 1; j <= 26;j++){
      cin >> s[i][j];
    }
  }
  vl t;
  vl last(27, 0);//last(d,i)==last[i]
  //ll satisfy = 0;
  for (ll date = 1; date <= d;date++){
    priority_queue<pair<ll, int>> q;
    for (ll contest = 1; contest <= 26;contest++){
      q.push(mp(evaluate(contest, date, last,c,s), contest));
    }
    t.pb(q.top().S);
    //satisfy += q.top().F;
    last[q.top().S] = date;
  }
  rep(i,d){
    print(t[i]);
  }
}

Measured memory_bytes: 3724
from math import factorial
n=int(input())
cnt=[0]*(n+1)
lst=list(map(int,input().split()))
for i in lst:
    cnt[i]+=1
ans=0
for i in range(n+1):
    p=cnt[i]
    if p>=2:
        ans+=factorial(p)//factorial(p-2)//2
for i in range(n):
    print(ans-cnt[lst[i]]+1)

Measured memory_bytes: 117760
#include<stdio.h>
int main(){
	int N, aa, A, S = 0;
	scanf("%d", &N);
	int a[N];
	for (int i = 0; i < N; i++){
		scanf("%d", &a[i]);
	}
	for (int j = 0; j < N; j++){
		A = a[j];
		for (int k = 0; k < 30; k++){
			aa = A % 2;
			if (aa == 1) break;
			A = A / 2;
			S += 1;
		}
	}
	printf("%d", S);
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
  char s[200001];
  int i=0;

  scanf("%s",s);

  while(s[i]=='P' || s[i]=='D' || s[i]=='?')
  {
    if(s[i]=='?') printf("D");
    else printf("%c",s[i]);
    i++;
  }

  printf("\n");

  return 0;
}

Measured memory_bytes: 1856
#include <bits/stdc++.h>
using namespace std;
void dfs (
    const vector<vector<pair<long long, int>>>& grh,
    vector<int>& col,
    int crr = 0,
    int prt = 0
  ) {
    for (auto const p : grh[crr]) {
      long long d; int nxt;
      tie(d, nxt) = p;
      if (nxt == prt) continue;
      col[nxt] = col[crr] ^ (d & 1);
      dfs(grh, col, nxt, crr);
    }
  } 
int main() {
  int n;
  cin >> n;
  vector<vector<pair<long long, int>>> grh(n);
  for (int i = 0; i < n - 1; i++) {
    int s, t; long long d;
    cin >> s >> t >> d;
    grh[--s].emplace_back(d, --t);
    grh[t].emplace_back(d, s);
  }
  vector<int> col(n); col[0] = 0;
  dfs(grh, col);
  for (int i = 0; i < n; i++) {
    cout << col[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 11264
function main(input){
  var _input = input.split('\n')
  var a500 = parseInt(_input[0]) 
  var b100 = parseInt(_input[1]) 
  var c50 = parseInt(_input[2]) 
  var total = parseInt(_input[3]) 
  var counter = 0
  var _total
  for (var a = 0; a <= a500 ; a++) {
    _total = 0
     for (var b = 0; b <= b100 ; b++) {
        for (var c = 0; c <= c50 ; c++) {
          _total = 500 * a + 100 * b + 50 * c
          if (_total === total) {
            counter++
            break
          }else if (_total > total) break
      }
        if (_total > total) break
    }
  }
  console.log(counter)
}


main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define REAP(i,a,n) for(int i=(a);i<(n);i++)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define fr first
#define sc second
#define pb push_back
#define All(v) v.begin(),v.end()
typedef long long ll;

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

    int a,b,c;
    cin >> a >> b >> c;
    if(a+b+c<22)cout << "win\n";
    else cout << "bust\n";

}


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int a, b, x, y;
    scanf("%d %d", &a, &b);
    if(1<=a && b<=100){
        x = a*b;
        y = 2*a + 2*b;
        printf("%d %d\n", x, y);
    }

    return 0;
}


Measured memory_bytes: 2060
l=list(map(int,input().split()))
l=sorted(l)
a=l[0]
b=l[1]
c=l[2]
count=0
count+=c-b
if (b-a)%2==0:
  count+=(b-a)//2
else:
  count+=(b-a+1)//2+1
print(count)
  

Measured memory_bytes: 3060
from collections import defaultdict
n,m = map(int,input().split())
l = [input().split() for _ in range(m)]
d = defaultdict(int)
count1=0 #正解数
count2=0 #ペナルティ数
for i in l:
    if i[1]=="WA" and d[i[0]]!= "OK":
        (d[i[0]]) += 1
    if i[1] =="AC"and d[i[0]]!= "OK":
        count1 += 1
        count2 += int(d[(i[0])])
        d[i[0]] ="OK"
print(count1,count2)

Measured memory_bytes: 41860
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

int n;

int main(){
	while(cin>>n){
		if(!n)return 0;
		int ans=0;
		for(int i=2;i<45;i++){
			if(i%2==0&&n%i==i/2&&n/i-i/2+1>0)ans++;
			if(i%2==1&&n%i==0&&n/i-i/2>0)ans++;
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	for(int i=0;i<s.size()-1;i++)
	{
		if(s[i]==s[i+1])
		{
			cout<<"Bad";
			return 0;
		}
	}
	cout<<"Good";
	return 0;
}


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

using namespace std;

#define il inline
#define re register
#define Rep(i, s, e) for (re int i = s; i <= e; ++i)
#define Dep(i, s, e) for (re int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)

typedef long long ll;
il ll max(ll x, ll y) {return x > y ? x : y;}

const ll mod = 1000000007;

il ll read() {
	ll x = 0; bool f = true; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = false; c = getchar();}
	while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	return f ? x : -x;
}

il ll qpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return res;
}

ll r1, r2, c1, c2, ans, n;
ll fac[2000010], inv[2000010];

il ll C(ll x, ll y) {
	if (x < y) return 0;
	return (fac[x] * inv[y] % mod) * inv[x - y] % mod;
}

int main() {
	r1 = read(), c1 = read(), r2 = read(), c2 = read();
	n = max(r2, c2) << 1 | 1, fac[0] = 1;
	Rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
	inv[n] = qpow(fac[n], mod - 2);
	Dep(i, n - 1, 0) inv[i] = inv[i + 1] * (i + 1) % mod;
	Rep(i, r1, r2) {
		ans = (ans + (C(i + c2 + 1, i + 1) - C(i + c1, i + 1) % mod)) % mod;
	}
	printf("%lld", (ans + mod) % mod);
	return 0;
}

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

int main(){
  int n,t;
  cin >> n >> t;
  int ans = 1e9+1;
  for(int i=0;i<n;++i){
    int u,v;  
    cin>>u>>v;
    if (v<=t) ans = min(ans,u);
  }
  if (ans == 1e9+1) cout << "TLE" << endl;
  else cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
int MOD = 1000000007;

int main() {
	for (;;) {
		int H, W; cin >> H >> W;
		if (H == 0 && W == 0) break;
		vector< vector<char> > a(H, vector<char>(W, '#'));
		for (int i = 1; i < H - 1; i++)
			for (int j = 1; j < W - 1; j++)
				a[i][j] = '.';
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++)
				cout << a[i][j];
			cout << endl;
		}
		cout << endl;
	}
}

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

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

	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;

	int x4 = x1 - (y2 - y1);
	int y4 = y1 + x2 - x1;
	int x3 = x4 + x2 - x1;
	int y3 = y4 + y2 - y1;

	cout << x3 << ' ' << y3 << ' ' << x4 << ' ' << y4 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <bitset>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define _CRT_SECURE_NO_WARNINGS
#define REP(i, n) for(LL i=0; i<(n); i++)
#define FOR(i, m, n) for(LL i=(m);i<(n);i++)
#define SZ(x) ((int)(x).size())
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define MP make_pair
#define PB push_back
#define INF INT_MAX

typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef long long LL;

int main() {
	int n, e = 0, o = 0;
	cin >> n;
	REP(i, n) {
		int x; cin >> x;
		if (x % 2 == 0)e++;
		else o++;
	}

	bool flag;
	if (o % 2 == 1)flag = false;
	else flag = true;
	puts(flag ? "YES" : "NO");
}

Measured memory_bytes: 256
li = list(map(int,input().split()))
a=li[0]
b=li[1]
k=li[2]

for i in range(1,k+1):
    if i%2==1:
        if a%2==0:
            a=a/2
            b=b+a
        else:
            a=(a-1)/2
            b=b+a
    else:
        if b%2==0:
            b=b/2
            a=a+b
        else:
            b=(b-1)/2
            a=a+b
print(int(a),int(b))


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<algorithm>
#include<cmath>
#include<tuple>
#include<iomanip>
#include<list>
#include<climits>
#include<sstream>
#define endl '\n'
#define ll long long
#define ld long double
#define sp fixed<<setprecision
#define bp __builtin_popcountll
#define mod 1000000007
#define mod1 998244353
#define PI acos(-1)
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	string str;
	cin>>str;
	ll ans=0;
	for(auto it:str)
	{
		ans += it-48;

	}
	if(ans%9)
	{
		cout<<"No";
	}
	else
	{
		cout<<"Yes";
	}
	
	return 0;
}

Measured memory_bytes: 3784
#include <cstdio>
#include <cstring>
#include <cmath>
#define EPS 1e-10
using namespace std;

double add(double a,double b){
	if(fabs(a+b)<EPS*(fabs(a)+fabs(b)))return 0;
	return a+b;
}

struct P{
	double x,y;
	P(double xx=0,double yy=0){
		x=xx;
		y=yy;
	}
	P operator +(P p){
		return P(add(x,p.x),add(y,p.y));
	}
	P operator -(P p){
		return P(add(x,-p.x),add(y,-p.y));
	}
	P operator *(double d){
		return P(x*d,y*d);
	}
	P operator /(double d){
		return P(x/d,y/d);
	}
	double abs(){
		return sqrt(norm());
	}
	double norm(){
		return x*x+y*y;
	}
};

typedef P Vector;
struct Segment{
	P p1,p2;
	Segment(P pp1=P(),P pp2=P()){
		p1=pp1;
		p2=pp2;
	}
};

double dot(Vector a,Vector b){
	return add(a.x*b.x,a.y*b.y);
}

double cross(Vector a,Vector b){
	return add(a.x*b.y,-a.y*b.x);
}

P getCrossPoint(Segment s1,Segment s2){
	Vector base=s2.p2-s2.p1;
	double d1=abs(cross(base,s1.p1-s2.p1));
	double d2=abs(cross(base,s1.p2-s2.p1));
	double t=d1/(d1+d2);
	return s1.p1+(s1.p2-s1.p1)*t;
}

int main(void){
	int q;
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		Segment s1,s2;
		scanf("%lf %lf",&s1.p1.x,&s1.p1.y);
		scanf("%lf %lf",&s1.p2.x,&s1.p2.y);
		scanf("%lf %lf",&s2.p1.x,&s2.p1.y);
		scanf("%lf %lf",&s2.p2.x,&s2.p2.y);
		P res=getCrossPoint(s1,s2);
		printf("%.10f %.10f\n",res.x,res.y);
	}
	return 0;
}

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

bool check_kaibun(string s);

int main(){
    string S;
    bool result = false;
    cin >> S;
    int N = S.size();

    if(check_kaibun(S)){
        if(check_kaibun(S.substr(0, N/2))){
            if(check_kaibun(S.substr((N+3)/2 - 1, N/2))){
                result = true;
            }
        }
    }
    if(result){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

bool check_kaibun(string s){
    bool result=true;
    for(int i=0; i<(s.size()/2); i++){
        if(s[i] != s[s.size()-1-i]){
            result = false;
        }
    }
    return result;
}

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

ll solve() {
    ll N, x = 0;
    cin >> N;
    vector<ll> A(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> A[i];
        if ( i >= 2 ) {
            x ^= A[i];
        }
    }
    // (A0-y)^(A1+y)==x となる最小のy<A0,y>=0
    // a = A0-y, b = A1+y 
    // => 2(a&(a^x))==A0+A1-x, 最大のa<=A0, a>0
    if ( A[0]+A[1] < x ) return -1;
    ll t = A[0] + A[1] - x;
    if ( t & 1 ) return -1;
    vector<ll> as(43,-1);
    for ( int i = 42; i >= 0; i-- ) {
        if ( (x >> i) & 1 ) {
            if ( (t >> (i+1)) & 1 ) return -1;
        } else {
            as[i] = (t >> (i+1)) & 1LL;
        }
    }
    ll a = 0;
    for ( int i = 42; i >= 0; i-- ) {
        if ( as[i] == 1 ) {
            a += 1LL << i;
        }
    }
    if ( a > A[0] ) return -1;
    for ( int i = 42; i >= 0; i-- ) {
        if ( as[i] == -1 ) {
            if ( a + (1LL<<i) <= A[0] ) {
                a += 1LL << i;
            }
        }
    }
    if ( a == 0 ) return -1;
    ll ans = A[0] - a;
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
const Int MAX = 2e18;

void chmin(Int &a,Int b){if(a>b) a=b;}

Int dfs(Int t,Int u,Int k){
  Int res=1LL<<(t-k);
  if(u!=3) res--;
  chmin(res,MAX);
  return res;
}

void restore(Int n){
  Int k=1;
  for(;;k++){
    Int tmp=0;
    for(Int a=0;a<10;a++){
      for(Int b=a+1;b<10;b++){
	if(a!=0) tmp+=dfs(k,1,1); //use a
	tmp+=dfs(k,2,1);          //use b > 0
	chmin(tmp,MAX);
      }
    }
    if(tmp>n) break;
    n-=tmp;
  }
  Int c,d;
  string ans;
  for(c=1;c<10;c++){
    Int tmp=0;
    for(Int a=0;a<c;a++){
      tmp+=dfs(k,2,1);
      chmin(tmp,MAX);
    }
    for(Int b=c+1;b<10;b++){
      tmp+=dfs(k,1,1);
      chmin(tmp,MAX);
    }
    if(tmp>n){
      ans+=char('0'+c);
      break;
    }
    n-=tmp;
  }
  Int l=k-1;
  while(l--){
    Int flg=0;
    for(d=0;d<c;d++){
      Int tmp=dfs(k,3,k-l);
      if(tmp>n){
	ans+=char('0'+d);
	flg=1;
	break;
      }
      n-=tmp;
    }
    if(flg) break;
    Int tmp=0;
    for(Int e=0;e<c;e++){
      tmp+=dfs(k,2,k-l);
      chmin(tmp,MAX);
    }
    for(Int e=c+1;e<10;e++){
      tmp+=dfs(k,1,k-l);
      chmin(tmp,MAX);
    }
    if(tmp>n){
      ans+=char('0'+c);
      continue;
    }
    n-=tmp;
    for(d=c+1;d<10;d++){
      Int tmp=dfs(k,3,k-l);
      if(tmp>n){
	ans+=char('0'+d);
	flg=1;
	break;
      }
      n-=tmp;
    }
    if(flg) break;
  }
  while(l--){
    if(c<d){
      Int tmp=dfs(k,3,k-l);
      if(tmp>n){
	ans+=char('0'+c);
      }else{	
	ans+=char('0'+d);
	n-=tmp;
      }
    }else{
      Int tmp=dfs(k,3,k-l);
      if(tmp>n){
	ans+=char('0'+d);
      }else{	
	ans+=char('0'+c);
	n-=tmp;
      }
    }
  }
  cout<<ans<<endl;
}
signed main(){
  Int n;
  while(cin>>n,n){
    restore(n-1);
  }
  return 0;
}



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

char in[120];
pair<pair<string,int>,int>p[110];
int main (){
    int a; scanf("%d",&a);
    for(int i=0;i<a;i++){
        int t; scanf("%s%d",in,&t);
        string tmp=in;
        p[i]=make_pair(make_pair(in,-t),i);
    }
    sort (p,p+a);
    for (int i=0;i<a;i++)printf("%d\n",p[i].second+1);
} 

Measured memory_bytes: 256
<?php
/**
 * ABC124
 * B - Great Ocean View
 */

$n = trim(fgets(STDIN));
$h_list = array_map('intval', explode(' ', trim(fgets(STDIN))));
$last_h = $h_list[0];
$result = 0;

foreach ($h_list as $h) {
    if ($h >= $last_h) {
        $last_h = $h;
        $result++;
    }
}
 
echo $result, PHP_EOL;


Measured memory_bytes: 4856
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<int, lint> pil;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(const T a, const T b){return a>=0 ? a/b : (a+1)/b-1;}
template<class T> T div_ceil(const T a, const T b){return a>=0 ? (a-1)/b+1 : a/b;}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod*mod;
constexpr int MAX = 100010;

int main(){
    int n;
    while(scanf("%d", &n) && n){
        string a[n];
        rep(i, n) cin >> a[i];
        int low = -mod, high =mod;
        bool flag = true;
        rep(i, n) {
            if (a[i] == "x") {
                if (i % 2 == 0) {
                    if (i - 1 >= 0) {
                        if (a[i - 1] == "x") {
                            flag = false;
                            break;
                        } else chmin(high, stoi(a[i - 1]));
                    }
                    if (i + 1 < n) {
                        if (a[i + 1] == "x") {
                            flag = false;
                            break;
                        } else chmin(high, stoi(a[i + 1]));
                    }
                } else {
                    if (i - 1 >= 0) {
                        if (a[i - 1] == "x") {
                            flag = false;
                            break;
                        } else chmax(low, stoi(a[i - 1]));
                    }
                    if (i + 1 < n) {
                        if (a[i + 1] == "x") {
                            flag = false;
                            break;
                        } else chmax(low, stoi(a[i + 1]));
                    }
                }
            }
            else{
                if(i%2 == 0 && i+1 < n && a[i+1] != "x"){
                    if(stoi(a[i]) >= stoi(a[i+1])){
                        flag = false;
                        break;
                    }
                }
                else if(i%2 == 1 && i+1 < n && a[i+1] != "x"){
                    if(stoi(a[i]) <= stoi(a[i+1])){
                        flag = false;
                        break;
                    }
                }
            }
        }
        if(!flag || high-low <= 1) puts("none");
        else if(high-low > 2) puts("ambiguous");
        else printf("%d\n", low+1);
    }
}


Measured memory_bytes: 3336
n,m = map(int,input().split())
sc = [list(map(int,input().split())) for i in range(m)]
tmp = [-1]*n
for j in range(m):
         if tmp[(sc[j][0]-1)] != sc[j][1]:
                  if tmp[(sc[j][0]-1)] != -1:
                           print(-1)
                           exit()
         tmp[(sc[j][0]-1)] = sc[j][1]
if len(tmp) == 1:
         if tmp[0] == -1:
                  tmp[0] = 0
         print(tmp[0])
         exit()
elif tmp[0] == 0:
         print(-1)
         exit()
else:
         if tmp[0] == -1:
                  tmp[0] = 1
         for k in range(1,n):
                  if tmp[k] == -1:
                           tmp[k] = 0
         ans = map(str,tmp)
         answer= "".join(ans)
         print(answer)


Measured memory_bytes: 3064
import random


def slv(N, C, X, V):
    ans_l = [(0, 0)]
    ans_l_ = [0]
    for x, v in zip(X, V):
        ans_l_.append(max(ans_l_[-1], ans_l[-1][1] + v - x))
        ans_l.append((x, ans_l[-1][1] + v))
    ans_l_.pop(0)
    ans_l.pop(0)

    ans_r = [(0, 0)]
    ans_r_ = [0]
    for x, v in list(zip(X, V))[::-1]:
        ans_r_.append(max(ans_r_[-1], ans_r[-1][1] + v - (C-x)))
        ans_r.append((C-x, ans_r[-1][1] + v))
    ans_r_.pop(0)
    ans_r.pop(0)
        

    # print('p1')

    ans_l_r = []
    for i, a in enumerate(ans_l[:-1], 1):
        # print(ans_r_[N-i-1],  a[1]-2*a[0])
        ans_l_r.append(ans_r_[N-i-1] + a[1]-2*a[0])

    # print('p2')
    ans_r_l = []
    for i, a in enumerate(ans_r[:-1], 1):
        # print(ans_l_[N-i-1],  a[1]-2*a[0])
        ans_r_l.append(ans_l_[N-i-1] + a[1]-2*a[0])

    l = max([x[1]-x[0] for x in ans_l])
    r = max([x[1]-x[0] for x in ans_r])
    lr = 0 if not ans_l_r else max(ans_l_r)
    rl = 0 if not ans_r_l else max(ans_r_l)

    # print(ans_l)
    # print(ans_l_)
    # print(ans_r)
    # print(ans_r_)

    # print(l, r, lr, rl)
    return max(l, r, lr, rl)



def main():
    N, C = list(map(int, input().split()))
    X = []
    V = []
    for _ in range(N):
        x, v = list(map(int, input().split()))
        X.append(x)
        V.append(v)

    # N = 100000
    # C = 1000000000000
    # X = [1]
    # V = [100]
    # for _ in range(N):
    #     X.append(X[-1]+random.randint(1, 10000))
    #     V.append(random.randint(1, 10000))

    print(slv(N, C, X, V))


if __name__ == '__main__':
    main()

Measured memory_bytes: 57816
#include <bits/stdc++.h>                                                                     
                                                                                             
using namespace std;                                                                         
                                                                                             
#define all(x) x.begin(), x.end()                                                            
#define rep(i, n) for (int i = 0; i < n; ++i)                                                
#define reps(i, m, n) for (int i = m; i <= n; ++i)                                           
                                                                                             
using i64 = long long;                                                                       
using pii = pair<i64, i64>;                                                                  
                                                                                             
template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}   
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}   
                                                                                             
constexpr int INF = 0x3f3f3f3f;                                                              
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;                                                   
constexpr int MOD = int(1e9) + 7;                                                            
                                                                                             
signed main()                                                                                
{                                                                                            
  ios::sync_with_stdio(false);                                                               
  cin.tie(nullptr);                                                                          
  char c;                                                                                    
  cin >> c;                                                                                  
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') cout << "vowel" << "\n";     
  else cout << "consonant" << "\n";                                                          
  return 0;                                                                                  
}                                                                                            


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
//#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
//#include <queue>

using namespace std;
#define n_max 10000
#define INF 10001000

#define rep(i, a, n) for(int i = a; i < n; i++)
#define rep2(i, a, n) for(int i = a; i <= n; i++)
#define rrep(i, a, n) for(int i = a; i > n; i--)
#define rrep2(i, a, n) for(int i = a; i >= n; i--)
#define lrep(i, a, n) for(long int i = a; i < n; i++)
#define in(a) cin >> a
#define out(a) cout << a << endl

int main()
{
    string s;

    cin >> s;

    if(s == "Sunny") { cout << "Cloudy" << endl; }
    if(s == "Cloudy") { cout << "Rainy" << endl; }
    if(s == "Rainy") { cout << "Sunny" << endl; }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
typedef long long ll;
#define tr(container, it) \
        for (auto it = container.begin(); it != container.end(); it++)
#define scontains(c, x) ((c).find(x) != (c).end())   //O(log n)
#define contains(c, x) (find((c).begin(),(c).end(),x) != (c).end()) //O(n)
#define ill(_x)  ll _x;scanf("%lld",&_x);
#define idb(_x)  double _x;scanf("%lf",&_x);
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define sll set<ll>
#define vs vector<string>
#define in0(x, a, b)((x)>=a && (x)<=b    )
#define in1(x, a, b)((x)>a && (x)<b)
#define  rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const double pi = 3.14159265358979323846;
const int INF = 0x3f3f3f3f;
const int X10=1024,X11=2048,X12=4096,X13=8196,X14=16392,X15=32786,X16=65536,X17=131072,X18=262144,X19=524288,X20=1048576;

int T[10001];
void _(){
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        ll a, b ,c ,d;
        ll n;
        cin >> a >> b >> c >> d;
        ll m = __gcd(b,d);
        if(b>d){cout << "No" <<endl;}
        else {
            if(a  > c){
                n=  (a - c -1)/m ;
                if(a - n*m < b){cout << "No" <<endl;
                    continue;}
                else cout << "Yes" <<endl;

            }
            else {
                if(a<b)cout << "No"<<endl;
                else {
                    a = a+c-b;
                    n=  (a - c -1)/m +1;
                    if(a - n*m < b){cout << "No" <<endl;
                        continue;}
                    else cout << "Yes" <<endl;
                }
            }
        }
    }
}






int main() {
#ifdef Debug
    freopen("/home/joduskame/Desktop/cpp/IO/Input.txt", "r", stdin);
    freopen("/home/joduskame/Desktop/cpp/IO/Output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    _();
    return 0;

}








Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define t(x) x==1?14:x
int main(){
	int a,b;
	cin>>a>>b;
	a=t(a);b=t(b);
	if(a>b)cout<<"Alice\n";
	else if(a<b)cout<<"Bob\n";
	else cout<<"Draw\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
#define pb push_back
#define pi pair<int,int>
#define pii pair<int,pi>
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int n,ans,a[200100],mn=1e6;
int main()
{
    go;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        ans+=(mn>x);
        mn=min(x,mn);
    }
    cout<<ans;
    return 0;
}


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

int main()
{
  int n, bidx, flr, ro, v;

  int buil[4][3][10] = { 0 };

  cin >> n;
  for( int i = 0; i < n; i++ ) {
    cin >> bidx >> flr >> ro >> v;
    buil[ bidx - 1 ][ flr - 1 ][ ro - 1 ] += v;
  }

  for( int i = 0; i < 4; i++ ) {
    for( int j = 0; j < 3; j++ ) {
      for( int k = 0; k < 10; k++ ) {
        cout << " " << buil[ i ][ j ][ k ];
      }
      cout << endl;
    }
    if( i == 3 ) {
      continue;
    }
    for( int l = 0; l < 20; l++ ) {
      cout << "#";
    }
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 3080
h,w = map(int,input().split())
mapl = [list(input()) for i in range(h)]
searched = [[0 for i in range(w)] for j in range(h)]
s_queue = []
move = ((0,1),(1,0),(-1,0),(0,-1))
def bfs():
    cnt=1
    s_queue.append([0,0,cnt])
    searched[0][0] = 1
    while(len(s_queue)>0):
        y,x,cnt=s_queue.pop(0)
        for a,b in move:
            ny = y+a
            nx = x+b
            if(ny<0 or ny>=h or nx<0 or nx>=w or mapl[ny][nx]=='#'):
                continue
            if(searched[ny][nx]==1):
                continue
            s_queue.append([ny,nx,cnt+1])
            searched[ny][nx]=1
            if(ny==(h-1) and nx==(w-1)):
                return cnt+1
    return -1

cnt = bfs()
if(cnt==(-1)):
    print(cnt)
else:
    dot_c = sum(map(lambda x:x.count('.'),mapl))
    print(dot_c-cnt)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
const double pi=acos(-1.0);
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int main(void){
    int n;
    cin>>n;
    int cnt=0;
    vector<int> a(110);
    rep(i,n+1)cin>>a.at(i+1);
    rep(i,n+1)if((i+1)%2==1&&a.at(i+1)%2==1)cnt++;
    cout<<cnt<<endl;
}

Measured memory_bytes: 3628
iN ,iM = [int(_) for _ in input().split()]
sS = input().rstrip()
sT = input().rstrip()

def fgcd(a,b):
    if b :
        return fgcd(b,a%b)
    else:
        return a

iD = fgcd(iN,iM)

if sS[0::iN//iD] == sT[0::iM//iD]:
    print(iN*iM//iD)
else:
    print("-1")


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

template<typename T>
void trace(T *a, int s, int n) {
    for (int i=s; i<n; i++) {
	cout<<a[i]<<" ";
    }
    cout<<endl;
}



typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;


int n;
ll x,d;

ll asum(ll i) {
    return i*(i+1)/2;
}

map<ll, vector<pair<ll,ll>>> mp;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>x>>d;
    
    if (d == 0 && x == 0) {
	out(1); //0
    }

    if (d == 0 && x != 0) {
	out(n+1);
    }

    if (x == 0 && d != 0) {
	out(asum(n-1) + 1);
    }



    assert(x!=0 && d!=0);

    


    //[X*take + sum_{i=0..take-1}i*D ...... X*take + sum{i=n-l..n-1}i*D]
    //count "collisions" modulo D, the arithmetic part won't change the modulo
    
    // # of elems that set S will take
    for (ll take=0; take<=n; take++) {
	ll base = x*take;

	ll losum = asum(take-1);
	ll hisum = asum(n-1) - asum(n-take-1);

	mp[base%d].push_back({base/d + losum, base/d + hisum});
    }

    // for (auto p: mp) {
    // 	watch(p.first);
    // 	for (auto i: p.second) {
    // 	    cout<<i.first<<" "<<i.second<<", ";
    // 	}
    // 	cout<<endl;
    // }


    ll ans = 0;


    for (auto p: mp) {
	auto v = p.second;
	assert(v.size());
	sort(v.begin(), v.end());
	pair<ll,ll> cur=v.front();
	for (int i=1; i<(int)v.size(); i++) {
	    ll s=v[i].first; ll e=v[i].second;
	    if (s<=cur.second) {
		cur.second=max(cur.second,e);
	    } else {
		ans += cur.second-cur.first+1;
		cur=v[i];
	    }
	}
	ans += cur.second-cur.first+1;
    }


    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 22144
// 2009ツアツジツアツ地ツ凝ヲツ予ツ選 D : Separate Points
#include <iostream>
#include <fstream>
#include <complex>
#include <vector>
#include <algorithm>

using namespace std;

const double EPS = 1e-8;

typedef complex<double> P;

struct L { P p, q; L(P p, P q) : p(p), q(q) {} };

double dot(P a, P b){ return real(conj(a)*b); }
double cross(P a, P b){ return imag(conj(a)*b); }
double angle(P a, P b){ return arg(conj(a)*b); }

bool compare(const P &a, const P &b){
	return make_pair(real(a),imag(a)) < make_pair(real(b),imag(b));
}

vector<P> convexHull(vector<P> vp){
	if(vp.size() < 3) return vp;
	sort(vp.begin(), vp.end(), compare);
	vector< pair<double,int> > vi;
	for(int i=1;i<vp.size();i++) vi.push_back(make_pair(angle(P(1,0),vp[i]-vp[0]), i));
	sort(vi.begin(), vi.end());
	vector<P> res(2);
	res[0] = vp[0]; res[1] = vp[vi[0].second];
	for(int i=1;i<vi.size();i++){
		P next = vp[vi[i].second];
		int sz = res.size();
		while(sz>=2&&cross(res[sz-1]-res[sz-2],next-res[sz-1])<EPS){
			res.pop_back(); sz--;
		}
		res.push_back(next);
	}
	return res;
}

bool ssIntersect(L a, L b){
	if(imag((a.q-a.p)/(b.q-b.p))<EPS) return false;
	return cross(a.q-a.p,b.p-a.p)*cross(a.q-a.p,b.q-a.p)<EPS&&
		   cross(b.q-b.p,a.p-b.p)*cross(b.q-b.p,a.q-b.p)<EPS;
}

bool contain(vector<P> vp, P p){
	if(vp.size()==1) return false;
	bool in = false;
	for(int i=0;i<vp.size();i++){
		P a = vp[i]-p, b = vp[(i+1)%vp.size()]-p;
		if(imag(a) > imag(b)) swap(a,b);
		if(imag(a) < EPS && EPS < imag(b))
			if(cross(a,b) < 0) in = !in;
		if(abs(cross(a,b))<EPS&&dot(a,b)<EPS) return true;
	}
	return in;
}

bool separate(vector<P> a, vector<P> b){
	if(a.size()!=1&&b.size()!=1)
		for(int i=0;i<a.size();i++)
			for(int j=0;j<b.size();j++)
				if(ssIntersect(L(a[i],a[(i+1)%a.size()]),L(b[j],b[(j+1)%b.size()]))) return false;
	for(int i=0;i<a.size();i++)
		if(contain(b, a[i])) return false;
	for(int i=0;i<b.size();i++)
		if(contain(a, b[i])) return false;
	return true;
}

int main(){
	int n, m;
	while(cin >> n >> m, n){
		int x, y;
		vector<P> black, white;
		for(int i=0;i<n;i++){ cin >> x >> y; black.push_back(P(x,y)); }
		for(int i=0;i<m;i++){ cin >> x >> y; white.push_back(P(x,y)); }
		cout << (separate(convexHull(black), convexHull(white)) ? "YES" : "NO") << endl;
	}
}

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

using namespace std;

int main() {
    int N;
    cin >> N;
    std::vector<long> A(N);
    std::vector<long> maxA(N);
    std::vector<long> minA(N);
    
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    long M = A[0];    
    for (int i = 0; i < N; i++) {
        M = min(M, A[i]);
        minA[i] = M;
    }
    
    long m = long(INT_MIN)*2L;
    for (int i = N-1; i >= 0; i--) {
        maxA[i] = m;
        m = max(m, A[i]);
    }
   
    M = LONG_MIN;
    for (int i = 0; i < N; i++) {
        if (M < maxA[i] - minA[i]) {
            //cerr << "i="<< i << ", " << maxA[i] << " - " << minA[i] << endl;
        }
        M = max(M, maxA[i]-minA[i]);
    }
    cout << M << endl;
    
}


Measured memory_bytes: 7524
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T> struct factorizaion {
    using NP = pair<T,int>;
    T n;
    explicit factorizaion(T n):n(n) {
        assert(n > 0);
    }
    vector<NP> factorlist() {
        if(n == 1) return {};
        T nn = n;
        vector<NP> ret;
        T i = 2;
        while (i*i <= n) {
            if(nn%i == 0) {
                nn /= i;
                if(!ret.empty() && ret[ret.size()-1].first == i) ret[ret.size()-1].second++;
                else ret.emplace_back(i,1);
            } else i++;
        }
        if(nn != 1) ret.emplace_back(nn,1);
        return ret;
    }
    bool isprime() {
        auto v = factorlist();
        return v.size() == 1 && v[0].second == 1;
    }
    int divisor() {
        int ret = 1;
        vector<NP> fl = factorlist(n);
        for(auto p : fl) {
            ret *= p.second+1;
        }
        return ret;
    };
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    if(n == 1) {
        cout << 0 << endl;
        return 0;
    }
    int ans = 0;
    map<int,int> m;
    rep2(i,2,50) {
        if(!factorizaion<int>(i).isprime()) continue;
        int sum = 0;
        int now = i;
        while(now <= n) {
            sum += n/now;
            now *= i;
        }
        if(sum > 0) m.insert({i,sum});
    }
    // (74+1)
    if(m[2] >= 74) ans++;
    // (2+1)(24+1)
    int n2 = 0,n24 = 0;
    for(auto p : m) {
        if(p.second >= 24) n24++;
        if(p.second >= 2) n2++;
    }
    ans += n24*(n2-1);
    // (4+1)(14+1)
    int n4 = 0,n14 = 0;
    for(auto p : m) {
        if(p.second >= 14) n14++;
        if(p.second >= 4) n4++;
    }
    ans += n14*(n4-1);
    // (2+1)(4+1)(4+1)
    ans += n4*(n4-1)/2*(n2-2);
//    cout << n4 << endl;

    cout << ans << endl;
}


Measured memory_bytes: 256