akhauriyash/Code-Regression huggingface dataset:
def main():
    N = int(input())
    S1 = input()
    S2 = input()
    cnt = 0
    MOD = 10 ** 9 + 7
    i = 0
    while i < N:
        if i == 0:
            if S1[i] == S2[i]:
                cnt += 3
                cnt %= MOD
                i += 1
            else:
                cnt += 6
                cnt %= MOD
                i += 2
        else:
            if S1[i] == S2[i]:
                if S1[i-1] == S2[i-1]:
                    cnt *= 2
                    cnt %= MOD
                    i += 1
                else:
                    cnt *= 1
                    cnt %= MOD
                    i += 1
            else:
                if S1[i-1] == S2[i-1]:
                    cnt *= 2
                    cnt %= MOD
                    i += 2
                else:
                    cnt *= 3
                    cnt %= MOD
                    i += 2

    print(cnt)




if __name__ == "__main__":
    main()

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    string n;
    
    cin >> n;
    
    for (int i = 0; i < 3; i++) {
        if (n[i] == '1') {
            n[i] = '9';
        }
        else if (n[i] == '9') {
            n[i] = '1';
        }
    }
    
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 2000000
#define INF (1<<30)

int H,A[MAX+1];

void maxHeap(int i){
  int l,r,largest;
  l=2*i;
  r=2*i+1;

  if(l<=H && A[l]>A[i])largest=l;
  else largest=i;
  if(r<=H && A[r]>A[largest])largest=r;

  if(largest!=i){
    int t=A[i];
    A[i]=A[largest];
    A[largest]=t;
    maxHeap(largest);
  }
}

int extract(){
  int maxv;
  if(H<1)return -INF;
  maxv=A[1];
  A[1]=A[H--];
  maxHeap(1);
  return maxv;
}

void increaseKey(int i,int key){
  if(key<A[i])return;
  A[i]=key;
  while(i>1 && A[i/2]<A[i]){
    swap(A[i],A[i/2]);
    i=i/2;
  }
}

void insert(int key){
  H++;A[H]=-INF;
  increaseKey(H,key);
}
int main(){
  int key;
  char com[10];
  cin>>H;


  while(1){
    scanf("%s", com);
    if(com[0]=='e'&&com[1]=='n')break;
    if(com[0]=='i'){
      scanf("%d",&key);
      insert(key);
    }else{
      printf("%d\n", extract());
    }
  }
  /*
  for(int i=1;i<H+1;i++){
    cin>>A[i];
  }
  for(int i=H/2;i>=1;i--)maxHeap(i);
  for(int i=1;i<=H;i++){
    cout<<" "<<A[i];
  }
  cout<<endl;
*/
  return 0;
}



Measured memory_bytes: 7068
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int INF = pow(2, 31) - 1;
#define ll long long
#define DEBUG(x) cout << "DEBUG>" << #x << ":" << x << endl;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int num(vector<int> v, int n) {
  int ans = 0;
  REP(i, v.size()) {
    if(v[i] >= n - 1) {
      ans++;
    }
  }
  return ans;
}

int main() {
  int N;
  cin >> N;
  vector<int> e(N + 1);
  e[1] = 1;
  FOR(i, 2, N) {
    int cur = i;
    FOR(j, 2, i) {
      while(cur % j == 0) {
        e[j]++;
        cur /= j;
      }
    }
  }
  int ans = num(e, 75) + num(e, 25) * (num(e, 3) - 1) + num(e, 15) * (num(e, 5) - 1) + (num(e, 5) * (num(e, 5) - 1)) * (num(e, 3) - 2) / 2;
  cout << ans << endl;
  return 0;
}


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

import sys

def mx( a ):
    # dictの最大値を見る
    max = 0
    for k, v in a.items():
        if max < v:
            max = v
    return max

def remove_duplicates(x):
    y=[]
    for i in x:
        if i not in y:
            y.append(i)
    return y

def tryal( stdin, i ):
    # stdinを先頭からi+1文字ずつ取り出して
    atoz = {
    "a":0,
    "b":0,
    "c":0,
    "d":0,
    "e":0,
    "f":0,
    "g":0,
    "h":0,
    "i":0,
    "j":0,
    "k":0,
    "l":0,
    "m":0,
    "n":0,
    "o":0,
    "p":0,
    "q":0,
    "r":0,
    "s":0,
    "t":0,
    "u":0,
    "v":0,
    "w":0,
    "x":0,
    "y":0,
    "z":0
    }
    for j in range(len(stdin)-i):
        c = stdin[j:j+i+1]
        #print remove_duplicates(c)
        for c1 in list(remove_duplicates(c)):
            atoz[c1] = atoz[c1] + 1
            #print "char:" + c1 + " count:" + str(atoz[c1])
    #print "max:" + str(mx( atoz ))
    return mx( atoz )

stdin = sys.stdin.readline().strip()

for i in range(len(stdin)+1):
    t = tryal( stdin, i )
    if t == len(stdin)-i:
        print str(i)
        break
        # print "try["+ str( i ) +"]=" + str(t) + " correct!!"
    #else:
    #    print "try["+ str( i ) +"]=" + str(t)

