akhauriyash/Code-Regression huggingface dataset:
s = gets.chomp!.split('')
t = gets.chomp!.split('')
s_dup = {}
t_dup = {}
s.each do |_s|
  s_dup[_s] = 0 unless s_dup.keys.include? _s
  s_dup[_s] += 1
end
t.each do |_t|
  t_dup[_t] = 0 unless t_dup.keys.include? _t
  t_dup[_t] += 1
end
s_dup = s_dup.to_a.sort{|a, b| a[1] <=> b[1]}.select{|val| val[1] >= 2 }
t_dup = t_dup.to_a.sort{|a, b| a[1] <=> b[1]}.select{|val| val[1] >= 2 }
def check(s_, t_)
  if s_.length == t_.length
    s_ = s_.map{ |val| val[1] }
    t_ = t_.map{ |val| val[1] }
    if s_ == t_
      return true
    else
      return false
    end
  end
  return false
end
if s.uniq.length == t.uniq.length
  if check(s_dup, t_dup)
    puts "Yes"
  else
    puts "No"
  end
else
  puts "No"
end

Measured memory_bytes: 59516
#include<bits/stdc++.h>
#define fo(i,a,b) for((i)=(a);i<=(b);i++)
#define rfo(i,a,b) for((i)=(a);i>=(b);i--)
#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))
#define ALL(vec) ((vec).begin(),(vec).end())
#define SOR(vec) sort(ALL(vec))
#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())
using namespace std;
int c[4];
string str;
int n;
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	while(n--){
		cin>>str;
		if(str=="AC") c[0]++;
		if(str=="WA") c[1]++;
		if(str=="TLE") c[2]++;
		if(str=="RE") c[3]++;
	}
	cout<<"AC x "<<c[0]<<endl;
	cout<<"WA x "<<c[1]<<endl;
	cout<<"TLE x "<<c[2]<<endl;
	cout<<"RE x "<<c[3]<<endl;
	return 0;
}


Measured memory_bytes: 3676
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int[] a;
		a = new int [10020];
		int n = scan.nextInt();
		int i;
		long sum = 0;
		for(i = 1; i <= n; ++i){
			a[i] = scan.nextInt();
		}
		int tmp = a[1];
		int tmp2 = a[1];
		for(i = 1; i <= n; ++i){
			if(tmp <= a[i]){
				tmp = a[i];
				}
			if(tmp2 >= a[i]){
				tmp2 = a[i];
			}
			sum = sum + a[i];
		}
		System.out.println(tmp2+" "+tmp+" "+sum);
	}
}

Measured memory_bytes: 41480
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main() {
  int n;
  cin >> n;
  vector<int> a[2], s[2];
  rep(i,2){
    a[i] = vector<int>(n);
    s[i] = vector<int>(n);
    rep(j,n) cin >> a[i][j];
  }
  s[0][0] = a[0][0];
  rep(j,n-1) s[0][j+1] = s[0][j] + a[0][j+1];
  s[1][n-1] = a[1][n-1];
  rep(j,n-1) s[1][n-1-j-1] = s[1][n-1-j] + a[1][n-1-j-1];
 
  int ans = 0;
  rep(i,n) ans = max(ans,s[0][i]+s[1][i]);
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits//stdc++.h>
using namespace std;
int in(void){int x;cin>>x;return x;}
#define ll long long int
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
long long int dx[4]={1,0,-1,0};
long long int dy[4]={0,1,0,-1};
int main() {
	string s;
	cin>>s;
	int num=0;
	int a[100]={0};
	for(int i=0;i<s.size();i++){
		if(s[i]=='A'||s[i]=='T'||s[i]=='G'||s[i]=='C'){
			num++;
			a[num]++;
		}else{
			num=0;
		}
	}
	int ans=0;
	for(int i=1;i<20;i++){
		if(a[i]>=1)ans=i;
	}
	cout<<ans;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int n, m, q, a[50], b[50], c[50], d[50], ans = 0, arr[10];
 
void dfs(int l, int p) {
	if (l == n) {
		int v = 0;
		for (int i = 0; i < q; i++)
			if (arr[b[i]] - arr[a[i]] == c[i])
				v += d[i];
		ans = max(ans, v);
	} else {
		for (int i = p; i <= m; i++) {
			arr[l] = i;
			dfs(l + 1, i);
		}
	}
}
 
int main() {
	cin >> n >> m >> q;
	for (int i = 0; i < q; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		a[i]--, b[i]--;
	}
	dfs(0, 1);
	cout << ans << endl;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define pb push_back
ifstream in("file.in");
ofstream out("file.out");
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

int n,p[100005],ans,dp[100005];

vector <int> g[100005];

void DFS(int nod){
    vector <int> p;
    for(int i : g[nod]){
        DFS(i);
        p.push_back(dp[i]);
    }
    sort(p.begin(),p.end());
    for(int i : p){
        dp[nod]=max(dp[nod],i)+1;
    }
    //cout << nod << ' ' << dp[nod] << '\n';
}

int main() {
    cin >> n;
    for(int i=2;i<=n;i++){
        cin >> p[i];
        g[p[i]].pb(i);
    }
    DFS(1);
    cout << dp[1];
}


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

namespace abc149_b
{
  class Program
  {
    static void Main(string[] args)
    {
      var A = CIn.ReadLong();
      var B = CIn.ReadLong();
      var K = CIn.ReadLong();

      var aa = Math.Min(A, K);
      K -= aa;
      var bb = Math.Min(B, K);

      Console.WriteLine("{0} {1}", A - aa, B - bb);
    }
  }

  class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }
      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(long n)
    {
      var array = new string[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = Read();
      }
      return array;
    }

    public static int[] ReadIntArray(long n)
    {
      var array = new int[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadInt();
      }
      return array;
    }

    public static long[] ReadLongArray(long n)
    {
      var array = new long[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadLong();
      }
      return array;
    }

    public static double[] ReadDoubleArray(long n)
    {
      var array = new double[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadDouble();
      }
      return array;
    }
  }
}

Measured memory_bytes: 13268
# -*- coding: utf-8 -*-
#E - Sum Equals Xor
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
L = readline().decode().rstrip()
S = len(L)

# dp[i][j] : 上からi桁目の数まで見たとき,L以下であることがj(0:未確定/1:確定)
#            であるような条件を満たす組の総数
# S[i] == 0のとき
#   未確定 dp[i-1][0] → (0,0)の1通り  
#   確定 dp[i-1][1] → (0,0)(0,1)(1,0)の3通り
# S[i] == 1のとき
#   未確定 dp[i-1][0] → (0,1)(1,0)の2通り  
#   確定 dp[i-1][1] → (0,0)(0,1)(1,0)の3通り
#       dp[i-1][0] → (0,0)の1通り

dp = [[0]*2 for _ in range(S+1)]
dp[0][0] = 1

for i,l in enumerate(L,1):
    if l == '0':
        dp[i][0] = dp[i-1][0] % MOD
        dp[i][1] = 3*dp[i-1][1] % MOD
    else:
        dp[i][0] = 2*dp[i-1][0] % MOD
        dp[i][1] = (3*dp[i-1][1]+dp[i-1][0]) % MOD

print(sum(dp[-1])%MOD)

Measured memory_bytes: 85944
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>
#include <map>
#define maxn 200005
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,a[maxn];
map <int,int> s;
typedef map<int,int> :: iterator Ite;
bool check(int x){
	s.clear();
	for(int i=1;i<=n;i++){
		if(a[i] > a[i - 1]) continue;
		Ite it = s.end();
		while(it != s.begin()){
			it--;
			if(it -> first > a[i]) s.erase(it);
			else break;
		}
		int pos = a[i];
		while(pos && s.find(pos) != s.end()){
			if(s[pos] < x - 1) break;
			s.erase(pos);
			pos--;
		}
		if(pos == 0) return false;
		s[pos]++;
	}
	return true;
}
int main(){
	scanf("%d",&n);
	bool ok1 = true;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i] <= a[i - 1]) ok1 = false;
	}
	if(ok1){
		puts("1");
		return 0;
	}
	int lb = 2, rb = (int)1e9;
	while(lb < rb){
		int mid = (lb + rb) >> 1;
		if(check(mid)) rb = mid;
		else lb = mid + 1;
	}
	printf("%d\n",lb);
	return 0;
}


