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

int main(){
    int n;
    cin>>n;
    char s[n];
    int count=0;
    for(int i=0;i<n;i++){
        cin>>s[i];
        if(i>=2&&s[i]=='C'){
            if(s[i-2]=='A'&&s[i-1]=='B') count++;
        }
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

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

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int maxn = (int) 2e5 + 5;
int n;
vector<int> g[maxn];
int good[maxn];
char tmp[maxn];

bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < n - 1; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    v--;
    u--;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  scanf("%s", tmp);
  for (int i = 0; i < n; i++) {
    good[i] = tmp[i] - '0';
  }
  return true;
}

int d[maxn];
long long res;

int getFarthest(int v, int p) {
  int res = v;
  for (int i = 0; i < sz(g[v]); i++) {
    int u = g[v][i];
    if (u == p) {
      continue;
    }
    d[u] = d[v] + 1;
    int cur = getFarthest(u, v);
    if (d[cur] > d[res]) {
      res = cur;
    }
  }
  return res;
}

bool getPath(int v, int t, int p, vector<int> &path) {
  path.push_back(v);
  if (v == t) {
    return true;
  }
  for (int i = 0; i < sz(g[v]); i++) {
    int u = g[v][i];
    if (u == p) {
      continue;
    }
    if (getPath(u, t, v, path)) {
      return true;
    }
  }
  path.pop_back();
  return false;
}

vector<int> getCenter() {
  int v = 0;
  d[v] = 0;
  int u = getFarthest(v, -1);
  d[u] = 0;
  v = getFarthest(u, -1);
  vector<int> path;
  getPath(v, u, -1, path);
  if (sz(path) & 1) {
    return {path[sz(path) / 2]};
  } else {
    return {path[sz(path) / 2 - 1], path[sz(path) / 2]};
  }
}

int dfs(int v, int p) {
  d[v] = 0;
  int x = inf;
  for (int i = 0; i < sz(g[v]); i++) {
    int u = g[v][i];
    if (u == p) {
      continue;
    }
    x = min(x, dfs(u, v));
    d[v] = max(d[v], d[u] + 1);
  }
  if (good[v]) {
    x = 0;
  }
  if (x < inf) {
    res += d[v] - x + 1;
    x = d[v] + 1;
    if (p != -1) {
      res++;
    }
  }
  return x;
}

void solve() {
  res = 0;
  vector<int> vs = getCenter();
  if (sz(vs) == 2) {
    int v = vs[0], u = vs[1];
    g[v].erase(find(g[v].begin(), g[v].end(), u));
    g[u].erase(find(g[u].begin(), g[u].end(), v));
    if (min(dfs(v, -1), dfs(u, -1)) < inf) {
      res++;
    }
  } else {
    dfs(vs[0], -1);
  }
  printf("%lld\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 29692
import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N = INT()
A = LIST()
C = Counter(A)

cur = sum(A)
Q = INT()
for _ in range(Q):
    b, c = MAP()
    cur -= b * C[b]
    cur += c * C[b]
    print(cur)
    C[c] += C[b]
    C[b] = 0


Measured memory_bytes: 88932
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;
    int min_doller;
    cin >> min_doller;
    int ans = -2 * 1e9;
    for(int i = 1; i < n; i++){
        int doller;
        cin >> doller;
        ans = max(ans, doller - min_doller);
        min_doller = min(min_doller, doller);
    }
    cout << ans << "\n";
}


Measured memory_bytes: 3104
#include <iostream>
#include <set>
#include <vector>
using namespace std;

typedef long long ll;
set<ll> ans;

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

  for(ll i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      ll tmp = n;
      while(tmp >= i) {
	if(tmp % i == 0) {
	  tmp /= i;
	}
	else tmp %= i;

	if(tmp == 1) {
	  ans.insert(i);
	  break;
	}
      }
    }
  }
  ans.insert(n);
  if(n > 2) ans.insert(n-1);
  n--;
  for(ll i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      ans.insert(i);
      ans.insert(n / i);
    }
  }
  cout << ans.size() << endl;
}


Measured memory_bytes: 256
abcd = input()

for i in range(1 << 3):
    res = int(abcd[0])
    op = abcd[0]
    for k in range(3):
        if i >> k & 1:
            res += int(abcd[k + 1])
            op += "+" + abcd[k + 1]
        else:
            res -= int(abcd[k + 1])
            op += "-" + abcd[k + 1]
    if res == 7:
        op += "=7"
        print(op)
        break


Measured memory_bytes: 9168
import numpy as np
def dist(ax, ay, bx, by):
  ans = np.sqrt( (ax-bx)**2 +(ay-by)**2 )
  return ans

N = int(input())
xs = []
ys = []

for _ in range(N):
  x, y = map(int, input().split())
  xs.append(x)
  ys.append(y)

di2 = 0.0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    else:
      di2 += dist(xs[i], ys[i], xs[j], ys[j])

print(2.0*di2/N)

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

using namespace std;

typedef pair<int, int> P;
int INF = 1e9;

int dp[1010][1010];

