akhauriyash/Code-Regression huggingface dataset:
N, M = list(map(int, input().split()))
P = [list(map(int, input().split())) for _ in range(N)]
Q = [list(map(int, input().split())) for _ in range(M)]

for i in range(N):
    d = 10 ** 9
    res = 0
    for j in range(M):
        _d = abs(P[i][0] - Q[j][0]) + abs(P[i][1] - Q[j][1])
        if _d < d:
            d = _d
            res = j + 1
    print(res)


Measured memory_bytes: 9196
n,m=map(int,input().split())
AB=[]
append=AB.append
for i in range(m):
  a,b=map(int,input().split())
  append([a,b])
AB.sort(key=lambda x:x[1])
c,ans=0,0
for a,b in AB:
  if a>=c:
    ans+=1
    c=b
print(ans)


Measured memory_bytes: 21340
judge = [
        [0, 1, 2], [3, 4, 5], [6, 7, 8],
        [0, 3, 6], [1, 4, 7], [2, 5, 8],
        [0, 4, 8], [2, 4, 6]
        ]

while True:
    try:
        n = list(input())
        ans = None
        for j in judge:
            if n[j[0]] == n[j[1]] == n[j[2]]:
                if n[j[0]] == 's':
                    continue
                else:
                    ans = n[j[0]]
                    break
        if ans:
            print(ans)
        else:
            print('d')
    except:
        break

Measured memory_bytes: 6724
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 500005,mo=1e9+7;
int n,a[N],f[N],g[N];
int main() {
	read(n);rep(i,1,n)read(a[i]);
	f[n+1]=1;
	per(i,n,1){
		if(a[i]!=a[i+1])g[a[i]]=(g[a[i]]+f[i+1])%mo;
		f[i]=g[a[i]];
	}
	cout<<f[1];
	return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mset(arr, val) memset((arr), (val), sizeof(arr))
#define For(i, init, n) for (int64_t (i) = (init); (i) < (n); (i)++)
#define ___ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

// const double PI = acos(-1.0), E = exp(1.0), EPS = 1e-9;
const int MOD = (int)1e9 + 7, N = (int)1e5;

int main()
{   
#ifdef MY_PREPROCESSOR
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ___
    
    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5])
        cout<< "Yes";
    else
        cout<< "No";
    
    return 0;
}

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

