akhauriyash/Code-Regression huggingface dataset:
n = int(input())
a = list(map(int, input().split()))

def insertion_sort(a, n):
    print(" ".join(map(str, a)))
    for i in range(1, n):
        v = a[i]
        j = i - 1
        
        while j >= 0 and a[j] > v:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v
        
        print(" ".join(map(str, a)))

insertion_sort(a=a, n=n)


"""
1 insertionSort(A, N) // N個の要素を含む0-オリジンの配列A
2   for i が 1 から N-1 まで
3     v = A[i]
4     j = i - 1
5     while j >= 0 かつ A[j] > v
6       A[j+1] = A[j]
7       j--
8     A[j+1] = v
"""


Measured memory_bytes: 5616
n=input().split()
row=int(n[0])
column=int(n[1])
pounce=[]
for i in range(row):
    lone=input()
    pounce.append([lone[k] for k in range(column)])
for i in range(row):
    for j in range (column):
        count=0
        if pounce[i][j]!='#':
            for z in [i-1,i,i+1]:
                for y in [j-1,j,j+1]:
                    if y>-1 and y<column and z>-1 and z<row:
                        if pounce[z][y]=='#':
                            count+=1
            pounce[i][j]=count
for i in range(row):
    for j in range(column):
        print(pounce[i][j],end='')
    print("")

Measured memory_bytes: 3444
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll INF = (ll)2e9;
const int N = 500500;
int n, q;
int m;

struct Edge
{
	int v, u;
	ll w;

	Edge() : v(), u(), w() {}
	Edge (int _v, int _u, ll _w) : v(_v), u(_u), w(_w) {}

	bool operator < (const Edge &e) const
	{
		return w < e.w;
	}
};

Edge ed[N];
ll a[N];

int par[N];
int sz[N];

int getPar(int v)
{
	return (par[v] == -1 ? v : par[v] = getPar(par[v]));
}
bool unite(int v, int u)
{
	v = getPar(v);
	u = getPar(u);
	if (v == u) return false;
	if (sz[v] < sz[u]) swap(v, u);
	sz[v] += sz[u];
	par[u] = v;
	return true;
}

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

	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++)
		a[i] = INF;
	while(q--)
	{
		int v, u;
		ll w;
		scanf("%d%d%lld", &v, &u, &w);
		ed[m++] = Edge(v, u, w);
		a[v] = min(a[v], w + 1);
		a[u] = min(a[u], w + 2);
	}
	for (int k = 0; k < 2; k++)
	{
		a[0] = min(a[0], a[n - 1] + 2);
		for (int i = 1; i < n; i++)
			a[i] = min(a[i], a[i - 1] + 2);
	}
	for (int i = 0; i < n; i++)
		ed[m++] = Edge(i, (i + 1) % n, a[i]);
	sort(ed, ed + m);
	for (int i = 0; i < n; i++)
	{
		par[i] = -1;
		sz[i] = 1;
	}
	ll ans = 0;
	for (int i = 0; i < m; i++)
		if (unite(ed[i].v, ed[i].u))
			ans += ed[i].w;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 11264
#include <bits/stdc++.h>
using namespace std;
int N,ans;
int m[2][111];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>N;
    for(int j=0;j<2;j++){
        for(int i=0;i<N;i++){
            cin>>m[j][i];
        }
    }
    for(int i=0;i<N;i++){
        int cnt=0;
        for(int j=0;j<=i;j++)cnt+=m[0][j];
        for(int j=i;j<N;j++)cnt+=m[1][j];
        ans=max(ans,cnt);
    }
    cout<<ans<<'\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll, ll> PLL;
#define chmax(x, y) do { x = max(x, y); } while(0)
#define chmin(x, y) do { x = min(x, y); } while(0)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) \
  for (ll i = static_cast<ll>(a); i < static_cast<ll>(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, ) (__VA_ARGS__)  // NOLINT
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;

ll N, Q;
string s;
char t[300000];
char d[300000];

bool check_l(ll m) {
  if (m <= -1) return true;
  if (m >= N) return false;
  rep(i, Q) {
    if (s[m] != t[i]) continue;
    if (d[i] == 'R') m++;
    if (d[i] == 'L') m--;
    if (m == -1) return true;
    if (m == N) return false;
  }
  return false;
}

bool check_r(ll m) {
  if (m <= -1) return false;
  if (m >= N) return true;
  rep(i, Q) {
    if (s[m] != t[i]) continue;
    if (d[i] == 'R') m++;
    if (d[i] == 'L') m--;
    if (m == -1) return false;
    if (m == N) return true;
  }
  return false;
}

signed main() {
  cin >> N >> Q >> s;
  rep(i, Q) {
    cin >> t[i] >> d[i];
  }

  ll p, q;
  {
    // 左端から落ちるならok
    ll ok = -1, ng = N;
    while (ok+1 < ng) {
      ll m = (ok + ng) / 2;
      (check_l(m) ? ok : ng) = m;
    }
    p = ok;
    // cout << "p = " << p << endl;
  }
  {
    // 右端から落ちるならok
    ll ok = N, ng = -1;
    while (ng+1 < ok) {
      ll m = (ok + ng) / 2;
      (check_r(m) ? ok : ng) = m;
    }
    q = ok;
    // cout << "q = " << q << endl;
  }
  cout << max(0LL, q - p - 1) << endl;

  return 0;
}


Measured memory_bytes: 1028
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100+7;
const int INF = 2e3+7;
int m[MAXN][MAXN];
int sum;
set<int> notin;
set<int> isin;
bool visit[MAXN];
void printset(set<int> r)
{

    for(set<int>::iterator it = r.begin(); it != r.end(); it++)
    {
        printf("%d,", *it);
    }
    printf("\n");
}
void prim(int root)
{
    isin.insert(root);
    notin.erase(root);
    visit[root] = true;
    while(!notin.empty())
    {
        int u;
        int min_e = INF;
        for(set<int>::iterator it = isin.begin(); it!=isin.end(); it++)
        {
            int r = *it;
            int i;
            for(set<int>::iterator it2 = notin.begin(); it2!=notin.end(); it2++)
            {
                int h = *it2;
                if(m[h][r]<min_e && m[h][r]!=-1 && visit[h] == false)
                {
                    min_e = m[h][r];
                    u = h;
                }

            }
        }
        isin.insert(u);
        notin.erase(u);
        visit[u] = true;
        sum+=min_e;
    }
}
int main()
{
//    freopen("../in.txt", "r", stdin);
    memset(visit, false, sizeof(visit));
    int n;
    scanf("%d", &n);
    int i, j;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            scanf("%d", &m[i][j]);
        }
        notin.insert(i);

    }
    sum = 0;
    prim(0);
    printf("%d\n", sum);
    return 0;
}



