akhauriyash/Code-Regression huggingface dataset:
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif

int prev[100001];
int rank[100001];
int size[100001];

void init(int n){
	for(int i=1; i<=n; i++){ prev[i]=i; rank[i]=1; size[i]=1; }
}
int root(int x){
	return prev[x]==x?x:(prev[x]=root(prev[x]));
}
long join(int x, int y){
	x=root(x), y=root(y);
	if(x==y) return 0;
	long ans = (long)size[x]*size[y];
	if(rank[x]<rank[y]){
		prev[x]=y;
		size[y]+=size[x];
	}else if(rank[x]>rank[y]){
		prev[y]=x;
		size[x]+=size[y];
	}else{
		prev[x]=y;
		rank[y]++;
		size[y]+=size[x];
	}
	return ans;
}

char bufr[14000014], bufw[7000000];
int bufrl, bufwl;
#define getchar_unlocked() bufr[bufrl++]
#define putchar_unlocked(c) bufw[bufwl++]=(c)

int32_t nextint(void){ char c=getchar_unlocked(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar_unlocked(); bool s=false; if(c=='-'){s=true;c=getchar_unlocked();} uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar_unlocked(); } return s?-x:x; }
int64_t nextlong(void){ char c=getchar_unlocked(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar_unlocked(); int s=0; if(c=='-'){s=1;c=getchar_unlocked();} uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar_unlocked(); } return s?-x:x; }
void printlong(int64_t x){ if(x<0){x=-x; putchar_unlocked('-');}else if(x==0){putchar_unlocked('0');} int d=0; char s[20]; while(x){ s[d]='0'+x%10; x/=10; d++; } for (int i=d-1; i>=0; i--) putchar_unlocked(s[i]); putchar_unlocked('\n'); }

int a[100000][2];
long b[100000];
int main(void){
	read(STDIN_FILENO, bufr, sizeof(bufr));
	int n=nextint();
	int m=nextint();
	for(int i=m-1; i>=0; --i){
		a[i][0]=nextint();
		a[i][1]=nextint();
	}
	init(n);
	for(int i=0; i<m; i++){
		b[i]=join(a[i][0], a[i][1]);
	}
	long ans=0;
	for(int i=m-1; i>=0; --i){
		ans+=b[i];
		printlong(ans);
	}
	write(STDOUT_FILENO, bufw, bufwl);
}


Measured memory_bytes: 9472
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i < n; i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define P pair<int, int>
typedef long long ll;
const ll mod = 1e9+7;

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

//繰り返し自乗法による累乗計算
//a**n
ll pow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = pow(a, n/2);
    return res * res;
  }
  return a * pow(a, n-1);
}
//繰り返し自乗法によるmod累乗計算
//a**n (mod)
ll modpow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = modpow(a, n/2);
    return res * res % mod;
  }
  return a * modpow(a, n-1) % mod;
}
//組み合わせ
//nCa
ll com(ll n, ll a){
  ll x = 1, y = 1;
  rep(i,a){
    x *= n-i;
    y *= i+1;
  }
  ll res = x / y;
  return res;
}
//組み合わせ(mod)
//nCa (mod)
ll modcom(ll n, ll a){
  ll x = 1, y = 1;
  rep(i, a){
    x = x * (n-i) % mod;
    y = y * (i+1) % mod;
  }
  ll ans = x * modpow(y, mod-2) % mod;
  return ans;
}
//gcd 最大公約数
ll gcd(ll x, ll y){
  if(x % y == 0) return y;
  return gcd(y, x%y);
}
//lcm 最小公倍数
ll lcm(ll x, ll y){
  return x * y / gcd(x, y);
}
//ngcd n個の最大公約数
ll ngcd(vector<ll> a){
  ll res;
  res = a[0];
  for(ll i = 1; i < a.size() && res != 1; i++) {
    res = gcd(a[i], res);
  }
  return res;
}
//nlcm n個の最小公倍数
ll nlcm(vector<ll> a) {
  ll res;
  res = a[0];
  for (ll i = 1; i < a.size(); i++) {
    res = lcm(res, a[i]);
  }
  return res;
}
// 素数判定
bool isprime(ll x){
  ll i;
  if(x < 2) return false;
  else if(x == 2) return true;
  if(x % 2 == 0) return false;
  for(i = 3; i*i <= x; i += 2){
    if(x % i == 0) return false;
  }
  return true;
}
// 桁和
ll digsum(ll x){
  ll res = 0;
  while(x > 0){
    res += x % 10;
    x /= 10;
  }
  return res;
}


int main(){
  int n, k, x, y;
  cin >> n >> k >> x >> y;
  int ans;
  if(n > k){
    ans = k*x + (n-k)*y;
  }
  else{
    ans = n*x;
  }
  cout << ans << endl;
} 






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

