akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int a,b;
    int data[51]={0};
    for(int i=0;i<m;i++){
        cin>>a>>b;
        data[a-1]++;
        data[b-1]++;
    }
    for(int i=0;i<n;i++){
        cout << data[i] << endl;
    }
    
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

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

    reverse (a, a + n);
    reverse (b, b + n);

    long long d = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] and b[i] == 1) continue;
        d += b[i] * ((a[i] + d) / b[i] + !!((a[i] + d) % b[i])) - (a[i] + d);
    }
    cout << d << endl;

    return 0;
}


Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
from itertools import combinations

n = int(input())

al = []
for _ in range(n):
    a = int(input())
    xy = [list(map(int, input().split())) for _ in range(a)]
    al.append(xy)

res = 0
for i in range(1,n+1):
    for c in combinations(range(n), i):
        flag = True
        for X in c:
            for x,y in al[X]:
                if y==1:
                    if x-1 not in c:
                        flag = False
                else:
                    if x-1 in c:
                        flag = False
        if flag:
            res = i
            break

print(res)


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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back

typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;


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

	sort(a,a+n,greater<int>());

	ll ans=1,p=0;
	for (int i = 0; i < n; ++i){
		if(a[i]==a[i+1]){
			ans*=a[i];
			i++;
			p++;
		}
		if(p==2){
			cout<<ans<<endl;
			return 0;
		}
	}

	cout<<0<<endl;

	return 0;
}


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

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

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> x(N);
  for (int i = 0; i < N; i++) cin >> x[i];

  x.push_back(X);
  sort(x.begin(), x.end());

  vector<int> dis(N);
  for (int i = 0; i < N; i++) dis[i] = x[i + 1] - x[i];

  int D = dis[0];
  for (int i = 1; i < N; i++) D = Gcd(D, dis[i]);

  cout << D << endl;

  return 0;
}

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

using namespace std;
using ll = long long;