int main() {
    string s; cin >> s;
    int n = 15 - s.size();
    int cnt = 0;
    for (char c: s) {
        if (c == 'o') cnt++;
    }
    bool ans = (cnt + n >= 8);
    cout << (ans ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

class Main {

    public static void main( final String[] args ) {

	final Scanner stdin = new Scanner( System.in );

	final int[] dx = { 0, -1, 0, 1 };
	final int[] dy = { 1, 0, -1, 0 };
	
	while ( true ) {
	    final int N = stdin.nextInt();
	    if ( N == 0 ) {
		break;
	    }
	    boolean[][] map = new boolean[21][21];
	    for ( int i = 0; i < N; i++ ) {
		final int x = stdin.nextInt();
		final int y = stdin.nextInt();
		map[y][x] = true;
	    }
	    final int M = stdin.nextInt();
	    int x = 10;
	    int y = 10;
	    for ( int j = 0; j < M; j++ ) {
		final int dir = getIndex( stdin.next() );
		final int dist = stdin.nextInt();
		for ( int i = 0; i < dist; i++ ) {
		    x += dx[dir];
		    y += dy[dir];
		    map[y][x] = false;
		}
		//System.err.printf( "(y, x) = (%d, %d)\n", y, x );
	    }
	    if ( isFalseAll( map ) ) {
		System.out.println( "Yes" );
	    } else {
		System.out.println( "No" );
	    }
	    //printMap( map );
	}
    }

    static void printMap( boolean[][] map ) {
	for ( boolean[] array : map ) {
	    System.err.println( Arrays.toString( array ) );
	}
    }

    static boolean isFalseAll( boolean[][] map ) {
	for ( boolean[] array : map ) {
	    for ( boolean val : array ) {
		if ( val ) {
		    return false;
		}
	    }
	}
	return true;
    }

    static int getIndex( String dir ) {
	//System.err.println( dir );
	if ( "N".equals( dir ) ) {
	    return 0;
	} else if ( "W".equals( dir ) ) {
	    return 1;
	} else if ( "S".equals( dir ) ) {
	    return 2;	    
	} else { // if "E".equals( dir ) {
	    return 3;
	}
    }    
}

Measured memory_bytes: 38768
#include <iostream>
using namespace std;
int main() {
    int A, B, C;
    cin >> A >> B >> C;

    int goal = C;
    int d = 1;
    while (true) {
        goal -= A;
        if (goal <= 0) break;
        if (d % 7 == 0) goal -= B;
        if (goal <= 0) break;
        d++;
    }
    cout << d << endl;
    
    return 0;
}



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

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

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

#define MAX 100005
#define INF 1001001001

int main(int, char**)
{
  set<int> a;
  int q;
  cin >> q;
  vector<int> ans;
  rep(i,q) {
    int command; cin >> command;
    if (command == 0) {
      int x; cin >> x;
      a.insert(x);
      ans.push_back(a.size());
    } else if (command == 1) {
      int x; cin >> x;
      ans.push_back(a.find(x) != a.end());
    }
  }

  for (auto a : ans) cout << a << endl;

  return 0;
}



Measured memory_bytes: 13028
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define loop3(i,j,k,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)
#define loop4(i,j,k,l,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)for(int l=0; l<a; l++)if(i!=l&&j!=l&&k!=l)
#define rep1(i,a) for(int i=1; i<=a; i++)

#define scnd1(a) scanf("%d", &a)
#define scnd2(a,b) scanf("%d%d", &a,&b)
#define scnd3(a,b,c) scanf("%d%d%d", &a,&b,&c)
#define scnd4(a,b,c,d) scanf("%d%d%d%d", &a,&b,&c,&d)

#define cin1(a) cin >> a;
#define cin2(a,b) cin >> a >> b;
#define cin3(a,b,c) cin >> a >> b >> c;
#define cin4(a,b,c,d) cin >> a >> b >> c >> d;
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define prtd1(a) printf("%d\n", a)
#define prtd2(a,b) printf("%d %d\n", a,b)
#define prtd3(a,b,c) printf("%d %d %d\n", a,b,c)
#define prtd4(a,b,c,d) printf("%d %d %d %d\n", a,b,c,d)

#define mem(a,n) memset( a, n, sizeof(a))
typedef long long ll;
const int INF = 1e9;
const ll LLINF = 1e18;

int main() {
    int sx, sy, tx, ty;
    cin4(sx,sy,tx,ty);
    
    int lenx = tx-sx;
    int leny = ty-sy;
    
    rep(i,leny) cout<<"U";
    rep(i,lenx) cout<<"R";
    rep(i,leny) cout<<"D";
    rep(i,lenx) cout<<"L";
    cout<<"LU";
    rep(i,leny) cout<<"U";
    rep(i,lenx+1) cout<<"R";
    cout<<"DR";
    rep(i,leny+1) cout<<"D";
    rep(i,lenx+1) cout<<"L";
    cout<<"U";
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    lim = int(1e18)
    ans = 1
    for a in A:
        ans *= a
        if ans > lim:
            ans = -1
            break
        elif ans == 0:
            break
    print(ans)



if __name__ == "__main__":
    main()

Measured memory_bytes: 21660
def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = INT()
ans = {}

for i in range(N):
    S, P = input().split()
    P = int(P)
    
    if S in ans.keys():
        ans[S].append([P, i + 1])
        ans[S].sort(key = lambda x : x[0], reverse = True)
    else:
        ans[S] = [[P, i + 1]]
    
store = list(ans.keys())
store.sort()

for s in store:
    for p in ans[s]:
        print(p[1])

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

typedef long long ll;

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

    int n; cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=n-1;i>=0;i--){
        if(i>0) cout << a[i] << ' ';
        else cout << a[i]; 
    }
    cout << endl;
    return 0;
}


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

int main(void){
  int N,M;
  cin >> N >> M;
  vector<string> A(N), B(M);
  for (int i=0; i<N; i++) cin >> A.at(i);
  for (int i=0; i<M; i++) cin >> B.at(i);
  
  bool is_exist = false;
  for (int i=0; i<N-M+1; i++) {
    for (int j=0; j<N-M+1; j++) {
      if (A.at(i).at(j) != B.at(0).at(0)) continue;
      else {
        bool is_match = true;
        for (int k=0; k<M; k++) {
          for (int l=0; l<M; l++) {
            if (A.at(i+k).at(j+l) != B.at(k).at(l)) {
              is_match = false;
              break;
            }
          }
          if (!is_match) break;
        }
        if (is_match) {
          is_exist = true;
          break;
        }
      }
    }
    if (is_exist) break;
  }
  if (is_exist) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr int INFI = 1000000007;
const int mod = 1000000007;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

// mint N;

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

// combination c(N);
// mint ans = c(N,n);
// cout << ans.x << endl;

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

int main(){
  int A,B,C;
  cin >> A >> B >> C;
  if(A+B+C>=22){
    cout << "bust" << endl;
  }else{
    cout << "win" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vll = vector<vector<ll>>;
using pii = pair<int,int>;
using ull = unsigned long long;
#define FOR(i,a,b) for(ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
const double PI = acos(-1);
const double EPS = 1e-10;
const ull MOD = 1000000007;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
ull make_hash(string s,ll sz,ull b = 1e9+7){
  ull res = 0;
  ull tmp = 1;
  REP(i,sz){
    res += s[sz-i-1]*tmp;
    tmp *= b;
  }
  return res;
}
vector<ull> rolling_hash(string s,ll sz,ull b = 1e9+7){
  vector<ull> res;
  if((ll)s.size()<sz) return res;
  ull bn = 1; //bn:b^sz
  ull r = b, n = (ull)sz;
  for (; n > 0;n>>=1,r*=r) bn *= (n & 1? r:1);
  res.push_back(make_hash(s,sz));
  REP(i,(ll)s.size()-sz){
    ull tmp = b * res.back();
    tmp -= bn*s[i];
    tmp += s[sz+i];
    res.push_back(tmp);
  }
  return res;
}

int main(){
  string t,p;
  cin >> t >> p;
  ull hash_p = make_hash(p,(ll)p.size());
  auto hash = rolling_hash(t,p.size());
  REP(i,(ll)(hash.size())){
    if(hash_p == hash[i]) cout << i << endl;
  }
}




Measured memory_bytes: 14196
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include <cstdio>
#include<map>
#include<string>
#include<assert.h>
#include<unordered_map>
#include <cstring>//memset();
#define Amr_Abdelazim ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define pp pop_back
#define ll long long
#define ld long double
#define pll pair<ll,ll> 
#define vll vector<ll> 
#define vvll vector<vector<ll> >  
#define vpll vector<pair<ll,ll> > 
#define all(v) v.begin(),v.end()
#define rep(i,n)   for(int i=0;i<n;i++)
#define repp(s,i,n)   for(int i=s;i<n;i++)
#define print(v) for(auto i:v)cout<<i<<" ";cout<<"\n"; 
#define mkp make_pair
#define clr(ar,v) memset(ar,v,sizeof(ar));
#define TC ll t;cin>>t;while(t--)
#define in_vec ll n;cin>>n;vll v(n);rep(i,n)cin >> v[i];
#define EPS 1e-9
using namespace std;
const int mod = 1000000007;
const int N = 1000005;
class cmp{
public:
	bool operator() (pair<ll, pll> &A, pair<ll, pll> &B){
		return A > B;
	}
};
bool by_sec(pll &A, pll &B){
	return A.second < B.second;
}
bool is(pll a, pll b){
	return !((a.first > b.second&&a.second > b.second) || (a.first < b.first&&a.second < b.first));
}
ld dist(pll p1, pll p2){
	return (ld)sqrt((ld)(p1.first - p2.first)*(p1.first - p2.first) + (ld)(p1.second - p2.second)*(p1.second - p2.second));
}
vvll vv(100000+9);
ll dp[100000 + 9];
ll path(ll n){
	if (vv[n].size() == 0)return 0;
	if (dp[n] == -1){
		ll mx = -1;
		rep(i, vv[n].size())mx = max(mx, path(vv[n][i])+1);
		dp[n] = mx;
	}
	return dp[n];
}
int main()
{
	Amr_Abdelazim
		clr(dp, -1);
		ll n, m,ans=0;
	cin >> n >> m;
	while (m--){
		ll a, b;
		cin >> a >> b;
		vv[a].push_back(b);
	}
	repp(1, i, n + 1)
		ans = max(ans, path(i));
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 8576
require "prime"
require "mathn"

MOD = 1000000007

def powmod(x, n, m)
  if n == 0
    1
  elsif n % 2 == 0
    powmod((x * x) % m, n.div(2), m)
  else
    (powmod((x * x) % m, n.div(2), m) * x) % m
  end
end

def inv(x, p)
  powmod(x, p-2, p)
end

N = gets.to_i
A = gets.split(" ").map(&:to_i)

B = [nil] * N

N.times do |i|
  B[i] = A[0] / A[i]
end

exp = {}

N.times do |i|
  primes = Prime.prime_division(B[i].denominator)
  primes.each do |p, e|
    exp[p] = [exp[p] || 0, e].max
  end
end

lcm = exp.entries.map{|p,e| powmod(p, e, MOD) }.inject(1) {|x, y| (x * y) % MOD }

ans = 0
N.times do |i|
  ans = (ans + B[i].numerator * inv(B[i].denominator, MOD) * lcm) % MOD
end
puts ans


Measured memory_bytes: 5372
#include <bits/stdc++.h>
using namespace std;
#define endl "\n" 
#define ll long long
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define umap unordered_map
#define uset unordered_set 
#define mod 1000000007
#define imax INT_MAX
#define imin INT_MIN
#define exp 1e9
#define sz(x) (int((x).size()))
#define int long long

int helper(int *arr, int n, int k) {
    int dp[n] = {0};
    dp[0] = 0;
    for(int i = 1; i < n; i++) {
        dp[i] = imax;
        for(int j = i - 1; j >= 0 and i - j <= k; j--) {
            dp[i] = min(dp[i], dp[j] + abs(arr[i] - arr[j]));
        }
    }
    return dp[n-1];
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k; cin >> n >> k;
    int arr[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << helper(arr, n, k);
    return 0;
}

Measured memory_bytes: 5168
/* Author: Dhruv Rastogi */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define all(sdk) sdk.begin(),sdk.end()
#define mll map<int, int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)
#define repd(i,a,b) for(int i=a;i>=b;--i)
#define mp make_pair
#define hell 1000000007
#define endl '\n'
#define vvll vector<vector<int> >
#define vll vector<int>
#define mint map<int,int> 
#define sz(x) (int)x.size()
#define sll set<int>
#define pll pair<int,int>
#define F first
#define S second
const long double PI = acos(-1.0);

void solve(){  
	int k,x;
	cin>>k>>x;
	rep(i,x-k+1,x+k){
		cout<<i<<' ';
	}
	cout<<endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a,b;
  string op;
  while(op!="?"){
    cin >> a >> op >> b;
    if(op=="+"){
      cout << a+b <<endl;
    }else if(op=="-"){
      cout << a-b << endl;
    }else if(op=="*"){
      cout << a*b << endl;
    }else if(op=="/"){
      cout << a/b << endl;
    }
  }
}


Measured memory_bytes: 3128
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

int n,N,id,s;
int cntx[15];
int cnty[15];
int vis[15][15];

string tmp[6] = 
{
	"abc",
	"abc",
	"def",
	"def",
	"ghi",
	"ghi",
};

char ans[1005][1005];

void dfs(int x,int y)
{
	if (y == n + 1)
	{
		x++;
		y = 1;
	}
	if (x > 1 && cntx[x - 1] != 3)
		return;
	if (x > 1 && cnty[y] > 3)
		return;
	if (x > 1 && cntx[x] > 3)
		return;
	if (x == n + 1)
	{
		bool ok = 1;
		for (int i = 1;i <= n;i++)
			if (cntx[i] != cntx[1] || cnty[i] != cntx[1])
				ok = 0;
		if (!ok || !cntx[1])
			return;
		for (int i = 1;i <= n;i++)
			for (int j = 1;j <= n;j++)
				ans[i + s - 1][j + s - 1] = (vis[i][j] ? char('a' - 1 + vis[i][j]) : '.');
		for (int i = 1;i <= N;i++,putchar('\n'))
			for (int j = 1;j <= N;j++)
				putchar(ans[i][j]);
		exit(0);
	}
	dfs(x,y + 1);
	if (y < n && !vis[x][y] && !vis[x][y + 1])
	{
		vis[x][y] = vis[x][y + 1] = ++id;
		cntx[x]++;
		cnty[y]++;
		cnty[y + 1]++;
		dfs(x,y + 1);
		vis[x][y] = vis[x][y + 1] = 0;
		id--;
		cntx[x]--;
		cnty[y]--;
		cnty[y + 1]--;
	}
	if (x < n && !vis[x][y] && !vis[x + 1][y])
	{
		vis[x][y] = vis[x + 1][y] = ++id;
		cntx[x]++;
		cnty[y]++;
		cntx[x + 1]++;
		dfs(x,y + 1);
		vis[x][y] = vis[x + 1][y] = 0;
		id--;
		cntx[x]--;
		cnty[y]--;
		cntx[x + 1]--;
	}
}

int main()
{
	cin >> n;
	N = n;
	if (n <= 2)
	{
		puts("-1");
		return 0;
	}
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= n;j++)
			ans[i][j] = '.';
	if (n % 3 == 0)
	{
		for (int i = 1;i <= n / 3;i++)
			ans[i * 2 - 1][n - i + 1] = ans[i * 2][n - i + 1] = ans[n - i + 1][i * 2 - 1] = ans[n - i + 1][i * 2] = 'a';
		for (int i = 1;i <= N;i++,putchar('\n'))
			for (int j = 1;j <= N;j++)
				putchar(ans[i][j]);
		return 0;
	}
	s = 1;
	while (n > 11)
	{
		for (int i = 0;i < 6;i++)
			for (int j = 0;j < 3;j++)
				ans[s + n - 3 + j][s + i] = ans[s + i][s + n - 3 + j] = tmp[i][j];
		n -= 9;
		s += 6;
	}
	dfs(1,1);
	return 0;
}


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

const int N=300005;

typedef long long LL;

int k,h,t;
vector<LL> num;
LL Q[N];

void work()
{h=t=0;
 for (int i=1;i<=9;i++)
   Q[++t]=i;
 while (h<t)
   {LL cur=Q[++h];
    int x=cur%10;
	if (x!=0) Q[++t]=cur*10ll+x-1;
	Q[++t]=cur*10ll+x;
	if (x!=9) Q[++t]=cur*10ll+x+1;
    if (t>=k) break;
   }
}

int main()
{
 cin>>k;
 work();
 cout<<Q[k]<<endl;
 return 0;
}


Measured memory_bytes: 4312
#include<stdio.h>
#define N 50

int w, h, c[N][N];
int dy[8]={-1,-1,-1,0,0,1,1,1};
int dx[8]={-1,0,1,-1,1,-1,0,1};

void dfs(int y, int x){

  int i, ny, nx;
  
  c[y][x]=0;

  for(i=0;i<8;i++){
    
    ny=y+dy[i];
    nx=x+dx[i];

    if(ny<0||nx<0||h<=ny||w<=nx) continue;
    
    if(c[ny][nx]==1) dfs(ny, nx);
  }
  
}

int main(){
  
  int i, j, ans;

  while(1){
    
    scanf("%d %d", &w, &h);
    
    if(!w&&!h) break;

    ans=0;
    
    for(i=0;i<h;i++)
      for(j=0;j<w;j++) scanf("%d", &c[i][j]);
  
    for(i=0;i<h;i++)
      for(j=0;j<w;j++)
	
	if(c[i][j]==1){
	  
	  dfs(i, j);

	  ans++;
	}

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

  }
  
  return 0;
}

Measured memory_bytes: 676
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,a;
    cin >> n;
    map<int64_t,int>bou;
    vector<int64_t> hen;
    
    for (int i=0; i<n; i++){
        cin >> a;
        bou[a]++;
        if(bou[a] %2 ==0) hen.push_back(a);
    }
    
    sort(hen.begin(),hen.end());
    int64_t ans=0;
    if(hen.size() <2) cout<< ans<< endl;
    else{
    ans = hen.at(hen.size()-1)* hen.at(hen.size()-2);
    
    cout << ans << endl;
    }

}

Measured memory_bytes: 6528
#include <iostream>

using namespace std;

int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

int lcm(int a, int b)
{
   return a * b / gcd(a, b);
}

int main()
{
   int a;
   cin >> a;
   cout << lcm(a,360)/a << endl;
   return 0;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> a(n);

    int max_a = -INF;
    int max_idx;
    int min_a = INF;
    int min_idx;
    rep(i, n) {
        cin >> a[i];
        if (a[i] > max_a) {
            max_idx = i;
            max_a = a[i];
        }
        if (a[i] < min_a) {
            min_idx = i;
            min_a = a[i];
        }
    }

    if (abs(max_a) >= abs(min_a)) {
        cout << 2 * (n - 1) << endl; 
        rep(i, n) {
            if (i == max_idx) continue;
            cout << max_idx + 1 << " " << i + 1 << endl;
        }
        REP(i, 1, n) {
            cout << i << " " << i + 1 << endl;
        }
    } else {
        cout << 2 * (n - 1) << endl; 
        rep(i, n) {
            if (i == min_idx) continue;
            cout << min_idx + 1 << " " << i + 1 << endl;
        }
        for (int i = n; i > 1; i--) {
            cout << i << " " << i - 1 << endl;
        }
    }

    return 0;
}

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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007
#define PI 3.1415926535897932384626433
#define pi 3.141592653
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;
    string s;
    cin >> k >> s;
    int len = s.size();
    string s1 = "";
    if(len > k){
        for(int i = 0; i < k; i++){
            s1 += s[i];
        }
        //cout << s1 << endl;
        for(int i = 1; i <= 3; i++){
            s1 += '.';
        }
        cout << s1 << endl;
    }
    else{
        cout << s << endl;
    }


    return 0;
}


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

signed main(){
  int n,k;cin>>n>>k;
  vector<int> v(n,0);
  for(int i=0;i<k;i++){
    int d;cin>>d;
    while(d--){
      int a;cin>>a;a--;v[a]++;
    }
  }
  int ans=0;for(int i=0;i<n;i++)ans+=v[i]==0;
  cout<<ans<<endl;
}


Measured memory_bytes: 3612
#include <iostream>
#include <iosfwd>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cassert>
#include <cctype>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <sstream>
#include <complex>
#include <fstream>
#include <functional>
#include <numeric>
#include <utility>
#include <algorithm>
#include <assert.h>
#include <unordered_map>

using namespace std;
const int N = 3e5 + 500;
const int LN = 21;
const long long mod = 1e9 + 7;
const long long INF = 1LL << 57;

long long n, m, u, v, k, t, q, a, h, x;


int X[N], Y[N];

map <pair <long long, long long>, int> mp;
int main() {
   ios::sync_with_stdio(false);cin.tie(0);
   cin >> n;
   
   for (int i = 1; i <= n; ++i) {
      cin >> X[i] >> Y[i];
   }
   
   for (int i = 1; i <= n; ++i) {
      for (int j = i + 1; j <= n; ++j) {
         long long x = X[i] - X[j];
         long long y = Y[i] - Y[j];
         if (x < 0) {
            x *= -1;
            y *= -1;
         } else if (x == 0 and y < 0) y *= -1;
         
         mp[make_pair(x, y)]++;
      }
   }
   
   int mx = 0;
   
   for (auto i: mp) {
      mx = max(mx, i.second);
   }
   
   cout << n - mx << endl;
}






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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int H, W; cin >> H >> W;
	vector<vi> grid (H, vi (W));
	F0R(i, H) F0R(j, W) {char c; cin >> c; grid[i][j] = (c == '#');}

	int total = 0;
	F0R(i, H) F0R(j, W) if (grid[i][j]) {
		++total;
		int pre = 0;
		if (j > 0 && grid[i][j-1]) ++pre;
		if (i > 0 && grid[i-1][j]) ++pre;
		if (pre != 1 && (j != 0 || i != 0)) total = H*W;
	}
	print((total == H + W - 1) ? "Possible" : "Impossible");
}

Measured memory_bytes: 256
#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;

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

    string str = "";
    cin >> str;
    size_t length = str.size();
    assert(1 <= length && length <= pow(10,5));

    size_t count = 0;
    for(size_t i = 0; i <= length; ++i)
    {
        if (str[i] == '1') {
            count++;
        }
    }

    size_t min_count = min(count, length - count);
    size_t answer = min_count * 2;

    cout << answer << endl;
}

Measured memory_bytes: 512
s = input()
A = []
for i in range(2 ** (len(s) - 1)):
    t = ''
    for j in range(len(s)):
        t += s[j]
        if j != len(s) - 1:
            if i % 2 == 0:
                t += '+'
        else:
            break
        i //= 2
    A.append(eval(t))
print(sum(A))

Measured memory_bytes: 3060
#include <stdio.h>

int town_num;
int map[10][10];

int main(void) {
	int i,j,k;
	int road_num;
	int road_from,road_to,road_time;
	int now_sum,min_sum,min_town;
	while(1) {
		scanf("%d",&road_num);
		if(road_num==0)break;
		town_num=1;
		for(i=0;i<10;i++) {
			for(j=0;j<10;j++)map[i][j]=-1;
			map[i][i]=0;
		}
		for(i=0;i<road_num;i++) {
			scanf("%d%d%d",&road_from,&road_to,&road_time);
			if(map[road_from][road_to]<0 ||
				map[road_from][road_to]>road_time)
					map[road_from][road_to]=road_time;
			if(map[road_to][road_from]<0 ||
				map[road_to][road_from]>road_time)
					map[road_to][road_from]=road_time;
			if(road_to>=town_num)town_num=road_to+1;
			if(road_from>=town_num)town_num=road_from+1;
		}
		for(k=0;k<town_num;k++) {
			for(i=0;i<town_num;i++) {
				for(j=0;j<town_num;j++) {
					if(map[i][k]>=0 && map[k][j]>=0) {
						if(map[i][j]<0 || map[i][j]>map[i][k]+map[k][j])
							map[i][j]=map[i][k]+map[k][j];
					}
				}
			}
		}
		min_town=0;
		min_sum=0x7fffffff;
		for(i=0;i<town_num;i++) {
			now_sum=0;
			for(j=0;j<town_num;j++)now_sum+=map[i][j];
			if(now_sum<min_sum) {
				min_sum=now_sum;
				min_town=i;
			}
		}
		printf("%d %d\n",min_town,min_sum);
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int main(void){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if(abs(a - b) <= d && abs(b - c) <= d || abs(a - c) <= d) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void){
  int a,b,c=0;
 cin >> a >> b;
  for(int i = 1;i <= a;i++){
    for(int j = 1;j <= 12;j++){
      if(i == j){
        if(!(a == i && a > b)){
          c++;
        }
      }
    }
  }
  cout << c;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int IsThree(int x)
{
	int flag=0;
	for(int i=x;i>0;i/=10){
		if (i%10==3){
			flag=1;
			break;
		}			
	}
	return flag;
}
void call(int n)
{
	for(int i=1;i<=n;i++){
		if(i%3==0 || IsThree(i)==1)
		 cout<<" "<<i;
	}
	cout<<endl;
}

int main()
{
	int n;
	cin>>n;
	call(n);
	return 0;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) true
#define dump(x) true
#endif

int N;
bool query(V<int> v){
	cout << "?";
	for(int x: v) cout << " " << x+1;
	cout << endl;
	string T; cin >> T;
	return T == "Red";
}
bool query_substr(int x){
	V<int> v(N); rep(i,N) v[i] = x+i;
	return query(v);
}

int main(){
	cin >> N;
	int L = 0, R = N;
	bool Lans = query_substr(0);
	while(R-L>1){
		int m = (L+R)/2;
		if(query_substr(m) == Lans){
			L = m;
		}else{
			R = m;
		}
	}
	// L: Lans, R: !Lans
	int o = L, x = L+N;
	string s(N+N,'?');
	s[o] = 'R', s[x] = 'B';
	for(int i=L+1;i<L+N;i++){
		V<int> v;
		for(int x=L;x<=L+N;x++) if(x != i) v.pb(x);
		s[i] = (query(v) == Lans) ? 'B' : 'R';
	}
	V<int> other;
	rep(i,L) other.pb(i);
	for(int i=L+N;i<N+N;i++) other.pb(i);
	for(int i: other){
		V<int> v = {i};
		for(int x=L+1;x<L+N;x++) v.pb(x);
		s[i] = (query(v) == Lans) ? 'R' : 'B';
	}
	if(!Lans){
		for(char& c: s) c ^= 'R'^'B';
	}
	cout << "! " << s << endl;
}


Measured memory_bytes: 724
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
#include<stdio.h>
using namespace std;
int main(){
    int ma,mi;
    int n;
    mi=10000000;
    ma=-10000000;
    long long sums;
    sums = 0;
    cin >> n ;
    int c;
    for (int i = 0; i < n ; i++){
        cin >> c;
        sums = sums + c;
        mi = min(mi,c);
        ma = max(ma,c);
    }
    cout << mi << " " << ma << " " << sums << endl;
    return 0;
}


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

int main() {
  vector<int> vec = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

  int K;
  cin >> K;
  K--;
  
  cout << vec.at(K) << endl;
  
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
B - Toll Gates
https://beta.atcoder.jp/contests/abc094/tasks/abc094_b

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    N, M, X = map(int, input().split())
    points = [0] * (N + 1)
    gates = [int(x) for x in input().split()]
    for g in gates:
        points[g] = 1

    ans_0 = sum(points[:X])
    ans_n = sum(points[X:N])
    print(min(ans_0, ans_n))


if __name__ == '__main__':
    main(sys.argv[1:])
    


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

using namespace std;

using ll = long long;

const double eps = 1e-10;
const int MOD = 1000000007;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

typedef vector<P> G;

struct C {
  P p; double r;
  C(const P &p, double r) : p(p), r(r) { }
};

int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}


vector<P> convex_hull(vector<P> ps) {
  int n = ps.size(), k = 0;
  sort(ps.begin(), ps.end());
  vector<P> ch(2*n);
  for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
    while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
    while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) <= 0) --k;
  ch.resize(k-1);
  return ch;
}

int main () {
  cin.tie(0);
  cout << fixed << setprecision(10);

  vector<P> pts;
  map<complex<double>, int> mp;
  int n; cin >> n;
  for(int i=0;i<n;++i) {
    double x, y; cin >> x >> y;
    auto c = complex<double>(x, y);
    pts.push_back(c);
    mp[c] = i;
  }
  if(n == 2) {
    cout << 0.5 << endl << 0.5 << endl;
    return 0;
  }
  vector<P> conv = convex_hull(pts);
  double sz = conv.size();
  reverse(conv.begin(), conv.end());
  conv.push_back(conv[0]);
  reverse(conv.begin(), conv.end());
  conv.push_back(conv[1]);
  vector<double> ans(n);
  for(int i=1;i<=sz;++i) {
    double p = 0;
    // cout << dot(conv[i-1] - conv[i], conv[i+1] - conv[i]) << ":" << (sqrt(norm(conv[i-1] - conv[i])) * sqrt(norm(conv[i+1] - conv[i]))) << endl;
    double theta = acos(dot(conv[i-1] - conv[i], conv[i+1] - conv[i]) / (sqrt(norm(conv[i-1] - conv[i])) * sqrt(norm(conv[i+1] - conv[i]))));
    p = 0.5 - theta / (2 * M_PI);
    // cout << mp[conv[i]] << ":" << theta << endl;
    ans[mp[conv[i]]] = p;
  }

  for(int i=0;i<n;++i) {
    if(std::isnan(ans[i])) cout << 0.5 << endl;
    else cout << ans[i] << endl;
  }


}


Measured memory_bytes: 256
import math

a, b = map(int, input().split())

diff = abs(a - b)
if diff >= 2:
  print(0)
  exit(0)
  
n = (10 ** 9) + 7
f = math.factorial(a) * math.factorial(b)
if diff == 1:
  print(f % n)
  exit(0)
  
print((2 * f) % n)



Measured memory_bytes: 5184
#include<cstdio>

int main(){
  int a,b;
  while(true){
    scanf("%d %d", &a, &b);
    if(a == 0 && b == 0) break;
    for(int i = 1; i <= a; i++){
      for(int j = 1; j <= b; j++){
	if(i == 1 || i == a){
	  printf("#");
	}
	else if(j == 1 || j == b){
	  printf("#");
	}
	else{
	  printf(".");
	}
      }
      printf("\n");
    }
    printf("\n");
  }
}

Measured memory_bytes: 1000
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static void main(String[] args){
        try{
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

                String ss=br.readLine();
                int n=Integer.parseInt(ss);
                String[] sk=br.readLine().split(" ");
                HashMap<Long,Long> map=new HashMap<>();
                long[] arr=new long[n];
                for(int i=0;i<n;i++){
                    long y=Long.parseLong(sk[i]);
                    arr[i]=y;
                    if(map.containsKey(y)){
                        map.put(y,map.get(y)+1);
                    }else{
                        map.put(y,(long)1);
                    }
                }
            Iterator it=map.entrySet().iterator();
            long y=0;
            while(it.hasNext()){
                Map.Entry element=(Map.Entry)it.next();

                long val=(long)element.getValue();
                y+=val*(val-1)/2;

            }
                for(int i=0;i<n;i++){
                    long u=arr[i];
                    long l=map.get(u);
                    long p= y- (l*(l-1))/2 + ((l-1)*(l-2))/2;
                    System.out.println(p);
                }





        }catch(Exception e){
            System.out.println("kkkk");
        }
    }
    static boolean isPal(String s){
        for(int i=0;i<s.length()/2;i++){
            if(s.charAt(i)!=s.charAt(s.length()-i-1)){
                return false;
            }
        }
        return true;
    }
    static class pair{
        int a,b;
        public pair(int a,int b){
            this.a=a;
            this.b=b;
        }
    }
}

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

mydic = {}

for i in range(N):
    mystr = "".join(sorted(input()))
    if mystr in mydic:
        mydic[mystr] += 1
    else:
        mydic[mystr] = 1
#print(mydic)
mycnt = 0
for i in mydic.values():
    if i > 1:
        mycnt += i*(i-1)//2
print(mycnt)

Measured memory_bytes: 17852
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
  if(x<y) swap(x,y);
  int r=x%y;
  while(r!=0){
    x=y;
    y=r;
    r=x%y;
  }
  return y;
}

