akhauriyash/Code-Regression huggingface dataset:
import sys
from itertools import accumulate

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    for _ in range(k if k < 60 else 60):
        imos = [0] * (n + 1)
        for i in range(n):
            left = max(0, i - A[i])
            imos[left] += 1
            right = min(n, i + A[i] + 1)
            imos[right] -= 1

        B = list(accumulate(imos))
        A = B
    print(*A[:n])


if __name__ == '__main__':
    resolve()


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

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

  for(int i = N; i <= 999; ++i){
    const auto s = to_string(i);
    if(s[0] == s[1] && s[1] == s[2]){
      cout << i << endl;
      break;
    }
  }
}


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

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

	string str = "";
	int cnt = 0;
	for(int i = 0; i < n; i++){
		if(s[i] == ')')cnt--;
		else cnt++;

		if(cnt < 0){
			str += '(';
			cnt++;
		}
	}
	cout << str << s;
	for(int i = 0; i < cnt; i++)cout << ')';
	cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
LL n,m;
LL x[N],y[N],fa[N],size[N],v[N];

int getfa(int x) {
	if (x==fa[x]) return x;
	int f=getfa(fa[x]);
	size[f]+=size[x];
	size[x]=0;
	return fa[x]=f;
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=m;i++) scanf("%lld%lld",&x[i],&y[i]);
	
	LL ans=n*(n-1)/2;
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=1;i<=n;i++) size[i]=1;
	for (int i=m;i;i--) {
		//printf("%lld\n",ans);
		v[i]=ans;
		int fx=getfa(x[i]),fy=getfa(y[i]);
		if (fx!=fy) {
			ans-=size[fx]*size[fy];
			fa[fy]=fa[fx];
			size[fx]+=size[fy];
			size[fy]=0;
		}
	}
	
	for (int i=1;i<=m;i++) printf("%lld\n",v[i]);
	return 0;
}

Measured memory_bytes: 5248
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
        String T = sc.nextLine();
        System.out.println(T.substring(0, S.length()).equals(S) ? "Yes" : "No");
    }
}

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

struct StCond                  // 材料質量・限界量
{
  StCond() : m_nWaterA(0), m_nWaterB(0),
             m_nSugerC(0), m_nSugerD(0),
             m_nConcE(0),  m_nLimitF(0) { }

  int m_nWaterA, m_nWaterB;
  int m_nSugerC, m_nSugerD;
  int m_nConcE;
  int m_nLimitF;
};

struct StAmt                   // 使用量
{
  StAmt() : m_nAmtA(0), m_nAmtB(0), m_nAmtC(0), m_nAmtD(0) { }

  int m_nAmtA, m_nAmtB, m_nAmtC, m_nAmtD;
};

struct StReslt                  // 出力結果
{
  StReslt() : m_nAllMass(0), m_nSugerMass(0) { }

  int m_nAllMass, m_nSugerMass;
};

void fnInput(StCond& roCond)
{
  cin >> roCond.m_nWaterA >> roCond.m_nWaterB >> roCond.m_nSugerC >> roCond.m_nSugerD;
  cin >> roCond.m_nConcE  >> roCond.m_nLimitF;
}

int fnAmtSumup(string sProc, const StCond& cnroCond, const StAmt& cnroAmt)
{ 
  if      (sProc == "A")
    return  (cnroCond.m_nWaterA * cnroAmt.m_nAmtA) * 100;
  if      (sProc == "A+B")
    return  (cnroCond.m_nWaterA * cnroAmt.m_nAmtA + cnroCond.m_nWaterB * cnroAmt.m_nAmtB) * 100;
  else if (sProc == "A+B+C")
    return  (cnroCond.m_nWaterA * cnroAmt.m_nAmtA + cnroCond.m_nWaterB * cnroAmt.m_nAmtB) * 100 
          + (cnroCond.m_nSugerC * cnroAmt.m_nAmtC);
  else if (sProc == "A+B+C+D")
    return  (cnroCond.m_nWaterA * cnroAmt.m_nAmtA + cnroCond.m_nWaterB * cnroAmt.m_nAmtB) * 100 
          + (cnroCond.m_nSugerC * cnroAmt.m_nAmtC + cnroCond.m_nSugerD * cnroAmt.m_nAmtD);
  else           // "C+D" 
    return  (cnroCond.m_nSugerC * cnroAmt.m_nAmtC + cnroCond.m_nSugerD * cnroAmt.m_nAmtD);
}

double fnConcCalc(const StCond& cnroCond, const StAmt& cnroAmt)
{
  static double stnLimtConc = 0.0;
  double nNowConc = 0.0;

  if (!stnLimtConc)
    stnLimtConc = cnroCond.m_nConcE / (100.0 + cnroCond.m_nConcE);

  if ( fnAmtSumup("A+B+C+D", cnroCond, cnroAmt) )
  {
    nNowConc =  (double)fnAmtSumup("C+D", cnroCond, cnroAmt)
               /        fnAmtSumup("A+B+C+D", cnroCond, cnroAmt);
    if (stnLimtConc < nNowConc)
      return -1.0;
    else
      return nNowConc;
  }
  else
    return -1.0;
}

