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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) (int)((a).size())
#define all(c) (c).begin(), (c).end()
#define debug(v) {for (auto z : v) {cerr << z << ' ';} cerr << endl;}

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

const ll MOD = 1e9 + 7;

int dist(const vi& a, int avg) {
	int r = 0;
	for (int x : a) r += (x - avg) * (x - avg);
	return r;
}

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	int n; scanf("%d", &n);
	vi a(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	int avg = accumulate(all(a), (double)0) / n;
	int ans = min(dist(a, avg), dist(a, avg+1));
	printf("%d\n", ans);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;
const int INF = 1001001001;

int main() {
    double r;
    cin >> r;
    r *= 2 * M_PI;
    printf("%.6f\n", r);
}


Measured memory_bytes: 3784
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<sstream>
#define ll long long
#define mes(x,y) memset(x,y,sizeof(x))
using namespace std;
int main(){
    double a,b;
	while(cin>>a>>b){
		if(a>=13){
			cout<<b<<endl;
		}
		if(a>=6&&a<=12){
			cout<<b/2<<endl;
		}
		if(a>=0&&a<=5){
			cout<<"0"<<endl;
		}
	} 
}

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

using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin >> n;
	ll a[n];
	ll maxi=0;
	rep(i,0,n){
		cin >> a[i];
		maxi=max(maxi,a[i]);
	}
	ll x=maxi/2;
	ll mini=inf;
	ll z;
	for(ll i=0; i<n; i++){
		if(abs(x-a[i])<mini && a[i]<maxi){
			mini=abs(x-a[i]);
			z=a[i];
		}
	}
	cout << maxi << " " << z;
	return 0;
}
/* The judge is never wrong! Your code is buggy
   Look for:
 * * Read the problem carefully.
 * * Don't forget to sort(), mod, ll!!!!
 * * Initial value = +/- infinity instead of zero!!!
 * * an easier and alternate approach
 * * read the problem statement carefully
 * * if concept is correct and still WA, try with a different implementation
 * * special cases (n=1?)
 * * overflow (ll vs int?)
 * * array bounds
 * * if you have no idea just guess the appropriate well-known algorithm instead of doing nothing :/
 */


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    string n;
    int k, z = 0;
    cin >> n >> k;
    int m = (int)n.length();
    if (k == 1) {
        z = (m - 1) * 9;
    } else if (k == 2) {
        if (m >= 2) z = (m - 1) * (m - 2) / 2 * 81;
    } else {
        if (m >= 3) z = (m - 1) * (m - 2) * (m - 3) / 6 * 729;
    }
    if (k == 1) {
        for (int i = 1; i <= 9; i++) {
            string t;
            t += (char)('0' + i);
            while (t.length() < m) t += '0';
            if (t <= n) z++;
        }
    } else if (k == 2) {
        for (int i = 1; i <= 9; i++) {
            string t;
            t += (char)('0' + i);
            while (t.length() < m) t += '0';
            for (int j = 1; j < m; j++) for (int g = 1; g <= 9; g++) {
                t[j] = g + '0';
                if (t <= n) z++;
                t[j] = '0';
            }
        }
    } else {
        for (int i = 1; i <= 9; i++) {
            string t;
            t += (char)('0' + i);
            while (t.length() < m) t += '0';
            for (int j = 1; j < m; j++) for (int g = 1; g <= 9; g++) {
                for (int k = j + 1; k < m; k++) for (int h = 1; h <= 9; h++) {
                    t[j] = g + '0';
                    t[k] = h + '0';
                    if (t <= n) z++;
                    t[j] = '0';
                    t[k] = '0';
                }
            }
        }
    }
    cout << z;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define ll_MAX LONG_LONG_MAX
#define ll_MIN LONG_LONG_MIN
#define pi pair<int,int>
#define endl "\n"
#define MAXN 100005
#define mod 1000000007
using namespace std;

void solve()
{
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    solve();
    ll n;
    cin>>n;
    ll h[n];
    for (ll i = 0; i < n; i++)
    {
        /* code */
        cin>>h[i];
    }
    vector<ll> dp(n, 1e10);
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for(ll i=2; i<n; i++)
    {
        dp[i] = min(dp[i - 2] + abs(h[i] - h[i - 2]), dp[i-1] + abs(h[i] - h[i-1]));
        // cout<<dp[i]<<'\n';
    }
    cout<<dp[n-1]<<'\n';
}

Measured memory_bytes: 4780
o = list(input())
e = list(input())
s = []
t = ""
if len(o+e) % 2 == 0:
    for i in range(int(len(o+e)/2)):
        s.append(o[i]+e[i])
    t = t.join(s)
else:
    for i in range(int(len(o+e)/2)):
        s.append(o[i]+e[i])
    t = t.join(s)
    t = t + o[int(len(o+e)/2)]

print(t)


