akhauriyash/Code-Regression huggingface dataset:
n, m = map(int, input().split())
A = []
for _ in range(m):
  k, *s = map(int, input().split())
  c = 0
  for i in s:
    c += 2**(i-1)
  A.append(c)
P = tuple(map(int, input().split()))
ans = 0
for i in range(2**n):
  f = True
  for j in range(m):
    c = bin(i & A[j]).count("1")
    if c%2 != P[j]:
      f = False
      break
  if f:
    ans += 1
print(ans)

Measured memory_bytes: 3064
abc = list(map(int , input().split()))
flg = False
for i in range(1<<3):
    v = [0]*2
    tmp = i
    for j in range(3):
        v[tmp%2] += abc[j]
        tmp = tmp // 2
    if v[0] == v[1]:
        flg = True

if flg:
    print("Yes")
else:
    print("No");


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

int main() {
    int Q; cin >> Q;
    
    for (int i=0; i<Q; i++) {
        int ci, ai, ni; cin >> ci >> ai >> ni;
        int can = min({ci, ai, ni});
        ci -= can;
        ai -= can;
        int cca = min(ci/2, ai);
        ci -= 2*cca;
        int ccc = ci/3;
        cout << can+cca+ccc << endl;
    }
}


Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  rep(i, 10) rep(j, 10) rep(k, 10) {
    int x = 0;
    vi v = {i, j, k, 10};
    rep(i, n) if(s[i] - '0' == v[x]) x++;
    if(x == 3) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

int main(){
    int n,m;
    cin>>n>>m;
    if(n==1&&m==0){
        cout<<0<<endl;
        return 0;
    }
    int v[n];
    fill(v,v+n,-1);
    bool can=true;
    rep(i,m){
        int s,c;
        cin>>s>>c;
        --s;
        if(v[s]==-1)v[s]=c;
        else if(v[s]!=c){
            can=false;
        }
    }
    if(n!=1&&v[0]==0){
        can=false;
    }
    if(!can){
        cout<<-1<<endl;
        return 0;
    }
    if(v[0]==-1)v[0]=1;
    rep(i,n){
        if(v[i]==-1){
            cout<<0;
        }
        else{
            cout<<v[i];
        }
    }
    cout<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <functional>

using namespace std;
int main()
{
	int N, X = 0;
	int m[101];

	cin >> N >> X;

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

	int sum = 0;
	for (int j = 0; j < N; j++) {
		sum += m[j];
	}

	sort(m, m + N);

	int A = X - sum;

	int min = m[0];

	int Ans = N + A / min;

	cout << Ans;

	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict

h, w, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
d = defaultdict(int)
L = [0]*10
L[0] = (h-2) * (w-2)
for a, b in AB:
  for i in range(-1, 2):
    for j in range(-1, 2):
      y, x = a+i, b+j
      if 1 < y < h and 1 < x < w:
        d[(y, x)] += 1
        L[d[(y, x)]] += 1
        L[d[(y, x)]-1] -= 1
print(*L, sep="\n")

Measured memory_bytes: 191180
#include<stdio.h>
#define NUM 50
int main()
{
  int k,n;
  int i,j;
  int rep,ans=0;
  int l[NUM];
  scanf("%d%d",&n,&k);
  for(i=0;i<n;i++)
    {
      scanf("%d",&l[i]);
      for(j=i;j>0;j--)
	{
	  if(l[j]>l[j-1])
	    {
	      rep=l[j];
	      l[j]=l[j-1];
	      l[j-1]=rep;
	    }
	  else break;
	}
    }
  for(i=0;i<k;i++) ans+=l[i];
  printf("%d\n",ans);
  return 0;
}


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

int main()
{
  vector <int> p;
  int n, k, t;
  
  cin >> n >> k;
  
  for (int i=0; i<n; i++)
  {
    cin >> t;
    p.push_back(t);
  }
  
  sort(p.begin(), p.end());
  t = 0;
  
  for (int i=0; i<k; i++)
    t += p[i];
  
  cout << t;
  return 0;
}

Measured memory_bytes: 3184
#include<iostream>
int main()
{
	int a[300], b[300];
	int i = 0;
	int j = 0;
	int v = 0, t = 0;
	for ( int i = 0; i < 300; i++ )
	{
		std::cin >> a[i] >> b[i];
		if ( a[i] == 0 && b[i] == 0 )
		{
			break;
		}
		else
			{
				j++;
		    }
	}
		for ( int i = 0; i < j; i++ )
	{
		for ( int v = 0; v < a[i]; v++ )
	{
		for ( int t = 0; t <= b[i]; t++ )
	{
		if ( ( v % 2 == 1 && t % 2 == 1 && t < b[i] && v < a[i] ) || (v % 2 == 0 && t % 2 == 0 && v < a[i]) && t < b[i] )
	    {
			std::cout << '#';
		}
		else if ( t == b[i] )
		{
			std::cout << '\n';
		}
		else
			{
			std::cout << '.';
		    }
	}
	}
		std::cout << '\n';
		}
	return 0;
}


Measured memory_bytes: 3040
#include <cstdio>
#include <iostream>
#define MN 1010000

int x[MN], y[MN], tot = 0;

int main()
{
	int n; scanf("%d", &n);
	if(n & 1)
	{
		for(int i = 1; i <= n; i++)
			for(int j = i + 1; j <= n; j++)
			{
				if(i + j == n) continue;
				++tot; x[tot] = i; y[tot] = j;
			}
	}
	else
	{
		for(int i = 1; i <= n; i++)
			for(int j = i + 1; j <= n; j++)
			{
				if(i + j == n + 1) continue;
				++tot; x[tot] = i; y[tot] = j;
			}
	}
	
	printf("%d\n", tot);
	for(int i = 1; i <= tot; i++) printf("%d %d\n", x[i], y[i]);
}

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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef pair<ll, ll> PLL;

signed main() {
    ll N,C;
    vector<ll> s(N),t(N),c(N);
    cin>>N>>C;
    rep(i,0,N){
        cin>>s[i]>>t[i]>>c[i];
    }
    vector<ll> ans(200020,0);
    vector<ll> timeline(200020,0);
    rep(k,1,C+1){
        fill(begin(timeline),end(timeline),0);
        rep(i,0,N){
            if (c[i] != k)
                continue;
            timeline[ 2*s[i]-1 ]++;
            timeline[ 2*t[i] ]--;
        }
        rep(i,1,200020)
            timeline[i] += timeline[i-1];
        rep(i,0,200020)
            if (timeline[i]>0)
                ans[i]++; // 同じチャネルの番組は一つの録画機でとれば充分
    }
    auto it = max_element(begin(ans),end(ans));
    cout<<*it<<endl;
    return 0;
}


Measured memory_bytes: 151040
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <math.h>
#include <utility>
#include <set>
#include <map>
#include <cstring>
#include <cstdio>
#include <stack>
#define INF 1000000000
#define rep(i,n) for(int i =0;i<n;i++)
using namespace std;
typedef long long int ll;

int n,k,s;
int ans = 0;
vector<int> used(21,0);

void dfs(int m, int sum){
    if(m==0){
        if(sum == s) ans++;
        return;
    }
    for (int i=1; i<=n;i++) {
        if (used[i]==0){
            for (int j=1; j<=i; j++) {
                if(used[j]==0) used[j]=m;
            }
            dfs(m-1, sum+i);
            for (int j=1; j<=i; j++) {
                if(used[j]==m)used[j]=0;
            }
        }
    }
    return;
}

int main(){
    for(;;){
        cin >>n>>k>>s;
        if(!n)break;
        rep(i,21)used[i]=0;
        ans = 0;
        dfs(k,0);
        cout << ans <<endl;
    }
}

Measured memory_bytes: 1192
n=int(input())
AC=0
WA=0
TLE=0
RE=0
for i in range(n):
    s=input()
    if s=="AC":
        AC+=1
    elif s=="WA":
        WA+=1
    elif s=="TLE":
        TLE+=1
    elif s=="RE":
        RE+=1
print("AC x "+str(AC))
print("WA x "+str(WA))
print("TLE x "+str(TLE))
print("RE x "+str(RE))

Measured memory_bytes: 9116
#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
	double pi = 2.0 * asin(1.0);
	double a = 0.0, b = 0.0, x = 0.0, n = 0.0, r = 0.0, b_default = 0.0, b_diff = 0.0, b_diff_2 = 0.0;
	
	std::cin >> a >> b >> x;

	n = x * 2.0 / (a * b);
	if (n <= a)
	{
		r = 90.0 - std::acos( b / std::sqrt( n * n + b * b )) * 180.0 / pi;
	}
	else
	{
		b_default = x / ( a * a );
		b_diff = b - b_default;
		b_diff_2 = b_diff * 2;
		r = 90.0 - std::acos(b_diff_2 / std::sqrt(a * a + b_diff_2 * b_diff_2)) * 180.0 / pi;
	}

	std::cout << std::fixed << std::setprecision(10) <<  r << std::endl;
	return 0;
}


Measured memory_bytes: 256
a=input()
b=input()
la,lb = len(a), len(b)
if a==b:
    print('No')
elif (la< lb and set(a)==set(b)):
    print('Yes')
else:
    sa = sorted(a)
    sb = sorted(b, reverse = True)
    if (sa[:lb] < sb):
        print('Yes')
    else:
        print('No')

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

int d(int a, int b){
  return abs(a-b);
}
int shortcut(int a, int b, int c){
  int d1,d2,d3;
  d1 = d(a,c);
  d2 = d(a,b);
  d3 = d(b,c);
  if(a==c){
    return 2*d2;
  }else if(a==b || b==c){
    return 0;
  }else if(d1>d2 && d1>d3){
    return 0;
  }else if(d2>d1 && d2>d3){
    return 2*d3;
  }else if(d3>d1 && d3>d2){
    return 2*d2;
  }
}

long long N,cost;
int A[100000];


int main(){
  cin >> N;
  for(int i=0; i<N; i++){
    cin >> A[i];
    if(i==0) cost += d(0,A[0]);
    else cost += d(A[i-1],A[i]);
  }
  cost += d(A[N-1],0);

  for(int i=0; i<N; i++){
    if(i==0) cout << cost-shortcut(0,A[0],A[1]) << endl;
    else if(i==N-1) cout << cost-shortcut(A[N-2],A[N-1],0) << endl;
    else cout << cost-shortcut(A[i-1],A[i],A[i+1]) << endl;
  }
}

Measured memory_bytes: 1664
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <sstream>

#define rep(i, a) REP(i, 0, a)
#define REP(i, a, b) for(int i = a; i < b; ++i)
#define rrep(i, a) RREP(i, a, 0)
#define RREP(i, a, b) for(int i = a; i >= b; --i)
#define repll(i, a) REPLL(i, 0, a)
#define REPLL(i, a, b) for(ll i = a; i < b; ++i)
#define rrepll(i, a) RREPLL(i, a, 0)
#define RREPLL(i, a, b) for(ll i = a; i >= b; --i)

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> P;
typedef std::pair<int, P> PP;
const double PI = 3.14159265358979323846;
const double esp = 1e-9;
const int infi = (int)1e+9 + 10;
const ll infll = (ll)1e+18 + 10;

int a, b;

void extgcd(int a, int b, int& x, int& y){
	int u, v, q, tmp;

	x = 1; y = 0; u = 0; v = 1;
	while (b > 0) {
		q = a / b;
		tmp = u; u = x - q * u; x = tmp;
		tmp = v; v = y - q * v; y = tmp;
		tmp = b; b = a - q * b; a = tmp;
	}
}


int main(){
	int x, y;
	std::cin >> a >> b;
	extgcd(a, b, x, y);
	std::cout << x << " " << y << std::endl;
	return 0;
}

Measured memory_bytes: 1164
a =[]
for i in range(5):
    a.append(int(input()))
k = int(input())

temp = i
for i in range(0,5):
    for j in range(i+1,5):
        if abs(a[i]-a[j]) > k:
            print(":(")
            exit()
else :
    print("Yay!")
    

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


int main(){
    int N;
    cin >> N;
    if(N==2){
	cout << 2 << endl;
	return 0;
    }
    
    for(int i=N;; i++){
	for(int j=2; ; j++){
	    if(i%j==0){
		break;
	    }
	    else if(j*j>N){
		cout << i <<endl;
		return 0;
	    }
	}	
    }
}



Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const int MAXN = 2345;
int pb[MAXN], pw[MAXN], costw[MAXN][MAXN], costb[MAXN][MAXN];
int dp[MAXN][MAXN];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= 2 * N; i++) {
        int tmp;
        char c;
        scanf(" %c %d", &c, &tmp);
        if (c == 'W') pw[tmp] = i;
        else pb[tmp] = i;
    }
    for (int i = 0; i < N; i++) {
        for (int j = i + 2; j <= N; j++)
            if (pw[j] < pw[i + 1]) costw[i][0]++;
        int sum = 0;
        costw[i][N] = costw[i][0];
        for (int j = N; j >= 1; j--) {
            if (pb[j] < pw[i + 1]) sum++;
            costw[i][j - 1] = costw[i][0] + sum;
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = i + 2; j <= N; j++)
            if (pb[j] < pb[i + 1]) costb[0][i]++;
        int sum = 0;
        costb[N][i] = costb[0][i];
        for (int j = N; j >= 1; j--) {
            if (pw[j] < pb[i + 1]) sum++;
            costb[j - 1][i] = costb[0][i] + sum;
        }
    }
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            if (!i && !j) continue;
            if (!i) dp[i][j] = dp[i][j - 1] + costb[0][j - 1];
            else if (!j) dp[i][j] = dp[i - 1][j] + costw[i - 1][0];
            else dp[i][j] = min(dp[i - 1][j] + costw[i - 1][j], dp[i][j - 1] + costb[i][j - 1]);
        }
    }
    printf("%d\n", dp[N][N]);
    return 0;
}


