akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	MyScanner sc = new MyScanner();
	Scanner sc2 = new Scanner(System.in);
	int mod = 1000000007;

	int N;
	int[] r;
	double[][] memo;

	void run() {
		while (sc2.hasNext()) {
			String[] input = sc2.nextLine().split(" ");
			int L = Integer.valueOf(input[0]);
			N = input.length - 1;
			r = new int[N];
			memo = new double[N][1 << N];

			for (int i = 1; i < N + 1; i++) {
				r[i - 1] = Integer.valueOf(input[i]);
			}
			boolean judge = false;
			for (int i = 0; i < N; i++) {
				double ans = tsp(i, 1 << i) + r[i];
				if (ans <= L) {
					judge = true;
				}
			}
			System.out.println(judge ? "OK" : "NA");
		}
	}

	double tsp(int v, int bit) {
		if(memo[v][bit] != 0) {
			return memo[v][bit];
		}
		if (bit == (1 << N) - 1) {
			return r[v];
		}
		double res = 1 << 10;
		for (int w = 0; w < N; w++) {
			if ((bit & (1 << w)) != 0) {
				continue;
			}
			double dis = Math.sqrt((r[v] + r[w]) * (r[v] + r[w])
					- (r[v] - r[w]) * (r[v] - r[w]));
			res = Math.min(res, dis + tsp(w, bit | 1 << w));
		}
		memo[v][bit] = res;
		return res;
	}

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

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	void debug2(int[][] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				System.out.print(array[i][j]);
			}
			System.out.println();
		}
	}

	class MyScanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-')
					return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}
	}
}

Measured memory_bytes: 27488
n = gets.chomp.to_i
ary = [0,0,0,]
total_ary = []
while line = gets
line = line.chomp

if line == "HIT"
  ary[0] += 1
  if ary[0] > 3
    ary[0] = 3
    ary[1] += 1
  end
elsif line == "HOMERUN"
ary[1] += ary[0] + 1
ary[0] = 0
elsif line == "OUT"
ary[2] += 1
if ary[2] == 3
  total_ary << ary[1]
  ary = [0,0,0,0]
end
end
end
puts total_ary


Measured memory_bytes: 6832
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+100;
int x[maxn],y[maxn];
int main() {
    int n,m,M,Mx=1e9,My=1e9,ans;
    cin>>n>>m>>M;
    for(int i=1;i<=n;i++)
        cin>>x[i],Mx=min(x[i],Mx);
    for(int i=1;i<=m;i++)
        cin>>y[i],My=min(y[i],My);
    ans = Mx+My;
    for(int i=1,xx,yy,c;i<=M;i++){
            cin>>xx>>yy>>c;
            ans = min(ans,x[xx]+y[yy]-c);
    }
    cout<<ans<<endl;
}



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

