akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll n, q; cin >> n >> q;
    string s; cin >> s;
    vector<pair<ll, ll>> vec(q);
    REP(i, q) {
        ll l, r; cin >> l >> r;
        vec[i] = make_pair(l, r);
    }

    vector<ll> t(n+1);
    REP(i, n) {
        t[i+1] = t[i] + (s.substr(i, 2) == "AC" ? 1 : 0);
    }

    REP(i, q) {
        ll l = vec[i].first, r = vec[i].second;
        cout << t[r-1] - t[l-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 3456
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0 ; i < n ; i++) {
            int a = sc.nextInt();
            if (map.containsKey(a)) {
                map.put(a, map.get(a) + 1);
            } else {
                map.put(a, 1);
            }
        }
        int count = 0;
        for (Entry<Integer, Integer> entry : map.entrySet()) {
            int value = entry.getValue();
            if (value % 2 == 0) {
                count++;
            }
        }

        System.out.println(count % 2 == 0 ? map.size() : map.size() - 1);

    }

}

Measured memory_bytes: 62120
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;



ll Largest_Rectangle(const vector<vector<bool>> &A){
    vector<vector<ll>> a(A.size(),vector<ll>(A[0].size(),0));
    ll count;
    for(int i=0;i<A[0].size();i++){
        count=0;
        for(ll h=0;h<A.size();h++){
            if(A[h][i]){count++;}
            else{count=0;}
            a[h][i]=count;
        }
    }
    ll mx=2;
    stack<pll> s;
    for(int i=0;i<A.size();i++){
        for(int t=0;t<A[0].size();t++){
            ll mi=t;
            while(!s.empty() && s.top().F>a[i][t]){
                pll w=s.top(); s.pop();
                mx=max(mx,(w.F+1)*(t-w.S+1));
                mi=w.S;
            }
            s.push({a[i][t],mi});
        }
        while(!s.empty()){
            pll w=s.top(); s.pop();
            mx=max(mx,(w.F+1)*((ll)A[0].size()-w.S+1));
        }
    }
    return mx;
}


int main(){
    ll h,w;
    cin>>h>>w;
    vector<vector<bool>> a(h,vector<bool>(w,0));
    for(int i=0;i<h;i++){
        for(int t=0;t<w;t++){
            char c;
            cin>>c;
            a[i][t]=c=='#';
        }
    }
    vector<vector<bool>> b(h-1,vector<bool>(w-1,0));
    for(int i=0;i<h-1;i++){
        for(int t=0;t<w-1;t++){
            ll count=0;
            if(a[i][t]){count++;}
            if(a[i+1][t]){count++;}
            if(a[i][t+1]){count++;}
            if(a[i+1][t+1]){count++;}
            b[i][t]=count%2==0;
        }
    }
    ll ans=Largest_Rectangle(b);
    ans=max(ans,h);
    ans=max(ans,w);
    
    cout<<ans<<endl;
    
    
    return 0;
}


Measured memory_bytes: 32896
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

using P = pair<int, int>;

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

    int h, w, m;
    cin >> h >> w >> m;

    map<P, int> field;
    vector< P > row(h);
    vector< P > col(w);
    rep (i, h) row[i] = P{0, i};
    rep (j, w) col[j] = P{0, j};
    rep (i, m)
    {
        int y, x;
        cin >> y >> x;
        --y, --x;
        field[P{y, x}] = 1;
        row[y] = P{row[y].first + 1, row[y].second};
        col[x] = P{col[x].first + 1, col[x].second};
    }


    sort(row.begin(), row.end(), greater<P>());
    sort(col.begin(), col.end(), greater<P>());

    int ans = 0;
    bool found = false;
    for (int i = 0; i < h && row[0].first == row[i].first; ++i)
    {
        for (int j = 0; j < w && col[0].first == col[j].first; ++j)
        {
            int y = row[i].second;
            int x = col[j].second;
            if (field.find(P{y, x}) != field.end())
            {
                ans = max(ans, row[i].first + col[j].first -1);
            }
            else
            {
                ans = max(ans, row[i].first + col[j].first);
                found = true;
            }
            if (found) break;
        }
        if (found) break;
    }

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 26688
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int half;
  cin >> half;
  string s;
  cin >> s;
  map<string,int> mp;
  for (int t = 0; t < (1 << half); t++) {
    string a = "", b = "";
    for (int i = 0; i < half; i++) {
      if (t & (1 << i)) {
        a += s[i];
      } else {
        b += s[i];
      }
    }
    string c = a + "." + string(b.rbegin(), b.rend());
    // cout<<c<<endl;
    mp[c]++;
  }
  long long ans = 0;
  for (int t = 0; t < (1 << half); t++) {
    string a = "", b = "";
    for (int i = 0; i < half; i++) {
      if (t & (1 << i)) {
        a += s[i + half];
      } else {
        b += s[i + half];
      }
    }
    string c = string(b.rbegin(), b.rend()) + "." + a;
    ans += mp[c];
  }
  cout << ans << '\n';
  return 0;
}

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

using namespace std;

#define PB push_back
#define SZ(a) (int)a.size()
#define MP make_pair

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;