Measured memory_bytes: 2696
A = list(input())
B = list(input())
C = list(input())
turn = 1
for i in range(len(A)*3):
    if turn == 1:
        #A勝利
        if len(A) == 0:
            print("A")
            break
        else:
            if A[0] == "a":
                turn = 1
            elif A[0] == "b":
                turn = 2
            elif A[0] == "c":
                turn = 3
            A.remove(A[0])
    if turn == 2:
        #B勝利
        if len(B) == 0:
            print("B")
            break
        else:
            if B[0] == "a":
                turn = 1
            elif B[0] == "b":
                turn = 2
            elif B[0] == "c":
                turn = 3
            B.remove(B[0])
    if turn == 3:
        #C勝利
        if len(C) == 0:
            print("C")
            break
        else:
            if C[0] == "a":
                turn = 1
            elif C[0] == "b":
                turn = 2
            elif C[0] == "c":
                turn = 3
            C.remove(C[0])

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

int f(int x) {
    int keta = 0;
    while (x) {
        keta++;
        x /= 10;
    }
    return keta;
}

int main() {
    ll n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n%i==0) {
            if (ans==0) ans = max(f(i),f(n/i));
            else ans = min(max(f(i),f(n/i)),ans);
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

typedef long long/*--------------------*/ll;
typedef long double/*------------------*/ld;
typedef unsigned long long/*-----------*/ull;
typedef pair<ll, ll >/*----------------*/pll;
typedef std::vector<pll >/*------------*/vpll;

#define rep(i,a)/*---------------------*/for(i = 0 ; i < a ; i++)
#define repr(i,a)/*--------------------*/for(i = a ; i >= 0 ; i--)
#define REP(i,a,b)/*-------------------*/for(i = a ; i <= b ; i++)
#define REPR(i,a,b)/*------------------*/for(i = a ; i >= b ; i--)

#define YES/*--------------------------*/cout << "YES" << endl
#define NO/*---------------------------*/cout << "NO" << endl

#define lb/*---------------------------*/lower_bound
#define ub/*---------------------------*/upper_bound
#define pb/*---------------------------*/push_back
#define popb/*-------------------------*/pop_back
#define mem(a,b)/*---------------------*/memset(a,b,sizeof(a))
#define sz/*---------------------------*/size()
#define mpp/*--------------------------*/make_pair
#define bs/*---------------------------*/binary_search
#define gcd(a, b)/*--------------------*/__gcd(a, b)
#define lcm(a, b)/*--------------------*/((a)*((b)/gcd(a,b)))
#define sqr(x)/*-----------------------*/(x)*(x)
#define all(a)/*-----------------------*/a.begin(),a.end()

#define ff/*---------------------------*/first
#define ss/*---------------------------*/second

#define endl/*-------------------------*/'\n'
#define inf/*--------------------------*/(ll)2e15
#define MOD/*--------------------------*/(ll)1000000007

void solve();
void boost()
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
}
int main()
{
	boost();
	ll t,i;
	t = 1;
    //cin >> t;
	REP(i,1,t)
	{
       //cout << "Case "<< i << ": ";
       solve();
	}
	return 0;
}
void solve()
{
    ll n,i;
    cin >> n;
    vector<ld> v(n),t(n),tt(n+1);
    tt[0] = 0;
    rep(i,n)
    {
        cin >> t[i];
        tt[i+1] = t[i] + tt[i];
    }
    rep(i,n)  cin >> v[i];
    ld ans = 0,p = 0;
    for(ld d = 0.0 ; d <= tt[n] ; d += 0.5)
    {
        ld imin = min(d,tt[n]-d);
        rep(i,n)
        {
            ld k;
            if(d <= tt[i])  k = v[i] + (tt[i] - d);
            else if(d >= tt[i+1]) k = v[i] + (d - tt[i+1]);
            else k = v[i];
            imin = min(imin,k);
        }
        ans += (p + imin)/4;
        p = imin;
    }
    cout << setprecision(10) << fixed << ans << endl;
}



















Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int s;
  cin >> s;
  string arare[s]={};
  bool flag=false;
  
  for (int i = 0; i < s; i++){
    string tmp;
	cin >> tmp ;
    if(tmp=="Y"){flag=true;}

  }
if(flag){cout << "Four" <<endl;}
  else {cout <<"Three" <<endl;}
 
}

Measured memory_bytes: 256
a,b,c,x,y=[int(i) for i in input().split()]

if 2*c<(a+b):
    if x>=y:
        if 2*c<a:
            print(2*c*x)
        else:
            print(2*c*y+(x-y)*a)
    else:
        if 2*c<b:
            print(2*c*y)
        else:
            print(2*c*x+(y-x)*b)
else:
    print(a*x+b*y)
    
        


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	int n,k;
	int a;
	int c[200001]={};

	cin>>n>>k;

	rep(i,n){
		cin>>a;
		c[a-1]++;
	}
	sort(c,c+n);

	int total=0;
	rep(j,n-k){
		total+=c[j];
	}
	cout<<total<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    cout << (1110 - n) % 1000 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n-1); i >= 0; i--)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;

// Binary Indexed Tree (Fenwick Tree)
template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  // 0-indexed
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  // 0-indexed
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  // 半開区間
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

int main(){

    int N, Q;
    string S;
    cin >> N >> S >> Q;
    
    vector<BIT<int>> indices(26, BIT<int>(N));

    rep(i,N) indices[S[i]-'a'].add(i,1);

    rep(i,Q){
        int type; cin >> type;
        if (type == 1){
            int index; cin >> index;
            index--;
            char letter; cin >> letter;
            indices[S[index]-'a'].add(index,-1);
            indices[letter-'a'].add(index,1);
            S[index] = letter;
        }
        else{
            int left, right;
            cin >> left >> right;
            left--;
            int ans = 0;
            rep(i,26){
                if (indices[i].sum(left,right) > 0) ans++;
            }
            cout << ans << endl;
        }
    }
}

