akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const long long INF=1LL<<60;
const int MAXN=1000005;
char s[MAXN],stk[MAXN];
vector<pair<int,int> >a,b,c;
int n,top;
bool cmp1(const pair<int,int> &X,const pair<int,int>&Y)
{
    return X.first<Y.first;
}
bool cmp2(const pair<int,int> &X,const pair<int,int>&Y)
{
    return X.second>Y.second;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",s);
        top=0;
        for(int j=0;s[j];++j)
        {
            if(s[j]=='(')
            {
                stk[++top]='(';
            }
            else
            {
                if(top&&stk[top]=='(')
                {
                    top--;
                }
                else
                {
                    stk[++top]=')';
                }
            }
        }
        int cnt0=0,cnt1=0;
        for(int j=1;j<=top;++j)
        {
            if(stk[j]==')')++cnt0;
            else ++cnt1;
        }
        if(cnt0>cnt1)c.emplace_back(cnt0,cnt1);
        if(cnt0==cnt1)b.emplace_back(cnt0,cnt1);
        if(cnt0<cnt1)a.emplace_back(cnt0,cnt1);
    }
    sort(a.begin(),a.end(),cmp1);
    sort(c.begin(),c.end(),cmp2);
    int now=0;
    bool flag=true;
    for(auto &i:a)
    {
        now-=i.first;
        if(now<0)flag=false;
        now+=i.second;
    }
    for(auto &i:b)
    {
        now-=i.first;
        if(now<0)flag=false;
        now+=i.second;
    }
    for(auto &i:c)
    {
        now-=i.first;
        if(now<0)flag=false;
        now+=i.second;
    }
    if(now)flag=false;
    if(flag)
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 11376
#include <iostream>
#define mod 1000000007
using namespace std;

long long beki(long long x, long long a){
	if(a==0){
		return 1;
	}
	if(a%2==0){
		return (beki(x,a/2)%mod)*(beki(x,a/2)%mod);
	}else{
		return (((beki(x,a/2)%mod)*(beki(x,a/2)%mod))%mod)*x%mod;
	}
}

long long a[410],b[410],sum[410][410],dp[410][410],bek[410][410];
int main(){
	long long i,j,k,n,c;
	cin >> n >> c;
	for(i=0;i<n;i++){
		cin >> a[i];
	}
	for(i=0;i<n;i++){
		cin >> b[i];
	}
	
	for(i=0;i<n;i++){
		for(j=0;j<=c;j++){
			sum[i][j] = 0;
			dp[i][j] = 0;
		}
	}
	
	for(i=0;i<=400;i++){
		for(j=0;j<=400;j++){
			bek[i][j] = beki(i,j);
			bek[i][j] = bek[i][j]%mod;
		}
	}
	
	for(i=0;i<n;i++){
		for(j=0;j<=c;j++){
			for(k=a[i];k<=b[i];k++){
				sum[i][j] += bek[k][j];
				sum[i][j] = sum[i][j]%mod;
			}
		}
	}
	
	for(j=0;j<=c;j++){
		dp[0][j] = sum[0][j];
	}
	
	for(i=1;i<n;i++){
		for(j=0;j<=c;j++){
			for(k=0;k<=j;k++){
				dp[i][j] += dp[i-1][k]*sum[i][j-k];
				dp[i][j] = dp[i][j]%mod;
			}
		}
	}
	
	cout << dp[n-1][c] << endl;
}
	

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const int MAX_N = 100010;

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

int n;
double x[MAX_N], r[MAX_N];

double func(double y){
    double ret = 1000010;
    for (int i = 0; i < n; i++){
        ret = min(ret, sqrt(r[i] * r[i] - (y - x[i]) * (y - x[i])));
    }

    return ret;
}

int main(){
    cin >> n;
    double left = -1000010;
    double right = 1000010;
    for (int i = 0; i < n; i++){
        cin >> x[i] >> r[i];
        left = max(left, x[i] - r[i]);
        right = min(right, x[i] + r[i]);
    }

    for (int i = 0; i < 100; i++){
        double c1 = (left * 2 + right) / 3;
        double c2 = (left + right * 2) / 3;
        if (func(c1) > func(c2)) right = c2;
        else left = c1;
    }

    printf("%.15f\n", func((left + right) / 2));

    return 0;
}


Measured memory_bytes: 4772
// Problem : D - Sum of Divisors
// Contest : AtCoder - AtCoder Beginner Contest 172
// URL : https://atcoder.jp/contests/abc172/tasks/abc172_d
// Memory Limit : 1024 MB
// Time Limit : 3000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

/*
 *   ﷽
 * In the name of Allah, the Most Gracious, the Most Merciful
 */

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <climits>
#include <cmath>

using namespace std;

long long int sqd(long long n)
{
	return (n*(n+1)*(2*n+1))/6;
}

long long int solve(int n)
{
	long long int sqt = sqrt(n);
	long long int sqss = sqd(sqt); 
	long long int ans = 0;
	for(long long int m=1; m<=sqt; m++) 
	{
		long long int sdsa = n/m;
		auto tmp = (m * (m + sdsa) * (sdsa + 1 - m));
		ans += tmp;
	}
	return ans - sqss;
}

int main()
{
	int input;
	cin >> input;
	cout << solve(input);
	return 0;
}

Measured memory_bytes: 3156
import java.util.Scanner;