Measured memory_bytes: 9112
from collections import deque
sa = deque(list(input()))
sb = deque(list(input()))
sc = deque(list(input()))
tmp = sa.popleft()
for _ in range(len(sa)+len(sb)+len(sc)):
    if tmp=='a':
        if sa==deque([]):
            print('A')
            exit()
        else:
            tmp = sa.popleft()
    if tmp=='b':
        if sb==deque([]):
            print('B')
            exit()
        else:
            tmp = sb.popleft()
    if tmp=='c':
        if sc==deque([]):
            print('C')
            exit()
        else:
            tmp = sc.popleft()

Measured memory_bytes: 3444
#include<iostream>
#include <string>

using namespace std;

int main() {
	int a, b, t, mai = 0;
	int i;
	cin >> a >> b >> t;
	for (i = a; i <= t; i += a) {
		mai += b;
	}
	cout << mai << endl;
	return 0;
}

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

# print(A)

B = [0 for i in range(len(A))]

for i in range(len(A)):
    B[i] = A[i] % M

# print(B)

acu = [0 for i in range(len(A))]

for i in range(len(A)):
    if i == 0:
        acu[i] = B[i]
    else:
        acu[i] = (acu[i - 1] + B[i]) % M

# print(acu)

modlist = {0:1}

for i in acu:
    if i in modlist.keys():
        modlist[i] = modlist[i] + 1
    else:
        modlist[i] = 1

sum = 0


def comb(n, r):
    top = 1
    bot = 1
    for i in range(r):
        top = top * (n - i)
        bot = bot * (i + 1)
    return (top / bot)


for i in modlist.keys():
    if modlist[i] >= 2:
        sum = sum + comb(modlist[i], 2)

print(int(sum))


Measured memory_bytes: 17064
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=200000+10;
int n;
ll a[maxn];
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    ll sum=0;
    for(int i=1; i<=n; i++)
        sum+=a[i];
    ll res=0;
    int i;
    for( i=1; i<=n; i++)
    {
        res+=a[i];
        if(res>=sum/2)
            break;
    }
    if(res==sum/2)
        printf("0\n");
    else
    {
        ll ans1=(res-(sum-res));
        ll ans2=(sum-res+a[i])-(res-a[i]);
        cout<<min(ans1,ans2)<<endl;

    }
    return 0;

}


Measured memory_bytes: 1792
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def my_round(a,dig=0):
    p = 10 ** dig
    return (a * p * 2 + 1) // 2 / p

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    a = [x for x in map(int,input().split())]
    ans = 0
    x = []
    x.append(abs(a[0]-a[1]))
    x.append(abs(a[1]-a[2]))
    x.append(abs(a[0]-a[2]))
    x.sort()
    for i in range(2):
        ans += x[i]
    print(ans)
    return

if __name__=='__main__':
    main()


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

using namespace std;

char mat[2][55];
long long D[55];

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


    int n;
    cin >> n;
    cin.ignore(); // ignore newline

    for (int i = 0; i < 2; ++i) {
        cin >> mat[i] + 1;
        cin.ignore();
    }

    D[1] = 3;

    if (mat[1][1] != mat[0][1]) {
        D[1] <<= 1;
    }

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

    for (int i = 2; i <= n; ++i) {
        D[i] = D[i - 1];

        if (mat[0][i] == mat[0][i - 1] && mat[1][i] == mat[1][i - 1]) {
            continue;
        }

        if (mat[0][i] == mat[1][i]) { // Vertical
            if (mat[0][i - 1] == mat[1][i - 1]) { // Vertical
                D[i] *= 2LL;
            }
            else { // Horizontal
                D[i] *= 1LL;
            }
        }
        else { // Horizontal
            if (mat[0][i - 1] == mat[1][i - 1]) { // Vertical
                D[i] *= 2LL;
            }
            else { // Horizontal
                D[i] *= 3LL;
            }
        }

        D[i] %= MOD;
    }

    cout << D[n];

    return 0;
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */


#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#include <numeric>
#include <iterator>

#define SIZE 100005
#define MOD 1000000007
#define INF 100000000

using namespace std;

class CManyFormulas {
public:
    void dfs(int n, vector<bool> plus) {
        if (n == s.size()) {
            string tmp = "";
            long long int tmp_sum = 0;
            vector<char> vec;
            for (int i = 0; i < s.size(); ++i) {
                tmp += s[i];
                if (plus[i]) {
                    tmp_sum += stol(tmp);
                    tmp = "";
                }
            }
            tmp_sum += stol(tmp);
            ans += tmp_sum;
            return;
        }
        dfs(n + 1, plus);
        plus[n-1] = true;
        dfs(n + 1, plus);
    }

    void solve(std::istream &cin, std::ostream &cout) {
        cin >> s;
        ans = 0;
        vector<bool> plus;
        plus.resize(s.size(), false);
        dfs(1, plus);
        cout << ans << endl;
    }