int main(){
    int n;cin >> n;
    vector<long double> vec;
    for(int i = 0;i < n;i++){
        int b;cin >> b;
        vec.push_back(b);
    }
    sort(vec.begin(), vec.end());
    long double ans = vec.front();
    for(int i = 1;i < vec.size();i++){
        ans = (ans + vec.at(i)) /2;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
object Main extends App {
  val n = io.StdIn.readLine().toInt
  val list = collection.mutable.ListBuffer[Array[Int]](Array(0 ,0, 0))
  (1 to n).foreach { i =>
    list += io.StdIn.readLine().split(' ').map(_.toInt).toArray
  }
  def f(t: Int, x: Int): Boolean = {
    if (t == 0) (x == 0)
    else if(x == 0) (t & 1) == 0
    else if (x < 0 || x > t) false
    else (f(t - 1, x - 1))
  }
  list.zip(list.tail)
  val list2 = list.zip(list.tail).map{case (x1, x2) => (x2(0) - x1(0), Math.abs(x2(1) - x1(1)) + Math.abs(x2(2) - x1(2)))}
  print(if(list2.forall{case (t, x) => f(t, x)}) "Yes" else "No")
}


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

#define F first
#define S second
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define in(x) insert(x)
#define forr(i, a, b) for(int i = a;i <= b;i++)
#define sz(s) (int)(s.size())
#define all(x) x.begin(), x.end()
#define did_you_calis_enough ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define int long long

using namespace std;

const int INF =  4294967295;
const int  N = 2e6 + 667;
const int mod = 1e9 + 7;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double PI = acos(-1.0);


main() {
	did_you_calis_enough
	int a, b, c;
	cin >> a >> b >> c;
	cout << ((a + (b-1)) / b) * c; 
}

//Coded by LoliThief


Measured memory_bytes: 3692
#include <iostream>
#include <cstdio>
#include <string>
#include <bits/stdc++.h>
#include <set>
#include <list> //list<???> a; a.push_back ,insert(追加したい要素),a.sort(),参照できない
#include <vector> //vector<???> a; a.push_back,sort(a.begin(),a.end());a[i]
//配列 int a[N];a[i]=追加したい要素;sort(a,a+N);a[i]
const int MOD = 1e9+7;
using namespace std;
typedef long  ll;
#define rep(i,n) for(int i=0;i<(n);i++)


//using namespace std;
//


int main(){
  string moji;cin>>moji;
  cout<<moji.substr(0,5)<<" "<<moji.substr(6,7)<<" "<<moji.substr(14,5)<<endl;;
}

Measured memory_bytes: 256
#include<stdio.h>

void swap(int *,int *);

main(){

  int N;
  int i,j,swapc=0;
  int A[100];
  
  scanf("%d",&N);

  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  for(i=0;i<N;i++){
    for(j=N-1;j>=1;j--){
      if(A[j]<A[j-1]){
	swap(&A[j],&A[j-1]);
	swapc++;
      }
    }
  }
  for(i=0;i<N;i++){
    printf("%d",A[i]);
    if(i!=N-1)printf(" ");
    else if(i==N-1)printf("\n");
  }
  printf("%d\n",swapc);
  return 0;
}


void swap(int *x,int *y)
{
  int temp;

  temp=*x;
  *x=*y;
  *y=temp;
}

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

int main(){
ll n;
cin >> n ;
vector<ll> a(n);
for(ll i = 0; i< n; i++)cin >> a[i];
int q;
cin >> q;

ll p[100005]={0};
for(ll i = 0; i< n; i++) p[a[i]]++;
ll sum = 0;
for(ll i = 0; i< 100005; i++) sum += i*p[i];

for(int i=1;i<=q;i++){
   int b, c;
   cin >> b >> c;
   sum = sum - p[b]*b + p[b]*c;
    p[c] = p[b] + p[c];    
    p[b] = 0;
    cout << sum << endl;
}
 return 0;
}
 

Measured memory_bytes: 4844
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool tris, dable;
int main(){
    int n, a, b, c, d, pang=0,  ping=0;
    string x, y;
    cin  >> n >> a >> b >> c >> d;
    cin >> x;
    for(int i=0; i<n; i++){
        if(i==a-1 || i==b-1){
            y+="&";
        }
        else{
            if(x[i]=='#'){
                y+="#";
            }
            else{
                y+=".";
            }
        }
    }
        
    ping = max(a-1, b-1);
    pang = min(c-1, d-1);
    if(y[c-1]=='#' || y[d-1]=='#' || c==d){
        cout << "No" << endl;
    }
    else if((a>b && c<d) || (a<b && c>d)){
        while(ping <= pang){
            if(y[ping]!='#' && y[ping-1]!='#' && y[ping+1]!='#'){
                tris = true;
            }
            ping++;
        }
        for(int i=a-1; i<c; i++){
            if(y[i]=='#' && y[i-1]=='#'){
                dable=true;
            }
        }
        for(int i=b-1; i<d; i++){
             if(y[i]=='#' && y[i-1]=='#'){
                dable=true;
            }
        }
        if(dable==true){
            cout << "No" << endl;
        }
        else{
            if(tris==true){
                cout << "Yes" << endl;
            }
            else{
                cout << "No" << endl;
            }
        }
    }
    else if((a>b && c>d) || (a<b && c<d)){
        for(int i=a-1; i<c; i++){
             if(y[i]=='#' && y[i-1]=='#'){
                dable=true;
            }
        }
        for(int i=b-1; i<d; i++){
             if(y[i]=='#' && y[i-1]=='#'){
                dable=true;
            }
        }
        if(dable==true){
            cout << "No" << endl;
        }
        else{
            cout << "Yes" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 776
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using Pair = pair<int, int>;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define INF 1000000007
#define SEP " "

int     main()
{
	string s;
	cin >> s;
	int len = s.size();
	vector<int> ans(len, 0);
	Pair c(1, 0);
	for (int i = 1; i < len; i++) {
		if (s[i] == 'R')
		{
			if (i & 1)
				c.second++;
			else
				c.first++;
			continue ;
		}
		if (i & 1)
		{
			ans[i] += c.second;
			ans[i-1] += c.first;
		}
		else
		{
			ans[i] += c.first;
			ans[i-1] += c.second;
		}
		while (i < len && s[i] == 'L')
			i++;
		if (i & 1)
			c = make_pair(0, 1);
		else
			c = make_pair(1, 0);
	}
	if ((len - 1) & 1)
		c = make_pair(0, 1);
	else
		c = make_pair(1, 0);
	for (int i = len - 2; i >= 0; i--) {
		if (s[i] == 'L')
		{
			if (i & 1)
				c.second++;
			else
				c.first++;
			continue ;
		}
		if (i & 1)
		{
			ans[i] += c.second;
			ans[i+1] += c.first;
		}
		else
		{
			ans[i] += c.first;
			ans[i+1] += c.second;
		}
		while (i >= 0 && s[i] == 'R')
			i--;
		if (i & 1)
			c = make_pair(0, 1);
		else
			c = make_pair(1, 0);
	}
	cout << ans[0];
	for (int i = 1; i < len; i++)
		cout << SEP << ans[i];
	cout << endl;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

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

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

template <class T> inline void chadd(T &a, const T &b) { a += b, a %= MOD; }

int main() {
  // Input
  std::string S;
  std::cin >> S;
  S.insert(S.begin(), '-');
  int N = S.size() - 1;

  // Main
  // 101010 の場合
  int res1 = 0;
  for (int i = 1; i <= N; ++i) {
    if (i % 2 == 1) {
      // 奇数
      if (S[i] != '1')
        res1 += 1;
    } else {
      // 偶数
      if (S[i] != '0')
        res1 += 1;
    }
  }

  // 010101 の場合
  int res2 = 0;
  for (int i = 1; i <= N; ++i) {
    if (i % 2 == 1) {
      // 奇数
      if (S[i] != '0')
        res2 += 1;
    } else {
      // 偶数
      if (S[i] != '1')
        res2 += 1;
    }
  }

  // Output
  int res = IINF;
  chmin(res, res1);
  chmin(res, res2);
  std::cout << res << std::endl;

  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
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; }
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll tmp1,tmp2,tmp3;
const ll mod = 998244353;
const int INF = 1e9;
const ll INFLONG = 1e18;
void swap(ll *x,ll *y){
  ll tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}
int main(){
  ll x,y;
  cin >> x >> y;
  if(x <= 9 && y <= 9){
    cout << x*y << endl;
  }else{
    cout << -1 << endl;
  }
}

Measured memory_bytes: 764
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}

template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

template<typename T,typename Y>
ostream& operator<<(ostream& os,const pair<T,Y>& p){
  return os<<"{"<<p.fs<<","<<p.sc<<"}";
}
template<typename T> ostream& operator<<(ostream& os,const V<T>& v){
  os<<"{";
  for(auto e:v)os<<e<<",";
  return os<<"}";
}
template<typename ...Args>
void debug(Args&... args){
  for(auto const& x:{args...}){
    cerr<<x<<' ';
  }
  cerr<<ENDL;
}



signed main(){
  cin.tie(0);cerr.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll a,b,c,k;cin>>a>>b>>c>>k;
  ll cnt=0;
  while(a>=b){
    ++cnt;
    b*=2;
  }
  while(b>=c){
    ++cnt;
    c*=2;
  }

  if(cnt<=k)cout<<"Yes"<<ENDL;
  else cout<<"No"<<ENDL;
}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

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

int main() {
	ll n;
	cin >> n;
	vector<int> a(n+1);
	for(ll x = 1; x*x <=n; x++) {
		for(ll y = 1; y*y <=n; y++) {
			for(ll z = 1; z*z <=n; z++) {
				ll t = x*x+y*y+z*z+x*y+y*z+z*x;
				if (t > n) continue;
				else a[t]++;
			}
		}
	}
		
	rep(i, n+1){
		if(i==0) continue;
		cout << a[i] << endl;
		
	}
	
	return 0;
}

Measured memory_bytes: 3520
#include<iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  int i=1;
  while(++i<=n){
    int x=i;
    if(x%3==0){
      cout << " " << i;
      continue;
    }
    while(x){
      if(x%10==3){
	cout << " " << i;
	break;
      }
      x/=10;
    }
  }
  cout << endl;
  return 0;
}



Measured memory_bytes: 3084
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val N, A, B, C = sc.nextInt
    val l = Array.fill[Int](N)(sc.nextInt)

    import Math.abs
    var result = Long.MaxValue

    def dfs(i: Int, mp: Int, a: Int, b: Int, c: Int): Unit = {
      if (i == N) {
        if (Array(a, b, c).min != 0) {
          val totalMp = mp + abs(A - a) + abs(B - b) + abs(C - c)
          if (totalMp < result) {
            result = totalMp
          }
        }
        return
      }
      dfs(i + 1, if (a != 0) mp + 10 else mp, a + l(i), b, c)
      dfs(i + 1, if (b != 0) mp + 10 else mp, a, b + l(i), c)
      dfs(i + 1, if (c != 0) mp + 10 else mp, a, b, c + l(i))
      dfs(i + 1, mp, a, b, c)
    }

    dfs(0, 0, 0, 0, 0)
    println(result)
  }
}

Measured memory_bytes: 39424
#include<iostream>
using namespace std;
int main(){
  
  int i,l,a,b,m[15],sum;
  
  while(cin >> l,l!=0){
    for(i=0;i<12;i++){
      cin >> a >> b;
      m[i] = a-b;
    }
    m[13] = l;
    
    sum = 0;
    for(i=0;i<=12;i++){
      sum += m[i];
      if(sum >= l){
	if(i == 12) cout << "NA" << endl;
	else cout << i+1 << endl;
	break;
      }
    }
  }
  return(0);
}



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

#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i) 
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i) 
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i) 