Measured memory_bytes: 59648
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int> vec(N);
  for(int i=0;i<N;i++){
  cin>>vec.at(i);
  }
  int count=0;
  for(int i=0;i<N;i++){
    if(vec.at(i)%2==0){
      if(vec.at(i)%3!=0&&vec.at(i)%5!=0)
        count++;
    }
  }
  if(count>0) cout<<"DENIED"<<endl;
  else cout<<"APPROVED"<<endl;
}
  

Measured memory_bytes: 3592
using System;
using System.Linq;
using System.Collections.Generic;

namespace abc153
{
    class Program
    {
        static void Main(string[] args)
        {
            var h= Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
            int ans = 0;
            while (true)
            {
                if (h[0] <= 0) break;

                h[0] = h[0] - h[1];
                ans++;
            }
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <stack>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <vector>
#include <cmath>
#include <stdlib.h>
#include <unordered_map>
#define ll long long
using namespace std;
map<string,int> mp;
int main()
{
    int n,f=1;
    char last;
    cin>>n;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        if(mp[s]>=1)
            f=0;
        mp[s]++;
        if(i==0){
            last=s[s.size()-1];
            continue;
        }
        if(s[0]!=last)
            f=0;
        last=s[s.size()-1];
    }
    if(f){
        cout<<"Yes";
    }
    else
        cout<<"No";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;
const int INF = 10000000;

bool isSame(string s){
    range(i,1,s.size()){
        if(s[i] != s[0]) return false;
    }
    return true;
}

int main(){
    string s;
    cin >> s;

    int ans = INF;
    for(char i = 'a'; i != 'z' + 1; i++){
        string tmp = s;
        int cnt = 0;
        while(not isSame(tmp)){
            string ns;
            rep(j,tmp.size() - 1){
                if(tmp[j] == i || tmp[j + 1] == i) ns+=i;
                else ns += tmp[j];
            }
            tmp = ns;
            cnt++;
        }
        ans = min(ans,cnt);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (lli i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

lli n, m;
unordered_map<string, lli> um;
int main() {
  cin >> n;
  for (lli i=0; i<n; ++i) {
    string s; cin >> s;
    um[s]++;
  }
  cin >> m;
  for (lli i=0; i<m; ++i) {
    string s; cin >> s;
    um[s]--;
  }
  lli ans = 0;
  for (auto& p : um) {
    ans = max(ans, p.second);
  }
  cout << ans << '\n';
  return 0;
}



Measured memory_bytes: 256
n, x, y = map(int, input().split())
x -= 1
y -= 1
dist = [0]*(n-1)
for start in range(n):
    for end in range(start+1, n):
        dst = min(end-start, abs(x-start) + abs(end-y) + 1)
        dist[dst-1] += 1

for d in dist:
    print(d)

Measured memory_bytes: 3444
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

#define mod 1e9+7
#define ll long long int
#define epsilon 1e-7

ll mi(ll x, ll y){
    if(x<y)return x;
    return y;
}
char ap[50][51];
int dis[50][50];
int h, w;
void dfs(int i, int j, int di){
    if(i < 0 || j < 0 || i >= h || j >= w || ap[i][j] == '#')return;
    if(dis[i][j] > di){
        dis[i][j] = di;
        dfs(i+1,j,di+1);
        dfs(i-1,j,di+1);
        dfs(i,j+1,di+1);
        dfs(i,j-1,di+1);
    }
    return;
}
int main(void){
    scanf("%d %d", &h, &w);
    for(int i = 0;i < h;i++){
        scanf("%s", &ap[i]);
    }
    for(int i = 0;i < h;i++){
        for(int j = 0;j < w;j++){
            dis[i][j] = mod;
        }
    }
    //printf("dfs\n");
    dfs(0,0,0);
    if(dis[h-1][w-1] == mod)printf("-1\n");
    else {
        int white = 0;
        for(int i = 0;i < h;i++){
            for(int j = 0;j < w;j++){
                if(ap[i][j] == '.')white++;
            }
        }
        printf("%d\n", white - dis[h-1][w-1] - 1);
    }
    /*for(int i = 0;i < h;i++){
        for(int j = 0;j < w;j++){
            printf("%d ", dis[i][j]);
        }
        printf("\n");
    }*/
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

bool isprime(int x){
  if(x==2){ return true; }
  if(x<2 || x%2==0){ return false; }
  
  int sqrtx = ceil(sqrt(x));
  for(int i=3; i<=sqrtx; i+=2){ if(x%i==0){ return false; } }
  return true;
}

int calc(int n, int x){
  int k=0;
  while(n>1){
    k += n/x;
    n /= x;
  }
  return k;
}

int main(){
  int n;
  cin >> n;
  ll ans=1;
  for(int i=1; i<=n; i++){
    if(isprime(i)){
      ans *= (calc(n,i)+1);
      ans %= mod;
    } 
  }
  cout << ans << endl; 
  return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [10**9] * N

for i in range(N):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        for j in range(1, K+1):
            if j > i:
                break
            dp[i] = min(dp[i], dp[i - j] + abs(h[i - j] - h[i]))

print(dp[N-1])

Measured memory_bytes: 84840
/*
　　　　　　 ＿＿
　　　　　／＞　　 フ
　　　　　| 　_　 _ l
　 　　　／` ミ＿xノ    見ちゃだめ！
　　 　 /　　　 　 |　
　　　 /　 ヽ　　 ﾉ　　
　 　 │　　|　|　|　　
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)__)
　＼二つ
*/

#include <bits/stdc++.h>
using namespace std;
#define SORT(a) sort((a).begin(), (a).end())
#define RSORT(a) reverse((a).begin(), (a).end())
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
const long long INF = 1LL << 60;

int main() {
  int n, m, i;
  cin >> n >> m;
  int p[m] = {}, y[m] = {};
  vector<int> v[n + 1];
  for (i = 0; i < m; i++) {
    cin >> p[i] >> y[i];
    v[p[i]].push_back(y[i]);
  }
  for (i = 0; i <= n; i++) {
    SORT(v[i]);
  }
  for (i = 0; i < m; i++) {
    printf("%06d%06d\n", p[i],
           (int)(lower_bound(v[p[i]].begin(), v[p[i]].end(), y[i]) -
                 v[p[i]].begin()) +
               1);
  }
  return 0;
}

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

int main() {
  int N,M;
  cin>> N >> M;
  vector<int> a(M),b(M);
  vector<int> count(N);
  
  for(int i=0;i<M;i++){
   	cin>>a.at(i)>>b.at(i); 
  }
  
  for(int j=0;j<M;j++){
   	count[(a.at(j)-1)]+=1;
    count[(b.at(j)-1)]+=1;
  }
  
  for(int k=0;k<N;k++)
    cout<<count.at(k)<<endl;
  
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    a48(readLineList())
}

fun readLineList(): Array<String> {
    val lineList = mutableListOf<String>()
    while (true) {
        val line = readLine()
        if (line.isNullOrBlank()) {
            break
        } else {
            lineList.add(line!!)
        }
    }
    return lineList.toTypedArray()
}

fun a48(args: Array<String>) {
    if (args.size != 1) {
        throw IllegalArgumentException()
    }
    println(args[0].split(" ").map { it -> it[0] }.toCharArray())
}


Measured memory_bytes: 36516
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = int(input())

# 1 * 1 * 2 * 3 * 4 * 5 * ... * i % (10^9 + 7)
mod = 1
for n in range(N):
    # 先にmodを取った値を掛け算していく
    mod = mod % (pow(10, 9) + 7)
    mod = mod * (n + 1)
else:
    # 最後にもう１度modを取る
    mod = mod % (pow(10, 9) + 7)
    print(mod)


Measured memory_bytes: 2940
#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#include<cstdlib>
using namespace std;

int n;
int spx[10],spy[10];

int main(){
	int x,y;
	while(cin>>x>>y,x|y){
		vector<pair<int,int> > a,b;
		cin>>n;
		for(int i=0;i<n;i++)cin>>spx[i]>>spy[i];
		a.push_back(make_pair(x,y));
		for(int i=0;i<n;i++){
			for(int j=0;j<a.size();j++){
				for(int dx=-2;dx<=2;dx++){
					for(int dy=-2;dy<=2;dy++){
						if(abs(dx)==2&&abs(dy)==2 || abs(dx)!=2&&abs(dy)!=2)continue;
						int nx=a[j].first+dx, ny=a[j].second+dy;
						if(abs(nx-spx[i])<=1 && abs(ny-spy[i])<=1){
							b.push_back(make_pair(nx,ny));
						}
					}
				}
			}
			a.clear();
			a.swap(b);
		}
		cout<<(a.empty()?"NA":"OK")<<endl;
	}
	return 0;
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ll N;
	ll D, X;
	cin >> N;
	cin >> D >> X;
	ll A[N + 3];
	ll sum = X;
	for (ll i = 0; i < N; i++) {
		cin >> A[i];
		sum += (D - 1) / A[i] + 1;
	}
	cout << sum << endl;
}



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

int main() {
    string s;
    cin >> s;
    rep(i, s.size()) cout << 'x';
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#define N 100005
using namespace std;

typedef long long ll;
ll M = 1e9 + 7;
ll n, ans, a[N];
string l;

ll f(ll p) {
	if (p == n) return 1;
	if (l[p] == '0') return f(p + 1);
	return (f(p + 1) * 2 + a[p + 1]) % M;
}

int main()
{
	ll i;
	cin >> l;
	n = l.size();
	a[n] = 1;
	for (i = n - 1; i >= 0; i--) a[i] = a[i + 1] * 3 % M;
    cout << f(0) << endl;
    return 0;
}

Measured memory_bytes: 2816
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cctype>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int r, l;
    int n = s.size();
    r = 0;
    l = n - 1;
    bool f = true;
    while (r < l)
    {
        if (s[r] != s[l])
        {
            f = false;
            break;
        }
        r++;
        l--;
    }
    if (f == false)
    {
        cout << "No" << endl;
        return 0;
    }

    r = 0;
    l = ((n - 1) / 2) - 1;
    f = true;
    while (r < l)
    {
        if (s[r] != s[l])
        {
            f = false;
            break;
        }
        r++;
        l--;
    }
    if (f == false)
    {
        cout << "No" << endl;
        return 0;
    }

    l = n - 1;
    r = ((n + 3) / 2) - 1;
    f = true;
    while (r < l)
    {
        if (s[r] != s[l])
        {
            f = false;
            break;
        }
        r++;
        l--;
    }
    if (f == false)
    {
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
def main():
    N = int(input())
    X = {}
    for a in map(int, input().split()):
        for i in range(-1, 2):
            if (a+i) not in X:
                X[a+i] = 0
            X[a+i] += 1
    print(max(X.values()))


if __name__ == "__main__":
    main()


Measured memory_bytes: 61996
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

string s, t;
int q;
int a[100010], b[100010], c[100010], d[100010];

int sum_s[100010], sum_t[100010];

int subsum_s(int p, int q) {
    return (sum_s[q] - sum_s[p-1]) % 3;
}
int subsum_t(int p, int q) {
    return (sum_t[q] - sum_t[p-1]) % 3;
}

void solve() {
    sum_s[0] = sum_t[0] = 0;
    for (int i = 0; i < s.size(); i++) sum_s[i+1] = sum_s[i] + (s[i]-'A'+1);
    for (int i = 0; i < t.size(); i++) sum_t[i+1] = sum_t[i] + (t[i]-'A'+1);

    for (int i = 0; i < q; i++) {
        cout << (subsum_s(a[i], b[i]) == subsum_t(c[i], d[i]) ? "YES" : "NO") << endl;
    }
}

void input() {
    cin >> s >> t >> q;
    for (int i = 0; i < q; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
}

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

    input();
    solve();
}


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

#define LL long long

#define FOR(INDEX, START, END) for (int INDEX = (START); INDEX < (END); ++INDEX)
#define REP(INDEX, COUNT) for (int INDEX = 0; INDEX < (COUNT); ++INDEX)

template <class T>
class Array2D {
public:
    Array2D(LL w, LL h, T v = T()) {
        m_vec.resize(w * h, v);
        m_width = w;
        m_height = h;
    }
    
    T& at(LL x, LL y) {
        return m_vec[y * m_width + x];
    }
    
    T const& at(LL x, LL y) const {
        return m_vec[y * m_width + x];
    }
    
    LL width() const {
        return m_width;
    }
    
    LL height() const {
        return m_height;
    }
    
    void print() const {
        for (LL y = 0; y < m_height; ++y) {
            for (LL x = 0; x < m_width; ++x) {
                cout << at(x, y) << " ";
            }
            cout << endl;
        }
    }
    
private:
    vector<T> m_vec;
    LL m_width;
    LL m_height;
};


int main()
{
    LL H, W;
    cin >> H >> W;
    
    Array2D<LL> field(W, H);
    for (LL y = 0; y < H; ++y) {
        for (LL x = 0; x < W; ++x) {
            cin >> field.at(x, y);
        }
    }
    
    vector<string> results;
    
    for (LL y = 0; y < H; ++y) {
        for (LL x = 0; x < W; ++x) {
            if ((field.at(x, y) % 2) != 0) {
                if (x + 1 < W) {
                    field.at(x, y) -= 1;
                    field.at(x + 1, y) += 1;
                    
                    stringstream ss;
                    ss << y+1 << " " << x+1 << " " << y+1 << " " << x+2;
                    results.push_back(ss.str());
                } else if (y + 1 < H) {
                    field.at(x, y) -= 1;
                    field.at(x, y + 1) += 1;
                    
                    stringstream ss;
                    ss << y+1 << " " << x+1 << " " << y+2 << " " << x+1;
                    results.push_back(ss.str());
                }
            }
        }
    }
    
    cout << results.size() << endl;
    for (auto const& result : results) {
        cout << result << endl;
    }
    
    return 0;
}


Measured memory_bytes: 10868
using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
    public static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        long L0 = 2;
        long L1 = 1;
        long L2 = 1;
        for (int i = 0; i < N-1; i++) {
            L2 = L0 + L1;
            L0 = L1;
            L1 = L2;
        }
        Console.WriteLine(L2);
    }
}


Measured memory_bytes: 11220
#include <iostream>
#include <string>

using namespace std;
typedef long long ll;

int main(){
    string s;
    cin >> s;
    const ll half = (s.size() + 1) / 2;
    if(s.size() % 2 == 1){
        ll i = 0;
        for(; i <= s.size() / 2; ++i){
            if(s.at(half - 1 + i) != s.at(half - 1) ||
               s.at(half - 1 - i) != s.at(half - 1)){
                break;
            }
        }
        cout << half + i - 1 << endl;
    }else{
        ll i = 1;
        for(; i <= s.size() / 2; ++i){
            if(s.at(half - 1 + i) != s.at(half - 1) ||
               s.at(half - 1 - (i - 1)) != s.at(half - 1)){
                break;
            }
        }
        cout << half + i - 1 << endl;
    }
    return 0;
}


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

#define int            long long 
#define vi             vector<int>
#define mod            1000000007
#define MAX            INT_MIN
#define MIN            INT_MAX
#define ff             first
#define ss             second
#define pb             push_back
#define mp             make_pair
#define pii            pair<int,int>
#define pqb            priority_queue<int>
#define floop(x,n)       for(int i=x;i<n;i++)
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define ps(x,y)        fixed<<setprecision(y)<<x         
#define FIO            ios_base::sync_with_stdio(false); cin.tie(NULL);
                  
void c_p_c()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif

}

void solutionA()
{
	int n;
	cin>>n;

	if(n%1000==0)
	{
		cout<<"0"<<endl;
	}
	else
	{
		cout<<1000-(n%1000)<<endl;
	}
}

void solutionB()
{
	int n;
	cin>>n;

	int a=0,b=0,c=0,d=0;

	while(n--)
	{
		string s;
		cin>>s;

		if(s=="AC")
		{
			a++;
		}
		else if(s=="TLE")
		{
			b++;
		}
		else if(s=="WA")
		{
			c++;
		}
		else
		{
			d++;
		}
	}

	cout<<"AC"<<" x "<<a<<endl;
	cout<<"WA"<<" x "<<c<<endl;
	cout<<"TLE"<<" x "<<b<<endl;
	cout<<"RE"<<" x "<<d<<endl;
	
}

void solutionC()
{

}

int32_t main()
{
	c_p_c();

	//solutionA();
	solutionB();
	//solutionC();

	return 0;
}


Measured memory_bytes: 3632
n,m,x = map(int,input().split())
c = [[int(i) for i in input().split()] for _ in range(n)]
inf = float("inf")
ans = inf
for i in range(1<<n):
    cnt = [0]*m
    cost = 0
    for j in range(n):
        if i >> j & 1:
            cost += c[j][0]
            for k in range(1,m+1):
                cnt[k-1] += c[j][k]
    for j in range(m):
        if cnt[j] < x: break
    else:
        ans = min(cost,ans)
print(ans if ans != inf else -1)


Measured memory_bytes: 9216
#include <stdio.h>
#include <vector>

using namespace std;

struct Node{
	Node(){
		brother = parent = -1;
		height = depth = num_of_children = 0;
	}
	int parent,brother,depth,num_of_children,height;
	vector<int> children;
};

void calcDepth(Node nodes[],int root_id){
	for(int i = 0;i < nodes[root_id].num_of_children;i++){
		nodes[nodes[root_id].children[i]].depth = nodes[root_id].depth+1;
		calcDepth(nodes,nodes[root_id].children[i]);
	}
}

void calcHeight(Node nodes[],int height,int parent){
	nodes[parent].height = max(nodes[parent].height,height+1);
	if(nodes[parent].parent != -1) calcHeight(nodes,height+1,nodes[parent].parent);
}

int main(){
	int n,id,left_id,right_id,root_id;
	scanf("%d",&n);
	Node nodes[n];

	for(int i = 0; i < n; i++){
		scanf("%d %d %d",&id,&left_id,&right_id);
		if(left_id != -1){
			nodes[id].children.push_back(left_id);
			nodes[id].num_of_children++;
			nodes[left_id].parent = id;
		}
		if(right_id != -1){
			nodes[id].children.push_back(right_id);
			nodes[id].num_of_children++;
			nodes[right_id].parent = id;
		}
		if(left_id != -1 && right_id != -1){
			nodes[left_id].brother = right_id;
			nodes[right_id].brother = left_id;
		}
	}

	for(root_id = 0; root_id < n; root_id++){
		if(nodes[root_id].parent == -1) break;
	}

	if(n > 1){
		calcDepth(nodes,root_id);

		for(int i = 0; i < n; i++){
			if(nodes[i].num_of_children == 0) calcHeight(nodes,0,nodes[i].parent);
		}
	}

	for(int i = 0; i < n; i++){
		printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d,"
				,i,nodes[i].parent,nodes[i].brother,nodes[i].num_of_children,nodes[i].depth,nodes[i].height);
		if(nodes[i].parent == -1){
			printf(" root\n");
		}else if(nodes[i].num_of_children == 0){
			printf(" leaf\n");
		}else{
			printf(" internal node\n");
		}

	}
}



Measured memory_bytes: 2800
#pragma region head
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << endl
#define int long long
typedef long long ll;
#define double long double
typedef double ld;
const int INF = 1001001001001001001ll;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;
const double PI = acos(-1.0);

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      s << '\n';
  }
  return s;
}

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;
}

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}
#pragma endregion

signed main() {
  int N;
  cin >> N;
  vector<int> A(N);
  int sum = 0;
  rep(i, N) {
    cin >> A[i];
    sum += A[i];
  }

  int num1 = N * (N + 1) / 2;
  if (sum % num1 != 0) {
    cout << "NO\n";
    return 0;
  }

  int op = sum / num1;

  vector<int> diff(N);
  rep(i, N) {
    diff[i] = A[(i + 1) % N] - A[i];
    diff[i] -= op;
    diff[i] *= -1;
  }

  int cnt = 0;
  rep(i, N) {
    if (diff[i] < 0 || diff[i] % N != 0) {
      cout << "NO\n";
      return 0;
    }
    cnt += diff[i] / N;
  }

  if (cnt == op)
    cout << "YES\n";
  else
    cout << "NO\n";
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long

using namespace std;

int n;

int main()
{
    ios::sync_with_stdio(0);
    vector<ll> v , vv;
    cin >> n;
    for (int i=0;i<n;i++)
    {
        ll x , y;
        cin >> x >> y;
        if (n % 2 == 0)
        {x *= 2;
        y *= 2;}
        v.push_back(x);
        vv.push_back(y);
    }
    sort(v.begin() , v.end());
    sort(vv.begin() , vv.end());
    ll st;
    if (n % 2 == 1)st = v[(n-1)/2];
    else st = (v[(n-1)/2+1] + v[(n-1)/2])/2;
    ll en;
    if (n % 2 == 1)en = vv[(n-1)/2];
    else en = (vv[(n-1)/2+1] + vv[(n-1)/2])/2;
    //cout << st << " " << en << endl;
    cout << en - st + 1 << endl;
    return 0;
}


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

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, __VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

#define MOD 1000000007
#define INF 1000000000
#define MAX_N 100010

ll N;
map<ll, ll> ans_map;

map<int, int> prime_factor(int n) {
    map<int, int> res;
    for(int i = 2; i * i <= n; ++i) {
        while(n % i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if(n != 1) { res[n] = 1; }
    return res;
}

int main()
{
    cin >> N;

    for(ll i = 2; i <= N; ++i) {
        map<int, int> m = prime_factor(i);
        for(auto& v : m) {
            ans_map[v.first] += v.second;
        }
    }
    ll ans = 1;
    for(auto& tmp : ans_map) {
        ans *= (tmp.second + 1);
        ans %= MOD;
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <set>
#include <vector>

typedef std::vector<std::vector<int> > TPuzzle;

void MakeGoal(TPuzzle& Goal)
{
	Goal.resize(3);
	for(int i = 0; i < 3; ++i){
		Goal[i].resize(3);
		for(int j = 0; j < 3; ++j){
			Goal[i][j] = (1 + 3 * i + j) % 9;
		}
	}
}

void ZeroPosition(int& Row, int& Col, const TPuzzle& Puzzle)
{
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 3; ++j){
			if(Puzzle[i][j] == 0){
				Row = i;
				Col = j;
			}
		}
	}
}

enum TMovePattern
{
	mpUp,
	mpDown,
	mpLeft,
	mpRight
};

bool Movable(const TPuzzle& Puzzle, const TMovePattern& Pattern)
{
	int Row, Col;
	ZeroPosition(Row, Col, Puzzle);
	switch(Pattern){
	case mpUp    : return Row != 0;
	case mpDown  : return Row != 2;
	case mpLeft  : return Col != 0;
	case mpRight : return Col != 2;
	}
	assert(false);
	return false;
}

TPuzzle Move(TPuzzle Puzzle, const TMovePattern& Pattern)
{
	int Row, Col;
	ZeroPosition(Row, Col, Puzzle);
	switch(Pattern){
	case mpUp    : std::swap(Puzzle[Row][Col], Puzzle[Row - 1][Col]);break;
	case mpDown  : std::swap(Puzzle[Row][Col], Puzzle[Row + 1][Col]);break;
	case mpLeft  : std::swap(Puzzle[Row][Col], Puzzle[Row][Col - 1]);break;
	case mpRight : std::swap(Puzzle[Row][Col], Puzzle[Row][Col + 1]);break;
	}
	return Puzzle;
}

void RenewTargets(
	const TPuzzle& Puzzle,
	const TMovePattern& Pattern,
	std::vector<TPuzzle>& Targets,
	std::set<TPuzzle>& History)
{
	if(!Movable(Puzzle, Pattern)) return;
	TPuzzle Moved = Move(Puzzle, Pattern);
	if(History.find(Moved) != History.end()) return;
	Targets.push_back(Moved);
	History.insert(Moved);
}
//?¬??????????????????????????????¶???????????????

//????¬??????????????????????????¨?????????£???????????°?????????
//?¬?????????????????????????????????§?????????????????????????????????
//???????????§????±\??´????????£????????????
//?¬???????????????????????????????????????????????????????
//?±\??´????????????
//????????????
bool CountMove(std::vector<TPuzzle>& NextTargets,
	          const TPuzzle& Goal,
	          std::set<TPuzzle>& History)
{
	if(std::find(NextTargets.begin(), NextTargets.end(), Goal) != NextTargets.end()) return true;
	std::vector<TPuzzle> NewTargets;
	for(std::vector<TPuzzle>::const_iterator It = NextTargets.begin(); It != NextTargets.end(); ++It){
		RenewTargets(*It, mpUp,    NewTargets, History);
		RenewTargets(*It, mpDown,  NewTargets, History);
		RenewTargets(*It, mpLeft,  NewTargets, History);
		RenewTargets(*It, mpRight, NewTargets, History);
	}
	NextTargets = NewTargets;
	return false;
}

int CountMinimumMove(const TPuzzle& Puzzle, const TPuzzle& Goal)
{
	std::vector<TPuzzle> Targets(1, Puzzle);
	std::set<TPuzzle> History;
	int Count = 0;
	while(!CountMove(Targets, Goal, History)) ++Count;
	return Count;
}

int main()
{
	TPuzzle Goal;
	MakeGoal(Goal);
	TPuzzle Start(3, std::vector<int>(3));
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 3; ++j){
			int Input;
			std::cin >> Input;
			Start[i][j] = Input;
		}
	}
	std::cout << CountMinimumMove(Start, Goal) << std::endl;
	return 0;
}

Measured memory_bytes: 50676
#include <bits/stdc++.h>
#define MOD 998244353
#define pb push_back
#define ll long long int
#define con 1000000007
using namespace std;


int main()
{    
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);
     ll i,j,k,n;
     ll t;
     cin>>n>>j;
     //cout<<j;
     map<ll,ll> m1;
     for(i=0;i<n;i++)
     {
         cin>>k;
         m1[i+1]=k;
     }
     i=1;
     ll c=0;
     map<ll,bool> m2;
     while(1)
     {   m2[i]=true;
         i=m1[i];
         c++;
         if(m2[i]==true)
         {
             break;
         }
     }
     //cout<<c<<" ";
     if(j>=c)
     { j=j-c;
     c=0;
     ll o=i;
     while(1)
     {
         i=m1[i];
         c++;
         if(i==o)
             break;
     }
     j=j%c;
     while(j>0)
     {
         i=m1[i];
         j--;
     }
     cout<<i;
     }
     else
     {
         i=1;
         while(j>0)
         {
             i=m1[i];
             j--;
         }
         cout<<i;
     }
}

Measured memory_bytes: 28344
import fractions
n,k=map(int,input().split())
l=list(map(int,input().split()))
ma=max(l)
if k>ma:
  print('IMPOSSIBLE')
else:
  gcd=l[0]
  l.remove(gcd)
  for x in l:
    gcd=fractions.gcd(gcd,x)
  if gcd==1:
    print('POSSIBLE')
  else:
    if k%gcd==0:
      print('POSSIBLE')
    else:
      print('IMPOSSIBLE')

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

int r[2000],w[2000],n;

void solve(int sum, int k) {
  if(k==n) {
    w[sum]=1;
    return;
  }
  solve(sum,k+1);

  if(sum+r[k]<=2000){
  solve(sum+r[k],k+1);
  }
}

int main() {
  int i,p,x;
  scanf("%d",&n);

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

  solve(0,0);
  scanf("%d",&p);
  for(i=0; i<p; i++) {
    scanf("%d",&x);

    if(w[x]) {
      printf("yes\n");
    }
    else {
      printf("no\n");
    }
  }
  return 0;
}



Measured memory_bytes: 2092
#include <cstdio>
#include <algorithm>

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

using namespace std;

typedef long double ld;

int n, t, l, b;
int x[101];
ld p[101][101];
ld r[101][101];

int adjust(int p){
	return p <= n ? p : 2 * n - p;
}

int main(){
	while(scanf("%d%d%d%d", &n, &t, &l, &b), n){
		fill_n(x, n + 1, 0);
		rep(i, l){
			int p;
			scanf("%d", &p);
			x[p] = 1;
		}
		rep(i, b){
			int p;
			scanf("%d", &p);
			x[p] = 2;
		}

		rep(i, t + 1){
			fill_n(p[i], n + 1, 0);
			fill_n(r[i], n + 1, 0);
		}
		p[0][0] = 1;

		ld ans = 0;
		for(int i = 1; i <= t; ++i){
			rep(j, n + 1){
				rep(k, 6){
					p[i][adjust(j + k + 1)] += p[i - 1][j] / 6;
				}
			}

			ans += p[i][n];
			p[i][n] = 0;

			rep(j, n + 1){
				if(x[j] == 1){
					r[i][j] = p[i][j];
					p[i][j] = r[i - 1][j];
				}
				else if(x[j] == 2){
					p[i][0] += p[i][j];
					p[i][j] = 0;
				}
			}
		}
		printf("%.8Lf\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1384
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;

const ll MOD = 1e9+7;




int main(){
    ll dx[] = {0,1,0,-1},dy[] = {1,0,-1,0};
    ll ans = 0;
    ll h,w;
    cin >> h >> w;
    char c[h+2][w+2];
    bool is_visited[h+2][w+2];
    rep(i,0,h+2) rep(j,0,w+2) c[i][j] = '#';

    rep(i,1,h+1){
        rep(j,1,w+1){
            cin >> c[i][j];
        }
    }

    rep(i,1,h+1){
        rep(j,1,w+1){
            if(c[i][j] == '.'){
                rep(k,0,h+2) rep(l,0,w+2) is_visited[k][l] = false;
                is_visited[i][j] = true;
                
                queue<Pll> que;
                Pll p;
                p.fs.fs = i;
                p.fs.sc = j;
                p.sc = 0;
                que.push(p);

                while(!que.empty()){
                    Pll v = que.front();
                    que.pop();
                    ans = max(ans,v.sc);

                    rep(k,0,4){
                        if(!is_visited[v.fs.fs + dx[k]][v.fs.sc + dy[k]] && c[v.fs.fs + dx[k]][v.fs.sc + dy[k]] != '#'){
                            p.fs.fs = v.fs.fs + dx[k];
                            p.fs.sc = v.fs.sc + dy[k];
                            p.sc = v.sc + 1;
                            que.push(p);
                            is_visited[v.fs.fs + dx[k]][v.fs.sc + dy[k]] = true;
                        }
                    }
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			int[][] map = new int[n+1][n+1];
			String s = "";
			int max = 0;
			for(int i=1;i<=n;i++){
				s = sc.next();
				for(int j=1;j<=n;j++){
					if(s.codePointAt(j-1)==46){
						map[i][j] = Math.min(Math.min(map[i-1][j], map[i][j-1]), map[i-1][j-1])+1;
						if(max<map[i][j])max=map[i][j];
					}
				}
			}
			System.out.println(max);
		}
	
	}	
}

Measured memory_bytes: 59384
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int main(){
	int H, W;
	cin >> H >> W;
	for(int i = 0; i < H; i++){
		string s;
		cin >> s;
		cout << s << "\n" << s << "\n";
	}
}


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

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)

using namespace std;
using ll = long long;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  int a[n+1];
  a[1]=1;
  for(int i=2;i<=n;i++)
    cin>>a[i];
  map<int,int>mp;
   for(int i=2;i<=n;i++)
   {
    mp[a[i]]++;
   }
   for(int i=1;i<=n;i++)
    cout<<mp[i]<<endl;

  return 0;
}

Measured memory_bytes: 13816
#include <stdio.h>

#define N 10000

int main(){

  int n1,n2,i,j,cnt=0,a[N],b[N];
  //入力
  
  scanf("%d",&n1);

  for(i=0;i<n1;++i){
    scanf("%d",&a[i]);
  }

  scanf("%d",&n2);
  
  for(i=0;i<n2;i++){
    scanf(" %d",&b[i]);
  }


  //探査
  for(i=0;i<n2;i++){
    for(j=0;j<n1;++j){
      if(b[i]==a[j]){
	cnt++;
	break;
      }
    }
  }
 
  //表示

  printf("%d\n",cnt);

  return 0;

}



Measured memory_bytes: 2108
#include<cstdio>
#include<algorithm>
using namespace std;
int A[1000+2];
void Init() {
	for(int i=1;i<=999;i++)
		A[i]=A[i-1]+i;
}
int main() {
	#ifdef LOACL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	Init();
	int a,b;
	scanf("%d %d",&a,&b);
	int x;
	for(int i=1;i<=999;i++) {
		if(A[i]-a==A[i+1]-b) {
			x=A[i]-a;
			break;
		}
	}
	printf("%d\n",x);
	return 0;
}

Measured memory_bytes: 128
#
# 1124:
#

MAXD = 100

loop do
    n, q = gets.split.map(&:to_i)
    break if (n | q) == 0
    
    votes = MAXD.times.map{0}
    
    n.times do
        ns = gets.split.map(&:to_i)
        m = ns.shift
        
        for i in (0...m)
            votes[ns[i]] += 1
        end
    end
    
    maxv = 0
    mind = 0
    
    for d in (0...MAXD)
        v = votes[d]
        if maxv < v 
            maxv = v 
            mind = d 
        end
    end
    
    puts (maxv < q ? 0 : mind)
end

Measured memory_bytes: 6140
N=int(input())
S=input()
b=[0 for i in range(N+1)]

m=0
for i in range(N):
    if S[i]=='#':
        m+=1
    b[i+1]=m

ans=2*b[0]+N-b[-1]

for i in range(1,N+1):
    ans=min(ans,2*b[i]+N-i-b[-1])

print(ans)


Measured memory_bytes: 11400
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(int argc, char *argv[]){
	int n, count = 0;
	vector<int> rabbits;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		rabbits.push_back(temp - 1);
	}
	for (int i = 0; i < n; i++) {
		if (i < rabbits[i] && rabbits[rabbits[i]] == i)
			count ++;
	}
	cout << count << endl;
}


Measured memory_bytes: 892