//K Cards
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), k = Math.min(n, sc.nextInt());
			if((n|k)==0)break;
			int[] a = new int[n];
			for(int i=0;i<n;i++)a[i]=sc.nextInt();
			int max = 1, CK = 1;
			for(int i=0;i<k;i++)CK*=a[i];
			max = CK;
			for(int i=k;i<n;i++){
				CK/=a[i-k]; CK*=a[i]; max = Math.max(max, CK);
			}
			int m = 1;
			for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
				if(a[i]==a[j])continue;
				int t = a[i];
				a[i] = a[j]; a[j] = t;
				int ck = 1;
				for(int x=0;x<k;x++)ck*=a[x];
				m = Math.max(m, ck);
				for(int x=k;x<n;x++){
					ck/=a[x-k]; ck*=a[x]; m = Math.max(m, ck);
				}
				a[j] = a[i]; a[i] = t;
			}
			System.out.println((m-max)<0?"NO GAME":(m-max));
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 0
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

template <typename T>
class WarshallFloyd {
private:
    int m_V;                   
    vector<vector<T>> m_d;
    
public:
    const T INF = std::numeric_limits<T>::max();
    WarshallFloyd(int V)
        : m_V(V) {

        // 辺のコストを初期化
        // 辺が存在しないときはINFとする
        m_d.resize(m_V, vector<T>(m_V, INF));
        REP(i,V) m_d[i][i] = 0;
    }
    void add_dir_edge(int from, int to, T cost) {
        m_d[from][to] = cost;
    }
    void add_undir_twoways(int v1, int v2, T cost) {
        add_dir_edge(v1, v2, cost);
        add_dir_edge(v2, v1, cost);
    }
    // 全点間の最短距離を求める
    vector<vector<T>> shortest_path() {
        REP(k, m_V) REP(i, m_V) REP(j, m_V) 
            // 辺が存在するときのみ短縮できる
            if(m_d[i][k] != INF && m_d[k][j] != INF)
                m_d[i][j] = min(m_d[i][j], m_d[i][k] + m_d[k][j]);
        return m_d;
    }
    // shortest_pathを呼んだあとに呼ぶこと
    bool has_negative_loop() {
        REP(i, m_V) {
            if (m_d[i][i] < 0) return true;
        }
        return false;
    }
};

int main(void)
{
    cin.sync_with_stdio(false);
    WarshallFloyd<int> wf(4);
    REP(n, 3) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        wf.add_undir_twoways(a, b, 1);
    }
    auto ret = wf.shortest_path();


    int mx = 0;
    REP(i, 4) {
        REP(j, 4) {
            // cerr << ret[i][j] << " ";
            mx = max(mx, ret[i][j]);
        }
        cout << endl;
    }
    if (mx == 3) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}


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

using ll = long long;
const int INF = 1e9+100;

const int S = 5e5 + 100;
const ll MOD = 998244353;

ll dp[S] = {0};
void add(int id, ll x){
	// cout<<"add: "<<id<<' '<<x<<'\n';
	x %= MOD;
	while(id < S){
		dp[id] += x;
		dp[id] %= MOD;
		id += id&-id;
	}
}
ll getVal(int id){
	// return dp[id];
	ll res = 0;
	while(id > 0){
		res += dp[id];
		res %= MOD;
		id -= id&-id;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, k;
	cin>>n>>k;
	vector<pair<int,int>> seg(k);
	for (int i = 0; i < k; i++){
		cin>>seg[i].first>>seg[i].second;
	}
	add(1, 1);
	add(2, -1);
	for (int pos = 1; pos < n; pos++){
		for (const auto it: seg){ // check index size
			add(pos + it.first, getVal(pos));
			add(pos + it.second+1, -getVal(pos));
			// for (int i = 0; i <= n; i++){
			// 	cout<<getVal(i)<<' ';
			// }
			// cout<<'\n';
		}
		// cout<<'\n';
	}
	cout<<(getVal(n) + MOD) % MOD<<'\n';
	return 0;
}

Measured memory_bytes: 6696
#include <stdio.h>
#include <string.h>

int main(void)
{
char st1[300], st2[200], st3[200];

scanf("%s", st1);
scanf("%s", st2);

strcpy(st3, st1);
strcat(st1, st3);


if(strstr(st1, st2) == NULL)
 printf("No\n");
else
 printf("Yes\n");

return 0;

}



Measured memory_bytes: 2100
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

const int MaxN = 100;
const int MaxM = 100;

const int MaxNV = MaxN + MaxM + 2;
const int MaxNE = MaxN * MaxM + 2;

const int INF = 0x3f3f3f3f;

int n, m;
char s[MaxM + 2];

int vS, vT;

struct halfEdge
{
	int v, w;
	halfEdge *next;
};
halfEdge adj_pool[MaxNE * 2], *adj_tail = adj_pool;
halfEdge *adj[MaxNV + 1];

inline void addEdge(const int &u, const int &v, const int &wA, const int &wB = 0)
{
	adj_tail->v = v, adj_tail->w = wA, adj_tail->next = adj[u], adj[u] = adj_tail++;
	adj_tail->v = u, adj_tail->w = wB, adj_tail->next = adj[v], adj[v] = adj_tail++;
}

inline halfEdge *oppo(const halfEdge *e)
{
	return adj_pool + ((e - adj_pool) ^ 1);
}

int q_n, q[MaxNV + 1];

int lev[MaxNV + 1];
halfEdge *dfsCur[MaxNV + 1];

inline bool calc_dist()
{
	q_n = 0;
	for (int u = 1; u <= vT; ++u)
		lev[u] = -1, dfsCur[u] = adj[u];
	lev[vS] = 0;

	q[++q_n] = vS;
	for (int i = 1; i <= q_n; ++i)
	{
		int u = q[i];
		for (halfEdge *e = adj[u]; e; e = e->next)
			if (e->w && !~lev[e->v])
			{
				lev[e->v] = lev[u] + 1;
				if (e->v == vT)
					return true;
				q[++q_n] = e->v;
			}
	}

	return false;
}

int dfs(const int &u, const int &flow)
{
	if (u == vT || !flow)
		return flow;

	int res = 0;
	for (halfEdge *&e = dfsCur[u]; e; e = e->next)
		if (e->w && lev[e->v] > lev[u])
		{
			int delta = dfs(e->v, min(e->w, flow - res));
			if (delta > 0)
			{
				e->w -= delta, oppo(e)->w += delta;
				if ((res += delta) == flow)
					break;
			}
		}

	if (res < flow)
		lev[u] = -1;

	return res;
}

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

	vS = n + m + 1, vT = vS + 1;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", s + 1);

		for (int j = 1; j <= m; ++j)
		{
			if (s[j] == 'o')
				addEdge(i, j + n, 1, 1);
			else if (s[j] == 'S')
			{
				addEdge(vS, i + 0, INF);
				addEdge(vS, j + n, INF);
			}
			else if (s[j] == 'T')
			{
				addEdge(i + 0, vT, INF);
				addEdge(j + n, vT, INF);
			}
		}
	}

	int tot_flow = 0;
	while (tot_flow < INF && calc_dist())
		tot_flow += dfs(vS, INF);

	if (tot_flow >= INF)
		cout << -1 << endl;
	else
		cout << tot_flow << endl;

	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
    update(a,b,x): 区間[a,b) の要素を x に更新。O(log(n))
    query(a,b): [a,b) での最小の要素を取得。O(log(n))