Measured memory_bytes: 3264
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
# from bisect import *
# from collections import *
# from heapq import *
# import functools
# import itertools
# import math
INF = 500000
MOD = 10**9+7

a, b, k = map(int, input().split())
print(max(0, a-k), max(0, b-max(0, k-a)))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(v) v.begin(), v.end()
#define allg(v) v.begin(), v.end(), greater<int>()



signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string s;
  int a, b, c;
  cin >> a >> b >> c;
  bool ans = false;
  
  for(int i = 1; i <= 180000000; i++) {
    if((i*a) %b == c) {
      ans = true;
      break;
    }
  }  
  
  cout << ( ans ?"YES" :"NO") << "\n";
  
}

Measured memory_bytes: 256
function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0]);
  var p = input[1].split(" ").map(i => parseInt(i));
  var psort = [...p];
  psort.sort(function(a,b){return a-b});
  var cnt=0;
  for(var i =0;i<N;i++){
    if(p[i]!=psort[i]){
      cnt++;
    }
  }
  var ans = "NO";
  if(cnt==0||cnt==2){
    var ans ="YES";
  }

  console.log('%s', ans);
  return ans;
}

function debug(n){
  var input = document.getElementById("input"+n).value;
  var ans=Main(input);
  var result="WA";
  if(ans==document.getElementById("output"+n).value.split("\n")[0]){
    result="AC";
  }
  document.getElementById("result"+n).innerHTML=result;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

bool D[15];

bool solve(ll n)
{
    while (n > 0)
    {
        if (D[n % 10])
            return false;
        n /= 10;
    }
    return true;
}

int main()
{
    ll N, K;
    cin >> N >> K;
    memset(D, 0, sizeof(D));
    REP(i, K)
    {
        ll d;
        cin >> d;
        D[d] = true;
    }
    while (true)
    {
        if (solve(N))
            break;
        N++;
    }
    cout << N << endl;
    return 0;
}

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


int main()
{
    int n; cin>>n;
    vector<int> r(n); for(auto& e: r) cin>>e;

    vector<double> x;
    x.push_back(r[0]);

    for(int i=1; i<n; ++i) {
        double t=r[i];
        for(int j=0; j<i; ++j) {
#define s(x) ((x)*(x))
            double d=sqrt(s(r[i]+r[j])-s(r[i]-r[j]));
            t=max(t, d+x[j]);
        }
        x.push_back(t);
    }
    double res=0;
    for(int i=0; i<n; ++i) res=max(res, x[i]+r[i]);
    printf("%.9f\n", res);
}

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

typedef double du ;
typedef string st ;
typedef long long ll ;
typedef long double ld ;
typedef long long int lli ;

#define vi vector <lli>
#define loop(num) for (lli i = 0 ; i < num ; i ++ )
#define loopcin(num , ar ) for (lli i = 0 ; i < num ; i ++ ) {cin >> ar [i] ;}
#define loopcout(num , ar) for (lli i = 0 ; i < num ; i ++ ) {cout << ar [i] << ' '; }

#define forr(num1 , num2) for (lli i = num1 ; i < num2 ; i ++ )
#define forrcin(num1 , num2 , ar ) for (lli i = num1 ; i < num2 ; i ++ ) {cin >> ar [i] ;}
#define forrcout(num1 , num2 , ar) for (lli i = num1 ; i < num2 ; i ++ ) {cout << ar [i] << ' '; }

#define D2forrcin(num1_1 , num1_2 , num2_1 , num2_2 , A ) for (lli i = num1_1 ; i < num1_2 ; i ++){ for (lli j = num2_1 ; j < num2_2 ; j++){cin >> A[i][j] ;}}
#define D2forrcout(num1_1 , num1_2 , num2_1 , num2_2 , A ) for (lli i = num1_1 ; i < num1_2 ; i ++){ for (lli j = num2_1 ; j < num2_2 ; j++){cout << A[i][j] << ' ' ;}cout << endl ;}

#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

#define F first
#define S second

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int main ()
{
    fastio
    st s[3] ; 
  loopcin (3 , s);
  loop(3)
    cout << s[i][0];
    return 0 ;
}

/*___________________________________________________________________functions___________________________________________________________________________*/



Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
using namespace std;

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

#define yes cout << "yes" << endl;
#define Yes cout << "Yes" << endl;
#define YES cout << "YES" << endl;

#define no cout << "no" << endl;
#define No cout << "No" << endl;
#define NO cout << "NO" << endl;

#define ll long long

int main() {
    ll N, K;
    cin >> N >> K;
    if (N >= K) {
        if (N % K < K - (N % K)) {
            cout << N % K << endl;
        } else {
            cout << K - (N % K) << endl;
        }
    } else {
        if (N < abs(N - K)) {
            cout << N << endl;
        } else {
            cout << abs(N - K) << endl;
        }
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int sz=1<<20;
const int inf=2e9+7;
const int mod=1e9+7;
const double pi=acos(-1);
int n,cnt[5],a[maxn],b[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-b-1;
    for(int i=m+1;i<=3;i++) b[i]=-1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==b[1]) cnt[1]++;
        if(a[i]==b[2]) cnt[2]++;
        if(a[i]==b[3]) cnt[3]++;
    }
    if(m==1&&b[1]==0) printf("Yes\n");
    else if(m==2&&(cnt[1]<<1)==cnt[2]&&b[1]==0) printf("Yes\n");
    else if(m==3&&cnt[1]==cnt[2]&&cnt[2]==cnt[3]&&(b[1]^b[2]^b[3])==0) printf("Yes\n");
    else printf("No\n");
    return 0;
}

Measured memory_bytes: 1024
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	dp = [INF for _ in range(n)]
	dp[0] = 0
	dp[1] = abs(A[0] - A[1])
	for i in range(2, n):
		dp[i] = min(dp[i], 
					dp[i-2] + abs(A[i-2]-A[i]),
					dp[i-1] + abs(A[i-1]-A[i])
					)
	print(dp[-1])
	stdout.close()

if __name__ == "__main__":
	main()

Measured memory_bytes: 91216
s=list(input())
if s[0]!='A':
    print('WA')
else:
    if s.count('C')!=1:
        print('WA')
    else:
        if s.index('C')<2 or s.index('C')>len(s)-2:
            print('WA')
        else:
            s.remove('A')
            s.remove('C')
            count=0
            for i in range(len(s)):
                if str.islower(s[i]):
                    count+=1
            if count==len(s):
                print('AC')
            else:
                print('WA')

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

int main() {
	string O, E;
	cin >> O >> E;
	string A;
	if (O.length()==E.length()){
	    for (int i=0; i<O.length(); i++){
	    A+=O.at(i);
	    A+=E.at(i);
	    }
	}
	else {
	    for (int i=0; i<E.length(); i++){
	    A+=O.at(i);
	    A+=E.at(i);
	    }
	    A+=O.at(O.length()-1);
	}
	cout << A << endl;
}


Measured memory_bytes: 256
S = gets.chomp
N = S.size

OI = N.times.map { |i| i % 2 }.join

match_cnt = 0
unmatch_cnt = 0
S.size.times do |i|
  if S[i] == OI[i]
    match_cnt += 1
  else
    unmatch_cnt += 1
  end
end

puts [match_cnt, unmatch_cnt].min


Measured memory_bytes: 2940
#include<stdio.h>
#include<string.h>
int main()
{
	char k[10004];
	int d;
	scanf("%s%d", k, &d);
	long long int p = 1e9 + 7;
	long long int dp[2][2][10004][102];
	int i, j, l;
	for (i = 0; i < 10004; i++)
		for (j = 0; j < 102; j++)
			dp[0][0][i][j] = dp[0][1][i][j] = dp[1][0][i][j] = dp[1][1][i][j] = 0;
	dp[1][0][0][0] = dp[1][1][0][0] = 1;
	int n = strlen(k);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < 10; j++)
		{
			if (j < k[i] - '0')
			{
				for (l = 0; l < d; l++)
				{
					dp[0][1][i + 1][(l + j) % d] = (dp[0][1][i + 1][(l + j) % d] + dp[0][0][i][l]) % p;
					dp[0][1][i + 1][(l + j) % d] = (dp[0][1][i + 1][(l + j) % d] + dp[1][0][i][l]) % p;
				}
			}
			else if (j == k[i] - '0')
			{
				for (l = 0; l < d; l++)
				{
					dp[0][1][i + 1][(l + j) % d] = (dp[0][1][i + 1][(l + j) % d] + dp[0][0][i][l]) % p;
					dp[1][1][i + 1][(l + j) % d] = (dp[1][1][i + 1][(l + j) % d] + dp[1][0][i][l]) % p;
				}
			}
			else
			{
				for (l = 0; l < d; l++)
					dp[0][1][i + 1][(l + j) % d] = (dp[0][1][i + 1][(l + j) % d] + dp[0][0][i][l]) % p;
			}
		}
		for (l = 0; l < d; l++)
		{
			dp[0][0][i + 1][l] = dp[0][1][i + 1][l];
			dp[1][0][i + 1][l] = dp[1][1][i + 1][l];
		}
	}
	printf("%lld\n", (dp[1][0][n][0] + dp[0][0][n][0] - 1 + p) % p);
	return 0;
}