void fnConcCheck(const StCond& cnroCond, StReslt& roReslt)
{
  StAmt oAmt;
  double nMaxConc = -1.0;
  
  for ( oAmt.m_nAmtA = 0; 
        fnAmtSumup("A", cnroCond, oAmt) <= cnroCond.m_nLimitF; oAmt.m_nAmtA++ )
  {
    for ( oAmt.m_nAmtB = 0; 
          fnAmtSumup("A+B", cnroCond, oAmt) <= cnroCond.m_nLimitF; oAmt.m_nAmtB++ )
    {
      for ( oAmt.m_nAmtC = 0; 
            fnAmtSumup("A+B+C", cnroCond, oAmt) <= cnroCond.m_nLimitF; oAmt.m_nAmtC++ )
      {
        for ( oAmt.m_nAmtD = 0;
              fnAmtSumup("A+B+C+D", cnroCond, oAmt) <= cnroCond.m_nLimitF; oAmt.m_nAmtD++ )
        {
          double nNowConc = fnConcCalc(cnroCond, oAmt);
          if (nMaxConc < nNowConc)
          {
            nMaxConc = nNowConc;
            roReslt.m_nAllMass = fnAmtSumup("A+B+C+D", cnroCond, oAmt);
            roReslt.m_nSugerMass = fnAmtSumup("C+D", cnroCond, oAmt);
          }
        }
      }
    }
  }
}

int main()
{
  StCond oCond;
  StReslt oReslt;

  fnInput(oCond);
  fnConcCheck(oCond, oReslt);
  cout << oReslt.m_nAllMass << " " << oReslt.m_nSugerMass << endl;

  return 0;
}

Measured memory_bytes: 3620
/*{{{*/
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB emplace_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    int M,N;
    R(N,M);
    VI A(N);
    int s=0;
    REP(i,N){
        R(A[i]);
        s+=A[i];
    }
    int c=0;
    REP(i,N){
        if(A[i]*4*M>=s)c++;
    }
    W(c>=M?"Yes":"No");
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<int64_t> A(n);
    copy_n(istream_iterator<int64_t>(cin), n, A.begin());
    vector<int64_t> S(n + 1);
    const int64_t INF = 1e17;
    int64_t ans = INF;

    for (int i = 0; i < n; i++)
        S[i + 1] = S[i] + A[i];

    int i = 1, k = 3;
    for (int j = 2; j < n - 1; j++){
        while(i < j - 1 and S[i] < S[j] - S[i])
            i++;
        while(k < n - 1 and S[k] - S[j] < S[n] - S[k])
            k++;
        for (int a = 0; a <= 1; a++){
            for (int b = 0; b <= 1; b++){
                vector<int64_t> D(4);
                D[0] = S[max(1, i - a)];
                D[1] = S[j] - D[0];
                D[2] = S[max(j + 1, k - b)] - S[j];
                D[3] = S[n] - S[max(j + 1, k - b)];
                int64_t ma = *max_element(D.begin(), D.end());
                int64_t mi = *min_element(D.begin(), D.end());
                ans = min(ans, ma - mi);
            }
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 3328
K = int(input())
if K == 1:
    print('ACL')
elif K == 2:
    print('ACLACL')
elif K == 3:
    print('ACLACLACL')
elif K == 4:
    print('ACLACLACLACL')
elif K == 5:
    print('ACLACLACLACLACL')

Measured memory_bytes: 9016
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const int MOD = 1000000007;

template <typename T>
void print(const T &v);

int main()
{
    vector<int> x(5);
    rep(i, 5) cin >> x[i];
    for (int i = 0; i < 5; i++)
    {
        if (x[i] == 0)
        {
            cout << i + 1 << endl;
            return 0;
        }
    }
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


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

using namespace std;

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

    t.erase(s.length());
    if (s == t) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}



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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;
const int MOD = 1e9 + 7;

int main()
{
    int a, b, c, x;
    cin >> a >> b >> c >> x;

    int ans = 0;
    rep(i,a+1){
        rep(j,b+1){
            if (0 <= x / 50 - 10 * i - 2 * j && x / 50 - 10 * i - 2 * j<=c){
                ans++;
            }
        }
    }

    cout << ans << endl;
    return (0);
}


Measured memory_bytes: 3596
def max(a, b); a < b ? b : a; end
def min(a, b); a < b ? a : b; end

class Problem
  attr_accessor *(?a..?z).to_a.map(&:to_sym)

  def initialize
    @n = gets.to_s.to_i
    @s = gets.chomp
  end

  def solve
    lo = 0
    hi = n - 1
    ans = 0
    while lo < hi
      if s[lo] == "R" && s[hi] == "W"
        lo += 1
        hi -= 1
      elsif s[lo] == "W" && s[hi] == "R"
        ans += 1
        lo += 1
        hi -= 1
      elsif s[lo] == "R" && s[hi] == "R"
        lo += 1
      else
        hi -= 1
      end
    end
    ans
  end

  def show(ans)
    puts ans
  end
end

Problem.new.instance_eval do
  show(solve)
end


Measured memory_bytes: 14672
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <stack>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
#define int long long
#define vint vector<int>
#define pint pair<int, int>
#define pb(a) push_back(a)
#define all(v) v.begin(), v.end()
#define dbg(x) cerr << #x << " = " << (x) << endl
#define yn(b) cout << ((b) ? "Yes" : "No") << endl
#define YN(b) cout << ((b) ? "YES" : "NO") << endl

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

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second > b.second;
    }else{
        return a.first > b.first;
    }
}

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

	int N, M;

	cin >> N >> M;
	vint A(N);
	vector<pint> B(M);

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

	for (int i = 0; i < M; i++) {
		pint tmp;
		cin >> tmp.first >> tmp.second;
		B[i] = tmp;
	}
	
	sort(all(A));
	sort(all(B),compare_by_b);
	/*
	cout<<"--------------"<<endl;
	for (int i = 0; i < M; i++) {
		cout<<B[i].first<<" "<<B[i].second<<endl;
	}
	cout<<"--------------"<<endl;*/
	
	int key = 0;
	for (int i = 0; i < M; i++) {

		for (int j = 0; j < B[i].first; j++) {
			int x = B[i].second;
			if(key>=A.size()){
				goto END;
			}
			if(A[key]<x){
				A[key]=x;
			}else{
				goto END;
			}
			key++;
		}
	}
	END:
	
	int ans=0;
	for (int i = 0; i < N; i++) {
		dbg(A[i]);
		ans+=A[i];
	}
	
	cout<<ans<<endl;

	return 0;
}

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