*/
template <typename T>
struct RMQ {
  const T INF = numeric_limits<T>::max();
  int n;
  vector<T> dat, lazy;
  RMQ(int size) : n(), dat(size * 4, INF), lazy(size * 4, INF) {
    int x = 1;
    while (size > x) {
      x *= 2;
    }
    n = x;
  }

  /*lazy eval*/
  void eval(int k) {
    if (lazy[k] == INF) {
      return;  //更新するものが無ければ終了
    }
    if (k < n - 1) {  //葉で無ければ子に伝搬
      lazy[k * 2 + 1] = lazy[k];
      lazy[k * 2 + 2] = lazy[k];
    }
    //自身を更新
    dat[k] = lazy[k];
    lazy[k] = INF;
  }

  void update(int a, int b, T x, int k, int l, int r) {
    eval(k);
    if (a <= l && r <= b) {  //完全に内側の時
      lazy[k] = x;
      eval(k);
    } 
    else if (a < r && l < b) {                   //一部区間が被る時
      update(a, b, x, k * 2 + 1, l, (l + r) / 2);  //左の子
      update(a, b, x, k * 2 + 2, (l + r) / 2, r);  //右の子
      dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }
  void update(int a, int b, T x) { update(a, b, x, 0, 0, n); }

  T query_sub(int a, int b, int k, int l, int r) {
    eval(k);
    if (r <= a || b <= l) {  //完全に外側の時
      return INF;
    } 
    else if (a <= l && r <= b) {  // 完全に内側の時
      return dat[k];
    }
    else{ //一部区間が被る時
      T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
      T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
      return (min(vl, vr));
    }
  }
  T query(int a, int b) { return query_sub(a, b, 0, 0, n); }

  /* debug */
  inline T operator[](int a) { return query(a, a + 1); }
  void print() {
      for (int i = 0; i < 2 * n - 1; ++i) {
          cout << (*this)[i];
          if (i != n) cout << ",";
      }
      cout << endl;
  }
};

int main() {
  int n, q;
  cin >> n >> q;
  RMQ<int> seg(n);
  for (int i = 0; i < q; i++) {
    int que, s, t, x;
    cin >> que;
    if(que==0){
      cin >> s >> t >> x;
      seg.update(s, t+1, x);
    } 
    else {
      cin >> s >> t;
      cout<<seg.query(s,t+1)<<'\n';
    }
  }
  return(0);
}


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

int main() {
  int X, Y;
  cin >> X >> Y;
  if(Y >= 2*X && Y<=4*X && Y%2 == 0){
    cout << "Yes" <<endl;
  }
  else{
    cout << "No" <<endl;
  }
}


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

using namespace std;

#define IO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define ull unsigned long long int

const int INF = 1e9 + 7;
const int N = 1e5+5;


int main() {

	IO;

	int n;
	cin >> n;
	
	vector<int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];
	
	int m;
	cin >> m;
	
	for (int j = 0; j < m; ++j) {
		int pos, x, ans = 0;
		cin >> pos >> x;
		
		for (int i = 0; i < n; ++i) {
			if ( pos-1 == i) ans += x;
			else ans += a[i];
		}
		cout << ans << endl;
	}
	
}


Measured memory_bytes: 3620
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num, p = 0, i ,[0]
        for _ in range(h):
            p.append(p[-1]+num%2)
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]
        for j in range(w):
            num = i
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p[m]] += s[m][j]
            if max(nex) > k:
                x = float('inf')
                break            
            for m in range(checker+1):
                c[m] += nex[m]
                if c[m]>k:
                    c = nex
                    x += 1
                    break
        result.append(checker+x)
print(min(result))

Measured memory_bytes: 47196
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
constexpr int MOD = 1000000007;
int main()
{
    int N;
    cin >> N;
    vector<lint> A(N);
    REP(i, N) cin >> A[i];
    vector<lint> X(N);
    REP(i, N) {
        if(i % 2 == 0) { 
            X[0] += A[i];
        } else {
            X[0] -= A[i];
        }
    }
    X[0] /= 2;
    X[N-1] = A[N-1] - X[0];
    IFOR(i, 1, N-1) {
        X[i] = A[i] - X[i+1];
    }
    REP(i, N) cout << X[i]*2 << (i!=N-1 ? " " : "");
    cout << endl;
}