Measured memory_bytes: 1024
import java.util.*;

public class Main {
    private static final Scanner scn = new Scanner(System.in);
    private static final String RIGHT = "yuiophjklnm";
    private static final String EOF = "#";
    
    public static void main(String[] args) {
        String str;
        while(!(str = scn.next()).equals(EOF)) {
            int cnt = 0;
            boolean left = RIGHT.indexOf(str.charAt(0)) < 0;
            for(char elm : str.toCharArray()) {
                boolean now = RIGHT.indexOf(elm) < 0;
                if(left != now) {
                    cnt++;
                }
                left = now;
            }
            System.out.println(cnt);
        }
    }
}

Measured memory_bytes: 27312
#include<bits/stdc++.h>
#define ll long long int
#define ff first
#define ss second
#define eps 1e-9

using namespace std;
vector< vector<pair<ll,ll> > > g;
vector< ll> col;
vector< bool > vis;

void bfs()
{
    vis[1]=1;
    col[1]=0;
    queue<ll>  q;
    q.push(1);

    while(!q.empty())
    {
        ll top = q.front();
        q.pop();

        for(int i=0;i<g[top].size();i++)
        {
            if(vis[g[top][i].ff]==0)
            {
                vis[g[top][i].ff] =1;

                if(g[top][i].ss %2 )
                {
                    col[ g[top][i].ff ] = 1 - col[top];

                }
                else
                {
                    col[ g[top][i].ff ] = col[top];
                }

                q.push(g[top][i].ff);
            }
        }

    }
}


int main()
{

    ll t,n,m,f,a,b,c,l,r,q,k,x,y,w,z,ans,mn,mx,sum=0;

    cin>>n;

    g.resize(n+1);
    col.resize(n+1);
    vis.resize(n+1);

    for(int i=0;i<n-1;i++)
    {
        cin>>x>>y>>w;

        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }

    bfs();

    for(int i=1;i<=n;i++)
    {
        cout<<col[i]<<endl;
    }




}


Measured memory_bytes: 11200
import sys

N = int(input())
H = list(map(int, input().split()))
count = 0

if N == 1:
    print("Yes")
    sys.exit()

for i in range(N - 1):
    d = H[i] - H[i + 1]
    if d > 1:
        print("No")
        sys.exit()
    elif d == 1:
        count += 1
    elif d < 0:
        count = 0
    
    if count > 1:
        print("No")
        sys.exit()

print("Yes")

Measured memory_bytes: 63856
#include <stdio.h>

int main(){
	char S[10];
	scanf("%s",S);
	if(S[0]=='S'){
		printf("Cloudy\n");
	}else if(S[0]=='C'){
		printf("Rainy\n");
	}else if(S[0]=='R'){
		printf("Sunny\n");
	}
	return 0;
}

	

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

int kInf = 1 << 20;
int dtime[101][101];
int dcost[101][101];

int n, m;

void wf() {
	for(int k = 1; k <= m; k++)
		for(int i = 1; i <= m; i++)
			for (int j = 1; j <= m; j++) {
				dtime[i][j] = min(dtime[i][j], dtime[i][k] + dtime[k][j]);
				dcost[i][j] = min(dcost[i][j], dcost[i][k] + dcost[k][j]);
			}
}

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

	while (cin >> n >> m, n || m) {
		fill(dtime[0], dtime[101], kInf);
		fill(dcost[0], dcost[101], kInf);
		for (int i = 0; i < 101; i++)
			dtime[i][i] = dcost[i][i] = 0;
		for (int i = 0; i < n; i++) {
			int a, b, cost, time;
			cin >> a >> b >> cost >> time;
			dtime[a][b] = dtime[b][a] = time;
			dcost[a][b] = dcost[b][a] = cost;
		}
		wf();
		int k;
		cin >> k;
		for (int i = 0; i < k; i++) {
			int p, q, r;
			cin >> p >> q >> r;
			if(r)
				cout << dtime[p][q] << endl;
			else
				cout << dcost[p][q] << endl;
		}
	}
}

