akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = 10000000;
const long long INFL = (1LL<<50);
const double PI = atan(1)*4;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}


int main() {
    int n;cin>>n;
    string s; cin>>s;
    int cl =0;
    rep(i,s.size()){
        if(s[i]=='('){
            cl++;
        }
        if(s[i]==')' && cl>0){
            cl--;
        }
    }
    int cr =0;
    rep(i,s.size()){
        if(s[(s.size()-1)-i]==')'){
            cr++;
        }
        if(s[(s.size()-1)-i]=='(' && cr>0){
            cr--;
        }
    }
    rep(i,cr)cout<<"(";
    cout<<s;
    rep(i,cl)cout<<")";
    cout<<endl;
    return 0;
}












Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
sum_arai = sum(A)
sum_sunuke = 0
dif = 0

ans = 10 ** 15

for i in range(N - 1):
    sum_arai -= A[i]
    sum_sunuke += A[i]
    dif = abs(sum_arai - sum_sunuke)
    if dif <= ans:
        ans = dif

print(ans)

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

int main()
{
  int H, N;
  cin >> H >> N;
  pair<int, int> magics[N];
  for (int i = 0; i < N; i++)
  {
    int A, B;
    cin >> A >> B;
    magics[i] = make_pair(A, B);
  }
  sort(magics, magics + N);
  long min_cost[10001];
  for (int i = 0; i <= 10000; i++)
  {
    min_cost[i] = LONG_MAX;
  }
  min_cost[0] = 0;
  for (int i = N - 1; i >= 0; i--)
  {
    long attack = magics[i].first;
    long cost = magics[i].second;
    for (int j = 0; j <= 10000; j++)
    {
      min_cost[j] = min(min_cost[j], (j - attack >= 0 ? min_cost[j - attack] : 0) + cost);
    }
  }
  cout << min_cost[H] << endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<string>
#include<bitset>
#include<cfloat>
#include<iomanip>
#include<numeric>

//#define int long long
#define repi(i,start,end) for(int (i)=(start),TemPNuM=(int)(end);(i)<TemPNuM;++(i))
#define rep(i,end) repi((i),0,(end))
#define rfor(x,v) for(auto& (x) : (v))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fsort(v,lambda) sort(all((v)),(lambda))
#define vin(v) rep(i,(v).size())cin >> (v)[i];
#define vpin(v) rep(i,(v).size())cin>>v[i].first>>v[i].second

using namespace std;
using ll =  long long;
using pint =  pair<int,int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vpint = vector<pint>;

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; }
template<class T>void put_double(T a){if(cout.precision()!=12)cout<<setprecision(12);cout<<a<<endl;}
template<class T>void print(T a){cout << a << endl;}
//lambda: [](int x, int y){return x<y;}

signed main(void) {
    int n; cin >> n;
    repi(x, 1, 50000) {
        int d = x * 1.08;
        if(d == n) {
            print(x);
            return 0;
        }
    }
    print(":(");

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long ll;
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;}

const ll INF = 1000000000;
const int MAX_N = 1000;

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

    for(int i = 0; i < n; i++){
        if(x[i] % 2 == 1) continue;
        if(x[i] % 3 == 0 || x[i] % 5 == 0) continue;
        cout << "DENIED" << endl;
        return 0;
    }
    
    cout << "APPROVED" << endl;


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
//map<pair<long long int,long long int>,long long int>mapa;
//pair<ll,ll>v[200005];
ll sum[200005];
//priority_queue<ll>pq;
class Myfirst{
private:
    string *name;       ll *age;
    public:
        ll gcd(ll a ,ll b)
        {   if(b==0) return a;  a%=b;   return gcd(b,a);    }
        ll exte_gcd(ll a,ll b,ll& x,ll& y)
        {
            if(b==0)
            {   x=1; y=0;   return a;   }
            ll x1,y1;             ll d=exte_gcd(b,a%b,x1,y1);
            x=y1;                 y=x1-y1*(a/b);  return d;
        }
        ll powe(ll d,ll s)
        {
            if(s==1) return d;      else if(s==0) return 1;
            else
            {   ll u,v=d;            for(u=1;u<s;u++)    d=d*v;
                return d;
            }
        }
        ll count_divisors(ll b)
        {
                ll i,count=0,n=1;
                for(i=2;i*i<=b;i++)
                {
                    count=0;
                    if(b%i==0)
                    {
                        while(b%i==0)
                        {
                            b=b/i;      count++;
                        }
                        n=n*(count+1);
                    }
                }
                if(b>1) n=2*n;
            return n;
        }
        ll bigmod(ll a,ll b, ll mod)
        {
            if(b==0)
                return 1;
            ll x=bigmod(a,b/2,mod);         x=(x*x)%mod;
            if(b%2) x=(x*a)%mod;
                return x;
        }
        ll phi(ll n)
        {
            double result=n;
            for (ll p=2;p*p<=n;++p){
                if (n%p==0){
                    while(n%p==0)       n/=p;
                    result*=(1.0-(1.0/(double)p));
                }
            }
            if(n>1)
                result*=(1.0-(1.0/(double)n));
            return (ll)result;
        }

        void solve()
        {
            ll n,i,m=1e9+7,j,x,ans=0,s=0;
            cin>>n;
            ll a[n+5];
            cin>>a[1];
            for(i=2;i<=n;i++)
            {
                cin>>a[i];
                sum[i]=(sum[i-1]+a[i]);
            }
            //cout<<sum[n]<<endl;
            for(i=2;i<=n;i++)
            {
                ans=(sum[n]-sum[i-1])%m;
                ans=(ans*a[i-1])%m;
                ans=ans%m;
                s=(s+ans)%m;
                //cout<<s<<endl;
            }
            cout<<s%m;



        }



};
int main()
{
    Myfirst *prg = new Myfirst();
    prg->solve();
}