typedef long long ll; 
typedef double ff; 

inline void print(ll x) { 
	int as=0; while (x) ++as, x/=10; 
	cout<<as<<endl; 
	exit(0); 
}
int main() { 
	int n,a,b; ll v[60],C[60][60]; ff as=0;
	memset(C,0,sizeof(C)); 	C[0][0]=1; 
	for (int i=1; i<=50; ++i) {C[i][0]=1; 
		for (int j=1; j<=i; ++j) 
			C[i][j]=C[i-1][j-1]+C[i-1][j]; 
	}
	scanf("%d%d%d",&n,&a,&b); 
//	rep(i,1,n) { rep(j,1,i) cout<<C[i][j]<<' ';cout<<endl;}
	rep(i,1,n) cin>>v[i];
	sort(v+1,v+1+n);
	reverse(v+1,v+1+n); 
	
	rep(i,1,a) as+=v[i]; 
	printf("%.10lf\n", as/a); 
	
	if (v[a]==v[1]) { 
		int i=a; ll as=0;  	
		while (i+1<=n&&v[i+1]==v[1]) 
			++i; 
		rep(j,a,min(i,b)) as+=C[i][j]; 
		return cout<<as<<endl,0; 
	} else { 
		int i=a,j=a;  ll as=0; 
		while (i+1<=n&&v[i+1]==v[i])++i; 
		while (j-1>=1&&v[j-1]==v[j])--j; 
		as=C[i-j+1][a-j+1]; 
		return cout<<as<<endl,0; 
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    ll x,y,z;
}a[100005];
int n;
ll sum=0;
bool cmp(node p1,node p2)
{
    return p1.z<p2.z;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].x),sum+=a[i].x;
    for(int i=1;i<=n;i++) scanf("%d",&a[i].y),sum-=a[i].y,a[i].z=a[i].x-a[i].y;
    if(sum<0) {printf("-1\n");return 0;}
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].z<=0) continue;
        if(sum>=a[i].z) sum-=a[i].z,a[i].z=0;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        if(a[i].z!=0) ans++;
    printf("%d\n",ans);
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define FORR(i,a,b) for (int i = b - 1; i >= a; --i)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) FORR(i,0,n)

template<class T>
inline void read(T& x) {
  T s = 0, base = 1;
  char c;
  while (!isdigit(c=getchar())) if (c == '-') base = -base;
  while (isdigit(c)) {
    s = s * 10 + (c^48);
    c = getchar();
  }
  x = base * s;
}

int R;

int main() {
  read(R);

  if (R < 1200) printf("ABC\n");
  else if (R < 2800) printf("ARC\n");
  else printf("AGC\n");
  
  return 0;
}


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


def main():
    a, b, c, d = map(int, input().split())
    a += b
    c += d
    if (a < c):
        print('Right')
    elif (a > c):
        print('Left')
    else:
        print('Balanced')


if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include <stdio.h>
int main(void) {
	int n;
    scanf("%d", &n);
    long long int a[n], b[n+1];
  	for(int i=0; i<n+1; i++) b[i] = 0;
  
    for(int i=0; i<n; i++){
    	scanf("%lld", &a[i]);
        //printf("%d\n", a[i]);
        b[i+1] = b[i] + a[i];
    }
    long long int y = 0;
    int m = 1000000007;
    for(int i=0; i<n; i++){
		y += (a[i] * ((b[n] - b[i+1]) % m) % m);
    }
    printf("%lld\n",  y%m);
    return 0;
}

