akhauriyash/Code-Regression huggingface dataset:
def comb(n, m)
  res = 1
  cnt = 0
  while cnt < m
    res *= n
    n -= 1
    cnt += 1
  end
  while m > 0
    res /= m
    m -= 1
  end
  res
end

require 'prime'
MOD = 1000000007
N, M = gets.split.map(&:to_i)

memo = Hash.new(0)
Prime.prime_division(M).each do |k, v|
  memo[k] += v
end

counter = 1
memo.each do |k, v|
  counter *= comb(v + N - 1, v)
end
p counter % MOD

Measured memory_bytes: 3964
//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

int main(int argc, char const* argv[])
{
	string s;
	cin >> s;
	bool ac = true;
	if (s[0] != 'A') {
		ac = false;
	}
	dump(int('a'));
	dump(int('A'));
	dump(int('Z'));
	int count_C = 0;
	for (int i = 2; i < s.size() - 1; i++) {
		if (s[i] == 'C') {
			count_C++;
		}
		else if (s[i] <= 'Z') {
			ac = false;
		}
	}
	if (s[1] <= 'Z' or s[s.size()-1] <= 'Z') {
		ac = false;
	}
	if (count_C != 1) {
		ac = false;
	}

	if (ac) {
		cout << "AC" << endl;
	}
	else {
		cout << "WA" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    a,b = mi()
    print(max(a*b,a-b,a+b))



if __name__ == "__main__":
    main()

Measured memory_bytes: 61872
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define LL long long
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define fast_io ios::sync_with_stdio(false)

const int maxn = 2e5 + 7;

char s[maxn];
LL vis[maxn];
deque<char>dq;

LL qpow(LL a,LL b, LL p) {
    LL res = 1;
    while(b) {
        if(b & 1LL) res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1LL;
    }
    return res;
}

int main() {
    int n,p;
    while(~scanf("%d%d",&n,&p)) {
        scanf("%s",s);
        LL ans = 0;
        if(p == 2 || p == 5) {
            for(int i = 0 ; i < n ; i++) {
                if((s[i] - '0') % p == 0) ans += 1LL * (i + 1);
            }
        } else {
            LL sum = 0;
            memset(vis,0,sizeof(vis));
            vis[0] = 1;
            for(int i = 0 ; i < n ; i++) {
                sum = (sum * 10 + (s[i] - '0')) % p;
                LL val = (qpow(10,n-i-1,p) * sum) % p;;
//                cout << "sum = " << sum << " val = " << val << endl;
                vis[val]++;
            }
            for(int i = 0 ; i < p ; i++) {
                ans += (vis[i] * (vis[i] - 1)) / 2;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,M;
  cin >> N >> M;
  vector<int>L(M);
  vector<int>R(M);
  for(int i=0;i<M;i++){
    cin >> L[i];
    cin >> R[i];
  }
  sort(L.begin(),L.end());
  sort(R.begin(),R.end());
  if(N-L[M-1]-(N-R[0])<0){
    cout << 0 << endl;
  }
  else{
    cout << R[0]-L[M-1]+1 << endl;
  }
  
}
      


Measured memory_bytes: 1024
#define _DEBUG
#include "bits/stdc++.h"
#include <atcoder/all>
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(index,num) for(int index=0;index<(int)num;index++)
#define rep1(index,num) for(int index=1;index<=(int)num;index++)
#define brep(index,num) for(int index=(int)num-1;index>=0;index--)
#define brep1(index,num) for(int index=(int)num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace atcoder;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=(ll)1e+18+1;
int INF=1e+9+1;
int main(){
	int N,M;
	char S[102][102]={};
	scan(N>>M);
	rep(i,N){
		scan(S[i]);
	}
	mf_graph<int> graph(N*M+2);
	rep(i,N){
		rep(j,M){
			if(S[i][j]=='.'){
				if((i+j)%2==0){
					graph.add_edge(N*M,i*M+j,1);
				}
				else{
					graph.add_edge(i*M+j,N*M+1,1);
				}
			}
		}
	}
	rep(i,N){
		rep(j,M){
			if((i+j)%2==0){
				if(S[i][j]=='.'&&S[i][j+1]=='.'){
					graph.add_edge(i*M+j,i*M+j+1,1);
				}
				if(S[i][j]=='.'&&S[i+1][j]=='.'){
					graph.add_edge(i*M+j,(i+1)*M+j,1);
				}
			}
			else{
				if(S[i][j]=='.'&&S[i][j+1]=='.'){
					graph.add_edge(i*M+j+1,i*M+j,1);
				}
				if(S[i][j]=='.'&&S[i+1][j]=='.'){
					graph.add_edge((i+1)*M+j,i*M+j,1);
				}
			}
		}
	}
	int ans=graph.flow(N*M,N*M+1);
	for(const auto& e:graph.edges()){
		if(e.from<N*M&&e.to<N*M&&e.flow==1){
			int i=min(e.from,e.to)/M,j=min(e.from,e.to)%M;
			if(e.from/M==e.to/M){
				S[i][j]='>',S[i][j+1]='<';
			}
			else{
				S[i][j]='v',S[i+1][j]='^';
			}
		}
	}
	prin(ans);
	rep(i,N){
		prin(S[i]);
	}
	return 0;
}


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

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


Measured memory_bytes: 1164
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int A = scanner.nextInt();
        int B = scanner.nextInt();
        int C = scanner.nextInt();
        int K = scanner.nextInt();

        if (K <= A) {
            System.out.println(K);
        } else if (K <= A + B) {
            System.out.println(A);
        } else {
            System.out.println(A - (K - A - B));
        }
    }
}


Measured memory_bytes: 35780
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    long long int a,b,k;
    cin >> a >> b >> k;
    if(a >= k)
    {
        cout << a - k << " " << b << "\n";
    }
    else if((a + b) >= k)
    {
        cout << "0 " << (a + b) - k << "\n";
    }
    else
    {
        cout << "0 0\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
n = int(input())
ans_list = []
for i in range(1, n + 1):
    if i % 2 == 1:
        count = 0
        for j in range(1, i + 1):
            if i % j == 0:
                count += 1
        if count == 8:
            ans_list.append(i)
    else:
        continue
print(len(ans_list))


Measured memory_bytes: 2940
/*
	容斥原理 + 递推
	不重复地选择一些的集合
	答案要求的是每一种元素必须出现两次以上
	ans = \sum (-1)^i f[i]
	其中 f[i] 表示至少有 i 个元素不满足条件
	考虑枚举这 i 个元素, 有 C(n, i) 种方式
	这 i 个元素放在集合的个数是 O(n) 级别的 (先不考虑其他元素), 而且最后答案也跟集合个数有关
	就先设 g[i][j] 为考虑了前 i 个元素放在 j 个集合里, 且都不满足条件的方案数
	g[i][j] = g[i - 1][j - 1] + g[i - 1][j] * (j + 1)
	前一个表示这个元素就放在第 j 个集合里
	后一个表示这个元素可以放在 j 个集合里, 也可以不放 
*/
#include <bits/stdc++.h>
#define N 3005

using namespace std;

const int bl = 32761;

int n, mod;
int comb[N][N], g[N][N];

int pw[2][2][bl + 1];

void init(int a[2][bl + 1], int x, const int mo) {
	a[0][0] = 1;
	for(int i = 1; i <= bl; ++i)
		a[0][i] = 1LL * x * a[0][i - 1] % mo;
	a[1][0] = 1;
	for(int i = 1; i <= bl; ++i)
		a[1][i] = 1LL * a[0][bl] * a[1][i - 1] % mo;
}
inline int fpm(int typ, int y) {
	return 1LL * pw[typ][1][y / bl] * pw[typ][0][y % bl] % mod;
}

int main() {
	scanf("%d %d", &n, &mod);
	
	init(pw[0], 2, mod);
	init(pw[1], 2, mod - 1);
	
	for(int i = 0; i <= n; ++i) {
		comb[i][0] = 1;
		for(int j = 1; j <= i; ++j)
			comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod;
	}
	for(int i = 0; i <= n; ++i) {
		g[i][0] = 1;
		for(int j = 1; j <= i; ++j)
			g[i][j] = (g[i - 1][j - 1] +
			(j + 1LL) * g[i - 1][j]) % mod;
	}
	
	int ans = 0;
	for(int i = 0; i <= n; ++i) {
		int res = 0;
		for(int j = 0; j <= i; ++j) {
			res = (res + 1LL * comb[n][i] * g[i][j] % mod
				   * fpm(0, (n - i) * j) % mod
				   * fpm(0, fpm(1, n - i))) % mod;
		}
		if(i & 1) {
			ans = (ans + mod - res) % mod;
		} else {
			ans = (ans + res) % mod;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 70272
#!/usr/bin/env python3

from collections import Counter


def solve(N: int, A: "List[int]", Q: int, BC: "List[(int,int)]"):
    A = Counter(A)
    answers = []
    ans = ans = sum((i * n for i, n in A.items()))
    for b, c in BC:
        if b != c:
            ans += (c - b) * A[b]
            A[c] += A[b]
            del A[b]
        answers.append(ans)
    return answers


def main():
    N = int(input())  # type: int
    A = list(map(int, input().split()))
    Q = int(input())
    BC = [tuple(map(int, input().split())) for _ in range(Q)]
    answer = solve(N, A, Q, BC)
    for ans in answer:
        print(ans)


if __name__ == "__main__":
    main()


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

path = [[] for _ in range(N)]
for _ in range(M):
    x, y, _ = map(int, input().split())
    path[x-1].append(y-1)
    path[y-1].append(x-1)

seen = [False] * (N+1)

last_start = -1
counter = 0
while True:
    start = last_start + 1
    while seen[start]:
        start += 1

    if start == N:
        break

    if path[start]:
        stack = [start]
        while stack:
            pos = stack.pop()
            seen[pos] = True
            for next_node in path[pos]:
                if not seen[next_node]:
                    stack.append(next_node)
    else:
        seen[start] = True

    counter += 1
    last_start = start

print(counter)

Measured memory_bytes: 70432
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FOR(i,l,r) for(i=l;i<r;i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define P pair<ll,ll>
#define F first
#define S second
ll mod=1000000007;
ll G(ll N){
  ll j=N,res=1,n=mod-2;
  while(n>0){
    if(n&1)res=res*j%mod;
    j=j*j%mod;
    n>>=1;
  } 
  return res;
}
ll K(ll N){
  ll i,res=1;
  REP(i,N){res*=i+1;res%=mod;}
  return res;
}
ll H(ll N,ll M){
  return K(N+M-1)*G(K(N)*K(M-1)%mod)%mod;
}
signed main(){
  ll N,i,ans=0;cin>>N;
  REP(i,N/3){
    ans+=H(N-3*(i+1),i+1);
    ans%=mod;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3616
#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> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> p(n),c(n);
    rep(i,n) cin >> p[i],--p[i];
    rep(i,n) cin >> c[i];
    ll ans = -LINF;
    rep(i,n){
        int now = i;
        vector<ll> scores;
        ll now_score = 0;
        while(1){
            scores.push_back(now_score);
            now = p[now];
            now_score += c[now];

            if(now == i) break;
        }
        ll cyc_score = now_score ;
        ll cyc = scores.size();

        ll res = -LINF;
        for(int j=1;j<min(k+1,(int)(scores.size()));++j) res = max(res,scores[j]);
        ans = max(ans,res);
        if(cyc_score < 0 || k+1 < (int)(scores.size())) continue;
        for(int j=0;j<(int)(scores.size());++j) res = max(res,cyc_score*((k-j)/cyc) + scores[j]);
        ans = max(ans,res);
    }
    cout << ans << endl;
    return 0;
}

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

#define ll long long
#define mod 1000000007
#define ffor(i,a,b) for(int i=a;i<b;i++)
#define bfor(i,a,b) for(int i=a-1;i>=b;i--)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define mem(x,y) memset(x,y,sizeof(x))
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sz(x) (int)x.size()
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define PI 3.14159265358979323846
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define endl '\n'

int main()
{
   

    int n,m;
    cin>>n>>m;
    cout<<(n)*(n-1)/2 + (m)*(m-1)/2;
    
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main(int argc, char const *argv[]) {
  string s1, s2, s3, ans;
  cin >> s1 >> s2 >> s3;
  ans = s1[0];
  ans += s2[0];
  ans += s3[0];
  transform(ans.begin(),ans.end(),ans.begin(),::toupper);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstring>
#include <cmath>
#include <cstdio>
 
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()

using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> P;

const int INF = 1<<29;

int main(){
	int n, m;
	cin >> n >> m;

	int l, h, cur;
	l = h = cur = m;

	rep(i, n){
		int in, out;
		cin >> in >> out;
		cur += in - out;
		l = min(l, cur);
		h = max(h, cur);
	}

	if(l < 0) cout << 0 << endl;
	else cout << h << endl;


    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false), cin.tie(0)
typedef long long ll;

int main()
{
    string s, t;
    cin >> s >> t;
    int a, b;
    cin >> a >> b;
    string u;
    cin >> u;
    if (u == s)
        a--;
    else if (u == t)
        b--;
    cout << a << " " << b << endl;
}

Measured memory_bytes: 256
x, y = map(int, input().split())

# kame = x - turu
# 2*turu + 4*kame = y
# 2*turu + 4*(x - turu) = y
#  -2*turu + 4x - y = 0
# turu = 2x - 1/2*y

turu = 2*x - 1/2*y
if(turu.is_integer() and turu >= 0 and (x-turu) >= 0):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 61772
N = int(input())
A = [0]*N
B = [0]*N
for i in range (N):
    A[i],B[i] = map(int, input().split())
ctr = 0
for i in range (N-1, -1, -1):
    k = (A[i] + ctr) % B[i]
    if k != 0:
        ctr += B[i] - k
print(ctr)

Measured memory_bytes: 16628
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int N = sc.nextInt();

		sc.close();

		for (int i = 1; i <= 9; i++) {
			if (N % i == 0 && N / i <= 9) {
				out.println("Yes");
				return;
			}
		}
		out.println("No");

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}


Measured memory_bytes: 23636
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");

        int[] cnt = new int[3];
        for (int i = 0; i < n; i++) {
            long num = Long.parseLong(str[i]);
            if (num % 2 == 0) {
                if (num % 4 == 0) {
                    cnt[2]++;
                } else {
                    cnt[1]++;
                }
            } else {
                cnt[0]++;
            }
        }

        if (cnt[1] > 0) {
            cnt[0]++;
        }

        if (cnt[0] <= cnt[2] + 1) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 37716
N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for _ in range(Q)]
l = [lr[i][0] for i in range(Q)]
r = [lr[i][1] for i in range(Q)]
#print(lr)
#print(l)
#print(r)

c = [0] * N
cnt = 0

for i in range(N-1):
    if S[i:i+2] == 'AC':
        c[i+1]=c[i]+1
    else:
        c[i+1]=c[i]
    #c[i] = S[:i].count('AC')

#print(c)

for i,j in zip(l,r):
    #print(sum(c[:j])-sum(c[:i]))
    #l,r = map(int,input().split())
    print(c[j-1]-c[i-1])

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

#define pb(n) push_back(n)
#define fi first
#define se second
#define X real()
#define Y imag()
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using comd = complex<double>;
using pii = pair<int,int> ;

constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

double CalcDist(comd p1, comd p2){
  return sqrt(pow(p1.X - p2.X,2.0) + pow(p1.Y -p2.Y,2.0));
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(all(v),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  double x = 0,y = 0,a,b;
  char c;
  int angle = 90;
  while(cin >>a >> c >> b){
    if(a == 0 && b == 0) break;
    x += cos(angle * PI/180) * a;
    y += sin(angle * PI/180) * a;
    angle -= b;
    angle %= 360;
  }
  cout << (int)x << endl;
  cout << (int)y << endl;
  return 0;
}

Measured memory_bytes: 3464
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

//割られる数：a
//余りを求めるやつ：valid
long long Modinv(long long a, long long valid = INV)
{
	long long b = valid, u = 1, v = 0;
	while (a)
	{
		if (a < b)
		{
			swap(a, b);
			swap(u, v);
		}
		long long t = a / b;
		a -= t * b;
		u -= t * v;
	}
	v %= valid;
	if (v < 0)
		v += valid;
	return v;
}

void execute()
{
	int N, Cmin, Cmax;
	int r, n;
	lint sum = 0;
	double ave = 0;
	lint C = 1;
	lint ans = 0;

	cin >> N >> Cmin >> Cmax;

	vector<lint> data(N);
	for (int i = 0; i < N; i++)
	{
		lint tmp;
		cin >> tmp;
		data[i] = tmp;
	}

	sort(all(data), greater<lint>());

	lint last = data[0];
	r = 0;
	n = 0;
	for (int i = 0; i < Cmin; i++)
	{
		if (last == data[i])
			r++;
		else
			r = 1;
		last = data[i];
		sum += data[i];
	}

	ave = (double)(sum) / Cmin;

	cout << ave << endl;
	for (int i = 0; i < N; i++)
	{
		if (last == data[i])
			n++;
	}
	for (int i = 0; i < n; i++)
	{
		C *= (n - i);
		//C % INV;
		C /= (i + 1);
		//C *= Modinv(i + 1);
		//C % INV;

		if (r == Cmin)
		{
			if (r <= i + 1 && i + 1 <= r + Cmax - Cmin)
			{
				ans += C;
			}
		}
		else
		{
			if (i + 1 == r)
			{
				cout << C << endl;
				return;
			}
		}
	}

	cout << ans << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define Endl endl
typedef long long ll;
const int MAXN = (int)1e5 + 5;
ll n, a[MAXN], ans[MAXN];
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	while (cin >> n)
	{
		ll sum = 0;
		for (int i = 0; i < n&&cin >> a[i]; ++i)
			sum += a[i], a[i] *= 2;
		ll t = (sum - sum%n) / n;
		for (int i = 0; i < n; ++i)
			ans[i] = t;
		for (int i = 0; i < sum%n; ++i)
			ans[i]++;
		ans[1] += ans[0];
		ans[0] = 0;
		while (1)
		{
			bool flag = true;
			for (int i = 0; i < n; ++i)
			{
				ll t = ans[i] + ans[(i + 1) % n];
				if (t > a[i])
					ans[(i + 1) % n] -= t - a[i], ans[(i + 2) % n] += t - a[i], flag = false;
			}
			if (flag)
				break;
		}
		for (int i = 0; i < n; ++i)
			cout << ans[i] << ' ';
		cout << endl;
	}
}
/*
3
2 2 4

5
3 8 7 5 5

3
1000000000 1000000000 0
*/

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

using namespace std;

using ll = long long;

int main(){
    ll n, m;
    cin >> n >> m;
    ll arr[m];
    for(ll i = 0; i < m; ++i){
        cin >> arr[i];
    }
    sort(arr, arr + m);
    vector<ll> v;
    for(ll i = 0; i < m - 1; ++i){
        v.push_back(abs(arr[i] - arr[i + 1]));
    }
    sort(v.begin(), v.end());
    ll ans = 0;
    for(ll i = 0; i <= m - n - 1; ++i){
        ans += v[i];
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 2168
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

N, R = map(int, input().split())
if N >= 10:
    print(R)
else:
    print(R + 100 * (10 - N))



Measured memory_bytes: 8260
implicit none
integer k,x,i
logical :: flg
read *,k,x
flg = .false.
do i = x-k+1,x+k-1
   if (flg) then
      write(6,'(a)',advance='no') ' '
   endif
   write(6,'(i0)',advance='no') i
   flg = .true.
enddo
write(6,'(a)') ''
end

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

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield max(p+abs(j-i)*a, s+abs(j+r)*a)
    p = s
  yield s+abs(len(prev)-i)*a

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*solve(a,i, pd)]

print(max(pd))


Measured memory_bytes: 9584
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct node{
  struct node *next['z'-'a'+1];
}node;

node *_N;
int _count;

node *allocNode(){
  return &_N[_count++];
}

#define MAX (72*(72*6)+2)
void init(){
  _N=(node *)calloc(sizeof(node),MAX);
  _count=0;
}
void reinit(){
  memset(_N,0,sizeof(node)*_count);
  _count=0;
}

node *get(node *s,const char *p){
  while(*p!='\0'){
    if(s==NULL) return NULL;
    s=s->next[*(p++)-'a'];
  }
  return s;
}

int set(node *s,const char *p){
  int ret=0;
  while(*p!='\0'){
    if(s->next[*p-'a']==NULL){
      s->next[*p-'a']=allocNode();
      ret=1;
    }
    s=s->next[*(p++)-'a'];
  }
  return ret;  
}

void makestr(char *dist,char *s1,char *s2){
  strcpy(dist,s1);
  strcat(dist,s2);
}

int main(){
  int n;
  init();
  scanf("%d ",&n);
  while(n-->0){
    char buff[101];
    char buff2[101];
    node *s=allocNode();
    int len,i,ans=0;
    char f[100],*b,*fr,br[100];

    fgets(buff,sizeof(buff),stdin);
    for(i=0; buff[i]; i++) if(buff[i]=='\n'){buff[i]='\0'; break;}
    len = strlen(buff);
    for(i=0;i<len;i++){
      buff2[i]=buff[len-1-i];
      br[i]=buff[len-1-i];
    }
    buff2[len]='\0';
    b=buff;
    fr=&buff2[len];

    ans+=set(s,buff);
    ans+=set(s,buff2);

    for(i=1;i<len;i++){
      char str[100];
      f[i-1]=buff[i-1];f[i]='\0';
      br[len-1-(i-1)]='\0';
      fr--;b++;
      //printf("%s(%s) + %s(%s)\n",f,fr,b,br);
      makestr(str,fr,b ); ans+=set(s,str);
      makestr(str,fr,br); ans+=set(s,str);
      makestr(str,f ,br); ans+=set(s,str);
      makestr(str,b ,f ); ans+=set(s,str);
      makestr(str,br,f ); ans+=set(s,str);
      makestr(str,b ,fr); ans+=set(s,str);
    }
    
    printf("%d\n",ans);

    if(n!=0) reinit();
  }
  return 0;
}

Measured memory_bytes: 0
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int count=1;
        int ans=0;
        for(int i=0;i<n;i++){
            if(sc.nextInt()==count){
                ans++;
                count++;
            }
        }
        System.out.println(ans!=0?n-ans:-1);
        

    }



}

Measured memory_bytes: 65084
import sys
H,W = map(int,input().split())
if H < 0 or H > 100 or W < 0 or H > 100:
    sys.exit()
pixeles = []
for I in range(H):
    pixeles.append(str(input()))

print("#"*(W+2))
for L in pixeles:
    print("#",end='')
    print(L,end='')
    print("#")
print("#"*(W+2))


Measured memory_bytes: 8896
#include <cstdio>
#include <vector>
static const int MAXN = 1e5 + 4;

int n;
std::vector<int> a;

int main()
{
    scanf("%d", &n);

    int ans = 0, last = 0;
    a.push_back(0);

    for (int i = 0, x; i < n; ++i) {
        scanf("%d", &x);
        if (__builtin_popcount(x) == 1) {
            a.push_back(8 * sizeof(int) - __builtin_clz(x) - 1);
        } else {
            int tail = 8 * sizeof(int) - __builtin_clz(x);
            if (tail - 1 >= a.back()) {
                a.push_back(tail - 1);
                a.push_back(tail);
            } else {
                a.push_back(tail);
                a.push_back(tail - 1);
            }
        }
    }

    for (int x : a) {
        if (x > last) ans += x - last;
        last = x;
    }
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 1528
a,b,x = map(int,input().split())
import math

if x >= a * a * b / 2:
    h0 = x / a / a
    tanr = (b - h0) * 2 / a
else:
    h1 = 2 * x / a / b
    tanr = b / h1

print(math.degrees(math.atan(tanr)))

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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000005 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

int main(){
    ll N;
    cin>>N;
    string S;
    cin>>S;
    int ans=1;
    char c=S[0];
    rep(i,N){
        if(S[i]!=c){
            ans++;
            c=S[i];
        }
    }
   cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3720
#include <stdio.h>
int main(void) {
  int N;
  scanf("%d", &N);
  switch (N % 10) {
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      printf("hon\n");
      break;
    
    case 0:
    case 1:
    case 6:
    case 8:
      printf("pon\n");
      break;
    
    default:
      printf("bon\n");
      break;
  }
  return(0);
}


Measured memory_bytes: 1664
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}
ll mp[Max+10];

int main()
{

   fastread();

   ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,ans=0;

      bool flag=false;

      string str;


    cin>>n;

    while(n>0)
    {
         a=n%26;

         if(a)
            str+=a-1+'a';

         else str+='z';

         n/=26;

         if(a==0)n--;


    }

    reverse(vll(str));

    cout<<str<<endl;







}


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

ans,ov = 0,0

for i in range(N):
    tmp = min(A[i],ov)
    ans += tmp
    A[i] -= tmp
    if B[i]>A[i]:
        ans+=A[i]
        ov = B[i]-A[i]
    else:
        ans+=B[i]
        ov = 0
tmp = min(A[N],ov)
ans+=tmp
print(ans)
        

Measured memory_bytes: 24136
#include <stdio.h>
#include <stdlib.h>

typedef struct Bomb
{
	int map[8][8];
	int x, y;
} BOMB;

int x_cnt, y_cnt;

BOMB* explode(BOMB*);	/*Recursion*/

int main()
{
    int input_times, input_cnt;
    char dump;
    BOMB input[50];
    
    /*Read input times*/
    scanf("%d", &input_times);
    input_cnt = 0;
    while(input_cnt < input_times)
    {
		/*Read input map*/
		dump = getchar();
		for(y_cnt = 0; y_cnt < 8; y_cnt++)
		{
			dump = getchar();
			for(x_cnt = 0; x_cnt < 8; x_cnt++)
			{
				input[input_cnt].map[x_cnt][y_cnt] = getchar() - 48;
			}
		}
		/*Read first explosion*/
		scanf("%d", &(input[input_cnt].x));
		scanf("%d", &(input[input_cnt].y));
		
		/*Process*/
		input[input_cnt].map[(input[input_cnt].x) - 1][(input[input_cnt].y) - 1] = 2;
		explode(&input[input_cnt]);
		
		input_cnt++;
	}
    
    input_cnt = 0;
    while(input_cnt < input_times)
    {
    	printf("Data %d:\n", input_cnt + 1);
    	for(y_cnt = 0; y_cnt < 8; y_cnt++)
		{
			for(x_cnt = 0; x_cnt < 8; x_cnt++)
			{
				printf("%d", input[input_cnt].map[x_cnt][y_cnt]);
			}
			printf("\n");
		}
    	input_cnt++;
	}

    
    return 0;
} 

BOMB* explode(BOMB* bombmap)
{
	int explode_cnt;
	for(y_cnt = 0; y_cnt < 8; y_cnt++)
	{
		for(x_cnt = 0; x_cnt < 8; x_cnt++)
		{
			if(bombmap->map[x_cnt][y_cnt] == 2)
			{
				bombmap->map[x_cnt][y_cnt] = 0;
				
				explode_cnt = 1;
				while((x_cnt - explode_cnt) >= 0 && explode_cnt <= 3)
				{
					if((bombmap->map[x_cnt - explode_cnt][y_cnt]) == 1)
					{
						(bombmap->map[x_cnt - explode_cnt][y_cnt]) = 2;
					}
					explode_cnt++;
				}
				
				explode_cnt = 1;
				while((x_cnt + explode_cnt) <= 7 && explode_cnt <= 3)
				{
					if((bombmap->map[x_cnt + explode_cnt][y_cnt]) == 1)
					{
						(bombmap->map[x_cnt + explode_cnt][y_cnt]) = 2;
					}
					explode_cnt++;
				}
				
				explode_cnt = 1;
				while((y_cnt - explode_cnt) >= 0 && explode_cnt <= 3)
				{
					/*printf("3: x:%d y:%d e:%d\n", x_cnt, y_cnt, explode_cnt);*/
					if((bombmap->map[x_cnt][y_cnt - explode_cnt]) == 1)
					{
						(bombmap->map[x_cnt][y_cnt - explode_cnt]) = 2;
					}
					explode_cnt++;
				}
				
				explode_cnt = 1;
				while((y_cnt + explode_cnt) <= 7 && explode_cnt <= 3)
				{
					/*printf("4: x:%d y:%d e:%d\n", x_cnt, y_cnt, explode_cnt);*/
					if((bombmap->map[x_cnt][y_cnt + explode_cnt]) == 1)
					{
						(bombmap->map[x_cnt][y_cnt + explode_cnt]) = 2;
					}
					explode_cnt++;
				}
				/*printf("LOOP\n");*/
				return explode(bombmap);
			}
		}
	}
	
	return bombmap;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N, A, B, C, D; 
	cin >> N >> A >> B >> C >> D; 
	A--; B--; C--; D--; 
	string S; 
	cin >> S; 
	if(C < D){
		bool ok = true; 
		for(int i = A; i < D; i++){
			if(S[i] == '#' && S[i+1] == '#'){
				ok = false; break; 
			}
		}
		if(ok) cout << "Yes" << endl; 
		else cout << "No" << endl; 
	}
	else{
		bool ok = false; 
		for(int i = B-1; i < D; i++){
			if(S[i] == '.' && S[i+1] == '.' && S[i+2] == '.'){
				ok = true; break; 
            }
		}
		for(int i = A; i < C; i++){
			if(S[i] == '#' && S[i+1] == '#'){
				ok = false; break; 
			}
		}
		if(ok) cout << "Yes" << endl; 
		else cout << "No" << endl; 
	}
}

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

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fst first
#define scd second

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

inline int read(){
	int f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline ll readll(){
	ll f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int main() {
	int q=read();while(q--){
		int a=read(),b=read(),c=read(),d=read();
		int len=max(a,b)/(min(a,b)+1);if(max(a,b)%(min(a,b)+1)!=0)len++;
		//cout<<"maxlen="<<len<<endl;
		int l=0,r=a;
		while(l<r){
			int mid=(l+r+1)>>1;
			//cout<<"checking mid="<<mid<<endl;
			int tb=b-max(0,(mid-1)/len);assert(tb>=0);
			int ta=a-mid;
			//int tl=max(ta,tb)/(min(ta,tb)+1);if(max(ta,tb)%(min(ta,tb)+1)!=0)tl++;
			if(tb<=(ll)(ta+1)*len)l=mid;
			else r=mid-1;
		}
		int x=l+max(0,(l-1)/len);
//		int tb=b-max(0,(l-1)/len);assert(tb>=0);
//		int ta=a-l;
//		int tl=max(ta,tb)/(min(ta,tb)+1);if(max(ta,tb)%(min(ta,tb)+1)!=0)tl++;
//		assert(tl==len);
		for(int i=c;i<=d;++i){
			if(i<=x){
				if(i%(len+1))putchar('A');
				else putchar('B');
			}else{
				if((a+b-i+1)%(len+1))putchar('B');
				else putchar('A');
			}
		}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 384
arr = []
a = [0]
b = []

3.times do
  arr << gets.split(" ").map(&:to_i)
end

for i in 0..2 do
  b << arr[0][i] - a[0]
end
for i in 1..2 do
  a << arr[i][0] - b[0]
end

for i in 0..2 do
  for j in 0..2 do
    unless arr[i][j] == a[i] + b[j]
      puts "No"
      exit
    end
  end
end

puts "Yes"


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(){
	int N, C; 
	cin >> N >> C; 
	pair<int, pair<int, int>> A[100010] = {}; 
	for(int i = 1; i <= N; i++){
		cin >> A[i].second.first >> A[i].second.second >> A[i].first; 
	}
	sort(A+1, A+N+1); 
	int R[100010] = {}; 
	for(int i = 1; i <= N; i++){
		if(A[i].first == A[i-1].first && A[i].second.first == A[i-1].second.second){
			R[(A[i].second.first) + 1] ++; R[A[i].second.second + 1] --;
		}
		else{
			R[(A[i].second.first)] ++; R[A[i].second.second + 1] --;
		}
	}
	int ans = 0; 
	int acc = 0; 
	for(int i = 1; i <= 100000; i++){
		acc += R[i]; 
		ans = max(ans, acc); 
	}
	cout << ans << endl; 
}

Measured memory_bytes: 1792
#include<iostream>

using namespace std;

int main()
{
  int R;
  cin >> R;
  
  if (R < 1200)
  {
    cout << "ABC" << "\n";
  }
  else if (R >= 1200 && R < 2800)
  {
    cout << "ARC" << "\n";
  }
  else
  {
    cout << "AGC" << "\n";
  }
    
}

Measured memory_bytes: 256
//{{{
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < int(n); ++i)
#define REPE(i, a, b) for (int i = (a); i <= int(b); ++i)
using LL = long long;
typedef long long LL;
//}}}

using cd = complex<double>;
double crx(cd a, cd b) { return imag(conj(a) * b); }

int main() {
  cd a[3];
  for (int i = 0; i < 3; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    a[i] = cd(x, y);
  }
  const double x = abs(a[0] - a[1]);
  const double y = abs(a[0] - a[2]);
  const double z = abs(a[1] - a[2]);
  const double r = fabs(crx(a[0] - a[1], a[0] - a[2]) / (x + y + z));
  double ans = 0, step = 1e9;
  const double m = max(x, max(y, z));
  for (int i = 0; i < 100; ++i, step /= 2) {
    double t = ans + step;
    if ((1 - t / r) * m >= t * 2) ans = t;
  }
  printf("%.12f\n", ans);
  return 0;
}



Measured memory_bytes: 384
N = int(input())
S = input()
w = [0]*N
b = [0]*N
s = S[::-1]
for i in range(N):
    b[i] = b[i-1]
    if S[i] == '#':
        b[i] += 1
    w[i] = w[i-1]
    if s[i] == '.':
        w[i] += 1

m = min(w[N-1],b[N-1])
for i in range(N-1):
    m = min(m,b[i]+w[N-i-2])

print(m)

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

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 11451419194545;

int main(){

    ll N; cin >> N;

    for(ll i = 1; i <= 9; i++){
        if(N / i <= 9){
            if(N / i * i == N){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    

}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a<=b&&b<=c){
		printf("%d %d %d\n",a,b,c);
	}else if(a<=c&&c<=b){
		printf("%d %d %d\n",a,c,b);
	}else if(b<=c&&c<=a){
		printf("%d %d %d\n",b,c,a);
	}else if(b<=a&&a<=c){
		printf("%d %d %d\n",b,a,c);
	}else if(c<=b&&b<=a){
		printf("%d %d %d\n",c,b,a);
	}else{
		printf("%d %d %d\n",c,a,b);
	}
	return 0;
}

Measured memory_bytes: 596
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
int input(char s[]);

int main() {
	int n, r, brk = 0, p, c, x[50], xs[50];
	
	while (1) {
		for (int i = 0; i < 50; i++)
			x[i] = xs[i] = i;
		scanf("%d %d", &n, &r);
		if (n == 0 && r == 0)
			break;
		for (int i = 0; i < r&&brk == 0; i++) {
			scanf("%d %d", &p, &c);
			for (int j = 0; j < c; j++)
				x[j] = xs[j + p - 1];
			for (int j = c; j < c + p - 1; j++)
				x[j] = xs[j - c];
			for (int j = 0; j < n; j++)
				xs[j] = x[j];
			/*for (int j = n-1; j >=0; j--) {
				printf("%2d  %2d\n",j, x[j]);
			}*/
		}
		printf("%d\n", n - x[0]);
	}
	return 0;
}


Measured memory_bytes: 3144
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char a[200020],b[200020];
int n,m,cnt0,cnt1;
long long ans;
int main()
{
	scanf("%s",a+1);
	n=strlen(a+1);
	for(int i=1;i<=n;++i)
		if(a[i]=='0')++cnt0;
		else ++cnt1;
	for(int i=1;i<=cnt1;++i)ans+=(i+1)/2;
	for(int i=1;i<=n;++i)
	{
		if(a[i]=='0')b[++m]='0';
		else if(b[m]=='1')--m,ans+=cnt0;
		else b[++m]='1';
	}
	int precnt0=0;
	for(int i=1;i<=m;++i)
	{
		if(b[i]=='0')++precnt0;
		else ans+=cnt0-(i&1?precnt0/2:(precnt0+1)/2);
	}
	printf("%lld",ans);
	return 0;
}

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

int getnum() {
  char C;
  while(!isdigit(C = getchar()));
  int n = C - '0';
  while(isdigit(C = getchar())) n = n*10 + C - '0';
  return n;
}
        

int main() {
  int N = getnum();
  int K = getnum();
  map<int, int> vec;
  while(N--) {
    int A = getnum();
    vec[A]++;
  }
  vector<int> ans(0);
  int kinds = vec.size();
  for (auto itr = vec.begin(); itr != vec.end(); itr++) ans.push_back(itr->second);
  sort(ans.begin(),ans.end());
  int cnt = 0;
  if(kinds > K) for (int i = 0; i < kinds - K; i++) cnt += ans[i];
  printf("%d\n", cnt);
}

Measured memory_bytes: 10748
#include<bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;++i)
#define N 100005
using namespace std;
typedef long long ll;
int a[N],b[N],n;
ll x=0,y=0,p=0;
int main(){
	scanf("%d",&n);
	rep(i,n)scanf("%d",a+i);int xx;
	rep(i,n)scanf("%d",&xx),a[i]-=xx;
	rep(i,n)p-=a[i];
	//rep(i,n)printf("%d ",a[i]);
	rep(i,n)if(a[i]<0){
		a[i]=-a[i];
		x+=a[i]/2;
		if(a[i]&1)++x,++y;
	}else y+=a[i];
	//printf("%d %d %d\n",x,y,p);
	if(x>p||y>p)puts("No");else puts("Yes");
	return 0;
}

Measured memory_bytes: 256
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import qualified Data.ByteString.Char8 as B
import Text.Printf

readInt = ( readLn :: IO Int )
readInts = map ( read :: String -> Int ) . words <$> getLine

getList = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	s <- sort <$> getLine
	t <- reverse . sort <$> getLine
	putStrLn $ which "Yes" "No" $ s < t


Measured memory_bytes: 508
h,w = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
A = [list(map(int,input().split())) for i in range(h)]

for i in range(10):
    for j in range(10):
        for k in range(10):
            c[j][k] = min(c[j][k],c[j][i]+c[i][k])
ans = 0
for i in range(h):
    for j in A[i]:
        if j != -1:
            ans += c[j][1]
print(ans)


Measured memory_bytes: 3316
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef vector<ll> vint;
typedef vector<string> vstr;
typedef pair<ll, ll> pint;
ll inf = (1LL << 50);

//bool operator< (pint a, pint b) {
	//return a.second < b.second;

//}



ll gcd(ll a, ll b) {

	if (b == 0)
		return a;

	return gcd(b, a % b);


}

ll max(ll a, ll b) {
	if (a < b) {
		return b;
	}
	else
		return a;

}

ll min(ll a, ll b) {
	if (a < b)
		return a;

	return b;
}




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

vector<pint> list;


bool compare(pint l, pint r) {

	return l.second < r.second;
}




ll sosuu[100005];

ll ans[100005];



vector<pint> query;

int main() {
	ll Q;
	ll l, r;
	cin >> Q;

	rep(i, Q) {
		cin >> l >> r;
		query.push_back({ l, r });

	}


	sosuu[0] = -1;
	sosuu[1] = -1;
	sosuu[2] = 0;
	for (int i = 3; i <= 100005; i++) {
		for(int j = 2; j*j <= i; j++){
			if (i % j == 0) { sosuu[i] = -1; break; }
		}
	}


	ll sum = 0;

	for (int i = 2; i < 100005; i++) {

		if (sosuu[i] == 0 && sosuu[(i + 1) / 2] == 0) sum += 1;
		ans[i] = sum;	

	}


	rep(i, Q) {

		if(sosuu[query[i].first] == 0 && sosuu[(query[i].first + 1)/2] == 0)
		cout << ans[query[i].second] - ans[query[i].first] + 1 << endl;
		else
		cout << ans[query[i].second] - ans[query[i].first]<< endl;

	}


	return 0;
}

Measured memory_bytes: 3824
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}


signed main(void) {
    string s;
    cin >> s;
    int n = s.size();
    bool ans = true;
    rep(i,n/2)if(s[i] != s[n-i-1])ans = false;
    n /= 2;

    rep(i,n/2)if(s[i] != s[n-i-1])ans = false;
    rep(i,n/2)if(s[n+1+i] != s[s.size()-i-1])ans = false;

    if(ans)cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100000

int main(){
  int i,l,m,r,n,q,count,key,S[MAX],T[MAX];

  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&S[i]);

  scanf("%d",&q);
  for(i=0;i<q;i++)
    scanf("%d",&T[i]);

  count = 0;
  for(i=0;i<q;i++){
    key = T[i];
    l = 0;
    r = n;
    while(l < r){
      m = (l + r) / 2;
      if(key == S[m]){
	count++;
	break;
      }
      else if(key < S[m])r = m;
      else if(key > S[m])l = m + 1;
    }
  }

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

  return 0;
}

Measured memory_bytes: 1192
# -*- coding: utf-8 -*-
"""
Created on Wed May 13 15:42:03 2020

@author: shinba
"""

n = int(input())

W = list(map(int,input().split()))

a = sum(W)
ans = float("inf")

for i in range(1,n):
    b = sum(W[:i])
    ans = min(ans,abs(2*b-a))

print(ans)
    


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,n) for (int i = 0;i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
int INF = 1e9;

struct UnionFind{
    vector<int> d;
    UnionFind(int n):d(n,-1){}
    int find(int x){
        if(d[x]<0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x,int  y){
        x = find(x);y = find(y);
        if(x==y) return false;
        if(d[x] > d[y]) swap(x,y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x,int y) {return find(x) == find(y);}
    int size(int x) {return -d[find(x)];}
};

int main(){
    int n,m;cin >> n >> m;
    bool G[55][55];
    rep(i,55)rep(j,55) G[i][j] = false;
    vector<P> edge(m);
    rep(i,m) {
        int a,b;cin >> a >> b;
        --a;--b;
        edge[i] = make_pair(a,b);
        G[a][b] = true;
        G[b][a] = true;
    }
    queue<int> q;
    int ans = 0;
    rep(i,m){
        UnionFind tree(55);
        P p = edge[i];
        G[p.first][p.second] = false;
        G[p.second][p.first] = false;
        q.push(0);
        while(!q.empty()){
            int v = q.front();q.pop();
            //cout << v << endl;
            for(int nv = 0;nv<n;nv++){
                if(!G[v][nv]) continue;
                if(!tree.unite(v,nv)) continue;
                tree.unite(v,nv);
                q.push(nv);
            }
        }
        if(tree.size(0) != n) ans++;
        G[p.first][p.second] = true;
        G[p.second][p.first] = true;
    }
    cout << ans << endl;


}

Measured memory_bytes: 3604
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n,k=map(int,input().split())
l=n-k
for i in range(k):
    print((cmb(l+1,i+1,mod)*cmb(k-1,i,mod))%mod)

Measured memory_bytes: 4512
import sys
import collections

while True:
    N = int(raw_input())
    if N == 0:
        break
    W, H = map(int, sys.stdin.readline().split())
    area = [[0 for i in xrange(H)] for j in xrange(W)]
    for z in xrange(N):
        x, y = map(int, sys.stdin.readline().split())
        area[x - 1][y - 1] = 1
    S, T = map(int, sys.stdin.readline().split())
#    col = [[0 for i in xrange(H)] for j in xrange(W)]
#    row = [[0 for i in xrange(H)] for j in xrange(W)]
    max = -1
    for x in xrange(W - S + 1):
        for y in xrange(H - T + 1):
            sum = 0
            for s in xrange(S):
                for w in xrange(T):
                    sum += area[x + s][y + w]
            if sum > max:
                max = sum
    print max

Measured memory_bytes: 4748