Measured memory_bytes: 1276
import scala.util.control.Breaks

object Main{
  def main(args:Array[String]) = {
    val sc = new java.util.Scanner(System.in)
    val N = sc.nextInt
    val M = sc.nextInt

    val as = Array.ofDim[Int](M)
    val bs = Array.ofDim[Int](M)

    for(i <- 0 to M-1){
      val a = sc.nextInt-1
      val b = sc.nextInt-1

      as(i) = a
      bs(i) = b
    }
    //println(as.deep)
    //println(bs.deep)

    var ans = 0
    for(ii <- 0 to M-1){
      val a = as(ii)
      val b = bs(ii)

      val d:Array[Array[Int]] = Array.fill(N,N)(1000)
      //println("...." + ii)
      for(j <- 0 to N-1){
        //println(j)
        d(j)(j) = 0
        //println(j)
      }
      for(j <- 0 to M-1) d(as(j))(bs(j)) = 1
      for(j <- 0 to M-1) d(bs(j))(as(j)) = 1
      d(a)(b) = 1000
      d(b)(a) = 1000

      //println("-------------------------------")
      //d.foreach(inp => println(inp.deep))


      for(k <- 0 to N-1){
        for(i <- 0 to N-1){
          for(j <- 0 to N-1){
            if(d(i)(j) > d(i)(k) + d(k)(j)) d(i)(j) = d(i)(k) + d(k)(j)
          }
        }
      }

      var f = false
      for(i <- 0 to N-1) for(j <- i+1 to N-1) if(d(i)(j) >= 1000) f=true
      if(f) ans = ans + 1
      //println(f)
      //d.foreach(inp => println(inp.deep))
    }
    println(ans)
  }
}


Measured memory_bytes: 44004
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1],reverse=True)
for b,c in bc:
    a.extend([c]*b)
    if len(a)>2*n:
        break
a.sort(reverse=True)
print(sum(a[:n]))

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

int main() {
  string c;
  cin >> c;
  if(c == "a" || c == "i" || c == "u" || c == "e" || c == "o"){
    cout << "vowel";
  }
  else{
    cout << "consonant";
  }
  return 0;
}

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

bool kei(vector<int> &moji,vector<bool> &op,int n,int x,bool b){
  if(n==3){
    if(b){
      x+=moji.at(n);
    }else{
      x-=moji.at(n);
    }
    if(x==7){
      op.at(n)=b;
      return true;
    }else{
      return false;
    }
  }
  if(b){
    if(kei(moji,op,n+1,x+moji.at(n),true)){
      op.at(n) = b;
      return true;
    }else if(kei(moji,op,n+1,x+moji.at(n),false)){
      op.at(n) = b;
      return true;
    }
  }else{
    if(kei(moji,op,n+1,x-moji.at(n),true)){
      op.at(n) = b;
      return true;
    }else if(kei(moji,op,n+1,x-moji.at(n),false)){
      op.at(n) = b;
      return true;
    }
  }
  return false;
}
int main(){
  string str;
  cin >> str;
  vector<int>moji(str.size());
  vector<bool>op(str.size());
  for(long unsigned int i=0;i < str.size();i++){
    moji.at(i)= str.at(i)-48;
  }
  kei(moji,op,0,0,true);
  for(int i=0;i<3;i++){
    cout << moji.at(i);
    if(op.at(i+1))
      cout << "+";
    else
      cout << "-";
  }
  cout << moji.at(3) << "=7";
  cout << endl;
}
  

Measured memory_bytes: 3632
#include <stdio.h>

int partition(int *, int, int);

int main(){
  int n, i, k;
  int A[100000];

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

  k = partition(A, 0, n-1);

  for(i=0; i<n; i++){
    if(i == k) printf("[%d]", A[i]);
    else printf("%d", A[i]);
    if(i != n-1) printf(" ");
  }
  printf("\n");
  
  return 0;
}

int partition(int *A, int p, int r){
  int x, i, j, temp;
  x = A[r];
  i = p-1;
  for(j=p; j<r; j++){
    if(A[j] <= x){
      i++;
      temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
  }
  temp = A[i+1];
  A[i+1] = A[r];
  A[r] = temp;
  
  return i+1;
}

Measured memory_bytes: 996
#include<bits/stdc++.h>
#define dbug printf("I am here\n");
#define Fast ios_base::sync_with_stdio(false); cin.tie(0);
#define vs              v.size()
#define ss              s.size()
#define sot(v)        sort(v.begin(),v.end())
#define rev(v)        reverse(v.begin(),v.end())
#define ii                pair<int,int>
#define ll                long long
#define ull              unsigned long long
#define pb              push_back
#define mpp          make_pair
#define Okay         0
#define pi               3.14159

static ll int inf = 1e9;
using namespace std;

void solve(){
    ll n;
   cin>>n;
     ll k = 7;
    ll ans = -1;
    for(int i=1; i<=n; i++){

        if(k%n == 0){
                ans = i;
                break;
        }
        k = ((k*10)+7);

        if(k >= n) k %= n;
    }
    cout<<ans;

}


int main(){

    solve();

    return Okay ;
}


Measured memory_bytes: 3588
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] array = new int[n];
		for(int i=0; i < n;i++){
			array[i] = sc.nextInt();
		}
		Arrays.sort(array);
		int score = 0;
		boolean b = true;
		for(int i = array.length-1;i>=0;i--){
			int x = b ? array[i] : -array[i];
			b = !b;
			score += x;
		}
		System.out.println(score);
	}
}

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