int main()
{
    int n, ans = 0;
    vector<P> q;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        q.push_back(P(b, a));
    }
    for (int i = 0; i < 1005; i++)
    {
        for (int j = 0; j < 1005; j++)
        {
            dp[i][j] = INF;
        }
    }
    for (int i = 0; i < 1005; i++)
        dp[i][0] = 0;

    sort(q.begin(), q.end());
    if (q[0].second <= q[0].first)
    {
        dp[1][1] = q[0].second;
    }
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            int tmp = dp[i - 1][j - 1] + q[i - 1].second;
            if (tmp > q[i - 1].first)
            {
                tmp = INF;
            }
            dp[i][j] = min(dp[i - 1][j], tmp);
            if (dp[i][j] != INF)
            {
                ans = max(ans, j);
            }
        }
    }
    cout << ans << endl;
}


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

using namespace std;

const int Nmax = 2e5 + 10;
const int Mod = 998244353;
const int oo = 2e9;

int n, m, k;
int po[Nmax], fact[Nmax];

int Lgput(int a, int x)
{
    int p = 1;

    while(x)
    {
        if(x % 2) p = 1LL * p * a % Mod;
        a = 1LL * a * a % Mod;
        x/=2;
    }

    return p;
}

int calc(int n, int k)
{
    return 1LL * fact[n] * Lgput(fact[k], Mod - 2) % Mod * Lgput(fact[n - k], Mod - 2) % Mod;
}

int main()
{
/**
    #ifndef ONLINE_JUDGE
        ifstream cin("test.in");
        ofstream cout("test.out");
    #endif // ONLINE_JUDGE
*/

    cin >> n >> m >> k;

    po[n - 1] = m;
    for(int i = n - 2; i >= 0; i--)
        po[i] = 1LL * po[i + 1] * (m - 1) % Mod;

    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = 1LL * fact[i - 1] * i % Mod;

    long long sol = 0;

    for(int i = 0; i <= k; i++)
    {
        int v = 1LL * calc(n - 1, i) * po[i] % Mod;

        sol = sol + v;
        if(sol >= Mod) sol -= Mod;
    }

    cout << sol;
    return 0;
}


Measured memory_bytes: 5152
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int N, U, V;
vv<int> graph;
vector<int> depth, maxDepth;

void dfs_a(int v, int from, int d) {
    depth[v] = d;
    maxDepth[v] = d;
    for (int u : graph[v]) {
        if (u == from) continue;
        dfs_a(u, v, d + 1);
        maxDepth[v] = max(maxDepth[v], maxDepth[u]);
    }
}

int dfs_t(int v, int from, int t) {
    int res = maxDepth[v] - 1;
    for (int u : graph[v]) {
        if (u == from) continue;
        if (depth[u] > depth[v]) continue;
        if (t + 1 >= depth[u]) continue;
        int r = dfs_t(u, v, t + 1);
        res = max(res, r);
        break;
    }
    return res;
}

int main() {
    cin >> N >> U >> V;
    U--; V--;
    graph.resize(N);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    depth.resize(N);
    maxDepth.resize(N);
    dfs_a(V, -1, 0);

    write(dfs_t(U, -1, 0));
}

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

int main()
{
  string S; cin >> S;
  
  string ans;
  for (int i=0; i<S.size(); i++ /* i+=2 */) 
  {
    if (i %2 == 0)
    ans += S[i];
  }  
  cout << ans << endl;  
}


Measured memory_bytes: 512
N,M = [int(i) for i in input().split()]
d = []
for i in range(M):
    d.append(list(map(int, input().split())))
d = sorted(d, key=lambda x: x[0])
X=[-2,-1]
D = 0
for i in range(M):
    if X[0] < d[i][1] and d[i][0] < X[1]:
        X = [d[i][0],min(X[1],d[i][1])]
    else:
        D += 1
        X = d[i]
print(D)

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

#define lld long long