Measured memory_bytes: 2944
#include<iostream>
#include<string>
#include<map>
using namespace std;
int main(){
  map<string,int> data;
int i;
int N;
cin>>N;
string a[N];
for(i=0;i<N;i++){
cin>>a[i]; 
data[a[i]]++;}
  int M;
cin>>M;
string b[M];
for(i=0;i<M;i++){
cin>>b[i];
  data[b[i]]--;
}  
  int ans=0;
  for(auto itr:data){
   ans=max(ans,itr.second);}
  cout<<ans;
}
  


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

typedef long long ll;
const int N = 100 + 5, W = 1e5 + 5;

int n, w;
ll dp[N][W], wt[N], v[N];

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> w;
  for(int i = 1; i <= n; i++) cin >> wt[i] >> v[i];

  for(int j = wt[1]; j <= w; j++) dp[1][j] = v[1];
  for(int i = 2; i <= n; i++) {
    for(int j = 1; j <= w; j++) {
      if(j - wt[i] >= 0) dp[i][j] = v[i] + dp[i-1][j - wt[i]];
      dp[i][j] = max(dp[i][j], dp[i-1][j]);
    }
  }
  cout << dp[n][w] << "\n";
}


Measured memory_bytes: 79360
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>

using namespace std;
template<class T1, class T2> inline void chkmin(T1 &x, const T2 &y) {if (x > y) x = y;}
template<class T1, class T2> inline void chkmax(T1 &x, const T2 &y) {if (x < y) x = y;}
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define mp make_pair
#define pb push_back
#define read(FILENAME) freopen((string(FILENAME) + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((string(FILENAME) + ".out").c_str(), "w", stdout);





int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read("input");
	int k;
	string s;
	cin >> s;
	k = sz(s);
	int ans = 0;
	for (auto x: s) {
		if (x == 'o') {
			ans++;
		}
	}
	if (ans + 15 - k >= 8) {
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}
	return 0;
}


Measured memory_bytes: 256
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    mul4 = len([a for a in A if a % 4 == 0])
    mul2 = len([a for a in A if a % 4 != 0 and a % 2 == 0])
    less = N - 2*mul4 - 1
    if less <= 0:
        print("Yes")
    elif less + 1 <= mul2:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 63384
use std::io::*;

fn main() {
  let stdin = stdin();
  let line = stdin.lock().lines().next().unwrap().unwrap();
  let mut iter = line.split_whitespace().map(|s| s.parse::<i32>().unwrap());

  let (a, b) = (iter.next().unwrap(), iter.next().unwrap());

  println!("{}", (a - b).abs());
}


Measured memory_bytes: 5024
#include <iostream>
#include <math.h> 
#include <string> 
#include <algorithm>
#include <numeric>
#include <cmath>
using namespace std;

int main() {

	int c[10][10]; for(int i = 1; i <= 3; i++) for(int j = 1; j <= 3; j++) cin >> c[i][j];
	string res = "Yes";

	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			for (int k = 1; k <= 3; k++) {
				for (int l = 1; l <= 3; l++) if (c[i][j] + c[k][l] != c[i][l] + c[k][j]) res = "No";
			}
		}
	}
	cout << res << endl;

}

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

struct Mod
{
    static const int P = int(1e9+7);
    long long k;

    Mod() = default;
    Mod(long long k) : k(k%P) {}
};

Mod operator+(const Mod a, const Mod b) { return a.k + b.k; }
Mod operator*(const Mod a, const Mod b) { return a.k * b.k; }
Mod operator-(const Mod a, const Mod b) { return a.k + (Mod::P - b.k); }
Mod operator+=(Mod& a, const Mod b) { return a = a+b; }
Mod operator-=(Mod& a, const Mod b) { return a = a-b; }
Mod power(const Mod a, const int k)
{
    if (k == 0) return 1;
    else if (k % 2 == 0) return power(a*a, k/2);
    else return a * power(a*a, k/2);
}

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

    auto divisors = vector<int>();
    for (auto d = 1; d*d <= N; d++) if (N % d == 0)
    {
        divisors.push_back(d);
        if (d != N/d) divisors.push_back(N/d);
    }
    sort(begin(divisors), end(divisors));
    const auto D = int(divisors.size());

    auto answer = Mod(0);
    auto ways = vector<Mod>(divisors.size());
    for (auto i = 0; i < D; i++)
    {
        ways[i] = power(K, (divisors[i] + 1)/2);
        for (auto j = 0; j < i; j++) if (divisors[i] % divisors[j] == 0)
            ways[i] -= ways[j];

        answer += ways[i] * (divisors[i] % 2 == 1 ? divisors[i] : divisors[i]/2);
    }
    cout << answer.k << endl;
}


Measured memory_bytes: 256
if __name__ == '__main__':
    args = input().split(' ')
    n = int(args[0])
    t = int(args[1])

    queue = []

    prolist = {}
    finish = []
    for i in range(n):
        datas = input().split(' ')
        prolist[datas[0]] = int(datas[1])
        # add to queue by order
        queue.append(datas[0])
    
    tottime = 0
    while len(queue) > 0:
        name = queue.pop(0)
        if prolist[name] == 0:
            pass
        else:
            if prolist[name] > t:
                # has some task unfinish
                prolist[name] -= t
                tottime += t
                queue.append(name)
            else:
                # finish all task, quit
                finish.append('%s %d' %(name, tottime + prolist[name]))
                tottime += prolist[name]
                prolist[name] = 0
    
    for info in finish:
        print(info)