int main()
{
    int n;
    cin>>n;
    long long int arr[n];
    long long int dp[n];
    for(int i=0;i<n;i++)
    	cin>>arr[i];
    dp[0]=0;
    dp[1]=abs(arr[0]-arr[1]);

    for(int i=2;i<n;i++)
    	dp[i]=min((dp[i-1]+abs(arr[i]-arr[i-1])),(dp[i-2]+abs(arr[i]-arr[i-2])));
    cout<<dp[n-1]<<endl;
}

// Cost to reach the ith stoen is min(dp[i-1]+(arr[i]-arr[i-1]),dp[i-1]+(arr[i]-arr[i-2]))
// Base case is dp[0]=0 dp[1]=arr[0]-arr[1]

Measured memory_bytes: 1792
#include <stdio.h>
#include <iostream>
using namespace std;

int main(){
    double a,b;
    cin >> a >> b;
    //cout << (int)(a/b) << " " << (int)((int)a%(int)b) << " " << (float)a/b << endl;
    printf("%d %d %.5f\n",(int)(a/b),(int)((int)a%(int)b),(double)a/b);
}


Measured memory_bytes: 3288
#include <iostream>
#include <algorithm>
#include <utility>
#include <cmath>

int n;
long long a[100005], b[100005];
long long data[100005];
int main()
{
	std::cin >> n;
	long long ans = 0;
	for (int i = 0; i < n; ++i) {
		std::cin >> a[i] >> b[i];
		data[i] = a[i] + b[i];
		ans -= b[i];
	}

	std::sort(data, data + n, std::greater<long long>());

	for (int i = 0; i < n; ++i)
		if (i % 2 == 0)
			ans += data[i];

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


Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}

template<class T>
void Add(T &a, const T &b, const T &mod = 1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}
////////////////////////////////////////

int main() {
	int N;
	cin >> N;
	vector<int>A(N), B(N), C(N);
	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; ++i)cin >> C[i];
	sort(A.begin(), A.end());
	sort(C.begin(), C.end());
	ll count = 0;
	for (int i = 0; i < N; ++i) {
		count += ((lower_bound(A.begin(), A.end(), B[i])-A.begin())*(C.end()-upper_bound(C.begin(), C.end(), B[i])));
	}
	cout << count << endl;
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;
void stringSwap(string *a, int i, int j);

void BubbleSort(string *C, int N);
void SelectionSort(string *C, int N);

bool check(string *C1, string *C2, int N) {
	
	for (int i = 0; i < N;i++) {
		if (C1[i] != C2[i]) return false;
		
	}
	return true;
}

	void Print(string * C,int N) {
		for (int i = 0; i < N; i++) {
			if (i > 0) cout << " ";
			cout << C[i];
		}
		cout << endl;

	}


int main()
{
	int N;
	string C1[100],C2[100];
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> C1[i];
		C2[i] = C1[i];
	}
	BubbleSort(C1, N);//&c[0][0]と同義なはず。ポインタに渡してあげましょう。
	Print(C1, N);
	cout << "Stable" << endl;

	SelectionSort(C2, N);// 一次配列の場合はなんか関数側でC[]でちゃんとどうさしてくれる。要検査;
	Print(C2, N);
	if (check(C1, C2,N)) cout << "Stable" << endl;
	else cout << "Not stable" << endl;

	return 0;
}

void stringSwap(string *a,int i,int j) {
	string t;
	t = a[i];
	a[i] = a[j];
	a[j] = t;
}
void BubbleSort(string *C, int N) {

	for (int i = 0; i<N; i++) {
		for (int j = N - 1; j>i; j--) {
			if ((int)C[j-1][1]>(int)C[j][1]) stringSwap(C, j-1, j);
		
		}
	}

}
void SelectionSort(string *C, int N) {
	int minj;

	for (int i = 0; i<N; i++) {
		minj = i;
		for (int j = i+1; j<N; j++) {
			if ((int)C[minj][1]>(int)C[j][1]) minj = j;
			
		}
		stringSwap(C, minj, i);
	}
}




Measured memory_bytes: 3228
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE BangPatterns #-}

import Control.Applicative
import Control.Monad
import Control.Arrow
import Data.List
import Data.Maybe
import Data.Char
import qualified Data.ByteString.Char8 as B
import Text.Printf

readInt = ( readLn :: IO Int )
readInts = map ( read :: String -> Int ) . words <$> getLine

getList = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = getLine >>= print . ( + 700 ) . ( * 100 ) . length . filter ( == 'o' )

Measured memory_bytes: 380
from math import ceil
 
n = int(input())
a = 1
b = 1
 
