akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

const int mod = 1000000007;

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  pair<int, int> ma = make_pair(INT_MIN, 0);
  pair<int, int> mi = make_pair(INT_MAX, 0);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    if (a[i] > ma.first)
      ma = make_pair(a[i], i + 1);
    if (a[i] < mi.first)
      mi = make_pair(a[i], i + 1);
  }
  vector<pair<int, int>> x;
  if (ma.first + mi.first < 0) {
    for (int i = 0; i < N; i++) {
      if (a[i] > 0) {
        a[i] += mi.first;
        x.push_back(make_pair(mi.second, i + 1));
      }
    }
    for (int i = N - 1; i > 0; i--) {
      if (a[i] < a[i - 1]) {
        a[i - 1] += a[i];
        x.push_back(make_pair(i + 1, i));
      }
    }
  } else {
    for (int i = 0; i < N; i++) {
      if (a[i] < 0) {
        a[i] += ma.first;
        x.push_back(make_pair(ma.second, i + 1));
      }
    }
    for (int i = 0; i < N - 1; i++) {
      if (a[i] > a[i + 1]) {
        a[i + 1] += a[i];
        x.push_back(make_pair(i + 1, i + 2));
      }
    }
  }
  cout << x.size() << endl;
  for (int i = 0; i < x.size(); i++) {
    cout << x[i].first << ' ' << x[i].second << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

double startTime;
double getCurrentTime() {
	return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}


ll MOD;
ll add(ll x, ll y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
ll sub(ll x, ll y) {
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
ll mult(ll x, ll y) {
	return (x * y) % MOD;
}
ll bin_pow(ll x, ll p) {
	if (p == 0) return 1;
	if (p & 1) return mult(x, bin_pow(x, p - 1));
	return bin_pow(mult(x, x), p / 2);
}
ll rev(ll x) {
	return bin_pow(x, MOD - 2);
}

const int N = 6006;
ll dp[N][N / 3];

int main()
{
	startTime = (double)clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	int n;
	scanf("%d%lld", &n, &MOD);
	dp[3 * n][0] = 1;
	for (int s = 3 * n; s > 0; s--)
		for (int k = 0; k <= n; k++) {
			if (s >= 1)
				dp[s - 1][k] = add(dp[s - 1][k], dp[s][k]);
			if (s >= 2 && k < n)
				dp[s - 2][k + 1] = add(dp[s - 2][k + 1], mult(dp[s][k], s - 1));
			if (s >= 3 && k < n)
				dp[s - 3][k + 1] = add(dp[s - 3][k + 1], mult(dp[s][k], mult(s - 1, s - 2)));
		}
	ll ans = 0;
	for (int k = 0; k <= n; k++)
		ans = add(ans, dp[0][k]);
	printf("%lld\n", ans);

	return 0;
}


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

using namespace std;

struct edge{
	int a, b, c;
	edge(int x, int y, int z){
		a = x, b = y, c = z;
	}
	bool operator<(edge ope){
		return c < ope.c;
	}
};

int N, M;
int h[205];
bool used[205];
vector<edge> E, E2;
vector<int> vec_h;

int parent[205];
void init(){
	for(int i = 1; i <= N; i++) parent[i] = i;
}
int root(int i){
	if(parent[i] == i) return i;
	return parent[i] = root(parent[i]);
}
bool same(int i, int j){
	return root(i) == root(j);
}
void unite(int i, int j)
{
	int root_i = root(i), root_j = root(j);
	if(root_i == root_j) return;
	parent[root_i] = root_j;
}

bool check(int day)
{
	init();
	for(int i = 0; i < E.size(); i++){
		if(h[E[i].a] <= day || h[E[i].b] <= day) continue;
		unite(E[i].a, E[i].b);
	}
	
	int cnt[205], remain_cnt = 0;
	for(int i = 1; i <= N; i++) cnt[i] = 0;
	for(int i = 1; i <= N; i++){
		if(h[i] > day){
			cnt[root(i)]++;
			remain_cnt++;
		}
	}
	int comp_num = 0;
	for(int i = 1; i <= N; i++){
		if(cnt[i]) comp_num++;
	}
	if(remain_cnt <= 1) return false;
	if(comp_num >= 2) return false;
	return true;
}


int main(void)
{
	while(1){
		cin >> N >> M;
		if(N == 0 && M == 0) break;
		
		vec_h.clear();
		for(int i = 1; i <= N; i++){
			cin >> h[i];
			vec_h.push_back(h[i]);
		}
		vec_h.push_back(0);
		sort(vec_h.begin(), vec_h.end());
			
		int a, b, c;
		E.clear();
		for(int i = 0; i < M; i++){
			cin >> a >> b >> c;
			E.push_back( edge(a, b, c) );
		}
		sort(E.begin(), E.end());
		
		int day_i;
		for(int i = 0; i < vec_h.size(); i++){
			if(!check(vec_h[i])){
				day_i = i;
				break;
			}
		}
		if(day_i == 0){
			cout << 0 << endl;
			continue;
		}
		
		
		init();
		int ans = 0;
		for(int t = day_i; t >= 0; t--){
			E2.clear();
			for(int i = 0; i < E.size(); i++){
				if(h[E[i].a] < vec_h[t] || h[E[i].b] < vec_h[t]){
					E2.push_back(E[i]);
					continue;
				}
				if(!same(E[i].a, E[i].b)){
					ans += E[i].c;
					unite(E[i].a, E[i].b);
				}else{
					E2.push_back(E[i]);
				}
			}
			E = E2;
		}
		
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3680
word = str(input())
wlist = []
for i in word:
    wlist.append(i)
n = int(input())
for i in range(n):
    com = list(input().split())
    a = int(com[1])
    b = int(com[2])
    if (com[0] == 'print'):
        for k in range(a, b + 1):
            print(wlist[k], end ='')
        print()
    elif (com[0] == 'reverse'):
        decoy = []
        for k in range(a, b+1):
            decoy.append(wlist[b+a-k])
        for l in range(b-a+1):
            wlist[a+l] = decoy[l]
    elif (com[0] == 'replace'):
        p = str(com[3])
        plist = []
        for k in p:
            plist.append(k)
        for l in range(b-a+1):
            wlist[a+l] = plist[l]
            


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

long long dp[105][100005],vi;

int main() {
	int n, w,wi;
	cin>>n>>w;;
	for(int i=0; i<w;i++) dp[0][i]=0;
	for (int i=1 ; i<=n; i++){
		cin>>wi>>vi;
		for (int p=0; p<=w; p++){
			if (wi<=p) dp[i][p] = max(dp[i-1][p], vi+dp[i-1][p-wi]);
			else dp[i][p]=dp[i-1][p];
			
		}
	}
	cout<<dp[n][w];
	
	return 0;
}

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
//typedef long long ll;
typedef long long ll;
//typedef pair<int, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e15;
const ll MINF = -10e10;
//const int INF = INT_MAX / 100;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)


//ifstream myfile("~/Downloads/02.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;
const int mod = 1000000007;
const double PI = 3.14159265358979323846;

typedef pair<ll, ll> P;

void print_line(vector<vector<int>> &ans) {
    for (int i = 0; i < ans.size(); i++) {
        for (int y = 0; y < ans[i].size(); y++) {
            cout << ans[i][y];
        }
        cout << endl;
    }
}

int main() {
    ll x;
    cin >> x;

    ll ans = x / 11 * 2;
    ll diff = x % 11;
    if (diff == 0) {
        cout << ans << endl;
        return 0;
    }

    if (7 <= diff && diff <= 10) {
        cout << ans + 2 << endl;
        return 0;
    }

    cout << ans + 1 << endl;


}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int N,X = 0,A[100010],pow[32] = {1};
int main(){
	cin >> N;
	for(int i=1;i<32;i++) pow[i] = pow[i-1]*2;
	for(int i=0;i<N;i++){
		cin >> A[i];
		X = (X xor A[i]);
	}
	int ans = 0;
	for(int i=31;i>=1;i--){
		if(!(X&(1<<(i-1)))) continue;
		for(int j=0;j<N;j++){
			if(pow[i]-1==(A[j] xor (A[j]-1))){
				X = (X xor A[j] xor (A[j]-1));
				ans++;
				break;
			}
		}
	}
	cout << (X==0? ans:-1) << endl;
}

Measured memory_bytes: 640
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;
const int INF= 1e9+5;
typedef long long ll;

int main(){
  int n;
  cin>>n;
  vector<int>p(n);
  vector<int>a;
  vector<int>b;
  for(int i=0;i<n;i++)cin>>p[i];
  vector<int>copy=p;
  sort(copy.begin(),copy.end());
  int count=0;
  if(copy==p){
    cout<<"YES"<<endl;
    return 0;
  }
  for(int i=0;i<n;i++){
    if(copy[i] !=  p[i]){
      count++;
      a.push_back(copy[i]);
      b.push_back(copy[i]);
    }
  }
  if(count !=2){
    cout<<"NO"<<endl;
    return 0;
  }
  sort(a.begin(),a.end());
  if(a==b)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

  
  

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <array>

using namespace std;

#define forange(counter, end) forstep(counter, 0, end)
#define forstep(counter, begin, end) forstep_type(size_t, counter, begin, end)
#define forange_type(type, counter, end) forstep_type(type, counter, 0, end)
#define forstep_type(type, counter, begin, end) for (type counter = begin, forstep_type_end_##counter = end; counter < forstep_type_end_##counter; counter++)

const int D = 365;
const int C = 26;

array<int, C> contest;
array<array<int, C>, D> satisfaction;

int decr(const int c, const int last, const int now) {
	return contest[c] * (now - last);
}

int getScore(const array<short, C>& last, const int open, const int day) {

	int score = 0;

	forange_type(int, c, C)
	{
		if (c == open)
		{
			score += satisfaction[day][c];
		}
		else
		{
			score -= decr(c, last[c], day);
		}
	}

	return score;
}

int getScore(const array<char, D>& cont) {

	int score = 0;
	array<short, C> last;
	last.fill(-1);

	forange_type(short, d, D)
	{
		score += getScore(last, cont[d], d);
		last[cont[d]] = d;
	}

	return 1000000 + score;
}

struct Data {
	Data() {
		last.fill(-1);
		c.fill(0);
	}

	array<short, C> last;
	array<char, D> c;
	int score = 0;

	bool operator<(const Data& o) const {
		return score < o.score;
	}
};

array<char, D> think() {

	priority_queue<Data> qData;
	qData.push(Data());

	const int BeamWidth = 600;

	forange_type(int, d, D)
	{
		decltype(qData) next;
		forange(w, BeamWidth)
		{
			if (qData.empty()) break;

			const auto top = qData.top();
			qData.pop();

			forange_type(char, c, C)
			{
				Data nextData = top;
				const int score = getScore(nextData.last, c, d);

				nextData.last[c] = d;
				nextData.c[d] = c;
				nextData.score += score;

				next.push(nextData);
			}

		}

		qData.swap(next);
	}

	const auto& top = qData.top();

	cerr << "score:" << getScore(top.c) << endl;

	return top.c;
}

int main() {

	int d;
	cin >> d;

	for (auto& c : contest)
	{
		cin >> c;
	}

	forange(d, D)
	{
		forange(s, C)
		{
			cin >> satisfaction[d][s];
		}
	}

	const auto ans = think();

	for (const auto& a : ans)
	{
		cout << (int)(a + 1) << endl;
	}

	return 0;
}


Measured memory_bytes: 23012
w = int(input())
n = int(input())
vertical = [x for x in range(1, w + 1)]

for i in range(n):
    a, b = [int(x) - 1 for x in input().split(',')]
    vertical[a], vertical[b] = vertical[b], vertical[a]

for i in vertical:
    print(i)

Measured memory_bytes: 7648
import std.stdio, std.string, std.range, std.conv, std.array, std.algorithm, std.math, std.typecons;

void main() {
    auto N = readln.chomp.to!long;
    alias Point = Tuple!(long, long);
    Point[] pointList;
    foreach (i; 0..N) {
        auto tmp = readln.split.to!(long[]);
        auto x = tmp[0], y = tmp[1];
        pointList ~= Point(x,y);
    }

    if (!pointList.map!(p => abs(p[0] + p[1]) % 2).all!(a => abs(pointList[0][0] + pointList[0][1]) % 2 == a)) {
        writeln(-1);
        return;
    }
    bool odd = abs(pointList[0][0] + pointList[0][1]) % 2 == 1;

    enum M = 31;
    writeln(M + !odd);

    if (!odd) write("1 ");
    M.iota.map!(i => (2^^i).to!string).join(" ").writeln;

    foreach (i; 0..N) {
        const p = pointList[i];
        auto u = (p[0] + p[1] + 2^^M-1 - (odd ? 0 : 1)) / 2;
        auto v = (p[0] - p[1] + 2^^M-1 - (odd ? 0 : 1)) / 2;
        if (!odd) write("R");
        foreach (j; 0..M) {
            if (u&1) {
                if (v&1) {
                    write("R");
                } else {
                    write("U");
                }
            } else {
                if (v&1) {
                    write("D");
                } else {
                    write("L");
                }
            }
            u >>>= 1;
            v >>>= 1;
        }
        writeln;
    }
}



Measured memory_bytes: 508
// Problem name: Single Source Shortest Path I
// Written by: by_sknight
// Date: 2019/4/27
#include <bits/stdc++.h>
using namespace std;
#define MAX 100
#define INFTY INT_MAX

int n, G[MAX][MAX];

int s3p(int x) {
    int color[MAX], d[MAX];
    for (int i = 0; i < n; i++) {
        color[i] = 0;
        d[i] = INFTY;
    }
    d[0] = 0;
    while (1) {
        int u = -1, minv = INFTY;
        for (int i = 0; i < n; i++) {
            if (color[i] != 1 && d[i] < minv) {
                minv = d[i];
                u = i;
            }
        }
        if (u == x)
            return minv;
        color[u] = 1;
        for (int v = 0; v < n; v++) {
            if (color[v] != 1 && G[u][v] != INFTY) {
                if (d[u] + G[u][v] < d[v])
                    d[v] = d[u] + G[u][v];
            }
        }
    }
}

int main(void) {
    int k, v, c;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            G[i][j] = INFTY;
        }
    }
    for (int i = 0; i < n; i++) {
        cin >> k >> k;
        while (k--) {
            cin >> v >> c;
            G[i][v] = c;
        }
    }

    for (int i = 0; i < n; i++) {
        cout << i << " " << s3p(i) << endl;
    }
}


Measured memory_bytes: 3116
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {

	public static void main(String[] args) throws IOException {
		// TODO 自動生成されたメソッド・スタブ
		int x;
		String str;
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		str = br.readLine();
		x = Integer.parseInt(str);
		System.out.println(x * x * x);
	}
}



Measured memory_bytes: 24172
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	private static final long MOD = 1000000007;

	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int x = in.nextInt();
		int y = in.nextInt();
		int r = solve(x, y);
		System.out.println(r);
		in.close();
	}

	private static int solve(int x, int y) {
		int r = 0;
		switch (x) {
		case 1:
			r += 300000;
			break;
		case 2:
			r += 200000;
			break;
		case 3:
			r += 100000;
		}
		switch (y) {
		case 1:
			r += 300000;
			break;
		case 2:
			r += 200000;
			break;
		case 3:
			r += 100000;
		}
		if (x == 1 && y == 1)
			r += 400000;
		return r;
	}
}

Measured memory_bytes: 23124
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    ll H, W, M;
    cin >> H >> W >> M;
    vector<ll> ob_r(H, 0), ob_c(W, 0);
    map<Pll, ll> p;

    rep(0, i, M)
    {
        ll h, w;
        cin >> h >> w;
        h--;
        w--;
        p[make_pair(h, w)]++;
        ob_r.at(h)++;
        ob_c.at(w)++;
    }

    ll max_r = 0, max_c = 0;
    rep(0, i, H)
    {
        max_r = max(max_r, ob_r.at(i));
    }
    rep(0, i, W)
    {
        max_c = max(max_c, ob_c.at(i));
    }

    vector<ll> r_i, c_i;
    rep(0, i, H)
    {
        if (max_r == ob_r.at(i))
        {
            r_i.push_back(i);
        }
    }
    rep(0, i, W)
    {
        if (max_c == ob_c.at(i))
        {
            c_i.push_back(i);
        }
    }

    ll ans = max_r + max_c;

    for (auto r : r_i)
    {
        for (auto c : c_i)
        {
            if (p[make_pair(r, c)] == 0)
            {
                cout << ans << endl;
                return 0;
            }
        }
    }

    cout << ans - 1 << endl;
}

Measured memory_bytes: 35060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int INF = 1000000000;
const long INF64 = 1000000000000000ll;
const int MOD = 1000000007;
int main(){
	std::vector<string> s(3);
	std::vector<int> a(3,0),g(3);
	rep(i,3){
		std::cin >> s[i];
		g[i]=s[i].size();
		
	}
	int dum=0;
	for (; ;) {
		
		
		//rep(i,3)std::cout << a[i] <<' ';
		//std::cout  << std::endl;
		if(a[dum]==g[dum]){
			if(dum==0)std::cout << "A" << std::endl;
			if(dum==1)std::cout << "B" << std::endl;
			if(dum==2)std::cout << "C" << std::endl;
			exit(0);
		}
		else if(s[dum].at(a[dum])=='a'){
	//		if(a[dum]==g[dum]){std::cout << "A" << std::endl;exit(0);}
			a[dum]++;dum=0;
			
		}
		else if(s[dum].at(a[dum])=='b'){
	//		if(a[dum]==g[dum]){std::cout << "B" << std::endl;exit(0);}
			a[dum]++;dum=1;
		}
		else if(s[dum].at(a[dum])=='c'){
	//		if(a[dum]==g[dum]){std::cout << "C" << std::endl;exit(0);}
			a[dum]++;dum=2;
		}
		
	//	std::cout << dum << std::endl;
		
		
		
		/* code */
	}
	
}

Measured memory_bytes: 256
// 問題の URL を書いておく
// 

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <numeric>
using namespace std;

//#define ENABLE_PRINT

template<typename T>
T Input()
{
    T v;
    cin >> v;
    return v;
}

template<typename T>
vector<T> InputVector(int n)
{
    vector<T> v(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
    return v;
}

template<typename T>
void InputArray(T* begin, int n)
{
    for(int i = 0; i < n; ++i)
    {
        cin >> begin[i];
    }
}

#if defined(ENABLE_PRINT)

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)

#else

#define Print(v) ((void)0)
#define PrintVec(v) ((void)0)

#endif

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

int main(int, const char**)
{
    int s, w;
    cin >> s >> w;
    cout << (w >= s ? "unsafe" : "safe") << endl;
    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPD(i,n) for(int i=(n)-1;i>=0;--i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define TLE() cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms.\n";
const ll MOD = 1E9+7;
const ll IINF = 1E18;
const int INF = 1e9;
const double EPS = 1E-9;
const double PI = atan(1.0) * 4.0;
template<class T> T getbit(T s, int i) {return s>>i&1;}
template<class T> void flipbit(T& s, int i) {s^=(1LL<<i);}
constexpr int cntbit(ll x) {return __builtin_popcountll(x);}
constexpr int lg2(ll x) {return __lg(x);} // return int(log2(x))
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
ll fpow(ll a,ll p){ll res=1LL;while(p){if(p&1LL) res=res*a%MOD;a=a*a%MOD;p>>=1LL;} return res;}

const int N=105;
const int MX=1e9;
int n,k;
ll small[N][32000],big[N][32000];

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k;
	if(n==1) exit(puts("1")*0);
	int base=sqrt(n)+1;
	small[0][1]=1;
	REP(i,k){
		FOR(j,1,base-1) (small[i][j]+=small[i][j-1])%=MOD;
		FORD(j,base-2,1) (big[i][j]+=big[i][j+1])%=MOD;
		FOR(j,1,base-1){
			if(n/j==j) continue;
			big[i+1][j]=small[i][j]*(n/j-n/(j+1))%MOD;
		}
		FOR(j,1,base-1) small[i+1][j]=(big[i][j]+small[i][base-1])%MOD;
	}	
	ll res=0;
	REP(i,base) (res+=small[k][i]+big[k][i])%=MOD;
	cout<<res<<'\n';
}



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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define IMP cout << "IMPOSSIBLE" << endl
#define Imp cout << "Impossible" << endl
#define imp cout << "impossible" << endl
#define M1 cout << "-1" << endl
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    os << "{";
    rep(i, v.size()) os << v[i] << (i == (int)v.size() - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &p)
{
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}
template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }
struct in
{
    const size_t n = 0;
    in() = default;
    in(size_t n) : n(n){};
    template <typename T>
    operator T()
    {
        T ret;
        cin >> ret;
        return ret;
    }
    template <typename T>
    operator vector<T>()
    {
        assert(n != 0);
        vector<T> ret(n);
        for (auto &x : ret)
            cin >> x;
        return ret;
    }
};

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using vpint = vector<pint>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

void Main()
{
    ll n, k;
    cin >> n >> k;
    ll tmp = 1;
    rep(i, 100000)
    {
        tmp *= k;
        if (tmp > n)
        {
            cout << i + 1 << endl;
            return;
        }
    }
}

signed main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
from __future__ import print_function

import sys

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd
# fractions.gcd() を用いること
# math.log2()はatcoderでは対応していない．留意せよ．

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def lcm(n, m):
    return int(n * m / gcd(n, m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    n = int(input().strip())
    S = input().strip()
    x=0
    ans=0
    for i in range(n):
        if S[i]=='I':
            x+=1
            ans = max(x,ans)
        else:
            x-=1
    print(ans)


if __name__ == '__main__':
    main()

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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

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

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

//最小公倍数
int lcm(int number1,int number2){
	return number1 * number2 / gcd(number1,number2);	
}

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

  S[K - 1] = S[K - 1] - ('A' - 'a');

  print(S);

}

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

int main() {
	string str;
	getline(cin, str);
	//cin >> str;
	
	for (int i=0; i<str.length(); i++) {
	    char c = str[i];
	    if ('A' <= c && c <= 'Z') {
	        //str[i] = tolower(c);
	        cout << (char)tolower(c);
	    } else if ('a' <= c && c <= 'z') {
	        //str[i] = toupper(c);
	        cout << (char)toupper(c);
	    } else {
	        cout << str[i];
	    }
	}
	
	cout << endl;
	
	return 0;
}

Measured memory_bytes: 3076
from bisect import bisect_left


def calc(N, A, cumsum, x):
    num = N ** 2
    total = cumsum[N] * N * 2
    for a in A:
        idx = bisect_left(A, x - a)
        num -= idx
        total -= cumsum[idx] + idx * a
    return num, total


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    cumsum = [0] * (N+1)
    for i in range(N):
        cumsum[i+1] = cumsum[i] + A[i]
    lo = 0
    hi = int(2e5+1)
    while lo < hi:
        mid = (lo + hi) // 2
        num, total = calc(N, A, cumsum, mid)
        if num <= M:
            hi = mid
        else:
            lo = mid + 1
    num, total = calc(N, A, cumsum, lo)
    ans = total - (num - M) * (lo - 1)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 54476
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
/////////////////////////////////
int main()
{
    string s;
    cin >> s;
    int n = s.length();
    vector<pair<char, int>> v(n);
    int cntL = 0, cntR = 0;
    rep(i, n)
    {
        if (s[i] == 'L')
        {
            cntL++;
            v[i] = make_pair('L', cntL);
        }
        else
            cntL = 0;
    }
    for (int i = n - 1; i >= 0; i--)
    {
        if (s[i] == 'R')
        {
            cntR++;
            v[i] = make_pair('R', cntR);
        }
        else
            cntR = 0;
    }
    vector<int> ans(n, 0);
    rep(i, n)
    {
        if (v[i].first == 'R')
        {
            if (v[i].second % 2 == 0)
            {
                ans[i + v[i].second]++;
            }
            else
            {
                ans[i + v[i].second - 1]++;
            }
        }

        else
        {
            if (v[i].second % 2 == 0)
            {
                ans[i - v[i].second]++;
            }
            else
            {
                ans[i - v[i].second + 1]++;
            }
        }
    }
    rep(i, n)
    {
        cout << ans[i];
        if (i != n - 1)
            cout << " ";
        else
            cout << endl;
    }
}

Measured memory_bytes: 4580
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val m = sc.nextInt()
    val d = Array(m) { 0 }
    val c = Array(m) { 0L }
    for (i in 0 until m) {
        d[i] = sc.nextInt()
        c[i] = sc.nextLong()
    }
    var digits = 0L
    var sum = 0L
    for (i in 0 until m) {
        digits += c[i]
        sum += d[i] * c[i]
    }
    println(digits + (sum - 1) / 9 - 1)
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


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

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)

int main(int argc, char *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, ret1 = 0, ret2 = 0;
    float sum = 0.0;
    cin >> n;

    vector<int> k(n);

    REP(i, n)
    {
        cin >> k[i];
        sum += k[i];
    }

    int ave1 = (int)ceil(sum / n);
    int ave2 = (int)floor(sum / n);

    REP(i, n)
    {
        ret1 += (ave1 - k[i]) * (ave1 - k[i]);
        ret2 += (ave2 - k[i]) * (ave2 - k[i]);
    }

    cout << min(ret1, ret2) << endl;

    return 0;
}


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

int main()
{
	int N;
	int a=0,b=0;
	int tmp;
	
	cin >> N;
	for(int i=0;i<N;i++)
	{
		cin >> tmp;
		if(tmp%4==0)a++;
		if(tmp%2==0)b++;
	}
	b-=a;
	if(N%2==1)N--;
	if(2*a+b>=N)cout << "Yes";
	else cout << "No";
	cout << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<x<<endl
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
const ll LINF = LLONG_MAX;
const int INF = INT_MAX;
const double PI=acos(-1);
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; }

int main(){
	ll n; cin>>n;
	vector<ll> a(n);
	rep(i,0,n) cin>>a[i];
	ll ans=0;
	vector<ll> m(n,0);
	ll x=0;
	rep(i,0,n){
		m[i]=max(x,a[i]);
		x=max(x,a[i]);
	}
	rep(i,0,n){
		ans+=(m[i]-a[i]);
	}
	cout<<ans<<endl;
}


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

int main(){
 string s;
 cin>>s;
 int g=s.size();
 for(int i=0;i<s.size();i++){
	 cout<<s[g-i-1];	 
	 }
 cout<<endl;
 return 0;
 }



Measured memory_bytes: 3132
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

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

    int n, m, k[11], s[11][11], p[11];

    cin >> n >> m;
    REP(i, m)
    {
        cin >> k[i];
        REP(j, k[i])
        cin >> s[i][j];
    }
    REP(i, m)
    cin >> p[i];

    int res;

    for (int i = 0; i < (1 << n); i++)
    {
        int sn[11];
        memset(sn, 0, sizeof(sn));
        REP(j, n)
        {
            if (!(i & (1 << j)))
                continue;
            REP(l, m)
            {
                bool has = false;
                REP(o, k[l])
                {
                    if (s[l][o] == j + 1)
                        has = true;
                }

                sn[l] += has;
            }
        }

        bool ok = true;
        REP(j, m)
        {
            if (sn[j] % 2 != p[j] % 2)
                ok = false;
        }

        res += ok;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int main()
{
    int L;
    cin >> L;
    L--;

    if (L == 1) {
        cout << 2 << " " << 2 << endl;
        cout << 1 << " " << 2 << " " << 0 << endl
             << 1 << " " << 2 << " " << 1 << endl;
        return 0;
    }

    int d = L;
    d |= d >> 1;
    d |= d >> 2;
    d |= d >> 4;
    d |= d >> 8;
    d |= d >> 16;
    d = (d & 0x5555'5555) + ((d & ~0x5555'5555) >> 1);
    d = (d & 0x3333'3333) + ((d & ~0x3333'3333) >> 2);
    d = (d & 0x0f0f'0f0f) + ((d & ~0x0f0f'0f0f) >> 4);
    d = (d & 0x00ff'00ff) + ((d & ~0x00ff'00ff) >> 8);
    d = (d & 0x0000'ffff) + ((d & ~0x0000'ffff) >> 16);

    vector<tuple<int, int, int>> edges;
    rep(i, d)
    {
        if (i > 0) {
            int b = 1 << (d - i - 1);
            edges.push_back(make_tuple(i - 1, i, 0));
            edges.push_back(make_tuple(i - 1, i, b));
        }
    }
    rep(i, d)
    {
        if (i > 0) {
            int b = 1 << (d - i - 1);
            if ((L & b) != 0) {
                int w = L - L % b - b;
                edges.push_back(make_tuple(0, i, w));
            }
        }
    }
    edges.push_back(make_tuple(0, d - 1, L));

    cout << d << " " << edges.size() << endl;
    rep(i, edges.size())
    {
        int from, to, w;
        tie(from, to, w) = edges[i];
        cout << from + 1 << " " << to + 1 << " " << w << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import org.w3c.dom.ranges.RangeException
import java.io.*
import java.util.*
import java.lang.*
import java.lang.Math.*


fun solve() {
    val (H, W) = rd.readIntArray()
    val S = Array(H){""}
    
    var cnt = 0
    for (i in 0 until H) {
        S[i] = rd.readString()
        cnt += S[i].count{ it == '#'}
    }

    val ans = if (cnt == H + W - 1) "Possible" else "Impossible"
    println(ans)
}


//val rd = debug.Reader("agc", "007", "a", "sample-1")
val rd = Reader()


fun main(args: Array<String>) {
    try {
        var exception: Throwable? = null
        val sth = Thread(null, SolveThread(), "solveThread", 128 * 1024 * 1024)
        sth.setUncaughtExceptionHandler { _, e -> exception = e }
        sth.start(); sth.join()
        if (exception != null) throw exception!! }
    catch (e: Exception) { throw e }
    finally { rd.close() }
}
const val MOD = 1_000_000_007L; const val INF = Int.MAX_VALUE/2; const val LINF = Long.MAX_VALUE/2
data class IntPair(val first: Int, val second: Int)
val errPrintln: (Any) -> Unit = { msg -> System.err.println(msg) }
fun rAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("EAssert Error: $msg"); throw Error(msg) }
}
fun tAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("TAssert Error: $msg"); Thread.sleep(3000) }
}
class SolveThread : Runnable {
    override fun run() { solve() }
}
class Reader {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    val readString: () -> String = { br.readLine() }
    val readInt: () -> Int = { br.readLine().toInt() }
    val readLong: () -> Long = { br.readLine().toLong() }
    val readIntArray: () -> IntArray = { br.readLine().split(' ').map { it.toInt() }.toIntArray() }
    val readLongArray: () -> LongArray = { br.readLine().split(' ').map { it.toLong() }.toLongArray() }
    val readListInt: () -> List<Int> = { br.readLine().split(' ').map { it.toInt() } }
    val readListLong: () -> List<Long> = { br.readLine().split(' ').map { it.toLong() } }
    val readListIntCol: (Int) -> List<Int> = { N -> (0 until N).map { readInt() } }
    val readListLongCol: (Int) -> List<Long> = { N -> (0 until N).map { readLong() } }
    val close: () -> Unit = { br.close() }
    protected fun finalize() { close() }
}