    string s;
    long long int ans;
};


int main() {
    CManyFormulas solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
(k, a, b) = map(int, input().split())
n = 1
if a > b-2:
    n += k
else:
    k1 = k
    while k1 > 0:
        if k1 < 2:
            n += k1
            k1 = 0
        elif n >= a:
            t=k1//2
            n += (b-a)*t
            k1 -= 2*t
        else:
            if k1 >= a-n + 2:
                t = a-n
                n += t
                k1 -= t
            else:
                n += k1
                k1 = 0
print(n)


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

int main(){
    int N;
    cin >> N;
    string S;
    int co1=0, co2=0, co3=0, co4=0;
    int i;
    for(i=0; i<N; i++){
        cin >> S;
        if(S=="AC"){
            co1++;
        }else if(S=="WA"){
            co2++;
        }else if(S=="TLE"){
            co3++;
        }else if(S=="RE"){
            co4++;
        }
    }
    cout << "AC x " << co1 << endl;
    cout << "WA x " << co2 << endl;
    cout << "TLE x " << co3 << endl;
    cout << "RE x " << co4 << endl;
    system("pause");
    return 0;
}

Measured memory_bytes: 3684
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
typedef long long ll;
int N; 

ll sum_ll(vector<int> vec){
  ll _sum=0;
  rep(i,(int)vec.size()) _sum+=vec[i];
  return _sum;
}

void beat(int &_hero, int &_enemy){
  if(_hero<_enemy){
    _enemy -= _hero;
    _hero = 0;
  }else{
    _hero -= _enemy;
    _enemy = 0;
  }
}

int main(){
  cin >> N;
  vector<int> hero(N);
  vector<int> enemy(N+1);
  rep(i,N+1) cin >> enemy[i];
  rep(i,N)   cin >> hero[i];
   
  ll ans=sum_ll(enemy);
  rep(i,N){
    beat(hero[i], enemy[i]);
    beat(hero[i], enemy[i+1]);
  }
  cout << ans - sum_ll(enemy) << "\n"; 
}



Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

ll N,M,K,H,W;

long long modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
    // a/b =equiv=  (a%MOD) * modinv(b, MOD) % MOD;
}

int main(){
    map<string, ll> mp;
    cin >> N;
    string str;
    REP(i, N){
        cin >> str;
        auto it = mp.find(str);
        if(it != mp.end()){
            it->second += 1;
        }
        else mp.insert(std::make_pair(str, 1));
    }
    vector<pair<int, string>> v;
    for (auto it=mp.begin(); it!=mp.end(); ++it){
        v.push_back(make_pair(it->second, it->first));
    }
    sort(v.begin(), v.end(), std::greater<pair<ll, string>>());
    ll ma = v[0].first;
    int k = 0;
    vector<string> s;
    while(ma == v[k].first){
        s.push_back(v[k].second);
      ++k;
    }
    sort(s.begin(), s.end());
    for(int i = 0; i < s.size(); ++i){
        cout << s[i] << "\n";
    }
    return 0;
}

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

#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d", &tmp);v.push_back(tmp);}}
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

using namespace std;

typedef pair<int,int> pii;

int main(){

  int n, x;
  scanf("%d %d", &n, &x);

  vector<int> v;
  SV(n,v);

  llong ans = 0;
  REP(i,n-1){
    if(v[i] + v[i + 1] > x){
      int num = v[i] + v[i + 1] - x;
      ans += num;
      if(v[i + 1] >= num){
        v[i + 1] -= num;
      }else{
        num -= v[i + 1];
        v[i + 1] = 0;
        v[i] -= num;
      }
    }
  }

  printf("%lld\n", ans);
  return 0;
}



Measured memory_bytes: 892
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

typedef long long ll;
//typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define revrep(i, n) for(ll i = n-1; i >= 0; i--)
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}

ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 1000000000;//10^9
ll MOD  = 1000000007;
//vector<int> dy = {0,0,1,-1};
//vector<int> dx = {1,-1,0,0};

ll N, M, Q;
ll dp[510][510];
ll sum[510][510];