for i in range(n):
    s,t = map(int,input().split())
    #x = max([ceil(a/s), ceil(b/t)])
    x = max((a+s-1)//s, (b+t-1)//t)

 
    a = x*s
    b = x*t

print(a+b)

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

int main(void)
{
    int N;
    cin >> N;
    vector<ll> A(N), B(N);
    ll asum = 0;
    ll bsum = 0;
    vector<ll> margin(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
        asum += (ll) A[i];
    }

    for (int i = 0; i < N; i++)
    {
        cin >> B[i];
        bsum += (ll) B[i];
        margin[i] = A[i] - B[i];
    }

    if(asum < bsum){
        cout << -1 << endl;
        return 0;
    }

    ll sum1= 0;
    ll num = 0;
    for (int i = 0; i < N; i++){
        if(margin[i] >= 0){
            
        } else {
            sum1 -= margin[i];
            num++;
        }
    }

    sort(margin.begin(), margin.end(), greater<ll>());

    for (int i = 0; i < N; i++)
    {
        if(sum1 <= 0) break;
        if(margin[i] > 0){
            sum1 -= margin[i];
            num++;
        }
    }
    
    cout << num << endl;
    return 0;
}


Measured memory_bytes: 5636
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

# sys.setrecursionlimit(5000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N = n1()

cnt = 0
ans = 0
for i in range(N):
    D1, D2 = nn()
    if D1 == D2: cnt += 1
    else: cnt = 0
    if cnt >= 3: ans = 1

if ans == 1:
    print("Yes")
else:
    print("No")

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

int main() {
  int s, s1, s2, s3;
  cin >> s;
  s1 = s / 100;
  s2 = (s - s1 * 100) / 10;
  s3 = (s - s1 * 100 - s2 * 10);
  cout << s1 + s2 + s3 << endl;
}

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

int main(){
  int n;
  int a[5000];
  int tmp;
  int ans;

  while(1){
    cin >> n;
    if(!n)break;

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

    ans = a[0];
    for(int i=0;i<n;i++){
      for(int j=i;j<n;j++){
	if(i==j)tmp = a[i];
	else tmp += a[j];
	ans = max(tmp,ans);
      }
    }

    cout << ans << endl;
  }
}

Measured memory_bytes: 0
#include<string>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<sstream>
#include<functional>
#include<map>
#include<set>
#include<cmath>
#include<iomanip>

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

using namespace std;

int main(){

	vector<int>v(10);

	int l;
	rep(i,10){
	cin >> l;
	v.push_back(l);
	}

	sort(v.begin(),v.end(),greater<int>());

	cout << v[0] << endl;
	cout << v[1] << endl;
	cout << v[2] << endl;

	return 0;
}

Measured memory_bytes: 1212
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,M,C = MI()
B = LI()
ans = 0
for i in range(N):
    A = LI()
    if C + sum(A[j]*B[j] for j in range(M)) > 0:
        ans += 1
print(ans)


Measured memory_bytes: 62216
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define ii pair<int,int>
#define MAX 1000000007
using namespace std;

int main(void){
	int n;
	cin>>n;
	int l[n];
	rep(i,n)cin>>l[i];
	sort(l,l+n);
	rep(i,n-2){
		l[i+1]+=l[i];
	}
	if(l[n-1]<l[n-2])cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
Alice = 0
Bob = 0
card = 0
for i in range(N):
    if A == []:
        break
    card = max(A)
    if card == 0:
        break
    else:
        Alice += card
        A.remove(card)
    if A == []:
        break
    card = max(A)
    if card == 0:
        break
    else:
      Bob += card
      A.remove(card)
print(Alice-Bob)

Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long

void test_case(){
	int n;
	cin >> n;
	int arr[n+1];
	for(int i=1;i<=n;i++) cin >> arr[i];
	sort(arr+1, arr+n+1);

	int ans=0;
	for(int players=1; players<=n-1; players++){
		ans += arr[n-players/2];
	}
	cout << ans << endl;
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int t=1;
	// cin >> t;

	while(t--) test_case();
	
	return 0;
}


Measured memory_bytes: 5212
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//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 PB push_back
#define MP make_pair
#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())
#define SORT(c) sort((c).begin(),(c).end())

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

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

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

  int N;
  while(cin >> N, N){
	bool table[101][101];
	fill((bool*)table, (bool*)table+101*101, false);
	REP(i,N){
	  int M; cin >> M;
	  REP(j,M){
		int x; cin >> x;
		table[i][x] = true;
	  }
	}
	int K; cin >> K;
	VI target(K);
	REP(i,K) cin >> target[i];

	int ans = -1;
	REP(i,N){
	  int j;
	  for(j=0;j<K;++j)
		if(!table[i][target[j]]) break;
	  
	  if(j == K){
		if(ans != -1){
		  ans = -1;
		  break;
		}
		else
		  ans = i+1;
	  }
	}
	cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1208
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		char[] x = sc.next().toCharArray();
		sc.close();

		int ans = 0;
		int cnt = 0;
		for (int i = 0; i < x.length; i++) {
			if (x[i] == 'S') {
				cnt++;
			} else {
				if (cnt > 0) {
					ans += 2;
					cnt--;
				}
			}
		}
		System.out.println(x.length - ans);
	}
}


Measured memory_bytes: 28472
#include<iostream>
using namespace std;
int main(){
	int a;
	cin>>a;
	int b[a];
	for(int i=0;i<a;i++){
		cin>>b[i];
	}
	int c=0;
	for(int i=0;i<a-2;i++){
		if(b[i]<b[i+1]&&b[i+1]<b[i+2]){
//			cout<<" "<<b[i]<<" "<<b[i+1]<<" "<<b[i+2]<<endl;
			c++;
		}
		if(b[i]>b[i+1]&&b[i+1]>b[i+2]){
//			cout<<"  "<<b[i]<<" "<<b[i+1]<<" "<<b[i+2]<<endl;
			c++;
		}
	}
	cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#define MAX_N       100
#define QUE_SIZE    10000


/* priority queue */
typedef struct _QueItem {
    int cost;
    int id;
} QueItem;
QueItem heapq[QUE_SIZE]; /* index 0: unuse, index 1.. : que */
int quecnt;

void enq(QueItem a);
QueItem deq();
int qcmp(QueItem a, QueItem b);


int cost[MAX_N];
int path[MAX_N][MAX_N];


int main(){
    int n,u,k,v,c;
    int i,j,tn,tk;
    int fin_cnt;
    QueItem item,item2;
    /* init */
    for(i=0;i<MAX_N;i++){
        for(j=0;j<MAX_N;j++){
            path[i][j]=-1;
        }
        cost[i]=-1;
    }
    /* input */
    scanf("%d",&n);
    for(tn=0;tn<n;tn++){
        scanf("%d %d",&u,&k);
        for(tk=0;tk<k;tk++){
            scanf("%d %d",&v,&c);
            path[u][v]=c;
        }
    }

    /* calc */
    cost[0] = 0;
    for(i=1;i<n;i++){
        if(path[0][i]>=0){
            item.cost = path[0][i];
            item.id   = i;
            enq(item);
        }
    }

    fin_cnt = 1;
    while(fin_cnt<n){
        item = deq();
        if(cost[item.id]<0){
            cost[item.id]=item.cost;
            fin_cnt++;
            for(i=0;i<n;i++){
                if(path[item.id][i]>=0 && cost[i]<0){
                    item2.cost = item.cost + path[item.id][i];
                    item2.id   = i;
                    enq(item2);
                }
            }
        }
    }

    /* output */
    for(i=0;i<n;i++){
        printf("%d %d\n",i,cost[i]);
    }

    return 0;
}




/* add a to heapq */
void enq(QueItem a){
    int i;
    QueItem tmp;
    quecnt++;
    heapq[quecnt] = a;
    for(i=quecnt;i/2>0;i/=2){
        if(qcmp(heapq[i/2],heapq[i]))break;
        tmp = heapq[i];
        heapq[i] = heapq[i/2];
        heapq[i/2] = tmp;
    }
}

/* get highest priority item in heapq */
QueItem deq(){
    int i,target;
    QueItem tmp,ret;
    ret = heapq[1];
    heapq[1] = heapq[quecnt];
    quecnt--;
    for(i=1;i*2<=quecnt;){
        if( i*2+1<=quecnt && qcmp(heapq[i*2+1],heapq[i]) ){
            if( qcmp(heapq[i*2],heapq[i*2+1]) ){
                target = i*2;
            }else{
                target = i*2+1;
            }
        }else if( qcmp(heapq[i*2],heapq[i]) ){
            target = i*2;
        }else{
            break;
        }
        tmp = heapq[i];
        heapq[i] = heapq[target];
        heapq[target] = tmp;
        i = target;
    }
    return ret;
}

/* return TRUE if priority(a) > priority(b) */
int qcmp(QueItem a, QueItem b){
    return (a.cost<b.cost);
}



Measured memory_bytes: 2100
import java.util.*;
import java.io.*;
 
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
public class Main{
    static final long mod=1000000007;
    static int dx[]={1,-1,0,0};
    static int dy[]={0,0,1,-1};

    public  static void main(String[] args)   throws Exception, IOException{
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        // int n=sc.nextInt();
        // char c[][] = new char[h][w];
        // char c[]=sc.nextString().toCharArray();
        // int d[]=new int[n];
        // for(int i=0; i<n; i++) {d[i]=sc.nextInt();}

        int n=sc.nextInt();
        if(n<=2) {
        	if(n==1) {
                out.println("Yes");
                out.println(2);
                out.println(1+" "+1);
                out.println(1+" "+1);
                out.flush();
                return;        	        		
        	}
            out.println("No");
            out.flush();
            return;        	
        }
        int x=0,c=1;
        for (int i = 0; i < n; i++) {
        	x+=i;
        	db(x);
			if(x==n) {c=i+1;break;}
			else if(n<x) {
	            out.println("No");
	            out.flush();
	            return;        	
			}
		}
        ArrayList<Integer> l[]=new ArrayList[c];
        for (int i = 0; i < c; i++) {
        	l[i] = new ArrayList<Integer>(); 
        }        
        for (int i = 1,v=1; i <= c; i++) {
        	for (int t = i+1; t <= c; t++) {
				l[i-1].add(v); l[t-1].add(v++);
			}
        }

        out.println("Yes");
        out.println(c);
        for (int i = 0; i < c; i++) {
			out.print(c-1+" ");
            for (int t = 0; t < c-1; t++) {
				out.print(l[i].get(t)+" ");
			}       	
            out.println();
        }     
        
//        out.println();
        out.flush();
    }

    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }  
}

class P implements Comparable<P>{
    int id, d;
    P(int  id, int d) {
        this.id=id;
        this.d=d;
    }
    public int compareTo(P p){
        return d-p.d; //des
    }
}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}