Measured memory_bytes: 56820
#include<stdio.h>
#include<string.h>
int main(void)
{
  char sun[]="Sunny";
  char rei[]="Rainy";
  char cro[]="Cloudy";
  char s[100000];
  scanf("%s",s);
  if(strcmp(s,sun)==0){
	printf("%s\n",cro);
  }
  else if(strcmp(s,rei)==0){
    printf("%s\n",sun);
  }
  else{
    printf("%s\n",rei);
  }
  return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
// const int MOD = 1e9+7;
const int MOD = 998244353;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

const int MAX = 1000000;
long long 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;
    }
}

// 二項係数計算
long long 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 modpow(ll a, ll n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main()
{
    cout << fixed << setprecision(15);
    ll N, M, K;
    cin >> N >> M >> K;

    // 前処理
    COMinit();

    ll ans = 0;
    for(ll i=0; i<=K; i++){
        ans += COM(N-1, i) * M % MOD * modpow(M-1, N-1-i) % MOD;
        // ans = ans % MOD;
    }
    cout << (ans+MOD) % MOD << endl;
    return 0;
}

Measured memory_bytes: 27080
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

int a[100000];
int depth[100000];
int k, ans = 0;
bool used[100000];

int dfs(int v) {
    if (used[v]) return depth[v];
    used[v] = true;
    depth[v] = dfs(a[v]) + 1;
    return depth[v];
}

int main(void) {
    int i, n;
    scanf("%d%d",&n,&k);
    REP (i,n) {
        scanf("%d",&a[i]);
        a[i]--;
    }
    if (a[0] > 0) ans++;
    used[0] = true;
    a[0] = 0;
    REP (i,n) dfs(i);
    priority_queue<pair<int,int>> q;
    REP (i,n) q.push(make_pair(depth[i],i));
    REP (i,n) used[i] = false;
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        bool co = false;
        REP (i,k-1) {
            x = a[x];
            if (used[x]) {
                co = true;
                break;
            }
            used[x] = true;
        }
        if (co) continue;
        if (a[x] > 0) {
            ans++;
            a[x] = 0;
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  int n, k, x, y;
  cin >> n;
  cin >> k;
  cin >> x;
  cin >> y;

  if (n < k) {
    k = n;
  }
  n = n - k;
  k = k * x;
  n = n * y;
  cout << (k + n) << endl;
}

Measured memory_bytes: 256
from itertools import accumulate
from bisect import bisect_right
N, M, K = [int(x) for x in input().split()]
A = [0] + [int(x) for x in input().split()]
B = [0] + [int(x) for x in input().split()]

cumA = list(accumulate(A))
cumB = list(accumulate(B))

ans = 0
for i in range(N + 1):
    if cumA[i] > K: break
    Tb = K - cumA[i]
    temp = i + bisect_right(cumB, Tb) - 1
    ans = max(ans, temp)

print(ans)

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

long long solve();

int main()
{
	printf("%lld\n", solve());

	return 0;
}

long long solve()
{
	int n;
	scanf("%d", &n);
	std::vector<long long> a(n);
	for (auto& e: a) scanf("%lld", &e);
	if (a.front() > 0) return -1;
	for (int i{1}; i < n; i++)
		if (a[i] > a[i - 1] + 1)
			return -1;
	long long sum{};
	for (int i{n - 1}; i > 0; i--)
	{
		if (a[i] == a[i - 1] + 1)
			sum++;
		else
			sum += a[i];
	}
	return sum;
}

Measured memory_bytes: 1792
#include <stdio.h>

 int main(void)
 {
      int i, j;
 
      for (i = 0; i < 9; i++){
          for (j = 0; j < 9; j++){
              printf("%dx%d=%d\n", i + 1, j + 1, (i + 1) * (j + 1));
         }
     }
     return (0);
 }

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

int main() {
  long n,i,a[111111],sum[111111];
  cin>>n;
  for(i=0;i<n;i++)
    cin>>a[i];
  sort(a,a+n);
  sum[0]=a[0];
  for(i=1;i<n;i++)
    sum[i]=sum[i-1]+a[i];
  i=1;
  while(1){
    if(sum[n-i-1]*2<a[n-i]){
      cout<<i<<endl;
      return 0;
    }
    i++;
    if(i==n){
      cout<<n<<endl;
      return 0;
    }
  }
}


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

using namespace std;

int main() {
  int H, W;
  char G[102][102];
  // 出力しない行
  vector<int> v1;
  // 出力しない列
  vector<int> v2;

  cin >> H >> W;

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> G[i][j];
    }
    G[i][W] = '\n';
  }

  for (int i = 0; i < H; i++) {
    bool flag = true;
    for (int j = 0; j < W; j++) {
      if (G[i][j] == '#') {
        flag = false;
      }
    }
    if (flag) { v1.push_back(i); }
  }

  for (int i = 0; i < W; i++) {
    bool flag = true;
    for (int j = 0; j < H; j++) {
      if (G[j][i] == '#') {
        flag = false;
      }
    }
    if (flag) { v2.push_back(i); }
  }

  for (int i = 0; i < H; i++) {
    for (int j = 0; j <= W; j++) {
      if (find(v1.begin(), v1.end(), i) != v1.end()) {
        continue;
      }
      if (find(v2.begin(), v2.end(), j) != v2.end()) {
        continue;
      }
      cout << G[i][j];
    }
  }
  return 0;
}