Measured memory_bytes: 6724
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000005;
const int mod=998244353;
int n;
int a[N],z[N];
bool check(int x){
    for(int i=1;i<=2*n-1;i++)
        z[i]=a[i]>=x;
    for(int i=0;i<n-1;i++){
        if(z[n-i]==z[n-i-1])
            return z[n-i];
        if(z[n+i]==z[n+i+1])
            return z[n+i];
    }
    return z[1];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=2*n-1;i++)
        scanf("%d",&a[i]);
    int l=1,r=2*n;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    printf("%d\n",l);
}


Measured memory_bytes: 4992
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100005
#define maxm 200005
typedef long long ll;
typedef pair<ll,int> pii;
#define mp make_pair
#define ff first
#define ss second
const int mod=1e9+7;

int n,m,s,t;
bool can[maxn];

inline int read(){
	int x=0,f=1; char ch=getchar();
	for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

struct graph{
	bool vis[maxn]; ll dis[maxn];
	int tot,now[maxn],pre[maxm*2],son[maxm*2],val[maxm*2],f[maxn]; pii heap[maxn];
	void add(int a,int b,int c){son[++tot]=b,pre[tot]=now[a],now[a]=tot,val[tot]=c;}
	void link(int a,int b,int c){add(a,b,c),add(b,a,c);}
	void dijkstra(int x){
		memset(dis,63,sizeof(dis)),dis[x]=0,f[x]=1;
		int top=0; heap[++top]=mp(dis[x],x),make_heap(heap+1,heap+top+1,greater<pii>());
		while (top){
			pii x=heap[1]; pop_heap(heap+1,heap+top+1,greater<pii>()),--top; ll d=x.ff; int id=x.ss,v=f[id];
			if (vis[id]) continue; vis[id]=1;
			for (int p=now[id];p;p=pre[p]){
				if (dis[son[p]]>d+val[p]){
					f[son[p]]=v;
					heap[++top]=mp(dis[son[p]]=d+val[p],son[p]);
					push_heap(heap+1,heap+top+1,greater<pii>());
				}
				else if (dis[son[p]]==d+val[p]) f[son[p]]=(f[son[p]]+v)%mod;
			}
		}
	}
}g1,g2;

struct edge{int x,y,z;}e[maxm];

int main(){
	n=read(),m=read(),s=read(),t=read();
	for (int i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		e[i]=(edge){x,y,z};
		g1.link(x,y,z),g2.link(x,y,z);
	}
	g1.dijkstra(s),g2.dijkstra(t);
	int ans=1ll*g1.f[t]*g1.f[t]%mod; ll all=g1.dis[t];
	if (~all&1){
		for (int i=1;i<=n;i++)
			if (i!=s&&i!=t&&g1.dis[i]+g2.dis[i]==all&&g1.dis[i]==g2.dis[i])
				ans=(ans-1ll*g1.f[i]*g2.f[i]%mod*g1.f[i]%mod*g2.f[i])%mod;
	}
	for (int i=1;i<=m;i++){
		int x=e[i].x,y=e[i].y,z=e[i].z;
		ll d1=g1.dis[x]+g2.dis[y]+z,d2=g1.dis[y]+g2.dis[x]+z;
		if (d1==all&&max(g1.dis[x],g2.dis[y])*2<all) ans=(ans-1ll*g1.f[x]*g2.f[y]%mod*g1.f[x]%mod*g2.f[y])%mod;
		if (d2==all&&max(g2.dis[x],g1.dis[y])*2<all) ans=(ans-1ll*g2.f[x]*g1.f[y]%mod*g2.f[x]%mod*g1.f[y])%mod;
	}
	printf("%d\n",(ans+mod)%mod);
	return 0;
}


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

int main(){
    int N,x=1;
    cin >> N;
    vector<int>v(N);
    for (int i = 0; i < N; i++){
        cin >> v.at(i);
    }
    vector<int>kudakanai;
    for (int i = 0; i < N; i++){
        if (v.at(i) == x){
            kudakanai.push_back(1);
            x++;
        }
    }
    if (kudakanai.size() == 0){
        cout << "-1" << "\n";
        return 0;
    }
    cout << v.size()-kudakanai.size() << "\n";
}

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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

ll n,a,b;

int main(){
	cin.sync_with_stdio(false);
  cin>>n>>a>>b;
  if(a>b){
    cout<<0<<endl;
    return 0;
  }
  if(n==1&&a!=b){
    cout<<0<<endl;
    return 0;
  }
  cout<<((n-1)*b+a)-((n-1)*a+b)+1<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= (int)end; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M, V, P;
    cin >> N >> M >> V >> P;
    vector<ll> A(N);
    for (auto& a : A) {
        cin >> a;
    }
    sort(all(A));
    reverse(all(A));
    int l = 0, r = N + 1;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (mid <= P) {
            l = mid;
            continue;
        }
        if (A[mid - 1] + M < A[P - 1]) {
            r = mid;
            continue;
        }
        ll sum = M * (P + N - mid);
        rep(i, P - 1, mid - 1) {
            sum += min(M, A[mid - 1] + M - A[i]);
        }
        if (sum >= M * V) {
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << l << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int correct[50];
  int counter=0;
  int N;
  
  cin >> N;
  
  for(int i=0;i<50;i++){
    correct[i]=i+1;
  }
  
  int l;
  int step=0;
  while(cin>>l) {
    if(l != correct[step])counter+=1;
    step+=1;
  }
  
  if(counter<=2)cout << "YES" << endl;
  else cout << "NO" << endl;
}

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

using namespace std;

typedef long long ll;

struct pos
{
    double x,y;
} p[9];

double sum;

int vis[9],n,num;

double distance(pos a,pos b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void dfs(int k,double ans,int po)
{
    if(k==n)
    {
        num++;
        sum+=ans;
    }
    else if(k==0)
    {
        int i;
        for(i=1; i<=n; i++)
        {
            vis[i]=1;
            dfs(1,ans,i);
            vis[i]=0;
        }
    }
    else
    {
        int i;
        for(i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                vis[i]=1;
                dfs(k+1,ans+distance(p[po],p[i]),i);
                vis[i]=0;
            }
        }
    }
}

int main()
{
    while(cin>>n)
    {
        memset(vis,0,sizeof(vis));
        sum=0;
        num=0;
        int i;
        for(i=1; i<=n; i++)
            cin>>p[i].x>>p[i].y;
        dfs(0,0,0);
        printf("%f\n",sum/num);
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

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

    int n, m;
    cin >> n >> m;
    int ans = 0;
    for (int i = 1; i * i <= m; i++)
    {
        if (m % i == 0)
        {
            int x = i, y = m / i;
            if (m / x >= n)
                ans = max(ans, x);
            if (m / y >= n)
                ans = max(ans, y);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
from collections import deque

N,K = map(int, input().split())
a_list = list(map(int, input().split()))

d = deque(a_list[:K])
for i in range(K, N):
    in_a = a_list[i]
    out_a = d.popleft()
    d.append(in_a)
    if in_a > out_a:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 32508
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(){
  int n,wlen;
  scanf("%d",&n);
  char w[n][11];
  for(int i=0;i<n;i++){
    scanf("%s",w[i]);
  }
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      if(strcmp(w[i],w[j])==0){
        printf("No");
        return 0;
      }
    }
  }
  for(int i=1;i<n;i++){
      if(w[i-1][strlen(w[i-1])-1]!=w[i][0]){
          printf("No");
          return 0;
      }
  }
  printf("Yes");
  return 0;
}


Measured memory_bytes: 128
#include <iostream>

using namespace std;

int n,test_count[4];
char test[5]={"AWTR"},s[4];

int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>s;
        for (int j=0; j<5; j++)
        {
            if (s[0]==test[j])
                test_count[j]++;
        }
    }
    cout<<"AC x "<<test_count[0]<<'\n';
    cout<<"WA x "<<test_count[1]<<'\n';
    cout<<"TLE x "<<test_count[2]<<'\n';
    cout<<"RE x "<<test_count[3]<<'\n';
    return 0;
}

Measured memory_bytes: 3612
#include<stdio.h>

int main(){
	while(1){
		int n,m;
		char ord;
		int d;
		int i,j;
		int px=10;
		int py=10;
		int ans=0;
		bool isj[21][21];
		scanf("%d",&n);
		if(n==0)return 0;
		for(i=0;i<21;i++)for(j=0;j<21;j++)isj[i][j]=false;
		for(i=0;i<n;i++){
			int x,y;
			scanf("%d %d",&x,&y);
			isj[x][y]=true;
		}
		scanf("%d",&m);
		for(i=0;i<m;i++){
			scanf(" %c %d",&ord,&d);
			for(j=0;j<d;j++){
				if(ord=='N')py++;
				if(ord=='E')px++;
				if(ord=='S')py--;
				if(ord=='W')px--;
				if(isj[px][py]){
					ans++;
					isj[px][py]=false;
				}
			}
		}
		if(ans==n)printf("Yes\n");
		else printf("No\n");
	}
}
			

Measured memory_bytes: 1012
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<climits>
#include<cstring>
#include<iomanip>
#include<string>
#include<bitset>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<algorithm>
#include<functional>
#include<chrono>
#include<random>

#define y0 asdahsdlkahsdad
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define taskname "B"
#define BeztDonkey

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

const int max4K = 1000 << 2;

static int s[max4K][max4K], n, k, k2, k4, x, y;
char c;

inline int Sum(int x, int y, int u, int v)
{
    int res = s[u][v];
    if (x > 0) res -= s[x - 1][v];
    if (y > 0) res -= s[u][y - 1];
    if (x > 0 && y > 0) res += s[x - 1][y - 1];
    return res;
}

int main()
{
    #ifdef BeztDonkey
    auto start = chrono::steady_clock::now();
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);

    cin >> n >> k;
    k2 = k << 1; k4 = k << 2;
    while (n--)
    {
        cin >> x >> y >> c;
        if (c == 'W') y += k;
        ++s[x %= k2][y %= k2];
        ++s[x + k2][y];
        ++s[x][y + k2];
        ++s[x + k2][y + k2];
    }
    int ans = 0;
    //for (int i = 0; i < k4; ++i)
        //for (int j = 0; j < k4; ++j) cout << s[i][j] << ' ', s[i][j] = s[i % k2][j % k2], cout << s[i][j] << '\n';
    for (int i = 0; i < k4; ++i)
        for (int j = 0; j < k4; ++j)
        {
            auto &sij = s[i][j];
            if (i > 0) sij += s[i - 1][j];
            if (j > 0) sij += s[i][j - 1];
            if (i > 0 && j > 0) sij -= s[i - 1][j - 1];
        }
    for (int i = 0; i < k2; ++i)
        for (int j = 0; j < k2; ++j)
            ans = max(ans, Sum(i, j, i + k - 1, j + k - 1)
                         + Sum(i + k, j + k, i + k2 - 1, j + k2 - 1));
    cout << ans;

    #ifdef BeztDonkey
    auto end = chrono::steady_clock::now();
    cerr << "In milliseconds : "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count();
    cerr << '\n' << "In seconds : "
         << chrono::duration_cast<chrono::seconds>(end - start).count() << '\n';
    #endif
    return 0;

}


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

int main()
{
    int N, M, K;
    cin >> N >> M;
    int Ai;
    vector<int> A(M, 0);
    for(int i=0;i<N;i++){
        cin >> K;
        for(int j=0;j<K;j++){
            cin >> Ai;
            A[Ai-1]++;
        }
    }
    int res = 0;
    for(int i=0;i<M;i++){
        if(A[i]==N) res++;
    }
    cout<<res<<endl;

    return 0;
}

Measured memory_bytes: 256
use proconio::input;
use std::collections::HashMap;

mod X{
    pub struct UnionFind {
        n: usize,
        par: Vec<usize>,
        rank: Vec<usize>,
        sz: Vec<usize>,
    }

    impl UnionFind {

        pub fn new(n:usize) -> UnionFind {
            UnionFind{
                n:n,
                par:(0..n).map(|i|i).collect(),
                rank:vec![0;n],
                sz:vec![1;n],
            }
        }

        pub fn size(&self) -> usize {self.n}

        pub fn size_of(&mut self,v:usize) -> usize { 
            let v = self.find(v);
            self.sz[v]
        }
        pub fn find(&mut self,v:usize) -> usize {
            if self.par[v] == v {
                v
            }
            else {
                let p = self.find(self.par[v]);
                self.par[v] = p;
                p
            }
        }


        pub fn unite(&mut self,a:usize,b:usize){
            let a = self.find(a);
            let b = self.find(b);
            if a==b {
                return
            }
            else {
                if self.rank[a]<self.rank[b] {
                    self.sz[b]+=self.sz[a];
                    self.par[a] = b;
                }
                else {
                    if self.rank[a]==self.rank[b] {
                        self.rank[a] += 1;
                    }
                    self.sz[a]+=self.sz[b];
                    self.par[b] = a;
                }
            }
        }

        pub fn is_same(&mut self,a:usize,b:usize) -> bool {
            self.find(a)==self.find(b)
        }

    }
}

use X::UnionFind;

fn main() {
    input!{
        n:usize,
        a:[i64;n],
        q:usize,
        bc:[(i64,i64);q]
    };

    let mut uf = UnionFind::new(n);
    let mut mp:HashMap<i64,usize> = HashMap::new();

    for (i,x) in a.iter().enumerate() {
        if mp.contains_key(x) {
            uf.unite(i,mp[x]);
        }
        else {
            mp.insert(*x,i);
        }
    }

    let mut sum:i64 = a.iter().sum();

    for (b,c) in bc {
        if !mp.contains_key(&b) {
            println!("{}",sum);
            continue;
        }

        let vb = mp[&b];
        sum -= (uf.size_of(vb) as i64)*b;
        if mp.contains_key(&c) {
            let vc = mp[&c];
            if !uf.is_same(vb,vc) {
                sum-=(uf.size_of(vc) as i64)*c;
                uf.unite(vb,vc);
            }
        }
        mp.remove(&b);
        mp.insert(c,vb);
        sum+=(uf.size_of(vb) as i64)*c;
        println!("{}",sum);
    }

    
}


Measured memory_bytes: 11720
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
cin >>n;
  vector<int> a(n);
  for(int i =0;i<n;i++)
    cin >>a.at(i);
  int ans =0;
  for(int i =0;i<n-2;i++){
  if(a.at(i)<=a.at(i+1) && a.at(i+1)<a.at(i+2)) ans ++;
  else if(a.at(i)>a.at(i+1) && a.at(i+1)>=a.at(i+2)) ans ++;  
  }
  cout <<ans<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	int i,j,k,n,a[10001],cnt=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",&a[i]);
	
	for(j=0;j<n;j++){
		for(k=0;k<100000;k++){
			if(a[j]%2==1)break;
			a[j]=a[j]/2;
			cnt++;
		}
	}
	printf("%d\n",cnt);
	return 0;
}


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