Measured memory_bytes: 14888
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		long[] souwa=new long[N];
		long sum=0;

		int[] cd=new int[N];
		for(int i=0; i<N; i++) {
			cd[i]=sc.nextInt();
		}
		souwa[0]=cd[0];
		sum=cd[0];

		for(int i=1; i<N; i++) {
			souwa[i]=souwa[i-1]+cd[i];
			sum+=cd[i];
		}
		long min_diff=9223372036854775807L;

		for(int i=0; i<N-1; i++) {
			min_diff=Math.min(Math.abs(2*souwa[i]-sum),min_diff);
		}
		System.out.println(min_diff);
	}
}

Measured memory_bytes: 88972
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    int a, b;
    cin >> a >> b;
    if((a+b)/2 == (a+b+1)/2){
        cout << (a+b)/2;
    }
    else
    {
        cout << "IMPOSSIBLE";
    }
    
    
    cout << endl;
}


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

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

	if (N - N / 100 * 100 - (N- N / 100 * 100) / 10 * 10 == N / 100) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
using System;
namespace HelloWorld
{
    class Program
    {
        static void Main()
        {
            double ansX = 0;
            double ansY = 0;
            double theta = 90;
            string line;
            while ((line = Console.ReadLine()) != "0,0")
            {
                string[] split = line.Split(',');
                int go = int.Parse(split[0]);
                int rotate = int.Parse(split[1]);

                ansX += Math.Cos(theta * Math.PI / 180) * go;
                ansY += Math.Sin(theta * Math.PI / 180) * go;
                theta -= rotate;
            }
            Console.WriteLine("{0}\n{1}", Math.Truncate(ansX), Math.Truncate(ansY));
        }
    }
}


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

using namespace std;

long long n,k,A[200005],F[200005];
long long ans;
vector<long long>v;

bool ok(long long x)
{
    long long i,need = 0;
    long long mn = 1e16;
    for(i=0;i<n;i++){
        if(x%F[i]==0)
            mn = x;
        else
            mn = min(mn,(x/F[i]+1)*F[i]);
    }
    for(i=0;i<n;i++)v.push_back(x/F[i]);
    for(i=0;i<n;i++)need += max((long long)0,A[i]-v[i]);
    v.clear();
    if(need <= k){
        ans = min(ans,mn);
        return true;
    }
    return false;
}

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

    long long i,lo,hi,mid;
    cin>>n>>k;
    for(i=0;i<n;i++)cin>>A[i];
    for(i=0;i<n;i++)cin>>F[i];
    sort(F,F+n);
    sort(A,A+n);reverse(A,A+n);
    if(ok(0)){
        cout<<0<<endl;
        return 0;
    }
    lo = 1;hi = 1e14;ans = 1e12;
    while(lo<=hi){
        mid = lo+(hi-lo)/2;
        if(ok(mid))hi = mid-1;
        else lo=mid+1;
    }
    cout<<ans<<'\n';
	return 0;
}


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

int main() {
  int N,A = 0,count = 0;
  cin >> N;
  vector<int>V(N);
  for ( int i = 0 ; i < N ; i++ )
    cin >> V.at(i);
  for ( int j = 0 ; j < N-1 ; j++ ) {
    if ( V.at(A) == 2) {
      count++;
      cout << count << endl;
      break;
    }
    else {
      A = V.at(A) - 1;
      count++;
      if ( j == N - 2 )
        cout << -1 << endl;
    }
  }
}



Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }

void solve();

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

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

const int MAX = 2000005; // c + r
ll fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}
// 二項係数計算
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

ll f(int r, int c) {
  return ((r + 2) * COM(c + r + 2, r + 2) % mod - c - 1 + mod) % mod * modpow(c + 1, mod - 2) % mod;
}

// https://www.wolframalpha.com/input/?i=Sum%5BSum%5Bcomb%28x+%2B+y%2C+x%29%2C+%7By%2C+0%2C+c%7D%5D%2C+%7Bx%2C+0%2C+r%7D%5D&lang=ja
void solve() {
  int r1, r2, c1, c2;
  cin >> r1 >> c1 >> r2 >> c2;

  COMinit();

  ll ans = f(r2, c2) + mod - f(r2, c1 - 1) + mod - f(r1 - 1, c2) + f(r1 - 1, c1- 1);
  cout << ans % mod << endl;
}


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

int main(){
  int X, Y;
  cin >> X >> Y;
  for(int i = 0; i <= X; ++i){
    if(i*2 + (X-i)*4 == Y){
      puts("Yes");
      return 0;
    }
  }
  puts("No");
}


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

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

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h1,m1,h2,m2,k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    m1 += h1*60;
    m2 += h2*60;
    m2 -= m1;
    cout << max(m2-k,0) << endl;

    return 0;
}