int main(){
  int x,y;
  cin>>x>>y;
  cout<<gcd(x,y)<<'\n';
  return 0;
}



Measured memory_bytes: 3120
#include<iostream>
#include<cstring>

using namespace std;

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

	int *a = new int[n];

	for (int i = 0; i<n; i++)
		cin >> a[i];
	
	int ans = 0, c_ans = 0, max_difference = 0;

	// ------ ans -------
	int min = a[0]; max_difference = 0;

	for (int i = 1; i < n; i++)
	{
		if (min > a[i])
			min = a[i];

		if (a[i] - min == max_difference)
		{
			ans++;
		}

		if (a[i] - min > max_difference)
		{
			max_difference = a[i] - min;
			ans = 1;
		}
	}
	//--------------------

	// ------ c_ans -------
	int max = a[n - 1]; max_difference = 0;

	for (int i = n - 2; i >= 0; i--)
	{
		if (max < a[i])
			max = a[i];

		if (max - a[i] == max_difference)
		{
			c_ans++;
		}

		if (max - a[i] > max_difference)
		{
			max_difference = max - a[i];
			c_ans = 1;
		}
	}
	//--------------------


	cout << (ans < c_ans ? ans : c_ans) << endl;

	return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
int mpow(int base, int exp);
void ipgraph(int m);
//void dfs(int u, int par);
const int mod = 1000000007;
const int N = 3e5, M = N;
const ll INF=1e18L+5;
// ll int dp[2090][3000]; 
ll int dp[200000];
int solve(int a[],int n,int i){
    if(i==n){
        return 0;

    }
    if(i==n-1)return 0;
    if(dp[i]!=-1)return dp[i];
    if(i<n-2)
    return dp[i]=min(solve(a,n,i+1)+abs(a[i]-a[i+1]),solve(a,n,i+2)+abs(a[i]-a[i+2]));
    else{
    return dp[i]=solve(a,n,i+1)+abs(a[i]-a[i+1]);
    }
}