Measured memory_bytes: 256
def main():
	H, W, K = [int(k) for k in input().split(" ")]
	C = []
	black_in_row = []
	black_in_col = [0] * W
	for i in range(H):
		C.append(list(input()))
		black_in_row.append(C[i].count("#"))
		for j in range(W):
			if C[i][j] == "#":
				black_in_col[j] += 1

	black = sum(black_in_row)
	if black < K:
		print(0)
		return 0

	cnt = 0
	for i in range(2 ** H):
		row_bit = [f for f, b in enumerate(list(pad_zero(format(i, 'b'), H))) if b == "1"]
		r = sum([black_in_row[y] for y in row_bit])
		for j in range(2 ** W):
			col_bit = [f for f, b in enumerate(list(pad_zero(format(j, 'b'), W))) if b == "1"]
			c = sum([black_in_col[x] for x in col_bit])
			bl = black - r - c + sum([1 for p in row_bit for q in col_bit if C[p][q] == "#"])
			if bl == K:
				cnt += 1
	print(cnt)


def pad_zero(s, n):
	s = str(s)
	return ("0" * n + s)[-n:]

main()

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

int main() {
  int n;
  cin >> n;
  int AC = 0;
  int WA = 0;
  int TLE = 0;
  int RE = 0;
  rep(i, n){
    string a;
    cin >> a;
    if(a == "AC") AC++;
    if(a == "WA") WA++;
    if(a == "TLE") TLE++;
    if(a == "RE") RE++;
  }
  cout << "AC x " + to_string(AC) << endl;
  cout << "WA x " + to_string(WA) << endl;
  cout << "TLE x " + to_string(TLE) << endl;
  cout << "RE x " + to_string(RE) << endl;
}


Measured memory_bytes: 3692
N = int(input())
Name = [input()[0] for _ in range(N)]
March = {x:Name.count(x) for x in 'MARCH' if Name.count(x) > 0}

import itertools
ans = 0
for x,y,z in itertools.combinations(March.values(), 3):
    ans += x*y*z
print(ans)

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

int main()
{
    int n;
    cin >> n;
    int s[n];
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }

    int q, k, sum = 0;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        cin >> k;
        if (binary_search(s, s + n, k))
            sum++;
    }
    cout << sum << endl;
}