Measured memory_bytes: 3628
#include<stdio.h>
int main(){
  int n,a,b,d,e,min,mj,i,j,l,k;
  int f[21]={0};
  int m[21][21]={0};
  int c[21];
  scanf("%d %d",&n,&l);
  for(i=0;i<n;i++){
    c[i+1]=2100000000;
    for(j=0;j<n;j++)m[i+1][j+1]=-1;
  }
  for(i=0;i<l;i++){
    scanf("%d,%d,%d,%d",&a,&b,&e,&d);
    m[a][b]=e;
    m[b][a]=d;
  }
  scanf("%d,%d,%d,%d",&a,&b,&e,&d);
  f[a]=1;
  c[a]=0;
  mj=a;
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      if(f[j])continue;//printf("j%d\n",j);
      if(m[mj][j]!=-1){//道あったら
	if(c[j]>c[mj]+m[mj][j])c[j]=c[mj]+m[mj][j];//printf("j%d\n",j);
      }//小さい方入れる
    }
    min=2100000000;
    for(j=1;j<=n;j++){
      if(f[j])continue;
      if(min>c[j]){
	min=c[j];
	mj=j;
      }
    }//printf("mj%d\n",mj);
    f[mj]=1;
    //for(k=0;k<n;k++)printf("%d ",c[k+1]);//printf("\n");
  }
  e-=c[b]+d;//printf("%d\n",c[b]);
  for(i=0;i<n;i++)c[i+1]=2100000000;
  f[b]=2;
  c[b]=0;
  mj=b;//for(i=1;i<=n;i++)printf("%d ",f[i]);//printf("\n");
  for(i=1;i<n;i++){
    for(j=1;j<=n;j++){
      if(f[j]==2)continue;
      if(m[mj][j]!=-1){//道あったら
	if(c[j]>c[mj]+m[mj][j])c[j]=c[mj]+m[mj][j];
      }//小さい方入れる
    }
    min=2100000000;
    for(j=1;j<=n;j++){
      if(f[j]==2)continue;
      if(min>c[j]){
	min=c[j];
	mj=j;
      }
    }
    f[mj]=2;
    //for(k=0;k<n;k++)printf("%d ",c[k+1]);printf("\n");
  }
  printf("%d\n",e-c[a]);
  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

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

    int ans = 0;

    rep(i,1000){
        int a = i / 100;
        int b = (i % 100) / 10;
        int c = i % 10;
        char x = a + '0';
        char y = b + '0';
        char z = c + '0';
        bool s = false;
        bool t = false;
        rep(j,N){
            if(!s){
                if(S[j] == x)s = true;
            }
            else if(!t){
                if(S[j] == y)t = true;
            }
            else{
                if(S[j] == z){
                    ans++;
                    break;
                }

            }
        }
    }

    cout << ans << endl;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
using namespace std;

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

    ll ans = 2018;
    for(ll i = l; i < r; ++i) {
        for(ll j = i + 1; j <= r; ++j) {
            ans = min(ans, (i * j) % 2019);
            if(ans == 0) {
                cout << ans << endl;
                return 0;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3640
#include<iostream>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

int main(){
  int n,p,S[100000],T[100000];
  bool exist;
  cin >> n;
  rep(i,n)cin >> S[i];
  cin >> p;
  rep(i,p)cin >> T[i];

  int h;
  rep(i,n){
    int ch = i;
    REP(j,i,n){
      if(S[ch] > S[j])ch = j;
    }
    h=S[ch];
    S[ch]=S[i];
    S[i]=h;
  }

  int count=0;

  rep(i,p){
    int lef=0,rig=n;
    exist = false;
    while(lef < rig){
      int index=(lef+rig)/2;
      if(T[i] == S[index]){
	exist=true;
	break;
      }
      else if(T[i] < S[index]){
	rig=index;
      }
      else {
	lef = index+1;
      }
    }
    if(exist){
      count++;
    }
  }
  cout << count << endl;


}

Measured memory_bytes: 880
while 1
  n=gets.to_i
  break if n==0
  k=gets.split.map(&:to_i)
  s=gets.chomp
  a=[]
  ("a".."z").each do |e|
    a<< e
  end
  ("A".."Z").each do |e|
    a<< e
  end
  (0...s.size).each do |x|
    s[x]=a[(a.find_index(s[x])-k[x%k.size]+a.size)%a.size]
  end
  puts s
end

Measured memory_bytes: 8796
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    bool yes = (n%2 == 0);
    for (int i=0; i<n/2; i++) {
        if (s[i] != s[i+n/2]) {
            yes = false;
            break;
        }
    }
    cout << (yes ? "Yes" : "No") << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <limits.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

typedef unsigned long long ULLONG;
typedef long long LLONG;

template <class _T> static _T tp_abs(const _T& a) {
	return ((a < 0) ? (a * -1) : a);
}
template <class _T> static _T tp_min(_T a, _T b) {
	return a < b ? a : b;
}
template <class _T> static _T tp_max(_T a, _T b) {
	return a > b ? a : b;
}
template<class _T> static void get1int(_T& a) {
	const char* fmt = " %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld";
	}

	if (scanf(fmt, &a) < 0) {
		printf("g1int Error\n");
	}
}
template<class _T> static void get2int(_T& a, _T& b) {
	const char* fmt = " %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld";
	}

	if (scanf(fmt, &a, &b) < 0) {
		printf("g2int Error\n");
	}
}
template<class _T> static void get3int(_T& a, _T& b, _T& c) {
	const char* fmt = " %d %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld %lld";
	}

	if (scanf(fmt, &a, &b, &c) < 0) {
		printf("g3int Error\n");
	}
}
static void getstring(char* buff) {
	if (scanf(" %s", buff) < 0) {
		printf("getstr error!\n");
	}
}
static const long long MOD_NUM = 1000000007LL;

static void D_task();

int main()
{
	D_task();
	fflush(stdout);
	return 0;
}

class RunLengthEnc {
public:
	class RLEData {
	public:
		char c = 0;
		int cnt = 0;
	};

	typedef std::vector<RLEData> RLEvec;

	void Exec(RLEvec& vRle, const char* str) {
		int sLen = (int)strlen(str);

		char bfr = 0;
		RLEData ccnt;
		for (int i = 0; i < sLen; i++) {
			if (str[i] != bfr) {
				if (ccnt.c != 0) {
					vRle.push_back(ccnt);
				}
				ccnt.c = str[i];
				ccnt.cnt = 1;
			}
			else {
				ccnt.cnt++;
			}
			bfr = str[i];
		}
		if (ccnt.c != 0) {
			vRle.push_back(ccnt);
		}
	}

	static bool dsc_cnt(RLEData& a, RLEData& b) {
		return a.cnt > b.cnt;
	}
};

