akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = 1 << 28;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    int n, W;
    cin >> n >> W;
    vl w(n), v(n);
    ll totW = 0;
    ll totV = 0;
    vector<deque<ll>> pq(4);
    for (int i = 0; i < n; ++i) {
        cin >> w[i] >> v[i];
        totW += w[i];
        totV += v[i];
        pq[w[i] - w[0]].emplace_back(v[i]);
    }
    for (int i = 0; i < 4; ++i) {
        sort(pq[i].begin(), pq[i].end(), greater<ll>());
    }
    for (int i = 0; i < 4; ++i) {
        pq[i].push_front(0); // centinel
    }
    vvl vv(4);
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < pq[i].size(); ++j) {
            if (j == 0) {
                vv[i].push_back(pq[i][0]);
            } else {
                vv[i].push_back(pq[i][j] + vv[i][j - 1]);
            }
        }
    }
    ll ret = 0;
    for (int i = 0; i < pq[0].size(); ++i) {
        for (int j = 0; j < pq[1].size(); ++j) {
            for (int k = 0; k < pq[2].size(); ++k) {
                for (int l = 0; l < pq[3].size(); ++l) {
                    ll weight =
                        i * w[0] + j * (w[0] + 1) + k * (w[0] + 2) + l * (w[0] + 3);
                    if (weight <= W)
                        chmax(ret, vv[0][i] + vv[1][j] + vv[2][k] + vv[3][l]);
                }
            }
        }
    }
    cout << ret << "\n";
    return 0;
}

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

int main(){
  int D[5],k;
for(int i=0;i<5;++i){
cin >> D[i];
}
cin >> k;
bool dis = true;
for(int i=0;i<5;i++){
for(int t=i;t<5;t++){
if((max(D[i],D[t])-min(D[i],D[t]))> k){
dis = false;
break;
}
}
}
if(dis) cout << "Yay!" << endl;
else cout << ":(" << endl;
}

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

#define int long long

using namespace std;

void print(vector<int> kek) {
    for (int i = 0; i < kek.size(); i++) {
        cout << kek[i] << " ";
    }
    cout << "\n";
}


void print(vector<vector<int>> kek) {
    for (int i = 0; i < kek.size(); i++) {
        print(kek[i]);
        cout << "\n";
    }
}

int getOne(vector<vector<int>> kek) {
    int res = 0;
    for (auto &i : kek) {
        for (int j = 0; j < i.size(); j++) {
            if (i[j] == 1) res++;
        }
    }
    return res;
}

vector<int> generateSubsets(int s, int n) {
    vector<int> subset;
    for (int i = 0; i < n; i++) {
        if ((s & (1 << i))) subset.push_back(i);
    }
    return subset;
}

vector<vector<int>> paintCols(vector<vector<int>> kek,
                              vector<int> cols) {

    for (auto x : cols) {
        for (int j = 0; j < kek.size(); j++) {
            kek[j][x] = 2;
        }
    }

    return kek;
}

vector<vector<int>> paintRows(vector<vector<int>> kek,
                              vector<int> rows) {

    for (auto x : rows) {
        for (int j = 0; j < kek[0].size(); j++) {
            kek[x][j] = 2;
        }
    }

    return kek;
}



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

    int n, w, k;
    char x;
    cin >> n >> w >> k;
    vector<vector<int>> kek;
    for (int i = 0; i < n; i++) {
        vector<int> temp;
        for (int j = 0; j < w; j++) {
            cin >> x;
            if (x == '.') temp.push_back(0);
            else if (x == '#') temp.push_back(1);
        }
        kek.push_back(temp);
    }
    int res = 0;
    if (getOne(kek) == k) res++;



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

        vector<vector<int>> kek2 = paintRows(kek,
                                             generateSubsets(i, n));

        if (getOne(kek2) == k) res++;
    }
    for (int i = 1; i < (1 << w); i++) {

        vector<vector<int>> kek2 = paintCols(kek,
                                             generateSubsets(i, w));

        if (getOne(kek2) == k) res++;
    }

    for (int i = 1; i < (1 << n); i++) {
        for (int j = 1; j < (1 << w); j++) {
            vector<vector<int>> kek2 = paintRows(kek,generateSubsets(i, n));
            kek2 = paintCols(kek2,generateSubsets(j, w));
            if (getOne(kek2) == k) {
                res++;
            }
        }
    }


    cout << res;


    return 0;

}

Measured memory_bytes: 3612
class Stack():
    def __init__(self):
        self.stack = list()

    def _is_empty(self):
        if len(self.stack) == 0:
            return True
        return False

    def push(self, obj):
        self.stack.append(obj)

    def pop(self):
        if self._is_empty():
            print('empty')
            return None
        return self.stack.pop(-1)

    def __len__(self):
        return len(self.stack)


def main():
    sentense = input().split(' ')
    stack = Stack()
    for chr in sentense:
        if chr in ['+', '-', '*']:
            b = stack.pop()
            a = stack.pop()
            if chr == '+':
                stack.push(a+b)
            elif chr == '-':
                stack.push(a-b)
            else:
                stack.push(a*b)
        else:
            stack.push(int(chr))
    print(stack.pop())


if __name__ == "__main__":
    main()



Measured memory_bytes: 5592
N=int(input())
A = []
for _ in range(N):
    A.append(int(input()))
A2=sorted(A,reverse=True)
M=A2[0]
M2=A2[1]
for i in range(N):
  #print(A[i])
  
  if A[i]==M:
    print(M2)
  else:
    print(M)
 
    