Measured memory_bytes: 32128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CF2016
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            int H = int.Parse(str[0]);
            int W = int.Parse(str[1]);
            int[] n = new int[26];
            for(int i = 0; i < H; i++)
            {
                string s = Console.ReadLine();
                for(int j = 0; j < W; j++)
                {
                    n[s[j] - 'a']++;
                }
            }
            int x = 0;
            int f = 0;
            if (H % 2 == 0 && W % 2 == 0)
            {
                for(int i = 0; i < 26; i++)
                {
                    if (n[i] % 4 != 0)
                    {
                        f++;
                        break;
                    }
                }
            }else if (H == 1||W==1)
            {
                for (int i = 0; i < 26; i++)
                {
                    if (n[i] % 2 != 0)
                    {
                        x++;
                    }
                }
                if (x > 1)
                {
                    f++;
                }
            }else if (H % 2 == 1 && W % 2 == 1)
            {
                int o = 0;
                for (int i = 0; i < 26; i++)
                {
                    if (n[i] % 2 == 1)
                    {
                        o++;
                    }
                    else if (n[i] % 4 != 0)
                    {
                        x++;
                    }
                }
                if (!(o == 1 && x <= (H / 2 + W / 2)))
                {
                    f++;
                }
            }
            else if (H % 2 == 1) 
            {
                for (int i = 0; i < 26; i++)
                {
                    if (n[i] % 2 == 1)
                    {
                        f++;
                    }
                    else if (n[i] % 4 != 0)
                    {
                        x++;
                    }
                }
                if (x > W / 2)
                {
                    f++;
                }
            }
            else
            {
                for (int i = 0; i < 26; i++)
                {
                    if (n[i] % 2 == 1)
                    {
                        f++;
                    }
                    else if (n[i] % 4 != 0)
                    {
                        x++;
                    }
                }
                if (x > H / 2)
                {
                    f++;
                }
            }

            //
            if (f == 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }

        }
    }
}