int main(void){
    int n;
    int *p;
    int count=0;

    scanf("%d", &n);

    p = malloc(sizeof(int) * n);

    for(int i=0;i<n;i++) {
        scanf("%d", &p[i]);
    }

    for(int i=1;i<n-1;i++) {
        if((p[i-1]<p[i] && p[i]<p[i+1]) || (p[i+1]<p[i] && p[i]<p[i-1])) {
            count++;
        }
    }
    printf("%d\n", count);

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
string s;

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

  cin >> s;

  int ans = s.length();
  REP(i, s.length() - 1) {
    if(s[i] != s[i + 1]) {
      ans = min(ans, max(i + 1, (int)s.length() - (i + 1)));
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 512
n,k = list(map(int, input().split()))
h = list(map(int, input().split()))

dp = [0] * n

dp[0]=0
for i in range(1, n):
    dp[i] = min([dp[j]+abs(h[i]-h[j]) for j in range(max(i-k, 0), i)])

print(dp[n-1])

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

#define rep(i,n) for (decay_t <decltype (n)> i = 0, i ## __len = (n); i < i ## __len; ++ i)

auto main () -> int
{
  cin.tie (nullptr);
  ios::sync_with_stdio (false);

  size_t n;
  size_t k;
  cin >> n >> k;

  vector <size_t> a (n);
  for (auto && elem : a) cin >> elem;

  enum {
    YET,
    FIRST,
    SECOND
  };
  using flag_t = size_t;

  vector <flag_t> dp (k + 1, YET);
  for (auto && elem : a)
  {
    dp [elem] = FIRST;
  }

  rep (i, k + 1)
  {
    for (auto && elem : a)
    {
      if (dp[i] == FIRST) continue;
      if (i < elem)
      {
        dp[i] = SECOND;
      }
      else
      {
        auto is_second = dp[i] == SECOND;
        dp[i] = dp[i - elem] ^ FIRST ^ SECOND;
        dp[i] %= 3;
        if (is_second && dp[i] == YET) dp[i] = SECOND;
      }
    }
  }

  array <const char *, 3> ans = {"chokudai", "First", "Second"};
  cout << ans [dp [k]] << endl;
}


Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
#include <set>

using namespace std;

int main(){
    int n;
    cin >> n;
    while(true){
        bool sosuu=true;
        for(int i = 2; i < n; i++){
            if(n%i == 0){sosuu = false;}
        }
        if(sosuu) break;
        n++;
    }
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int x,y,i,j;
	char a[101][101];
	while(scanf("%d%d\n",&x,&y)!=EOF)
	{
		for(i=0;i<x;i++)
		{
			for(j=0;j<y;j++)
			{
				if(j!=y-1)
			    a[i][j]=getchar();
		        else
		        {
		        	a[i][j]=getchar();
		        	getchar();
		        }
			}
		}
		for(i=0;i<y+2;i++)
		printf("#");
		printf("\n");
		for(i=0;i<x;i++)
		{
			printf("#");
			for(j=0;j<y;j++)
			{
				printf("%c",a[i][j]);
			}
			printf("#\n");
		}
		for(i=0;i<y+2;i++)
		printf("#");
		printf("\n");
	}
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> V(N), C(N);
  int ans = 0;
  
  for (int i=0;i<N;i++) cin >> V.at(i);
  for (int i=0;i<N;i++) cin >> C.at(i);
  
  for (int i=0;i<N;i++) ans += max(0,V.at(i)-C.at(i));
  
  cout << ans << endl;
}

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

ma = [0] * (N + 1)
mb = [0]*(M+1)


for i in range(N):
    ma[i + 1] = ma[i] + A[i]

for i in range(M):
    mb[i + 1] = mb[i] + B[i]

j = M
max_num = 0

for i in range(N+1):
    if ma[i] > K:
        break
    while ma[i] + mb[j] > K:
        j -= 1
    max_num = max(max_num, i + j)
print(max_num)


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

S, T = [], []
for i in range(N):
  s, t = input().split()
  S.append(s)
  T.append(int(t))

X = input()

sum = 0

for i in range(N):
  sum += T[i]
  if X == S[i]:
    sum = 0

print(sum)

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

int main() {
  int n;
  std::cin >> n;
  std::vector<std::vector<int>> am(n, std::vector<int>(n, 0));
  for (int i = 0; i < n; ++i) {
    int k, u;
    std::cin >> u >> k;
    for (int j = 0; j < k; ++j) {
      int v;
      std::cin >> v;
      am[u-1][v-1] = 1;
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      std::cout << am[i][j] << (j == n-1 ? "\n" : " ");
    }
  }
}
      

Measured memory_bytes: 3116
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const long long LINF = 1000000000000000018ll;
const int INF = 1000000009;
const int mod = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << fixed;

  string s; cin >> s;
  // dp[i][x] := i文字までみたとき,
  // dp[i][0]: Aが何個あるか?
  // dp[i][1]: ABが何個あるか?
  // dp[i][2]: ABCが何個あるか?
  vector<vector<long long>> dp(s.length()+10, vector<long long>(3, 0));
  // mul: 文字列として考えられる種類 "?" があると3倍される
  long long mul = 1;
  for (int i = 0; i < s.length(); i++) {
    if (s[i] == 'A') {
      dp[i+1][0] = dp[i][0] + mul;
      dp[i+1][1] = dp[i][1];
      dp[i+1][2] = dp[i][2];
    }
    if (s[i] == 'B') {
      dp[i+1][0] = dp[i][0];
      dp[i+1][1] = dp[i][1] + dp[i][0];
      dp[i+1][2] = dp[i][2];
    }
    if (s[i] == 'C') {
      dp[i+1][0] = dp[i][0];
      dp[i+1][1] = dp[i][1];
      dp[i+1][2] = dp[i][2] + dp[i][1];
    }
    if (s[i] == '?') {
      // ?のときは, 3つの構成可能文字列に分岐するので, 3倍する
      dp[i+1][0] = dp[i][0] * 3 + mul;
      dp[i+1][1] = dp[i][1] * 3 + dp[i][0];
      dp[i+1][2] = dp[i][2] * 3 + dp[i][1];
      mul = (mul * 3) % mod;
    }
    dp[i+1][0] %= mod;
    dp[i+1][1] %= mod;
    dp[i+1][2] %= mod;
  }
  cout << dp[s.length()][2] << endl;
  return 0;
}

Measured memory_bytes: 5840
import copy

N = int(input())

a = [int(x) for x in input().split()]
b = copy.copy(a)

for i in range(N//2, 0, -1):
    num = 0
    for j in range(2*i, N+1, i):
        num += b[j-1]
    #     print(i, j, b[j-1])
    # print(i, num)
    if a[i-1] == divmod(num, 2)[1]:
        b[i-1] = 0
    else:
        b[i-1] = 1

# print(b)

ret = []
for i in range(N):
    if b[i] == 1:
        ret.append("{}".format(i+1))
print(len(ret))
print(" ".join(ret))


Measured memory_bytes: 18100
import java.util.Scanner;

public class Main {
	public static void main(String[] a){
		Scanner scn = new Scanner(System.in);
		String str = scn.nextLine();
		int len = str.length();
		for(int i = 0;i < len;i++){
		System.out.print(str.charAt(len - 1 - i));
		}
		System.out.println("");
	}
}

Measured memory_bytes: 25916
N=int(input())
D={}
for i in range(N):
    s=input()
    if s in D:
        D[s]+=1
    else:
        D[s]=1
    

m=max(D.values())
d=list(D.values())
k=list(D.keys())
ans=[]
for i in range(len(D)):
    if m==d[i]:
        ans.append(k[i])

ans=sorted(ans)
for a in ans:
    print(a)

Measured memory_bytes: 36188
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <cstdint>
#include <iomanip>
using ll = long long;
#define fast_io(); std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

int main(){
    ll n; std::string s;
    std::cin >> n >> s;

    int x=0, ans=0;
    for(int i=0; i<n; i++){
        if(s[i]=='I') x++;
        else x--;
        ans = std::max(ans, x);
    }
    std::cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
// head{{{
/* vim: set foldmethod=marker ft=cpp: */
#include <iostream>
#include <list>
#pragma GCC optimize("O3")
using namespace std;
// }}}
 
int main() {
    //optimize{{{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //---------}}}

    int N=0; //groups
    int tmp=0;
    int resf=0;
    cin >> N;
    for (int i=0;i<N;i++) {
        int l,r=0;
        cin >> l >> r;
        tmp = r-l+1;
        resf += tmp;
    }
    cout << resf << endl;
}



Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007

char a[1010][1010];
ll dp[1010][1010];
void fn(ll i,ll j,ll h,ll w)
{
    memset(dp,0,sizeof(dp));
    for(i=0; i<h; i++)
    {
        if(a[i][0] == '.')
        dp[i][0] = 1;
        else
        break;
    }
    
    for(i=0; i<w; i++)
    {
        if(a[0][i] == '.')
        dp[0][i] = 1;
        else
        break;
    }
    
    for(i=1; i<h; i++)
    {
        for(j=1; j<w; j++)
        {
            if(a[i][j] == '#')
            continue;
            
            if(dp[i-1][j] > 0)
            {
                dp[i][j] += dp[i-1][j];
                dp[i][j] %= mod;
            }
            
            if(dp[i][j-1] > 0)
            {
                dp[i][j] += dp[i][j-1];
                dp[i][j] %= mod;
            }
        }
    }
    
    cout<<dp[h-1][w-1]%mod;
    return;
}
int main()
{
    ll i,j,h,w;
    cin>>h>>w;
    for(i=0; i<h; i++)
    {
        for(j=0; j<w; j++)
        {
            cin>>a[i][j];
        }
    }
    fn(0,0,h,w);
    return 0;
}

Measured memory_bytes: 12516
#include<iostream>

using namespace std;

int main(){
  string S;
  int N,K;
  cin >> N >> K;
  cin >> S;
  K = K - 1;
  if(S[K] == 'A'){
    S[K] = 'a';
  }else if(S[K] == 'B'){
    S[K] = 'b';
  }else if(S[K] == 'C'){
	S[K] = 'c';
  }
  cout << S << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		String S = sc.next();
		
		String result = S.substring(0,K-1) + S.substring(K-1,K).toLowerCase() + S.substring(K,S.length());
		System.out.println(result);		
	}
}



Measured memory_bytes: 21972
n=gets.to_i
n.times do
  l = gets
  ll = l.split
  if ll[0].to_i**2 + ll[1].to_i**2 == ll[2].to_i**2
    puts "YES"
  elsif ll[1].to_i**2 + ll[2].to_i**2 == ll[0].to_i**2
    puts "YES"
  elsif ll[2].to_i**2 + ll[0].to_i**2 == ll[1].to_i**2 then
    puts "YES"
  else
    puts "NO"
  end
end

Measured memory_bytes: 6116
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int MX=4e5+7;
const int mod=9901;
using namespace std;
int p[MX],k[MX];
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}
ll __gcm(ll a,ll b){return a*b/__gcd(a,b);}
int main()
{
  //ios::sync_with_stdio(0),cin.tie(0);
  int N,K;
  cin>>N>>K;
  for(int i=1;i<=N;i++)
  {
    cin>>p[i];
    p[i]=p[i]+p[i-1];
  }
  double ans=0;
  for(int i=K;i<=N;i++)
  {
      ans=max(ans,1.0*(K+p[i]-p[i-K])/2);
  }
  printf("%.10f\n",ans);

}


Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<random>
#include<functional>

#define rep(i,n) for(int i=0; i<n; i++)
#define pb push_back
#define pint pair<int, int>
#define mp make_pair

using namespace std;

typedef long long ll;



const int INF = 1e9;

struct edge{
	int to, co;
};

int N, K;
int c[5000], r[5000];
vector<int> road[5005];
vector<edge> G[5005];

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> c[i] >> r[i];
	}
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b; a--; b--;
		road[a].push_back(b);
		road[b].push_back(a);
	}

	for (int i = 0; i < N; i++) {
		vector<bool> f(N, false);
		queue<pint> q;
		q.push(mp(i, r[i]+1));
		while (!q.empty())
		{
			pint p = q.front(); q.pop();
			int v = p.first;
			if (p.second == 0) continue;
			if (f[v]) continue;
			f[v] = true;

			edge e;
			e.to = v; e.co = c[i];
			if (i != v) G[i].push_back(e);
			for (int ei : road[v]) {
				q.push(mp(ei, p.second - 1));
			}
		}
	}

	priority_queue<pint, vector<pint>, greater<pint> > pq;
	vector<int> d(N, INF);

	d[0] = 0;
	pq.push(mp(0, 0));
	while (!pq.empty())
	{
		pint p = pq.top(); pq.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (auto e : G[v]) {
			if (d[e.to] > d[v] + e.co) {
				d[e.to] = d[v] + e.co;
				pq.push(mp(d[e.to], e.to));
			}
		}
	}

	cout << d[N - 1] << endl;


	return 0;
}