Measured memory_bytes: 4856
D = int(input())
c = [*map(int, input().split())]
s = [0] + [[*map(int, input().split())] for _ in range(D)]
t = [0] + [int(input()) for _ in range(D)]

v = 0
last = [0] * 26
for d in range(1, D+1):
    select = t[d] - 1
    v += s[d][select]
    last[select] = d
    v -= sum(c[i] * (d - last[i]) for i in range(26))
    print(v)


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

using namespace std;

int main(){
	int n;
	cin >> n;
	bool flag = false;
	for(int i = 0;i < 100; i+=4){
		for(int j = 0;j < 100; j+=7){
			if(n == i + j) flag = true;
		}
	}
	if(flag) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define REP(i,b,e) for(ll i=b; i<e; i++)
#define ALL(vec) vec.begin(),vec.end()
#define PRINT(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define SCAN(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 998244353;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

ll modpow(ll a, ll p){
	ll ret = 1;
	while(p){
		if(p&1) ret = ret * a % MOD;
		a = a * a % MOD;
		p >>= 1;
	}
	return ret;
}

int main(){
	int n;
	scanf("%d", &n);
	int a[n];
	REP(i, 0, n) scanf("%d", &a[i]);

	int dis[n] = {};
	for(auto x: a) dis[x]++;

	ll ans = (dis[0]==1 and a[0]==0);
	REP(i, 1, n){
		ans = ans * modpow(dis[i-1], dis[i]) % MOD;
	}
	printf("%ld\n", ans);
	return 0;
}



Measured memory_bytes: 4540
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
struct edge {int to,costa,costb;};

signed main() {
int n;
cin>>n;
if(n==7||n==5||n==3)cout<<"YES";
else cout<<"NO";


return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const ll inf = 1e18;const double INF = 1e12, EPS = 1e-9;

const int MX = 524288;
ll mx[MX], ad[MX];
ll query(int a, int b, int k, int l, int r){
	//dbg(a, b, k, l, r);
	if(b <= l || a >= r) return -inf;
	if(a <= l && r <= b) return mx[k] + ad[k];
	if(ad[k]){
		ad[k * 2 + 1] += ad[k];
		ad[k * 2 + 2] += ad[k];
		mx[k] += ad[k];
		ad[k] = 0;
	}
	ll res = max(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
	mx[k] = max(mx[k * 2 + 1] + ad[k * 2 + 1], mx[k * 2 + 2] + ad[k * 2 + 2]);
	return res;
}
void add(int a, int b, ll x, int k, int l, int r){
	//dbg(a, b, x, k, l, r);
	if(b <= l || a >= r) return;
	if(a <= l && r <= b){
		ad[k] += x;
		return;
	}
	if(ad[k]){
		ad[k * 2 + 1] += ad[k];
		ad[k * 2 + 2] += ad[k];
		mx[k] += ad[k];
		ad[k] = 0;
	}
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);
	mx[k] = max(mx[k * 2 + 1] + ad[k * 2 + 1], mx[k * 2 + 2] + ad[k * 2 + 2]);
}

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int n, m, N; cin >> n >> m;
	for(N = 1; N < n; N *= 2);
	
	vector<tuple<int,int,int>> v;
	rep(i, m){
		int l, r, a; cin >> l >> r >> a;
		v.emplace_back(l - 1, r, a);
	}
	sort(all(v));
	
	for(int i = m - 1, pl = n; i >= 0; i--){
		int l, r, a; tie(l, r, a) = v[i];
		ll right = max(0ll, query(pl, n, 0, 0, N));
		
		//dbg(pl, l, r, a, right);
		
		add(l, min(pl, r), a + right, 0, 0, N);
		if(pl < r) add(pl, r, a, 0, 0, N);
		pl = l;
	}
	cout << max(0ll, query(0, n, 0, 0, N)) << endl;
	return 0;
}

Measured memory_bytes: 8816
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
ll N, K;

vector<int> cross(vector<int> a, vector<int> b) {
    vector<int> ret(N+1);
    ret[0] = -1;
    for(int i = 1; i <= N; i++) {
        ret[i] = a[b[i]];
    }
    return ret;
}

vector<int> inverse(vector<int> a) {
    vector<int> ret(N+1);
    ret[0] = -1;
    for(int i = 1; i <= N; i++) {
        ret[a[i]] = i;
    }
    return ret;
}

vector<int> beki(vector<int> a, int b) {
    vector<int> ret(N+1);
    ret[0] = -1;
    if(b == 0) {
        for(int i = 1; i <= N; i++) ret[i] = i;
        return ret;
    }
    ret = beki(a, b / 2);
    ret = cross(ret, ret);
    if(b % 2 == 1) ret = cross(ret, a);
    return ret;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    vector<int> p(N+1);
    vector<int> q(N+1);
    for(int i = 1; i <= N; i++) cin >> p[i];
    for(int i = 1; i <= N; i++) cin >> q[i];
    vector<int> pInv = inverse(p);
    vector<int> qInv = inverse(q);
    vector<int> initial[7];
    initial[1] = p;
    initial[2] = q;
    initial[3] = cross(q, pInv);
    initial[4] = cross(q, cross(pInv, qInv));
    initial[5] = cross(q, cross(pInv, cross(qInv, cross(p, qInv))));
    initial[6] = cross(q, cross(pInv, cross(qInv, cross(p, cross(p, qInv)))));
    vector<int> S = cross(q, cross(pInv, cross(qInv, p)));
    int ans_index = (K - 1) % 6 + 1;
    int ans_times = (K - ans_index) / 6;
    S = beki(S, ans_times);
    vector<int> ans = cross(S, cross(initial[ans_index], inverse(S)));
    for(int i = 1; i <= N; i++) cout << ans[i] << " ";
    cout << endl;
    return 0;
}


Measured memory_bytes: 27008
n = int(input())
ac,wa,tle,re = 0,0,0,0
for i in range(n):
  s = str(input())
  if s == "AC":
    ac += 1
  elif s == "WA":
    wa += 1
  elif s == "TLE":
    tle += 1
  else:
    re += 1
print("AC x",ac)
print("WA x",wa)
print("TLE x",tle)
print("RE x",re)

Measured memory_bytes: 9060
#include<cstdio>
#include<cstring>
using namespace std;
char s[10005];int n,f[10005][105][2],len,mod=1000000007;
int dfs(int nw,int res,int lim){
    int ans=0,&me=f[nw][res][lim];
    if(f[nw][res][lim]!=-1) return me;
    if(nw==len) return me=(res==0);
    int up=lim?(s[nw]-48):9;
    for(int i=0;i<=up;i++)
    ans=(ans+dfs(nw+1,(res+i)%n,lim&&(i==up)))%mod;
    return me=ans;
}
int main()
{
    scanf("%s%d",s,&n);
    len=strlen(s);
    memset(f,-1,sizeof(f));
    printf("%d",(dfs(0,0,1)-1+mod)%mod);
    return 0;
}

Measured memory_bytes: 9216
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {
  int ans=0,a[5],b[5],B=0;
  for(int i=0;i<5;i++){
    cin>>a[i];
    b[i]=10-a[i]%10;
    if(b[i]==10) b[i]=0;
    ans+=a[i]+b[i];
    B=max(b[i],B);
  }
  cout<<ans-B<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
#define erep1(i,n) for(int i = 1;i<=n;i++)
typedef long long ll;
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vll vector<ll>
#define vbool vector<bool>
#define INF 1000000009


int main(){
  string s;
  cin >> s;
  int ans = INF;
  rep(i,26){
    int count = 0;
    int temp = 0;
    rep(j,s.size()){
      if(s[j] == i+97){
        temp = max(temp,count);
        count = 0;
      }
      else count++;
    }
    temp = max(temp,count);
    ans = min(ans,temp);
  }
  cout << ans << endl;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int N, M, a, b;
    cin >> N >> M;
    vector<pair<int, int>> pairs(N);
    for(int i = 0; i < N; ++i){
        cin >> a >> b;
        pairs[i] = make_pair(a, b);
    }
    sort(pairs.begin(), pairs.end());
    int honsuu = 0;
    int index = 0;
    int tmp = pairs[0].second;
    long long ans = 0;
    while(true){
        if(honsuu == M){
            cout << ans << endl;
            return 0;
        }
        if(tmp == 0){
            ++index;
            tmp = pairs[index].second;
        }
        for(int i = 0; i < pairs[index].second; ++i){
            if(honsuu == M){
                cout << ans << endl;
                return 0;
            }
            ++honsuu;
            --tmp;
            ans += pairs[index].first;
        }
    }

    return 0;
}

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

namespace _175A
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            var threeDays = "RRR";
            const string twoDays = "RR";
            const char oneDay = 'R';
            if (S.Contains(threeDays))
            {
                Console.WriteLine(3);
                return;
            }
            if (S.Contains(twoDays))
            {
                Console.WriteLine(2);
                return;
            }
            if (S.Contains(oneDay))
            {
                Console.WriteLine(1);
                return;
            }
            Console.WriteLine(0);

        }
    }
}