Measured memory_bytes: 14112
#include <stdio.h>
#include<ctype.h>
int main(void){
    int i,n,r,k;
    char s;
    int card[4][13]={};
    char suit[5]={"SHCD"};
    scanf("%d",&n);
    for(i=0;i<n*2;i++){
        scanf("%c %d",&s,&r);
        if(s=='S'){
            card[0][r-1]=1;
        }
        if(s=='H'){
            card[1][r-1]=1;
        }
        if(s=='C'){
            card[2][r-1]=1;
        }
        if(s=='D'){
            card[3][r-1]=1;
        }
    }
    
    for(i=0;i<4;i++){
        for(k=0;k<13;k++){
            if(card[i][k]==0){
                printf("%c %d\n",suit[i],k+1);
            }
        }
    }
    return 0;
}


Measured memory_bytes: 1816
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int a[29];
int b[29];
int s[105];
int tanxue[18];
int n;
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf(" %c",&s[i]);
	}
	int t1,t2;
	int maxn=0;
	for(int i=2;i<=n;i++)
	{
		t1=0;	
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		for(int j=1;j<i;j++)
		{
			if(a[s[j]-'a']==0)
			{
				a[s[j]-'a']=1;
			}
		}
		for(int j=i;j<=n;j++)
		{
			if(b[s[j]-'a']==0)
			{
				b[s[j]-'a']=1;
			}
		}
		for(int j=0;j<26;j++)
		{
			if(a[j]==b[j]&&a[j]==1) t1++;
		}
		if(t1>maxn)
		{
			maxn=t1;
		}
	}
	printf("%d",maxn);
}

Measured memory_bytes: 128
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
       	int s=a-b;
        if (s>c) System.out.println(0);
      else System.out.println(c-s);
    }
}

Measured memory_bytes: 23252
#pragma warning(disable:4996)
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
#define FOR(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

TPL<TNM K, TNM V> using umap = unordered_map<K, V>;
TPL<TNM K, TNM V> using uset = unordered_set<K, V>;

TPL <class T = int> inline T IN() { T x; cin >> x; return x; }
TPL<class T> inline void OUT(const T &x) { cout << x << "\n"; }
void YESNO(bool c) { OUT(c ? "YES" : "NO"); };
void YesNo(bool c) { OUT(c ? "Yes" : "No"); };
void bOUT(bool c, string s, string t) { OUT(c ? s : t); }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); /*cout << fixed << setprecision(6);*/ } } pre__;

TPL<TNM V, TNM H> void resize(vector<V>& v, const H h) { v.resize(h); }
TPL<TNM V, TNM H, TNM ... T> void resize(vector<V>& v, const H& h, const T ... t) { v.resize(h); for (auto& _v : v) resize(_v, t ...); }
TPL<TNM V, TNM T> void fill(V& x, const T& val) { x = val; }
TPL<TNM V, TNM T> void fill(vector<V>& vec, const T& val) { for (auto& v : vec) fill(v, val); }
TPL<TNM T> vector<T> make_v(size_t a) { return vector<T>(a); }
TPL<TNM T, TNM... Ts> auto make_v(size_t a, size_t b, Ts... ts) { return vector<decltype(make_v<T>(b, ts...))>(a, make_v<T>(b, ts...)); }

TPL<TNM T> using vec2 = decltype(make_v<T>(0, 0));
TPL<TNM T> using vec3 = decltype(make_v<T>(0, 0, 0));
TPL<TNM T> using vec4 = decltype(make_v<T>(0, 0, 0, 0));
TPL<TNM T> using vec5 = decltype(make_v<T>(0, 0, 0, 0, 0));

int main(void) {
	int N = IN();
	vector<int> A(N);
	REP(i, N)A[i] = IN();
	int n = *max_element(ALL(A));
	int diff = n;
	int r = n;
	REP(i, N) {
		if (abs(A[i] - n / 2) < diff) {
			diff = abs(A[i] - n / 2);
			r = A[i];
		}
	}
	if (n == r)r = 0;
	cout << n << " " << r << endl;
	return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int i = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int i = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define MP make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1 << 30;
const ll LINF = 1LL << 61;
const int MOD = 1e9 + 7;

int main() {
    int K, S;
    cin >> K >> S;
    int res = 0;
    for(int i = 0; i <= K; i++) {
        for(int j = 0; j <= K; j++) {
            if(S - i - j >= 0 && S - i - j <= K)
                res++;
        }
    }
    cout << res << endl;
    return 0;
}

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

typedef long long   ll;
typedef long double ld;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
    cin >> n >> k;
    double p[n];
    for(int i = 0; i < n; i++) {
        cin >> p[i];
    }

    double refps=0;
    for(int i = 0; i < k; i++) {
        refps+=(p[i]+1)/2;
    }

    double ps=refps;
    for(int i = k; i < n; i++) {
        ps=ps+(p[i]+1)/2-(p[i-k]+1)/2;
        refps=max(refps,ps);
    }

    cout << setprecision(10) << refps << "\n";

    return 0;
}

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

int main(){
  int H,W;
  cin >> H >> W;
  while(H!=0 && W!=0){
    for(int i=0;i<W;i++){
      cout << "#";
    }
    cout << endl;
    for(int i=0;i<H-2;i++){
      cout << "#";
      for(int j=0;j<(W-2);j++){
	cout << ".";
      }
      cout << "#" << endl;
    }
    for(int i=0;i<W;i++){
      cout << "#";
    }
    cout << endl << endl;
    cin >> H >> W;
  }
}


