akhauriyash/Code-Regression huggingface dataset:
import java.io.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1;
        String str2;
        
        str1 = br.readLine();
        str1 += str1;

        str2 = br.readLine();
        
        if(str1.indexOf(str2) == -1){
            System.out.println("No");
        }else{
            System.out.println("Yes");
        }
        
    }
}

Measured memory_bytes: 24456
X, N = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]
# 近い順でソートできないか
# 負の数でも可なので、自分自身以外の場合は必ず二つある
# 一つあった場合はもう一方
# 一つもなかった場合は小さい方を選ぶ
P = sorted(P, key=lambda a: abs(a-X))
if N == 0 or P[0] != X:
    print(X)
else:
    # 1, 2が1ずれてるか、2, 3が2ずれてるか...と確認する
    i = 1
    for j in range(1, N):
        if abs(P[j] - X) != i:
            if X - i in P:
                print(X+i)
                exit()
            else:
                print(X-i)
                exit()

        if j % 2 == 0:
            i += 1
    if N % 2 == 1:
        print(X - (N+1) // 2)
    else:
        if X-N//2 in P:
            print(X+N//2)
        else:
            print(X-N//2)
        

    

Measured memory_bytes: 62068
#n = int(input()) #入力
#a, b = (int(x) for x in input().split())
#a, b = map(int, input().split())

#a = [int(x) for x in input().split()]
#a = list(map(int, input().split()))
#a = [list(map(int,input().split(" "))) for i in range(N)]   #2次元


#a.sort() # C++ の sort(a.begin(), a.end());
#a.append(3) # C++ の a.push_back(3);


#exit(0) # return 0 的な。終了できる。
## 整数の切り捨て除算は // (ダブルスラッシュ)


#a[始まりの位置: 終わりの位置: スライスの増分] # (a は配列)


#import numpy as np  #importに100 ms 程度かかる。
import math
import copy
import string
#math.gcd(a, b) で、gcd 計算できる。
#math.pi は円周率。

INF = int(10**18) #べき乗 C++ の pow(10, 18) or 1e18;
pi = math.pi

MOD = 1000000007
#MOD = 1000000009
#MOD = 998244353




#繰り返し2乗法
#N^aの、Mで割った余りを求める。
def my_pow(N, a, M):
    if(a == 0):
        return 1
    else:
        if(a % 2 == 0):
            tempo = my_pow(N, a/2, M)
            return (tempo * tempo) % M
        else:
            tempo = my_pow(N, a - 1, M)
            return (tempo * N) % M




#N_C_a を M で割った余り
def my_combination(N, a, M):
    res = 1

    for i in range(0, a):
        res *= N - i
        res %= M

    for i in range(0, a):
        res *= my_pow(i + 1, M - 2, M)
        res %= M

    return res




#N_C_i を M で割った余りを、v[i] に代入する。
def my_combination_table(N, M, v):
    if(len(v) < N + 1):
        l = N + 1 - len(v)
        tempo = [1] * l
        v.extend(tempo)

    for i in range(1, N + 1):
        v[i] = v[i - 1] * (N - (i - 1))
        v[i] %= M

        v[i] *= my_pow(i, M - 2, M)
        v[i] %= M

    return




#math.factorial で階乗は計算できる。
#math.gcd で gcd は計算できる。
#np.gcd.reduce(A) #(Aは配列) で、Aの全ての要素の gcd が計算できる。



H, W, K = (int(x) for x in input().split())
c = [input() for i in range(0, H)]

res = 0
for i in range(0, 2 ** H):
    for j in range(0, 2 ** W):
        cnt = 0
        for h in range(0, H):
            for w in range(0, W):
                if(c[h][w] == '#' and (1 << h & i) and (1 << w & j)): cnt += 1
        if(cnt == K): res += 1

print(res)

















Measured memory_bytes: 10076
N, A, B = map(int, input().split())
if (B - A) % 2 == 0:
    print((B - A) // 2)
else:
    # N に向かうことを考える
    A_to_N_dis = N - B + 1
    A_to_N = A + A_to_N_dis
    tmp_ans = (N - A_to_N) // 2 + A_to_N_dis

    # 1に向かうことを考える
    B_to_1_dis = A - 1 + 1
    B_to_1 = B - B_to_1_dis
    ans = (B_to_1 - 1) // 2 + B_to_1_dis
    print(min(tmp_ans, ans))

Measured memory_bytes: 9072
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int main() {
  int x;
  cin>>x;
  if(x<600) cout<<8<<endl;
  else if(x<800) cout<<7<<endl;
  else if(x<1000) cout<<6<<endl;
  else if(x<1200) cout<<5<<endl;
  else if(x<1400) cout<<4<<endl;
  else if(x<1600) cout<<3<<endl;
  else if(x<1800) cout<<2<<endl;
  else if(x<2000) cout<<1<<endl;
  return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define N 100001
#define LOG_MAX 30
int n,q;
vector<int> g[N];
int root;
int par[N][LOG_MAX];
int depth[N];

void dfs(int x,int d){
  depth[x]=d;
  //cout<<x<<endl;
  for(int i=0;i<g[x].size();i++){
    par[g[x][i]][0]=x;
    dfs(g[x][i],d+1);
  }
}

int KthAns(int u,int k){
  for(int i=0;i<LOG_MAX;i++){
    if(u==-1)return -1;
    if(k>>i&1)u=par[u][i];
  }
  return u;
}

void build(){
  dfs(root,0);
  par[root][0]=-1;
  for(int i=1;i<LOG_MAX;i++)
    for(int j=0;j<n;j++){
      if(par[j][i-1]==-1)par[j][i]=-1;
      else par[j][i]=par[par[j][i-1]][i-1];
    }
}

int lca(int u,int v){
  //cout<<u<<" "<<v<<endl;
  if(depth[u]>depth[v])swap(u,v);
  v=KthAns(v,depth[v]-depth[u]);
  if(u==v)return u;
  for(int i=LOG_MAX-1;i>=0;i--){
    int up=par[u][i];
    int vp=par[v][i];
    //cout<<u<<" "<<v<<endl;
    if(up==vp)continue;
    u=up,v=vp;
  }
  return par[u][0];
}

int main(){
  root=0;
  cin>>n;
  for(int i=0;i<n;i++){
    int k,c;
    cin>>k;
    for(int j=0;j<k;j++){
      cin>>c;
      g[i].push_back(c);
    }
  }
  build();
  cin>>q;
  for(int i=0;i<q;i++){
    int u,v;
    cin>>u>>v;
    cout<<lca(u,v)<<endl;
  }
  return 0;
}



Measured memory_bytes: 25336
void main(){
	int a, b, c, d;
	scanf("%d %d %d %d", &a, &b, &c, &d);
	writeln(max(a*b, c*d));
}
     
import std.stdio, std.conv, std.algorithm, std.numeric, std.string, std.math, std.range;
const long mod = 10^^9+7;      
// 1要素のみの入力
T inelm(T= int)(){
	return to!(T)( readln().chomp() );
}
     
// 1行に同一型の複数入力
T[] inln(T = int)(){
	T[] ln;
	foreach(string elm; readln().chomp().split())ln ~= elm.to!T();
	return ln;
}


Measured memory_bytes: 2476
import java.util.Scanner;

public class Main {

	public static final MyScanner in = new MyScanner();

	public static void main(String[] args) {

		int K = in.nextInt();
		int N = in.nextInt();
		int[] A = new int[N];
		for(int i=0;i<N;i++)
			A[i] = in.nextInt();

		int from = A[N-1];
		int to = K + A[0];
		int maxLen= to - from;
		
		to = A[0];
		for(int i=1;i<N;i++) {
			from = to;
			to = A[i];
			int len = to - from;
			if(maxLen < len) maxLen = len;
		}

		System.out.println(K - maxLen);

	}


	public static class MyScanner {
		Scanner sc = new Scanner(System.in);
		String next() { return sc.next();}
		int nextInt() { return Integer.valueOf(sc.next());}
		long nextLong() { return Long.valueOf(sc.next()); }
	}
}

Measured memory_bytes: 63444
#include<iostream>
#include<string>
#include<cstdio>
#include <cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
 
void No(){
	cout<<"No"<<endl;
	exit(0);
}

ll g(ll x) {
    if(x % 4 == 3) {
        return 0;
    } else if(x % 4 == 1) {
        return 1LL;
    } else if(x % 4 == 2) {
        return x ^ 1LL;
    } else {
        return x;
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    ll A, B; cin >> A >> B;
    ll ans = g((A - 1 >= 0 ? A - 1 : 0)) ^ g(B);
    cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;

namespace Atcoder.Abc
{
    //https://atcoder.jp/contests/abc176/tasks/abc176_b
    public class Abc176_B
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            string s = Console.ReadLine();

            var loop = s.Length - 1;
            var sum = 0;

            for (int i = 0; i <= loop; i++)
            {
                sum += int.Parse(s.Substring(i, 1));
            }

            WriteLine(sum % 9 == 0 ? "Yes" : "No");

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 21784
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
//#define rep2(i, n) for(ll i = 1; i <= ll(n); i++)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); i++)
#define rep2(i, k, n) for(ll i = k; i <= ll(n); i++)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 2e5;
const char newl = '\n';

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

  ll n, a, b, c, d;
  string s;
  cin >> n >> a >> b >> c >> d >> s;
  a--; b--; c--; d--;
  
  rep2(i, a, max(c,d)-1) if(s.substr(i, 2) == "##") {cout << "No" << newl; return 0;}
  if(c>d) {
    bool t=0;
    rep2(i, b-1, d-1) if(s.substr(i, 3) == "...") t=1;
    if(!t) {cout << "No" << newl; return 0;}
  }
  
  cout << "Yes" << newl;
  return 0;
}

Measured memory_bytes: 3768
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

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

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

	ll n;cin >> n;
	ll sum = 0;
	map<ll, ll> mp;
	REP(i, n){
		ll a;cin >> a;mp[a]++;
		sum += a;
	}

	ll q;cin >> q;
	REP(i, q){
		ll a, b;cin >> a >> b;
		sum -= mp[a] * a;
		sum += mp[a] * b;
		mp[b] += mp[a];
		mp[a] = 0;
		cout << sum << endl;
	}

	return 0;
}


Measured memory_bytes: 9516
from collections import deque

S = [input()]
d = deque(S)
#print(d)
Q = int(input())

pos = 0

for q in range(Q):
  myinput = list(input().split())
  #print(myinput)
  if len(myinput) == 1:
      pos += 1
  else:
      if myinput[1] == '1':
          if pos% 2 == 0:
               d.appendleft(myinput[2])   
          elif pos%2 !=0:
              #逆方向、先頭
              d.append(myinput[2])   
      elif myinput[1] == '2':
          if pos% 2 == 0:
              #正方向、末尾
              d.append(myinput[2])   
          elif pos%2 !=0:
              #逆方向、末尾
              d.appendleft(myinput[2])   

if pos%2 == 0:                 
    print(''.join(d))
else:
    print((''.join(d))[::-1])

Measured memory_bytes: 7028
#include<iostream>

using namespace std;

int main() {
	int n,a;
	int b[82];
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			a=i*j;
			b[a]=1;
		}
	}
	cin >> n;

	if(b[n]==1) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
	
}	

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

const int MAX_N=21,MAX_M=31;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M,sx,sy,tx,ty;
    vector<int> x(MAX_N),y(MAX_N),l(MAX_M),ok(MAX_M);
    vector<char> d(MAX_M);
    while(cin >> N,N){
        for (int i=0;i<N;++i) cin >> x[i] >> y[i],ok[i]=0;
        cin >> M;
        sx=10,sy=10;
        for (int i=0;i<M;++i){
            cin >> d[i] >> l[i];
            if (d[i]=='N') tx=sx,ty=sy+l[i];
            if (d[i]=='E') tx=sx+l[i],ty=sy;
            if (d[i]=='S') tx=sx,ty=sy-l[i];
            if (d[i]=='W') tx=sx-l[i],ty=sy;
            pair<int,int> p=minmax(sx,tx),q=minmax(sy,ty);
            for (int i=0;i<N;++i){
                if (p.first<=x[i]&&x[i]<=p.second&&q.first<=y[i]&&y[i]<=q.second){
                    ok[i]=1;
                }
            }
            sx=tx,sy=ty;
        }
        int f=1;
        for (int i=0;i<N;++i) if (!ok[i]) f=0;
        if (f) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}


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

long long jio(long long x,long long y){
  for(int i=0;i<y;i++){
    x*=2;
  }
  return x;
}

long long max(long long a,long long b,long long c,long long k){
  long long su=a+b+c;
  if(a>b){
    if(c>a){
      su-=c-jio(c,k);
    }else{
      su+=jio(a,k)-a;
    }
  }else{
    if(c>b){
      su-=c-jio(c,k);
    }else{
      su+=jio(b,k)-b;
    }
  }
  return su;
}

int main(){
  long long a,b,c,k;
  std::cin >> a >> b >> c >> k;
  std::cout << max(a,b,c,k) << std::endl;
}
    


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

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

    int n,k;

    
    while(cin >> n >> k){
        if(!n && !k) break;

        int card[n];
        rep(i,n) cin >> card[i];

        sort( card, card + n );

        int ans = 0;
        map<int,int> memo;
        do{
            int temp = 0;
            rep(i,k){
                temp *= 10;
                if(card[i]>9) temp *= 10;
                temp += card[i];
            }
            if(memo[temp] == 0) ans++;
            memo[temp] = 1;
        }while(next_permutation( card, card + n ));

        cout << ans << endl;
    }

    return 0;
}


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

int main(void)
{
	long int n,q,a,b,c,num[100001] = {0},i,j,k,sum=0;
	scanf("%ld",&n);
	for(i=0;i<n;i++){
		scanf("%ld",&a);
		sum += a;
		num[a]++;
	}
	scanf("%ld",&q);
	for(i=0;i<q;i++){
		scanf("%ld %ld",&b,&c);
		sum += num[b] * (c-b);
		num[c] += num[b];
		num[b] = 0;
		printf("%ld\n",sum);
	}
	
	return 0;
}

Measured memory_bytes: 2492
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n; cin >> n;
  vector<int> dp(3, 0);
  for(int i = 0; i < n; i++){
    vector<int> a(3), ndp;
    ndp = dp;
    for(int j = 0; j < 3; j++) cin >> a[j];
    for(int j = 0; j < 3; j++) {
      for(int k = 0; k < 3; k++) {
        if(k != j){
          ndp[j] = max(ndp[j], dp[k] + a[j]);
        }
      }
    }
    dp = ndp;
  }
  cout << max(dp[0], max(dp[1], dp[2])) << endl;
  return 0;
}


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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second

template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}
void debug(istringstream&){}
template <char sep=',', class Head, class... Tail>
void debug(istringstream& iss, Head&& head, Tail&&... tail)
{
  string name;
  getline(iss, name, ',');
  cerr << sep << name << "=" << head;
  debug(iss, forward<Tail>(tail)...);
}
#define DEBUG(...) \
  do{ \
    istringstream ss(#__VA_ARGS__); \
    debug<' '>(ss, __VA_ARGS__); \
    cerr<<endl; \
  }while(0)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  int N;
  cin >> N;

  LL crt[3] = {0}, nxt[3] = {0};
  REP(i,N){
    REP(k,3) nxt[3] = 0;
    VL xs(3);
    cin >> xs;

    REP(j,3) REP(k,3) if(j != k) maxi(nxt[k], crt[j] + xs[k]);
    swap(crt, nxt);
  }

  cout << *max_element(ALL(crt)) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef long double ld;

//repetition
#define REP(i,n)  for(ll i=0;i<n;i++)

unsigned GetDigit(unsigned num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}
 
unsigned binarySearch(ll target, ll max, ll min) {
  while((max - min) > 1) {
      if((max + min)/2 > target) {
        max = (max + min)/2;
        min = min;
      } else {
        max = max;
        min = (max + min)/2;
      }
    }
}


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

  if (a > 0) { 
    if ( a <= k) {
      k = k - a;
      a = 0;
    } else {
      a = a - k;
      k = 0;
    }
  }
  if (b > 0) {
    if (b <= k) b = 0;
    else b = b - k;
  } 
  
  cout << a << " " << b;
}

Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
 
using namespace std;
 
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
 
const int INF=1<<29;
const double EPS=1e-9;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

std::vector<vector<int> > G;
std::vector<int> flag;
std::vector<int> in;
std::vector<int> out;
int N;
int dfs(int u, int count) {
	if (flag[u] == 1) return -1;
	flag[u] = 1;
	
	in[u] = count;
	for (int i = 0; i < N; ++i) {
		if (flag[i] == 0 && G[u][i] == 1) {
			count = dfs(i, count + 1);
		}
	}
	out[u] = count + 1;
	return count + 1;
}

int main(int argc, char const *argv[]) {
	
	cin >> N;

	for (int i = 0; i < N; ++i) {
		G.push_back(vector<int>());
		flag.push_back(0);
		in.push_back(0);
		out.push_back(0);
		for (int j = 0; j < N; ++j) {
			G[i].push_back(0);
		}
	}

	for (int i = 0; i < N; ++i) {
		int u, k;
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; ++j) {
			int v;
			cin >> v;
			v--;
			G[u][v] = 1;
		}
	}

	int count = 1;
	for(int i = 0; i < N; i++) {
		int r = dfs(i, count);
		if (r != -1) {
			count = r + 1;
		}
	}

	for (int i = 0; i < N; ++i) {
		cout << i + 1 << " " << in[i] << " " << out[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <vector>
#include <cassert>

int const nmax = 200000;
int const sigma = 50;
int v[5 + nmax], temp[5 + nmax];

void process(int n) {
  for(int i = 0;i <= n; i++)
    temp[i] = 0;
  for(int i = 1;i <= n; i++) {
    temp[std::max(1, i - v[i])]++;
    temp[std::min(n + 1, i + v[i] + 1)]--;
  }
  for(int i = 1;i <= n; i++)
    temp[i] += temp[i - 1];
  for(int i = 1;i <= n; i++)
    v[i] = temp[i];
}

int main() {

  int n, k;
  std::cin >> n >> k;
  for(int i = 1;i <= n; i++) 
    std::cin >> v[i];
  for(int i = 1;i <= std::min(sigma, k); i++)
    process(n);
  for(int i = 1;i <= n; i++)
    std::cout << v[i] << " ";
}


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


ll N, A, B;

void Main() {
  cin >> N >> A >> B;

  if ((B - A) % 2 == 0) {
    cout << (B - A) / 2 << endl;
  } else {
    if (N - A > B - 1) {
      cout << A - 1 + 1 + (B - A - 1) / 2 << endl;
    } else {
      cout << N - B + 1 + (B - A - 1) / 2 << endl;
    }
  }
}

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


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

using namespace std;
vector<long long> factors;
#define ll long long


#define pii pair<int,int>
#define pll pair<ll,ll>
#define _ <<'\n'
#define __ << ' '
#define all(x) (x).begin(), (x).end()
#define gcd __gcd
int IT_MAX = 1 << 17;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
#define szz(x) (int)(x).size()
#define IOS ios_base::sync_with_stdio(false); cout.tie(0);cin.tie(0);
#define flush fflush(stdout)

template<typename T>
int BS(vector<T> &mas, T val)
{
	int l, r;
	l = 0;
	r = mas.size() - 1;
	while (r - l > 1)
	{
		int mid = l + (r - l) / 2;
		if (mas[mid] < val)
		{
			l = mid;
		} else
			r = mid;
	}
	if (mas[r] == val)
		return r;
	if (mas[l] == val)
		return l;
	return -1;
}

template<typename T>
int UBS(vector<T> &mas, T val)
{
	int l, r;
	l = 0;
	r = mas.size() - 1;
	while (r - l > 1)
	{
		int mid = l + (r - l) / 2;
		if (mas[mid] < val)
		{
			l = mid;
		} else
			r = mid;
	}

	if (mas[l] >= val)
		return l;
	if (mas[r] >= val)
		return r;
	return -1;
}

ll mod(ll a, ll m)
{ return (a + (abs(a) / m) * m + m) % m; }


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

	int n;
	cin >> n;

	vector<ll> a(n);
	ll sum = 0;
	for(int i = 0;i < n; ++i){
		cin >> a[i];
		sum += a[i];
	}
	sort(all(a));
	if(a[a.size() - 1]* 2 < sum){
		cout << "Yes\n";
	} else
		cout << "No";


	return 0;
}

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

int main(){
	long N,t,f;
  int count = 0,sw = 0;
  string first;
  deque<char> s;
  deque<char> q;
  char  c1,c2;
  cin >> first >> N;
  for(int i = 0;i < first.size();i++){
    c1 = first[i];
    s.push_back(c1);
  }
  

  for(int i = 0;i < N;i++){
    cin >> t;
  if(t == 1){
    sw += 1;
  }else{
    cin >> f >> c1;
    if(sw % 2 == 0){
    if(f == 1){
      s.push_front(c1);
    }else{
      s.push_back(c1);
    }
    }else{
          if(f == 1){
      s.push_back(c1);
    }else{
      s.push_front(c1);
    }
    }
  }

  }
  while(!s.empty()){
    if(sw % 2 == 0){
    cout << s.front();
    s.pop_front();
    }else{
          cout << s.back();
    s.pop_back();
    }
  }
  cout << endl;
return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<string.h>
#include<limits.h>

#define n_max 200000


long merge(int A[],int left,int mid,int right);
long mergeSort(int A[],int left,int right);
int main(void){
	int n,i;
	int a[n_max];
	int ans;
	long cnt;
	
	scanf("%d", &n);
	for(i = 0;i<n;i++){
		scanf("%d", &a[i]);
	}
	
	cnt = mergeSort(a, 0, n);
	printf("%ld\n", cnt);
	return 0;
	
}


long merge(int A[],int left,int mid,int right){
  	int n1 = mid - left;
  	int n2 = right - mid;
	int R[n1+1], L[n2+1];
	int i, j, k;
	long cnt=0;
  //L[0...n1], R[0...n2] を生成
	for (i = 0;i <n1;i++){
		L[i] = A[left + i];
	}
	for (i = 0;i <n2;i++){
		R[i] = A[mid + i];
	}
 	L[n1] = INT_MAX;
  	R[n2] = INT_MAX;
	i = 0;
	j = 0;
	for (k = left ;k<right;k++){
		if( L[i] <= R[j]){
	      A[k] = L[i];
	      i = i + 1;
		  
		}
		else {
	      A[k] = R[j];
	      j = j + 1;
			cnt +=n1 - i ;
		}
	}
	return cnt;
}
long mergeSort(int A[],int left,int right){
	long cnt1 = 0, cnt2 = 0, cnt3 = 0;
	if( left+1 < right){
    int mid = (left + right)/2;
    cnt1 = mergeSort(A, left, mid);
    cnt2 = mergeSort(A, mid, right);
    cnt3 = merge(A, left, mid, right);
	}
	return cnt1+cnt2+cnt3;
}


Measured memory_bytes: 3296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b:i--)
//Binary_Indexed_Tree (Range_Sum_Query)
//(1-indexed)
const long long max_n = 1 << 20;
long long n;
long long bit[30][max_n+1];
//i番目(1-indexed)までの和
long long sum(long long aa, long long i){
    long long s = 0;
    while(i > 0){
        s += bit[aa][i];
        i -= i & -i;
    }
    return s;
}
//i番目(1-indexed)にxを加える
void add(long long aa, long long i,long long x){
    while(i <= n){
        bit[aa][i] += x;
        i += i & -i;
    }
}

int main() {
    // your code goes here
    ll mi;
    char s[500005];
    cin >> n >> s;
    rep(i,1,n){
        rep(j,0,25) bit[j][i]=0;
    }
    rep(ii,0,n-1){
        mi=s[ii]-'a';
        add(mi,ii+1,1);
    }
    ll qr;
    cin >> qr;
    rep(q,1,qr){
        ll type;
        cin >> type;
        if(type==1){
            ll iq;
            char cq[5];
            cin >> iq >> cq;
            iq--;
            mi=s[iq]-'a';
            add(mi,iq+1,-1);
            mi=cq[0]-'a';
            add(mi,iq+1,1);
            s[iq]=cq[0];
        } else {
            ll lq,rq,memo=0;
            cin >> lq >> rq;
            rep(ii,0,25){
                if(sum(ii,rq)-sum(ii,lq-1)>0) memo++;
            }
            cout << memo << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 107264
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner inp = new Scanner(System.in);
        int total = inp.nextInt();

        int[] b = new int[total];

        for (int k = 0; k < total; k++) {
            int a = inp.nextInt();

            b[k] = a;
        }

        shellSort(b, total);
    }

    public static int insertionSort(int[] b, int n, int g) {
        int counter = 0;
        for (int i = g; i < n; i++) {
            int v = b[i];
            int j = i - g;
            while (j >= 0 && b[j] > v) {
                b[j + g] = b[j];
                j = j - g;
                counter++;
            }

            b[j + g] = v;
        }

        return counter;
    }

    public static void shellSort(int[] b, int n) {
        int counter = 0;
        int m = 0;
        int g[] = new int[100];

        for (int i = 1; i <= n; i=i*3+1) {
            g[m] = i;
            m++;
        }

        System.out.println(m);

        m--;

        for (int i = m; i >= 0; i--) {
            counter += insertionSort(b, n, g[i]);

            if (i == 0) {
                System.out.printf(" %d", g[i]);
            } else {
                System.out.printf(" %d", g[i]);
            }
        }

        System.out.println("\n" + counter);

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



Measured memory_bytes: 299508
n = int(input())
l = sorted(list(map(int,input().split())))
if n%2 == 1:
  testl = sorted([2*i for i in range(len(l)//2+1)]*2)[1:]
else:
  testl = sorted([2*i+1 for i in range(len(l)//2)]*2)
if l == testl:
  print((2**(len(l)//2))%(10**9+7))
else:
  print(0)

Measured memory_bytes: 14008
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#include <iostream>

using namespace std;

#define MAX_N 1000000

int N;
int inf = 1000000000;

int d[MAX_N+1], d2[MAX_N+1]; // ?????????j??¨?????????????????????????°??????°

int calc_sn(int n){
	return n*(n+1)*(n+2)/6;
}

int main() {
	d[0] = 0;
    for(int i = 1; i <= MAX_N; i++){
    	d[i] = inf;
       	for (int j = 1; ; j++)
        {
        	if(i < calc_sn(j)) break;
            d[i] = min(d[i], d[i-calc_sn(j)]+1);
        }
    }
    d2[0] = 0;
    for(int i = 1; i <= MAX_N; i++){
    	d2[i] = inf;
       	for (int j = 1; ; j++)
        {
        	if(i < calc_sn(j)) break;
        	if(calc_sn(j) % 2 == 0) continue;
            d2[i] = min(d2[i], d2[i-calc_sn(j)]+1);
        }
    }
    while(1){
    	cin >> N;
    	if(N == 0) break;
    	cout << d[N] << " " << d2[N] << endl;
    }
    return 0;
}

Measured memory_bytes: 8972
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int inf=-1e9;
bool cmp(pair<int,int>a,pair<int,int>b) {
    return a.second<b.second;
}
int main(int argc, char const *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    int n;
    cin>>n;
    vector<pair<int,int>>v;
    for(int i=0;i<n;i++) {
        int x,l;
        cin>>x>>l;
        v.push_back({x-l,x+l});
    }
    sort(v.begin(),v.end(),cmp);
    // for(auto x:v) cout<<x.first<<" "<<x.second<<endl;
    int ans=0;
    int last=inf;
    for(auto x:v) {
        if(x.first>=last) {
            ans++;
            last=x.second;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1400
/*  -*- coding: utf-8 -*-
 *
 * 1379.cc: Parallel Lines
 */

#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>
 
using namespace std;

/* constant */

const int MAX_M = 16;
const int MAX_N = MAX_M * (MAX_M - 1) / 2;

/* typedef */

template <typename T>
struct Pt {
  T x, y;

  Pt() {}
  Pt(T _x, T _y) : x(_x), y(_y) {}
  Pt(const Pt<T> &pt) : x(pt.x), y(pt.y) {}

  Pt<T> operator+(const Pt<T> pt) const { return Pt<T>(x + pt.x, y + pt.y); }
  Pt<T> operator-() const { return Pt<T>(-x, -y); }
  Pt<T> operator-(const Pt<T> pt) const { return Pt<T>(x - pt.x, y - pt.y); }
  Pt<T> operator*(T t) const { return Pt<T>(x * t, y * t); }
  Pt<T> operator/(T t) const { return Pt<T>(x / t, y / t); }
  T dot(Pt<T> v) const { return x * v.x + y * v.y; }
  T cross(Pt<T> v) const { return x * v.y - y * v.x; }

  bool operator==(const Pt<T> pt) const { return x == pt.x && y == pt.y; }
  bool operator<(const Pt<T> &pt) const {
    return x < pt.x || (x == pt.x && y < pt.y);
  }
  void print() { printf("(%d,%d)", x, y); }
};

typedef Pt<int> pt;

/* global variables */

pt ps[MAX_M], vs[MAX_M][MAX_M], v[MAX_M], w[MAX_M];
bool used[MAX_M];
int maxpn = 0;

/* subroutines */

template <typename T>
T gcd(T m, T n) {  // m > 0, n > 0
  if (m < n) swap(m, n);
  while (n > 0) {
    T r = m % n;
    m = n;
    n = r;
  }
  return m;
}

void normalize(pt &p) {
  if (p.x != 0 || p.y != 0) {
    if (p.x == 0) p.y = 1;
    else if (p.y == 0) p.x = 1;
    else {
      if (p.x < 0) p.x = -p.x, p.y = -p.y;
      int g = gcd(abs(p.x), abs(p.y));
      if (g > 1) p.x /= g, p.y /= g;
    }
  }
}

void rec(int u, int m, int k) {
  if (k >= m / 2) {
    memcpy(w, v, sizeof(w));
    sort(w, w + k);
    int pn = 0;
    for (int i = 0; i < k;) {
      int j = i + 1;
      while (j < k && w[i] == w[j]) j++;
      int a = j - i;
      pn += a * (a - 1) / 2;
      i = j;
    }
    if (maxpn < pn) maxpn = pn;
    return;
  }

  while (u < m && used[u]) u++;
  used[u] = true;
  for (int j = u + 1; j < m; j++)
    if (! used[j]) {
      used[j] = true;
      v[k] = vs[u][j];
      rec(u + 1, m, k + 1);
      used[j] = false;
    }
  used[u] = false;
}

/* main */

int main() {
  int m;
  scanf("%d", &m);

  for (int i = 0; i < m; i++) scanf("%d%d", &ps[i].x, &ps[i].y);

  for (int i = 0; i < m; i++)
    for (int j = i + 1; j < m; j++) {
      vs[i][j] = ps[j] - ps[i];
      normalize(vs[i][j]);
    }

  rec(0, m, 0);

  printf("%d\n", maxpn);
  return 0;
}



Measured memory_bytes: 3236
mod=10**6+3

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

data=[1]
for i in range(1,mod):
    data.append(data[-1]*i%mod)

Q=int(input())
xdn=[list(map(int,input().split())) for i in range(Q)]

for x,d,n in xdn:
    if d==0:
        print(pow(x,n,mod))
        continue
    if x==0:
        print(0)
        continue
    k=x*inv[d]%mod
    if k+n-1>=mod:
        print(0)
    else:
        print(pow(d,k+n-1,mod)*data[k+n-1]*inv[pow(d,k-1,mod)*data[k-1]%mod]%mod)
    

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

const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};

int ans,h,w,c;
int tmp;
int flag[8][8];

void print(int panel[8][8]){

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){

      if(j) cout<<" ";
      cout<<panel[i][j];

    }

    cout<<endl;

  }

}

void dfs2(int y,int x,int color,int next[8][8]){

  flag[y][x]=1;

  for(int i=0;i<4;i++){

    int y1=y+dy[i];
    int x1=x+dx[i];

    if(y1<0 || y1>=h) continue;
    if(x1<0 || x1>=w) continue;

    if(next[y][x]==next[y1][x1])
      if(!flag[y1][x1])
	dfs2(y1,x1,color,next);

  }

  next[y][x]=color;

}

void dfs3(int y,int x,int panel[8][8]){

  flag[y][x]=1;

  if(panel[y][x]!=c) return;

  tmp++;

  for(int i=0;i<4;i++){

    int y1=y+dy[i];
    int x1=x+dx[i];

    if(y1<0 || y1>=h) continue;
    if(x1<0 || x1>=w) continue;

    if(!flag[y1][x1])
      dfs3(y1,x1,panel);

  }

}


void dfs1(int y,int x,int (&panel)[8][8],int how){

  if(how==5){

    tmp=0;
    for(int j=0;j<h;j++) for(int k=0;k<w;k++) flag[j][k]=0;

    dfs3(y,x,panel);
    ans=max(ans,tmp);

    return;

  }

  for(int i=1;i<=6;i++){

    int next[8][8];
    for(int j=0;j<h;j++) for(int k=0;k<w;k++) next[j][k]=panel[j][k],flag[j][k]=0;

    dfs2(y,x,i,next);
    dfs1(y,x,next,how+1);

  }

}

signed main(){

  for(;;){

  cin>>h>>w>>c;

  if(!h) break;

  int panel[8][8];

  for(int i=0;i<h;i++) for(int j=0;j<w;j++) cin>>panel[i][j];

  ans=0;

  dfs1(0,0,panel,0);

  cout<<ans<<endl;

  }

  return 0;

}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
// define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define rollcall cout << "I'm Sucu." << endl;
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// debug
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
  os << "(" << p.first << "," << p.second << ")";return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  for (auto it = v.begin();it != v.end();++it){
    if(it != v.begin())os << " ";os << *it;
      }return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp){
  for(auto x: mp)os << "(" << x.first << "," << x.second << ")" << endl;
  return os;
}
template<typename T, int SIZE>
int array_length(const T (&)[SIZE]){return SIZE;}
template<typename T, int N>
void PRINTF(const T (&a)[N], int s = N, int t = -1, bool f = true){
	if(t == -1){rep(i,s){if(i)cout << " ";cout << a[i];}}
	else repi(i,s,t){if(i!=s)cout << " ";cout << a[i];}
	if(f)cout << "\n";
}
template<typename T, int N1, int N2>
void PRINTF(const T (&a)[N1][N2], int h = N1, int w = N2){
	rep(i,h){rep(j,w){cout << a[i][j] << " \n"[j==w-1];}}
}
// typedef
typedef complex<double> Point;
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;


map<int, int> mp;
const int mod = 1e9+7, MAX = 1e6;
int fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i-1]*i%mod;
        inv[i] = mod-inv[mod%i]*(mod/i)%mod;
        finv[i] = finv[i-1]*inv[i]%mod;
    }
}
// 二項係数計算
int COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}


signed main(){
  int n, m;
  COMinit();
  scanf("%lld%lld", &n, &m);
  int tmp = m;
  for(int i = 2;(i-1)*(i-1) <= m;i++){
    // printf("%lld %lld\n", i, tmp);
    while(tmp%i == 0){mp[i]++;tmp /= i;}
  }
  if(tmp > 1)mp[tmp]++;
  // if(mp.size() == 0){printf("%lld\n", n);return 0;}
  int ans = 1;
  for(auto it = mp.begin();it != mp.end();++it){
    // printf("%lld %lld\n", it->fi, it->se);
    ans = (ans*COM(n+it->se-1, n-1))%mod;
  }
  printf("%lld\n", ans);
	return 0;
}








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

int main() {
	int n,a,b,ta=0,tb;cin>>n;
  	for(int i=0;i<n;i++){
    	cin>>a>>b;
      	if(ta<a){
        	ta=a;tb=b;
        }
    }
  	cout<<ta+tb<<endl;
 }

Measured memory_bytes: 256
n=int(input())
a=n//15
b=n%15
B=[0,1,2,0,4,0,0,7,8,0,0,11,0,13,14]
C=[0,1,2,2,3,3,3,4,5,5,5,6,6,7,8]
c=0
for i in range(b+1):
  c=c+B[i]
print(60*a+120*a*(a-1)//2+c+C[b]*15*a)

Measured memory_bytes: 9200
#include <stdio.h>
#include <string.h>
#define SIZE 1000

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

int main(){
  int n,i,j,cnt=0;
  char x[SIZE],y[SIZE];
  scanf("%d",&n);
  
  while(cnt != n){
    char tmp1[SIZE],tmp2[SIZE];
    scanf("%s %s",tmp1,tmp2);
    x[0]=y[0]=' ';
    strcpy(x+1,tmp1);
    strcpy(y+1,tmp2);
    int dp[SIZE+100][SIZE+100];
    int xlen = strlen(x);
    int ylen = strlen(y);
    int ans = 0;

    for(i=0; i<=xlen; i++) dp[i][0] = 0;
    for(i=0; i<=ylen; i++) dp[0][i] = 0;
    
    for(i=1; i<=xlen; i++){
      for(j=1; j<=ylen; j++){
        if(x[i] == y[j]){
          dp[i][j] = dp[i-1][j-1]+1;
                }
        else{
          dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
        ans = max(ans,dp[i][j]);
      }
    }
    
    ans--;
        
    printf("%d\n",ans);
    
    cnt++;
  }
  
  return 0;
}



Measured memory_bytes: 6120
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n = readInt()
t = readInts()
x = []
for i in range(n):
	x.append([i,t[i]])
x = sorted(x, key=lambda x: x[1])
ans = [-1]*n
for i in range(len(x)):
	if i<n//2:
		ans[x[i][0]]=x[n//2][1]
	else:
		ans[x[i][0]]=x[n//2-1][1]

for i in ans:
	print(i,end=" ")

Measured memory_bytes: 46884
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <map>
using namespace std;

int N, A, B;
string S;
string s;
int current;
int gakusei;

int main()
{
	cin >> N >> A >> B;
	cin >> S;
	current = 0;
	gakusei = 0;
	for (int i=0; i<S.size(); i++){
		s = S[i];
		if (s=="a"){
			if (current<A+B) {
				puts("Yes");
				current++;
			}
			else puts("No");
		}
		else if (s=="b"){
			gakusei++;
			if (current<A+B && gakusei<=B){
				puts("Yes");
				current++;
			}
			else puts("No");
		}
		else{
			puts("No");
		}
	}
	return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
#define BIT(n) (1LL << (n))
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPB(i, n) for (int i = 0; i < BIT(n); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORA(i, n) for (auto &&i : n)
#define FORS(i, m, n) for (int i = m; i <= n; i++)
#define DEBUG(x) cerr << #x << ": " << x << "\n"
#define PRINTALL(V)                                                            \
  for (auto v : (V)) {                                                         \
    cerr << v << " ";                                                          \
  }                                                                            \
  cerr << "\n";
#define ALL(v) v.begin(), v.end()
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define epb emplace_back
#define int long long
using namespace std;
template < class T > bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template < class T > bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template < class T > using vec = std::vector< T >;
template < class T > void print(const T &x) { cout << x << "\n"; }
const int MOD = 1000000007, INF = 1061109567, INF2 = INF * INF;
const double EPS = 1e-10, PI = acos(-1.0);
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
  cin.tie(0), ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int N, A, B;
  cin >> N >> A >> B;
  vec< int > x(N);
  REP(i, N) { cin >> x[i]; }
  sort(ALL(x));
  int ans = 0;
  REP(i, N - 1) {
    ans += min(B, A * (x[i + 1] - x[i]));
 //   DEBUG(ans);
  }
  print(ans);
}

Measured memory_bytes: 1024
N = int(input())
A = [int(x) for x in input().split()]
mean_a = sum(A)/N
ans = 0
ans_dist = float('inf')
for ind,a in enumerate(A):
    if(abs(mean_a-a)<ans_dist):
        ans_dist = abs(mean_a-a)
        ans = ind
print(ans)


Measured memory_bytes: 3060
#include "bits/stdc++.h"

// Begin Header {{{
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

#define all(x) x.begin(), x.end()
#define rep(i, n) for (intmax_t i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)

constexpr size_t    operator""_zu(unsigned long long value) { return value; };
constexpr intmax_t  operator""_jd(unsigned long long value) { return value; };
constexpr uintmax_t operator""_ju(unsigned long long value) { return value; };

constexpr int INF = 0x3f3f3f3f;
constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd;

template <class T, class Compare = less<>>
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template <class T, class Compare = greater<>>
using MinHeap = priority_queue<T, vector<T>, Compare>;

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
    cin >> head;
    input(forward<Tail>(tail)...);
}

template <class T>
inline istream& operator>>(istream &is, vector<T> &vec) {
    for (auto &e: vec) {
        is >> e;
    }
    return is;
}

inline void output() { cout << "\n"; }
template <class Head, class... Tail>
inline void output(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) {
        cout << " ";
    }
    output(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e: vec) {
        os << e << delim[&e == &vec.back()];
    }
    return os;
}

template <class T>
inline vector<T> makeVector(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeVector(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeVector<T>(initValue, args...))>(sz, makeVector<T>(initValue, args...));
}

template <class Func>
class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}

    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func>{forward<Func>(f)};
}

template <class T>
inline bool chmax(T &a, const T &b) noexcept {
    return b > a && (a = b, true);
}

template <class T>
inline bool chmin(T &a, const T &b) noexcept {
    return b < a && (a = b, true);
}

template <class T>
inline T diff(const T &a, const T &b) noexcept {
    return a < b ? b - a : a - b;
}
// End Header }}}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    var(intmax_t, a, b, c);

    cout << ((b - a == c - b) ? "YES" : "NO") << "\n";

    return 0;
}


Measured memory_bytes: 896
r1,c1,r2,c2=map(int, input().split())
MOD=10**9+7

M=2*(10**6+1)
fac=[0]*(M+1)
ifac=[0]*(M+1)
fac[0]=1
for i in range(1,M+1):
    fac[i]=fac[i-1]*i%MOD
ifac[M]=pow(fac[M],MOD-2,MOD)
for i in range(M-1,0,-1):
    ifac[i]=ifac[i+1]*(i+1)%MOD

def comb(a,b): return fac[a]*ifac[a-b]*ifac[b]%MOD

def g(r,c): return comb(r+c+2,r+1)-1

ans=g(r2,c2)-g(r1-1,c2)-g(r2,c1-1)+g(r1-1,c1-1)
print(ans%MOD)

Measured memory_bytes: 72684
W,H,N = map(int,input().split())
act = [[0 for j in range(3)] for i in range(N)]
xl = 0 #左端 
xr = W #右端
yd = 0 #上端
yu = H #下端
for i in range(N):
	act[i] = [int(j) for j in input().split()]
for obj in act:
	if(obj[2]==1):
		xl = max(obj[0],xl)
	elif(obj[2]==2):
		xr = min(obj[0],xr)
	elif(obj[2]==3):
		yd = max(obj[1],yd)
	elif(obj[2]==4):
		yu = min(obj[1],yu)
ans = (xr-xl)*(yu-yd)
# print(xr,xl,yu,yd)
if(xr < xl or yu < yd):
	print(0)
else:
	print(ans)

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

int main(){
  int N,K;
  string S;
  cin>>N>>K>>S;
  for(int i=0;i<N;i++){
    if((i+1)!=K){
      cout<<S.at(i);
    }else{
      switch(S.at(i)){
        case 'A':cout<<'a';break;
        case 'B':cout<<'b';break;
        case 'C':cout<<'c';break;
        case 'D':cout<<'d';break;
        case 'E':cout<<'e';break;
        case 'F':cout<<'f';break;
        case 'G':cout<<'g';break;
        case 'H':cout<<'h';break;
        case 'I':cout<<'i';break;
        case 'J':cout<<'j';break;
        case 'K':cout<<'k';break;
        case 'L':cout<<'l';break;
        case 'M':cout<<'m';break;
        case 'N':cout<<'n';break;
        case 'O':cout<<'o';break;
        case 'P':cout<<'p';break;
        case 'Q':cout<<'q';break;
        case 'R':cout<<'r';break;
        case 'S':cout<<'s';break;
        case 'T':cout<<'t';break;
        case 'U':cout<<'u';break;
        case 'V':cout<<'v';break;
        case 'W':cout<<'w';break;
        case 'X':cout<<'x';break;
        case 'Y':cout<<'y';break;
        case 'Z':cout<<'z';break;
      }
    }
  }
  cout<<endl;
        
    
}

Measured memory_bytes: 256
n = int(input())
pre_list = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
 
#nをn+1個並べたリストを作る
dp = [n]*(n+1)
#0を初期化する
dp[0] = 0
 
 
#dp[i]について一つずつ考える
for i in range(1,n+1):
#dp[i]のそれぞれの場合分けについて考える。場合はpre_listの中身の分だけ回せばいい
	for j in pre_list:
		if i - j >= 0:
			dp[i] = min(dp[i],dp[i-j]+1)
 
print(dp[n])

Measured memory_bytes: 3828