Measured memory_bytes: 36804
#include <stdio.h>

int gcd(int a, int b);
int lcm(int a, int b);

int main(void)
{
	int s_gcd, s_lcm;
	int a, b;
	
	while (scanf("%d %d", &a, &b) != EOF){
	
		s_gcd = gcd(a, b);
		s_lcm = lcm(a, b);
		
		printf("%d %d\n", s_gcd, s_lcm);
		
	}
	return (0);
}

int gcd(int m, int n)
{
    if (m % n == 0){
		return (n);
		
    }
	return (gcd(n, m % n));
}

int lcm(int a, int b)
{
	return (a / gcd(a, b) * b);
}

Measured memory_bytes: 596
#include<iostream>
#include<vector>
#include<fstream>
using namespace std;

typedef long long int ll;



int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int h, w;

    //ifstream fin  ("inputd.txt");

   // cin >> h >> w;

    cin >> h >> w;

    vector<vector<ll>> c = vector<vector<ll>>(10, vector<ll>(10, 0));
    ll inp;
    for(int i=0; i < 10; i++) {
        for(int j=0; j < 10; j++) {

            cin >> inp;
            c[i][j] = inp;
        }
    }
    bool update = true;
    while(update) {
        update = false;
        for(int i=0; i < 10; i++) {
            for(int j=0; j < 10; j++) {
                if(c[i][1] > c[i][j] + c[j][1]) {
                    c[i][1] = c[i][j] + c[j][1];
                    update = true;
                }
            }
        }

    }
    ll sol = 0;
    for(int i=0; i < h; i++) {
        for(int j=0; j < w; j++) {
            cin >> inp;
            if(inp != -1) sol += c[inp][1];
        }
    }
    cout << sol << endl;
}