Measured memory_bytes: 127788
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <functional>
#include <queue>
#include <climits>
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
using namespace std;
typedef long long ll;
//typedef unsigned long long ull;
typedef pair<int, int> P;

string s;

int main() {
    cin >> s;
    int res = INT_MAX;
    Rep(i,s.size()-2){
        int a = (int)(unsigned char)s[i]-48;
        int b = (int)(unsigned char)s[i+1]-48;
        int c = (int)(unsigned char)s[i+2]-48;
        int d = a*100+b*10+c*1;
        if(abs(d-753)<res){
            res = abs(d-753);
        }
    }
    put(res);
    return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

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

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

ll dp[202020];
vector<ll> B;
vector<ll> basho(202020);
vector<ll> G[202020];
ll M;

ll rec(ll i){
	if(dp[i]>-1) return dp[i];
	if(i==M-1) return 1;
	ll res = 0;
	res += rec(i+1);
	res %= mod;
	if(G[B[i]].size()-1==basho[i]){
		1;
	}else{
		ll ne = G[B[i]][basho[i]+1];
		res += rec(ne);
		res %=mod;
	}
	dp[i]= res;
	return res;
}

int main(){
	ll N;
	cin >> N;
	vector<ll> C(N);
	REP(i, N) cin >> C[i];


	B.push_back(C[0]);
	for(int i=1;i<N;i++){
		if(C[i]!=C[i-1]) B.push_back(C[i]);
	}
	M = B.size();

	REP(i, 202020) dp[i] = -1;
	REP(i, M){
		G[B[i]].push_back(i);
		basho[i] = G[B[i]].size()-1;
	}

	/*
	REP(i, 5){
		REP(j, G[i].size()){
			cout << G[i][j] << " ";
		}
		cout << endl;
	}
	*/

	cout << rec(0) << endl;

    return 0;
}

Measured memory_bytes: 23792
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  int h,w,n;
  cin>>h>>w>>n;
  vector<pair<ll,ll>> v;
  ll g[h+1]={};
  for(int i=0;i<=h;i++) g[i]=w+1;
  map<pair<ll,ll>,int> mp;
  for(int i=0;i<n;i++){
    ll x,y;
    cin>>x>>y;
    v.push_back(make_pair(x,y));
    g[x]=min(g[x],y);
  }

  ll ans=h-1;
  ll pre=1;
  for(int i=2;i<=h;i++){
    //cout<<i<<" "<<pre<<" "<<ans<<endl;
    if(g[i]<=i-1){
      if(g[i]<=pre){
        //cout<<i<<" "<<g[i]<<" "<<ans<<endl;
        ans=min(ans,(ll)i-2);
      }
      pre=min(pre+1,g[i]-1);
    }else{
      if(pre+1<g[i]) pre=pre+1;
    }
  }

  cout<<ans+1<<endl;

  return 0;
}