int main(){
    int a,b;
    cin >> a >> b;
    for(int i = 1; i <= 1000;i++){
        int t_a = i * 0.08;
        int t_b = i * 0.10;
        if(t_a == a && t_b == b){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

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

bool is_palindrome(string s){
    string t(s.rbegin(),s.rend());
    return s == t;
}

int main(){
    string s;
    cin>>s;
    int n=s.size();
    if(is_palindrome(s) && is_palindrome(s.substr(0,(n-1)/2)) && is_palindrome(s.substr((n+1)/2))){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
x = input()
x2 = int(x[-2:])
x = int(x)
c = 0
for i in [5,4,3,2,1]:
    a, b = divmod(x2, i)
    c = c+a
    x2 = b
if x2 == 0:
    print(1 if 100*c < x else 0)
else:
    print(0)

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

Ans=0
Ans2=0
Count2=0
for i in range(1,N+1):
    Ans=i
    Count=0
    for j in range(N):
        if i%2==0:
            Count+=1
            i=i//2
        else:
            break
    if Count>Count2:
        Ans2=Ans
        Count2=Count
    
print(Ans2 if Ans2>0 else 1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
const int INFTY =2147483647;
int main(){
    int a;
    cin>>a;
    cout<<a+a*a+a*a*a<<endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
#define rep(i,n) for(int i=0; i<(int)(n);i++)

int main(){
  int n;
  cin >> n;
  vs w(n);
  rep(i,n){
    cin >> w.at(i);
  }
  set<string> s;
  s.insert(w.at(0));
  for(int i=1;i<n;i++){
    if(s.count(w.at(i))){
      cout << "No" << endl;
      return 0;
    }
    s.insert(w.at(i));
    int pp = w.at(i-1).size();
    if(w.at(i).at(0) != w.at(i-1).at(pp-1)){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
import sys

s = input()

if s[0] != 'A':
  print('WA')
  sys.exit()

s_list = list(s)

if s_list[2:-1].count('C') != 1:
  print('WA')
  sys.exit()

s_list.remove('A')
s_list.remove('C')

s = ''.join(s_list)

if s.islower():
  print('AC')
else:
  print('WA')


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

int main() {
 int N,X;
  cin >> N >> X;
  vector<int> L(N);
  for(int i=0;i<N;i++){
    cin >> L.at(i);
  }
  int count=0,ans=1;
  for(int i=0;i<N;i++){
  	count+=L.at(i);
    if(count<=X){
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i))
#define mat(type, c, m, n) vector<vector<type>> c(m, vector<type>(n));for(auto& r:c)for(auto& i:r)cin>>i;
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define each(x,y) for(auto &(x):(y))
#define var(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__);
template<typename T> void Scan(T& t) { cin >> t; }
template<typename First, typename...Rest>void Scan(First& first, Rest&...rest) { cin >> first; Scan(rest...); }
#define vec(type, c, n) vector<type> c(n);for(auto& i:c) cin>>i;
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define em emplace
#define pb pop_back
#define fi first
#define se second
#define get(a, i) get<i>(a)
#define bit_count __builtin_popcount
#define mt make_tuple
inline string zero(int a,string s,char c='0'){return string(a-len(s),c)+s;}
inline string zero(int a,int t,char c='0'){return zero(a, to_string(t), c);}
inline string zero(int a,ll t,char c='0'){return zero(a, to_string(t), c);}
#define mini min_element
#define maxi max_element
#define sum accumulate
#define chmax(a,b) if(a<b)a=b
#define chmin(a,b) if(a>b)a=b
template <class T> inline void print(T t){cout << t << '\n';}
template <class H, class... T> inline void print(H h, T... t){cout << h << " ";print(t...);}
string mode = "LRDU";
vi m;
char move(int& a, int b, int c) {
	int op = a < 0 ? -1 : 1;
	char s = mode[2 * c + (a >= 0)];
	a = (abs(a) - b) * op;
	return s;
}
void solve() {
	var(int, n);
	int yx[n][2];
	rep(i, 0, n) cin >> yx[i][0] >> yx[i][1];
	bool odd = (abs(yx[0][0]) + abs(yx[0][1])) % 2;
	rep(i, 1, n) {
		if (((abs(yx[i][0]) + abs(yx[i][1])) % 2) != odd) {
			print(-1);
			return;
		}
	}
	rrep(i, 30, -1) {
		m.eb(1 << i);
	}
	if (!odd) m.eb(1);
	print(len(m));
	rep(i, 0, len(m) - 1)
		cout << m[i] << " ";
	print(m.back());
	each(a, yx) {
		string s = "";
		each(b, m) {
			if (abs(a[0]) > abs(a[1])) {
				s += move(a[0], b, 0);
			} else {
				s += move(a[1], b, 1);
			}
		}
		print(s);
	}
}
int main() {
	solve();
	return 0;
}


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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
ll mod = 1000000007;

int main() {
source:
    ll h, n;
    cin >> h >> n;
    ll a[n], b[n];
    rep(i, n) { cin >> a[i] >> b[i]; }

    ll a_max = 0;
    rep(i, n) { a_max = max(a_max, a[i]); }

    ll array_size = h + a_max + 1;

    ll dp[array_size];

    rep(i, array_size) { dp[i] = mod; }
    dp[0] = 0;

    rep(i, array_size) {
        rep(j, n) {
            ll index = i - a[j];
            if (index >= 0) {
                dp[i] = min(dp[index] + b[j], dp[i]);
            }
        }
    }

    ll ans = mod;
    repd(i, h, array_size) { ans = min(ans, dp[i]); }
    cout << ans << endl;

    return 0;
}



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

    using namespace std;
     
    int main(){
    	int n, h, prev;
  		int cnt = 0, m = 0;
  		scanf("%d", &n);
  		scanf("%d", &prev);
  		for(int i = 1; i<n ; ++i){
    		scanf("%d", &h);
    		if(prev<h){
    			m = max(cnt, m);
      			cnt = 0;
    		}else{
    			cnt++;
   			}
   			prev = h;
  		}
  		m = max(cnt, m);
  		printf("%d",m);
    	return 0;
    }

Measured memory_bytes: 256
/*
 Author: Alokit Kumar 
 */
 #include<bits/stdc++.h>
 using namespace std;
 #define int long long
 int32_t main()
 {
   string s;
   cin>>s;
   if(s[1]=='B') cout<<"ARC";
   else cout<<"ABC";
   return 0;
 }

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

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef pair <ll, ll> dl;
typedef pair <int, int> ii;
typedef vector <ii> vii;
typedef vector <vl> graph;

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

    bitset <10> vis;
    vis.reset();
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    vis[a] = vis[b] = vis[c] = vis[d] = true;
    if (vis[1] && vis[9] && vis[7] && vis[4]) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

Measured memory_bytes: 256
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
// #include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb push_back
#define res(v) v.resize(unique(v.begin(), v.end()) - v.begin());
#define cnt_res(v) std::distance(v.begin(),std::unique(v.begin(), v.end())); 
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int,int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
#define mp         make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,b,a) for (int i = b; i >= a; i--)
#define all(x)     x.begin(), x.end()
using namespace std;
const int N=2e6+10;
const int inf = /*0x3f3f3f3f*/1e18+10;
// const ll M = 998244353 ; // Mulo
// const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
string s;
void solve(){
  cin>>s;int n=s.length();
  rep(i,0,n-1){
    if(s[i]=='?')cout<<"D";
    else cout<<s[i];
  }
}
int32_t main()
{
  ibs;cti;
  solve()
  /*,cout<<"\n"*/;
  // cout<<"\n";
  int xx=0;
  // int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<":\n"*/;solve();cout<<"\n";}
  return 0;
}

Measured memory_bytes: 3740
#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

#define rep(i, n)      for (int i=0; i<int(n); i++)
#define rep3(i, s, n)  for (int i=int(s); i<int(n); i++)
#define rev_rep(i, n)  for (int i=int(n)-1; i>=0; i-=1)

int n, m;
int dist[100100];

int main() {
  cin >> n >> m;
  rep(i, n-1) {
    int x;
    cin >> x;
    dist[i+1] = dist[i] + x;
  }
  int x = 0, a;
  int ans = 0;
  rep(i, m) {
    cin >> a;
    ans = (ans + abs(dist[x+a] - dist[x])) % 100000;
    x += a;
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 3480
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')

def lcm(x, y):
    return x * y // gcd(x, y)
def solve():
    n = int(input())
    ans = 0
    for i in range(n):
        t = int(input())
        if i:
            ans = lcm(ans, t)
        else:
            ans = t
    print(ans)
    

        
    
t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

7
3 1
4 1
5 9
2 6
5 3
5 8
9 7 5

"""


Measured memory_bytes: 9256
import java.util.Arrays
import java.util.ArrayList
import java.util.ArrayDeque

const val MOD: Long = (1e9+7).toLong()
fun Double.format(digits: Int) = String.format("%.${digits}f", this)
fun <T : Comparable<T>> Iterable<T>.argmax(): Int? = withIndex().maxBy{it.value}?.index
fun <T : Comparable<T>> Iterable<T>.argmin(): Int? = withIndex().minBy{it.value}?.index

data class Move(val y1: Int, val x1: Int, val y2: Int, val x2: Int)
fun main(args: Array<String>) {
    val reader = System.`in`.bufferedReader()
    val (h, w) = reader.readLine()!!.split(" ").map{it.toInt()}
    val a = Array(h, {reader.readLine()!!.split(" ").map{it.toInt()}.toIntArray()})

    val res = arrayListOf<Move>()
    for (row in 0..h-1) {
        if (row%2 == 0) {
            for (col in 0..w-1) {
                if (a[row][col]%2 != 0) {
                    if (col != w-1) {
                        res.add(Move(row, col, row, col+1))
                        a[row][col+1]++
                    } else if (row != h-1) {
                        res.add(Move(row, col, row+1, col))
                        a[row+1][col]++
                    }
                }
            }
        } else {
            for (col in w-1 downTo 0) {
                if (a[row][col]%2 != 0) {
                    if (col != 0) {
                        res.add(Move(row, col, row, col-1))
                        a[row][col-1]++
                    } else if (row != h-1) {
                        res.add(Move(row, col, row+1, col))
                        a[row+1][col]++
                    }
                }
            }
        }
    }

    println(res.size)
    res.forEach {
        println("${it.y1+1} ${it.x1+1} ${it.y2+1} ${it.x2+1}")
    }
}


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

int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll n,k;
    cin >> n >> k;
    
    cout << min(n%k, (n + k-1)/k * k  - n) << "\n";
    
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public final class Main {
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        
        String s = stdIn.next();
        char[] cs = s.toCharArray();
        int [] flag = new int [26];
        int containTwo = 0;
        
        for(int i=0; i<cs.length; i++){
            flag['Z'-cs[i]]++;
        }
        for(int i=0; i<flag.length; i++){
            if(flag[i] == 2){
                containTwo++;
            }
        }

        if(containTwo == 2){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 23252
#include <stdio.h>

int main()
{
	char T[100 + 1];
	char H[100 + 1];
	int n,tc,hc,i,j;

	scanf("%d",&n);

	tc = hc = 0;

	for (i = 0; i < n; i++)
	{
		scanf("%100s",T);
		scanf("%100s",H);

		j = 0;

		while (T[j] != '\0' && H[j] != '\0' && T[j] == H[j]) j++;

		if (T[j] == '\0' && H[j] == '\0')
		{
			tc++; hc++;
		}
		else
		{
			if ((T[j] - H[j]) > 0) tc += 3;
			else hc += 3;
		}
	}

	printf("%d %d\n",tc,hc);

	return 0;
}

Measured memory_bytes: 1744
import sys

icase=0
if icase==0:
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
elif icase==1:
    n,k=4,9
    a=[7,4,0,3]
elif icase==2:
    n,k=3,7
    a=[1,6,3]
elif icase==3:
    n,k=1,0
    a=[1000000000000]

if k==0:
    print(sum(a))
    sys.exit()
    
kk=[0]*42
kkk=k
kcnt=0
while kkk>0:
    kk[kcnt]=kkk%2
    kcnt+=1
    kkk=kkk//2
    
f=[0]*42
for ai in a:
    icnt=0
    while ai>0:
        f[icnt]+=ai%2
        ai=ai//2
        icnt+=1

n2=n//2+1
fm=[0]*42

flg1=0
flg2=0
for i in range(41,-1,-1):
    if flg1==0 and kk[i]==0:
        fm[i]=0
    if flg1==0 and kk[i]==1:
        flg1=1
    if flg1==0:
        fm[i]=f[i]        
        continue
#  case : flg1=1
    if kk[i]==1 and f[i]>=n2 and flg2==0:
        flg2=1
    if kk[i]==1 or (kk[i]==0 and flg2==1):
        if f[i]<n2:
            fm[i]=n-f[i]
        else:
            fm[i]=f[i]        
    else:
        fm[i]=f[i]        
    
smax=0
idx=1
for i in range(len(fm)):
    smax+=idx*fm[i]
    idx*=2

print(smax)


Measured memory_bytes: 86352
# AOJ 0254: Scone
# Python3 2018.6.25 bal4u

s = [0 for i in range(30001)]
while True:
	n, m = map(int, input().split())
	if n == 0: break
	f = [-1 for i in range(m)]
	sum, nmax, ans = 0, 0, 0
	a = list(map(int, input().split()))
	for i in range(n):
		sum += a[i]
		a[i] %= m
		if a[i] > nmax: nmax = a[i]
		if a[i] == m-1: ans = a[i]
		s[i+1] = s[i] + a[i]
		if s[i+1] >= m: s[i+1] -= m
		f[s[i+1]] = i+1
	if ans == 0:
		if nmax == 0: ans = 0
		elif sum < m: ans = sum
		else:
			done = False
			for ans in range(m-1, nmax-1, -1):
				for i in range(n+1):
					x = s[i]+ans
					if x >= m: x -= m
					if f[x] >= i:
						done = True
						break
				if done: break
	print(ans)



Measured memory_bytes: 12684
import bisect

def wantp(p,day):

    for i in range(len(db)):
        i = len(db)-1-i

        if day & (2 ** i) > 0:
            p = db[i][p]

        #print (day,i)

    return p


N = int(input())
x = list(map(int,input().split()))
L = int(input())

able = []

for i in range(N):

    able.append(bisect.bisect_right(x,x[i] + L) - 1)


db = [able]

while min(db[-1]) != N-1:

    new = []

    for i in range(N):

        new.append(db[-1][db[-1][i]])

    db.append(new)


Q = int(input())

for loop in range(Q):

    a,b = map(int,input().split())
    if a > b:
        t = a
        a = b
        b = t
    a -= 1
    b -= 1

    l = 0
    r = 2 ** len(db)

    while r-l != 1:

        m = (l+r) // 2

        np = wantp(a,m)
        #print (a,m,np)

        if np < b:
            l = m
        else:
            r = m

    print (r)


Measured memory_bytes: 93592
s = int(input())
a = [s]
cnt = 2

while True:
    if a[-1]%2 == 1:
        if a[-1]*3+1 in a:
            print(cnt)
            exit()
        else:
            a.append(a[-1]*3+1)
            cnt += 1
    else:
        if a[-1]//2 in a:
            print(cnt)
            exit()
        else:
            a.append(a[-1]//2)
            cnt += 1

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

typedef double du ;
typedef string st ;
typedef long long ll ;
typedef long double ld ;
typedef long long int lli ;


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

    if (a == b && b == c)
        cout << 1 ;
    else if (a == b || a == c || b == c)
        cout << 2 ;
    else if (a != b && b != c && a != c)
        cout << 3 ;



    return 0 ;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long x = in.nextLong();

        long ans = 0;
        ans += (x / 11) * 2;
        x = x % 11;
        
        if (x == 0) {
            System.out.println(ans);
        } else if (x <= 6) {
            System.out.println(ans + 1);
        } else {
            System.out.println(ans + 2);
        }
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pa;
const int N=301,P=1e9+7;

struct data{
	int l,r,x;
}r[N];

inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    char ch=nc();int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}

int f[N][N][N];
bool vis[N][N][N];
vector<pa> v[N];

inline bool ck(int k,int r,int b,int g){
	for(int i=0;i<v[k].size();i++){
		if((r>=v[k][i].first)+(b>=v[k][i].first)+(g>=v[k][i].first)!=v[k][i].second) return 0;
	}
	return 1;
}

inline void add(int&a,int &b){a=a+b;if(a>P) a-=P;}

int main(){
	int n,m;
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int l,r,x;
		l=read(),r=read(),x=read();
		v[r].push_back(pa(l,x)); 
	}
	int ban=0;
	f[0][0][0]=1;
	int ans=0;
	for(int i=0;i<n;i++){
		for(int B=0;B<=i;B++){
			for(int G=0;G<=i;G++) if(f[i][B][G]){
				if(ck(i+1,i+1,B,G)){
					if(i+1==n) add(ans,f[i][B][G]);
					else add(f[i+1][B][G],f[i][B][G]);
				}
				if(ck(i+1,i,i+1,G)){
					if(i+1==n) add(ans,f[i][B][G]);
					else add(f[i+1][i][G],f[i][B][G]);
				}
				if(ck(i+1,i,B,i+1)){
					if(i+1==n) add(ans,f[i][B][G]);
					else add(f[i+1][B][i],f[i][B][G]);
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}
	

Measured memory_bytes: 106752
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

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

using namespace std;

const int inf = 1 << 30;

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

class Edge {
public:
  int cost;
  int nextx;
  int nexty;
  int direction;
  Edge (int c, int x, int y, int d):cost(c), nextx(x), nexty(y), direction(d) {}
};

bool operator> (Edge e1, Edge e2) {
  return (e1.cost > e2.cost);
}

int main(){
  int w, h;
  while(cin >> w >> h, w + h) {
    vector<vector<int>> s(h, vector<int>(w));
    int c[4];    
    REP (i, 0, h) REP (j, 0, w) cin >> s[i][j];
    REP (i, 0, 4) cin >> c[i];
    priority_queue<Edge, vector<Edge>, greater<Edge> > edge;
    vector<vector<vector<int>>> memo(4, vector<vector<int>>(h, vector<int>(w, inf)));
    vector<vector<vector<int>>> isAccess(4, vector<vector<int>>(h, vector<int>(w, 0)));
    edge.emplace(0, 0, 0, 0);
    
    while (edge.size()) {
      Edge e = edge.top();
      edge.pop();
      int x = e.nextx;
      int y = e.nexty;
      int d = e.direction;
      if (isAccess[d][y][x]) continue;
      isAccess[d][y][x] = 1;
      REP (k, 0, 4) {
	int nextd = (d + k) % 4;
	int nextx = x + dx[nextd];
	int nexty = y + dy[nextd];

	if (nextx < 0 || nextx >= w || nexty < 0 || nexty >= h) continue;
	int cost = (k == s[y][x] ? 0 : c[k]) + e.cost;
	if (memo[nextd][nexty][nextx] > cost) {
	  edge.emplace(cost, nextx, nexty, nextd);
	  memo[nextd][nexty][nextx] = cost;
	}
      }      
    }
    
    int min_ = inf;
    REP (i, 0, 4) min_ = min(min_, memo[i][h - 1][w - 1]);
    cout << min_ << endl;
  }
  return 0;
}

Measured memory_bytes: 3228
# coding:utf-8
 
def main():
    sanka, rate = map(int, input().split())
    
    if sanka < 10:
        print(100 * (10 - sanka) + rate)
        
    else:
        print(rate)
  
    return 0 
 
if __name__ == '__main__':
  main()

Measured memory_bytes: 2940
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            double q = sc.nextInt();
            if (q == -1) {
                break;
            }
            double x = q / 2;
            while (Math.abs(x * x * x - q) >= 0.00001 * q) {
                x -= (x * x * x - q) / (3 * x * x);
            }
            System.out.printf("%.6f\n", x);
        }
    }
}


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

using namespace std;

#define INF 1000007
#define MOD 1000000007
#define maxn 100
#define int long long int
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

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

int mpow(int N, int P, int M)  //繰り返し自乗法
{
    if (P == 0)
        return 1;
    if (P % 2 == 0) {
        int t = mpow(N, P / 2, M);
        return t * t % M;
    }
    return N * mpow(N, P - 1, M) % M;
}

vector<bool> prime(maxn + 1, true); //素数テーブル
void prime_table(void) {
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= maxn; i++) {
        if (!prime[i]) {
            continue;
        }
        for (int j = i + i; j <= maxn; j += j + i) {
            prime[j] = false;
        }
    }
}

signed main() {
    int N;
    cin >> N;
    vector<int> b;
    vector<int> ans;
    rep(i, N) {
        int a;
        cin >> a;
        b.push_back(a);
    }
    rep(i, N) {
        int place = 0;
        rep(j, b.size()) {
            if (b[j] == j + 1) {
                place = j;
            }
        }
        if (b[place] != place + 1) {
            cout << "-1" << endl;
            return 0;
        }
        ans.push_back(b[place]);
        b.erase(b.begin() + place);
    }
    rep(i, N) {
        cout << ans[(N - 1) - i] << endl;
    }
}


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

int main() {
  long long num = 0;
  cin >> num;
  long long minS = 10000000000000000;

  vector<long long> sp(5,0);
  for (int i = 0; i < 5; i++) {
	cin >> sp.at(i);
	if (minS > sp.at(i)) {
		minS = sp.at(i);
	}
  }

  if (num % minS == 0) {
  	cout << num / minS + 4 << endl;
  } else {
  	cout << num / minS + 5 << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

typedef struct Node* NodePointer;

typedef struct Node {
  int key;
  NodePointer left, right;
} Node;

NodePointer makeNode(int key) {
  NodePointer node = (NodePointer)malloc(sizeof(Node));
  node->key = key;
  node->left = node->right = NULL;
  return node;
}

NodePointer head;

void init() {
  head = makeNode(INT_MAX);
}

void treeInsert(NodePointer T, NodePointer z) {
  NodePointer *next;
  next = (z->key <= T->key) ? &(T->left) : &(T->right);
  if(*next == NULL) {
    *next = z;
  } else {
    treeInsert(*next, z);
  }
}

void printInorder(NodePointer node) {
  if(node->left  != NULL) printInorder(node->left);
  if(node == head) return;
  printf(" %d", node->key);
  if(node->right != NULL) printInorder(node->right);
}

void printPreorder(NodePointer node) {
  if(node != head) printf(" %d", node->key);
  if(node->left  != NULL) printPreorder(node->left);
  if(node == head) return;
  if(node->right != NULL) printPreorder(node->right);
}

int main() {
  int N, key;
  char str[10];
  init();
  scanf("%d", &N);
  while(N--) {
    scanf("%s", str);
    if(str[0] == 'i') {
      scanf("%d", &key);
      treeInsert(head, makeNode(key));
    } else {
      printInorder(head);
      printf("\n");
      printPreorder(head);
      printf("\n");
    }
  }
  return 0;
}

Measured memory_bytes: 8276
#include<bits/stdc++.h>
using namespace std;
string s,t;
bool check(string a,string b)
{
	for(int i=0;i<a.size();i++)
	{
		if(a[i]=='?')continue;
		if(a[i]!=b[i])return false;
	}
	return true;
}
int main()
{
	cin>>s>>t;
	for(int i=s.size()-t.size();i>=0;i--)
	{
		if(check(s.substr(i,t.size()),t))
		{
			for(int j=i;j<i+t.size();j++)
				s[j]=t[j-i];
			for(int j=0;j<s.size();j++)
				if(s[j]=='?')
					s[j]='a';
			cout<<s<<endl;
			return 0;
		}
	}
	cout<<"UNRESTORABLE\n";
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int n;
  scanf("%d",&n);
  
  int num[n];
  int j =0;
  for(int i = 0;i<n;i++){
    scanf("%d",&num[i]);
    if(num[i]!=i+1){
      j++;
    }
  }
  if(j>=3){
    printf("NO\n");
  }else{
    printf("YES\n");
  }
  return 0;
}

Measured memory_bytes: 128