Measured memory_bytes: 256
/* 
 * ?????????????????§??????#1612957 ????????¨???#827239 ???????????????????????????????????????????????????
 */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int n, k, A[2000000], C[10001];

int main(void) {

    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        scanf("%d", &A[i]);
        if (A[i] > k) {
            k = A[i];
        }
        ++C[A[i]];
    }

    for (int i = 0, f = 0; i <= k; ++i) {
        for (int j = 0; j < C[i]; ++j) {
            if (f) {
                printf(" %d", i);
            }
            else {
                f = 1;
                printf("%d", i);
            }
        }
    }
    printf("\n");

    return 0;
}

Measured memory_bytes: 9044
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e3+4;
inline int read() {
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
int n,m,sum;
int a[N];
int main() {
//	freopen("in.txt","r",stdin);
	n=read(),m=read();
	for (register int i=1;i<=n;++i) a[i]=read();
	sort(a+1,a+n+1);
	for (register int i=1;i<=m;++i) sum+=a[i];
	printf("%d\n",sum);
	return 0;
}

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

int main(void) {
	int A, B, C, K;
	cin >> A >> B >> C >> K;
	int cnt = 0;
	while (A >= B) {
		B *= 2;
		++cnt;
	}
	while (B >= C) {
		C *= 2;
		++cnt;
	}
	if (cnt <= K)
		cout << "Yes\n";
	else
		cout << "No\n";
	return 0;
}


Measured memory_bytes: 3508
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;

long long x[123456];

int main(void)
{
	vector<long long>walk;
	long long ans = 0;
	long long a, b;
	long long n;
	cin >> n >> a >> b;
	for (long long i = 0; i < n; ++i)
	{
		cin >> x[i];
	}
	for (long long i = 1; i < n; ++i)
	{
		walk.push_back(x[i] - x[i - 1]);
	}
	sort(walk.begin(), walk.end());
	for (long long elm : walk)
	{
		ans += elm * a;
	}
	for (auto itr = walk.rbegin(); itr != walk.rend(); ++itr)
	{
		if ((*itr) * a <= b)break;
		ans -= (*itr) * a;
		ans += b;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2168
import sys
from sys import stdin
input = stdin.readline

def BinarySearch(L, key, left, right):
    if left+1 == right:
        return False
    
    mid = (left+right)//2
    if L[mid] == key:
        return True
    elif L[mid] >key:
        return BinarySearch(L, key, left, mid)
    else:
        return BinarySearch(L, key, mid, right)

n = int(input())
NUM_LIST = list(map(int, input().split()))

k = int(input())
keys = list(map(int, input().split()))

cnt = 0
for key in keys:
    if BinarySearch(NUM_LIST, key, 0, len(NUM_LIST)):
        
        cnt += 1

print(cnt)


Measured memory_bytes: 16180
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Threading.Tasks;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		string[] input = Console.ReadLine().Split(' ');
		int[] d = new int[N];
        for(int i = 0; i < N; i++)
		{
			d[i] = int.Parse(input[i]);
		}
		int ans = 0;
		Array.Sort(d);
		int l = d[(N / 2) - 1];
		int r = d[N / 2];
		if (l == r) { ans = 0; }
		else { ans = r - l; }

		Console.WriteLine(ans);
	}
	
}

Measured memory_bytes: 18400
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int n;
    cin >> n;
    rep(i, n) {
        int a;
        cin >> a;
        if (a % 2 == 0) {
            if (a % 3 != 0 && a % 5 != 0) {
                cout << "DENIED" << endl;
                return 0;
            }
        }
    }
    cout << "APPROVED" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma warning(disable:4996)
using namespace std;
using ll = long long;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
//#define int long long
signed main() {
	int n, m, x, y;
	cin >> n >> m >> x >> y;
	vector<int>xs(n);
	for (int i = 0; i < n; i++) {
		cin >> xs[i];
	}
	sort(xs.begin(), xs.end());
	int x_end = xs[xs.size() - 1];
	vector<int>ys(m);
	for (int i = 0; i < m; i++) {
		cin >> ys[i];
	}
	sort(ys.begin(), ys.end());
	int y_begin = ys[0];
	if (x_end >=y_begin) {
		cout << "War" << endl;
	}
	else {//xs ysの条件は満たしている
		if (x < x_end + 1 && y_begin <= y) {
			cout << "No War" << endl;
		}
		else {
			cout << "War" << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int a,b,s=0,count=0,coin=0;
  
  scanf("%d %d", &a, &b);
  
  do{
    if(a>=b){
      coin=coin+a;
      a--;
    }
    else{
      coin=coin+b;
      b--;
    }
    count++;
  }while(count<2);
  
  printf("%d", coin);
  
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main(){
   int N;
   set<int> st;
   cin >> N;
   for(int i=0; i<N; i++){
       int x;
       cin >> x;

       st.insert(x);
   }

   cout << st.size() << endl;
}

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

int main() {
    string s;
    cin >> s;
    if ((s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3])) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = LONG_LONG_MAX / 100;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

int main() {
    ll n, x, d;
    cin >> n >> x >> d;

    if (d == 0) {
        if (x == 0) {
            cout << 1 << endl;
        } else {
            cout << n + 1 << endl;
        }
        return 0;
    }

    map<int, vector<P>> mp;
    rep(i, n + 1) {
        ll s = x * i;
        ll l = i * (i - 1) / 2;
        ll r = l + i * (n - i);
        s += l * d;
        r -= l;
        mp[(s + (d << 30)) % d].emplace_back(s, r);
    }
    ll ans = 0;
    for (auto p : mp) {
        auto a = p.second;
        int m = a.size();
        rep(i, m) a[i].first = (a[i].first - p.first) / d;
        vector<P> ev;
        rep(i, m) {
            ev.emplace_back(a[i].first, 1);
            ev.emplace_back(a[i].first + a[i].second + 1, -1);
        }
        sort(ev.begin(), ev.end());
        ll count = 0, pre = -INF;
        for (auto e : ev) {
            ll len = e.first - pre;
            if (count) ans += len;
            count += e.second;
            pre = e.first;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 25448
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

M = 10 ** 9 + 7
H, W = map(int, readline().split())
grid = []
for i in range(H):
    grid.append(readline().decode("utf-8").rstrip())
    assert len(grid[-1]) == W


def solve():
    t = [0] * W
    t[0] = 1
    for c in range(1, W):
        if grid[0][c] == ".":
            t[c] = t[c - 1]
    for r in range(1, H):
        for c in range(W):
            if grid[r][c] == "#":
                t[c] = 0
            elif c > 0:
                t[c] += t[c - 1]
                t[c] %= M
        # print(r, "\t", t)
    return t[-1]


if __name__ == "__main__":
    print(solve())


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

using namespace std;

int main(){
  long long n, a[100009], sm[100009];
  cin >> n;
  for(int i=0;i<=n;i++)cin >> a[i];
  sm[n] = a[n];
  for(int i=n-1;i>=0;i--)sm[i] = sm[i+1] + a[i];
  long long cnt = 0, mx=1;
  for(int i=0;i<=n;i++){
    if(mx<a[i]){
      cout << -1 << endl;
      return 0;
    }
    cnt += a[i];
    if(sm[i]<=mx){
      mx = sm[i]-a[i];
    }
    else{
      mx -= a[i];
    }
    cnt += mx;
    mx *= 2;
  }
  cout << cnt << endl;
}



Measured memory_bytes: 5188