int main(){
ios_base::sync_with_stdio(0);
ll int t,n,i,j,k,m;
t=1;
memset(dp,-1,sizeof dp);
// cin>>t;
int T;
Fo(T,1,t+1){
//  cout<<"Case #"<<T<<": ";
    cin>>n;
    int a[n];

    fo(i,n){
        cin>>a[i];
    }
    cout<<solve(a,n,0);

}

}


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

class Dice{
public:
  int c[3];

  Dice(){
    for(int i = 0 ; i < 3 ; i++)c[i] = i+1;
  }

  int getTop(){
    return c[0];
  }

  void rN(){
    swap(c[0],c[1]);
    c[1] = 7 - c[1];
  }
  
  void rE(){
    swap(c[0],c[2]);
    c[0] = 7 - c[0];
  }
  
  void rW(){
    swap(c[0],c[2]);
    c[2] = 7 - c[2];
  }
  
  void rS(){
    swap(c[0],c[1]);
    c[0] = 7 - c[0];
  }

  void rR(){
    swap(c[1],c[2]);
    c[2] = 7 - c[2];
  }

  void rL(){
    swap(c[1],c[2]);
    c[1] = 7 - c[1];
  }
};

int N;

void solve(){
  string str;
  int res = 1;
  Dice dice;

  for(int i = 0 ; i < N ; i++){
    cin >> str;
    switch(str[0]){
    case 'N':
      dice.rN();
      break;
    case 'E':
      dice.rE();
      break;
    case 'W':
      dice.rW();
      break;
    case 'S':
      dice.rS();
      break;
    case 'R':
      dice.rR();
      break;
    case 'L':
      dice.rL();
      break;
    }
    res += dice.getTop();
  }
  cout << res  << endl;
}