Measured memory_bytes: 25920
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 1000000000000000007LL;
constexpr int inf = 1000000007;

// 最大公約数
template <typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

int main() {
    ll a, b; cin >> a >> b;
    cout << a * b / gcd(a, b) << endl;
    return 0;
}

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

typedef long long ll;
typedef vector<ll> vint;
typedef vector< vector<ll> > vvint;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define ALL(obj) (obj).begin(), (obj).end()
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 (b<a) { a=b; return 1; } return 0; }

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

vector< bool > prime_table(int n) {
  vector< bool > prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}


int main() {
    cout<<fixed<<setprecision(10);

    ll n; cin>>n;
    vint a(n); rep(i,n) cin>>a[i];

    sort(ALL(a));
    if(a.back() == 1){
        puts("pairwise coprime");
        return 0;
    }

    auto pt = prime_table(1000000+100);

    vint cnt(1000000+100, 0);
    for(auto e:a) cnt[e]++;

    bool f = false;

    repf(x, 2, 1000000+100){
        if(!pt[x]) continue;
        ll i = 1;
        ll tmp = 0;
        while(x*i < 1000000+100){
            if(( cnt[x*i] > 1 ) or ( tmp > 0 and cnt[x*i] > 0 )) {
                f = true;
                break;
            }
            tmp += cnt[x*i];
            i++;
        }

        if(f) break;
    }

    if(f){
        ll g = a[0];
        repf(i,1,n) g = gcd(g, a[i]);
        if(g == 1) puts("setwise coprime");
        else puts("not coprime");

    }else{
        puts("pairwise coprime");
    }


    return 0;

}

Measured memory_bytes: 19028
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define ALL(a) begin(a),end(a)
#define ifnot(a) if(not (a))
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

// #define int ll
#ifdef _MSC_VER
const bool test = true;
#else 
const bool test = false;
#endif

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................
const int MAX = (int)2e5 + 5;