int main() {

	int X;
	scanf("%d", &X);

	int hap = (X / 500) * 1000;
	X = X%500;

	hap += (X / 5) * 5;

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

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B;
    cin >> A >> B;
    if(abs(A - B) % 2 == 1) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        cout << (A + B) / 2 << endl;
    }

    return 0;
}


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

int main(){
  string s;
  cin >> s;

  int n = s.size();


  string t = "keyence";

  for(int l = -1;l < n;l++){
    for(int r = l;r < n;r++){
      int k = 0;
      for(int i = 0;i < n;i++){
        if(!(l <= i && i <= r)){
          if(s[i] == t[k]){
            k++;
            if(k == t.size() && i != n-1){
              k++;
              break;
            }
          }else{
            break;
          }
        }
      }
      if(k == t.size()){
        cout << "YES" << endl;
        return 0;
      }
    }
  }

  cout << "NO" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;

LL ans;
int i,n,flag;
LL a[100005];
bool cmp(LL x,LL y)
{
	return x>y;
}
int main()
{
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+1+n,cmp);
	ans=0;
	flag=0;
	for(i=2;i<=n;i++)
	{
		if(a[i]==a[i-1])
		{
			if(ans==0)
				ans=a[i];
			else
				ans=a[i] *ans;
			//cout<<ans<<endl;
			flag++;
			i+=1;
			if(flag==2)
			{
				cout<<ans<<endl;
				return 0;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
N = int(input())

max_num = -1
max_index = []
second_num = -1
dic = {}
for i in range(1, N+1):
    num = int(input())
    dic[i] = num
    if num > max_num:
        second_num = max_num
        max_num = num
        max_index.clear()
        max_index.append(i)
    elif num == max_num:
        max_index.append(i)
    elif num > second_num:
        second_num = num

for i in range(1, N+1):
    if dic[i] < max_num:
        print(max_num)
    elif dic[i] == max_num:
        if len(max_index) > 1:
            print(max_num)
        else:
            print(second_num)

    



Measured memory_bytes: 33936
import math
s = input()
m = len(s)
for i in range(26):
    c = chr(i+ord('a'))
    t = s
    for j in range(len(t)):
        if t.count(c) == len(t):
            m = min(m, j)
        u = ''
        for k in range(len(t)-1):
            if t[k+1] == c:
                u += c
            else:
                u += t[k]
        t = u
print(m)


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

int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++)
  {
    cin >> A.at(i);
  }
  
  sort(A.begin(), A.end(), greater<int>());
  
  cout << A.at(0) - A.at(N - 1) << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <utility>
using namespace std;
const int INF=2147483647;
int min(int a,int b){
    if(a>b)return b;
    return a;
}
struct segment_tree{
    pair<int,int> map[2000010];
    void build(int now,int l,int r){
        map[now].first=INF;
        map[now].second=-1;
        if(l==r)return;
        int mid=(l+r)/2;
        build(now*2+1,l,mid);
        build(now*2+2,mid+1,r);
        return ;
    }
    void change(int n,int now,int L,int R,int l,int r){
        if(R<l||L>r)return;
        if(L>=l&&R<=r){
            map[now].second=map[now].first=n;
            return;
        }
        if(map[now].second!=-1){
            map[now*2+1].second=map[now*2+1].first=map[now*2+2].first=map[now*2+2].second=map[now].second;
            map[now].second=-1;
        }
        int mid=(L+R)/2;
        change(n,now*2+1,L,mid,l,r);
        change(n,now*2+2,mid+1,R,l,r);
        map[now].first=min(map[now*2+1].first,map[now*2+2].first);
        return ;
    }
    int find(int now,int L,int R,int l,int r){
        if(R<l||L>r)return INF;
        if(L>=l&&R<=r)return map[now].first;
        if(map[now].second!=-1){
            map[now*2+1].second=map[now*2+1].first=map[now*2+2].first=map[now*2+2].second=map[now].second;
            map[now].second=-1;
        }
        int mid=(L+R)/2;
        return min(find(now*2+1,L,mid,l,r),find(now*2+2,mid+1,R,l,r));
    }
};
int main(){
    int n,m,k,l,r;
    segment_tree arr;
    scanf("%d%d",&n,&m);
    arr.build(0,0,n-1);
    while(m--){
        scanf("%d%d%d",&k,&l,&r);
        if(k==0){
            scanf("%d",&k);
            arr.change(k,0,0,n-1,l,r);
        }
        else printf("%d\n",arr.find(0,0,n-1,l,r));
    }
}

Measured memory_bytes: 18400
while True:
    num = int(input())
    if num == 0:
        break
    y = int(input())
    rmax = 0
    bmax = None
    for _ in range(num):
        b, r, t = [int(x) for x in input().split()]
        if t == 1:
            val = 1 + r*y/100
        else:
            val = (1 + r/100)**y
        
        if val > rmax:
            bmax,rmax = b, val
    print(bmax)

        
        
        


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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const ll mod = 1e9 + 7;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int N;
  cin >> N;

  ll ans = 1;
  for (int i = 2; i <= N; i++) {
    bool no = false;
    for (int j = 2; !no && j * j <= i; j++) {
      if (i % j == 0) no = true;
    }
    if (no) continue;
    ll p = i, sum = 0;
    while (p <= N) {
      sum += N / p;
      p *= i;
    }
    (ans *= (sum + 1)) %= mod;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
  int i,j,m,f,r;
  char s;

  for(;;){
    scanf("%d%d%d",&m,&f,&r);
    if(m+f+r == -3) break;

    if(m == -1 || f == -1)
      s = 'F';
    else if(m+f >= 80)
      s = 'A';
    else if(m+f >= 65)
      s = 'B';
    else if(m+f >= 50)
      s = 'C';
    else if(m+f >= 30)
      if(r >= 50)
        s = 'C';
      else
        s = 'D';
    else
      s = 'F';

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


Measured memory_bytes: 2724
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <deque>
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFL 1100000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> Pi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<Pi> > vvPi;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
template <class T>
using vec = vector<T>;
template<class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
string debug_show(Pi a) {
	return "(" + to_string(a.first) + "," + to_string(a.second) + ")";
}

template<class T>
struct augEdge {
	T from, to;
	int cost;
	bool operator<(augEdge e) { return cost < e.cost; }
	bool operator>(augEdge e) { return cost > e.cost; }
};
template<class T>
using augGraph = vector<augEdge<T>>;



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

	int k, s;
	cin >> k >> s;
	int ans = 0;
	rep(i, k + 1) {
		rep(j, k + 1) {
			int t = s - i - j;
			if (t >= 0 && t <= k) {
				ans++;
			}
		}
	}
	
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
#include <iomanip>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }


int m[] = {200, 300, 500};
int p[] = {380, 550, 850};
int d[] = {5, 4, 3};
double r[] = {0.8, 0.85, 0.88};
const int INF = 1 << 30;

int dfs(int k, int rest, double x)
{
    if(rest == 0) return x;
    
    if(k == 3 || rest < 0) return INF;
    
    int res = INF;
    rep(i, 41)
        chmin(res, dfs(k + 1, rest - m[k] * i, x + p[k] * (i - i % d[k]) * r[k] + p[k] * (i % d[k])));
    
    return res;
}

int main()
{
	int v;
	while(cin >> v && v)
        cout << dfs(0, v, 0) << endl;
}

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

string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main(){
	string s,t,v;
	cin >> s >> t >> v;
	int a = s[0] - 'a';
	int b = t[0] - 'a';
	int c = v[0] - 'a';
	cout << alphabet[a] << alphabet[b] << alphabet[c] << endl;
    return 0;
}



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


using LL = long long int;
using uLL = unsigned long long int;
using uint = unsigned int;
using ld = long double;

const int N = 3007;

int dp[N][N];

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(0);
    string s, t;
    cin >> s >> t;
    for(int i = 1; i <= s.size(); i++){
        for(int j = 1; j <= t.size(); j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(s[i-1] == t[j-1]){
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
            }
        }
    }
    int i = s.size();
    int j = t.size();
    string ans;
    while(dp[i][j] > 0){
        if(s[i-1] == t[j-1]){
            ans.push_back(s[i-1]);
            i--;
            j--;
        }
        else if(dp[i-1][j] > dp[i][j-1]){
            i--;
        }
        else{
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
    
    return 0;
}

Measured memory_bytes: 35584
//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int mod = n % 10;
    if(mod == 2 || mod == 4 || mod == 5 || mod == 7 || mod == 9){
        cout<<"hon\n";
    }
    else if(mod == 0 || mod == 1 || mod == 6 || mod == 8){
        cout<<"pon\n";
    }
    else{
        cout<<"bon\n";
    }

    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define ll long long
#define N 100005
#define mk(x,y) make_pair(x,y)
#define ft first
#define sd second
using namespace std;
int x,y,z;
ll ans;
int a[N],b[N],c[N],q[N],p[N],v[N];
bool cmp1(int x,int y)
{
    if(b[x]!=b[y])return b[x]>b[y];
    return c[x]<c[y];
}
bool cmp2(int x,int y)
{
    return c[x]>c[y];
}
priority_queue<pair<int,int> >q1;
multiset<int>s;
multiset<int>::iterator it;
int main()
{
    scanf("%d%d%d",&x,&y,&z);
    int n=x+y+z;ll now=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        p[i]=q[i]=i;now+=a[i];
        b[i]-=a[i];c[i]-=a[i];
    }
    sort(q+1,q+n+1,cmp1);sort(p+1,p+n+1,cmp2);
    for(int i=1;i<=y;i++)
    {
        now+=b[q[i]];q1.push(mk(c[q[i]]-b[q[i]],q[i]));v[q[i]]=1;
    }int point=1;
    for(int i=1;i<=z;i++)
    {
        while(v[p[point]])point++;
        now+=c[p[point]];s.insert(c[p[point]]);v[p[point]]=1;point++;
    }
    ans=max(ans,now);
    for(int i=y+1;i<=y+z;i++)
    {
        now+=b[q[i]];q1.push(mk(c[q[i]]-b[q[i]],q[i]));
        s.insert(q1.top().ft+b[q1.top().sd]);
        now+=q1.top().ft;
        q1.pop();
        if(v[q[i]]&&s.find(c[q[i]])!=s.end())
        {
            s.erase(s.find(c[q[i]]));
            now-=c[q[i]];
        }
        else
        {
            it=s.begin();
            now-=(*it);
            s.erase(it);
        }
        ans=max(ans,now);
    }
    cout<<ans<<endl;
    return 0;
}


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

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
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; }

using ll = long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class DStringEquivalence {
public:

    int n;
    void dfs(vector<int>& v, int used) {
      if (v.size() == n) {
        for(auto e: v) {
          cout << (char)(e+'a');
        }
        cout << '\n';
        return;
      }

      for(int i=0; i<=used; i++) {
        v.push_back(i);
        dfs(v, max(used, i+1));
        v.pop_back();
      }
    }

    void solve(istream& cin, ostream& cout) {
      SPEED;
      cin >> n;
      vector<int> v;
      dfs(v, 0);
    }
};

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

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

int main()
{
  int n;
  scanf("%d",&n);
  char str[2*n];
  scanf("%s",&str);
  if((str[0] == 'W') || (str[2*n-1] == 'W')){
    printf("0\n");
    return 0;
  }
  
  int ar[2*n]; // 0:left 1:right
  ar[0] = 0;
  for(int i=1; i<2*n; i++){
	ar[i] = (str[i] == str[i-1] ? 1 - ar[i-1] : ar[i-1]);
  }
  
  ll ans = 1;
  int l = 0;
  int r = 0;
  for(int i=0; i<2*n; i++){
    if(ar[i] == 1){
      ans = (ans * (ll)(l - r) % MOD) % MOD;
      r++;
    }
    else
    {
      l++;
    }
  }
  if(l!=r) ans = 0;
  for(int i=1; i<=n; i++) ans = (ans * i) % MOD;   
  printf("%d\n",ans);
  return 0;
}


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

using namespace std;
typedef long long ll;


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

    int N;
    cin>>N;
    vector<int> vi;
    int L;
    for(int i=0;i<2*N;++i){
        cin>>L;
        vi.push_back(L);
    }

    sort(vi.begin(), vi.end());
    int sum=0;
    for(int i=0;i<vi.size();i+=2){
        sum+=vi[i];
    }
    cout<<sum;
    return 0;
}



Measured memory_bytes: 256
using System;
using System.Linq;

class E
{
	static void Main() => Console.WriteLine(((MInt)2).Pow(2 * int.Parse(Console.ReadLine()) - 2) * Console.ReadLine().Split().Select(int.Parse).OrderBy(x => -x).Select((c, i) => (MInt)(i + 2) * c).Aggregate((x, y) => x + y));
}

struct MInt
{
	const int M = 1000000007;
	public long V;
	public MInt(long v) { V = (v %= M) < 0 ? v + M : v; }

	public static implicit operator MInt(long v) => new MInt(v);
	public static MInt operator +(MInt x) => x;
	public static MInt operator -(MInt x) => -x.V;
	public static MInt operator +(MInt x, MInt y) => x.V + y.V;
	public static MInt operator -(MInt x, MInt y) => x.V - y.V;
	public static MInt operator *(MInt x, MInt y) => x.V * y.V;

	public MInt Pow(int i) => MPow(V, i);
	public override string ToString() => $"{V}";

	static long MPow(long b, int i)
	{
		for (var r = 1L; ; b = b * b % M)
		{
			if (i % 2 > 0) r = r * b % M;
			if ((i /= 2) < 1) return r;
		}
	}
}


Measured memory_bytes: 35456
#include <bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define X first
#define Y second
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define D double
#define ll long long
#define REP(i,a) for(int i=0;i<a;i++)
#define REP1(i,a,b) for(int i=a;i<b;i++)
#define REP2(i,a,b) for(int i=a;i<=b;i++)
#define RREP(i,a) for(int i=a-1;i>=0;i--)
#define RREP1(i,a,b) for(int i=a;i>b;i--)
#define RREP2(i,a,b) for(int i=a;i>=b;i--)
#define SREP(i,x) for(auto i:x)
#define MS0(x) memset((x),0,sizeof((x)))
#define MS1(x) memset((x),-1,sizeof((x)))
#define MSF(x) memset((x),127,sizeof(x))
#define pb push_back
#define LE(x) (int)((x).size())
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDD pair<D,D>
#define im guagua
#define RI(x) x=rit()
#define RII(a,b) a=rit(),b=rit()
#define RIII(a,b,c) a=rit(),b=rit(),c=rit()
#define debug 0
const int INF = 0x7F7F7F7F;
const double EPS = 1e-10 ;
const ll mod7 = 1e9+7;
const ll mod9 = 1e9+9;
using namespace std;
inline ll rit(){
    ll f=0,key=1;
    char c;
    do{
        c=getchar();
        if(c=='-') key=-1;
    }while(c<'0' || c>'9');
    do{
        f=f*10+c-'0';
        c=getchar();
    }while(c>='0' && c<='9');
    return f*key;
}
inline void fprt(D f){
    printf("%.08lf",f);
}
void init(){
}
ll n,m;
int chk(ll x){
    ll f = max(0ll,x-n);
    if(m>=2*f+x*2) return 1;
    else return 0;
}
void read(){
    RII(n,m);
}
void solve(){
    ll p,q,mid,ans;
    p = ans = 0;
    q = max(n,m);
    while(p<=q){
        mid = (p+q)>>1;
        if(chk(mid)){
            ans = mid;
            p = mid+1;
        }
        else q = mid-1;
    }
    cout<<ans<<endl;
}
int main(){
    int nn=1;
    // nn=rit();
    while(nn--){
        // while(cin>>n) 
            init(),read(),solve();
    }
    return 0;
}

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

int main(){
    int n, m;
    cin >> n >> m;
    //vector<int> a(n);
    //vector<int> b(n);
    vector<vector<int> > money_num(n, vector<int>(2));
    for(int i = 0;i < n; i++){
        cin >> money_num.at(i).at(0);
        cin >> money_num.at(i).at(1);

    }
    sort(money_num.begin(), money_num.end());
    int counter = 0;
    long ans = 0;
    /*
    cout << "---------------" << endl;
    for(int i = 0; i < n; i++){
        cout << "A " << money_num.at(i).at(0);
        cout << " B " << money_num.at(i).at(1) << endl;
    }
    cout << "---------------" << endl;
    */
    for(int i = 0; i < n; i++){
        if(counter == m)
                break;
        for(int j = 1; j <= money_num.at(i).at(1); j++){
            if(counter == m)
                break;
            counter++;
            ans += money_num.at(i).at(0);
        }
    }
    cout << ans << endl;
}

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

string s;

int dp[10009][2][100],p,d;


int dfs(int idx,int z,bool tight){
  if(idx==s.size())return !z;
  int &res=dp[idx][tight][z];
  if(~res)return res;
  res=0;
  int r=(tight?9:s[idx]-'0');
  for(int i=0;i<=r;i++){
    res+=dfs(idx+1,(z+i)%d,tight||i<r);
    res%=1000000007;
  }
  return res;
}

int main(){
  memset(dp,-1,sizeof dp);
  cin>>s>>d;
  cout<<(dfs(0,0,0)-1+1000000007)%1000000007<<endl;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


Measured memory_bytes: 8832
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
#define println std::cout << std::endl;
using LL = long long;
#define lrt rt << 1
#define rrt rt << 1 | 1
#define lson l, m, lrt
#define rson m + 1, r, rrt
const int N = 2e5 + 5;
const int NN = N * 3.2;
LL sum[NN], s10[N];
int col[NN];
const LL M = 998244353;
void pushUp(int rt) {
	sum[rt] = sum[lrt] + sum[rrt];
	if (sum[rt] >= M) sum[rt] -= M;
}
void pushDown(int l,int r, int rt) {
	if (col[rt] != -1) {
		int m = (l + r) >> 1;
		col[lrt] = col[rrt] = col[rt];
		col[rt] = -1;
		sum[lrt] = (s10[m] - s10[l - 1] + M) * col[lrt] % M;
		sum[rrt] = (s10[r] - s10[m] + M) * col[rrt] % M;
	}
}
void build(int l, int r, int rt) {
	if (l == r) {
		sum[rt] = s10[r] - s10[l - 1];
		if (sum[rt] < 0) sum[rt] += M;
		col[rt] = 1;
		return;
	}
	col[rt] = 1;
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
	pushUp(rt);
}
void update(int L, int R, int p, int l, int r, int rt) {
	if (L <= l && R >= r) {
		sum[rt] = (s10[r] - s10[l - 1] + M) * p % M;
		col[rt] = p;
		return;
	}
	pushDown(l, r, rt);
	int m = (l + r) >> 1;
	if (L <= m) update(L, R, p, lson);
	if (R > m) update(L, R, p, rson);
	pushUp(rt);
}

int main() {
	//freopen("in","r",stdin);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	s10[0] = 0;
	LL now = 1;
	for (int i = 1; i < N; ++i) {
		s10[i] = now;
		now = now * 10 % M;
	}
	for (int i = 1; i < N; ++i) {
		s10[i] += s10[i - 1];
		if (s10[i] >= M) s10[i] -= M;
	}
	int n, q;
	std::cin >> n >> q;
	build(1, n, 1);
	while (q--) {
		int l, r, d;
		std::cin >> l >> r >> d;
		update(n - r + 1, n - l + 1, d, 1, n, 1);
		print(sum[1]);
	}
	return 0;
}

Measured memory_bytes: 11368
#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 true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++) 
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    //ll N; cin >> N;
    //ll N,M; cin >> N >> M;
    //string S; cin >> S;
    //ll H,W; cin >> H >> W;
    int N;
    cin >> N;
  	int A[N];
    int B[N+1];
  	int rsum=0;
    rep(i,N){
        cin >> A[i];
        if(i!=0){
          B[i]=abs(A[i]-A[i-1]);
          rsum+=B[i];
        }
    }
    B[0]=abs(A[0]);
    B[N]=abs(A[N-1]);
  	rsum+=B[0]+B[N];
    rep(i,N){
      	int sum=rsum-B[i]-B[i+1];
      	if(i==0)sum+=abs(A[1]);
        else if(i==N-1)sum+=abs(A[N-2]);
        else sum+=abs(A[i+1]-A[i-1]);
        cout << sum << endl;
    }
}

/*



 */



Measured memory_bytes: 2048
// https://onlinejudge.u-aizu.ac.jp/problems/0033
// 玉
// 1-10的序列，分成两组，让每一组都升序
// 虽然想让你用dfs，但是这个似乎直接贪心就可以了

#include <iostream>
#include <stack>

using namespace std;
int a[10];

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        for (int i = 0; i < 10; ++i)
            cin >> a[i];
        stack<int> q1;
        stack<int> q2;
        for (int i = 0; i < 10; ++i)
        {
            int t1, t2;
            if (q1.empty())
                t1 = 0;
            else
                t1 = q1.top();
            if (q2.empty())
                t2 = 0;
            else
                t2 = q2.top();
            if (t1 > a[i] && t2 > a[i])
            {
                cout << "NO" << endl;
                break;
            }
            else if (t1 < a[i] && t2 > a[i])
            {
                q1.push(a[i]);
            }
            else if (t1 > a[i] && t2 < a[i])
            {
                q2.push(a[i]);
            }
            else if (t1 < t2)
            {
                q2.push(a[i]);
            }
            else
            {
                q1.push(a[i]);
            }
            if (i == 9)
            {
                cout << "YES" << endl;
            }
        }
        
    }
    return 0;
}


Measured memory_bytes: 3016
#include <iostream>
#include <cstdlib>
#include <climits>

using namespace std;

int main()
{
  int a, b, c, d, ab, bc, ca;
  std::cin >> a >> b >> c >> d;

  ab = abs(a - b);
  bc = abs(b - c);
  ca = abs(c - a);

  if (abs(c - a) <= d)
  {
    cout << "Yes";
    return 0;
  }
  
  int k, l;
  k = abs(a - b);
  l = abs(c - b);
  if (k <= d && l <= d)
  {
    cout << "Yes";
    return 0;
  }

  cout << "No";
  return 0;

}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
#include<map>
#include<iterator>
#include<set>
#include<stack>
#include<queue>
#include<fstream>
#include<iomanip>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include<cmath>
#include<list>
#include <sstream>
#include<unordered_map>
#include<cstring>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define ALL(a) a.begin(),a.end()
#define SZ(a) (int)a.size()
#define PB push_back
#define MP make_pair

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

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 5 * 1000 * 100 + 47;

int P[MAX];
int ANS[MAX];
int M[MAX];
priority_queue<int> q;

struct RMQ
{
	int T[MAX * 4];
	int n;

	int Max(int a, int b)
	{
		return P[a] > P[b] ? a : b;
	}

	void build(int v, int tl, int tr)
	{
		if (tl == tr)
		{
			T[v] = tl;
			return;
		}

		int tm = (tl + tr) / 2;
		build(2 * v, tl, tm);
		build(2 * v + 1, tm + 1, tr);
		T[v] = Max(T[2 * v], T[2 * v + 1]);
	}

	void init(int n)
	{
		this->n = n;
		build(1, 0, n - 1);
	}

	int get1(int v, int tl, int tr, int l, int r)
	{
		if (l > r) return n - 1;

		if (tl == l && tr == r) return T[v];

		int tm = (tl + tr) / 2;
		int v1 = get1(2 * v, tl, tm, l, min(r, tm));
		int v2 = get1(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
		return Max(v1, v2);
	}

	int get(int l, int r)
	{
		return get1(1, 0, n - 1, l, r);
	}

	void update(int v, int tl, int tr, int ind, int val)
	{
		if (tl == tr)
		{
			T[v] = tl;
			P[tl] = val;
			return;
		}

		int tm = (tl + tr) / 2;
		if (tm >= ind)
		{
			update(2 * v, tl, tm, ind, val);
		}
		else
		{
			update(2 * v + 1, tm + 1, tr, ind, val);
		}

		T[v] = Max(T[2 * v + 1], T[2 * v]);
	}

	void update(int ind, int val)
	{
		update(1, 0, n - 1, ind, val);
	}
} R;

int n, k;
void upd(int block)
{
	int l = block * k;
	int r = min((block + 1) * k - 1, n - 1);
	int ind = R.get(l, r);
	if (ind == M[block] || ind == n) return;
	int v = R.get(max(ind - k + 1, 0), min(ind + k - 1, n - 1));
	if (v == ind)
	{
		q.push(ind);
		M[block] = ind;
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	FOR(i, 0, n)
	{
		cin >> P[i];
		P[i]--;
	}

	P[n] = -INF;
	R.init(n + 1);
	int sz = (n + k - 1) / k;
	FILL(M, -1);

	FOR(i, 0, sz)
	{
		upd(i);
	}

	int ind = n - 1;
	while (!q.empty())
	{
		int pos = q.top();
		q.pop();
		ANS[pos] = ind;
		R.update(pos, -INF);
		int block = pos / k;
		upd(block);
		if (block) upd(block - 1);
		if (block + 1 != sz) upd(block + 1);
		ind--;
	}

	FOR(i, 0, n) cout << ANS[i] + 1 << "\n";
	system("pause");
}

Measured memory_bytes: 19560
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

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


const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int N;
ll A,B;
vector<ll> X;
const ll INF = (1LL << 60);
const int MAX_N = 100010;
ll dp[MAX_N];

ll memo(int pos){
  if (pos == N - 1){
    return 0;
  }
  ll &res = dp[pos];
  if (res >= 0){
    return res;
  }
  res = INF;
  ll next_pos = X[pos + 1];
  ll dist = next_pos - X[pos];
  //walk
  res = min(res, memo(pos + 1) + dist * A);
  //teleport
  res = min(res, memo(pos + 1) + B);
  return res;
}

int main() {
  cin >> N >> A >> B;
  X.resize(N);
  for (auto &val : X){
    cin >> val;
  }
  memset(dp, -1, sizeof(dp));
  cout << memo(0) << endl;
  return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, a[200008];

int main(){
	cin >> n;
	a[0] = 0;
	for(ll i = 1; i <= n; i++){cin >> a[i];}
	for(ll i = 2; i <= n; i++){a[i] +=  a[i-1];}
	
	map<ll, ll> m;
	for(ll i = 0; i <= n; i++){
		if(m.find(a[i]) == m.end()){m[a[i]] = 1;}
		else{m[a[i]]++;}
	}
	
	ll ans = 0;
	for(auto itr = m.begin(); itr != m.end(); itr++){
		ll cnt = itr->second;
		ans += cnt*(cnt-1)/2;
	}
	
	cout << ans << endl;
	return 0;
}

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

 int main ()

 {
     int a , b ,c ;
     cin >> a >> b >> c ;

     if ((a==b && b != c ) || (b == c && b != a) || (a == c && a != b)){
        cout << "Yes" ;
     }
      else
        cout << "No" ;



     return 0 ;
 }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long mod=998244353;
long long n,a,b,c,k,ans;
long long fac[300005],rev[300005];
long long power(long long x,long long y,long long mod){
	if(y==0){
		return 1;
	}else{
		long long dm=power(x,y/2,mod);
		if(y%2==1){
			return ((dm*dm)%mod*x)%mod;
		}else{
			return (dm*dm)%mod;
		}
	}
}
long long inverse_mod(long long a,long long mod){
	return power(a,mod-2,mod);
}
long long C(int k,int n){
	if(k>n){
		return 0;
	}else{
	    return ((fac[n]*rev[k]%mod)*rev[n-k])%mod;
	}
}
int main(){
	cin>>n>>a>>b>>k;
	fac[0]=1;
	rev[0]=inverse_mod(fac[0],mod);
	for(int i=1;i<=n;i++){
		fac[i]=(fac[i-1]*i)%mod;
		rev[i]=inverse_mod(fac[i],mod)%mod;
	}
	if(k==0){
		cout<<"1";
	}else{
		for(long long x=1;x<=k/a&&x<=n;x++){
			long long tmp=k-a*x;
			if(tmp%b==0){
				long long y=tmp/b;
			    ans=(ans+(C(x,n)%mod)*(C(y,n)%mod)%mod)%mod;
			}
		}
		cout<<ans;
	}
}

Measured memory_bytes: 4992
#include <vector>
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i = 0;i<(n);i++)
#define revrep(i,n) for(int i = (n)-1;i>=0;i--)
using namespace std;

int main(){
	vector<int> V;
	while(1){
		V.clear();
		int n,r;
		cin >> n >> r;
		if(n == 0 && r == 0){
			break;
		}
		revrep(i,n){
			V.push_back(i + 1);
		}
		// rep(i,V.size()){
		// 		cout << V[i];
		// 	}
		// cout << endl;
		rep(qery,r){
			int p,c;
			cin >> p >> c;
			rotate(begin(V),begin(V)+p-1,begin(V)+p+c-1);
			// rep(i,V.size()){
			// 	cout << V[i];
			// }
			// cout << endl;
		}
		cout << V[0] << endl;
	}
	return 0;
}

Measured memory_bytes: 1220
def dec2bin(n, base=10):
    s=""
    x="01"
    while n>0:
        s+=x[n%2]
        n/=2
    return (s+"0"*base)[:base]

x=[[0 for i in range(50)] for i in range(11)]
for i in range(0, 2**10):
    tmp = dec2bin(i)
    s=0
    c=0
    for j in range(10):
        if tmp[j]=="1":
            s+=j
            c+=1
    x[c][s]+=1

while True:
    n, s=map(int, raw_input().split())
    if n==0 and s==0: break
    if s>=50: print 0
    else: print x[n][s]

Measured memory_bytes: 4276
n = int(input())

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

ans = 0
for c in range(1, n):
    d = primeFactor(n-c)
    temp = 1
    for k, v in d.items():
        temp *= (v+1)
    ans += temp
print(ans)


Measured memory_bytes: 68672
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
//#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int calc(int a, int b, char op){
	if(op=='+') return a+b;
	if(op=='-') return a-b;
	if(op=='*') return a*b;
}


signed main() {
	while (1) {
		int sum = 0;
		vi d;
		rep(i, 0, 4) {
			int num;
			cin >> num;
			d.push_back(num);
			sum += d[i];
		}
		if (sum == 0) break;
		bool f = false;
		char op[4] = { "+-*" };
		sort(all(d));
		do {
			/*rep(i, 0, 4) {
				cout << d[i] << " ";
			}
			cout << endl;*/
			rep(i, 0, 3) {
				rep(j, 0, 3) {
					rep(k, 0, 3) {
						int t1 = calc(d[0], d[1], op[i]);
						int t2 = calc(d[2], d[3], op[k]);
						int t3 = calc(t1, d[2], op[j]);
						int t4 = calc(d[1], d[2], op[j]);
						int t5 = calc(d[0], t4, op[i]);
						int t6 = calc(d[1], t2, op[j]);
						int t7 = calc(t4, d[3], op[k]);
						if (calc(t1, t2, op[j]) == 10) {
							printf("((%d %c %d) %c (%d %c %d))\n", d[0], op[i], d[1], op[j], d[2], op[k], d[3]);
							k = 3; j = 3; i = 3; f = true;
						}
						else if (calc(t3, d[3], op[k]) == 10) {
							printf("(((%d %c %d) %c %d) %c %d)\n", d[0], op[i], d[1], op[j], d[2], op[k], d[3]);
							k = 3; j = 3; i = 3; f = true;
						}
						else if (calc(t5, d[3], op[k]) == 10) {
							printf("((%d %c (%d %c %d)) %c %d)\n", d[0], op[i], d[1], op[j], d[2], op[k], d[3]);
							k = 3; j = 3; i = 3; f = true;
						}
						else if (calc(d[0], t6, op[i]) == 10) {
							printf("(%d %c (%d %c (%d %c %d)))\n", d[0], op[i], d[1], op[j], d[2], op[k], d[3]);
							k = 3; j = 3; i = 3; f = true;
						}
						else if (calc(d[0], t7, op[i]) == 10) {
							printf("(%d %c ((%d %c %d) %c %d))\n", d[0], op[i], d[1], op[j], d[2], op[k], d[3]);
							k = 3; j = 3; i = 3; f = true;
						}
						if(f) break;
					}
					if(f) break;
				}
				if(f) break;
			}
			if (f) break;
		} while (next_permutation(all(d)));
		if (f == false) cout << 0 << endl;
	}
}

Measured memory_bytes: 1244
#include <iostream>
using namespace std;
int main(void){
    int fibary[50];
    int n;
    cin >> n ;
    fibary[0]=fibary[1]=1;
    for(int i=2;i<=n;i++) {
        fibary[i]=fibary[i-1]+fibary[i-2];
    }
    cout << fibary[n] << endl;
    return 0;
}

Measured memory_bytes: 1160
#include "bits/stdc++.h"

typedef long long ll;
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define REP(i,n) for (int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
 
using namespace std;


int main(){
    ll n;
    cin >> n;
    ll a[n],b[n];

    ll cnt = 0;
    REP(i,n){
        cin >> a[i];
        b[i] = a[i];
        a[i] -= i+1;
    }
    sort(a,a+n);
    REP(i,n){
        cnt += abs(b[i] - (i + 1 + a[n/2]));
    }
    
    cout << cnt;

    return 0;
}


Measured memory_bytes: 3328
n=int(input())
a=list(map(int,input().split()))
s=0
for i in range(n):
    if a[i]<0:
        s+=1
        a[i]*=-1
if s%2==0:
    print(sum(a))
else:
    a.sort()
    print(sum(a)-2*a[0])

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

int main(){

string str;

int alp[26]={};

while(getline(cin, str)){

    for(int i=0;i<str.size();i++){
        if('a'<=str[i] && str[i]<='z'){
            alp[str[i]-'a']++;
            
        }else if('A'<=str[i] && str[i]<='Z'){
            alp[str[i]-'A']++;

        }
    }

}

for(int i=0;i<26;i++){

    cout<<char('a'+i)<<" : "<<alp[i]<<endl;
}


}


Measured memory_bytes: 3180
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9+7;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
//typedef boost::multiprecision::cpp_int bigint;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef unsigned long long ULL;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	string S;
	cin >> S;
	int N = S.size();
	bool flag = true;
	for (int i = 0; i < N; i++) {
		if (S[i] != S[N - i - 1])flag = false;
	}
	for (int i = 0; i < (N - 1) / 2; i++) {
		if (S[i] != S[(N - 1) / 2 - 1 - i])flag = false;
	}
	for (int i = 0; i < N / 2; i++) {
		if (S[i + (N + 1) / 2] != S[N / 2 - i - 1 + (N + 1) / 2])flag = false;
	}
	if (flag)cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 3156
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
   cin >> a >> b;
   int sum=a;
   int cunt=1;
   if(b==1){
    cout << "0";
    return 0;
   }
   for(int i=0;;i++){
    if(sum<b) cunt++;
    else if(sum>=b){
        cout << cunt;
        return 0;
    }
     sum+=a-1;
   }
   //cout << cunt;

    return 0;
}


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

using namespace std;
typedef long long ll;

int main(){
    int n, m; cin >> n >> m;
    vector< pair <int , string> > p(n);
    int ans = 0;
    int ng = 0;
    for(int i = 0; i< m ;i++){
        int q;
        string res;
        cin >> q >> res;
        if(res == "AC"){
            if(p[q-1].second != "AC"){
                ans++;
                ng += p[q-1].first;
                p[q-1].second = "AC";
            }
        }else{
            p[q-1].second == "WA";
            p[q-1].first++;
        }
    }
    cout << ans << " " << ng << endl;
}

Measured memory_bytes: 6528