Measured memory_bytes: 46356
#include <bits/stdc++.h>
using namespace std;
int h,w,x,y,a[8][8];
string s[8];
int main(){
  cin>>h>>w;
  for(int i=0;i<h;++i)cin>>s[i];
  a[0][0]++;
  for(int i=0;i<h+w-2;++i){
    if(s[x][y+1]=='#'){
      y++;
      a[x][y]++;
    }else if(s[x+1][y]=='#'){
      x++;
      a[x][y]++;
    }else{
      cout << "Impossible" << endl;
      return 0;
    }
  }
  for(int i=0;i<h;++i){
    for(int j=0;j<w;++j){
      if((s[i][j]=='.'&&a[i][j]==1)||(s[i][j]=='#'&&a[i][j]==0)){
        cout << "Impossible" << endl;
        return 0;
      }
    }
  }
  cout << "Possible" << endl;
  return 0;
}

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

typedef long long int ll;
typedef string str;

int main ()
{
	// ios::sync_with_stdio(0);
 //    cin.tie(0);
 //    cout.tie(0);
	ll t,n,m,k,i,a,b,j;
	cin >> n >> k;
	ll arr[n+2];
	for(i=1;i<n+1;i++)
	{
		cin >> arr[i];
	}
	vector < ll > v;
	ll h[n+2]={0};
	i=1;
	while(h[i]==0)
	{
		h[i]=1;
		v.push_back(i);
		i=arr[i];
	}
	m=i;
	vector <ll> cyc;
	vector <ll> nor;
	for(i=0;i<v.size();i++)
	{
		if(v[i]!=m)
			nor.push_back(v[i]);
		else
			break;
	}
	for(i=i;i<v.size();i++)
	{
		cyc.push_back(v[i]);
	}
	if(k<nor.size())
	{
		m = nor[k];
	}
	else
	{
		k-=nor.size();
		a=cyc.size();
		m=cyc[k%a];
	}
	cout << m << endl;
	return 0;
}

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

int main()
{
	string S, P;
	cin >> S >> P;
	S = S + S;
	if(S.find(P) != string::npos)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

    return 0;
}



Measured memory_bytes: 3216
<?php

fscanf(STDIN, "%d %d %d", $a, $b, $k);

class ABCookie {
    public $A;
    public $B;