int main(){
  while(cin >> N,N)solve();
  return 0;
}

Measured memory_bytes: 1204
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != gy and gx != 0 and gy != 0:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = 0
        for xy in xys:
            if xy > 0:
                nx += 1
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Measured memory_bytes: 114908
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			String[] result = new String[8];
			Set<String> set = new HashSet<String>();
			String train = sc.next();
			for (int k = 1; k < train.length(); k++) {
				String front = train.substring(0, k);
				String back = train.substring(k);
				StringBuilder fsb = new StringBuilder(front);
				StringBuilder bsb = new StringBuilder(back);
				fsb.reverse();
				String revFront = fsb.toString();
				bsb.reverse();
				String revBack = bsb.toString();
				result[0] = train;
				result[1] = back + front;
				result[2] = revFront + back;
				result[3] = front + revBack;
				result[4] = back + revFront;
				result[5] = revBack + front;
				result[6] = revFront + revBack;
				result[7] = revBack + revFront;
				for (int j = 0; j < 8; j++) {
					set.add(result[j]);
				}
			}
			System.out.println(set.size());
		}
	}
}

Measured memory_bytes: 65604
import Data.List

ans ([0]:_) = []
ans ([n]:x) =
  let d = take n x
      r = drop n x
      m = maximumBy (\ [p1,d1] [p2,d2] -> compare d1 d2 ) $ map (\ [p,d1,d2] -> [p,d1+d2] ) d
  in
    m:ans r