Measured memory_bytes: 3448
#define _DEBUG
#include "bits/stdc++.h"
#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;
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 dp[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int main(){
	int H,W,K;
	int x0,y0,x1,y1;
	scan(H>>W>>K);
	char c[H+2][W+4];
	int dismin[H+2][W+4];
	fill(dismin[0],dismin[H+2],INF);
	scan(y0>>x0>>y1>>x1);
	rep1(i,H){
		scanf("%s",c[i]+1);
	}
	rep(j,W+2){
		c[0][j]='@';
		c[H+1][j]='@';
	}
	rep(i,H+2){
		c[i][0]='@';
		c[i][W+1]='@';
	}/*
	rep(i,H+2){
		rep(j,W+2){
			printf("%c",c[i][j]);
		}
		kaigyo;
	}*/
	vector<pair<pint,vint > > record;
	vint ve; rep(i,4) ve.push_back(1);
	record.push_back({{y0,x0},ve});
	dismin[y0][x0]=0;
	int count=1;
	while(!record.empty()){
		vector<pair<pint,vint > > before=record;
		record.clear();
		rep(i,before.size()){
			pint to=before[i].first;
			vint ve=before[i].second;
			rep(j,4){
				if(ve[j]==0) continue;
				rep1(k,K){
					int y=to.first+dp[j][1]*k;
					int x=to.second+dp[j][0]*k;
					if(c[y][x]=='@') break;
					if(y==y1&&x==x1){
						prin(count);
						return 0;
					}
					if(count<dismin[y][x]){
						vint ve(4); rep(s,4) ve[s]=1;
						ve[(j+2)%4]=0;
						if(k!=K) ve[j]=0;
						record.push_back({{y,x},ve});
						dismin[y][x]=count;
					}
				}
			}
		}
		count++;/*
		rep(i,H+2){
			rep(j,W+2){
				if(dismin[i][j]==INF) printf("-");
				else printf("%d",dismin[i][j]);
			}
			kaigyo;
		}*/
	}
	prin(-1);
	return 0;
}


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

using namespace std;

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

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

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

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

pii pos[26][2];
int num[26];
string in[510];

int main(void){
	int m,n;
	cin >> m >> n;
	rep(i,m) cin >> in[i];
	rep(i,m)rep(j,n){
		if(in[i][j]=='.')
			continue;
		int cur=in[i][j]-'A';
		pos[cur][num[cur]].first=i;
		pos[cur][num[cur]++].second=j;
	}
	int ans=0;
	rep(loop,26*26)rep(i,26) if(num[i]==2){
		bool ok=false;
		if(pos[i][0].first==pos[i][1].first){
			ok=(pos[i][0].second+1!=pos[i][1].second);
			for(int j=pos[i][0].second+1;j<pos[i][1].second;++j)
				if(in[pos[i][0].first][j]!='.')
					ok=false;
		}else if(pos[i][0].second==pos[i][1].second){
			ok=(pos[i][0].first+1!=pos[i][1].first);
			for(int j=pos[i][0].first+1;j<pos[i][1].first;++j)
				if(in[j][pos[i][0].second]!='.')
					ok=false;
		}else{
			if(in[pos[i][1].first][pos[i][0].second]=='.'){
				ok=true;
				for(int j=min(pos[i][0].first,pos[i][1].first)+1;j<max(pos[i][0].first,pos[i][1].first);++j)
					if(in[j][pos[i][0].second]!='.')
						ok=false;
				for(int j=min(pos[i][0].second,pos[i][1].second)+1;j<max(pos[i][0].second,pos[i][1].second);++j)
					if(in[pos[i][1].first][j]!='.')
						ok=false;
			}
			if(!ok&&in[pos[i][0].first][pos[i][1].second]=='.'){
			ok=true;
			for(int j=min(pos[i][0].first,pos[i][1].first)+1;j<max(pos[i][0].first,pos[i][1].first);++j)
				if(in[j][pos[i][1].second]!='.')
					ok=false;
			for(int j=min(pos[i][0].second,pos[i][1].second)+1;j<max(pos[i][0].second,pos[i][1].second);++j)
				if(in[pos[i][0].first][j]!='.')
					ok=false;
			}
		}

		if(ok){
			in[pos[i][0].first][pos[i][0].second]='.';
			in[pos[i][1].first][pos[i][1].second]='.';
			ans+=2,num[i]=0;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1484
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <queue>
#define rep(i,n) for (int i=0;i<(n);++i)
#define REP(i,n) for (int i=0;i<=(n);++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int INF = 10000000;

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

    int ans = 0;
    if(k <= a) cout << k << endl;
    else if(k <= a + b) cout << a << endl;
    else cout << a - (k - a - b) << endl;
    return 0;
}

Measured memory_bytes: 3636
import java.util.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;

// AOJ 0035
public class Main {

	static Scanner sc = new Scanner(System.in);
	static final double EPS = 1e-10;
	public static void main(String[] args) {
		while (sc.hasNext()) {
			String[] buf = sc.next().split(",");
			Complex[] cs = new Complex[4];
			for (int i = 0; i < 4; i++) 
				cs[i] = new Complex(Double.valueOf(buf[i * 2]), Double.valueOf(buf[i * 2 + 1]));
			if (Complex.isConvex(cs)) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}
}

class Complex {
	static final double EPS = 1e-10;
	
	double re, im;
	
	Complex (double r, double i) {
		re = r; im = i;
	}

	double arg() {
		return Math.atan2(im, re);
	}
	
	double abs2() {
		return re * re + im * im;
	}
	
	double abs() {
		return Math.sqrt(abs2());
	}
	
	double innerProdut(Complex o) {
		return re * o.re + im * o.im;
	}
	
	double crossProduct(Complex o) {
		return re * o.im - im * o.re;
	}
	
	static Complex polar(double theta, double r) {
		return new Complex(r * Math.cos(theta), r * Math.sin(theta));
	}
	
	Complex conj() {
		return new Complex(re, -im);
	}
	
	Complex add(Complex o) {
		return new Complex(re + o.re, im + o.im);
	}

	Complex sub(Complex o) {
		return new Complex(re - o.re, im - o.im);
	}
	
	Complex mul(Complex o) {
		return new Complex(re * o.re - im * o.im, re * o.im + im * o.re);
	}
	
	Complex div(Complex o) {
		return new Complex((re * o.re + im * o.im) / o.abs2(), (im * o.re - re * o.im) / o.abs2());
	}

	static int ccw(Complex a, Complex b, Complex c) {
		b = b.sub(a); c = c.sub(a);
		if (b.crossProduct(c) > 0) 	return +1;	// counter clockwise
		if (b.crossProduct(c) < 0) 	return -1;	// clockwise
		if (b.innerProdut(c) < 0) 	return +2;	// c--a--b on line
		if (b.abs() < c.abs())		return -2;	// a--b--c online
		return 0;
	}
	
	static boolean isConvex(Complex[] cs) {
		int size = cs.length, d = ccw(cs[(size + 0 - 1) % size], cs[0], cs[(0 + 1) % size]);
		for (int i = 1; i < size; i++) {
			
			if (ccw(cs[(size + i - 1) % size], cs[i], cs[(i + 1) % size]) * d < 0) return false;
			
		}
		return true;
	}
}

Measured memory_bytes: 12000
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <tuple>
#include <numeric>
#include <string>
#include <map>

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

  std::set<std::pair<int, int>> s;
  for (intmax_t i = 1; i < n; ++i) {
    if (i != n-i) s.insert(std::minmax(i, n-i));
  }
  printf("%zu\n", s.size());
}


Measured memory_bytes: 25728
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=998244353,MAX=100005,INF=1<<28;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        int N,L,R;cin>>N>>L>>R;
        if(N==0) break;
        vector<int> A(N);
        for(int i=0;i<N;i++) cin>>A[i];
        
        int ans=-1,point=-1;
        
        for(int i=L;i<=R;i++){
            if(ans<=A[i-1]-A[i]){
                ans=A[i-1]-A[i];
                point=i;
            }
        }
        
        cout<<point<<endl;
    }
}



Measured memory_bytes: 3216
#include <stdio.h>
 
int main(int argc, char *argv[])
{
    int X, i, t = 0;
 
    scanf("%d", &X);
 
    for ( i = 1; i <= X; i++ ){
        t += i;
        if ( t >= X ){
            break;
        }
    }
    printf("%d\n", i);
    return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;
 
signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(20);
 
  int k;
  cin >> k;
  k++;

  int sum = 0;
 
  FOR(i, 1, k)FOR(j, 1, k)FOR(l, 1, k){
    sum += gcd(gcd(i, j), l);
  }

  cout << sum << endl;
 
  return 0;
}


Measured memory_bytes: 3652
#include<iostream>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<iomanip>
#include<string>
#include<string.h>
#include<cmath>
using namespace std;
int main()
{
	double a, b;
	cin >> a >> b;
	cout << ceil(a / b);
}


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

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#ifdef MAROON_LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

ll read(){
	ll i;
	scanf("%" SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int Sub(int n,int c,vi x,vi v){
	vi s=v;
	FOR(i,1,n)s[i]+=s[i-1];
	int res=0,cur=0,w=0;
	for(int i=n-1;i>=0;i--){
		chmax(res,s[i]-x[i]+cur);
		w+=v[i];
		chmax(cur,w-(c-x[i])*2);
	}
	return res;
}

signed main(){
	int n=read(),c=read();
	vi x(n),v(n);
	REP(i,n)x[i]=read(),v[i]=read();
	int ans=0;
	REP(_,2){
		chmax(ans,Sub(n,c,x,v));
		for(auto&a:x)
			a=c-a;
		reverse(ALL(x));
		reverse(ALL(v));
	}
	print(ans);
}


Measured memory_bytes: 4176
#include <stdio.h>

int main(void){
    int R;
    scanf("%d",&R);
    if(R<1200){
        printf("ABC\n");
    }
    else if(R<2800){
        printf("ARC\n");
    }
    else{
        printf("AGC\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "}"; return os; }

bool solvable(LL n, LL k, vector<LL>& a, vector<LL>& f, LL m){
    LL needed = 0;
    for(LL i = 0; i < n; ++i){
        needed += max(0LL, a[i] - m / f[i]);
    }
    return needed <= k;
}



int main(){
    LL n, k;
    cin >> n >> k;
    vector<LL> a(n);
    vector<LL> f(n);
    for(LL i = 0; i < n; ++i){
        cin >> a[i];
    }
    for(LL i = 0; i < n; ++i){
        cin >> f[i];
    }
    LL good = 1e+13;
    LL bad = -1;
    sort(a.begin(), a.end(), greater<LL>());
    sort(f.begin(), f.end());
    while(good > bad+1){
        LL middle = (good+bad)/2;
        if(solvable(n, k, a, f, middle)){
            good = middle;
        }else{
            bad = middle;
        }
    }
    cout << good << endl;
    return 0;
}



Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long N, K; cin >> N >> K;
    vector<pair<int, int>> x(N);
    for (int i = 0; i < N; i++)
    {
        cin >> x[i].first >> x[i].second;
    }
    sort(x.begin(), x.end());
    long long p = 0, i = 0, ans;
    while (p < K)
    {
        p += x[i].second;
        ans = x[i].first;
        i++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main()
{
  int i,j,N,A[1000],v,n;
 
  scanf("%d\n",&N);

  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }

  for(i=1;i<=N;i++){
    v = A[i];
    j = i - 1;
    for(n=0;n<N-1;n++){
      printf("%d ",A[n]);
    }
    printf("%d",A[N-1]);
    while(j >= 0 && A[j] > v){
      A[j+1] = A[j];
      j--;
      A[j+1] = v;
    }
  
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 608
#include<stdio.h>
#include<stdlib.h>
int main(){
  int n,i,max=0;
  scanf("%d",&n);
  int a[n+2];
  a[0]=0;
  a[n+1]=0;
  for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
  for(i=0;i<=n;i++)
    max+=abs(a[i+1]-a[i]);
  for(i=1;i<=n;i++)
    printf("%d\n",max-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]));
  return 0;
}


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

#define MAX_N (50)
#define MAX_X (50)
#define MAX_S (MAX_N * MAX_X)

long sum_comb[MAX_N + 1][MAX_N + 1][MAX_S + 1] = {}, ret;

int main(int argc, char *argv[]) {
  // sum_comb[n][k][S] is the number of subarrays of x[0, n)
  // with length k that add up to S.
  // Note that,
  //     sum_comb[n][k][S] = 0 when (n == 0 and !(k == 0 and S == 0) or k > n or S < 0
  //     sum_comb[n][k][S] = 1 when k == 0 and S == 0
  //     sum_comb[n + 1][k][S] = sum_comb[n][k][S]
  //                           + sum_comb[n][k - 1][S - x[i]]
  int x[MAX_N], N, A;
  scanf("%d %d", &N, &A);
  for (int i = 0; i < N; i++)
    scanf("%d", &x[i]);
  for (int n = 0; n <= N; n++)
    sum_comb[n][0][0] = 1;
  for (int n = 1; n <= N; n++) {
    for (int k = 1; k <= n; k++) {
      for (int S = 0; S <= MAX_S; S++) {
        sum_comb[n][k][S] = sum_comb[n - 1][k][S] +
                            (S - x[n - 1] >= 0 ? sum_comb[n - 1][k - 1][S - x[n - 1]] : 0);
      }
    }
  }
  ret = 0;
  for (int k = 1; k <= N; k++)
    ret += sum_comb[N][k][k * A];
  printf("%ld\n", ret);
  
  return 0;
}


Measured memory_bytes: 49024
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        long[] inpt = Reader.ReadLine().Split(' ').Select(a => long.Parse(a)).ToArray();
        int procCount = (int)inpt[0];
        long targetIdx = inpt[1] - 1;

        Dictionary<int, long> dic = new Dictionary<int, long>();
        for (int i = 0; i < procCount; i++)
        {
            inpt = Reader.ReadLine().Split(' ').Select(a => long.Parse(a)).ToArray();
            int num = (int)inpt[0];
            long val = inpt[1];
            if (!dic.ContainsKey(num))
            {
                dic.Add(num, val);
            }
            else
            {
                dic[num] += val;
            }
        }

        int ans = 0;
        long curIdx = 0;

        int[] keys = dic.Keys.OrderBy(a => a).ToArray();
        for(int i=0; i<keys.Length; i++) {
            if(targetIdx >= curIdx && targetIdx < curIdx+dic[keys[i]]) {
                ans = keys[i];
                break;
            }
            curIdx+=dic[keys[i]];
        }
        Console.WriteLine(ans);

    
    }




    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"

10 500000
1 100000
1 100000
1 100000
1 100000
1 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000

";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}

Measured memory_bytes: 20664
n, k = map(int, input().split())

C = [[0]*(2*k) for _ in range(2*k)]

for i in range(n):
    x, y, c = map(str, input().split())
    x, y = int(x), int(y)
    if c == 'W':
        y += k
    C[y%(2*k)][x%(2*k)] += 1

#print(C)
s = [[0]*(2*k+1) for _ in range(2*k+1)]
for i in range(2*k):
    for j in range(2*k):
        s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + C[i][j]

#print(s)

def count(x1, x2, y1, y2):
    return s[y2][x2]-s[y1][x2]-s[y2][x1]+s[y1][x1]

ans = 0
for i in range(k):
    for j in range(k):
        temp = 0
        temp += count(0, j, 0, i)
        temp += count(j, j+k, i, i+k)
        temp += count(0, j, i+k, 2*k)
        temp += count(j+k, 2*k, 0, i)
        temp += count(j+k, 2*k, i+k, 2*k)
        ans = max(ans, max(temp, n-temp))
print(ans)


Measured memory_bytes: 137824
#include<bits/stdc++.h>
using namespace std;
 
 
int main(){
	long long n;
  	cin >> n;
    
  	for (long long i=sqrt(n);i>=1;i--){

      if (n%i==0){
        long long p=n/i;
       cout <<i+ p-2<<endl;
        break;
      }
    }
  
  	
 
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <tuple>
#include <map>

using namespace std;

const string button = "22233344455566677778889999";
int ctob[256];

bool check(string &s, string &t, int idx){
	if (idx + s.size() > t.size()) return false;
	for (int i = 0; i < s.size(); ++i){
		if (ctob[s[i]] != t[i + idx]) return false;
	}
	return true;
}

vector<string> v;
vector<vector<pair<int, int>>> G;
int ans[500];
int len;

void dfs(int idx, int n){
	if (idx == len){
		for (int i = 0; i < n; ++i){
			cout << v[ans[i]] << (i == n - 1 ? ".\n" : " ");
		}
		return;
	}
	for (auto e : G[idx]){
		ans[n] = e.first;
		dfs(idx + e.second, n + 1);
	}
}

int main(){
	for (int i = 0; i < button.size(); ++i){
		ctob['a' + i] = button[i];
	}

	int n;
	while (cin >> n, n){
		v.clear(), v.resize(n);
		for (int i = 0; i < n; ++i) cin >> v[i];
		string t;
		cin >> t;
		len = t.size();
		G.clear(), G.resize(len);
		for (int i = 0; i < len; ++i){
			for (int j = 0; j < n; ++j){
				if (check(v[j], t, i)) G[i].push_back(make_pair(j, v[j].size()));
			}
		}
		dfs(0, 0);
		cout << "--\n";
	}


	return 0;
}

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



int main() {
  
  int N;
  cin>> N;
  vector<int> h(N);
  for (int i=0; i<N; i++){
    cin >> h.at(i);
  }
  
 
  vector<int> cost(N);
  cost.at(0)=0;
  cost.at(1)=abs(h.at(1)-h.at(0));
  for (int i=2;i<N;i++){
  	cost.at(i)=min(cost.at(i-1)+abs(h.at(i-1)-h.at(i)),cost.at(i-2)+abs(h.at(i-2)-h.at(i)));
  }
  cout << cost.at(N-1) << endl;

  
}

Measured memory_bytes: 1024
#include <iostream>

int main() {
    int n, m, c;
    std::cin >> n >> m >> c;
    
    int b[m];
    for (int i = 0; i < m; i++) {
        std::cin >> b[i];
    }
   
    int count = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
      sum = 0;
        for (int j = 0; j < m; j++) {
            int a;
            std::cin >> a;
            sum += a * b[j];
        }
        if (sum + c > 0) {
            count++;
        }
    }
    
    std::cout << count << std::endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i, s, t) for(i = s; i <= t; ++i)
#define dep(i, s, t) for(i = s; i >= t; --i)

using namespace std;

typedef long long LL;
const int P = 1e9 + 7;
const int N = 18, S = 1 << N;
int n, m; LL ans;
int a[N];
LL fac[S], inv[S];
LL f[N][S];

LL lp(LL a, LL b) {
	LL ret = 1;
	for(; b; b >>= 1, a = a * a % P)
		if(b & 1) ret = ret * a % P;
	return ret;
}

LL A(int a, int b) {
	return fac[a] * inv[a-b] % P;
}

int main() {
	int i, j, S, ful, have, need; bool fu;
	scanf("%d%d", &n, &m); ful = 1 << n;
	rep(i, 1, m) scanf("%d", &a[m+1-i]);
	fac[0] = 1;
	rep(i, 1, ful) fac[i] = fac[i-1] * i % P;
	inv[ful] = lp(fac[ful], P-2);
	dep(i, ful, 1) inv[i-1] = inv[i] * i % P;
	
	f[0][0] = 1;
	rep(i, 0, m-1) {
		rep(S, 0, ful-1)
		if(f[i][S]) {
			f[i+1][S] = (f[i+1][S] + f[i][S]) % P;
			rep(j, 0, n-1)
			if(!(S>>j&1)) {
				have = ful-a[i+1]-S;
				need = (1<<j)-1;
				if(have < need) continue;
				f[i+1][S|(1<<j)] = (f[i+1][S|(1<<j)] + f[i][S] * (need+1) % P * A(have, need) % P) % P;	
//				printf("%d %d %lld\n", S, j, f[i+1][S|(1<<j)]);		
			}
		}
//		rep(S, 0, ful-1) printf("%d %lld\n", S, f[i+1][S]);
//		puts("");
	}
	rep(S, 0, ful-1) {
//		printf("%d %lld\n", S, f[m][S]);
		f[m][S] = f[m][S] * fac[ful-1-S] % P;
		fu = 1;
		rep(i, 0, n-1)
			if(S & (1<<i)) fu ^= 1;
		if(fu) ans = (ans + f[m][S]) % P;
		else ans = (ans - f[m][S] + P) % P;
	}
	ans = ans * ful % P;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 36992
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
const ll mod=998244353;
ll n,ri,le,s0,f[1000005];
struct node{
	int x,y;
	/*bool operator<(node b)const{
		return x-y>b.x-b.y;
	}*/
}a[1000005];
int tot;
char s[1000005];
int cmp(node a,node b){
	return a.x-a.y>b.x-b.y;
}
int main(){
	//n=read();
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		ll l=0,r=0;
		scanf("%s",s+1);
		for(int j=1;s[j];j++)
			if(s[j]=='(')l++;
			else if(s[j]==')'){
				if(l)l--;
				else r++;
			}
		if(!l&&r)ri+=r;
		else if(l&&!r)le+=l;
		else if(l&&r)a[++tot]=(node){l,r};	
		//s0+=l-r;
	}
	//if(s0!=0)return puts("No"),0;
	sort(a+1,a+1+tot,cmp);
	for(int i=1;i<=tot;i++){
		if(le<a[i].y)
			return puts("No"),0;
		le-=a[i].y-a[i].x;
	}
	if(le!=ri)puts("No");
	else puts("Yes");
	return 0;
}

Measured memory_bytes: 5376
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

const int mmod = 1000000007;

int main()
{
  int n;
  cin >> n;
  vector<string> str(n);
  for (int i=0; i<n; i++)
    cin >> str[i];

  int non_empty = 0; int all = 0;
  for (int i=0; i<n; i++) {
    int cnt = 0;
    for (int j=0; j<n; j++)
      if (str[j][i] == '#') { non_empty ++; cnt ++; }
    if (cnt == n) all ++;
  }
  if (!non_empty) {
    printf("-1\n");
    return 0;
  }

  int res = 9999;
  for (int i=0; i<n; i++) {
    int now = n - all;
    for (int j=0; j<n; j++)
      if (str[i][j] == '.') now ++;
    now ++;
    for (int j=0; j<n; j++)
      if (str[j][i] == '#') { now --; break; }
    res = min(res, now);
  }

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


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define vll vector<int>
#define pii pair<int,int>
#define pb push_back
#define sz(v) (int)(v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=a;i<b;++i)
using namespace std;

#define M 100010


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   	
   	int n;cin>>n;
   	int x[n],y[n];
   	vll a,b;
   	rep(i,0,n)cin>>x[i]>>y[i],a.pb(x[i]+y[i]),b.pb(x[i]-y[i]);
   	sort(all(a));
   	sort(all(b));
   	cout<<max(a[n-1]-a[0],b[n-1]-b[0]);
   	
   	
    return 0;
}

Measured memory_bytes: 9808
#include<cstdio>
#include<vector>
using namespace std;
int n;
int a,b;
vector<int>g[100001];
bool f[100001];
bool dfs(int x,int fa)
{
	f[x]=1;
	int cnt=0;
	for(int i=0;i<g[x].size();i++)
	{
		if(g[x][i]==fa)continue;
		if(dfs(g[x][i],x))return 1;
		if(f[g[x][i]])
		{
			cnt++;
			f[x]=0;
			if(cnt==2)return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&a,&b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	if(dfs(1,0)||f[1])printf("First");
	else printf("Second");
}

Measured memory_bytes: 5888