Measured memory_bytes: 7920
while True:
	n = int(input())

	if n == 0:
		break
	
	dic = {}
	for i in range(n):
		pre, pos = input().split()
		dic[pre] = pos.rstrip()

	n = int(input())
	s = ""
	for i in range(n):
		c = input().rstrip()
		if c in dic:
			s += dic[c]
		else:
			s += c

	print(s)

Measured memory_bytes: 7780
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size)
#define MOD 1000000007
const long long mod = 1e9+7;
typedef vector<long long> Vl;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef long long ll;

int main(){ 
    int N,r,l=0;
    ll s=0;
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        cin >> r;
        if (r-l>0) s+=r-l;
        l=r;
    }
    cout << s << endl;
    return 0;
}

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

long long int n=1,cnt=0,ans=0,a[10000000],b,c,cmp=INF*-1,cmpp=INF,cmpcmp,data,m,h,w,x,y,xcmp=0,ycmp=0,sum=0;

string s;

vector<int> z;

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


    bool fu=false;
    bool sei=false;
       cin >> n;
       rep(i,n){
           cin >> a[i];
           cmp=max(cmp,a[i]);
           cmpp=min(cmpp,a[i]);
           if(a[i]<=0){
               fu=true;
           }
           else{
               sei=true;
           }
       }
       if(sei==true && fu==true){
           if(cmp>=cmpp*-1){
               rep(i,n){
                   if(cmp==a[i]){
                       cmpcmp=i+1;
                   }
               }
               Cout(2*(n-1));
               rep(i,n){
                   if(i+1!=cmpcmp){
                       cout << cmpcmp << " " << i+1 << endl;
                   }
               }
               rep(i,n-1){
                   cout << i+1 << " " << i+2 << endl; 
               } 
           }
           else{
               rep(i,n){
                   if(cmpp==a[i]){
                       cmpcmp=i+1;
                   }
               }
               Cout(2*(n-1));
               rep(i,n){
                   if(i+1!=cmpcmp){
                       cout << cmpcmp << " " << i+1 << endl;
                   }
               }
               rrrep(i,n-1,0){
              cout << i+1 << " " << i << endl;
           }
               
           }
       }
       else if(sei==true && fu==false){
           Cout(n-1);
           rep(i,n-1){
               cout << i+1 << " " << i+2 << endl; 
            }
       }
       else if(sei==false && fu==true){
           Cout(n-1);
           rrrep(i,n-1,0){
              cout << i+1 << " " << i << endl;
           }
       }
return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define EPS 1e-8
#define Size 101
struct point {
  double x;
  double y;
};
struct point poly[Size];
int constrain(int n, struct point p);
int main(void)
{
  int i, n, q;
  struct point qoly;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%lf%lf", &poly[i].x, &poly[i].y);
  poly[n] = poly[0];
  scanf("%d", &q);
  for (i = 0; i < q; i++) {
    scanf("%lf%lf", &qoly.x, &qoly.y);
    printf("%d\n", constrain(n, qoly));
  }
}
int constrain(int n, struct point p)
{
  int i, x = 0;
  double cross, dot;
  struct point a, b;
  for (i = 0; i < n; i++) {
    a.x = poly[i].x - p.x, a.y = poly[i].y - p.y;
    b.x = poly[i+1].x - p.x, b.y = poly[i+1].y - p.y;
    cross = a.x * b.y - b.x * a.y;
    dot = a.x * b.x + a.y * b.y;
    if (abs(cross) < EPS && dot < EPS) return 1;
    if (a.y > b.y) {
      struct point temp = a;
      a = b;
      b = temp;
      cross *= -1;
    }
    if (a.y < EPS && b.y > EPS && cross > EPS) x = !x;
  }
  return (x % 2 ? 2 : 0);
}


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

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define rept(i,n) for(ll (i)=0;(i)<=(ll)(n);(i)++)
#define reps(i,s,n) for(ll (i)=(s);(i)<(ll)(n);(i)++)
#define repst(i,s,n) for(ll (i)=(s);(i)<=(ll)(n);(i)++)
#define repr(i,n) for(ll (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define dbg(x) cout<<#x" = "<<(x)<<ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\???
// .???.:( ^??^)?????????.???.:( ^??^)?????????.???.:( ^??^)?????????.???.:( ^??^)?????????.???.:( ^??^)?????????
// ?????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\????????????????????\??????????????????