int main(){
    lld N;
    cin >> N;
    lld sum = 0;
    for(int i=0;i<N;i++){
        if((i+1)%3 != 0 && (i+1)%5 != 0){
            sum += (i+1);
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 3624
#include <stdio.h>

int main(void){
	int num, x, y, temp;
	
	scanf("%d %d", &x, &y);
	
	while(!(x == 0 && y == 0)){
		if(x > y){
			temp = x;
			x = y;
			y = temp;
		}
		printf("%d %d\n", x, y);
		scanf("%d %d", &x, &y);
	}
	
	return 0;
}

Measured memory_bytes: 600
def main():
    S = input()
    words = ["dream", "dreamer", "erase", "eraser"]
    while len(S):
        ok = False
        for w in words:
            if S.endswith(w):
                S = S[:-len(w)]
                ok = True
                break
        if not ok:
            print("NO")
            return
    print("YES")


if __name__ == "__main__":
    main()


Measured memory_bytes: 134600
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)   for(signed i=0; i<n; i++)
#define FOR(i, k, n)    for(signed i=k; i<n; i++)
#define yn(b)   cout << ((b)?"Yes":"No") << endl
#define YN(b)   cout << ((b)?"YES":"No") << endl
#define pr(r)   cout << r << endl
#define min(x,y)    (x<y)?x:y
#define max(x,y)    (x>y)?x:y
#define ll  long long
int main(void){
    int a[5], i;
    rep(i, 5) cin >> a[i];
    int b[5];
    rep(i, 5) b[i] = a[i]%10;
    sort(b, b+5);
    int r = 0;
    rep(i, 5){
        if(a[i]%10 == 0) a[i]-=10;
        r += 10*(a[i]/10+1);
    }
    i=0;
    while(1){
        if(b[i] != 0) break;
        i++;
        if(i==5){
            i=0;
            b[i] += 10;
            break;
        }
    }
    r = r - 10 + b[i];
    pr(r);
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<iomanip>
#include<algorithm>
using namespace std;
int main()
{
	/*int t; cin>>t;

	while(t--)
	{
		int c=0, st=105, end;
		string s; cin>>s; int n=s.size();
		for(int i=0; i<n; ++i)
		{
					if(s[i]=='1') {st=i; break;}
	    }
		for(int j=n-1; j>=0; --j)
		{
					if(s[j]=='1') {end=j; break;}
		}
		for(int x=st; x<=end; ++x)
		{
			if(s[x]=='0') c++;

		}
		cout<<c<<endl;
	}
*/

	//nastya and rice

	long int n, arr[200005], total=0; cin>>n;

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

	for(int i=1; i<n; ++i)
	{
		if(arr[i]<arr[i-1])
		{
			total+=abs(arr[i]-arr[i-1]);
			arr[i]+=abs(arr[i]-arr[i-1]);

		}


	}
	cout<<total<<endl;

	return 0;

}



Measured memory_bytes: 5136
#include<iostream>
using namespace std;
int main()
{
	int x,i,j;
	for(i=1;i<=9;i++){
		for(j=1;j<=9;j++){
	x=i*j;
	cout<<i<<"x"<<j<<"="<<i*j<<endl;
	
		}
	}

	return 0;
}


Measured memory_bytes: 3080
def cal(operand,a,b):
  if operand == "+":
    return int(a)+int(b)

  elif operand == "-":
    return int(a)-int(b)

  elif operand == "*":
    return int(a)*int(b)

S=[]
top=0
S = list(input().split())
stk=[]
for i in S:
    if i.isdigit() == True:
        stk.append(int(i))
    else:
          b=stk.pop()
          a=stk.pop()
          stk.append(cal(i,a,b))
    
print(stk[0])



Measured memory_bytes: 5600
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int N;
    cin >> N;
    map<string,ll> S;
    REP(i, N){
        string s;
        cin>>s;
        SORT(s);
        S[s]++;
    }

    ll ans = 0;
    for(auto&& i:S){
        ans += ((i.se-1)*i.se)/2;
    }
    pr(ans);
}

Measured memory_bytes: 11136
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
	long long n;
	scanf("%lld",&n);
	for(long long i=n;i>=0;i--)
		{
			double m;
			long long  k;
			m=sqrt(i);
			k=long(m);
			if(m==k) 
			{
				printf("%lld\n",i);
				return 0;
			}
		}
}

Measured memory_bytes: 128
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include <set>
#include <queue>
#include <iomanip>

typedef long long ll;

#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;

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 = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[510][510];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}

ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}


int main() {
	ll k;
	cin >> k;
	cin >> s;
	if (s.size() <= k) {
		cout << s << endl;
	}
	else {
		string t;
		rep(i, k) {
			t += s[i];
		}
		t += "...";
		cout << t << endl;
	}
}

Measured memory_bytes: 3720
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

Measured memory_bytes: 43340
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.HashMap;

public class Main
{
    int h, w;
    String s[] = new String[101];
    
    public static void main(String args[])
    {
	new Main().solve();
    }
    
    void solve()
    {
	in();
	
	out();
    }

    void in()
    {
	Scanner sc = new Scanner(System.in);
	h = sc.nextInt();
	w = sc.nextInt();
	for(int i = 0; i < h; i++) s[i] = sc.next();
    }

    void out()
    {
	for(int i = 0; i < h; i++) {
	    out(s[i]);
	    out(s[i]);
	}
    }
    
    void out(int n)
    {
	System.out.println(n);
    }

    void out(char c)
    {
	System.out.print(c);
    }
    
    void out(String s)
    {
	System.out.println(s);
    }
}


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

const int N = 10;

char s[N][N];
bool vis[N][N];

void no(){
	puts("Impossible");
	exit(0);
}

int main(){
	int h, w;
	scanf("%d%d", &h, &w);
	for (int i = 0; i < h; ++ i){
		scanf("%s", s[i]);
	}
	if (s[0][0] != '#' || s[h - 1][w - 1] != '#') no();
	vis[0][0] = true;
	for (int i = 0, j = 0; i < h - 1 || j < w - 1; ){
		char ch1 = i < h - 1 ? s[i + 1][j] : '.';
		char ch2 = j < w - 1 ? s[i][j + 1] : '.';
		if ((ch1 == '#') + (ch2 == '#') != 1) no();
		if (ch1 == '#') ++ i;
		else ++ j;
		vis[i][j] = true;
	}
	for (int i = 0; i < h; ++ i){
		for (int j = 0; j < w; ++ j){
			if (!vis[i][j] && s[i][j] == '#') no();
		}
	}
	puts("Possible");
	return 0;
}

Measured memory_bytes: 256
//include
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

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

//change
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

//math
template <class T>
inline T sqr(T x) { return x * x; }