Measured memory_bytes: 3112
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 2005
#define _x1 x1
#define _x2 x2
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int n,m;
ll v;
int fa[maxn],id[maxn],x[maxn],y[maxn];
ll w[maxn];
int getfa(int now)
{
	return fa[now]==now ? now : fa[now]=getfa(fa[now]);
}
int cmp(int i,int j)
{
	return w[i]<w[j];
}
ll kruskal(int now)
{
	for(int i=1;i<=n;i++) fa[i]=i;
	ll ans=0;
	if(now)
		fa[x[now]]=y[now],ans+=w[now];
	for(int i=1;i<=m;i++)
	{
		int pos=id[i];
		int x1=getfa(x[pos]),y1=getfa(y[pos]);
		if(x1!=y1)
		{
			ans+=w[pos];
			fa[x1]=y1;
		}
	}
	return ans;
}
ll quickpow(ll p,ll k)
{
	ll ans=1;
	while(k)
	{
		if(k&1)
			ans=(ans*p)%mod;
		p=(p*p)%mod;
		k>>=1;
	}
	return ans;
}
int main()
{
	scanf("%d%d%lld",&n,&m,&v);
	for(int i=1;i<=m;i++)
		scanf("%d%d%lld",&x[i],&y[i],&w[i]),id[i]=i;
	sort(id+1,id+1+m,cmp);
 
	ll temp=kruskal(0);
 
	if(temp>v)
	return printf("0\n"),0;
 
	if(temp==v)
	{
		int cnt1=0,cnt2=0;
		for(int i=1;i<=m;i++)
		{
			if(kruskal(i)==temp)
				cnt1++;
			else
				cnt2++;
		}
		ll res1=(quickpow(2,cnt1)-2+mod)%mod;
		ll res2=quickpow(2,cnt2)%mod;
		return printf("%lld\n",res1*res2%mod),0;
	}
	else
	{
		int cnt1=0,cnt2=0;
		for(int i=1;i<=m;i++)
		{
			ll res1=kruskal(i);
			if(res1==v)
				cnt1++;
			else if(res1>v)
				cnt2++;
		}
		ll res1=2ll*((quickpow(2,cnt1)-1+mod)%mod)%mod;
		ll res2=quickpow(2,cnt2);
		printf("%lld\n",res1*res2%mod);
	}
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(Type, ...)  Type __VA_ARGS__; input(__VA_ARGS__)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
inline i64  sigma(i64 n)            { return (n * (n + 1) >> 1); }
inline i64  updiv(i64 a, i64 b)     { return (a + b - 1) / b; }
inline i64  sqr(i64 n)              { return n * n; }
inline string to_string(char c)     { return string(1, c); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

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

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

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

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

template <typename Func>
struct FixPoint : Func {
    inline constexpr FixPoint(Func &&f) noexcept : Func(forward<Func>(f)) {}

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

template< typename Func >
inline decltype(auto) makeFixPoint(Func &&f) {
    return FixPoint< Func >{forward< Func >(f)};
}
// }}} End Header

signed main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    var(int, N, K);
    var(int, R, S, P);
    var(string, s);

    char KK[128] {};
    KK['r'] = 'p';
    KK['s'] = 'r';
    KK['p'] = 's';

    int score[128] {};
    score['r'] = R;
    score['s'] = S;
    score['p'] = P;

    i64 ans = 0;

    rep(i, N) {
        char before = (i - K >= 0) ? s[i-K] : '~';
        if (s[i] == before) {
            s[i] = '~';
        } else {
            trace(i, s[i], before, KK[s[i]], score[KK[s[i]]]);
            ans += score[KK[s[i]]];
        }
    }

    print(ans);

    return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
int binarysearch(int *,int,int);

int main(){
  int n,q,i,key,result=0;
  int s[100000+1];

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

  scanf("%d",&q);
  for(i=0; i<q; i++){
    scanf("%d",&key);
    if(binarysearch(s,n,key)!=0) result++;
  }
  printf("%d\n",result);
  return 0;
}

int binarysearch(int s[],int n,int key){
  int left=0;
  int right=n;
  int mid;

  while(left<right){
    mid=(left+right)/2;
    if(key==s[mid]){
      return 1;
    }//keyをみつけたとき真を返す

    if(key<s[mid]){
      right=mid;
    }//keyがmidよりちいさいときみつけたい値は前にあるので、rightをmidとする
    
    if(key>s[mid]){
      left=mid+1;
    }
  }
  return 0;
}
		   



Measured memory_bytes: 2108
#include <bits/stdc++.h> 
#define lb lower_bound 
#define ub upper_bound 
#define sqr(x) (x)*(x) 
#define lowbit(x) (x)&(-x) 
#define mem(a,x) memset(a,x,sizeof(a));
using namespace std; 
typedef long long ll;

const ll mo = 1e9+7;
ll dp[2007];

int main(){
	int s;
	scanf("%d",&s);
	dp[0] = 0;
	dp[1] = 0;
	dp[2] = 0;
	dp[3] = 1;
	
	for(int i=4;i<=s;i++){
		dp[i] = dp[i-1] + dp[i-3]; 
		dp[i] %= mo;
	}
	printf("%d\n",dp[s]);
}

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

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int64_t> A(N), B(N);
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < N; i++) cin >> B[i];
  vector<int64_t> wins;
  int64_t loseSum = 0;
  int64_t loseCount = 0;
  for (int i = 0; i < N; i++) {
    if (A[i] > B[i]) {
      wins.push_back(A[i] - B[i]);
    } else {
      loseSum += B[i] - A[i];
    }
    if (A[i] < B[i]) {
      loseCount++;
    }
  }
  sort(wins.rbegin(), wins.rend());

  int i = 0;
  while (loseSum > 0 and i < wins.size()) {
    loseSum -= wins[i];
    i++;
  }

  if (loseSum > 0) {
    printf("-1\n");
  } else {
    printf("%zu\n", loseCount + i);
  }

  return 0;
}


Measured memory_bytes: 2556
N = int(input())
P = list(map(int,input().split()))
ans = 0
for i in range(1,N-1):
  if P[i] >= P[i-1] and P[i] <= P[i+1]:
    ans += 1
  elif P[i] <= P[i-1] and P[i] >= P[i+1]:
    ans += 1
print(ans)

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

int main() {
	string S, T;
	cin >> S >> T;
	
	string comp = S + S;
	for (int i = 0;i < S.length();i ++) {
		if (T == comp.substr(i, S.length())) {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

文字列の回転を代わりに次のような操作と考える
例えば、kyotoの回転だと次のように考える
最初にkyotokyotoという単語が与えられており、最初は5文字目から読んでいる
回転すると4文字目から読み……という風に1文字ずつスタート地点を変えていくものとする

この操作だと最初にS + Sを行った単語に関してみていけば分かる
*/

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;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
// cout << fixed << setprecision(10) << ans << endl; 有効桁数指定
// *min_element(c + l, c + r) *max_element(c + l, c + r) 配列の中のmin-max
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// ~ は、-1の時だけfalse

int main () {

    string s;cin>>s;

    int n = s.size();

    int l=0,r=(int)s.size()-1;

    bool ok=true;

    while (l!=r) {
        if (s[l]!=s[r]) {
            ok=false;
            break;
        } else {
            l++;
            r--;
        }
    }

    int l1 =0,r1=(n-1)/2-1;
    while (l1<r1)  {
        if (s[l1]!=s[r1]) {
            ok=false;
            break;
        } else {
            l1++;
            r1--;
        }
    }

    int l2 =(n+3)/2-1,r2=n-1;
    while (l2<r2)  {
        if (s[l2]!=s[r2]) {
            ok=false;
            break;
        } else {
            l2++;
            r2--;
        }
    }

    if (ok) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;



}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
long long  n,k;
long long out=0;
int mod=1e9+7;
struct macierz {
	int t[51][51];
};
macierz mac()
{
	macierz a;
		for(int i=0;50>=i;i++)
			for(int j=0;50>=j;j++)
				a.t[i][j]=0;
	return a;
}
macierz mno ( macierz a , macierz b)
{
	macierz c=mac();
	for(int i=0;n>i;i++)
		for(int k=0;n>k;k++)
			for(int j=0;n>j;j++)
				c.t[i][j]=(c.t[i][j]+1LL*a.t[i][k]*b.t[k][j])%mod;
	return c;
}
macierz pot ( macierz a , long long d )
{
	macierz wynik=a;
	d--;
	while(d)
	{
		if(d%2==1)
			wynik=mno(wynik,a);
		a=mno(a,a);
		d/=2;
	}
	return wynik;
}
int main(){
	cin>>n>>k;
	macierz xd = mac();
	for(int i=0;n>i;i++)
		for(int j=0;n>j;j++)
			cin>>xd.t[i][j];
	xd=pot(xd,k);
	for(int i=0;n>i;i++)
		for(int j=0;n>j;j++)
			out+=xd.t[i][j];
	cout<<out%mod;
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long int;
using pii = pair<int, int>;

int main()
{
    ll h, w, n;
    cin >> h >> w >> n;

    map<pii, int> black_cnt;
    rep(i, 0, n)
    {
        int a, b;
        cin >> a >> b;

        rep(x, a - 2, a + 1)
        rep(y, b - 2, b + 1)
        if (x > 0 and y > 0 and x <= h - 2 and y <= w - 2)
            ++black_cnt[make_pair(x, y)];
    }

    vector<ll> ans(10, 0);
    // cout << h << endl;
    ll total = (h - 2) *1LL * (w - 2)- black_cnt.size();
    // cout << total << endl;
    for (auto b_cnt: black_cnt)
    {
        pii b;
        int cnt;
        tie(b, cnt) = b_cnt;
        // cout << b.first << ' ' << b.second << ' ' << cnt << endl;

        ++ans[cnt];
    }
    ans[0] = total;
    for (auto a: ans)
        printf("%lld\n", a);
    return 0;
}

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

typedef long long ll;

int main(){
    int N;
    cin >> N;
    
    vector<ll> L(N+1);
    L[0]=2; L[1]=1;
    for(int i=2; i<=N; i++){
        L[i] = L[i-1] + L[i-2];
    }
    
    cout << L[N] << endl;
}


Measured memory_bytes: 256
def K1(n):
    ans = 0
    d = len(str(n))
    ans += int(str(n)[0])
    ans += 9 * (d-1)
    return ans


def K2(n):
    d = len(str(n))
    ans = 9**2*(d-2)*(d-1)//2
    ans += (int(str(n)[0]) - 1) * 9 * (d-1)
    ans += K1(int(str(n)[1:]))
    return ans


def K3(n):
    d = len(str(n))
    ans = 0
    for i in range(2,d-1):
        ans += i*(i-1)//2
    ans *= 9**3
    ans += (int(str(n)[0]) - 1) * 9**2 * (d-1)*(d-2) // 2
    ans += K2(int(str(n)[1:]))
    return ans


def main():
    N = int(input())
    K = int(input())

    if K == 1:
        print(K1(N))

    if K == 2:
        if N < 10:
            print(0)
            exit()
        print(K2(N))

    if K == 3:
        if N < 100:
            print(0)
            exit()
        print(K3(N))



if __name__ == "__main__":
    main()


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

int main() {
	int n;
	cin >> n;
	vector<int> nums(2 * n);

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

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

	int res = 0;

	for (int i = 0; i < 2 * n - 1; i += 2) {
		res += min(nums[i], nums[i + 1]);
	}

	cout << res << endl;
}

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

typedef long long LL;
typedef long double LD;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define mp1(a,b,c) P1(a,P(b,c))
#define pque(a) priority_queue<a>
#define rpque(a) priority_queue<a,vector<a>,greater<a>>

const int INF=1000000000;
const int dre_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dre_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
const int kaijou[10]={1,1,2,6,24,120,720,5040,40320,362880};

int gcd(int x,int y){
	if(y==0)return x;
	return gcd(y,x%y);
}

int main(){
	int a,b;
	while(~scanf("%d%d",&a,&b))printf("%d %d\n",gcd(a,b),a/gcd(a,b)*b);
}

Measured memory_bytes: 1172
s = input()
t = input()

stri = []
mincount = 1e9
for i in range(len(s)-len(t)+1):
    count = 0
    for j in range(len(t)):
        if(s[i+j] != t[j]):
            count+= 1
    mincount = min(mincount,count) 
print(mincount)

Measured memory_bytes: 9024
#include <bits/stdc++.h>
using LL = long long;
using namespace std;
#define DBG(x) ; // cerr<<#x<<" = "<<x<<endl
#define rep(i,n) for(int i=0;i<(n);++i)

LL N;

int main()
{
	cin >> N;
	std::vector<LL>a(N), b(N);
	rep(i, N) cin >> a[i] >> b[i];
	
	std::priority_queue<LL, std::vector<LL>, std::greater<LL>>c;
	rep(i, N) c.push(a[i] + b[i]);
	
	while(!c.empty())
	{
		LL num1 = c.top(); c.pop();
		if (c.empty())
		{
			cout << num1 << " 0" << endl;
			break;
		}
		LL num2 = c.top();
		if (num1 == num2)
		{
			c.pop();
			c.push(num1 + 1);
		}
		else cout << num1 << " 0" << endl;
	}
	return 0;
}


Measured memory_bytes: 5516
#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 sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    ll h,w,m;cin>>h>>w>>m;
    vector<ll> mp1(300010,0),mp2(300010,0);
    map<pair<ll,ll>,ll> mp3;
    rep(i,m){
        ll h,w;cin>>h>>w;h--;w--;
        mp1[h]++;mp2[w]++;
        mp3[{h,w}]++;
    }
    ll buf1=-1,buf2=-1;
    rep(h,300010)chmax(buf1,mp1[h]);
    rep(w,300010)chmax(buf2,mp2[w]);
    vector<ll> x,y;
    rep(h,300010){
        if(buf1==mp1[h])x.push_back(h);
    }
    rep(w,300010){
        if(buf2==mp2[w])y.push_back(w);
    }
    ll res=buf1+buf2-1;
    bool ok=false;
    rep(i,x.size()){
        if(ok)break;
        rep(j,y.size()){
        ll h=x[i],w=y[j];
        if(mp3[{h,w}]==0){
            res++;
            ok=true;
            break;
        }
        }
    }
    cout<<res<<endl;
}

Measured memory_bytes: 34980
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;
int n, m;

const int INF = 1 << 29;

vector<int> stage, me;

int main(void)
{
	while(cin >> n >> m && n && m)
	{
		stage.resize(n);
		for (int i = 0; i < n; i++)
		{
			cin >> stage[i];
		}
		me.resize(m);
		for (int i = 0; i < m; i++)
		{
			cin >> me[i];
		}

		int cur = 0;
		int ans = -1;
		for (int i = 0; i < m; i++)
		{
			cur += me[i];

			if(cur >= n)
			{
				ans = i;
				break;
			}
			cur += stage[cur];
			
			if(cur >= n)
			{
				ans = i;
				break;
			}
		}
		if(ans == -1) ans = m - 1;
		cout << ans + 1 << endl;
	}
	return 0;
}

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

#define int long long
#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define eb emplace_back
#define dump(x) cout << #x << " = " << (x) << endl
#define chk() cout << "now" << endl;
#define ALL(x) (x).begin(), (x).end()
#define SORT(c) sort((c).begin(), (c).end())
#define SORTG(c) sort(ALL(c), greater<int>());
#define fi first
#define se second
int INF = 1e9 + 7;

typedef pair<int, int> P;
typedef vector<int> vi;

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

int n;
vi a;

void solve() {
  cin >> n;
  a.resize(n + 1);
  a[0] = 0;
  rep(i, 1, n + 1) { cin >> a[i]; }
  vi res;
  rep(i, 0, n) {
    int pivot = -1;
    for (int j = a.size() - 1; j >= 1; j--) {
      if (a[j] == j) {
        pivot = j;
        break;
      }
    }

    if (pivot == -1) {
      cout << -1 << endl;
      return;
    }

    res.pb(pivot);
    a.erase(a.begin() + pivot);
  }
  reverse(ALL(res));
  rep(i, 0, n) cout << res[i] << endl;
}

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

  // cout << fixed << setprecision(10);

  solve();

  return 0;
}


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

int main(void) {
	char a[10],b[10],c[10];

	scanf("%s %s %s",a,b,c);

	int A,B;

	A=strlen(a);
	B=strlen(b);

	if(a[A-1]==b[0] && b[B-1]==c[0]) {
		printf("YES\n");
	}
	else {
		printf("NO\n");
	}

	return 0;
}


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

int main(){
    int a,b,c,x;
    int count = 0;
    cin >> a >> b >> c;
    for(int x=a; x<=b; x++){
        if(c%x==0){
            count+=1;}
        }
    cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
 ll N;
  cin>>N;
 ll m;
  cin>>m;
  ll ans=0;
  for(ll i=0;i<N-1;i++) {
    ll A;
    cin>>A;
    if(A<m) {
ans+=m-A;
    }
    if(m<A) {
m=A;
    }
  }
  
  cout<<ans<<endl;
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

constexpr ll MOD = 1'000'000'007;
int N;
int A[500100], Z[500100];
ll S[500100], T[500100];
std::map<int, int> pm;

template <typename T>
T mod_expt(T a, std::int64_t n, T mod){
    T power {1};
    while(n > 0){
        if(n & 1){power = power * a % mod;}
        a = a * a % mod;
        n >>= 1;
    }
    return power;
}

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

    scanf("%d", &N);

    for(int i=1;i<=N;++i){
        scanf("%d", A + i);
        
        A[i] ^= A[i-1];
        Z[i] = Z[i-1] + (A[i] == 0);
    }

    S[0] = 1;
    T[0] = 0;

    for(int i=1;i<=N;++i){
        if(A[i] == 0){
            continue;
        }

        int p = pm[A[i]];

        ll z = Z[i] - Z[p];
        S[i] = (S[p] + T[p] * z % MOD) % MOD;
        T[i] = (S[i] + T[p]) % MOD;
        pm[A[i]] = i;
        
        // std::cout << p << ", " << z << ", " << S[i] << ", " << T[i] << std::endl;
    }

    ll res = S[N];

    if(A[N] == 0){
        res = (res + mod_expt<ll>(2ll, Z[N] - 1, MOD)) % MOD;

        for(int i=1;i<N;++i){
            res = (res + S[i]) % MOD;
        }
    }

    std::cout << res << std::endl;
}


Measured memory_bytes: 25472
#include<bits/stdc++.h>
using namespace std;
#define F(i,s,e) for(int i=s;i<e;++i)

int main()
{
    string s;
    cin >> s;
    long c=0;
    F(i,0,s.size()/2){
        if(s[i]!=s[s.size()-1-i]) ++c;
    }
    cout << c << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <string>
#include <cstring>
#include <numeric>
#include <iomanip>
#include <fstream>
using namespace std;
int main(){
	int n,a,b,c;
	cin>>n>>a>>b>>c;
	vector<char> ans;
	string s[100000];
	for(int i=0;i<n;i++){
		cin>>s[i];
	}
	for(int i=0;i<n;i++){
		if(s[i]=="AB"){
			if(a==0&&b==0){
				cout<<"No"<<endl;
				return 0;
			}else if(a<b){
				ans.push_back('A');	
				a++;
				b--;
			}else if(a>b){
				ans.push_back('B');
				a--;
				b++;
			}else{
				if(i==n-1){
					ans.push_back('A');
					a++;
					b--;
				}else if(s[i+1]=="AB"){
					ans.push_back('A');
					a++;
					b--;
				}else if(s[i+1]=="BC"){
					ans.push_back('B');
					a--;
					b++;
				}else{
					ans.push_back('A');
					a++;
					b--;
				}
			}
		}else if(s[i]=="BC"){
			if(b==0&&c==0){
				cout<<"No"<<endl;
				return 0;
			}else if(b<c){
				ans.push_back('B');
				b++;
				c--;
			}else if(b>c){
				ans.push_back('C');
				b--;
				c++;
			}else{
				if(i==n-1){
					ans.push_back('B');
					b++;
					c--;
				}else if(s[i+1]=="AB"){
					ans.push_back('B');
					b++;
					c--;
				}else if(s[i+1]=="BC"){
					ans.push_back('B');
					b++;
					c--;
				}else{
					ans.push_back('C');
					b--;
					c++;
				}
			}
		}else{
			if(a==0&&c==0){
				cout<<"No"<<endl;
				return 0;
			}else if(a<c){
				ans.push_back('A');
				a++;
				c--;
			}else if(a>c){
				ans.push_back('C');
				a--;
				c++;
			}else{
				if(i==n-1){
					ans.push_back('A');
					a++;
					c--;
				}else if(s[i+1]=="AB"){
					ans.push_back('A');
					a++;
					c--;
				}else if(s[i+1]=="BC"){
					ans.push_back('C');
					a--;
					c++;
				}else{
					ans.push_back('A');
					a++;
					c--;
				}

			}
		}
//		if(a<0||b<0||c<0){
//			cout<<"out"<<endl;
//		}
	}
	cout<<"Yes"<<endl;
	for(int i=0;i<ans.size();i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 6884
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long


signed main(){
  string l;
  cin>>l;
  int cnt=0,fst;
  int num[100010];
  int ans=0;
  num[0]=1;
  repi(i,1,100010){
    num[i]=(num[i-1]*3)%MOD;
  }
  
  if(l[l.size()-1]=='0') ans=1;
  else ans=3;
  
  cnt=1;
  repn(i,l.size()-2 ){
    if(l[i]=='1'){
      ans*=2;
      ans%=MOD;
      ans+=num[cnt];
      ans%=MOD;
    }
    cnt++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1280
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a[100005]={};
int main()
{
	int n,m;
	char x;
	scanf("%d%d",&n,&m);
	cin>>x;
	char c;
	for (int i=2;i<=n;i++)
	{
		cin>>c;
		if (x=='A'&&c=='C')
		{
			a[i]=a[i-1]+1;
		}
		else a[i]=a[i-1];
		x=c;
	}
	a[1]=0;
	for (int i=1,l,r;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",a[r]-a[l]);
	}
}

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

/* -128 ~ 127 */
using i8  = int8_t;
/* 0 ~ 255 */
using u8  = uint8_t;
/* -32,768 ~ 32,767 */
using i16 = int16_t;
/* 0 ~ 65,535 */
using u16 = uint16_t;
/* -2,147,483,648 ~ 2,147,483,647 */
using i32 = int32_t;
/* 0 ~ 4,294,967,295 */
using u32 = uint32_t;
/* -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 */
using i64 = int64_t;
/* 0 ~ 18,446,744,073,709,551,615 */
using u64 = uint64_t;
/* (-3.4 * 10^38) ~ (3.4 * 10^38) */
using f32 = float;
/* (-1.7 * 10^308) ~ (1.7 * 10^308) */
using f64 = double;
using f80 = __float80;

template <class T>
using Vec = vector<T>;

template <typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template <typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }

/* 定数 */
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;

#define fn auto
#define ALL(v) v.begin(), v.end()

fn Main() {
    u32 K, N;
    cin >> K >> N;
    Vec<u32> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    Vec<u32> B(N);
    B[N - 1] = K - A[N - 1] + A[0];
    for (int i = 0; i < N - 1; i++) {
        B[i] = A[i + 1] - A[i];
    }
    sort(ALL(B));

    u32 sum = 0;
    for (int i = 0; i < N - 1; i++) {
        sum += B[i];
    }
    cout << sum << endl;
}

fn main() -> int {
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}



Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
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 << " ";
  }
}
int main() {
  cin.tie(0);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  vector<ll> x(n);
  for(int i=0;i<n;++i) {
    cin >> x[i];
  }
  ll l; cin >> l;
  vector<vector<int>> r(31, vector<int>(n));
  for(int i=0;i<n;++i) {
    auto it = upper_bound(x.begin(), x.end(), x[i] + l);
    int pos = distance(x.begin(), it);
    r[0][i] = pos - 1;
  }
  for(int i=1;i<31;++i) {
    for(int j=0;j<n;++j) {
      r[i][j] = r[i-1][r[i-1][j]];
    }
  }
  int q; cin >> q;
  while(q > 0) {
    q--;
    int a, b; cin >> a >> b;
    a--; b--;
    if(a > b) swap(a, b);
    int ans = 0;
    int now = a;
    for(int i=29;i>=0;--i) {
      if(r[i][now] < b) {
        ans += 1<<i;
        now = r[i][now];
      }
    }
    cout << ans + 1 << endl;
  }
}


Measured memory_bytes: 13816
N, X, Y = map(int, input().split())
f = [0] * N
for i in range(1, N):
    for j in range(i + 1, N + 1):
        if j <= X or Y < i:
            d = j - i
        elif i <= X and j <= Y:
            d = min(j - i, Y - j + 1 + X - i)
        elif i <= X and Y < j:
            d = X - i + 1 + j - Y
        elif X < i and Y < j:
            d = min(j - i, j - Y + 1 + i - X)
        elif X < i and j <= Y:
            d = min(j - i, i - X + 1 + Y - j)
        f[d] += 1
for i in range(1, N):
    print(f[i])

Measured memory_bytes: 48092
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(ll i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<llint,llint>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 100000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
struct edge { int to, cost; };

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}

long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//aCbをmod.mで割った余りを求める
ll int c(ll int a, ll int b, ll int m) {
	ll int ans = 1;
	for (ll int i = 0; i < b; i++) {
		ans *= a - i;
		ans %= m;
	}
	for (ll int i = 1; i <= b; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}
	int size(int a) {
		return par[root(a)];
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
int max(int a, int b) {
	if (a < b)return b;
	return a;
}
int min(int b, int a) {
	if (a > b)return b;
	return a;
}
int f(llint a) {
	int ans = 0;
	while (a) {
		a /= 2;
		ans++;
	}
	return ans;
}

int main() {
	int a, b;
	cin >> a;
	b = a % 10;
	string ans;
	if (b == 2 || b == 4 || b == 5 || b == 7 || b == 9)ans = "hon";
	else {
		if (b == 0 || b == 1 || b == 6 || b == 8)ans = "pon";
		else {
			ans = "bon";
		}
	}
	cout << ans << endl;
	return 0;
}



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

int main() {
    int N, K; cin >> N >> K;
    vector<ll> x(N);
    vector<ll> y(N);
    rep(i, N){
        cin >> x[i] >> y[i];
    }

    ll ans = (1e18) * 5;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            for (int k = 0; k < N; k++){
                for (int l = 0; l < N; l++){
                    if(x[i] <= x[j] && y[k] <= y[l]){
                        int cnt = 0;
                        for (int m = 0; m < N; m++){
                            if(x[m] >= x[i] && x[m] <= x[j] && y[m] >= y[k] && y[m] <= y[l]){
                                cnt++;
                            }
                        }
                        if(cnt >= K){
                            ans = min(ans, (x[j] - x[i]) * (y[l] - y[k]));
                        }
                    }
                }
            }
        }
    }
    
    cout << ans << endl;

    return 0;
}

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

int main() {

	string s;
	cin >> s;

	if(count(s.begin(), s.end(), 'o') + (15-s.length()) >= 8){
		cout << "YES" << endl;
	}
	else{
		cout << "NO" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

const ll N=2e5+10;
mat G(N);
vec ans(N);

void dfs(ll cur, ll pre) {
	for(auto nex:G[cur]) {
		if(nex==pre) continue;
		ans[nex]+=ans[cur];
		dfs(nex,cur);
	}
}

int main() {
  ll n,q;
  cin >> n >> q;
  for(ll i=0;i<n-1;i++) {
    ll a,b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
  }
	for(ll i=0;i<q;i++) {
		ll p,x;
		cin >> p >> x;
		ans[p]+=x;
	}
	dfs(1,-1);
	for(ll i=1;i<=n;i++) {
		if(i!=1) cout << " ";
		cout << ans[i];
	}
	cout << endl;
}

Measured memory_bytes: 24320
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>a
#define pb push_back
#define sz(x) int(x.size())

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

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

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

class UnionFind{
public:
  vi Parent;
  UnionFind(int n){
    Parent = vi(n,-1);
  }

  int root(int a){
    if(Parent[a] < 0) return a;
    else return Parent[a] = root(Parent[a]);
  }

  int size(int a){
    return -Parent[root(a)];
  }

  bool merge(int a, int b){
    a = root(a);
    b = root(b);
    if(a == b) return false;

    if(size(a) < size(b)) swap(a,b);
    Parent[a] += Parent[b];
    Parent[b] = a;

    return true;
  }
};

class Factrial{
public:
  vl Fac;
  Factrial(int MAX){
    Fac = vl(MAX+1);
    rep(i,MAX) {
      if(i == 0) Fac[i+1] = 1;
      else Fac[i+1] = ((i+1)*Fac[i])%MOD;
    }
  }
};

const int MAX = 510000;
long long 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;
    }
}

// 二項係数計算
long long 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;
}

ll myPow(ll x, ll n){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % MOD, n / 2);
  else
    return x * myPow(x, n - 1) % MOD;
}

int main(){
  ll n, k; cin >> n >> k;
  COMinit();
  ll ans = 0;
  if(k >= n-1){
    cout << COM(n+n-1,n) << endl;
    return 0;
  }
  for(ll i = 0; i <= k; i++) {
    ll sum = COM(n, i)*COM(n-1, n-i-1);
    sum %= MOD;
    ans += sum;
    ans %= MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 12160
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define llu unsigned long long int
#define sa(a,n,t) for(int ii=0;ii<n;ii++) scanf("%"#t"",&(a)[ii])
#define rep(i,n) for(int i=0;i<n;i++) 
#define reps(i,a,n) for(int i=a;i<n;i++) 
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rreps(i,a,n) for(int i=n-1;i>=a;i--)
#define validl(i,a,b) ((i>=a)&&(i<=b))?1:0
#define validmat(x,y,a,b,c,d) (validl(x,a,b) && validl(y,a,b))?1:0
#define validmn(x,y,m,n) validmat(x,y,0,m,0,n)
#define valid(i,n) validl(i,0,n)
#define v(t) vector<t>
#define vv(t) vector<vector<t> >
#define mk make_pair
#define pb push_back
#define pa(a,n,t)  for(int i=0;i<n;i++) printf("%"#t"",a[i])
#define p2 pair<int,int>
#define p3 pair<p2,int>
#define fi first
#define se second
#define sd(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define pl(a) printf("%lld",a)
#define pd(a) printf("%d",a)
#define sf(a) scanf("%lf",&a)
#define pf(a) printf("%lf",a)
#define nline printf("\n")
#define ss(a) scanf("%s",a)
#define ps(a) printf("%s",a)
#define sc(a) scanf("%c",&a)
#define pc(a) printf("%c",&a)
#define mf(m,f) m.find(f)!=m.end()
#define pp3(m) cout<<m.fi.fi<<" "<<m.fi.se<<" "<<m.se<<" "
#define pp2(m) cout<<m.fi<<" "<<m.se<<" "
#define debug 0
/*v(int) adj[200001];
void dfs(int i,int p){
    rep(j,adj[i].size()){
        if(p!=adj[i][j])
            dfs(adj[i][j],i);
    }
}*/
int main()
{
  char c;
  cin>>c;
  if(c>='A' && c<='Z') cout<<"A\n";
  else cout<<"a\n";
  
  return 0;
}


Measured memory_bytes: 3592
#include <cstdio>
#include <iostream>
#include <string>
#include <queue>
#define INF (1<<21)
using namespace std;

class State{
public:
  int n,cost,c,f;
  State(int n = 0,int cost = 0, int c = 0,int f = 0):n(n),cost(cost),c(c),f(f){}
  bool operator < (const State &s) const{ return cost > s.cost;}
};

int main(){
  int i,j;
  while(1){
    int G[101][101],c,n,m,s,t;
    State d[101][11];
    priority_queue<State> PQ;

    cin >> c >> n >> m >> s >> t;
    if(c == 0 && n == 0 && m == 0 && s == 0 && t == 0) break;

    for(i=0;i<=n;i++){
      for(j=0;j<=n;j++) G[i][j] = INF;
      for(j=0;j<=c;j++){
	d[i][j].cost = INF;
	d[i][j].n = i;
	d[i][j].c = j;
	d[i][j].f = 0;
      }
    }

    for(i=0;i<m;i++){
      int a,b,c;
      cin >> a >> b >> c;
      G[a][b] = G[b][a] = c;
    }

    d[s][c].cost = 0;
    State p = d[s][c];
    PQ.push(p);

    while(!PQ.empty()){
      p = PQ.top();
      PQ.pop();
      d[p.n][p.c].f = 1;

      for(i=0;i<=n;i++){
	if(d[i][p.c].f == 0 && G[p.n][i] + p.cost < d[i][p.c].cost){
	  d[i][p.c].cost = G[p.n][i] + p.cost;
	  PQ.push(d[i][p.c]);
	}
	if(p.c > 0 && G[p.n][i] != INF && d[i][p.c-1].f == 0 && G[p.n][i] / 2 + p.cost < d[i][p.c-1].cost){
	  d[i][p.c-1].cost = G[p.n][i] / 2 + p.cost;
	  PQ.push(d[i][p.c-1]);
	}
      }
    }

    int min = INF;
    for(i=0;i<=c;i++){
      if(min > d[t][i].cost) min = d[t][i].cost;
    }
    cout << min << endl;

  }
  return 0;
}

//0212

Measured memory_bytes: 992
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int N = Integer.parseInt(br.readLine());
        String S = br.readLine();
        int K = Integer.parseInt(br.readLine());
        String s = "[^" + String.valueOf(S.charAt(K - 1)) + "]";
        String ans = S.replaceAll(s, "*");
        out.println(ans);
        out.close();
    }
}


Measured memory_bytes: 21332