    public function eatAndGiveAtoB() {
        if ($this->A % 2 == 1) {
            $this->A = $this->A - 1;
        }
        $this->A = $this->A / 2;
        $this->B = $this->B + $this->A;
    }

    public function eatAndGiveBtoA() {
        if ($this->B % 2 == 1) {
            $this->B = $this->B - 1;
        }
        $this->B = $this->B / 2;
        $this->A = $this->A + $this->B;
    }
}

$hoge = new ABCookie();
$hoge->A = $a;
$hoge->B = $b;

for ($i = 0; $i < $k; $i++ ) {
    if ($i % 2 == 0) {
        $hoge->eatAndGiveAtoB();
    } else {
        $hoge->eatAndGiveBtoA();
    }
}

echo $hoge->A. " ". $hoge->B. "\n";


Measured memory_bytes: 4856
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll MOD = 1000000007;
// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
template <typename T>
ll gcd(T a, T b) {
  if (b == 0) {
    return a;
  }
  ll d = gcd(b, a % b);
  return d;
}
struct Segment_Tree {
  // 随時評価セグ木
  // 値を渡すときは0-indexed，半閉区間で動作させる
  vector<int> A;
  int N;
  Segment_Tree(int x) {
    int i = 1;
    while (i <= x) {
      i = i << 1;
    }
    N = i;
    A.resize(2 * i + 1, 0);
  }
  void ValueUpdate(int id) {
    //ここを随時書き換える
    int prev = A[id];
    //区間内和
    A[id] = gcd(A[id << 1 | 0], A[id << 1 | 1]);
    if (id == 1 || prev == A[id]) return;
    ValueUpdate(id >> 1);
  }
  void ValueSet(int id, int x) {
    //値の入力は0-indexed
    A[N + id] = x;
    ValueUpdate((N + id) >> 1);
  }
  int Query(int l, int r, int nowl = 0, int nowr = -1, int id = 1) {
    if (nowr == -1) nowr = N;
    if (nowr <= l || r <= nowl) return 0;
    if (l <= nowl && nowr <= r || nowr == nowl) return A[id];
    return gcd(Query(l, r, nowl, nowl + (nowr - nowl) / 2, id << 1 | 0),
               Query(l, r, nowl + (nowr - nowl) / 2, nowr, id << 1 | 1));
  }
};
int main() {
  int N;
  cin >> N;
  Segment_Tree seg(N);
  REP(i, N) {
    int a;
    cin >> a;
    seg.ValueSet(i, a);
  }
  int ans = 0;
  for (int i = 1; i < N - 1; i++) {
    int tmp = gcd(seg.Query(0, i), seg.Query(i + 1, N));
    ans = max(ans, tmp);
  }
  ans = max<ll>(seg.Query(1, N), ans);
  ans = max<ll>(seg.Query(0, N - 1), ans);
  cout << ans << endl;
}

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

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

  
  int n,k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  while(k>0){
    vector<int> imos(n+1);
    vector<pair<int,int>> qu;
    rep(i,n){
      qu.push_back({max(0,i-a[i]),min(n-1,i+a[i])});
    }
    rep(i,n){
      imos[qu[i].first]++;
      imos[qu[i].second+1]--;
    }
    vector<int> na(n);
    na[0] = imos[0];
    rep1(i,n-1){
      na[i] = imos[i] + na[i-1];
    }
    swap(a,na);
    k--;
    rep(i,n) {
      if(a[i]!=n) break;
      else if(i==n-1) k=0;
    }
  }
  rep(i,n) cout << a[i] <<" ";
  cout << endl;

  return 0;
    

}


Measured memory_bytes: 8712
lines = []
colums = []

while True:
  H,W = map(int,input().split())
  if H == 0 and W == 0:
    break
  lines.append(H)
  colums.append(W)

for H,W in zip(lines,colums):
  for i in range(H):
    if i%2==0:
      for j in range(W):
        if j%2==0:
          print("#",end="")
        else:
          print(".",end="")
    else:
      for j in range(W):
        if j%2!=0:
          print("#",end="")
        else:
          print(".",end="")
      
    print("\n",end="")
  print("\n",end="")


Measured memory_bytes: 7024
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<iomanip>
#define mod 1000000007
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod

#define N 2010
ll n,m,q;
string s[N];
ll ra[N][N],rb[N][N],rc[N][N];
int main(){
    cin>>n>>m>>q;
    for(int i=0;i<N;i++){
	ra[i][0]=ra[0][i]=0;
	rb[i][0]=rb[0][i]=0;
	rc[i][0]=rc[0][i]=0;
    }
    for(int i=0;i<n;i++){
	cin>>s[i];
    }
    for(int i=0;i<n;i++){
	for(int j=0;j<m;j++){
	    ra[i+1][j+1]=ra[i][j+1]+ra[i+1][j]-ra[i][j]+(s[i][j]=='1');
	}
    }
    for(int i=0;i<n;i++){
	for(int j=0;j<m-1;j++){
	    rb[i+1][j+1]=rb[i][j+1]+rb[i+1][j]-rb[i][j]+(s[i][j]=='1'&&s[i][j+1]=='1');
	}
    }
    for(int i=0;i<n-1;i++){
	for(int j=0;j<m;j++){
	    rc[i+1][j+1]=rc[i][j+1]+rc[i+1][j]-rc[i][j]+(s[i][j]=='1'&&s[i+1][j]=='1');
	}
    }
    while(q--){
	ll a,b,c,d;
	cin>>a>>b>>c>>d; a--,b--;
	ll v=ra[c][d]-ra[a][d]-ra[c][b]+ra[a][b];
	ll e1=rb[c][d-1]-rb[a][d-1]-rb[c][b]+rb[a][b];
	ll e2=rc[c-1][d]-rc[a][d]-rc[c-1][b]+rc[a][b];
	cout<<v-e1-e2<<endl;
    }
}




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

template <typename T>
struct Edge
{
    int to;
    T cost;
};

struct Graph
{
    int n;
    vector<vector<int>> g;
    