static void D_task()
{
	int N, K;
	get2int(N, K);
	
	auto str = new char[N + 1];
	str[N] = 0;
	getstring(str);

	RunLengthEnc::RLEvec data;
	RunLengthEnc enc;
	enc.Exec(data, str);

	std::vector<int> happy;
	int blkCnt = (int)data.size();
	int rest = K;
	char chg = 'R';
	if (data[0].c == 'L') {
		chg = 'L';
	}
	for (int i = 0; i < blkCnt; i++) {
		if ((i % 2) && (rest)) {
			data[i].c = chg;
			rest--;
		}
	}

	int ans = 0;
	int bfrc = 0;	//最初は不一致にする
	for (int i = 0; i < blkCnt; i++) {
		ans += data[i].cnt - 1;
		if (bfrc == data[i].c) {
			ans++;
		}
		bfrc = data[i].c;
	}

	printf("%d\n", ans);
}


Measured memory_bytes: 1528
K = int(input())
k = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(k[K-1])

Measured memory_bytes: 3060
n = int(input())
 
s = input()
 
x = []
 
for i in range(n):
    x.append(s[i])
 
import collections
 
clist = collections.Counter(x)
 
y = list(clist.values())
 
cnt = 1
 
for item in y:
    cnt = cnt * (item + 1)
 
cnt = cnt - 1
cnt = cnt % (10 ** 9 + 7)
print(cnt)

Measured memory_bytes: 48624
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int x; cin >> x;
  int ans = 1;
  for(int i=2; i<=x; i++) {
    int tmp = 1;
    while(tmp * i <= x) tmp *= i;
    if(tmp == i) break;
    chmax(ans, tmp);
  }
  cout << ans << endk;
  return 0;
}


Measured memory_bytes: 3564
n = int(input())
p = list(map(int,input().split()))
count = 0
for i in range(1,n-1,1):
    if min(p[i-1],p[i],p[i+1]) < p[i] < max(p[i-1],p[i],p[i+1]):
        count += 1
print(count)

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

using namespace std;
typedef long long ll;

ll n, K;
ll a[5010];

bool check(int m) {
  bool dp[5010] = {};
  dp[0] = true;
  for (int i = 0; i < n; i++) {
    if (i == m) continue;
    for (int j = K; j - a[i] >= 0; j--) {
      dp[j] |= dp[j - a[i]];
    }
  }

  bool res = false;
  for (int i = max(0LL, K - a[m]); i < K; i++) {
    res |= dp[i];
  }
  return res;
}

int main() {
  cin >> n >> K;

  ll sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    sum += a[i];
  }

  if (sum < K) {
    cout << n << endl;
    return 0;
  }
  sort(a, a + n);

  int ng = -1, ok = n - 1;
  while (ok - ng > 1) {
    int m = (ng + ok) / 2;
    if (check(m)) ok = m;
    else ng = m;
  }
  cout << ng + 1 << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int a[101][101];
int main(){
    int n,w,h,x,y,s,t;
    while(cin>>n,n){
        cin>>w>>h;
        memset(a,0,sizeof(a));
        rep(i,n){
            cin>>x>>y;
            ++a[y][x];
        }
        cin>>s>>t;
        rep(i,h)rep(j,w){
        a[i+1][j+1]+=a[i][j+1]+a[i+1][j]-a[i][j];
        }
        int mx=0;
        FOR(i,1,h-t+2)FOR(j,1,w-s+2){
            mx=max(mx,a[i+t-1][j+s-1]-a[i+t-1][j-1]-a[i-1][j+s-1]+a[i-1][j-1]);
        }
        cout<<mx<<endl;
    }
    return 0;
}


Measured memory_bytes: 3136
n = int(input())
p = list(map(float, input().split()))
dp = [[0.0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(n+1):
        if j == 0:
            dp[i+1][0] = dp[i][0] * (1 - p[i])
        else:
            dp[i+1][j] = dp[i][j-1] * p[i] + dp[i][j] * (1-p[i])
print(1 - sum(dp[n][:(n+1)//2]))

Measured memory_bytes: 120412
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<vector<pair<int,int>>> tes(n+1);
	for (int i = 1; i <= n; i++) {
		vector<pair<int, int>> t;
		int a;
		cin >> a;
		for (int j = 0; j < a; j++) {
			int x, y;
			cin >> x >> y;
			t.emplace_back(x, y);
		}
		tes[i] = t;
	}
	int ans = 0;
	for (int mask = 0; mask < (1 << n); mask++) {
		set<int>now;
		for (int j = 0; j < n; j++) {
			if (mask & (1 << j)) {
				now.emplace(j+1);
			}
		}
		bool ok = true;
		for (auto cur : now) {
			for (auto t : tes[cur]) {
				if (t.second == 0 && now.find(t.first) != now.end()) {
					ok = false;
				}
				if (t.second == 1 && now.find(t.first) == now.end()) {
					ok = false;
				}
			}
		}
		if (ok) {
			ans = max(ans, (int)__builtin_popcount(mask));
		}
	}
	cout << ans;
	return 0;
}

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

#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y
//#define CPP_STR(x) CPP_STR_I(x)
//#define CPP_STR_I(args...) #args
//#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
//using f80 = __float80;

constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
constexpr char EL[] = "\n";

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(),(x).end()
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define UNIQUE(x) (x).erase(unique(all(x)), (x).end());
#define REPIT(x) for(auto it=(x).begin(), end=(x).end(); it!=end; ++it)
#define perm(c) sort(all(c)); for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

template<typename T = i64>
T IN() { T x; cin >> x; return (x); }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T(&)[N]) { return static_cast<i64>(N); }

template<typename T, typename U, typename Comp = less<>>
bool chmax(T& xmax, const U& x, Comp comp = {}) {
	if (comp(xmax, x)) {
		xmax = x;
		return true;
	}
	return false;
}
template<typename T, typename U, typename Comp = less<>>
bool chmin(T& xmin, const U& x, Comp comp = {}) {
	if (comp(x, xmin)) {
		xmin = x;
		return true;
	}
	return false;
}

void print() {
  cout << EL;
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cout << head;
  if (sizeof...(tail) != 0) cout << " ";
  print(forward<Tail>(tail)...);
}
template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
	cout << a;
	if (&a != &vec.back()) cout << " ";
  }
  cout << EL;
}
template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) {
	print(vec);
  }
}