int main() {
	string s;
	getline(cin, s);
	stringstream ss(s);
	map<string, int> m;
	string s2;
	string max_size_s;
	// dump(max_size_s.size());
	while (ss >> s2) {
		m[s2]++;
		if (s2.size() > max_size_s.size()) {
			max_size_s = s2;
		}
	}
	string most_fre_s;
	int most_fre_cnt = 0;
	for (auto p : m) {
		if (p.second > most_fre_cnt) {
			most_fre_s = p.first;
			most_fre_cnt = p.second;
		}
	}
	cout << most_fre_s << " " << max_size_s << endl;
	return 0;
}

Measured memory_bytes: 3024
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MOD = (int)1e9 + 7;
int INF = (int)2e18;
// Comment out below and program paste

// #include "UnionFind.hpp"
// #include "power.hpp"

signed main() {
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> sum(N + 1, 0);
    for (int i = 1; i < N; i++) {
        if (S[i - 1] == 'A' && S[i] == 'C') {
            sum[i + 1] = sum[i] + 1;
        } else sum[i + 1] = sum[i];
    }
    // cout << " " << S << endl;
    // for (int i = 0; i < sum.size(); i++) cout << sum[i];
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        cout << sum[r] - sum[l] << endl;
    }
}


Measured memory_bytes: 1792
#include <stdio.h>

long long int members_number[4001];
int funami;

void reset(void) {
  int i;
  funami = 0;
  for(i = 0; i < 4001; i++ ) {
    members_number[i] = 0;
  }
}

void check(long long int staff, long long int price, long long int number) {
  int flag = 0;
  if(members_number[staff] < 1000000) {
    members_number[staff] += price * number;
    if(members_number[staff] >= 1000000) {
      printf("%lld\n",staff);
      funami = 1;
    }
  }
}

void scan_result(long int n) {
  long long int staff, number, i, price;
  for(i = 0; i < n; i++ ) {
    scanf("%lld %lld %lld",&staff, &price, &number);
    check(staff, price, number);
  }
}