template <class T>
inline T nCr(T n, T r)
{
    T num = 1;
    for (int i = 1; i <= r; ++i)
    {
        num *= (n - i + 1) / i;
    }
    return num;
}
template <class T>
inline T nPr(T n, T r)
{
    r = n - r;
    T sum = 1;
    int i;
    for (i = n; i >= r + 1; --i)
        sum *= i;
    return sum;
}

template <class T>
inline T facctorial(T k)
{
    T sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

//numeric
template <class T>
inline T gcd(T a, T b)
{
    if (a < b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return b ? gcd(b, a % b) : a;
}

template <class T>
inline T lcm(T a, T b)
{
    return a * b / gcd(a, b);
}

//typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())

//repetition
#define FOR(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)

//constant
constexpr double EPS = 1e-10;
const double PI = acos(-1.0);
constexpr LL INF = 1e10;

//clear memory
#define CLR(a) memset((a), 0, sizeof(a))

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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    vector<int> c(n - 1);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> b[i];
    }
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> c[i];
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i)
    {
        ans += b[a[i] - 1];
        if (a[i] + 1 == a[i + 1])
        {
            ans += c[a[i] - 1];
        }
    }
    ans += b[a[n - 1] - 1];
    cout << ans << endl;
}


Measured memory_bytes: 256
N = int(input())
divisors = []
for i in range(1,int(N**0.5)+1):
    #print(i)
    if N%i == 0:
        divisors.append(i)
        divisors.append(N//i)
divisors.remove(1)
ds = set(divisors)
ans = 0
for div in ds:
    if div == 1:
        continue

    if N//(div-1) == N%(div-1):
        ans += div-1
print(ans)

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

#define ll long long
#define pb push_back
#define ins insert
#define mp make_pair
#define pii pair<int, int>
#define pil pair<int, ll>
#define pib pair<int, bool>
#define SET(a, c) memset(a, c, sizeof(a))
#define MOD 1000000007
#define enld endl
#define endl "\n"
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define FOUND(u, val) u.find(val) != u.end()
#define max_self(a, b) a = max(a, b);

#include <string>
#include <vector>
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
//#include <algorithm>
//#include <set>
//#include <map>
//#include <unordered_set>
//#include <unordered_map>
//#include <cmath>
//#include <cstring>
//#include <sstream>
//#include <stack>
//#include <queue>

vector<vi> adj;
vl black, white;
void dfs(int a, int parent = 0) {
    if (adj[a].size() == 1 && a != 1) return;
    for (int b : adj[a]) {
        if (b != parent) {
            dfs(b, a);
        }
    }
    ll p1 = 1;
    ll p2 = 1;
    for (int child : adj[a]) {
        if (child == parent) continue;
        p1 = (p1 * (white[child] + black[child])) % MOD;
        p2 = (p2 * white[child]) % MOD;
    }
    white[a] = p1, black[a] = p2;
}

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

    int n;
    cin >> n;
    adj.resize(n + 1);
    black.resize(n + 1);
    white.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for (int i = 2; i <= n; i++) {
        if (adj[i].size() == 1) {
            black[i] = 1;
            white[i] = 1;
        }
    }
    dfs(1);
    // for (int i = 1; i <= n; i++) {
    //     cout << white[i] << " " << black[i] << endl;
    // }
    cout << ((white[1] + black[1]) % MOD);
}