struct ProconInit {
	static constexpr int IOS_PREC = 15;
	static constexpr bool AUTOFLUSH = false;

	ProconInit() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(IOS_PREC);
		if (AUTOFLUSH)
			cout << unitbuf;
	}
} PROCON_INIT;
#pragma endregion

signed solve()
{
	string s;
	cin >> s;
	map<char, int> mp;
	REP(i, SIZE(s))
	{
		if (i == 0)
		{
			mp[s[i]]++;
		}
		else
		{
			if (s[i - 1] != s[i])
				mp[s[i]]++;
		}
	}
	int ans = 0;
	if (SIZE(mp) > 1)
		ans = mp['B'] + mp['W'] - 1;
	print(ans);
	return 0;
}

#ifndef LOCALCODE
signed main()
{
	return solve();
}
#endif


Measured memory_bytes: 512
//#include <bits/stdc++.h>
#include <algorithm>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e10;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }

signed main() {
  int n, m;
  cin >> n >> m;
  int ans = 1;
  for (int i = 1; i * i < m + 1; i++) {
    if (m % i == 0) {
      int b = m / i;
      if (i * n <= m) cmax(ans, i);
      if (b * n <= m) cmax(ans, b);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#define ENABLE_DEBUG 0
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
#define REP(i, n) for (int i = 0; (i64)(i) < (i64)(n); ++i)

#if ENABLE_DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define DEBUG(...)                \
  do {                            \
    cerr << " \033[33m (L";       \
    cerr << __LINE__ << ") ";     \
    cerr << #__VA_ARGS__ << ": "; \
    cerr << "\033[0m";            \
    debug(__VA_ARGS__);           \
    cerr << endl;                 \
  } while (0)
#else
#define debug(...)
#define DEBUG(...)
#endif

const i64 INF = 1LL << 50;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  cin.ignore();
  vector<vector<i64>> adj(N, vector<i64>(N, INF));
  vector<int> deg(N);
  REP(i, N) {
    string s;
    getline(cin, s);
    int d = 0;
    REP(j, N) {
      if (s[j] == '1') {
        adj[i][j] = 1;
        d++;
      } else if (j == i) {
        adj[i][j] = 0;
      }
    }
    deg[i] = d;
  }

  vector<int> color(N, -1);
  auto dfs = [&](auto rec, int v, int p, int c) -> bool {
    if (color[v] != -1) {
      return (color[v] == c);
    }
    color[v] = c;
    REP(x, N) {
      if (x == v || x == p || adj[v][x] != 1) continue;
      if (!rec(rec, x, v, c ^ 1)) return false;
    }
    return true;
  };

  if (!dfs(dfs, 0, -1, 0)) {
    cout << -1 << endl;
    return 0;
  }

  REP(k, N) REP(i, N) REP(j, N) {
    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
  }

  i64 diam = 1;
  REP(i, N) REP(j, N) {
    if (adj[i][j] != INF && diam < adj[i][j]) {
      diam = adj[i][j];
      DEBUG(i, j, diam);
    }
  }
  cout << (diam + 1) << endl;
}


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

int main() {
    int a,b,k;
    cin >> a >> b >> k;
    int count = 0;
    int ans = 1;
    for(int c = max(a,b);c>=1;c--){
        if(a % c == 0 && b % c == 0){
            count++;
            if(count ==k){
                ans = c;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N=int(input())
List=[input() for i in range(N)]

dict = {}

for i in range(N):
	if List[i] in dict:
		dict[List[i]] += 1
	else:
		dict[List[i]] = 1

dict_list = list(dict.items())
dict_list.sort(key=lambda x: x[1], reverse=True)
max = dict_list[0][1]
dict_list.sort(key=lambda x: x[0])

for id in dict_list:
	if max == id[1]:
		print(id[0])


Measured memory_bytes: 48076
import itertools
li = list(map(int,input()))

# 0- 1+
for i in itertools.product([0,1], repeat=3): 
    tmp = li[0]
    for j,k in enumerate(i):
        if k:
            tmp += li[j+1]
        else:
            tmp -= li[j+1]
    if tmp == 7:
        L = str(li[0])
        for _ in range(3):
            if i[_]:
                L += '+' + str(li[_+1])
            else:
                L += '-' + str(li[_+1])
        print(L+'=7')
        break


Measured memory_bytes: 3064
# -*- coding:utf-8 -*-

def solve():
    import sys

    N = int(sys.stdin.readline())

    dp = [None]*45
    dp[0], dp[1] = 1, 1

    def fib(n):
        if dp[n] is not None:
            return dp[n]
        dp[n] = fib(n-1) + fib(n-2)
        return dp[n]

    print(fib(N))


if __name__ == "__main__":
    solve()



Measured memory_bytes: 5616
#include<cstdio>
#include<iostream>
#include<math.h>
#include<algorithm>

using namespace std;

# define mod 1000000007
long long a[100005];

int main()
{
    a[0]= 1;
    long long n;
    for(int i = 1; i < 100005; i++)
        a[i] = a[i-1]*i % mod;

    while(~scanf("%lld",&n))
    {
         cout << a[n] << endl;
    }
    return 0;
}


Measured memory_bytes: 1024