ll n, n1, n2, W, v[40], w[40], m = 1, r;
vector<pll> ps;

int main() {
	cin >> n >> W;
	rep(i,n) cin >> v[i] >> w[i];
	n1 = n/2, n2 = n-n1;
	rep(i,1<<n1) {
		ll tw = 0, tv = 0;
		rep(j,n1) if (i>>j & 1) tw += w[j], tv += v[j];
		if (tw<=W) ps.pb(mp(tw, tv));
	}
	sort(all(ps));
	reps(i,1,ps.size()) if (ps[m-1].se<ps[i].se) ps[m++] = ps[i];
	rep(i,1<<n2) {
		ll tw = 0, tv = 0;
		rep(j,n2) if (i>>j & 1) tw += w[n1+j], tv += v[n1+j];
		if (tw<=W) {
			ll p = ((lower_bound(ps.begin(), ps.begin()+m, mp(W-tw, linf)))-1)->se;
			chmax(r, tv+p);
		}
	}
	cout << r << ln;
}

Measured memory_bytes: 19404
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <climits>
#include <ctime>
#include <random>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
//#define ll long long
#define eps 1e-9
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;

int main() {
    speed;
    char c;
    cin >> c;
    cout << char(c + 1);
}

Measured memory_bytes: 256
#include<cstdio>
#define int long long
#define N 105
inline void chk(int &x,int y){if(y>x)x=y;}
int n,W,w[N],v[N],dp[N][100005];
signed main(){
	scanf("%lld%lld",&n,&W);
	for(int i=0;i<n;++i)scanf("%lld%lld",&w[i],&v[i]);
	int ans=0;
	for(int i=0;i<n;++i)for(int j=0;j<=W;++j){
		if(j+w[i]<=W)chk(dp[i+1][j+w[i]],dp[i][j]+v[i]);
		chk(dp[i+1][j],dp[i][j]);
	}
	for(int j=0;j<=W;++j)chk(ans,dp[n][j]);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 79232
import bisect
a = [True] * 100001
a[0] = False
a[1] = False
p = []
for i in range(2, 100001):
    if a[i]:
        for j in range(i * 2, 100001, i):
            a[j] = False
        if i % 2 != 0 and a[(i + 1) // 2]:
            p.append(i)
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(p, r) - bisect.bisect_left(p, l))

Measured memory_bytes: 4212
n = int(input())
s = list(input())
count = 0
for i in range(n):
    x = set(s[0:i])
    y = set(s[i:n])
    x = list(x)
    y = list(y)
    c = x+y
    count = max(count,len(c)-len(set(c)))
print(count)

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

using namespace std;

const int N = 305;
int n, cnt[4];
double dp[N][N][N];

double solve (int cnt1, int cnt2, int cnt3) {
    if (!cnt1 && !cnt2 && !cnt3) return 0;
    double &ret = dp[cnt1][cnt2][cnt3];
    if (ret != -1) return ret;
    ret = 0;
    if (cnt1) ret += 1.0 * cnt1 / n * (solve(cnt1 - 1, cnt2, cnt3) );
    if (cnt2) ret += 1.0 * cnt2 / n * (solve(cnt1 + 1, cnt2 - 1, cnt3) );
    if (cnt3) ret += 1.0 * cnt3 / n * (solve(cnt1, cnt2 + 1, cnt3 - 1) );
    ret += 1;
    ret *= 1.0 * n / (cnt1 + cnt2 + cnt3);
    return ret;
}

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a; cin >> a;
        ++cnt[a];
    }

    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) for (int k = 0; k < N; ++k) dp[i][j][k] = -1;
    cout << fixed << setprecision(10) << solve(cnt[1], cnt[2], cnt[3]);

    return 0;
}