Measured memory_bytes: 15844
#include<iostream>
#include<cstdio>
using namespace std;
int main(void)
{
    while(1)
    {
    int n;
    int nn,p1,p2;
    int sum;
    int mnn=0,mpp=0;
    
        cin >> n;
        if(n==0)break;
        for(int i = 0 ; i<n ; i++)
        {
            cin>>nn>>p1>>p2;
            sum=p1+p2;
            if(mpp<sum)
            {
                mnn = nn;
                mpp = sum;
            }
        }
        cout << mnn << " " << mpp << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


typedef long long LL;


const LL mod = 998244353;


char str[300010];

int n;


int main()
{
	scanf("%d", &n);
	scanf("%s", str + 1);
	
	LL Ans = 1;
	int R = 0, G = 0, B = 0, RG = 0, RB = 0, GB = 0;
	for (int i = 1; i <= 3*n; i++)
	{
		if (str[i] == 'R')
		{
			if (GB)
				Ans = Ans * (GB--) % mod;
			else if (G)
				Ans = Ans * (G--) % mod, RG++;
			else if (B)
				Ans = Ans * (B--) % mod, RB++;
			else R++;
		}
		else if (str[i] == 'G')
		{
			if (RB)
				Ans = Ans * (RB--) % mod;
			else if (B)
				Ans = Ans * (B--) % mod, GB++;
			else if (R)
				Ans = Ans * (R--) % mod, RG++;
			else G++;
		}
		else
		{
			if (RG)
				Ans = Ans * (RG--) % mod;
			else if (G)
				Ans = Ans * (G--) % mod, GB++;
			else if (R)
				Ans = Ans * (R--) % mod, RB++;
			else B++; 
		}
	}
	
	for (int i = 1; i <= n; i++)
		Ans = Ans * i % mod;
	
	printf("%lld\n", Ans);
}

Measured memory_bytes: 512
from sys import stdin
readline=stdin.readline
N,M,K=map(int,readline().split())
mod=998244353

fact=[1]*(N+1)
finv=[1]*(N+1)
inv=[1]*(N+1)
inv[0]=0
for i in range(2,N+1):
    fact[i]=(fact[i-1]*i%mod)
    inv[i]=(-inv[mod%i]*(mod//i))%mod
    finv[i]=(finv[i-1]*inv[i])%mod

def com(N,K,mod):
    if (K<0) or (N<K):
        return 0
    return fact[N]*finv[K]*finv[N-K]%mod

ans=0
for x in range(K+1):
    ans+=com(N-1,x,mod)*M*pow(M-1,N-x-1,mod)
    ans%=mod

print(ans)

Measured memory_bytes: 32636
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n, m = 1;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    for(int i = 0; i < n; i++){
        if(a[i] == m){
            m++;
        }
    }
    cout << (m == 1 ? -1 : n - m + 1) << endl;
    return 0;
}

Measured memory_bytes: 1024
from heapq import heapify, heapreplace

n, m = list(map(int, input().split()))
aaa = [-a for a in map(int, input().split())]
heapify(aaa)

for _ in range(m):
    heapreplace(aaa, aaa[0] // 2 + aaa[0] % 2)

print(-sum(aaa))


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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll calc(string s, ll bit) {
    ll n = s.length();
    ll m = s[0] - '0';
    ll ret = 0;
    REP(i, s.length() - 1) {
        if ((bit >> i) & 1) {
            ret += m;
            m = 0;
        }
        m = m * 10 + s[i + 1] - '0';
    }
    return ret + m;
}

int main() {
    string S;
    cin >> S;
    ll N = S.length();
    ll ans = 0;
    REP(i, pow(2LL, N - 1)) {
        ans += calc(S, i);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  
  int a[4][3][10], n;
  int i, j, k, l;
  int b, f, r, v;
  for(i = 0; i < 4; i++) {
    for(j = 0; j < 3; j++) {
      for(k = 0; k < 10; k++) {
	a[i][j][k] = 0;
      }
    }
  }
  
  scanf("%d", &n);
  
  for(l = 0; l < n; l++) {
    scanf("%d %d %d %d", &b, &f, &r, &v);
    a[b-1][f-1][r-1] += v;
  }
  for(i = 0; i < 4; i++) {
    for(j = 0; j < 3; j++) {
      for(k = 0; k < 10; k++) {
	printf(" %d", a[i][j][k]);
      }
      printf("\n");
    }
    
    if(i < 3) {
      printf("####################");
    }
    if(i < 3) {
      printf("\n");
    }
  }
  
  return 0;
}

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

int main(){
  	int d;
    cin >> d;
  
 	if(d == 25)
      	cout << "Christmas" << endl;
  	if(d == 24)
      	cout << "Christmas Eve" << endl;
  	if(d == 23)
      	cout << "Christmas Eve Eve" << endl;
  	if(d == 22)
      	cout << "Christmas Eve Eve Eve" << endl;
    return 0;
}

Measured memory_bytes: 256
def prime(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i] and i!=1:
      f=False
      break
    mm[i]=1
    si=i**0.5
    for j in range(168):
      if p[j]>si:
        break
      if i%p[j]==0 and i!=p[j]:
        if mm[p[j]]:
          f=False
          break
        mm[p[j]]=1
        t=i//p[j]
        if mm[t] and t!=p[j]:
          f=False
          break
        mm[t]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")
      

Measured memory_bytes: 207996
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <cstdlib>

using std::pair;
typedef pair<int,int> pii;
const int N = 200010;
const int M = 19;
int _w;

int max( int a, int b ) {
	return a > b ? a : b;
}

int n, v, x[N], m;

int ans[N];
void answer() {
	for( int i = 1; i <= n; ++i )
		puts( ans[i] ? "Possible" : "Impossible" );
	exit(0);
}

int R[M][N];
void prelude() {
	int t = v;
	for( m = 0; ; ++m, t >>= 1 ) {
		R[m][n] = R[m][n+1] = n;
		for( int j = n-1; j >= 1; --j )
			if( x[j+1] - x[j] > t )
				R[m][j] = j;
			else R[m][j] = R[m][j+1];
		if( !t ) break;
	}
	++m;
}

int f[1<<M];
bool check( int l, int r ) {
	memset(f, 0, sizeof f);
	if( l == 1 ) f[0] = r;
	for( int i = 0; i < (1<<m); ++i )
		for( int j = 1; j < m; ++j )
			if( (i&(1<<j)) == 0 ) {
				int k = i|(1<<j);
				f[k] = max( f[k], R[j][f[i]+1] );
				if( f[k] >= l-1 && f[k] <= r )
					f[k] = r;
			}
	return f[(1<<m)-2] == n;
}

void solve() {
	static pii tmp[N];
	static int tn;
	for( int i = 1; i <= n; i = R[0][i]+1 )
		tmp[tn++] = pii(i, R[0][i]);
	if( tn > m ) answer();
	for( int i = 0; i < tn; ++i )
		if( check(tmp[i].first, tmp[i].second) ) {
			for( int j = tmp[i].first; j <= tmp[i].second; ++j )
				ans[j] = 1;
		}
	answer();
}

int main() {
	_w = scanf( "%d%d", &n, &v );
	for( int i = 1; i <= n; ++i )
		_w = scanf( "%d", x+i );
	prelude(), solve();
	return 0;
}


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

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

 if(k <= a){
 cout << a - k << ' ' << b <<endl;
 }else if(k <= a+b){
 cout << 0 << ' ' << b - (k-a) <<endl;
 }else{
 cout << 0 << ' ' << 0 <<endl;
 }
 }


Measured memory_bytes: 256
X = int(input())

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

prime_list = primes(100100)

for i in prime_list:
    if X <= i:
        print(i)
        exit()



Measured memory_bytes: 4148
#include <iostream>
#include <cstdio>
#include <cmath>

int main(){
  double x1, y1, x2, y2;
  double dist;
  std::cin >> x1 >> y1 >> x2 >> y2;

  dist = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

  printf("%.8lf\n", dist);
}



Measured memory_bytes: 3196
#include <iostream>
using namespace std;
int bubbleSort(int A[],int N){
  int sw=0;
  bool flag=1;
  for(int i=0;flag;i++){
    flag=0;
    for(int j=N-1;j>=i+1;j--){
      if (A[j]<A[j-1]){
	swap(A[j],A[j-1]);
	flag=1;
	sw++;
      }
    }
  }
  return sw;
}
int main(){
  int A[100],N,sw;
  cin>>N;
  for(int i=0;i<N;i++)cin>>A[i];
  sw=bubbleSort(A,N);
  for(int i=0;i<N;i++){
    if(i) cout<<" ";
    cout <<A[i];
  }
  cout <<endl;
  cout<<sw<<endl;
  return 0;
}



Measured memory_bytes: 3096
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	char A, B, C;
	cin>>A>>B>>C;
	if((int) A + (int) B + (int) C == 161)
	{
		cout<<"YES"<<endl;
	}
	else
		cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
num_restaurants = int(input())
restaurants = [input().split() for _ in range(num_restaurants)]
city_restaurant = dict()
cities = set()
for idx, i in enumerate(restaurants):
    if i[0] in cities:
        city_restaurant[i[0]].append((int(i[1]), idx + 1))
    else:
        city_restaurant[i[0]] = [(int(i[1]), idx + 1)]
        cities.add(i[0])
cities = sorted(list(cities))
for i in cities:
    for j in reversed(sorted(city_restaurant[i], key=lambda x: x[0])):
        print(j[1])


Measured memory_bytes: 3064
n=gets.to_i-1
a=gets.split.map &:to_i
c=0
(0..n).map{|i|m=i
(m..n).map{|j|a[m]>a[j]&&m=j}
a[i],a[m]=a[m],a[i]
i!=m&&c+=1}
puts a*" ",c

Measured memory_bytes: 6148
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <numeric>
#include <set>
#include <list>
#include <valarray>
#include <functional>
#include <array>

int main() {
	int a,b;
	std::cin >> a >> b;
	if (a + b >= 10)
		std::cout << "error" << std::endl;
	else
		std::cout << a + b << std::endl;
}



Measured memory_bytes: 256
N = gets.to_i
H = gets.chomp.split(" ").map(&:to_i)

ans = 'Yes'
(N - 2).downto(0){|i|
  (ans = 'No'; break) if H[i] - H[i + 1] > 1
  H[i] -= 1 if H[i] - H[i + 1] == 1
}

puts ans


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

int main() {
	int n, q;
	string s;
	cin >> n >> s >> q;
	set<int> st[26];
	for (int i = 0; i < n; i++) {
		int c = s[i] - 'a';
		st[c].insert(i);
	}
	for (int k = 0; k < q; k++) {
		int type;
		cin >> type;
		if (type == 1) {
			int i;
			char c;
			cin >> i >> c;
			i--;
			int next_c = c - 'a';
			int prev_c = s[i] - 'a';
			if (prev_c == next_c) continue;
			s[i] = c;
			st[prev_c].erase(i);
			st[next_c].insert(i);
		} else {
			int l, r;
			cin >> l >> r;
			l--; r--;
			int ans = 0;
			for (int j = 0; j < 26; j++) {
				auto itr = st[j].lower_bound(l);
				if (itr == st[j].end()) continue;
				if (*st[j].lower_bound(l) <= r) ans++;
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 24196
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define rrep(i,n,a) for(int i=n;i>=a;i--)
#define FOR(i,n) for(int i=0;i<n;i++)
#define all(s) s.begin(),s.end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define pcnt(n) __builtin_popcount(n)
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const double PI = acos(-1);

int lcm(int a,int b){
    return ((b/__gcd(a,b))*a);
}
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int x;
    cin>>x;
    cout<<lcm(x,360)/x;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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 (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin>>S;
    int N = S.size();
    bool yes=true;
    if (S[0]=='0' || S[N-2]=='0' || S[N-1]=='1') yes=false;
    rep(i,(N-1)/2){
        if (S[i]!=S[N-2-i]) yes=false;
    }
    if (!yes){
        cout<<"-1\n";
        return 0;
    }
    int cur=2, ms=1;
    rep(i,N-1){
        cout<<ms<<" "<<cur<<"\n";
        if (S[i]=='1') ms=cur;
        cur++;
    }
    return 0;
}


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

using namespace std;

string s;
int v = 1;

int main()
{
	cin >> s;
	if(s[s.size() - 1] == '1' || s[0] == '0')
		return cout << -1 , 0;
	for(int i = 0 ; i < s.size() - 1 ; i++)
		if(s[i] != s[s.size() - 2 - i])
			return cout << -1 , 0;
	for(int i = 0 ; i < s.size() - 1 ; i++)
	{
		cout << v << " " << i + 2 << endl;
		if(s[i] == '1')
			v = i + 2;
	}
	/*
	if(s[0] == '1' && s[1] == '1')
	{
		for(int i = 1 ; i < s.size() ; i++)
			cout << i << " " << i + 1 << endl;
	}
	else
	{
		for(int i = 2 ; i <= s.size() ; i++)
			cout << 1 << " " << i << endl;
	}*/
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
// #include <numeric>
#include <complex>
#include <tuple>

#define FAST ios_base::sync_with_stdio(false); cin.tie(0)
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define repr(i, a, b) for(int i=int(a); i>=int(b); i--)
#define reps(i,n) for(int i=1;i<=int(n);++i)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define iceil(x,y) (x+y-1)/y
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define all(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

int gcd(int a,int b){return b?gcd(b,a%b):a;}

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII> PP;

int d;

int main()
{
	FAST;

	cin >> d;

	if (d==25) cout << "Christmas\n";
	else if (d==24) cout << "Christmas Eve\n";
	else if (d==23) cout << "Christmas Eve Eve\n";
	else if (d==22) cout << "Christmas Eve Eve Eve\n";

	return 0;
}

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

const int INF = 100000000;

int main(){
  int n;
  cin >> n;
  vector<int> h(n);
  rep(i,n) cin >> h[i];

  vector<int> dp(n,0);
  rep(i,n){
    int d,dd;

    if(i==0) continue;
    if(i==1){
      dp[i] = abs(h[i] - h[i-1]);
      continue;
    }
    if(i-1>=0) d = dp[i-1] + abs(h[i]-h[i-1]);
    if(i-2>=0) dd = dp[i-2] + abs(h[i]-h[i-2]);

    dp[i] = min(d,dd);
  }

  cout << dp[n-1] << endl;

  return 0;
}

Measured memory_bytes: 3944
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<bitset>
using namespace std;

const int inf = 1001001000;

int TSP(int bit,int v, vector<vector<int>> &dist, vector<vector<int>> &dp){
	if (dp[bit][v] >= 0) return dp[bit][v];
	if (bit == ((1 << dist.size()) - 1) && v == 0) {
		dp[bit][v] = 0;
		return dp[bit][v];
	}
	int res = inf;

	for (int u = 0; u < dist.size(); u++){
		if ((bit>>u&1) == 0) {
			res = min(res,TSP((bit|(1<<u)),u,dist,dp) + dist[v][u]);
		}
	}
	dp[bit][v] = res;
	return dp[bit][v];
}
int main(){
	int v, e; cin >> v >> e;
	vector<vector<int>> dist(v,vector<int>(v,inf));
	vector<vector<int>> dp((1 << v),vector<int>(v,-1));
	for (int i = 0; i < e; i++){
		int s, t, d; cin >> s >> t >> d;
		dist[s][t] = d;
	}

	int ans = TSP(0,0,dist,dp);
	
	if (ans == inf) cout << -1 << endl;
	else cout << ans << endl;


	return 0;
}




Measured memory_bytes: 6312
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;

int main(){
	int n, k, r;
	bool bunny[51][51];
	map<int, int> b;
	
	for(int i=0; i<=50; ++i)
	for(int j=0; j<=50; ++j)
	bunny[i][j]=false;
	
	scanf(" %d %d", &n, &k);
	for(int i=0; i<k; ++i){
		int m;
		scanf(" %d", &m);
		for(int j=0; j<m; ++j){
			int p;
			scanf(" %d", &p);
			b[p]=i;
		}
				
	}
	
	int bad[51]={0};
	
	scanf(" %d", &r);
	for(int i=0; i<r; ++i){
		int p, q;
		scanf(" %d %d", &p, &q);
		if(b[p]==b[q]){
			bad[p]=1;	
			bad[q]=1;
		}
	}
	
	int ans=0;
	for(int i=1; i<=50; ++i) ans+=bad[i];
	printf("%d\n", ans);
}

Measured memory_bytes: 1196
'use strict'
function Main(input){
  input=input.split('\n');
  input[0]=input[0].split(' ');
  var N=parseInt(input[0].shift());
  var M=parseInt(input[0].shift());
  input.shift();
  var K=[];
  var ninzu=[];
  for(let i=0;i<M;i++){
    ninzu[i]=0;
  }
  for(let i=0;i<N;i++){
    input[i]=input[i].split(' ');
    K[i]=parseInt(input[i].shift());
    for(let j=0;j<K[i];j++){
      ninzu[parseInt(input[i][j])-1]++;
    }
  }
  var counter=0;
  for(let i=0;i<M;i++){
    if(ninzu[i]===N)counter++;
  }
  console.log(counter);
} 

Main(require('fs').readFileSync('/dev/stdin','utf8'));

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

#define ED return 0;
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define MAX 99999999

int main(){
    int K, S;
    long int count = 0;
    cin >> K >> S;
    for(int a = 0;a <= K;a++){
        for(int b = 0;b <= K;b++){
            if(S - (a + b) <= K && a + b <= S){
                count++;
            }
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
N,M=map(int,input().split())
AB=[0]*N
for i in range(N):
  AB[i]=list(map(int,input().split()))
AB.sort()
cost=0
for i in AB:
  if M>=i[1]:
    cost += i[0]*i[1]
    M-=i[1]
  else:
    cost += i[0]*M
    M -= M
  if M==0:
    break
print(cost)

Measured memory_bytes: 27876
import java.util.Scanner;

public class Main {

	public static void main (String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int k = scan.nextInt();
		int result = k;
		for(int i=1; i<n; i++)result *= k-1;
		System.out.println(result);
	}

}

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

long long pow2(int n) {
	return (1ll << n);
}

long long num_of_ones(long long x, int d) {
	long long a = pow2(d), b = pow2(d+1);
	return x / b * a + x % b / a * (x%a + 1);
}

long long xor_sum(long long x) {
	long long res = 0;
	for (int d = 0; d < 60; d++) {
		if (num_of_ones(x,d) % 2 == 1) res += pow2(d);
	}
	return res;
}

int main() {
	long long a, b;
	cin >> a >> b;
	long long ans;
	if (a == 0) ans = xor_sum(b);
	else ans = xor_sum(b) ^ xor_sum(a-1);
	cout << ans << endl;
	return 0;
}

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

long t[444444];
int main() {
	const int p = 998244353;
	int n;
	string x;
	cin >> n >> x;
	int y = 0;
	for (int i = 1; i <= n + n; i++) {
		if (i % 2 == 0)
			y = (y * 2 + x[i / 2 - 1] - '0') % p;
		if (n * 2 % i || n % i == 0)
			continue;
		int b = 1;
		for (int j = 0; j < n; j++) {
			int z = x[j % (i / 2)] ^ j / (i / 2) & 1;
			if (x[j] != z) {
				b = x[j] > z;
				break;
			}
		}
		t[i] = (y + b) % p;
	}
	for (int i = 1; i <= n + n; i++) {
		if (n * 2 % i || n % i == 0)
			continue;
		for (int j = i * 3; j <= n + n; j += i + i)
			if (n * 2 % j == 0)
				(t[j] += p - t[i]) %= p;
	}
	long r = 0;
	for (int i = 1; i <= n + n; i++) {
		if (n * 2 % i || n % i == 0)
			continue;
		(r += t[i] * i) %= p;
	}
	cout << r << endl;
	return 0;
}


Measured memory_bytes: 644
number = int(input())
dict = {}
for x in ["S","H","C","D"]:
        dict[x] = [i for i in range(1,14)]
for i in range(number):
    x,y = map(str,input().split())
    dict[x].remove(int(y))
for x in ["S","H","C","D"]:
    for i in dict[x]:
        print(x,i)

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

struct Doll{
  int h, r;
};

int lis(Doll d1[], Doll d2[], int n, int m) {
  int size = n+m*(n+1)+1;
  int L[size];
  Doll A[size];
  int p = 1;
  A[0].h = A[0].r = 0;
  for(int i = 0; i <= n; i++) {
    for(int j = 0; j < m; j++) {
      A[p++] = d2[j];
    }
    if(i == n) break;
    A[p++] = d1[i];
  }
  for(int i = 0; i < size; i++) {
    L[i] = 0;
  }

  for(int i = 1; i < size; i++) {
    for(int j = 0; j < i; j++) {
      if(A[j].h < A[i].h && A[j].r < A[i].r && L[j]+1 > L[i]) {
	L[i] = L[j] + 1;
      }
    }
  }

  int ans = 0;
  for(int i = 0; i < size; i++) {
    if(L[i] > ans) ans = L[i];
  }
  return ans;
}

int main() {
  while(1) {
    int n, m;

    cin >> n;
    if(n == 0) break;
    Doll d1[n];
    for(int i = 0; i < n; i++) cin >> d1[i].h >> d1[i].r;

    cin >> m;
    Doll d2[m];
    for(int i = 0; i < m; i++) cin >> d2[i].h >> d2[i].r;

    cout << lis(d1, d2, n, m) << endl;
  }
  return 0;
}

Measured memory_bytes: 952
n = input().split()
A = int(n[0])
B = int(n[1])
K = int(n[2])
yAArr = []
yBArr = []
pubArr = []
# AとBの公約数を調べる
for i in range(1,A):
   if A % i == 0:
       yAArr.append(i)
yAArr.append(A)
for i in range(1,B):
    if B % i == 0:
        yBArr.append(i)
yBArr.append(B)

pubArr = list(set(yAArr) & set(yBArr))
pubArr = sorted(pubArr, reverse=True)

for i, name in enumerate(pubArr):
    if i + 1 == K:
        print(pubArr[i])
        break

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

int main() {
	int A, B, C, X, Y; cin >> A >> B >> C >> X >> Y;
	int M=min(X, Y);
	if(A+B<2*C){
	    cout << A*X + B*Y << endl;
	} 
	else{
	    int D=2*C*M;
	    D += min(A, 2*C)*(X-M)+min(B, 2*C)*(Y-M);
	    cout << D << endl;
	}
	return 0;
}


Measured memory_bytes: 256