int main(){
    char A[4] = {'A', 'C', 'G', 'T'};
    char O[4] = {'T', 'G', 'C', 'A'};
    char b;
    cin >> b;
    
    for(int i = 0; i < 4; i++){
        if(b == A[i])
            cout << O[i];
    }
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int sum1 = 0;
		int sum2 = 0;
		long cnt1 = 0;
		long cnt2 = 0;
		for (int i=0;i<n;i++){
			int x = sc.nextInt();
			sum1+=x;
			sum2+=x;
			if (i%2==0) {
				if(sum1>=0){
					cnt1+=sum1+1;
					sum1=-1;
				}
				if (sum2<=0) {
					cnt2+=-sum2+1;
					sum2=1;
				}
			}else{
				if(sum1<=0){
					cnt1+=-sum1+1;
					sum1=1;
				}
				if (sum2>=0){
					cnt2+=sum2+1;
					sum2=-1;
				}
			}
		}
		System.out.println(Math.min(cnt1, cnt2));
	}
}


Measured memory_bytes: 48740
#include<cstdio> 
#include<cctype>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
long long k,a,b;
int main(){
	cin >> k >> a >> b;
	if(k < (a + 1)){
		printf("%lld\n",k + 1);
		return 0;	
	}
	if(b <= a + 2){
		printf("%lld\n",k + 1);
		return 0;
	}
	else{
		long long  ans = 0;
		ans = b;k = k - a - 1;
		ans += (k / 2) * (b - a);
		k %= 2;
		ans += k;
		cout << ans;
		return 0;	
	}
	return 0;
}

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

void Main() {
	string S;
	cin >> S;
	if (S.compare("ABC") == 0) {
		cout << "ARC" << endl;
	}
	else {
		cout << "ABC" << endl;
	}
}