Measured memory_bytes: 13140
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x: x[1])
c = 0
d = 0
i = 0
for t in ab:
  if d < t[0]:
    c += 1
    d = t[1]-1
print(c)

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

int main(void){
    
    int H,W;
    cin >> H >> W;
    char S[H][W];
    
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            cin >> S[i][j];
        }
    }
    
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(S[i][j] == '#'){
                for(int k=i-1;k<=i+1;k++){
                    for(int l=j-1;l<=j+1;l++){
                        if(0 <= k && k < H && 0 <= l && l < W && S[k][l] != '#') {
                            if(S[k][l] == '.') S[k][l] = '1';
                            else S[k][l] = char(S[k][l] + 1);
                        }
                    }
                }
            }
        }
    }
    
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(S[i][j] == '.') S[i][j] = '0';
            if(j != W-1) cout << S[i][j];
            else cout << S[i][j] << endl;
        }
    }
    
}

Measured memory_bytes: 3652
// #include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace std;
// using namespace __gnu_pbds;
// template <class c, class cmp = less<c> > using ordered_set = tree<c, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 
#endif
template<class T> ostream& operator<<(ostream &os, vector<T> V) {os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {return os << "(" << P.first << "," << P.second << ")";}
template <typename T,typename U>pair<T,U> operator+(const pair<T,U> & l,const std::pair<T,U> & r) { return {l.first+r.first,l.second+r.second};}
typedef long long int ll;
const ll mod =1e9+7;
const int maxn = 81;
#define endl '\n'
#define ld long double
//#define int ll
#define all(x)  (x).begin(),(x).end()

int32_t main(){

  IOS


  int n;
  cin >> n;
  string s = "";
  for(int i = 0;i<n;i++) s += "ACL";
  cout << s<< endl;
  

  




  

  
    
}



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

using lint = long long int;
using pii = std::pair<int, int>;

using std::vector;

vector<pii> ve;
vector<int> ve2;

int main(void) {
	int N, M;
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		ve.push_back(pii(t1, -t2));
	}

	sort(ve.begin(), ve.end());

	int cou = 0;
	for (int i = 0; i < N; i++) {
		if (ve[i].first <= cou) {
			ve2.push_back(-ve[i].second);
		}
		else {
			cou++;
		}
	}

	sort(ve2.begin(), ve2.end(), std::greater<int>());

	int cou2 = cou;
	cou = 0;
	int ans = 0;
	for (int i = 0; i < ve2.size(); i++) {
		if (M - cou == cou2) {
			ans++;
		}
		else if (M + 1 - ve2[i] <= cou) {
			ans++;
		}
		else {
			cou++;
		}
	}
	
	printf("%d", ans);

	return 0;
}

Measured memory_bytes: 3568
#include <iostream>
#include <queue>
#include <functional>
#include <cstring>
using namespace std;
#define MAX_V 10240

// ?????¶???from????????¶???to????????????cost??????
struct edge
{
	int to, distance, cost;
	edge(){}
	edge(int to, int distance, int cost) : to(to), distance(distance), cost(cost){}
};

// first ???????????????????????????second????????¶?????????
typedef pair<int, int> P;

// ???
vector<edge> G[MAX_V];

// ????????????
int d[MAX_V];
// V?????¶?????°
int V;