    Graph(int n) : n(n){
        g.resize(n);
    }
    
    void init(int n_){
        n = n_;
        g.resize(n_);
    }
    
    void add_edge(int from, int to){
        g[from].push_back(to);
    }
};

int main()
{
    int n;
    cin >> n;
    int x[1002];
    Graph g(n);
    for(int i = 1; i < n; i++){
        int p;
        cin >> p;
        p--;
        g.add_edge(p, i);
    }
    for(int i = 0; i < n; i++) cin >> x[i];
    int l[1002], h[1002];
    for(int i = 0; i < n; i++) l[i] = h[i] = -1;
    for(int i = n - 1; i >= 0; i--){
        int k = 0;
        for(int c : g.g[i]) k += l[c] + h[c];
        bool dp[5003]{0};
        dp[0] = true;
        for(int c : g.g[i]){
            for(int j = 5000; j >= 0; j--){
                if(!dp[j]) continue;
                dp[j] = false;
                if(j + l[c] <= 5000) dp[j + l[c]] = true;
                if(j + h[c] <= 5000) dp[j + h[c]] = true;
            }
        }
        for(int j = x[i]; j >= 0; j--){
            if(dp[j]){
                h[i] = max(x[i], k - j);
                l[i] = min(x[i], k - j);
                break;
            }
        }
        if(l[i] == -1){
            cout << "IMPOSSIBLE" << endl;
            return 0;
        }
    }
    cout << "POSSIBLE" << endl;
}

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

long long maxi(long long a, long long b){
    return (a>b) ? a : b;
}


int main(){

    int n, W;
    cin >> n >> W;
    long long dp[W+1];
    dp[0] = 0;
    int items[n][2];
    for(int i = 0; i < n; i++) cin >> items[i][0] >> items[i][1];
    for(int i = 1; i <= W; i++) dp[i] = -1;
    for(int i = 0; i < n; i++){
        for(int j = W; j >= items[i][0]; j--){
            if(dp[j-items[i][0]]+1) dp[j] = maxi(dp[j],dp[j-items[i][0]]+items[i][1]);
        }
    }
    long long ans = -1;
    for(int i = 0; i <= W; i++) ans = maxi(ans, dp[i]);
    cout << ans;


    return 0;
}


Measured memory_bytes: 1024
N = int(input())
nums = list(map(int, input().split()))
total, ano = sum(nums), 0
last_dif = 100000000000000
for i in range(len(nums)-1):
    total -= nums[i]
    ano += nums[i]    
    if abs(ano-total) < last_dif:
        dif = abs(ano-total)
        last_dif = dif
print(dif)
    

Measured memory_bytes: 23792
N = int(input())
A = list(map(int, input().split()))
def insertionSort(N, A):
    for i in range(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)))
insertionSort(N,A)


Measured memory_bytes: 5600
// #include <cstdio>
// #include <algorithm>
// using namespace std;
// const int N = 50+5;
// struct Edge
// {   
//     int next, to;
//     Edge(int next = 0, int to = 0):next(next), to(to) {};
// }edge[N*N<<2];
// int head[N*N], tot;
// void _add(int x, int y) { edge[++tot] = Edge(head[x], y), head[x] = tot; }
// void add(int x, int y) { _add(x, y), _add(y, x); }
// int n, m, ans;
// char s[N][N];
// int rec[N][N], col[N], t;
// void dfs(int i, int j, int c)
// {
//     if(rec[i][j]||s[i][j] != 'c') return;
//     rec[i][j] = t;
//     dfs(i+1, j, c), dfs(i, j+1, c); 
//     dfs(i-1, j, c), dfs(i, j-1, c); 
// }
// int main()
// {
//     freopen("paint.in", "r", stdin);
//     freopen("paint.out", "w", stdout);
//     scanf("%d%d", &n, &m);
//     for(int i = 1; i <= n; ++i) scanf("%s", s[i]+1);
//     for(int i = 1; i <= n; ++i)
//         for(int j = 1; j <= m; ++j)
//         {
//             if(rec[i][j]) continue;
//             col[++t] = s[i][j], dfs(i, j, col[t]);
//         }
//     for(int i = 1; i < n; ++i)
//         for(int j = 1; j <= m; ++j)
//             if(rec[i][j] != rec[i+1][j]) add(rec[i][j], rec[i+1][j]);
//     for(int i = 1; i <= n; ++i)
//         for(int j = 1; j < m; ++j)
//             if(rec[i][j] != rec[i][j+1]) add(rec[i][j], rec[i][j+1]);
//     for(int i = 1; i <= n; ++i)
//         for(int j = 1; j < m; ++j)

//     printf("%d\n", ans);
//     return 0;
// }
#include <cstdio>
#include <cmath>
long long s, px1, py1, x2, y2;
int main()
{
    scanf("%lld", &s);
    if(s == 0) return puts("0 0 0 0 0 0");
    y2 = px1 = sqrt(s);
    if(px1*px1 < s) ++y2, ++px1;
    if(px1*y2 != s) x2 = 1, py1 = px1*y2-s;
    printf("0 0 %lld %lld %lld %lld\n", px1, py1, x2, y2);
    return 0;
}
/* 
1 6
101101
499999999999999999
400000000000000000
*/

Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
template<typename T>inline void in(T &a)
{
	T ch=getchar(),f=1;
	for(a=0;!isdigit(ch);ch=getchar())
	  ch=='-'?f=-1:f=f;
	for(;isdigit(ch);ch=getchar())
	  a=(a<<3)+(a<<1)+ch-'0';
	a*=f;
}
template<typename T>inline void print(T x)
{
	if(x<0)
	  x=-x,putchar('-');
	if(x>9)
	  print(x/10);
	putchar(x%10+'0');
}
long long x,y;
long long n,a,b;
signed main()
{
	long long ans=0;
	cin>>n>>a>>b;
	for(long long i=1;i<=n;i++)
	{
		cin>>x>>y;
		if(x>=a&&y>=b)
		  ans++;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256