Measured memory_bytes: 221952
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define int ll
#define rep(i, n) for (int i = 0, i##_cond = (n); i < i##_cond; ++i)
#define FOR(i, a, b) for (int i = (a), i##_cond = (b); i < i##_cond; ++i)
#define ROF(i, a, b)                                                           \
  for (int i = (a)-1, i##_cond = (b); i >= i##_cond; --i) // ROF(i,n,0)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend() // sortで降順
#define SUM(a) accumulate(all(a), int(0))
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using pii = pair<int, int>;
constexpr ll inf = 1ll << 61;
constexpr ll mod = 1e9 + 7;
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> T add(const T &a, const T &b) { return (a + b) % mod; }

vi dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
int h, w;

bool isin(int x, int y) { return 0 <= x and x < h and 0 <= y and y < w; }

signed main() {
  int k;
  cin >> h >> w >> k;
  int sx, sy, gx, gy;
  cin >> sx >> sy >> gx >> gy;
  sx--;
  sy--;
  gx--;
  gy--;
  vs c(h);
  rep(i, h) cin >> c[i];

  vvi d(h, vi(w, inf));
  d[sx][sy] = 0;
  queue<pii> q;
  q.push(pii(sx, sy));
  while (not q.empty()) {
    auto now = q.front();
    q.pop();

    rep(i, 4) {
      FOR(j, 1, k + 1) {
        int nx = now.first + j * dx[i], ny = now.second + j * dy[i];
        if (not isin(nx, ny) or c[nx][ny] == '@' or
            d[nx][ny] <= d[now.first][now.second])
          break;
        if (d[nx][ny] == inf) {
          d[nx][ny] = d[now.first][now.second] + 1;
          q.push(pii(nx, ny));
        }
      }
    }
  }
  if (d[gx][gy] == inf)
    cout << -1 << endl;
  else
    cout << d[gx][gy] << endl;
}

Measured memory_bytes: 20004
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
#define inf 1e18+42
#define endl "\n"
#define pi 3.1415926535897932384626433832795028841971693993751058
#define maxn 100005

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define fori(it,A) for(auto it=A.begin();it!=A.end();it++)

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define pq priority_queue
#define all(x) (x).begin(),(x).end()
#define zero(x) memset(x,0,sizeof(x));
#define ceil(a,b) (a+b-1)/b
 
using namespace std;

int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

//START OF CODE ->->->->->->->

void solve()
{
    int n;
    cin>>n;
    map<int,int> a;
    map< string,pq<int> > v;
    rep(i,0,n){
        string s;
        cin>>s;
        int p;
        cin>>p;
        a[p] = i+1;
        v[s].push(p);
    }
    fori(it,v){
        while(!it->sd.empty()){
            cout<<a[it->sd.top()]<<endl;
            it->sd.pop();
        }
    }
}

//END OF CODE ->->->->->->->->

signed main()
{
    fast;
    int t = 1;
    // cin>>t;

    while(t--)
    {
        solve();
    }
    return 0;
}



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

int n, m;

int main(void){
	cin >> n >> m;
	vector<int> ans(n);
	rep(i, m){
		int a, b;
		cin >> a >> b;
		ans[a-1]++;
		ans[b-1]++;
	}
	rep(i, n) cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 3552
H,W=map(int,input().split())
C=[list(map(int,input().split())) for i in range(10)]

A=[]
for i in range(H):
    A+=list(map(int,input().split()))
A.sort()
while A[0]==-1:
    A.pop(0)

def warshall_floyd(D,n):  #最短経路を表すマップを作る
    for k in range(n):
        for i in range(n):
            for j in range(n):
                D[i][j] = min(D[i][j],D[i][k] + D[k][j])
    return D

True_Map = warshall_floyd(C,10)

ans=0
for i in A:
    ans+=True_Map[i][1]
print(ans)

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long

const int N=100005;
const int MOD=1e9+7;
 

// lower_bound - which does not compare less than val
// upper_bound - which compares greater than val
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
 
int32_t main()
{
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  /* stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?)
  * do smth instead of nothing and stay organized
*/

int t;
cin>>t;
int sum=0;
for(int i=1;i<=t;i++)
{
	for(int j=1;j<=t;j++)
	{
		for(int k=1;k<=t;k++)
		{
			int x=__gcd(i,j);
			int y=__gcd(x,k);
			sum+=y;
		}
	}
}
cout<<sum;
}

Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

ll n,k;
int a[505];

bool f(int d) {
  vector<int> t;
  vector<int> sum;
  for(int i = 0; i < n; i++) t.push_back(a[i] % d);
  sort(t.begin(),t.end());

  sum.push_back(0);
  for(int i = 0; i < t.size(); i++) sum.push_back(t[i]+sum.back());

  for(int i = 0; i <= n; i++) {
    ll A = sum[i];
    ll B = (n - i) * 1ll * d - (sum[n] - sum[i]);
    if(max(A,B) <= k) return true;
  }

  return false;
}

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

  int ans = 0;

  for(int i = 1; i * i <= S; i++) {
    if(S % i == 0) {
      if(f(i)) ans = max(ans,i);
      if(f(S/i)) ans = max(ans,S/i);
    }
  }

  cout << ans << endl;
}

  


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
	char c = getchar(); int x = 0, f = 1;
	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, a[MAXN];
main() {
	N = read();
	for(int i = 1; i <= N; i++) a[i] = read();
//	sort(a + 1, a + N + 1);
	int mn = 0, mx = 0, num = 0;
	for(int i = 1; i <= N; i++) {
		if(!mn) mn = a[i], num = 1;
		else if(a[i] == mn) num++;
		else if(!mx) mx = a[i];
		else if(a[i] != mx) {puts("No"); return 0;}		
	}
	if(mn > mx && (mx)) swap(mn, mx), num = N - num;

	if(!mx) {
		if((mn == N - 1) || (mn * 2 <= N)) puts("Yes");
		else puts("No");
	} else {
		if((mx == mn + 1) && (2 * (mx - num) <= N - num) && (mx - num > 0)) puts("Yes");
		else puts("No");
	}
	return 0;
}

Measured memory_bytes: 640
n = gets.to_i
as = gets.split.map(&:to_i)

ans = 0
tmp = []
as.each.with_index(1) do |a,i|
  tmp << a-i
  # ans += (a - (x + i)).abs
end
tmp.sort!
x = tmp[tmp.size / 2]
as.each.with_index(1) do |a,i|
  ans += (a - (x + i)).abs
end

puts ans


Measured memory_bytes: 19840
#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;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

int N, M, K, H, W, L, R;
//long long int N, M, K, H, W, L, R;

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

	cin >> N;
	map<pair<int, int>, int>mp;
	for (int i = 0; i < N; i++) {
		cin >> W >> H >> K;
		mp[{W, H}] += K;
	}
	int ans = 0;
	for (auto i : mp) {
		{
			int box = 0;
			for (int j = 0; j <= 1; j++) {
				for (int k = 0; k <= 1; k++) {
					if (mp.find({ i.first.first + j,i.first.second + k }) != mp.end()) {
						box += mp[{i.first.first + j, i.first.second + k}];
					}
				}
			}
			ans = max(ans, box);
		}
		{
			int box = 0;
			for (int j = 0; j <= 1; j++) {
				for (int k = -1; k <= 0; k++) {
					if (mp.find({ i.first.first + j,i.first.second + k }) != mp.end()) {
						box += mp[{i.first.first + j, i.first.second + k}];
					}
				}
			}
			ans = max(ans, box);
		}
		{
			int box = 0;
			for (int j = -1; j <= 0; j++) {
				for (int k = 0; k <= 1; k++) {
					if (mp.find({ i.first.first + j,i.first.second + k }) != mp.end()) {
						box += mp[{i.first.first + j, i.first.second + k}];
					}
				}
			}
			ans = max(ans, box);
		}
		{
			int box = 0;
			for (int j = -1; j <= 0; j++) {
				for (int k = -1; k <= 0; k++) {
					if (mp.find({ i.first.first + j,i.first.second + k }) != mp.end()) {
						box += mp[{i.first.first + j, i.first.second + k}];
					}
				}
			}
			ans = max(ans, box);
		}
	}
	cout << ans << " / " << 1 << endl;
}


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