int main() {
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

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

#define int long long

int X, Y, Z, K;
vector<int> A, B, C;
vector<int> cand;
vector<int> ans;

signed main() {
  cin >> X >> Y >> Z >> K;
  A.resize(X);
  B.resize(Y);
  C.resize(Z);
  for (int i = 0; i < X; i++) { cin >> A[i]; }
  for (int i = 0; i < Y; i++) { cin >> B[i]; }
  for (int i = 0; i < Z; i++) { cin >> C[i]; }

  // AとBの組み合わせをあらかじめ求める
  for (int i = 0; i < X; i++) {
    for (int j = 0; j < Y; j++) {
      cand.push_back(A[i] + B[j]);
    }
  }

  // candを降順にする
  sort(cand.begin(), cand.end());
  reverse(cand.begin(), cand.end());

  vector<int> ans;
  for (int i = 0; i < min(K, (int)cand.size()); i++) {
    for (int j = 0; j < Z; j++) {
      ans.push_back(cand[i] + C[j]);
    }
  }

  // 答えを降順にする
  sort(ans.begin(), ans.end());
  reverse(ans.begin(), ans.end());

  for (int i = 0; i < K; i++) {
    cout << ans[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 43112
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll i=0;i<n;i++)cin>>a[i];
    ll ans=0,memo=0;
    for(ll i=0;i<n-1;i++){
        if(a[i]>=a[i+1])memo++;
        else {
            memo=0;
        }
        ans=max(ans,memo);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cctype>
#include <stack>
#include <bitset>
#include <unordered_set>
#include <map>
#include <set>
#include <cmath>
//#include <bits/stdc++.h>

using namespace std;
typedef long long lolo;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef unsigned long long ulolo;

const int maxn = (int)2e5 + 5;
const lolo maxx = (lolo)10000001;
const int maxm =(int)2e3 + 5;
const int INF = 0x3f3f3f3f;
const lolo inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const int MOD = (int)1e6 + 3;

template<class T>
inline void read(T &x) {
    x = 0; T flag = 1;char c;
    do { c = (char) getchar(); if (c == '-') break; } while (c < '0' || c > '9');
    if (c == '-') { c = '0', flag = -1;}
    do { x = x * 10 + c - '0';c = (char) getchar();} while (c >= '0' && c <= '9');
    x *= flag;
}
template<class T>
inline void out(T x) {
    if (x > 9) out(x / 10);
    x = x % 10;
    putchar('0' + x);
}

int to[maxn<<1], nxt[maxn<<1], head[maxn], tot, n;
void add_edge(int u, int v) {
    to[tot] = v;
    nxt[tot] = head[u];
    head[u] = tot++;
}
int dist[maxn];
int BFS(int u) {
    memset(dist, -1, sizeof(int)*(n+1));
    dist[u]=1;
    queue<int> Q;
    Q.push(u);
    int f = u;
    while (!Q.empty()) {
        u = Q.front();Q.pop();
        for (int i = head[u]; i != -1; i=nxt[i]) {
            int& v = to[i];
            if (dist[v]==-1) {
                dist[v]=dist[u]+1;
                Q.push(v);
                if (dist[v]>dist[f]) {
                    f = v;
                }
            }
        }
    }
    return f;
}
int f[maxn];
int main() {
    read(n);
    memset(head, -1, sizeof(head));
    tot = 0;
    int u, v;
    for (int i = 1; i < n; ++i) {
        read(u);
        read(v);
        add_edge(u, v);
        add_edge(v, u);
    }
    int x = BFS(1);
    int y = BFS(x);
    y = dist[y];
    f[0]=f[2]=0;
    f[1]=1;
    for (int i = 3; i < y+1; ++i) {
        if (f[i-1]&&f[i-2]) {
            f[i]=0;
        } else {
            f[i]=1;
        }
    }
    puts(f[y]?"First":"Second");
    return 0;
}


Measured memory_bytes: 5760
int main(){
    int a, b, c, n;
    scanf("%d%d%d", &a, &b, &c);
    if(a>b){
        n=a;
        a=b;
        b=n;}
    if(b>c){
        n=b;
        b=c;
        c=n;}
    if(a>b){
        n=a;
        a=b;
        b=n;}
    printf("%d %d %d\n", a, b, c);
    return 0;
}

Measured memory_bytes: 596
#include<iostream>
using namespace std;
int n;
void countingsort(int *a,int k){
  int count[10001]={},b[2000001]={};
  for(int i=0;i<n;++i) ++count[a[i]];
  for(int i=1;i<=k;++i) count[i]+=count[i-1];
  for(int i=n-1;i>=0;--i){
    b[count[a[i]]]=a[i];
    --count[a[i]];
  }    
  for(int i=0;i<n;++i){
    if(i) cout<<" ";
    cout<<b[i+1];
  }
  cout<<endl;
}
int main(){
  int m=0,a[2000000]; cin>>n;
  for(int i=0;i<n;++i){
    cin>>a[i];
    if(m<a[i]) m=a[i];
  }
  countingsort(a,m);
  return 0;
}



Measured memory_bytes: 18724
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <unordered_map>
constexpr int MOD = 1000000000 + 7;
constexpr int INF = 2000000000;
using namespace std;
using LL = long long;
int main() {
	LL n, a, b;
	cin >> n >> a >> b;
	LL ans = 0;
	LL x[100001];
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	for (int i = 0; i < n - 1; i++) {
		ans += min((x[i + 1] - x[i])*a, b);
	}
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>

#define N 30
#define M 30

int main() {
	static int kk[M];
	int n, n_, m, a, cnt;

	scanf("%d%d", &n, &m);
	n_ = n;
	while (n--) {
		int k;

		scanf("%d", &k);
		while (k--) {
			scanf("%d", &a), a--;
			kk[a]++;
		}
	}
	cnt = 0;
	for (a = 0; a < m; a++)
		if (kk[a] == n_)
			cnt++;
	printf("%d\n", cnt);
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define mt make_tuple
#define mp make_pair
#define pu push_back
#define INF 1000000001
#define MOD 1000000007
#define EPS 1e-6
#define ll long long int
#define ld long double
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define pr(v) { for(int i=0;i<v.size();i++) { v[i]==INF? cout<<"INF " : cout<<v[i]<<" "; } cout<<endl;}
#define t1(x)                cerr<<#x<<" : "<<x<<endl
#define t2(x, y)             cerr<<#x<<" : "<<x<<" "<<#y<<" : "<<y<<endl
#define t3(x, y, z)          cerr<<#x<<" : " <<x<<" "<<#y<<" : "<<y<<" "<<#z<<" : "<<z<<endl
#define t4(a,b,c,d)          cerr<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<" "<<#d<<" : "<<d<<endl
#define t5(a,b,c,d,e)          cerr<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<" "<<#d<<" : "<<d<<" "<<#e<<" : "<<e<<endl
#define t6(a,b,c,d,e,f)          cerr<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<" "<<#d<<" : "<<d<<" "<<#e<<" : "<<e<<" "<<#f<<" : "<<f<<endl
#define GET_MACRO(_1,_2,_3,_4,_5,_6,NAME,...) NAME
#define t(...) GET_MACRO(__VA_ARGS__,t6,t5, t4, t3, t2, t1)(__VA_ARGS__)
#define _ cerr<<"here"<<endl;
#define __ {ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}

using namespace std;
template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &a){ return out<<"("<<a.first<<", "<<a.second<<")";}
template <int> ostream& operator<<(ostream& os, const vector<int>& v) { os << "["; for (int i = 0; i < v.size(); ++i) { if(v[i]!=INF) os << v[i]; else os << "INF";if (i != v.size() - 1) os << ", "; } os << "]\n"; return os; } 
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { os << "["; for (int i = 0; i < v.size(); ++i) { os << v[i]; ;if (i != v.size() - 1) os << ", "; } os << "]\n"; return os; } 


int main()
{
  __;
  int n;
  cin >> n;
  string s;
  cin >> s;
  int cnt = 0;
  for(int i=0;i<n-2;i++)
  {
    if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C') cnt++;
  }
  cout << cnt << endl;
  return 0;
}


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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#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 SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//main code

vector<vector<char>> grid;

struct UnionFind
{
	// par[i]：データiが属する木の親の番号。i == par[i]のとき、データiは木の根ノードである
	vector<LL> par;
	// sizes[i]：根ノードiの木に含まれるデータの数。iが根ノードでない場合は無意味な値となる
	vector<LL> sizes;

	UnionFind(LL n) : par(n), sizes(n, 1) {
		// 最初は全てのデータiがグループiに存在するものとして初期化
		for(LL i = 0;i < n;i++) par[i] = i;
	}

	// データxが属する木の根を得る
	LL find(LL x) {
		if (x == par[x]) return x;
		return par[x] = find(par[x]);  // 根を張り替えながら再帰的に根ノードを探す
	}

	// 2つのデータx, yが属する木をマージする
	void unite(LL x, LL y) {
		// データの根ノードを得る
		x = find(x);
		y = find(y);

		// 既に同じ木に属しているならマージしない
		if (x == y) return;

		// xの木がyの木より大きくなるようにする
		if (sizes[x] < sizes[y]) swap(x, y);

		// xがyの親になるように連結する
		par[y] = x;
		sizes[x] += sizes[y];
		// sizes[y] = 0;  // sizes[y]は無意味な値となるので0を入れておいてもよい
	}

	// 2つのデータx, yが属する木が同じならtrueを返す
	bool same(LL x, LL y) {
		return find(x) == find(y);
	}

	// データxが含まれる木の大きさを返す
	LL size(LL x) {
		return sizes[find(x)];
	}
};

int main(int argc, char const* argv[])
{
	LL h,w;
	cin >> h >> w;
	grid = vector<vector<char>>(h,vector<char>(w));
	for (LL i = 0; i < h; i++) {
		for (LL j = 0; j < w; j++) {
			cin >> grid[i][j];
		}
	}
	LL ans = 0;
	UnionFind uf(h*w);
	for (LL i = 0; i < h; i++) {
		for (LL j = 0; j < w; j++) {
			if (j != w-1) {
				if (grid[i][j] != grid[i][j+1]) {
					uf.unite(i*w+j,i*w+j+1);
				}
			}
			if (i != h-1) {
				if (grid[i][j] != grid[i+1][j]) {
					uf.unite(i*w+j,(i+1)*w+j);
				}
			}
		}
	}
	map<LL,LL> num_b;
	for (LL i = 0; i < h; i++) {
		for (LL j = 0; j < w; j++) {
			if (grid[i][j] == '#') {
				num_b[uf.find(i*w+j)]++;
			}
		}
	}
	for (auto&& var : num_b) {
		ans += var.second * (uf.size(var.first) - var.second);
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
  int n,l;
  cin >> n >> l;
  vector<int> s;
  for(int i = 1;i <= n;i++){
    s.push_back(l+i-1);
  }
  bool flag = false;
  bool flag_o = false;
  for(int i = 0;i < n;i++){
    if(s[i] < 0){
      flag = true;
    }
    if(s[i] == 0){
      flag_o = true;
    }
  }
  int add = 0;
  if(flag != true){
    for(int i = 1;i < n;i++){
      add += s[i];
    }
  }
  else if(flag == true && flag_o == true){
    for(int i = 0;i < n;i++){
      if(s[i] != 0){
        add += s[i];
      }
    }
  }
  else if(flag == true && flag_o != true){
    for(int i = 0;i < n-1;i++){
      add += s[i];
    }
  }
  cout << add << endl;
}


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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

inline bool eq(char a, char b) {
    if (a == 'b')return b == 'd';
    if (a == 'd')return b == 'b';
    if (a == 'p')return b == 'q';
    if (a == 'q')return b == 'p';
    return a == b;
}

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

    li n = sz(s);
    if (n % 2 > 0) {
        puts("No");
        return 0;
    }
    rep(i, n / 2) {
        if (!eq(s[i], s[n - 1 - i])) {
            puts("No");
            return 0;
        }
    }
    puts("Yes");

    return 0;
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

ll bit[63];

const ll mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    ll a;
    memset(bit, 0, sizeof(bit));
    ll ans = 0LL;
    rep(i,n){
        cin >> a;
        rep(j,63){
            if((a>>j) & 1) bit[j]++;
        }
    }
    ll tmp = 1LL;
    rep(i,63){
        if(bit[i] == 0){
            tmp = (tmp * 2) % mod;
            continue;
        }
        ll p = ((n-bit[i]) * bit[i]) % mod;
        p = (tmp * p) % mod;
        ans = (ans + p) % mod;
        tmp = (tmp * 2) % mod;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	string S;
	cin >> N >> S;
	vector< vector<string> > V[2];
	for(int k = 0; k < 2; k++) {
		V[k].resize(N+1);
		if(k) reverse(begin(S), end(S));
		for(int i = 0; i < (1<<N); i++) {
			string s1, s2;
			for(int j = 0; j < N; j++)
				if((i>>j)&1) s1 += S[j];
				else s2 += S[j];
			V[k][s1.length()].push_back(s1+s2);
		}
	}
	cat ans = 0;
	for(int i = 0; i <= N; i++) {
		sort(begin(V[0][i]), end(V[0][i]));
		sort(begin(V[1][i]), end(V[1][i]));
		int a = 0;
		for(int j = 0; j < (int)V[0][i].size(); j++) if(j == 0 || V[0][i][j] != V[0][i][j-1]) {
			int b = j;
			while(b < (int)V[0][i].size() && V[0][i][b] == V[0][i][j]) b++;
			while(a < (int)V[1][i].size() && V[1][i][a] < V[0][i][j]) a++;
			while(a < (int)V[1][i].size() && V[1][i][a] == V[0][i][j]) {
				ans += b-j;
				a++;
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

// look at my code
// my code is amazing


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

typedef pair<int, int> P;

int main() {
    int N, M;
    cin >> N >> M;
    vector<P> v(N);
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v[i] = P(a, b);
    }
    sort(v.begin(), v.end());
    int i = 0;
    long long ans = 0;
    int rest = M;
    while (rest) {
        long long t = min(v[i].second, rest);
        rest -= t;
        ans += t * v[i].first;
        i++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
int a[5];
for(int i=0;i<5;i++){
scanf("%d",&a[i]);
}
sort(a,a+5);
printf("%d %d %d %d %d\n",a[4],a[3],a[2],a[1],a[0]);
return 0;
}

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

set <tuple <string, int, int>> S;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		string s;
		int p;
		cin >> s >> p;
		S.insert(make_tuple(s, -1 * p, i + 1));
	}
	for (auto s: S){
		cout << get<2>(s) << '\n';
	}
}

Measured memory_bytes: 256
//http://s8pc-4.contest.atcoder.jp/tasks/s8pc_4_d
#include <bits/stdc++.h>

using namespace std;

const int maxn = 150010;

int n,deg[maxn];
double F[maxn],G[maxn];
vector<int> adj[maxn];

void visit(int u,int pa) {
    int son = deg[u];
    if (pa!=-1) son--;
    for (int j=0;j<adj[u].size();j++) {
        int v=adj[u][j];
        if (v!=pa) {
            visit(v,u);
            F[u] = F[u] + 1.0*(F[v]+1)/son;
        }
    }
}

void visit2(int u,int pa) {
    int p = deg[u];
    for (int j=0;j<adj[u].size();j++) {
        int v=adj[u][j];
        if (v!=pa) {
            if (pa==-1) {
                if (p==1) G[v]=1;
                else G[v] = ((F[u]+1)*p - (F[v]+2))/(p-1);
            }
            else G[v] = (G[u]+1)/(p-1) + (F[u]+1) - (F[v]+2)/(p-1);
            visit2(v,u);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
   // freopen("in.txt","r",stdin);
    cin>>n;
    for (int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++; deg[v]++;
    }
    visit(1,-1);
    visit2(1,-1);
    printf("%.8f\n", F[1]);
    for (int i=2;i<=n;i++) printf("%.8f\n",(F[i]*(deg[i]-1) + G[i])*1.0 / deg[i]);
}


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

const int N=1e3+5;
typedef long long ll;

int main()
{
    int n,ans,a;
    cin >> n;
    ans=0;
    for(int i=0;i<n;i++) cin >> a ,ans+=a-1;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
//#pragma comment(linker, "/STACK:1024000000,1024000000")
/* vim: set fdm=marker */
//{{{
#define __ return
int ATTENTION() {
	/* pls IGNORE this function and go down and HACK me
	 * read this AFTER contest
	 * this function is empty and it will not be called !
	 */

	http://codeforces.com/group/Pmz2A2x7ES
	/* I created a group there.
	 * I hope with the group, people can finish
	 * past contests, which is important for 
	 * increasing rating.
	 * I am still getting familiar with this function.
	 */
	 __ 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int iinf = 0x7fffffff;
const ll linf = ~(1LL<<63);
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef map<ll, int> mli;
typedef map<ll, ll> mll;
template<typename T>
inline T gcd(T a, T b) {
	if(a < 0) return gcd(-a, b);
	if(b < 0) return gcd( a,-b);
	if(a < b) return gcd(b, a);
	if(b == 0) return a;
	return gcd(b, a%b);
}

ll qpow(ll a, ll n, ll mod) {
	a %= mod;
	ll ans = 1LL;
	while(n) {
		if(n & 1) ans = (ans*a % mod);
		a = (a*a % mod);
		n >>= 1;
	}
	return ans;
}

inline ll rev(ll a, ll p) {
	return qpow(a, p - 2, p);
}

#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define rep(x, st, en) for(int x = st; x < en; x++)
#define rer(x, st, en) for(int x = st; x >= en; x--)
#define pb push_back
#define mp make_pair
#define dbgm(msg, var) cerr<<#msg<<" "<<#var<<" = "<<var<<endl; 
#define dbg(var) cerr<<#var<<" = "<<var<<endl;
#define X first
#define Y second
// build prefix sum
template<typename T>
inline void BPS(T* DST, T* SRC, int N, int s = 0) {
	DST[s] = SRC[s];
	rep(i, 1, N) DST[s + i] = DST[s + i - 1] + SRC[s + i];
}
inline int in() { int x; cin>>x; return x; }
#ifdef ALNDBG
namespace alndbg {
	clock_t s, e;
}
#endif

inline void tic() {
#ifdef ALNDBG
	alndbg::s = clock();
#endif
}

inline void toc() {
#ifdef ALNDBG
	alndbg::e = clock();
	cerr<<1000.0 * (alndbg::e - alndbg::s) / CLOCKS_PER_SEC<<" ms"<<endl;
#endif
}



//}}}

// -------------------- Spliters ------------------------
// BFS求最短路小心vis可能访问过
const int maxn = 1000;

int main() {
	ios::sync_with_stdio(0);
  int a,b,c,d;cin>>a>>b>>c>>d;
  int l=a+b,r=c+d;
  if(l>r) cout<<"Left"<<endl;
  else if(l ==r) cout<<"Balanced"<<endl;
  else cout<<"Right"<<endl;
	return 0;
}
// --USE C++11
// *-USE O2


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int main(){
  int n;
  cin >> n;
  for(int i=0;i<50000;i++){
    if(floor(i*1.08) == n){
      cout << i << "\n";
      return 0;
    }
  }
  cout << ":(" << "\n";
  return 0;
}

Measured memory_bytes: 256
def solve():
    MOD = 10**9 + 7

    S = int(input())

    N = S//3

    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(3, S+1):
            dp[i][j] = (dp[i][j-1] + dp[i-1][j-3]) % MOD

    ans = sum([dp[i][S] for i in range(N+1)]) % MOD
    print(ans)


solve()


Measured memory_bytes: 40236
#include<iostream>
#include<vector>

using namespace std;

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

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

using namespace std;

int N,M;
long long ans=0;
priority_queue<int>q;

int main(){
  cin >> N >> M;
  for(int i=0;i<N;i++){
    int x;
    cin >> x; 
    q.push(x);
  }
  for(;M--;q.pop()) q.push(q.top()/2);
  for(;N--;q.pop()) ans += q.top();
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 892
#include<iostream>
#include<sstream>
#include<vector>

using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}

bool fizz(string s,int n)
{
  if(n%15==0)
    {
      if(s=="FizzBuzz")
	return true;
      else
	return false;
    }
  if(n%3==0)
    {
      if(s=="Fizz")
	return true;
      else
	return false;
    }
  if(n%5==0)
    {
      if(s=="Buzz")
	return true;
      else
	return false;
    }
  if(n==toInt(s))
    return true;
  return false;
}

int main()
{
  int m,n;
  for(;cin>>m>>n,m;)
    {
      vector<int> p;
      p.clear();
      for(int i=1;i<=m;i++)
	p.push_back(i);
      int pp=0;
      for(int i=1;i<=n;i++)
	{
	  string s;
	  cin>>s;
	  if(p.size()==1)
	    continue;
	  if(!fizz(s,i))
	    {
	      //     cout<<p[pp]<<" "<<i<<endl;
	      p.erase(p.begin()+pp);
	    }
	  else 
	    pp++;

	  if(p.size()<=pp)
	    pp=0;
	  
	}

      for(int i=0;i<p.size();i++)
	{
	  cout<<p[i];
	  if(i==p.size()-1)
	    cout<<endl;
	  else
	    cout<<" ";
	}
    }

}

Measured memory_bytes: 1264
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); ++ i)
#define rrp(i,a,b) for (int i = (a); i >= (b); -- i)
#define gc() getchar()
#define fir first
#define sec second
typedef pair<int,int> pii;
typedef double db;
typedef long long ll;
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc(); !isdigit(tmp); tmp = gc())
    key = (tmp == '-');
  for (; isdigit(tmp); tmp = gc()) 
    x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
template <typename tp>
inline void ckmn(tp& x,tp y) {
  x = x < y ? x : y;
}
template <typename tp>
inline void ckmx(tp& x,tp y) {
  x = x < y ? y : x;
}

const int MOD = (int)(1e9 + 7);
inline void Add(int& x,int y) {
  x = x + y >= MOD ? x + y - MOD : x + y;
}
inline void Sub(int& x,int y) {
  x = x - y < 0 ? x - y + MOD : x - y;
}
int power(int a,int b) {
  int ret = 1;
  while (b) {
    if (b&1) ret = 1ll * ret * a % MOD;
    a = 1ll * a * a % MOD;
    b >>= 1;
  }
  return ret;
}

const int N = 100010;
int n, dp[N], val[N], lim = -1, cur[3], rec[N][2];
vector<int> vec[3];
char str[N];
int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  int key = 0;
  rep (i, 1, n-1) if (str[i] == str[i+1])
    key = 1;
  if (!key) {
    puts("1");
    return 0;
  }
  dp[0] = 1;
  vec[0].push_back(0);
  cur[0] = cur[1] = cur[2] = -1;
  rep (i, 1, n) {
    if (i >= 2 && str[i] == str[i-1]) lim = i-2;
    rep (j, 0, 2) {
      while (cur[j]+1 < (int)vec[j].size() && vec[j][cur[j]+1] <= lim)
	++ cur[j];
    }
    val[i] = (val[i-1] + (str[i] - 'a' + 1)) % 3;
    // Add(dp[i], dp[i-1]);
    rec[i+1][0] = i;
    int tmp = str[i] - 'a' + 1;
    if (tmp == 1) tmp = 2;
    else tmp = 1;
    tmp = val[i] - tmp;
    if (tmp < 0) tmp += 3;
    if (cur[tmp] >= 0 && vec[tmp][cur[tmp]] <= lim) {
      // Add(dp[i], dp[vec[tmp][cur[tmp]]]);
      rec[i+1][1] = vec[tmp][cur[tmp]]+1;
    }
    vec[val[i]].push_back(i);
    // cerr << dp[i] << endl;
    // cerr << rec[i+1][0] << ' ' << rec[i+1][1] << endl;
  }
  dp[n+1] = 1;
  rrp (i, n+1, 2) {
    Add(dp[rec[i][0]], dp[i]);
    Add(dp[rec[i][1]], dp[i]);
  }
  // rep (i, 1, n) {
  //   cerr << dp[i] << endl;
  // }
  int ans = 0;
  rep (i, 0, n-1)
    if (val[i] == 0) Add(ans, dp[i+1]);
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 2556
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
#pragma GCC optimize ("Ofast")
#define ll long long
#define pll pair<long long,long long>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define forn(i, n) for(int i=0; i<int(n); i++)
#define Forn(i, n) for(int i=1; i<=int(n); i++)

using namespace std;

/*#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;*/

int main()
{
    cin.tie(0);ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    int ans = 0;
    for(int i=0; i+1<=s.size()/2; i++) if(s[i]!=s[s.size()-i-1]) ans++;
    cout << ans << endl;
}


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

a = [input() for w in range(N)]
b = [input() for w in range(M)]

message = "No"

for i in range(N + M - 1):
    for j in range(N + M - 1):
        s = [t[j:j+M] for t in a[i:i+M]]
        if s == b:
            message = "Yes"
            break

print(message)

Measured memory_bytes: 3060
from math import sqrt
def calc(x, h):
    return max(h+r-sqrt(r**2 - x**2), 0)
while 1:
    r, n = map(int, raw_input().split())
    if r == 0:
        break
    H = [0]*41
    for i in xrange(n):
        xl, xr, h = map(int, raw_input().split())
        for j in xrange(xl, xr):
            H[j] = max(H[j], h)
    ans = 10**9
    for i in xrange(-r, r):
        ans = min(ans, calc(i, H[i]), calc(i+1, H[i]))
    print "%.6f" % ans

Measured memory_bytes: 6416
#include <iostream>
#include <map>

using namespace std;

int main()
{
    int n, m;
    map<string, int> blue, red;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        blue[s]++;
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        red[s]++;
    }

    int result = 0;
    for (const auto p : blue) {
        result = max(result, p.second - red[p.first]);
    }

    cout << result << endl;

    return 0;
}

Measured memory_bytes: 256
N,X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
mod = 10**9+7

dp = [[x]+[0]*N for x in range(X+1)]
for x in range(X+1):
    for n in range(1,N+1):
        dp[x][n] = (dp[x%S[n-1]][n-1] + (n-1)*dp[x][n-1])%mod

print(dp[X][N])

Measured memory_bytes: 225548
from collections import defaultdict as dd
primes = dd(int)
n,p = map(int, input().split())
gcd = 1
for i in range(2,int(p**.5)+1):
  while p%i == 0:
    p //= i
    primes[i] += 1
if p > 1:
  primes[p] += 1
for fac in primes:
  gcd *= fac**(primes[fac]//n)
print(gcd)

Measured memory_bytes: 3316
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

int m,n,s,t,fl;
int x[1001],y[1001];
int g[301][301];
int g2[301][301];
int visit[301];
stack<int> rev;

int main(){


  cin >> n >> m;

  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++)g[i][j] = 0;
  }

  for(int i=1;i<=m;i++){
    cin >> x[i] >> y[i];
    g[x[i]][y[i]] = i;
    g2[x[i]][y[i]] = i;
    g2[y[i]][x[i]] = i;
  }

  cin >> s >> t;
  fl = 0;
  while(1){
    /*
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++)cout << g2[i][j] << " ";
      cout << endl;
    }
    */
    for(int i=1;i<=n;i++)visit[i] = 0;
    queue<int> q;
    q.push(s);
    int tmp = 0;
    visit[s] = s;
    while(q.size()){
      tmp = q.front();
      q.pop();
      if(tmp == t)break;
      for(int i=1;i<=n;i++){
	if(g2[tmp][i] && !visit[i]){
	  q.push(i);
	  visit[i] = tmp;
	}
      }
    }
    
    if(tmp == t){
      fl++;
      while(tmp!=s){
	if(!g[visit[tmp]][tmp])rev.push(g2[visit[tmp]][tmp]);
	g2[visit[tmp]][tmp] = 0;
	g2[tmp][visit[tmp]] = 0;
	tmp = visit[tmp];
      }
    }else break;
  }

  cout << fl << endl;
  cout << (int)rev.size() << endl;
  while(rev.size()){
    cout << rev.top() << endl;
    rev.pop();
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>*/
 
#define pb push_back
#define mp make_pair
#define sz(s) ((int)(s.size()))
#define all(s) s.begin(), s.end()
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, n, a) for (int i = n; i >= a; --i)
#define onlycin ios_base::sync_with_stdio(false); cin.tie(0) 
#define F first
#define S second
using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
/*typedef tree<
pair < int, int >,
null_type,
less< pair < int, int > >,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
// find_by_order() order_of_key()
const int MAXN = (int)5e5+228;
const char nxtl = '\n';
const int mod = (int)1e9+7;
const double eps = (double)1e-7;
template<typename T> inline bool updmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<typename T> inline bool updmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

int n;

int main() {
	#ifdef accepted
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif
	onlycin;
	cin >> n;
	if(n == 3) {
		cout << "2 3 25";
		return 0;
	} else if(n == 4) {
		cout << "2 5 20 63";
		return 0;
	} else if(n == 5) {
		cout << "2 5 20 30 63";
		return 0;
	}
	int sum = 0, lk = -1;
	set < int > s;
	rep(k, 0, MAXN) {
		vector < int > cur = {0, 2, 3, 4};
		lk = k;
		for(auto &to : cur) {
			int num = 6*k+to;
			if(num < 1) continue;
			s.insert(num);
			sum += num;
			if(sz(s) == n) break;
		}
		if(sz(s) == n) break;
	}
	lk++;
	if(sum % 6 == 2) {
		s.erase(8); s.insert(lk*6);
	} else if(sum % 6 == 3) {
		s.erase(9); s.insert(lk*6);
	} else if(sum % 6 == 5) {
		lk--;
		if(*s.rbegin() >= lk*6+3) lk++;
		s.erase(8); s.insert(lk*6+3);
	}
	for(auto &to : s) cout << to << ' ';
	cout << nxtl;
	
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, M;
vector<ll> a;
ll sums[100001];
ll sum;

bool ok(ll x) {
  ll res = 0;
  sum = 0;
  for (ll i = 0; i < N; i++) {
    ll lb = -1; ll ub = N;
    while (ub-lb > 1) {
      ll mid = (ub+lb)/2;
      (a[mid] >= x-a[i]? ub:lb) = mid;
    }
    res += (N-ub);
    sum += (sums[N]-sums[ub]+(N-ub)*a[i]);
  }
  sum -= (res - M)*x;
  return (res >= M);
}

int main() {
  cin >> N >> M; 
  for (ll i = 0; i < N; i++) {
    ll x; cin >> x; a.push_back(x);
  }
  sort(a.begin(), a.end());
  sums[0] = 0;
  for (ll i = 1; i <= N; i++) {
    sums[i] = sums[i-1]+a[i-1];
  }
  ll lb = -1; ll ub = 1e16;
  while (ub - lb > 1) {
    ll mid = (ub+lb)/2;
    (ok(mid)? lb:ub) = mid;
  }
  ok(lb);
  cout << sum << endl;
}

Measured memory_bytes: 1908
// フェルマーの小定理
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	m = 1000000007
)

func mpow(x, y int) int {
	result := 1
	for y != 0 {
		if y&1 == 1 {
			result *= x
			result %= m
		}
		x *= x
		x %= m
		y >>= 1
	}
	return result
}

var (
	fac []int
)

func mcomb(n, k int) int {
	if n == 0 && k == 0 {
		return 1
	}
	if n < k || k < 0 {
		return 0
	}
	return (fac[n] * mpow(fac[n-k], m-2) % m) * mpow(fac[k], m-2) % m
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	X := readInt()
	Y := readInt()

	if (X+Y)%3 != 0 {
		fmt.Println(0)
		return
	}

	a := (2*Y - X) / 3
	b := (2*X - Y) / 3

	if a < 0 || b < 0 {
		fmt.Println(0)
		return
	}

	n := a + b
	k := min(a, b)

	fac = make([]int, n+1)
	fac[0] = 1
	for i := 0; i < n; i++ {
		fac[i+1] = fac[i] * (i + 1) % m
	}

	fmt.Println(mcomb(n, k))
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}


Measured memory_bytes: 7240