int main(void) {
  long int n;
  scanf("%ld",&n);
  while(n) {
    reset();
    scan_result(n);
    if(!funami) {
      puts("NA");
    }
    scanf("%ld",&n);
  }
  return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m;
string ss[10];
main()
{
	while(cin>>n>>m,n)
	{
		for(int i=0;i<n;i++)cin>>ss[i];
		vector<int>R,C,S;
		for(int r=1;r<21;r++)for(int c=1;c<21;c++)for(int s=1;s<21;s++)
		{
			bool flag=1;
			int cr=0,cc=0,cs=0;
			for(int i=0;i<n;i++)
			{
				int cnt=0;
				for(int j=0;j<ss[i].size()&&ss[i][j]=='.';j++)cnt++;
				if(cr*r+cc*c+cs*s!=cnt)
				{
					flag=0;
					break;
				}
				for(int j=0;j<ss[i].size();j++)
				{
					if(ss[i][j]=='(')cr++;
					else if(ss[i][j]==')')cr--;
					else if(ss[i][j]=='{')cc++;
					else if(ss[i][j]=='}')cc--;
					else if(ss[i][j]=='[')cs++;
					else if(ss[i][j]==']')cs--;
				}
			}
			if(flag)
			{
				R.push_back(r);
				C.push_back(c);
				S.push_back(s);
			}
		}
		vector<int>ans;
		int cr=0,cc=0,cs=0;
		for(;m--;)
		{
			string t;cin>>t;
			int cnt=-1;
			for(int j=0;j<R.size();j++)
			{
				int now=cr*R[j]+cc*C[j]+cs*S[j];
				if(cnt<0)cnt=now;
				else
				{
					if(cnt!=now)cnt=114514;
				}
			}
			if(cnt==114514)ans.push_back(-1);
			else ans.push_back(cnt);
			for(int j=0;j<t.size();j++)
			{
				if(t[j]=='(')cr++;
				else if(t[j]==')')cr--;
				else if(t[j]=='{')cc++;
				else if(t[j]=='}')cc--;
				else if(t[j]=='[')cs++;
				else if(t[j]==']')cs--;
			}
		}
		for(int i=0;i<ans.size();i++)cout<<ans[i]<<(i+1==ans.size()?"\n":" ");
	}
}



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

int main() {
  char C;
  cin >> C;

    if (C == 'a' || C == 'i' || C == 'u' || C == 'e' || C =='o') {
       cout << "vowel" << endl;
    }	else {
      cout << "consonant" << endl;
    }

}


Measured memory_bytes: 256
input = gets()
x = input.chomp.to_i

# input = readlines()
# meta = input.shift.chomp.split("\s").map{|x| x.to_i}

if x >= 1800
  puts '1'
elsif x >= 1600
  puts '2'
elsif x >= 1400
  puts '3'
elsif x >= 1200
  puts '4'
elsif x >= 1000
  puts '5'
elsif x >= 800
  puts '6'
elsif x >= 600
  puts '7'
else
  puts '8'
end


Measured memory_bytes: 14408
k,n = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

rev = a[0] + k - a[n-1]
dif = [a[i]-a[i-1] for i in range(1,n)]
dif.append(rev)
print(sum(dif)-max(dif))

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

int main() {
  int n,m;
  cin >> n >> m;
  vector<string>a(n);
  vector<string>b(n);
  rep(i,n) cin >> a[i];
  rep(i,m) cin >> b[i];
  rep(i,n-m+1){
    rep(j,n-m+1){
      rep(k,m){
        string sub = a[i+k].substr(j,m);
        if(sub != b[k]) break;
        if(k == m-1){
          cout << "Yes" << endl;
          return 0;
        }
      }
    }
  }
  cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <type_traits>
#include <map>

using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    vector<pair<int, int>> r(n), b(n);
    for(int i = 0; i < n; i++){
        cin >> r[i].first;
        cin >> r[i].second;
    }
    for(int i = 0; i < n; i++){
        cin >> b[i].first;
        cin >> b[i].second;
    }
    sort(r.begin(), r.end());
    sort(b.begin(), b.end());


    int ans = 0;
    for(int i = 0; i < n; i++){
        int m = -1;
        int mIndex = -1;
        for(int j = 0; j < n; j++){
            if(r[j].first < b[i].first && r[j].second < b[i].second){
                if(r[j].second > m){
                    m = r[j].second;
                    mIndex = j;
                }
            }
        }
        if(mIndex != -1){
            r[mIndex].first = 999;
            r[mIndex].second = 999;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>

#define int long long
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPS(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)

using namespace std;

string s;

string MAX_STRING = "zyxwvutsrqponmlkjihgfedcba";

signed main()
{
    cin >> s;

    if (s == MAX_STRING)
    {
        cout << -1 << endl;
        return 0;
    }

    map<char, int> smap;
    REP(i, s.size()) smap[s[i]] = i;

    if (s.size() < 26)
    {
        char c;
        for (c = 'a'; c <= 'z'; ++c)
        {
            if (smap.find(c) == smap.end()) break;
        }
        s += c;
        cout << s << endl;

        return 0;
    }

    for (int i = s.size()-2; i > 0; --i)
    {
        char nc = s[i] + 1;
        while (nc <= 'z')
        {
            auto find = smap.find(nc);
            if (i < find->second)
            {
                string ans = s.substr(0, i);
                ans += nc;
                cout << ans << endl;
                return 0;
            }
            ++nc;
        }
    }

    int zidx = smap['z'];
    char nc = s[zidx - 1] + 1;
    while (nc < 'z')
    {
        auto find = smap.find(nc);
        if (find == smap.end()) break;
        if (zidx - 1 < find->second) break;
        ++nc;
    }
    string ans = s.substr(0, zidx-1);
    ans += nc;
    cout << ans << endl;

    return 0;
}

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

int dp[3000+1][3000+1];

int main()
{
	string s,t,ans;
	cin >> s >> t;
	fill(dp[0],dp[3000+1],0);
	for(int i=0;i<s.size();++i)
	{
		int foo = 0;
		for(int j=0;j<t.size();++j)
		{
			if(s[i]==t[j])
			{
				dp[i+1][j+1]=dp[i][j]+1;
				
			}
			else
			{
				if(dp[i][j+1]>dp[i+1][j])
				{
					dp[i+1][j+1]=dp[i][j+1];
				}
				else
				{
					dp[i+1][j+1]=dp[i+1][j];
				}
			}
		}
	}

	int sl = s.size();
	int tl = t.size();
	int l = dp[sl][tl];
	
	while(l>0)
	{
		
		if(s[sl-1]==t[tl-1])
		{
			ans.push_back(s[sl-1]);
			sl--;
			tl--;
			l--;
			
			
		}
		else if(dp[sl][tl]==dp[sl-1][tl])
		{
			sl--;
		}
		else
		{
			tl--;
		}

	
		
	}
	reverse(ALL(ans));
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 35584
using System;
using System.Collections.Generic;
using System.Text;

class Program
{
	static void Main(string[] args)
	{
		string[] input = Read();
		int h = int.Parse(input[0]);
		int w = int.Parse(input[1]);
		int k = int.Parse(input[2]);
		char[][] color = new char[h][];
		for(int i=0; i<h; i++)
		{
			color[i] = Read()[0].ToCharArray();
		}
		int max = 1 << (h+w);
		int count = 0;
		for(int i=0; i<max; i++)
		{
			bool[] act = new bool[h+w];
			int black = 0;
			for(int j=0; j<h+w; j++)
			{
				act[j] = (i & (1 << j)) != 0;
			}
			for(int row=0; row<h; row++)
			{
				for(int col=0; col<w; col++)
				{
					if(color[row][col]=='#' && !act[row] && !act[h+col]) black++;
				}
			}
			if(black == k) count++;
		}
		Write(count);
	}

	static string[] Read()
	{
		return Console.ReadLine().Split(' ');
	}

	static void Write(object o)
	{
		Console.WriteLine(o.ToString());
	}
}



Measured memory_bytes: 27700
//abc142_d.cpp
//Sat Sep 28 20:50:00 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	vector<ll> yakusu;
	yakusu.push_back(1);

	ll x = 2;
	ll temp = a;
	while (a>=x*x){
		if (temp%x==0){
			if (b%x==0){
				yakusu.push_back(x);
			}
			temp = temp/x;
		}else{
			x++;
		}
	}
	if (b%temp==0){
		yakusu.push_back(temp);
	}

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

	ll prev = 0;
	ll ans = 0;
	for (int i=0;i<yakusu.size();i++){
		if (yakusu[i]!=prev){
			ans++;
		}
		prev = yakusu[i];
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

// This file is a "Hello, world!" in Java language by OpenJDK for wandbox.

class Main
{
	public static void main(String[] args)
	{
		new Main().run();
	}

	void run(){
		Scanner sc=new Scanner(System.in);
		char c=sc.next().toCharArray()[0];
		System.out.println((char)(c+1));
	}
	
	void tr(Object...o){System.out.println(Arrays.deepToString(o));}
}
// OpenJDK reference:
//   http://openjdk.java.net/

// Java language references:
//   http://docs.oracle.com/javase
	

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

#define ALL(a) (a).begin(), (a).end()
#define llong long long

using namespace std;

signed main(){
	string str; cin >> str;
	int a = stoi(str.substr(0,2).c_str());
	int b = stoi(str.substr(2,2).c_str());
	bool flag = false;
	if(b < a){
		flag = true;
		swap(a,b);
	}
	if(a == 0 && b == 0)cout << "NA" << endl;
	else if(a == 0 && b < 13){
		if(flag) cout << "MMYY" << endl;
		else cout << "YYMM" << endl;
	}
	else if(a == 0 && b >= 13) cout << "NA" << endl;
	else if(a < 13 && b < 13)cout << "AMBIGUOUS" << endl;
	else if(a < 13){
		if(flag) cout << "YYMM" << endl;
		else cout << "MMYY" << endl;
	}
	else cout << "NA" << endl;

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
void read (int &x) {
    char ch = getchar(); x = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}
struct mat {
    int a[21][21];
    /*
    rep(i,0,21){
        rep(j,0,21){
            mtx[i][j] = mtx2[i][j] = 0;
            if(i<10){
                if((i^1)==j){  //成对
                    mtx2[i][j] = 1;
                }else if(i%2==0&&i<j&&(j%2==1||10<=j)){
                    mtx2[i][j] = 1;
                }
            }else{
                if(i<=j){
                    mtx2[i][j] = 1;
                }
            }
        }
    }*/
    void in() {
        for (int i = 0; i < 21; ++i)
            for (int j = 0; j < 21; ++j) {
                if (i < 10) {       //前5块  0偶1奇  2偶3奇
                    a[j][i] = ((i ^ 1) == j) | (i % 2 && i >= j && (j >= 10 || j % 2 == 0));
                } else a[j][i] = (i >= j && (j >= 10 || j % 2 == 0));
            }
        // for (int i = 0; i < 21; ++i) {
        //     for (int j = 0; j < 21; ++j) printf ("%d ", a[i][j]); puts ("");
        // }
    }
    void clear() {
        for (int i = 0; i < 21; ++i)
            for (int j = 0; j < 21; ++j) a[i][j] = 0;
    }
    mat operator * (const mat &x) const {
        mat p; p.clear();
        for (int i = 0; i < 21; ++i)
            for (int j = 0; j < 21; ++j)
                for (int k = 0; k < 21; ++k)
                    p.a[i][j] = (p.a[i][j] + a[i][k] * x.a[k][j]) % mod;
        return p;
    }
} T, K;
void Pow (int y) {
    for (; y; y >>= 1, K = K * K) if (y & 1) T = T * K;
}
signed main() {
    int t; read (t);
    while (t--) {
        int n; read (n);
        T.clear(), K.clear();
        if (n < 5) { puts ("0"); continue; }
        T.a[0][0] = 1, K.in(); Pow (n - 4);
        printf ("%lld\n", T.a[0][20]);
    } return 0;
}


Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll one = 1;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    ll N, X, M;
    cin >> N >> X >> M;
    set<ll> s;
    s.insert(X);
    
    vector<ll> cyc(M+1);
    cyc[0] = X;
    ll tmp = X;
    ll ind = 1;
    while(true){
        tmp = tmp * tmp % M;
        cyc[ind] = tmp;
        if(s.count(tmp)){
            break;
        }
        else{
            s.insert(tmp);
        }
        ind++;
    }

    ll st, en;
    en = ind;
    for (int i = 0; i < en; i++) {
        if(cyc[i] == tmp){
            st = i;
            break;
        }
    }
    ll len = en - st;
    ll ans = 0;
    for (ll i = 0; i < st; i++) {
        ans += cyc[i];
    }
    ll cy = 0;
    for (ll i = st; i < en; i++) {
        cy += cyc[i];
    }
    ans += cy * ((N - st) / len);
    ll p = (N - st) % len;
    for (ll i = st; i < st+p; i++) {
        ans += cyc[i];
    }
    printf("%lld\n", ans);


}

Measured memory_bytes: 6340
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
int main()
{
	string s,t;
	cin>>s>>t;
	int count=0;
	for(int i=0;i<3;i++)
	{
		if(s[i]==t[i])
		{
			count++;
		}
		
		
	}
	cout<<count;
	
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

int main() {
	int N;
	while (~scanf("%d", &N)) {
		vector<vector<int> > A(N, vector<int>(N));
		for (int i = 0; i < N; ++ i) for (int j = 0; j < N; ++ j)
			scanf("%d", &A[i][j]);

		bool ok = true;
		rep(k, N) rep(i, N) rep(j, N)
			ok &= A[i][j] <= A[i][k] + A[k][j];
		if (!ok) {
			puts("-1");
			continue;
		}
		vector<pair<int, pii>> edges;
		rep(i, N) reu(j, i + 1, N)
			edges.emplace_back(A[i][j], make_pair(i, j));
		sort(edges.begin(), edges.end());
		vector<vi> B(N, vi(N, INF));
		rep(i, N)
			B[i][i] = 0;
		ll ans = 0;
		for (auto e : edges) {
			int i, j, w = e.first;
			tie(i, j) = e.second;
			rep(k, N) {
				amin(B[i][j], B[i][k] + B[k][j]);
				B[j][i] = B[i][j];
			}
			if (B[i][j] > A[i][j]) {
				ans += w;
				B[i][j] = B[j][i] = w;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}


Measured memory_bytes: 1532
import sys
input = sys.stdin.readline
lr, lc, rr, rc = map(int, input().split())
mod = 10 ** 9 + 7
class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(rr + rc + 1, mod)
res = 0
for i in range(lr, rr + 1):
  res += f.combi(i + rc + 1, i + 1)
  res %= mod
for i in range(lr, rr + 1):
  res -= f.combi(i + lc, i + 1)
  res %= mod
print(res)

Measured memory_bytes: 135424