#define ll long long
#define fast_io ios::sync_with_stdio(0); cin.tie(0)
#define infl 1e18L+9
#define inf 1e9L+9
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()

const int mod=1e9L+7; 

void solve(){
  int n; cin>>n; 
  cout<<n*n*n<<endl; 
}

int main()
{
	fast_io;
	clock_t beg=clock(); 
	solve(); 
	clock_t end=clock(); 
	fprintf(stderr,"%.2lf sec\n",(double)(end-beg)/CLOCKS_PER_SEC); 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;
typedef long long int ll;
typedef long double ld;
#define MOD 1000000007
#define ALL(obj) (obj).begin(),(obj).end()
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;}
const long long INF = 1LL << 60;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
//四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct edge{//グラフに使うヤツ
    ll from,to,cost;
};

typedef vector<vector<edge> > G;
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}

int main(){
    ll a,b;
    cin >> a >> b;
    ll l=a*b/gcd(a,b);
    vector<ll> n,m;
    string s,t;
    cin >> s >>t;
    for (ll i=0;i<a;i++){
        n.push_back(i*(l/a));
    }
    for (ll i=0;i<b;i++){
        m.push_back(i*(l/b));
    }
    if (n.size()!=s.size() or m.size()!=t.size()){
        cout << -1 << endl;
        return 0;
    }

    ll of=0;
    for (ll i=0;i<n.size();i++){
        while(of<m.size()-1 and n[i]>m[of]){
            of++;
        }
        if (n[i]==m[of]){
            if (s[i]!=t[of]){
                cout << -1 << endl;
                return 0;
            }
        }
    }    
    cout << l << endl;
    return 0;
}


Measured memory_bytes: 5512
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n)repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
typedef pair<int,int> P;
typedef pair<int, P> PP;
#define all(v) v.begin(),v.end()
#define fi first
#define se second
const int inf = 1e9;
int mod = 1e9+7;

int dp[2000][2000], fac[2000], inv[2000];
int Pow(int x, int k){
	int res = 1;
	while(k > 0){
		if(k&1)res = (x*res)%mod;
		x = (x*x)%mod;
		k >>= 1;
	}
	return res;
}
void Factrial(int n){
	fac[0] = inv[0] = 1;
	rrep(i,n){
		fac[i] = (fac[i-1]*i)%mod;
		inv[i] = Pow(fac[i], mod-2);
	}
}
int perm(int n, int k){
	return (fac[n]*inv[n-k])%mod;
}

signed main(){
	int n, a, b, c, d;
	scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d);
	Factrial(1002);
	
	dp[a-1][0] = 1;
	repi(i,a,b+1)rep(j,n+1){
		dp[i][j] = dp[i-1][j];
		repi(k,c,d+1){
			if(j-i*k < 0)break;
			int tmp1 = (dp[i-1][j-i*k]*perm(n-j+i*k,i*k))%mod;
			int tmp2 = (Pow(inv[i], k)*inv[k])%mod;
			dp[i][j] += (tmp1*tmp2)%mod;
			dp[i][j] %= mod;
		}
	}
	printf("%lld\n",dp[b][n]);
	return 0;
}


Measured memory_bytes: 16128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  string s;
  cin>>s;
  int a=0;
  for(char c:s){
    if(c=='+') a++;
    else a--;
  }
  cout<<a<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (1<<29)
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int p){
	for(int i=2;i<=sqrt(p);i++){
		if(!p%i)return false;
	}
	return true;
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b==1)return a%MOD;
    if(b%2)return modpow(a,b-1)*a%MOD;
    else return modpow(a,b/2)*modpow(a,b/2)%MOD;
}
int comb(int a,int b){
    if(b==0||a==b)return 1;
    if(b==1)return a%MOD;
    return (comb(a-1,b-1)+comb(a-1,b))%MOD;
}
// Library End !
signed main(){
    int n,k,ans=0;
    cin>>n>>k;
    if(k%2==1)ans=(n/k)*(n/k)*(n/k);
    else ans=(((n/(k/2))-(n/k))*((n/(k/2))-(n/k))*((n/(k/2))-(n/k)))+((n/k)*(n/k)*(n/k));
    cout<<ans<<endl;
	return 0;
}


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

using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l&&r<=sr
#define outside sr<l||r<sl

typedef long long ll;

int n;
int arr[200005];
int yer[200005];

int get(int i){
	return yer[i] < yer[i+1];
}

int main(){
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> arr[i];
		yer[arr[i]] = i;
	}
	
	int maxx = 0;
	int cur = 0;
	for (int i = 0; i < n-1; i++){
		//cout << get(i+1) << " ";
		if (get(i+1)){
			cur++;
		} else {
			maxx = max(maxx, cur);
			cur = 0;
		}
	}
	//cout << endl;
	
	maxx = max(maxx, cur);
	//cout << bas(maxx) << endl;
	
	cout << n-maxx-1 << endl;
}