main = do
  c <- getContents
  let i = map (map read) $ map words $ lines c :: [[Int]]
      o = ans i
  mapM_ putStrLn $ map unwords $ map (map show) o

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

int main(){
  string s, t;
  cin >> s >> t;
  int a, b;
  cin >> a >> b;
  string u;
  cin >> u;
  if (s == u) --a;
  else --b;
  cout << a << ' ' << b;
  return 0;
}


Measured memory_bytes: 256
/*author:revolIA*/
/*明日を変えるなら今日変えなきゃ*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int main(){
    int a,b;
    scanf("%d%d%*d%*d",&a,&b);
    printf("%d\n",ans[a] == b);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf = 1012345678;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

int a[100][100];


int main(){
  ll L, R;
  cin >> L >> R;
  ll m = 3000;
  for(ll i = L; i <= R; i++){
    for(ll j = i+1; j <= R; j++){
      m = min(m,(i*j)%2019);
      if(m == 0){
	cout  << 0 << endl;
	return 0;
      }
    }
  }
  cout << m << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
V = list(map(int,input().split()))

from collections import Counter

def get_counter(X):
  counter = Counter(X)
  X = sorted(counter.items(), key = lambda x:x[1], reverse = True)
  X.append((0,0))
  return X

V1 = get_counter(V[::2])
V2 = get_counter(V[1::2])

if V1[0][0] != V2[0][0]:
  print(N - (V1[0][1] + V2[0][1]))
else:
  print(N - max(V1[0][1] + V2[1][1],V1[1][1] + V2[0][1]))


Measured memory_bytes: 25424
#include <bits/stdc++.h>
using namespace std;
long long n,i,ans,d; 
long long s(long long x)
{
	long long sum=0;
	while (x)
	{
		sum+=(x%10);
		x/=10;
	}
	return sum;
}
int main(){
	cin>>n;
	d=ans=1;
	cout<<1<<endl;
	for (i=1;i<n;i++){
		if ((ans+10*d)*s(ans+d)<(ans+d)*s(ans+10*d)) d*=10;
		cout<<(ans+=d)<<endl;
	}
	return 0;
}


Measured memory_bytes: 256