// ?±??§£?????¶???s????????°?????????????????????????????¶???????°???±?´????
void dijkstra(int s)
{
	priority_queue<P, vector<P>, greater<P> > que;
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	que.push(P(0, s));

	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (int i = 0; i < G[v].size(); ++i)
		{
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.distance)
			{
				d[e.to] = d[v] + e.distance;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{

	int /*N = V,*/ M;
	while (cin >> V >> M && V)
	{
		for (int i = 0; i < V; ++i)
		{
			G[i].clear();
		}
		for (int i = 0; i < M; ++i)
		{
			int u, v, d, c;
			cin >> u >> v >> d >> c;
			--u, --v;
			G[u].push_back(edge(v, d, c));
			G[v].push_back(edge(u, d, c));
		}
		// ?????????0???
		dijkstra(0);
		int ans = 0;
		for (int i = 1; i < V; ++i)
		{
			int min_cost = 0x3f3f3f3f;
			// ??????????¶????????????????????????¶????´???¨???????????£??????????´???¨
			for (int j = 0; j < G[i].size(); ++j)
			{
				if (d[G[i][j].to] + G[i][j].distance == d[i] && G[i][j].cost < min_cost)
				{
					min_cost = G[i][j].cost;
				}
			}
			ans += min_cost;
		}
		cout << ans << endl;
	}

	return 0;
}
///////////////////////////End Sub//////////////////////////////////

Measured memory_bytes: 3304
def calc(str)
    ret=0
    s = str.size
    s.times{|i|
        ret+=str[0..i].to_i * (i+1!=s ? 1<<(s-i-2) : 1)
        ret+=calc(str[(i+1)..-1]) if i!=str.size-1
    }
    return ret
end

str = gets.chomp
p calc(str)

Measured memory_bytes: 1788
#include <algorithm>
#include <iterator>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <string>
#include <vector>
#include <limits>
#include <queue>
#include <cmath>
#include <map>
#include <set>

using namespace std;

using ll = long long;

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

    cout << n * n * n << endl;

    return 0;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    a = int(input())
    b = int(input())
    c = int(input())
    x=int(input())
    cnt=0
    for i in range(a+1):
        for j in range(b+1):
            for k in range(c+1):
                if 500*i+100*j+50*k==x:
                    cnt+=1
    print(cnt)

main()

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

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#if !defined(M_PI)
#define M_E 2.71828182845904523536
#define M_LOG2E 1.44269504088896340736
#define M_LOG10E 0.434294481903251827651
#define M_LN2 0.693147180559945309417
#define M_LN10 2.30258509299404568402
#define M_PI 3.14159265358979323846
#define M_PI_2 1.57079632679489661923
#define M_PI_4 0.785398163397448309616
#define M_1_PI 0.318309886183790671538
#define M_2_PI 0.636619772367581343076
#define M_2_SQRTPI 1.12837916709551257390
#define M_SQRT2 1.41421356237309504880
#define M_SQRT1_2 0.707106781186547524401
#endif

int solve() {
    int q = 1000000007;

    int n;
    cin >> n;

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

    vector<ll> sfx_sum(n, 0);
    sfx_sum[n - 1] = a[n - 1];

    for (int i = n - 1 - 1; i >= 0; i--) {
        sfx_sum[i] = (sfx_sum[i + 1] + a[i]) % q;
    }

    ll ans = 0;

    for (int i = 0; i < n - 1; i++) {
        ans = (ans + (a[i]*sfx_sum[i + 1]) % q) % q;
    }
    return ans;
}

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

    int tt = 1;
    // cin >> tt;

    for (int tc = 1; tc <= tt; tc++) {
        cout << solve() << "\n";
    }
}


Measured memory_bytes: 6296
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 10007;
static const int INF = 1 << 25;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { 1, -1, 0, 0 };
static const int dy[] = { 0, 0, 1, -1 };

static int a, ans;

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


int main() {
	while ( ~scanf( "%d", &a ) && a ) {
		if ( a < 2 ) {
			printf( "0\n" );
			continue;
		}
		ans = 0;
		for ( int i = 1; i <= a; i++ ) {
			int now = i;
			for ( int j = i + 1; j <= a; j++ ) {
				if ( now + j == a ) {
					ans++;
					break;
				}
				if ( now + j > a ) {
					break;
				}
				now += j;
			}
		}
		printf( "%d\n", ans );
	}
	return 0;
}

Measured memory_bytes: 1196
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(m)]
    edges = [[] for _ in range(n)]
    for a, b in ab:
        edges[a - 1].append(b - 1)
        edges[b - 1].append(a - 1)
    
    q = int(input())
    ans = [0 for _ in range(n)]
    dd = [-1 for _ in range(n)]
    vdc = [tuple(map(int, input().split())) for _ in range(q)]
    for v, d, c in vdc[::-1]:
        if dd[v - 1] >= d:
            #  v - 1 から距離 d の部分は塗りつぶされているため無視
            continue
        
        node = []
        node.append(v - 1)
        while d >= 0 and len(node) > 0:
            next_node = []
            while len(node) > 0:
                u = node.pop()
                if dd[u] >= d:
                    continue
                dd[u] = d
                if ans[u] == 0:
                    ans[u] = c
                for v in edges[u]:
                    if dd[v] < d - 1:
                        next_node.append(v)
            node = next_node
            d -= 1
    
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


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