int main(){
  cin >> N >> M >> Q;
  rep(i, M){
    ll L, R; cin >> L >> R;
    dp[L-1][R-1]++;
  }
  rep(i, 505)rep(j, 505){
    sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + dp[i][j];
  }
  rep(i, Q){
    ll p, q; cin >> p >> q;
    cout << sum[505][q] - sum[p-1][q] << endl;
  }
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

int main(){
    vector<int> nums(3);
    rep(i,3) cin >> nums[i];
    sort(RALL(nums));
    int ans = 0;
    ans += nums[0] * 10 + nums[1];
    ans += nums[2];
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF (1 << 30 - 1)
#define LLINF (1LL << 60)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

signed main() {
    cin >> S;
    auto c = S.back();
    if (c == '3') {
        cout << "bon" << endl;
    } else if (c == '0' || c == '1' || c == '6' || c == '8') {
        cout << "pon" << endl;
    } else {
        cout << "hon" << endl;
    }
}

Measured memory_bytes: 3620
s=input()
t=input()
if s==t:
    print("Yes")
else:
    s_len=len(s)
    ans="No"
    for i in range(1,s_len):
        if s[i:]==t[:s_len-i] and s[:i]==t[s_len-i:]:
            ans="Yes"
            break
    print(ans)

Measured memory_bytes: 3060
var lines = [];
var readline = require('readline');

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (x) => {
    lines.push(x);
});

rl.on('close', () => {
    var N = Number(lines[0]);
    var a = lines[1].split(" ").map(value => Number(value));

    var counter = 0;

    for (var i = 0; i < N; i++) {
        for (var j = 1; j < 30; j++) {
            if (a[i] % 2 === 0) {
                a[i] = a[i] / 2
                counter++;
            }
        }
    }

    console.log(counter);
});

Measured memory_bytes: 12108
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
 
using namespace std;
 
int main() {
	string str;
	cin >> str;
	int s, n, w, e;
	s = count(str.begin(), str.end(), 'S');
	n = count(str.begin(), str.end(), 'N');
	w = count(str.begin(), str.end(), 'W');
	e = count(str.begin(), str.end(), 'E');
	bool a, b;
	if (s != 0 && n != 0) {
		a = true;
	}
	else if (s == 0 && n == 0) {
		a = true;
	}
	else {
		a = false;
	}
 
	if (w != 0 && e != 0) {
		b = true;
	}
	else if (w == 0 && e == 0) {
		b = true;
	}
	else {
		b = false;
	}
 
	if (a == true && b == true) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

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

#define pb push_back
#define mp make_pair
#define loop1(x,s,e) for(int x=s;x!=e;x+=1-2*(s>e))
#define input_matrix(a,m,n) for(int i=0;i<m;i++)for(int j=0;j<n;j++)cin>>a[i][j];
#define input_array(a,n) for(int i=0;i<n;i++)cin>>a[i];
#define all(x) x.begin(),x.end()
#define newl "\n"
#define tests(t) int t; cin>>t; while(t--)
#define speed ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main()
 {
	speed;
	string c,s;
	cin>>c>>s;
	int count=0;
	for(int i=0;i<s.length();i++) if(s[i]==c[i])count++;
	cout<<count<<newl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Int int32_t
#define all(c) c.begin(), c.end()
#define FAST ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define pii pair< int , int >
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define bitcnt(n) __builtin_popcountll(n)
#define setpre(n) cout << fixed << setprecision(n)
#define tr(c) for(auto x : c )cout << x << " ";
#define ol(c , s , e ) for(int pos=s; pos<e ; pos++) cout << c[pos] << " ";
#define PI acos(-1l)
const int M = 1000000007;
const int N=3e5+5;
const int INF = 2e18+5;
//#define rohit
#ifdef rohit
template<typename... T >
void bug(T... __VA_ARGS__) {
    ((cerr << __VA_ARGS__ << " ") , ...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", bug(__VA_ARGS__) , cerr << endl;
#endif

void solve(){
    int x, n;
    cin >> x >> n;
    int a[n];
    map< int , int > mp;
    for(int i=0 ; i<n ;i++){
        cin >> a[i];
        mp[a[i]]++;
    }
    int k = x;
    while(mp.count(k) && k<=100){
        k++;
    }
    int kt = x;
    while(mp.count(kt) && kt>=1){
        kt--;
    }
//    cerr << k << " "<< kt << endl;
    if(abs(kt - x) < abs(k -x)){
        cout << kt;
    }
    else if(abs(kt - x) == abs(k -x)){
        cout <<min(kt , k);
    }
    else{
        cout <<k;
    }

}


signed main(){
    FAST;
    //TODO: check test cases.
    int tc=1;
//    cin >> tc;
    for(int t = 1 ; t <= tc ; t++){
        solve();
    }
}
/* Extra Cares
 * 1)In graphs or dp problems sometimes long long creates MLE.
 * 2)Check whether int to long long typecasting is commented or not?
 * 3)Check overflows.
*/

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

struct Block {
  Block() : xl(0), xr(0), cnt(12), n(0), ng(0) {
    fill(cnt.begin(), cnt.end(), 0);
  }

  int xl, xr;
  vector<int> cnt;
  vector<Block> children;

  int n, ng;
};

void makeTree(Block &b, int y, int x, char n,
	      vector<vector<char> > &q, int ly, int lx) {
  if (q[y][x] == '.') {
    return;
  }

  if (q[y][x] > '9') {
    if (q[y][x] - 9 != n && ly == y + 1) {
      b.xl = min(b.xl, lx);
      b.xr = max(b.xr, lx);
    }
    return;
  }

  if (q[y][x] != n) {
    if (ly == y + 1) {
      b.xl = min(b.xl, lx);
      b.xr = max(b.xr, lx);
    }
    if (ly == y - 1) {
      Block child;
      child.xl = child.xr = lx;
      makeTree(child, y, x, q[y][x], q, y, x);
      b.children.push_back(child);
    }
    return;
  }

  b.cnt[x]++;
  q[y][x] += 9;
  makeTree(b, y, x - 1, n, q, y, x);
  makeTree(b, y, x + 1, n, q, y, x);
  makeTree(b, y - 1, x, n, q, y, x);
  makeTree(b, y + 1, x, n, q, y, x);
}

bool stable(Block &b) {
  bool s = true;

  for (int x = 1; x <= 10; x++) {
    b.n += b.cnt[x];
    b.ng += x * b.cnt[x];
  }

  for (int i = 0; i < b.children.size(); i++) {
    s = s && stable(b.children[i]);
    b.n += b.children[i].n;
    b.ng += b.children[i].ng;
  }

  double gVal = (double)b.ng / b.n - 0.5;

  return s && gVal > (b.xl - 1) && gVal < b.xr;
}

int main() {
  int w, h;

  while (cin >> w >> h, w != 0) {
    vector<vector<char> > q(h + 2);
    for (int i = 0; i < h + 2; i++) {
      q[i].resize(w + 2);
      fill(q[i].begin(), q[i].end(), '.');
    }

    for (int y = 1; y <= h; y++) {
      for (int x = 1; x <= w; x++) {
        cin >> q[h - y + 1][x];
      }
    }

    Block root;
    for (int x = w; x >= 1; x--) {
      if (q[1][x] != '.') {
        root.xr = x;
        break;
      }
    }

    for (int x = 1; x <= w; x++) {
      if (q[1][x] != '.') {
        root.xl = x;
        makeTree(root, 1, x, q[1][x], q, 1, x);
        break;
      }
    }

    cout << (stable(root) ? "STABLE" : "UNSTABLE") << endl;
  }

  return 0;
}

Measured memory_bytes: 3096
from fractions import gcd

n, x = map(int, input().split())
l = list(map(int, input().split()))

if n == 1:
    print(abs(x-l[0]))
    exit()

diff = []
for i in range(len(l)-1):
    diff.append(abs(l[i] - l[i+1]))

for i in range(len(l)):
    diff.append(abs(l[i] - x))

gcd_1 = gcd(diff[0], diff[1])
if n == 2:
    print(gcd_1)
    exit()

for i in range(2, len(diff)-1):
    gcd_1 = gcd(gcd_1, diff[i])

print(gcd_1)

Measured memory_bytes: 18760
N = gets.to_i
h={}
sum=0
gets.split.map(&:to_i).each do |a|
    sum+=a
    if h.has_key?(a)
        h[a]+=1
    else
        h[a]=1
    end
end
Q = gets.to_i
Q.times do |i|
    b,c = gets.split.map(&:to_i)
    dif=c-b
    h[b]=0 unless h.has_key?(b)
    h[c]=0 unless h.has_key?(c)
    sum=sum+h[b]*dif
    h[c]+=h[b]
    h[b]=0
    puts sum
end

Measured memory_bytes: 26040
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define ARRAY_LENGTH(array) sizeof(array)/sizeof(*array)
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 = 1000100100;

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

    vector<ll> A(N);
    REP(i, N) {
        cin >> A[i];
    }

    ll max = 0, prev_max = 0;
    REP(i, N) {
        if(A[i] > max) {
            prev_max = max;
            max = A[i];
        } else {
            if(A[i] > prev_max) {
                prev_max = A[i];
            }
        }
    }

    REP(i, N) {
        if(A[i] != max) {
            cout << max << endl;
        } else {
            cout << prev_max << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 4840
#include<iostream>
#include<vector>
#define MAX 7.5*1e6
using namespace std;

int main(){
  int n, m;
  while(1) {
    scanf("%d %d\n", &m, &n);
    if(n == 0)break;
    vector<bool> isBoring(MAX, false);
    for (int i = 0; i < n; i++) {
      while(isBoring[m] == true) m++;
      for (int j = m; j < MAX; j+=m) {
        isBoring[j] = true;
      }
    }
    while(isBoring[m] == true)m++;
    std::cout << m << std::endl;
  }
  return 0;
}

Measured memory_bytes: 4100
#include <bits/stdc++.h>
using namespace std;
 
// #define int long long
 
/* short */
#define pb push_back
#define print(x) cout << x << '\n'
 
/* REPmacro */
#define REP(i, n) for (int i = 0; i < (n); i++)
#define REPS(i, a, n) for (int i = (a); i < (n); i++)
 
/* typedef */
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef pair<int, int> pii;

/* const */
const int INF = INT_MAX;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

/* func */
inline bool is_uruu(int y) {return (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0));}

int dp[45];

int fibo(int n)
{
  if (dp[n] != -1){
    return (dp[n]);
  }

  if (n == 0 || n == 1){
    return (1);
  }
  return (dp[n] = fibo(n - 1) + fibo(n - 2));
}

signed main()
{
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  fill(dp, dp + 45, -1);
  print(fibo(n));
  return (0);
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
signed main(){
    long long a,b,c,d;
    cin>>a>>b>>c>>d;
    long long sum1,sum2,ans1,ans2;
    sum1=a*c;
    sum2=a*d;
    ans1=b*c;
    ans2=b*d;
    if(sum1<sum2 && ans1<sum2 && ans2<sum2){
        cout<<sum2<<endl;
    }else if(sum2<sum1 && ans1<sum1 && ans2<sum1){
        cout<<sum1<<endl;
    }else if(sum1<ans1 && sum2<ans1 && ans2<ans1){
        cout<<ans1<<endl;
    }else{
        cout<<ans2<<endl;
    }
    return(0);
}


Measured memory_bytes: 3624
li = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(li[int(input()) - 1])


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

template<class T, class Cond>
struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  bool operator()(T& a, const T& b) const {
    if(cond(a, b)) { a = b; return true; }
    return false;
  }
};
template<class T, class Cond>
chain<T, Cond> make_chain(Cond cond) { return chain<T, Cond>(cond); }

vector<vector<i64>> G;

vector<i64> match;

bool dfs(i64 v, i64 f) {
  for(auto t: G[v]) {
    if(t == f) continue;
    if(!dfs(t, v)) {
      return false;
    }
  }

  if(match[v] == 0) {
    if(0 <= f && match[f] == 0) {
      match[v] = 1;
      match[f] = 1;
      return true;
    }
    else {
      return false;
    }
  }
  return true;
}

int main() {
  i64 N;
  cin >> N;
  G.resize(N);
  rep(i,0,N - 1) {
    i64 a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  match.resize(N);

  if(dfs(0, -1)) {
    cout << "Second" << endl;
  }
  else {
    cout << "First" << endl;
  }
}


Measured memory_bytes: 7168
# The Number of Inversions
N = int(input())
A = list(map(int, input().split()))
INF = float('inf')
cnt = 0


def merge(left, mid, right):
    global cnt
    L = A[left:mid]+[INF]
    R = A[mid:right]+[INF]
    l = 0
    r = 0
    nl = mid - left

    for i in range(right-left):
        if L[l] < R[r]:
            A[left+i] = L[l]
            l += 1
        else:
            A[left+i] = R[r]
            r += 1
            cnt += nl - l


def merge_sort(left, right):
    if left+1 < right:
        mid = (left+right)//2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)


merge_sort(0, N)
print(cnt)



Measured memory_bytes: 27472
s=list(input())

a=int(s[0]+s[1])
b=int(s[2]+s[3])
A=0<a and a<13
B=0<b and b<13

if A and B:
    print("AMBIGUOUS")
elif A:
    print("MMYY")
elif B:
    print("YYMM")
else:
    print("NA")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    init();
    ll N;
    cin >> N;
    vl C(N + 1);

    repe(i, 1, 100)repe(j, 1, 100)repe(k, 1,100){
        ll v = i * i + j * j + k * k + i * j + j * k + k * i;
        if (v <= N) C[v]++;
    }

    repe(i, 1, N+1){
        cout << C[i] << '\n';
    }
}

Measured memory_bytes: 3664
K = int(input())
import sys

nums = [[] for _ in range(11)]
for x in range(1, 10):
    nums[0].append(x)

def push(x, n):
    global nums, cnt
    nums[x].append(n)
    cnt += 1
    if cnt == K:
        print(n)
        sys.exit()
    

if 1 <= K <= 9:
    print(K)
    sys.exit()

cnt = 9
for x in range(1, 11):
    for n in nums[x - 1]:
        if str(n)[-1] == "0":
            push(x, int(str(n) + "0"))
            push(x, int(str(n) + "1"))
        elif str(n)[-1] == "9":
            push(x, int(str(n) + "8"))
            push(x, int(str(n) + "9"))
        else:
            for i in range(-1, 2):
                push(x, int(str(n) + str(int(str(n)[-1]) + i)))
            




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

long long gcd(long long a, long long b) {
	if(a == 1 || b == 1){
		return 1;
	}
	if(a < b) gcd(b, a);
	long long r;
	while ((r=a%b)) {
		a = b;
		b = r;
	}
	return b;
}





int main() {
	// your code goes here
	long long n, x, a, b = 99999999, c;
	cin >> n >> x;
	if(n == 1){
		cin >> b;
		cout << abs(b - x)<< endl;
		return 0;
	}
	long long s[n + 1];
	bool flag = false;
	for(long long i = 0; i < n; i++){
		cin >> s[i];
		
	}
	s[n] = x;
	sort(s, s+n+1);
	
	b = s[1] - s[0];
	for(long long i = 1; i <= n; i++){
		b = abs(gcd(b, s[i] - s[i - 1]));
	}
	cout << b << endl;
	return 0;
}
//7 13 19 23 43
// 6  6  4  20

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
using namespace std;
using ll = long long;
const int inf = 1e8;

int main() {
    int n, e;
    cin >> n >> e;
    int dp[1<<n][n];
    vector<vector<int>> d(n,vector<int>(n,-1));
    rep(i,e) {
        int s, t, cost;
        cin >> s >> t >> cost;
        d[s][t] = cost;
    }
    int ans = inf;
    rep(V,n) {
        rep(i,1<<n)rep(j,n) dp[i][j] = inf;
        dp[(1<<n)-1][V] = 0;
        for (int S = (1<<n) - 2; S >= 0; S--) {
            for (int v = 0; v < n; v++) {
                for (int u = 0; u < n; u++) {
                    if (!(S >> u & 1) && (d[v][u] != -1)) {
                        dp[S][v] = min(dp[S][v],dp[S|1<<u][u] + d[v][u]);
                    }
                }
            }
        }
        ans = min(ans,dp[0][V]);
    }
    if (ans == inf) cout << -1 << endl;
    else cout << ans << endl;
}


Measured memory_bytes: 5092
#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 FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define M_PI 3.14159265358979323846

#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

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

int dx[]={1, 0, -1, 0, 0};
int dy[]={0, 1, 0, -1, 0};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
const int NIL = -1;
static mt19937 _g(time(nullptr));
 
std::string pad(int num){ char buffer[4]; std::snprintf(buffer, sizeof(buffer), "%03d", num); return buffer;}
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }



int main()
{
    fast_io();
    #ifdef __LOCAL
        fs::path p = __FILE__;
        fs::path input,output;
        input = output = p.parent_path();
        input += string("/input/") + string(p.stem()) + string(".txt");
        output += string("/output/") + string(p.stem()) + string(".txt");
        freopen(input.c_str(), "r", stdin);
        freopen(output.c_str(), "w", stdout);
    #endif
    string S,T,U;
    int A,B;
    cin >> S >> T;
    cin >> A >> B;
    cin >> U;
    if(S==U) A--;
    if(T==U) B--;

    cout << A << " " << B << endl;

    return 0;


}


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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

int N,S,W,Q;
const int nmax=100010;
ll a[nmax];
ll sum[nmax];
ll ten[nmax];

void gen(){
	int g=S;
	for(int i=0;i<N;i++){
		a[i]=(g/7)%10;
		if(g%2==0)
			g=(g/2);
		else
			g=(g/2)^W;
	}
}

// 123*10^3+456

// aならば， a*10^n
// sum[j]==sum[i-1]*ten[j-i+1]  2 or 5 is easy

// a*b+c==0

int solve(){
	gen();
	ll res=0;
	if(Q==2||Q==5){
		ll cur=0;
		rep(i,N){
			if(a[i]%Q==0){
				res+=cur;
				if(a[i]!=0) res++;
			}
			if(a[i]!=0) cur++;
		}
	}else{
		ll cur=1LL;
		for(int i=0;i<N;i++){
			ten[i]=cur;
			cur=(cur*10)%Q;
		}

		for(int i=N-1;i>=0;--i)
			sum[i]=(sum[i+1]+a[i]*ten[N-1-i])%Q;

		map<int,int> num;
		num[0]=1;
		for(int i=N-1;i>=0;--i){
			if(a[i]!=0)
				res+=num[sum[i]];
			num[sum[i]]++;
		}
	}
	return res;
}

int main(void){
	while(1){
		cin >> N >> S >> W >> Q;
		rep(i,N+1) sum[i]=0LL;
		if(N==0)
			break;
		cout << solve() << endl;
	}
	return 0;
}
//   430000000 2143435 sum[i]-sum[j]

Measured memory_bytes: 7760
// atcoder/abc144/D/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

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

  double a, b, x;
  while (cin >> a >> b >> x) {
    if (x < (a * a * b) / 2.0) {
      double c = 2.0 * x / (a * b);
      // double r = asin(c / b) * 180 / M_PI;
      // printf("%.10lf\n", 90.0 - r);
      double r = atan(b / c);
      printf("%.10lf\n", r * 180.0 / M_PI);
    } else {
      double c = 2.0 * (a * a * b - x) / (a * a);
      double r = atan(c / a);
      printf("%.10lf\n", r * 180.0 / M_PI);
    }
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int A, B, K,i;
    cin>>A>>B>>K;
    if((B-A+1)/2<K){
        for(i=0;i<=B-A;i++){
            cout<<A+i<<" ";
        }
    }else{
        for(i=0;i<K;i++){
            cout<<A+i<<" ";
        }
        for(i=K-1;i>=0;i--){
            cout<<B-i<<" ";
        }
    }
    return 0;
}

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

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T> T id(T b) {return b;};
template <class It> bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It> bool any(It f,It l){return std::any_of(f,l,id<bool>);}
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}

int n,d;

int main()
{
#ifdef FASTIO
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif

  cin >> n >> d;

  int res = n / (2*d+1);

  if (n % (2*d+1)) res++;

  cout << res << endl;

  return 0;
}


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


int main(){
  int n;
  cin>>n;
  long long L0=2,L1=1,L=0;
  if (n==1) {
    cout<<L1<<endl;
    return 0;
  }
  for(int i=2;i<=n;i++){
    L=L0+L1;
    L0=L1;
    L1=L;
  }
  
  cout<<L<<endl;
  return 0;
}

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

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, a, b;
  cin >> n >> a >> b;
  vector<int> vec(n);
  for (int i = 0; i < n; i++) {
    cin >> vec[i];
  }
  long long res = 0;
  for (int i = 0; i < n - 1; i++) {
    res += min(1LL * a * (vec[i + 1] - vec[i]), 1LL * b);
  }
  cout << res << '\n';
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
int t,n,m;
int arr[maxn];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	int flag=0;
	while(n)
	{
		int z=n%10;
		if(z==7) flag=1;
		n=n/10;
	 }
	if(flag) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include <utility>

std::vector< std::pair<char,int> > bubbleSort(std::vector< std::pair<char,int> > );
std::vector< std::pair<char,int> > selectionSort(std::vector< std::pair<char,int> >);
bool stable_judge(std::vector< std::pair<char,int> >,std::vector< std::pair<char,int> >);

int main(int argc, char const *argv[]){
	int N;
	std::cin >> N;
	std::vector< std::pair<char,int> > input;

	for (int i = 0; i < N; ++i){
		std::string buff;
		std::cin >> buff;
		input.push_back(std::make_pair(buff[0],buff[1]-'0'));
	}

	std::vector< std::pair<char,int> > bubble = bubbleSort(input);
	std::vector< std::pair<char,int> > select = selectionSort(input);

	for (int i = 0; i < N; ++i){
		std::cout << bubble[i].first << bubble[i].second;
		if(i<N-1)std::cout << " ";
	}
	std::cout << std::endl;

	if(stable_judge(input,bubble)){
		std::cout << "Stable" << std::endl;
	}else{
		std::cout << "Not stable" << std::endl;		
	}

	for (int i = 0; i < N; ++i){
		std::cout << select[i].first << select[i].second;
		if(i<N-1)std::cout << " ";
	}
	std::cout << std::endl;

	if(stable_judge(input,select)){
		std::cout << "Stable" << std::endl;
	}else{
		std::cout << "Not stable" << std::endl;		
	}


	return 0;
}

std::vector< std::pair<char,int> > bubbleSort(std::vector< std::pair<char,int> > fig){
	for (int i = 0; i < fig.size(); ++i){
		for (int j = fig.size()-1; j > i ; --j){
			if(fig[j].second<fig[j-1].second){
				std::pair<char,int> buff = fig[j];
				fig[j] = fig[j-1];
				fig[j-1] = buff;
			}				
		}
	}
	return fig;
}

std::vector< std::pair<char,int> > selectionSort(std::vector< std::pair<char,int> > fig){
	for (int i = 0; i < fig.size(); ++i){
		int minj = i;
		for (int j = i; j < fig.size(); ++j){
			if(fig[j].second < fig[minj].second){
				minj = j;
			}				
		}
		if(i!=minj){
			std::pair<char,int> buff = fig[i];
			fig[i] = fig[minj];
			fig[minj] = buff;
		}
	}
	return fig;
}

bool stable_judge(std::vector< std::pair<char,int> > before, std::vector< std::pair<char,int> > after){

	while(!before.empty()){

		std::string str_before;
		std::string str_after;
		int fig = after[0].second;

		for (int i = 0; i < before.size(); ++i){
			if(fig==before[i].second){
				str_before += before[i].first;
				before.erase(before.begin() + i);
				i -= 1;
			}
		}

		for (int i = 0; i < after.size(); ++i){
			if(fig==after[i].second){
				str_after += after[i].first;
				after.erase(after.begin() + i);
				i -= 1;
			}
		}
		if(str_before != str_after)return false;
	}
	return true;
}



Measured memory_bytes: 3204
#include<bits/stdc++.h>
using namespace std;
using ll=long long int;
constexpr int  mod = 1e9 + 1;

int main() {
	ll a, b, c, k; ll res = 0;
	cin >> a >> b >> c >> k;
	if(k>=a)
	res += a;
	else {
		cout << k;
		return 0;
	}
	k -= a; k -= b;
	if (k <= 0)cout << res;
	else {
		res -= (k);
		cout << res;
	}
	return 0;
}

Measured memory_bytes: 3624