int main() {
	string s, p;
	getline(cin, s);
	getline(cin, p);

	if ((s + s).find(p) != string::npos) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}



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

int main() {
  string S;
  cin >> S;
  int N;
  N = S.size();
  
  bool a = true;
  for(int i = 0; i < N; i++) {
    if(S.at(i) != S.at((N - 1)- i)) {
      a = false;
    }
  }
  
  bool b = true;
  for(int i = 0; i < (N / 2); i++) {
    if(S.at(i) != S.at((N - 1) / 2 - 1 - i)) {
      b = false;
    }
  }

  bool c = true;
  for(int i = 0; i < (N / 2); i++) {
    if(S.at((N + 3) / 2 - 1 + i) != S.at((N - 1) - i)) {
      c = false;
    }
  }
  
  if(a == 1 & b == 1 & c == 1) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

int main() {
    int t_hp, t_a, a_hp, a_a;
    cin >> t_hp >> t_a >> a_hp >> a_a;
    
    while (1) {
        a_hp = a_hp - t_a;
        if (a_hp <= 0) {
            cout << "Yes" << endl;
            break;
        } else {
            t_hp = t_hp - a_a;
            if (t_hp <= 0) {
                cout << "No" << endl;
                break;
            }
        }
    }
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <string>
#include <fstream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<int> stones(n);
	for(int i=0; i<n;i++)
	{
		cin>>stones[i];
	}
	vector<int> cost(n,INT_MAX);
	cost[0] = 0;
	for(int i = 0; i<n ;i++)
	{
		for(int j : {i+1, i+2})
		{
			if(j<n)
			{
				cost[j] = min(cost[j] , cost[i] + abs(stones[i] - stones[j]));
			}
		}
	}
	cout<<cost[n-1];
    return 0;
}

Measured memory_bytes: 1024
#include <string>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,h[100005];
ll dp[100005];
 
int main()  {

  int A,B;
  std::cin >> A >> B;
  
  int ans;
  
  if(B%A==0){
	
		printf("%d",A+B);
   }
   else{
		printf("%d",B-A);
	}  
   
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<stdio.h>
#include<cmath>
#include<math.h>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<sstream>
#include<iomanip>
#define forn(i,n) for(int (i)=0;i<(n);i++)
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int MAXN=100005;
const int INF=2147483647;
const ll LINF=9223372036854775807;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	cout<<n*(n-1)/2+m*(m-1)/2;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int i,sum=0;
  for(i=0;i<s.size();i++){
    sum+=(s[i]-'0');
  }
  if(sum%9==0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3656
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

int sum(int i, vector<int>& bit)
{
	auto s = 0;
	while (i > 0)
	{
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

void add(int i, int x, vector<int>& bit)
{
	auto n = (int)bit.size() - 1;
	while (i <= n)
	{
		bit[i] += x;
		i += i & -i;
	}
}

int main()
{
	int N;
	cin >> N;

	vector<vector<int>> bits(30, vector<int>(N + 1));
	string S;
	cin >> S;
	for (auto i = 0; i < N; ++i)
	{
		auto c = S[i] - 'a';
		add(i + 1, 1, bits[c]);
	}

	int Q;
	cin >> Q;

	vector<int> ans;
	for (auto k = 0; k < Q; ++k)
	{
		int t;
		cin >> t;

		if (t == 1)
		{
			int i;
			char c;
			cin >> i >> c;
			--i;
			if (S[i] != c)
			{
				auto prev = S[i] - 'a';
				add(i + 1, -1, bits[prev]);
				auto next = c - 'a';
				add(i + 1, 1, bits[next]);
				S[i] = c;
			}
		}
		else
		{
			int l, r;
			cin >> l >> r;
			auto kind = 0;
			for (auto j = 0; j < 30; ++j)
			{
				auto s = sum(r, bits[j]);
				s -= sum(l - 1, bits[j]);
				if (s > 0)
				{
					++kind;
				}
			}
			ans.push_back(kind);
		}
	}

	for (auto i = 0; i < (int)ans.size(); ++i)
	{
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 60928
#include <stdio.h>

int main(){
	int a=0,n;
	long long int min=1000000,max=-1000000,sum=0;
	scanf ("%d",&n);
	int x[n];
	for (a=0;a<n;a++){
		scanf ("%d",&x[a]);
	}
	//--------- a = n ;
	for( a=0;a<n /*?????¶*/ ; a++ /*a???1????¶????*/ ){
		if( min>x[a]){
			min=x[a];
		}
		if (max<x[a]){
			max=x[a];
		}
		sum=sum+x[a];
	}
	printf ("%lld %lld %lld\n",min,max,sum);
	return 0;
}

Measured memory_bytes: 636
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;

int main(){
  int k,s;cin >> k >> s;
  int ans = 0;
  for(int x=0;x<=k;x++){
    for(int y=0;y<=k;y++){
      if(0<=s-x-y&&k>=s-x-y) ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

ll modpow(ll x, ll b){
  ll res = 1;
  while(b){
    if(b&1)res = res * x % MOD;
    x = x * x % MOD;
    b>>=1;
  }
  return res;
}

ll modinv(ll x){
  return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
  if(was_output)cout << " ";
  cout << a;
  was_output = true;
}
void outendl(){
  was_output = false;
  cout << endl;
}
ll in(){
  ll res;
  scanf("%lld", &res);
  return res;
}

template<class t>
istream& operator>>(istream&is, vector<t>&x){
  for(auto &i:x)is >> i;
  return is;
}

template<class t, class u>
istream& operator>>(istream&is, pair<t, u>&x){
  is >> x.first >> x.second;
  return is;
}

template<class t>
void in(t&x){
  cin >> x;
}

template<class t>
void out(t x){
  cout << x;
}

int main(){
  int n = in();
  map<int,int> m;
  rep(i,n)++m[in()];
  int ans = 0;
  foreach(i,m)ans += i.first<=i.second ? i.second-i.first:i.second;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4736
#include<iostream>
#include<stack>
#include<sstream>
#include<string>
#include<ctype.h>
using namespace std;

stack<int> s;

int main(){

    while(!s.empty()){
      s.pop();
    }
    string tmp="";
    while(getline(cin,tmp,' ')){
      stringstream ss;
      int a=0;
      if(isdigit(tmp[0])){
        ss << tmp;
        ss >> a;
        s.push(a);
      }else{
        string sign;
        sign = tmp;
        int left,right;
        right = s.top(); s.pop();
        left = s.top(); s.pop();
        switch (sign[0]) {
          case '+':
            s.push(left+right);
            break;
          case '-':
            s.push(left-right);
            break;
          case '*':
            s.push(left*right);
            break;
          case '/':
            s.push(left/right);
            break;
          default:
            break;
        }
        //cout << s.top() << endl;
      }
    }

    cout << s.top() << endl;

    return 0;
}

Measured memory_bytes: 3192
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;
int n,k,vis,tmp;
ll a[N],minn=LONG_LONG_MAX,ans[N];
int main(){
	cin>>n>>k;
	for(int i = 1;i<=n;i++){
		cin>>a[i];
		if(a[i]>=0&&!tmp) vis=i,tmp=1;
	}
	if(vis==0){
		cout<<abs(a[n-k+1])<<endl;
		return 0;
	}
	for(int i = 1;i<vis;i++){
		if(i+k-1>n) continue;
		ans[i]=abs(a[i]);//+abs(a[i+k-1]);
		if(a[i+k-1]>0) ans[i]+=abs(a[i])+abs(a[i+k-1]);
		minn=min(minn,ans[i]);
	}
	for(int i = vis;i<=n;i++){
		if(i-k+1<1) continue;
		ans[i]=abs(a[i]);//+abs(a[i-k+1]);
		if(a[i-k+1]<0) ans[i]+=abs(a[i])+abs(a[i-k+1]);
		minn=min(minn,ans[i]);
	}
	cout<<minn<<endl;
	return 0;
}

Measured memory_bytes: 1792
/* ****mittal**** */
#include<bits/stdc++.h>
#define ll          long long int 
#define pb          push_back
#define endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define repr(i,a,b)   for(ll int i=a;i>=b;i--)
#define lbnd    lower_bound
#define ubnd        upper_bound
#define mp          make_pair
using namespace std;
ll add(ll x,ll y)
{
return (x%hell+y%hell)%hell;
}
ll mul(ll x,ll y)
{
return ((x%hell)*(y%hell))%hell;
}
ll sub(ll x,ll y)
{
return (x-y+hell)%hell;
}
#define N  100005
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        ll n,m;
        cin>>n>>m;
        std::vector<string> v[n+2];
        for(int i=0;i<m;i++)
        {
           ll x;
           string d;
           cin>>x;
           cin>>d;
           v[x].pb(d);
        }
        // for(int i=1;i<=n;i++)
        // 	sort(all(v[i]));
        ll cnt=0,jk=0;
        // for(int i=1;i<=n;i++)
        // {
        // 	if(v[i].size()>0&&v[i][0]=="AC")
        // 		cnt++;
        // }
        for(int i=1;i<=n;i++)
        {
        	ll p=0,w=0;
        	for(int j=0;j<v[i].size();j++)
        	{
        		if(v[i][j]=="AC")
        			{
        				cnt++;
        				p=1;
        				break;
        			}
        		else
        			{
        				w++;
        			}
        	}
        	if(p==1)
        		jk+=w;
        }
        cout<<cnt<<" "<<jk;
    }
    return 0;
}

Measured memory_bytes: 10368
#include<iostream>
using namespace std;
#include<stdio.h>

int main(){
    
    long long n,a,min=1000000,max=-1000000,sum=0;
    cin >>n;
    
    for (int i=0;i<n;i++){
        cin >> a;
        sum = sum + a;
        if (a<min) min = a;
        if (a>max) max = a;
    }
    printf("%ld %ld %ld\n", min, max, sum);
    return 0;
}




Measured memory_bytes: 3216
#include <stdio.h>
int main(void){
    int bi,mi,n,m;
    scanf("%d %d",&n,&m);
    if(n<m){
        bi=m;
        mi=n;
    }
    else{
        bi=n;
        mi=m;
    }
    while(1){
        n=bi%mi;
        bi=mi;
        mi=n;
        if(mi==0)break;
    }
    printf("%d\n",bi);
    return 0;
}

Measured memory_bytes: 592
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) (a*a)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

int main() {
	string str;
	cin >> str;
	switch (str[0]) {
	case 'a':
	case 'i':
	case 'u':
	case 'e':
	case 'o':
		cout << "vowel" << endl;
		break;
	default:
		cout << "consonant" << endl;
	}
	return 0;
}

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

int main() {
	string s;

	cin >> s; 

	if(s[0] != s[1] || s[1] != s[2] || s[0] != s[2] ) {
		cout << "Yes";
	} else {
		cout << "No";
	}

	return 0;
}



Measured memory_bytes: 256
use std::collections::BinaryHeap;

const INF: i64 = 1 << 50;
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let m: usize = sc.read();
    let l: i64 = sc.read();
    let mut graph = vec![vec![]; n];
    for _ in 0..m {
        let a = sc.read::<usize>() - 1;
        let b = sc.read::<usize>() - 1;
        let c: i64 = sc.read();
        if c <= l {
            graph[a].push((b, c));
            graph[b].push((a, c));
        }
    }

    let mut ans = vec![];
    for start in 0..n {
        let mut dist = vec![(INF, 0); n];
        dist[start] = (0, l);
        let mut vis = vec![false; n];
        let mut heap = BinaryHeap::new();
        heap.push((0, l, start));
        while let Some((_, _, v)) = heap.pop() {
            if vis[v] {
                continue;
            }
            vis[v] = true;
            for &(next, cost) in graph[v].iter() {
                let next_state = if dist[v].1 < cost {
                    (dist[v].0 + 1, l - cost)
                } else {
                    (dist[v].0, dist[v].1 - cost)
                };
                if dist[next].0 > next_state.0
                    || (dist[next].0 == next_state.0 && dist[next].1 < next_state.1)
                {
                    dist[next] = next_state;
                    heap.push((-next_state.0, next_state.1, next));
                }
            }
        }
        ans.push(dist);
    }

    let q: usize = sc.read();
    for _ in 0..q {
        let a = sc.read::<usize>() - 1;
        let b = sc.read::<usize>() - 1;
        let ans = ans[a][b].0;
        if ans == INF {
            sc.write("-1\n");
        } else {
            sc.write(format!("{}\n", ans));
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 8572
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<double,int> pii;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<pii> vp;
typedef vector<pdd> vdd;
typedef vector<pair<double,int> >vdi;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip	;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
class DIJ{
    public:
    struct edge{
        int to;
        double cost;
    };
    vector<vector<edge> >G;
    int n;
    vector<double> d;//distance
    DIJ(int size){
        n=size;
        G=vector<vector<edge> >(n);
    }
    void add_edge(int a,int b,double c){
        edge e={b,c},ee={a,c};
        G[a].pb(e);
        G[b].pb(ee);
    }
    void dij(int s){
        d=vector<double>(n,inf);
        d[s]=0;
        priority_queue<pii>q;
        q.push(pii(0,s));
        while(!q.empty()){
            pii p=q.top();
            q.pop();
            int pos=p.second;
            double cost=-p.first;
            if(cost>d[pos])continue;
            rep(i,G[pos].size()){
                edge e=G[pos][i];
                int to=e.to;
                double nowcost=cost+e.cost;
                if(nowcost<d[to]){
                    d[to]=nowcost;
                    q.push(pii(-d[to],to));
                }
            }
        }
    }
};
int main(){
    int n;
    while(cin>>n,n){
        vi m(n);
		map<int,int>M;
        vector<pair<int,int> > in(n);
        rep(i,n){
            int a,b,c;
            cin>>a>>b>>c;
            m[i]=a;
			M[a]=i;
            in[i]=pair<int,int>(b,c);
        }
        DIJ dij(n);
        rep(i,n)rep(j,i)if(i!=j&&hypot(in[i].first-in[j].first,in[i].second-in[j].second)<EPS+50)dij.add_edge(i,j,hypot(in[i].first-in[j].first,in[i].second-in[j].second));
        int N;
        cin>>N;
        while(N--){
            int a,b;
            cin>>a>>b;
			a=M[a];b=M[b];
            dij.dij(a);
            if(abs(dij.d[b]-inf)<EPS)cout<<"NA"<<endl;
            else{
                vi out;
                out.pb(b);
                int t=b;
                while(1){
                    rep(i,n)rep(j,dij.G[i].size()){
                        if(t==dij.G[i][j].to&&abs(dij.d[i]+dij.G[i][j].cost-dij.d[t])<EPS){
                            out.pb(i);
                            t=i;
                            goto end;
                        }
                    }
                    end:;
                    if(out[out.size()-1]==a)break;
                }
                for(int i=out.size()-1;i>=0;i--)cout<<m[out[i]]<<(i?" ":"\n");
            }
        }
    }
}

Measured memory_bytes: 1252
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<unordered_map>
#include<bitset>
#include<cctype>
#include<sstream>
#define LL long long
#define ULL  unsigned  long long
#define maxn (LL)1e6
#define INF 0x3f3f3f3f
#define inf 0x7fffffff
#define PI  acos(-1.0)
#define pb push_back
#define re register LL
const double eps = 0.0000001;
using namespace std;
typedef pair<int,int> pii;
inline int sgn(double x) {
    return (x > eps) - (x < -eps);
}
static char buf[100000],*pa=buf,*pd=buf;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read()
{
    register LL x(0),f(1);register char c(gc);
    while(c>'9'||c<'0')f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9')x=x*10+c-48,c=gc;
    return f*x;
}
int T,n,m;
int  main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
   // freopen("input.txt","r",stdin);
   // freopen("outl.txt","r",stdin);
    #endif // ONLINE_JUDE
    int a;string s;
    cin>>a>>s;
    if(a<3200) cout<<"red"<<endl;
    else cout<<s<<endl;




}


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

int main() {
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  
  int counter = 0;
  
  for (int i = 0; i < A+1; i++) {
    for (int j = 0; j < B+1; j++) {
      for (int k = 0; k < C+1; k++) {
        if ((500*i + 100*j + 50*k) == X) counter++;
      }
    }
  }
  
  cout << counter << endl;
  
}

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

int main() {
    int x, y, z;
    cin >> x >> y >> z;
    swap(x,y);
    swap(x,z);
    cout << x << " " << y << " " << z << endl;
}


Measured memory_bytes: 256
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 998244353;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
const int N = 3e3 + 10;
int A, B, C, D, dp[N][N];
int main()
{
	A = read(), B = read(), C = read(), D = read();
	dp[A][B] = 1;
	for (int i = A; i <= C; ++i)
		for (int j = B; j <= D; ++j) if (i != A || j != B)
		{
			dp[i][j] = add(mul(dp[i][j - 1], i), mul(dp[i - 1][j], j));
			if (i > A && j > B)
				inc(dp[i][j], P - mul(mul(i - 1, j - 1), dp[i - 1][j - 1]));
		}
	write(dp[C][D], '\n');
	return 0;
}


Measured memory_bytes: 38804
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <functional>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int> > g(n);
    repeat (i, m) {
        int a, b; scanf("%d%d", &a, &b); -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    // solve
    vector<bool> used(n);
    vector<int> path;
    function<void (int)> go = [&](int i) {
        path.push_back(i);
        used[i] = true;
        for (int j : g[i]) if (not used[j]) {
            go(j);
            break;
        }
    };
    go(0);
    reverse(whole(path));
    assert (path.back() == 0);
    used[0] = false;
    path.pop_back();
    go(0);
    // output
    printf("%d\n", int(path.size()));
    repeat (i, path.size()) {
        printf("%d%c", path[i] + 1, i + 1 == path.size() ? '\n' : ' ');
    }
    return 0;
}


Measured memory_bytes: 9720
import java.util.*;

public class Main{
    static long sum = 0;
    static long X;
    static int[] a;
    static String S;
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        S = sc.next();
        sc.close();

        X = Long.parseLong(S);
        a = new int[S.length()];

        dps(0, 0);

        System.out.println(sum);

    }
    static void dps(int pos, int val){
        a[pos] = val;
        if(pos == S.length()-1){
            long y = X;
            long sum_p = 0;
            for(int i = S.length()-1; i >= 0; i--){
                if(a[i] == 1){
                    sum_p += y/(int)(Math.pow(10, i));
                    y -= y/(int)(Math.pow(10, i)) * (int)(Math.pow(10, i));
                }
            }
            sum += sum_p+y;
        } else{ 
            dps(pos+1, 1);
            dps(pos+1, 0);
        }
    }
}

Measured memory_bytes: 23892
//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#include<map>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
inline LL readl() {
    LL x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}
int power(int a, int b) {
	int ans = 1;
	while (b) {
		if(b & 1) ans = ans * a;
		b >>= 1; a = a * a;
	}
	return ans;
}
int power_mod(int a, int b, int mod) {
	a %= mod;
	int ans = 1;
	while (b) {
		if(b & 1) ans = (ans * a) % mod;
		b >>= 1, a = (a * a) % mod;
	}
	return ans;
}
LL powerl(LL a, LL b) {
	LL ans = 1ll;
	while (b) {
		if(b & 1ll) ans = ans * a;
		b >>= 1ll;a = a * a;
	}
	return ans;
}
LL power_modl(LL a, LL b, LL mod) {
	a %= mod;
	LL ans = 1ll;
	while (b) {
		if(b & 1ll) ans = (ans * a) % mod;
		b >>= 1ll, a = (a * a) % mod;
	}
	return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
//==========================Code here==========================
int n, f[200000 + 5], sz1[200000 + 5], sz2[200000 + 5];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
int main() {
	
	cin >> n;
	
	for (int i = 0; i <= 200001; ++i) f[i] = i;
	
	for (int i = 1; i <= 100000; ++i) sz1[i] = 1;
	for (int i = 100001; i <= 200000; ++i) sz2[i] = 1;
	
	for (int x, y, i = 1; i <= n; ++i) {
		scanf("%d%d", &x, &y);
		int a = find(x), b = find(y + 100000);
		if (a != b) {
			sz1[b] += sz1[a];
			sz2[b] += sz2[a];
			f[a] = b;
		}
	}
	LL ans = 0;
	for (int i = 1; i <= 200000; ++i) if (find(i) == i) {
		ans += 1ll * sz1[i] * sz2[i];
	}
	cout << ans - n;
	return 0;
}

Measured memory_bytes: 2176
#include<iostream>
using namespace std;
int main() {
	while(1) {
		int a, b;
		char op;
		cin >> a >> op >> b;
		if(op == '?')
			return 0;
		if(op == '+')
			cout << a + b << endl;
		if(op == '-')
			cout << a - b << endl;
		if(op == '*')
			cout << a * b << endl;
		if(op == '/')
			cout << a / b << endl;
	}
}


Measured memory_bytes: 3096
n, k = gets.chomp.split(" ").map(&:to_i)
hs = []
n.times do
  hs << gets.chomp.to_i
end

hs.sort!.reverse!

calc = []
ans = []

hs.each do |h|
  if calc.length < k
    calc << h
  end
  if calc.length == k
    ans << calc.first - calc.last
    calc.shift
  end
end

puts ans.min

Measured memory_bytes: 4592
#include <stdio.h>
#define Max 110
#define INFTY 90000000

int min(int *,int);

int main(){
  int n,i,p[Max];

  scanf("%d",&n);

  for(i=1;i<=n;i++){
    scanf("%d",&p[i-1]);
    scanf("%d",&p[i]);
  }

  printf("%d\n",min(p,n));

  return 0;
}


int min(int *p,int n){
  int i,m[n+1][n+1],l,j,data,k;

  
  for(i=1;i<=n;i++){
    m[i][i]=0;
  }

  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j=i+l-1;
      m[i][j]=INFTY;
      for(k=i;k<=j-1;k++){
	data=m[i][k]+m[k+1][j]+(p[i-1]*p[k]*p[j]);
      if(m[i][j]>data){
	m[i][j]=data;
      }
      }
    }
  }
  return m[1][n];
}
  



Measured memory_bytes: 2148
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> void Max(T &m, const T q) { if (m < q) m = q; }
template<typename T> void Min(T &m, const T q) { if (m > q) m = q; }
template<typename T1, typename T2> pair<T1, T2> operator+(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

int N;
vector<int> A;

int main()
{
    cin >> N;
    A.resize(N);
    cin >> A;

    int mi = 0;
    lint ans = 0;
    REP(i, N) if (A[i] > mi)
    {
        if (A[i] == mi + 1) mi++;
        else
        {
            ans += (A[i] - 1) / (mi + 1);
        }
        Max(mi, 1);
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
     
using namespace std;
     
#define FOR(i,a,b)		for(int i=(a),_b=(b);i<(_b);++i)
#define FORD(i,a,b)		for(int i=(a),_b=(b);i>(_b);--i)
#define pb			push_back
#define mp			make_pair
#define	all(c)			(c).begin(),(c).end()
#define	present(c,x)		((c).find(x) != (c).end())
#define	cpresent(c,x)		(find(all(c),x) != (c).end())
#define	endl			'\n'
     
typedef long long		ll;
typedef unsigned long long	ull;
typedef unsigned char	 	byte;
typedef vector<int>		vi;
typedef pair<int, int>		pii;
typedef pair<ll, ll>		pll;
typedef vector<pii>		vpii;
     
const int MX = 3000;

// dp[i][h] : probability up to ith coins having h heads turned up
double dp[MX][MX];

int main(int argc, char *argv[])
{
#ifdef	HTRINH_UNIT_TEST
	freopen(argv[1],"r",stdin);
	ifstream cin(argv[1]);
#endif
#if 0
	ofstream cout(argv[2]);
#endif
	ios :: sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;
	double p[n];
	FOR(i,0,n) cin >> p[i];
	dp[0][0] = 1-p[0];	// probability of having 0 head after the 1st coin is tossed.
	FOR(i,1,n) dp[i][0] = dp[i-1][0]*(1-p[i]);
	dp[0][1] = p[0];	// probability of having 1 head after the 1st coin is tossed.
	FOR(i,1,n) {
		FOR(h,1,n+1) {
			// coin ith comes up head.
			dp[i][h] = dp[i-1][h-1]*p[i];
			// coin ith comes up tail.
			dp[i][h] += dp[i-1][h]*(1-p[i]);
		}
	}
	double ans = 0;
	FOR(h,n/2+1,n+1) ans += dp[n-1][h];
	cout << std::fixed;
	cout << std::setprecision(10) << ans << endl;
    return 0;
}


Measured memory_bytes: 70528
fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim_right().to_owned()
}

fn str_to_ints(s: String) -> std::vec::Vec<i64> {
    let mut ret = std::vec::Vec::new();
    let ws = s.split_whitespace();
    for w in ws {
        ret.push(w.parse().unwrap());
    }
    ret
}

fn read_ints() -> std::vec::Vec<i64> {
    str_to_ints(read_line())
}

fn abs(x: i64) -> i64 {
    if x < 0 {
        -x
    } else{
        x
    }
}

fn main() {
    let s = read_line();
    let mut n: std::vec::Vec<i64> = std::vec::Vec::new();
    for c in s.chars() {
        n.push(c as i64 - 48);
    }
    let mut ret: i64 = 1000;

    for i in 0..n.len() - 2 {
        ret = std::cmp::min(ret, abs(753 - (100*n[i] + 10*n[i+1] + n[i+2])))
    }
    println!("{}", ret);
}

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

struct RS {
	using type = ll;
	static type id() { return 0; }
	static type op(const type& l, const type & r) {
		return l + r;
	}
};

class lct_node {
	using M = RS;
	using T = typename M::type;
	using U = ll;

	lct_node *l, *r, *p;
	T val, all;
	int size;
	bool flag;
	U lazy;

	int pos() {
		if (p && p->l == this) return -1;
		if (p && p->r == this) return 1;
		return 0;
	}
	void update() {
		size = (l ? l->size : 0) + (r ? r->size : 0) + 1;
		all = M::op(l ? l->all : M::id(), M::op(val, r ? r->all : M::id()));
	}
	void update_lazy(U v) {
		val += v;
		all += v * size;
		if (!flag) {
			lazy = v;
			flag = true;
		}
		else {
			lazy += v;
		}
	}
	void rev_data() {}
	void push() {
		if (pos()) p->push();
		if (flag) {
			if (l) l->update_lazy(lazy);
			if (r) r->update_lazy(lazy);
			flag = false;
		}
	}
	void rot() {
		lct_node *par = p;
		lct_node *mid;
		if (p->l == this) {
			mid = r;
			r = par;
			par->l = mid;
		}
		else {
			mid = l;
			l = par;
			par->r = mid;
		}
		if (mid) mid->p = par;
		p = par->p;
		par->p = this;
		if (p && p->l == par) p->l = this;
		if (p && p->r == par) p->r = this;
		par->update();
		update();
	}
	void splay() {
		push();
		while (pos()) {
			int st = pos() * p->pos();
			if (!st) rot();
			else if (st == 1) p->rot(), rot();
			else rot(), rot();
		}
	}

public:
	lct_node() : l(nullptr), r(nullptr), p(nullptr), val(M::id()), all(M::id()), size(1), flag(false) {}
	lct_node(const T& v) : l(nullptr), r(nullptr), p(nullptr), val(v), all(v), size(1), flag(false) {}
	void init(U v) {
		val = all = T(v);
	}
	void expose() {
		for (lct_node *x = this, *y = nullptr; x; y = x, x = x->p) x->splay(), x->r = y, x->update();
		splay();
	}
	void link(lct_node *x) {
		x->expose();
		expose();
		p = x;
	}
	void cut() {
		expose();
		l->p = nullptr;
		l = nullptr;
		update();
	}
	T find() {
		expose();
		return all;
	}
	void update(U v) {
		expose();
		update_lazy(v);
	}
};

const int MAX = 1e5;

lct_node lct[MAX];

void build(int v, const graph& G) {
	for (auto to : G[v]) {
		lct[to].link(&lct[v]);
		build(to, G);
	}
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	graph G(n);
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int c;
			cin >> c;
			G[i].push_back(c);
		}
	}
	build(0, G);
	int q;
	cin >> q;
	while (q--) {
		int com;
		cin >> com;
		if (com == 0) {
			int v, w;
			cin >> v >> w;
			lct[v].update(w);
		}
		else {
			int u;
			cin >> u;
			printf("%lld\n", lct[u].find() - lct[0].find());
		}
	}
	return 0;
}



Measured memory_bytes: 27944
W, H, N = map(int, input().split())
input_list = []
for i in range(N):
  input_list.append(list(map(int, input().split())))

point_list = []
for h in range(H):
  list_ = []
  for w in range(W):
    list_.append(1)
  point_list.append(list_)

for input_ in input_list:
  x, y, a = input_
  if a == 1:
    for h in range(H):
      for i in range(x):
        point_list[h][i] = 0
  if a == 2:
    for h in range(H):
      for i in range(x, W):
        point_list[h][i] = 0
  if a == 3:
    for i in range(y):
      for w in range(W):
        point_list[i][w] = 0
  if a == 4:
    for i in range(y, H):
      for w in range(W):
        point_list[i][w] = 0

ans = sum([sum(point) for point in point_list])
print(ans)
    

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

int main(){

  int cnt=0,n,A[100];
  
  cin >> n;
  
  if(n == 1){
    cin >> n;
    if(n%2==0) cout << 1 << endl;
    else cout << 2 << endl;
    return 0;
  }
  
  for(int i=0;i<n;i++){
    cin >> A[i];
    if(A[i]%2 == 0) cnt++;
  }
  
  cout << pow(3,n) - pow(2,cnt) << endl;
  
  return 0;
}

Measured memory_bytes: 256
use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let s = sc.chars();
    let result = parse(&s);
    println!("{} {}", result.0, result.1);
}

fn read_char(_: &Vec<char>, pos: &mut usize) {
    *pos += 1;
}

fn next_char(s: &Vec<char>, pos: &mut usize) -> char {
    s[*pos]
}

fn parse_term(s: &Vec<char>, pos: &mut usize) -> (usize, usize) {
    if next_char(s, pos) == '(' {
        read_char(s, pos);
        let result = parse_or(s, pos);
        read_char(s, pos);
        result
    } else {
        read_char(s, pos);
        (1, 1)
    }
}

fn parse_and(s: &Vec<char>, pos: &mut usize) -> (usize, usize) {
    let mut left = parse_term(s, pos);
    while *pos < s.len() && next_char(s, pos) == '&' {
        read_char(s, pos);
        let right = parse_term(s, pos);
        left.0 = cmp::min(left.0, left.1 + right.0);
        left.1 += right.1;
    }
    left
}

fn parse_or(s: &Vec<char>, pos: &mut usize) -> (usize, usize) {
    let mut left = parse_and(s, pos);
    while *pos < s.len() && next_char(s, pos) == '|' {
        read_char(s, pos);
        let right = parse_and(s, pos);
        left.1 = cmp::min(left.1, left.0 + right.1);
        left.0 += right.0;
    }
    left
}

fn parse(s: &Vec<char>) -> (usize, usize) {
    parse_or(s, &mut 0)
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}



Measured memory_bytes: 5028
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace std::chrono;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e15
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int a,b;cin>>a>>b;
	cout<<a*b;
}


Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
        char a = '0', b = '1';
        if(i%2) swap(a, b);
        ans += a == s[i];
    }
    cout << min(ans, (int)s.size()-ans) << "\n";
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<int,P> PP;

vector<PP> v;
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main()
{
	
	string s,t;
	cin >> s >> t;
	ll alpha_cnt[s.size()+1][26] ={-1};
	vector<int> alpha[26];
	rep(i,s.size()){
		alpha[s[i] - 'a'].push_back(i);
	}
	rep(i,s.size()){
		rep(j,26){
			if(alpha[j].size() != 0){
				alpha_cnt[i][j] = alpha[j][0];
			}
			else alpha_cnt[i][j] = -1;
		}
		alpha[s[i] - 'a'].erase(alpha[s[i] - 'a'].begin());
	}		
		// rep(i,s.size()){
			
		// rep(j,26) printf("%3lld ",alpha_cnt[i][j]);//cout << alpha_cnt[i][j] << " " ;
	// cout << " i = " << i << endl;
		// }
	ll ans = 0,p = 0,sp=0;
	bool flag = false;
	//ll cnt = 0;
	while(p < t.size() ){
		ll next = alpha_cnt[sp][t[p]-'a'];
	//	cout << "next " << next << " ans " << ans << " p" << p << " sp " << sp << endl;
		if(next != -1){
			ans += next - sp + 1;
			sp = (next + 1) % s.size();
			p++;
			flag = false;
		}
		else{
			ans += s.size()-sp;
			sp = 0;
			if(flag)break;
			flag = true;
		}
	}
	if(p<t.size()) cout << "-1" << endl;
	else cout << ans << endl;
	return 0;
}


Measured memory_bytes: 21568