int main(){
  int a, b, x;
  cin >> a >> b;
  x = a*b;
 
  if(x%2 == 1){
    cout << "Odd" << endl;
  }
  else{
    cout << "Even" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define nmax_def 1100
#define Cmax_def 2200
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;



int main() {
	int N, M;
	int ans[nmax_def][10000];
	cin >> N >> M;
	ans[0][0] = 0;
	int Looptime = pow(2, N);
	rep(j, Looptime) {
		if (j == 0)
			continue;
		ans[0][j] = pow(10, 9);
	}
	rep(i, M) {
		int a, b;
		cin >> a >> b;
		int atmp = 0;
		rep(j, b) {
			int c;
			cin >> c;
			c--;
			atmp += pow(2, c);
		}
		rep(j, Looptime) {
			ans[i + 1][j] = ans[i][j]; // 初期値をiを使わないものに設定
		}
		rep(j, Looptime) {
			int j_or_atmp = j | atmp;
			ans[i + 1][j_or_atmp] = min(ans[i + 1][j_or_atmp], ans[i][j] + a); // iを使うべきか
		}
	}
	int ansans = ans[M][Looptime - 1];
	if (ansans == pow(10, 9))
		ansans = -1;
	cout << ansans << endl;
	return 0;
}

Measured memory_bytes: 40192
N = int(input())
p = list(map(int,input().split()))

for i in range(N):
	if p[i] != i + 1:
		j = p.index(i + 1)
		p[i], p[j] = p[j], p[i]
		break
		
if p == [i for i in range(1, N + 1)]:
	print('YES')
else:
	print('NO')

Measured memory_bytes: 3060
package main

import "fmt"

func main() {
	var N int
	fmt.Scan(&N)
	nums := scanNums(N)
	var sameSums = make(map[int]int) //部分和が同じものの個数を数え上げたもの

	// nums[0]の初期化
	prevk := nums[0]
	sameSums[nums[0]]++

	//空な部分列の和は0
	sameSums[0]++

	for i := 1; i < N; i++ {
		k := prevk + nums[i]
		sameSums[k]++
		prevk = k
	}

	cnt := 0
	for _, v := range sameSums {
		cnt += combination(v, 2)
	}

	fmt.Println(cnt)
}

func combination(n, r int) int {
	a := 1
	b := 1
	for i := 0; i < r; i++ {
		a *= n - i
		b *= r - i
	}
	return a / b
}

func scanNums(length int) (nums []int) {
	var num int
	for i := 0; i < length; i++ {
		fmt.Scan(&num)
		nums = append(nums, num)
	}
	return
}


Measured memory_bytes: 13824
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.stream.Stream;

import java.util.Set;
import java.util.HashSet;

public class Main {

    private static Set<String> ans;
    private static ArrayList<Integer> arr;

    private static void hasArrayTwoCandidates(ArrayList<Integer> a, int arSize, int sum, int x) {
	Integer l = 0;
	Integer r = arSize - 1;

	while (l<r) {
	    if (a.get(l) + a.get(r) == sum &&
		a.get(l)!=a.get(r) &&
		a.get(l)!=(x-sum)  &&
		a.get(r)!=(x-sum)
		) {
		arr = null;
		arr = new ArrayList<Integer>();
		arr.add(x - sum);
		arr.add(a.get(l));
		arr.add(a.get(r));
		Collections.sort(arr);
		ans.add(arr.toString());
		//System.out.println(arr.toString());
		l++;
	    } else if (a.get(l) + a.get(r) < sum) {
		l++;
	    } else {
		r--;
	    }
	}
	return;
    }

    public static void main(String[] args) {
	try {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    List<String> lines = new ArrayList<String>();
	    String line = "";

	    while((line = br.readLine()) != null){
	    lines.add(line);
	    }
	    br.close();

	    //lines.add("5 9");
	    //lines.add("0 0");
	    //lines.add("100 100");
	    //lines.add("100 200");
	    //lines.add("100 297");
	    //lines.add("0 0");

	    for (String e:lines) {
		if (e.equals("0 0")) {
		    break;
		} else {
		    int initial = Integer.parseInt(e.split(" ")[0]);
		    ArrayList<Integer> n = new ArrayList<Integer>();
		    for (Integer i = 1; i < initial+1; i++) {
			n.add(i);
		    }
		    Integer x = Integer.parseInt(e.split(" ")[1]);

		    ans = null;
		    ans = new HashSet<String>();
		    for (Integer t : n) {
			hasArrayTwoCandidates(n, n.size(), x - t, x);
		    }

		    //for (String ansstr : ans) {
		    // 	System.out.println(ansstr);
		    //};

		    //Collections.sort(ans);
		    System.out.println(ans.size());
		}
	    }

	    System.exit(0);

	} catch (Exception e) {
	    System.out.println(e.getMessage());
	    System.out.println(Arrays.toString(e.getStackTrace()));
	    System.exit(0);
	}
    }
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  
  int n, m;
  cin >> n >> m;

  vector<vector<int>> dp(n, vector<int>(2, 0));
  vector<pii> v(m);
  for (int i = 0; i < m; i++) {
    cin >> v[i].first >> v[i].second;
    v[i].second--;
  }
  sort(v.begin(), v.end());

  for (int i = 0; i < m; i++) {
    int pos = v[i].second;
    dp[pos][1] = dp[pos + 1][1] + 1;
    dp[pos + 1][0] = dp[pos][0] + 1;
  }

  for (int i = 0; i < n; i++) {
    cout << dp[i][0] + dp[i][1] + 1 << (i + 1 == n ? '\n' : ' ');
  }
  
  return 0;
}


Measured memory_bytes: 14744
#include "bits/stdc++.h"
using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 998244353
#define P pair<ll, ll>

int main() {
    string s, t;
    cin >> s;
    cin >> t;
    REP(i, 26){
        string now = s;
        now.push_back('a' + i);
        if(t == now){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <math.h>
#include <bitset>
#include <queue>

using namespace std;

void solve() {
    int64_t h;
    cin >> h;

    if(h == 1) {
        cout << 1;
        return;
    }

    int64_t divCount = 0;
    int64_t count;
    while (true) {
        if (h != 1) {
            h /= 2;
            divCount++;
        } else {
            count = pow(2, divCount+1) - 1;
            cout << count;
            break;
        }
    }
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n, k, s, ans[100100], i;
    cin >> n >> k >> s;
    for(i=0;i<n;i++){
        if(i<=k-1) ans[i]=s;
        else if(s==1000000000) ans[i]=1000000000-1;
        else ans[i]=1000000000;
    }
    for(i=0;i<n;i++){
        cout << ans[i] <<" ";
    }
    cout <<endl;
    return 0;
}


Measured memory_bytes: 2048
# coding: utf-8
DATA = """
20 3
5 10 15
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

K, N = [int(i) for i in get_line().strip().split(" ")]
A = [int(i) for i in get_line().strip().split(" ")]

A.append(A[0] + K)
#print (A)

p = [A[i+1] - A[i] for i in range(N) ]
#print (p)
p.sort()
print (K - p[-1])

Measured memory_bytes: 26444
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>
 
#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define REPR(i, x, n) for(int i = n - 1 ; i >= x ; i--)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) REPR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int main(){
    int h, w;
    cin >> h >> w;
    vector< vector<char> > s(h+2);
    rep(i, h+2){
        s[i].resize(w+2, '.');
    }
    int dx[] = {0,1,2,0,2,0,1,2}, dy[] = {0,0,0,1,1,2,2,2};
    rep(i, h){
        rep(j, w){
            cin >> s[i+1][j+1];
            if(s[i+1][j+1] == '.'){
                s[i+1][j+1] = '0';
            }
        }
    }
    rep(i, h){
        rep(j, w){
            if(s[i+1][j+1] == '#'){
                rep(k, 8){
                    if(s[i+dx[k]][j+dy[k]] != '#'){
                        s[i+dx[k]][j+dy[k]]++;
                    }
                }
            }
        }
    }
    rep(i, h){
        rep(j, w){
            cout << s[i+1][j+1];
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import AtCoder._

object Main extends App
  {
    val a, b, c, d, e, k = Int.scan
    (e.value - a.value > k.value).cond(":(", "Yay!").println
  }

object AtCoder
  {
    val scanner = new java.util.Scanner(System.in)

    trait Read[A]
      {
        def read(string :String) :A
        def scan :A = this.read(scanner.next)
      }

    trait Write
      extends Any
      {
        def write :String
        def print :Unit = write.print
        def println :Unit = write.println
      }

    implicit class Bool(val value :scala.Boolean)
      extends AnyVal
      {
        def cond[A](t :A, f :A) :A = if(this.value) t else f
        def yes_no :String = this.cond("yes", "no")
        def Yes_No :String = this.cond("Yes", "No")
        def YES_NO :String = this.cond("YES", "NO")
      }

    object Int
      extends Object
      with Read[Int]
      {
        def read(string :String) :Int = string.value.toInt
      }

    implicit class Int(val value :scala.Long)
      extends AnyVal
      with Write
      {
        def write = this.value.toString
        def +(a :Int) :Int = this.value + a.value
        def -(a :Int) :Int = this.value - a.value
        def *(a :Int) :Int = this.value * a.value
        def /(a :Int) :Int = this.value / a.value
        def %(a :Int) :Int = this.value % a.value
        def <(a :Int) :Bool = this.value < a.value
        def >(a :Int) :Bool = this.value > a.value
        def <=(a :Int) :Bool = this.value <= a.value
        def >=(a :Int) :Bool = this.value >= a.value
        def ==(a :Int) :Bool = this.value == a.value
        def !=(a :Int) :Bool = this.value != a.value
      }

    implicit class Float(val value :scala.Double)
      extends AnyVal
      with Write
      {
        def write = this.value.toString
      }

    implicit class String(val value :java.lang.String)
      extends AnyVal
      with Write
      {
        def write = this
        override def print = System.out.print(value)
        override def println = System.out.println(value)
      }
  }


Measured memory_bytes: 27328
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll N, M;
  cin >> N >> M;
  vector<ll> all_like(M, 0);
  for (int i = 0; i < N; i++) {
    ll k, a;
    cin >> k;
    for (int j = 0; j < k; j++) {
      cin >> a;
      a--;
      all_like[a]++;
    }
  }
  ll ans = 0;
  for (auto cnt : all_like) {
    if (cnt == N) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
    int x, e, i, j, m;

    for(;;){
      e = sc.nextInt();
      if(e == 0)break;
      m = e;
      for(i = 0;i * i * i <= e;i++)for(j = 0;j * j <= e;j++)
        if(i * i * i + j * j <= e){
          x = e - (i * i * i + j * j);
          if(m > x + j + i)m = x + j + i;
        }
      out.println(m);
    }

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 26488
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long int ll;
typedef unsigned long long ull;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
typedef pair<ll,ll> P;


int main()
{
    string s;
    cin>>s;
    rep(i,3){
        if(s[i]==s[i+1]){
            cout<<"Bad"<<endl;
            return 0;
        }
    }
    cout<<"Good"<<endl;
    return 0;

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            solve(in);
        }
    }

    static void solve(Scanner in) {
        int N = in.nextInt();
        long[] T = new long[N];
        long[] A = new long[N];
        for (int i = 0; i < N; i++) {
            T[i] = in.nextInt();
            A[i] = in.nextInt();
        }

        long t = T[0];
        long a = A[0];
        for (int i = 1; i < N; i++) {
            long Ti = T[i];
            long Ai = A[i];
            long Tm = (t - 1) / Ti;
            long Am = (a - 1) / Ai;
            long m = Tm > Am ? Tm : Am;
            Ti += Ti * m;
            Ai += Ai * m;
            t = (Ti + Ai) / (T[i] + A[i]) * T[i];
            a = (Ti + Ai) / (T[i] + A[i]) * A[i];
        }
        System.out.println(t + a);
    }
}

Measured memory_bytes: 13068
a = []
for _ in range(3):
  a += [int(i) for i in input().split()]

n = int(input())

ans = []
for _ in range(3):
  ans += [0]*3
  
for _ in range(n):
  b = int(input())
  if b in a:
    ans[a.index(b)] = 1
    
f = False
for i in range(3):
  if sum(ans[3*i:3*i+3]) == 3:
    f = True

for i in range(3):
  if sum(ans[i::3]) == 3:
    f = True
    
if (ans[0] + ans[4] + ans[8]) == 3:
  f = True
if (ans[2] + ans[4] + ans[6]) == 3:
  f = True
  
if f:
  print('Yes')
else:
  print('No')




Measured memory_bytes: 38256
#include <iostream>
#include <cstdio>
#include <cmath>
#define PI 3.14159265
using namespace std;

int h,m;

void solve() {
  double longhand,shorthand,theta;
  longhand = (30*h + (30.0/60.0)*m);
  shorthand = 6*m;
  //  cout << longhand << " " << shorthand << endl;
  theta = min(abs( longhand - shorthand),360-abs( longhand - shorthand));
  //  cout << theta << endl;
  if(theta < 30.0) {
    cout << "alert" << endl;
  }
  else if(theta <= 180 && 90 <= theta) {
    cout << "safe" << endl;
  }
  else {
    cout << "warning" << endl;
  }
}

int main() {
  int n;
  cin >> n;
  for(int i=0;i<n;i++) {
    scanf("%d:%d\n",&h,&m);
    solve();
  }
}

Measured memory_bytes: 0
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstdlib>

using namespace std;

template<class T> void gc(T &x)
{
	char c;
	int s = 0;
	x = 0;

	c = getchar_unlocked();

	if (c == '-') s = 1;
	else if ('0' <= c && c <= '9')  x = c - '0';

	while (true)
	{
		c = getchar_unlocked();

		if (c < '0' || c > '9') break;
		x = x * 10 + (c - '0');
	}

	if (s) x = -x;
}
int N;
// 現在の場所
int now_t, now_x, now_y;
// 次に行く場所
int t, x, y;

int main() {
	int N;
	gc(N);

	for (int i = 0; i < N; i++) {
		gc(t);
		gc(x);
		gc(y);

		// まず最低限必要な時間
		int rest_t = t - now_t - (abs(x - now_x) + abs(y - now_y));
		if (rest_t < 0 || rest_t % 2 == 1) {
			printf("No\n");
			return 0;
		}

		// 更新
		now_t = t;
		now_x = x;
		now_y = y;
	}

	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i,n) for(int i=0;i<(n);i++)
int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<min(a,b)+min(c,d)<<endl;
}

Measured memory_bytes: 256
if __name__ == '__main__':
    N = []
    X = []
    M = 0
    while True:
        n, x = map(int, input().split())
        if n==0 and x==0:
            break
        N.append(n)
        X.append(x)
        M += 1
    
    for i in range(M):
        num_size = N[i]
        target = X[i]
        cnt = 0
        for j in range(1, num_size+1):
            for k in range(j+1, num_size+1):
                l = target-(j+k)
                if j<l<k:
                    cnt += 1
        print(cnt)


Measured memory_bytes: 5596
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g

n,k = map(int,input().split())
k = k-1
s = input()
s = list(s)

if s[k] == "A":
    s[k] = "a"
elif s[k] == "B":
    s[k] = "b"
else:
    s[k] = "c"

out = ""

for i in range(n):
    out += str(s[i])
print(out)








Measured memory_bytes: 3064
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney,chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun



int main() {
	
	string s;
	cin >> s;
	int c = 0;
	if (s == "RRR") c = 3;
	else if (s == "RRS" || s == "SRR") c = 2;
	else if (s == "SSS")c = 0;
	else c = 1;
	cout << c << endl;
	return 0;
}

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

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  string S;
  cin >> S;
  if ((S.at(0) == S.at(1) && S.at(1) == S.at(2)) ||
      (S.at(1) == S.at(2) && S.at(2) == S.at(3))) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <utility>
#include <cctype>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#define LL long long
#define LB long double
#define x first
#define y second
#define Pair pair<int,int>
#define pb push_back
#define pf push_front
#define mp make_pair
#define LOWBIT(x) x & (-x)
using namespace std;

const int MOD=1e9+9;
const LL LINF=2e16;
const int INF=2e9;
const int magic=348;
const double eps=1e-10;
const double pi=3.14159265;

inline int getint()
{
    char ch;int res;bool f;
    while (!isdigit(ch=getchar()) && ch!='-') {}
    if (ch=='-') f=false,res=0; else f=true,res=ch-'0';
    while (isdigit(ch=getchar())) res=res*10+ch-'0';
    return f?res:-res;
}

int n,k;
int a[100048];

int main ()
{
	int i,minpos;n=getint();k=getint();
	for (i=1;i<=n;i++)
	{
		a[i]=getint();
		if (a[i]==1) minpos=i;
	}
	int left=minpos-1,right=n-left-1,ti,ll;
	if (left%(k-1)==0) ti=left/(k-1); else ti=left/(k-1)+1;
	ll=left%(k-1);if (ll) right-=(k-ll-1);
	if (right>0)
		if (right%(k-1)==0) ti+=right/(k-1); else ti+=right/(k-1)+1;
	printf("%d\n",ti);
	return 0;
}


Measured memory_bytes: 640