Measured memory_bytes: 1792
package main

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

var pq []int

func push(x int) {
	p := sort.Search(len(pq), func(i int) bool { return pq[i] <= x })
	if p == len(pq) {
		pq = append(pq, x)
		return
	}
	pq = append(pq[:p+1], pq[p:]...)
	pq[p] = x
}

func pop() int {
	if len(pq) == 0 {
		return 0
	}

	ans := pq[0]
	pq = pq[1:]
	return ans
}

type task struct{ a, b int }
type tasks []task

func (t tasks) Len() int           { return len(t) }
func (t tasks) Swap(i, j int)      { t[i], t[j] = t[j], t[i] }
func (t tasks) Less(i, j int) bool { return t[i].a < t[j].a }

func main() {
	var n, m int
	fmt.Scan(&n, &m)

	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	ts := tasks(make([]task, n))
	for i := range ts {
		sc.Scan()
		ts[i].a, _ = strconv.Atoi(sc.Text())
		sc.Scan()
		ts[i].b, _ = strconv.Atoi(sc.Text())
	}
	sort.Sort(ts)

	pq = make([]int, 0, n)
	ans := 0
	ti := 0
	for i := 1; i <= m; i++ {
		for ti < len(ts) && ts[ti].a == i {
			push(ts[ti].b)
			ti++
		}
		ans += pop()
	}
	fmt.Println(ans)
}


Measured memory_bytes: 4480
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
ll g(ll a,ll b){
    ll tmpa,tmpb,tmp;
    tmpa = a;tmpb = b;
    if(tmpa < tmpb){
        tmp = tmpb;
        tmpb  =tmpa;
        tmpa = tmp;
    }
    while(tmpb != 0){
        tmp = tmpa%tmpb;
        tmpa = tmpb;
        tmpb = tmp;
    }
    return tmpa;
}

int main(){
    ll a,b;cin >> a >> b;
    ll ma = g(a,b);
    int ans = 1;
    if(ma == 1){
        cout << ans << endl;
        return 0;
    }
    //cout << ma << endl;
    ll tmpma = ma;
    for(int i=2;i <= sqrt(tmpma)+1;i++){
        if(ma%i == 0){
            int j = ma/i;
            while(ma%i == 0){
                ma = ma/i;
            }
            ans ++;
        }
    }
    if(ma != 1){
        ans ++;
    }

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

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

int main(){
    long long n;
    cin >> n;
    
    int a[] = {0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120};
    
    long long ans = 0;
    map<long long,int> mp;
    for(long long i = 2;i * i <= n;i++){
        if(n % i != 0)continue;
        n /= i;
        
        long long ex = 1;
        while(n % i == 0){
            n /= i;
            ex++;
        }
        mp[i] += ex;
        
        long long l = 1;
        while(mp[i] >= l){
            mp[i] -= l;
            l++;
        }
        ans += l-1;
    }
    if(n > 1){
        mp[n]++;
        for(int j = 0;j < 15;j++){
            if(a[j] <= mp[n] && mp[n] < a[j+1]){
                ans += j;
                mp[n] -= a[j];
                break;
            }
        }
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 3592
/*** 𝕒𝕜𝕤𝕙𝕒𝕪𝕜𝕦𝕞𝕒𝕣𝟡𝟡 ***/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using id_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update> ;
 
#define f(i,x,n) for(i=x;i<n;i++)
#define fr(i,x,n) for(i=x;i>=n;i--)
#define pu push_back           
#define pp pop_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SP(x) fixed<<setprecision(x)
#define IOS() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
const long long MOD=1e9+7;
const long double PI = acos(-1);
const long long INF=INT_MAX;
const long long LINF=LLONG_MAX;
const long long N=1e5+1;
 
typedef long long ll;
typedef long double ld;

vector<ll> v[N];
vector<ll> h(N);
ll ans;

void test_case()
{
   ll x,i,j,a,b;
   cin>>x;
   ll mx=1e17, curr=0, tot;
   vector<pair<ll,ll>> v;
   tot = 0;
   while(tot<mx)
   {
        ll z=pow(curr, 5);
        v.pu({z,curr});
        v.pu({-z, -curr});
        tot=z;
        curr++;
   } 
   // cout<<v.size();
   f(i,0,v.size())
   {
        f(j,0,v.size())
        {
            if(v[i].F-v[j].F==x)
            {
                cout<<v[i].S<<' '<<v[j].S<<'\n';
                return ;
            }
        }
   }
   
}

int32_t main()
{
    IOS();
   
    int tc=1;
    // cin>>tc;
    while(tc--)
        test_case();
    return 0;
}

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

int main(){
    int N,M;
    int count = 0;
    int score = 0;
    cin >> N;
    vector<string> s(N);
    for(int i=0;i<N;i++){
        cin >> s.at(i);
    }
    cin >> M;
    vector<string> t(M);
    for(int i=0;i<M;i++){
        cin >> t.at(i);
    }
    for(int i=0;i<N;i++){
        count = 0;
        for(int j=0;j<N;j++){
            if(s.at(i) == s.at(j)) count++;
        }
        for(int j=0;j<M;j++){
            if(s.at(i) == t.at(j)) count--;
        }
        score = max(score,count);
    }
    cout << score << endl;


}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define MSET(x,y) memset(x,y,sizeof(x))
#define M 
using namespace std;
int main()
{
    char in[10];
    while (~scanf("%s", in+1)) {
        sort(in+1, in+5);
        if (in[1]==in[2] && in[3]==in[4] && in[1]!=in[3])
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}


Measured memory_bytes: 256