akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
 
#define int long long int
#define ld long double
#define mod 1000000007 
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define forn(i,s, e) for (int i = s; i <= e; i++)
#define fornd(i,s, e) for (int i = s ; i >= e; i--)
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define print(x) for(auto el: x) cout<<el<<" ";cout<<"\n"
#define PSET(x,y) fixed<<setprecision(y)<<x
// #define bits(x) __builtin_popcount(x)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
/*void fileio()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}*/
 
 
template <typename T> 
void swap(T& a, T& b){
    T temp = a;
    a = b;
    b = temp;
}
void selfadd(int& a, int b){
    a = a+b;
    if(a>=mod)
        a = a-mod;
}
void selfsub(int& a, int b){
    a = a-b+mod;
    if(a>=mod)
        a = a-mod;
}  
const int N = 100005; 
 
int dp[101][N];
vector<int> a;

void solve(){
    int n,k;
    cin>>n>>k;
    a.assign(n,0);
 
    forn(i,0,n-1)
        cin>>a[i];
 
    memset(dp,0,sizeof(dp));
    
    dp[0][0] = 1;

    for(int i=0;i<=a[0];i++)
        dp[0][i] = 1;

    for(int i=1;i<n;i++){
        int sum = 0;
        for(int j = 0;j<=k;j++){
            sum = dp[i-1][j];
            if(j>0)
                selfadd(sum, dp[i][j-1]);
            if(j>a[i]){
                selfsub(sum, dp[i-1][j-a[i]-1]);
            }            
            dp[i][j] = sum;
        }
    }
    cout<<dp[n-1][k];
}
 
int32_t main()
{
    //fileio();
    fast;
    // int t;
    // cin>>t;
    // for(int y=1;y<=t;y++)
    {
        // cout<<"Case #"<<y<<": ";
        solve();
    }
    return 0;
} 

Measured memory_bytes: 79232
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;


int main(){
    char a,b,c;
    scanf("%c%c%c",&a,&b,&c);
    if(a==c)
        cout<<"="<<endl;
    else if(a<c)
        cout<<"<"<<endl;
    else cout<<">"<<endl;
}


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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat (i, a, b) for (int i = (a); i < (b); i++)
#define rep (i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const int M = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 300 + 5;
const int MAX_N = 1e5 + 5;

int main() {
    int n, t, i;
    cin >> n;
    vector<int> height;
    vector<bool> lock(n, false);
    if (n == 1) {
        puts("Yes");
        return 0;
    }
    for (i = 0; i < n; i++) {
        cin >> t;
        height.push_back(t);
    }
    for (i = 0; i < n - 1; i++) {
        if (height[i] > height[i + 1]) {
            if (!lock[i]) {
                height[i]--;
                lock[i] = true;
                if (i - 1 >= 0 && height[i - 1] > height[i]) {
                    i = i - 2;
                }
            }
        }
    }
    for (i = 0; i < n - 1; i++) {
        if (height[i] > height[i + 1]) {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
}


Measured memory_bytes: 896
#include<iostream>
#include<set>
using namespace std;
long long n,i,k,a[200001],b[200001],ans;
set<int>s;
int main()
{
    cin>>n;
    s.insert(0);
    s.insert(n+1);
    for(i=1;i<=n;i++){
       cin>>a[i];
        b[a[i]]=i;
    }
    for(i=1;i<=n;i++){
       auto it=s.lower_bound(b[i]);
       k=*it;
       it--;
       ans+=(k-b[i])*(b[i]-*it)*i;
       s.insert(b[i]);
    }
    cout<<ans<<endl;
    return 0;
       
}

Measured memory_bytes: 12800
from sys import stdin
def main():
    readline=stdin.readline
    s=readline().strip()
    flagA=False
    flagB=False
    for i in range(len(s)):
        if s[i]=="A":
            flagA=True
        else:
            flagB=True
    if flagA and flagB:
        print("Yes")
    else:
        print("No")

if __name__=="__main__":
    main()

Measured memory_bytes: 3060
def resolve():
  n = int(input())
  a = list(map(int, input().split()))
  b = list(map(int, input().split()))
  ans = 0
  for i in range(n):
    if a[i] >= b[i]:
      ans += b[i]
    else:
      ans += a[i]
      b[i] -= a[i]
      if a[i+1] >= b[i]:
        ans += b[i]
        a[i+1] -= b[i]
      else:
        ans += a[i+1]
        a[i+1] = 0
  print(ans)
  return

if __name__ == "__main__":
  resolve()


Measured memory_bytes: 18380
import java.util.Scanner;

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

		int[] num = new int[w + 1];
		for (int i = 1; i < (w + 1); i++) {
			num[i] = i;
		}

		int n = sc.nextInt();

		for (int i = 0; i < n; i++) {
			String str = sc.next();
			String[] ab = str.split(",");
			int a = Integer.parseInt(ab[0]);
			int b = Integer.parseInt(ab[1]);
			int save = num[b];
			num[b] = num[a];
			num[a] = save;
		}

		for (int i = 1; i < w + 1; i++) {
			System.out.println(num[i]);
		}
	}
}

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

#define INF 1e9
using namespace std;
typedef long long ll;

int even[100010] = {};
int odd[100010] = {};

int main() {

    int n; cin >> n;

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

        if (i & 1) {
            ++odd[v];
        } else {
            ++even[v];
        }
    }

    int max_e = 0;
    int max_o = 0;
    int second_e = 0;
    int second_o = 0;

    int max_e_i;
    int max_o_i;
    int second_e_i;
    int second_o_i;

    for (int i = 0; i < 100010; ++i) {
        max_e = max(max_e, even[i]);
        if (max_e == even[i]) {
            max_e_i = i;
        }
    }

    for (int i = 0; i < 100010; ++i) {
        if (i != max_e_i) {
            second_e = max(second_e, even[i]);
        }
        if (second_e == even[i]) {
            second_e_i = i;
        }
    }

    for (int i = 0; i < 100010; ++i) {
        max_o = max(max_o, odd[i]);
        if (max_o == odd[i]) {
            max_o_i = i;
        }
    }

    for (int i = 0; i < 100010; ++i) {
        if (i != max_o_i) {
            second_o = max(second_o, odd[i]);
        }
        if (second_o == odd[i]) {
            second_o_i = i;
        }
    }

    if (max_e_i != max_o_i) {
        cout << (n/2 - max_e) + (n/2 - max_o) << endl;
    } else {
        int k1 = (n/2 - max_e) + (n/2 - second_o);
        int k2 = (n/2 - second_e) + (n/2 - max_o);

        cout << min(k1, k2) << endl;
    }
}

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

int main(){
    long long H, W;

    cin >> H >> W;

    long long h, w, x;

    if((H % 2) == 0) h = H / 2;
    else h = (H / 2) + 1;


    if((W % 2) == 0) w = W / 2;
    else w = W / 2 + 1;

    if(H == 1 || W == 1) x = 1;
    else if((H % 2) == 0) x = h * W;
    else if((W % 2) == 0) x = w * H;
    else if(H % 2 != 0 && W % 2 != 0) x = h * w + (h-1) * (w-1);
    

    cout << x << endl;


}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;

void solve(long long A, long long B){
    ll K = 50;
    vector<string> GB(K), GW(K);
    REP(i, K){
        GB[i] = string(2*K, '#');
        GW[i] = string(2*K, '.');
    }
    for(ll i=0; i < K; i+=2){
        if(A <= 1) break;
        for(ll j= 0; j< K; j++){
            if(A <= 1) break;
            GB[i][2*j] = '.';
            A--;
        }
    }
    for(ll i=0; i < K; i+=2){
        if(B <= 1) break;
        for(ll j= 0; j< K; j++){
            if(B <= 1) break;
            GW[i][2*j] = '#';
            B--;
        }
    }
    reverse(ALL(GW));
    cout<<"100 100"<<endl;
    REP(i, K) cout<<GB[i]<<endl;
    REP(i, K) cout<<GW[i]<<endl;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)


int main(){
    int n,m;
    cin>>n>>m;
    vector<int> v(n);
    rep(i,n)cin>>v[i];
    rep(i,n)v[i]--;
    
    vector<int> hist(n,0);
    rep(i,n){
        hist[v[i]]++;
    }
    
    vector<int> seg(n,0);
    rep(i,n){
        if(hist[i]==0)continue;
        rep(j,hist[i]){
            if(i-j<0)break;
            seg[i-j]++;
        }
    }
    
    int less = 0;
    for(auto e:seg)if(e==0)less++;
    
    
    rep(i,m){
        int ind,val;
        cin>>ind>>val;
        ind--,val--;
        int bef, aft;
        bef = v[ind];
        aft = val;
        
        if(bef-hist[bef]+1>=0){
            seg[bef-hist[bef]+1]--;
            if(seg[bef-hist[bef]+1]==0)less++;
        }
        hist[bef]--;

        if(aft-hist[aft]>=0){
            if(seg[aft-hist[aft]]==0)less--;
            seg[aft-hist[aft]]++;
        }
        hist[aft]++;
        
        v[ind] = aft;
        
        cout<<less<<endl;
    }
}

Measured memory_bytes: 3840
/*
 * @Author: Wa_King 
 * @Date: 2019-11-23 19:58:12 
 * @Last Modified by: Wa_King
 * @Last Modified time: 2019-11-23 20:57:05
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define fi first
#define se second
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
const int mod = 1e9 + 7;
const int maxn = 2e7 + 10;
const int inf = 0x3f3f3f3f;
int book[maxn],top=0;
int d[200005];
ll c[200005],ans=0,w[11];
void solve(int a,ll b)
{
    if(b==1)
    {
        book[top++]=a;
        return ;
    }
    if(a*2>=10)
    {
        if(b&1) book[top++]=a,b--;
        ans+=b;
        b/=2;
        a=w[a];
        solve(a,b);
    }
    else
    {
        if(b&1) book[top++]=a,b--;
        ans+=b/2;
        a*=2;
        b/=2;
        solve(a,b);
    }
    
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    int m;
    cin>>m;
    rep(i,1,m) cin>>d[i]>>c[i];
    rep(i,5,9)
    {
        int x=i*2;
        w[i]=x%10+x/10;
    }
    rep(i,1,m) solve(d[i],c[i]);
    rep(i,0,top-2)
    {
        ans++;
        book[i+1]+=book[i];
        if(book[i+1]>=10)
        {
            ans++;
            book[i+1]=book[i+1]/10+book[i+1]%10;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

Measured memory_bytes: 16640
s = input()
K = int(input())

arr = []
sn = len(s)
for i in range(1, K+1):
  for j in range(0, sn):
    if i+j <= sn:
	    arr.append(s[j:i+j])
    else:
      break
unique_arr = sorted(list(set(arr)))

print(unique_arr[K-1])


Measured memory_bytes: 5068
inputs = input().split()
inputs_int = []
for i in inputs:
    inputs_int.append(int(i))

df1 = inputs_int[0] - inputs_int[1]
df2 = inputs_int[1] - inputs_int[2]

if df1 < 0 and df2 < 0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 5600
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define INF ((1LL<<62)-(1LL<<31))
#define min(p,q)((p)<(q)?(p):(q))

int d[26][26];

//辺の情報を個別に持つタイプ
typedef struct edge{int s,g,c;}E;
typedef struct graph{
	int vcnt,ecnt;
	E  e[1000];//適宜変える(ecnt)
	int inv[1000];//逆辺のindex(ecnt)
	int id[30];//適宜変える(vcnt)
}G;
G g;

int esort(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).s<(*q).s)return -1;
	if((*p).s>(*q).s)return  1;
	if((*p).g<(*q).g)return -1;
	return 1;
}
void makeinvedge(){
	//逆辺とidx
	rep(i,0,g.ecnt){
		int l=0,r=g.ecnt;
		while(r-l>1){
			int m=(l+r)/2;
			if(g.e[m].s<g.e[i].g||(g.e[m].s==g.e[i].g&&g.e[m].g<=g.e[i].s))l=m;
			else r=m;
		}
		if(g.e[l].s!=g.e[i].g||g.e[l].g!=g.e[i].s){
			g.e[g.ecnt].s=g.e[i].g;
			g.e[g.ecnt].g=g.e[i].s;
			g.e[g.ecnt].c=0;
			g.ecnt++;
		}
	}
	qsort(g.e,g.ecnt,sizeof(E),esort);
	rep(i,0,g.ecnt){
		int l=0,r=g.ecnt;
		while(r-l>1){
			int m=(l+r)/2;
			if(g.e[m].s<g.e[i].g||(g.e[m].s==g.e[i].g&&g.e[m].g<=g.e[i].s))l=m;
			else r=m;
		}
		g.inv[i]=l;
	}
}
void readgraph(int v){
	//適宜変える
	g.vcnt=27;
	g.ecnt=26*26;
	for(int i=0;i<26;i++)for(int j=0;j<26;j++){
		g.e[i*26+j].s=i;
		g.e[i*26+j].g=j==v?26:j;
		g.e[i*26+j].c=d[i][j];
	}
	qsort(g.e,g.ecnt,sizeof(E),esort);
	makeinvedge();

	int p=0;
	rep(i,0,g.vcnt){
		while(p<g.ecnt&&g.e[p].s<i)p++;
		g.id[i]=p;
	}
	g.id[g.vcnt]=g.ecnt;//番兵
}


//dinic O(VVE)
//ソースs,シンクtを引いてsからtへの最大流を返す
//*
int dist[1010];//ソースからの距離
int checked[1010];//dfsの行き止まりフラグ
void dinicbfs(int s){
	rep(i,0,g.vcnt)dist[i]=-1;
	dist[s]=0;
	//まだ流せる辺だけを使ってbfs
	int que[1010],qcnt=0;
	que[qcnt++]=s;
	rep(q,0,qcnt){
		int v=que[q];
		rep(i,g.id[v],g.id[v+1])if(g.e[i].c>0&&dist[g.e[i].g]==-1){
			dist[g.e[i].g]=dist[v]+1;
			que[qcnt++]=g.e[i].g;
		}
	}
}
ll dinicdfs(int a,int t,ll m){
	//aはm受け取ってる(⇔aから最大m流せる)
	//いくら流せるかを返す
	if(a==t)return m;
	if(checked[a])return 0;
	ll ans=0;
	checked[a]=1;
	rep(i,g.id[a],g.id[a+1])if(g.e[i].c>0&&dist[g.e[i].g]>dist[a]){
		int b=g.e[i].g;
		ll addedflow=dinicdfs(b,t,min(m,g.e[i].c));
		if(addedflow){
			g.e[i].c-=addedflow;
			g.e[g.inv[i]].c+=addedflow;
			checked[a]=0;
			ans+=addedflow;
			m-=addedflow;
			if(m<=0)break;
		}
	}
	return ans;
}
//ソース,シンク
ll dinic(int s,int t){
	ll ans=0;
	int flag=1;
	while(flag){
		flag=0;//更新フラグ
		dinicbfs(s);
		while(!checked[s]){
			ll addedflow=dinicdfs(s,t,INF);
			ans+=addedflow;
			if(addedflow)flag=1;
		}
		rep(i,0,g.vcnt)checked[i]=0;
	}
	return ans;
}
//*/

int out[26],in[26];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		char s[110];
		scanf(" %s",s);
		int len=strlen(s);
		d[s[0]-'a'][s[len-1]-'a']++;
		out[s[0]-'a']++;
		in[s[len-1]-'a']++;
	}
	for(int i=0;i<26;i++){
		readgraph(i);
		if(in[i]&&dinic(i,26)==out[i])printf("%c\n",'a'+i);
	}
}


Measured memory_bytes: 2148
#include<stdio.h>

#define H 250
#define NIL -200000
 
int main()
{


int A[H], i, n;

for(i = 0 ; i < H ; i++)
  A[i] = NIL;

scanf("%d",&n);

for(i = 0 ; i < n ; i++)
  scanf("%d",&A[i]);
  
for(i = 0 ; i < n ; i++){
printf("node %d: ",i+1);
if(2*i+1 < n){
if(i ==0 )    
  printf("key = %d, left key = %d, right key = %d, \n",A[i],A[i + 1],A[i +2]);
 else if(A[2*(i+1)] != NIL  &&  A[2*i+1] != NIL) 
   printf("key = %d, parent key = %d, left key = %d, right key = %d, \n",A[i],A[(i-1)/2],A[2*i+1],A[2*(i+1)]);
 else if(A[2*(i+1)] == NIL  &&  A[2*i+1] != NIL)
   printf("key = %d, parent key = %d, left key = %d, \n",A[i],A[(i-1)/2],A[2*i+1]);
 else 
   printf("key = %d, parent key = %d, \n",A[i],A[(i-1)/2]);
} 
 else printf("key = %d, parent key = %d, \n",A[i],A[(i-1)/2]);
}
return 0;
}

Measured memory_bytes: 596
//Problem B
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1000005;
int n,k,t,f[N];ll a[N],x[N],S;

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1];
    for(int i=1;i<=n;i++)for(int j=0;j<i;j++)x[++t]=a[i]-a[j],f[t]=1;
    //for(int i=1;i<=t;i++)printf("%d\n",x[i]);
    for(int i=40;~i;i--){
        int c=0;for(int j=1;j<=t;j++)if( (1ll<<i&x[j])&&f[j])++c;
        if(k<=c)for(int j=1;j<=t;j++)if(!(1ll<<i&x[j])&&f[j])f[j]=0;
        if(k<=c)S|=1ll<<i;
        //printf("\n\n%d %d\n",i,c);if(k<=c)printf("ok\n");
        //for(int j=1;j<=t;j++)if(f[j])printf("%d\n",x[j]);
    }
    printf("%lld",S);
    return 0;
}

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

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

	int A = 0, B = 0, C = 0;
	int SA = 0, SB = 0, SC = 0;
	int NSA = 0, NSB = 0, NSC = 0;
	cin >> SA >> SB >> SC;
	N--;
	while (N--) {
		cin >> A >> B >> C;
		NSA = max(SB + A, SC + A);
		NSB = max(SA + B, SC + B);
		NSC = max(SA + C, SB + C);
		SA = NSA;
		SB = NSB;
		SC = NSC;
	}

	cout << max(SA, max(SB, SC)) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k,c,g;
  vector<int> book[11];
  cin >> n >> k;
  for(int i=0;i<n;i++){
    cin >> c >> g;
    book[g].push_back(c);
  }
  int dp[11][2001]={};
  for(int i=1;i<=10;i++){
    sort(book[i].begin(),book[i].end(),greater<int>());
    for(int j=1;j<book[i].size();j++) book[i][j] += book[i][j-1];
    
    for(int j=1;j<=k;j++){
      dp[i][j] = max(dp[i][j],dp[i-1][j]);
      for(int l=0;l<book[i].size();l++){
	int sum = l+1;
	if(j >= sum) dp[i][j] = max(dp[i][j],dp[i-1][j-sum]+book[i][l]+(sum)*l);
      }
    }    
  }
  cout << dp[10][k] << endl;
  return (0);
}

Measured memory_bytes: 3240
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define iter vector<int>::iterator
#define mod 1000000007
#define inf 1e12

int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,k;
    cin>>n>>k;

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

    int dp[k+1]={0};//dp[i] stores whether game will end with taro's chance or not given i number of stones 

    for(int i=0;i<n;i++)
    {
        dp[a[i]]=1;
    }

    for(int i=0;i<=k;i++)
    {
        if(dp[i]==0)
        {
            for(int j=0;j<n;j++)
            {
                if(i-a[j]>=0)
                {
                    if((dp[i-a[j]]==0 && dp[a[j]]==1)||(dp[i-a[j]]==1 && dp[a[j]]==0))
                    {
                        dp[i]=1;
                    }
                }
            }
        }
    }

    if(dp[k]==1)
    {
        cout<<"First"<<"\n";
    }
    else 
    {
        cout<<"Second"<<"\n";
    }

}

Measured memory_bytes: 1024
i=->{gets.split.map &:to_i};w,h,n=i[];l=b=0;n.times{x,y,a=i[];a<2&&l<x&&l=x;a==2&&x<w&&w=x;a==3&&b<y&&b=y;a>3&&y<h&&h=y};p l<w&&b<h ?(w-l)*(h-b):0

Measured memory_bytes: 1916
#include <bits/stdc++.h>
//#include <atcoder/all>
#define ll long long int
#define MOD 1000000007
#define P pair<ll,ll>
#define INF 1000000000000000000

//using namespace atcoder;
using namespace std;

int main(void){
  ll l;
  cin >> l;
  
  ll n = 0;
  while ((1 << n) <= l){
    n++;
  }
  vector<tuple<ll,ll,ll>> m(0);
  for (ll i = 0; i < n-1; i++){
    m.emplace_back(make_tuple(i+1, i+2, 0));
    m.emplace_back(make_tuple(i+1, i+2, (1LL << i)));
  }
  ll t = l % (1LL << (n-1));

  ll k = 0;
  for (ll i = 0; i < n; i++){
    if ((t >> i) & 1){
      k |= (1 << i);
      m.emplace_back(make_tuple(i+1, n, (1LL << (n-1)) + t - k));
    }
  }
  cout << n << " " << m.size() << endl;
  for (auto p : m){
    ll u = get<0>(p);
    ll v = get<1>(p);
    ll w = get<2>(p);

    cout << u << " " << v << " " << w << endl;
  }


  return 0;
}


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

int main(){
  int n,k,p;
  string s1,s2,ans;
  cin>>n;
  while(n--){
    ans.clear();
    p=0;
    cin>>s1;
    cin>>s2;
    reverse(s1.begin(),s1.end());
    reverse(s2.begin(),s2.end());
    k=max(s1.size(),s2.size());
    for(int i=s1.size();i<k;i++)s1+='0';
    for(int i=s2.size();i<k;i++)s2+='0';
    for(int i=0;i<k;i++){
      int sum=s1[i]-'0'+s2[i]-'0'+p;
      ans+=(sum%10)+'0';
      p=sum/10;
    }
    if(p)ans+=p+'0';
    reverse(ans.begin(),ans.end());
    if(ans.size()<=80)cout<<ans<<endl;
    else cout<<"overflow"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1204
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,x) memset(a,x,sizeof(a))
#define SZ(x) ((int)(x).size())
#define lson rt<<1
#define rson rt<<1|1
#define pb push_back
#define fi first
#define se second
#define what_is(x) cerr<<#x<<" "<<x<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
template <typename T>
inline void _read(T& x){
    cin>>x;
}
void R(){}
template <typename T,typename... U>
void R(T&head,U&... tail){
    _read(head);
    R(tail...);
}

template <typename T>
inline void _write(const T& x){
    cout<<x<<' ';
}
void W(){cout<<endl;}
template <typename T,typename... U>
void W(const T&head,const U&... tail){
    _write(head);
    W(tail...);
}

void go();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    go();
    return 0;
}
/****************ackun*********************/
void go(){
    int n,k;
    R(n,k);
    queue<pii> que;
    string s;
    R(s);
    int len=s.length();
    s+="2";
    vector<pii> a;
    int num=1;
    rep(i,1,len){
        if(s[i]==s[i-1]){
            num++;
        }else{
            a.pb({s[i-1]-'0',num});
            num=1;
        }
    }
    int cnt=0;
    int ans=0;
    int sum=0;
    for(auto x:a){
        if(x.fi==1){
            que.push(x);
            sum+=x.se;
        }else{
            que.push(x);
            sum+=x.se;
            cnt++;
            while(cnt>k){
                pii temp=que.front();
                que.pop();
                sum-=temp.se;
                if(temp.fi==0){
                    cnt--;
                }
            }
        }
        ans=max(ans,sum);
    }
    W(ans);
}


Measured memory_bytes: 1604
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;

map<ll, int> prime_factor(ll n) {
  map<ll, int> ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll a,b; cin >> a >> b;
  auto pfa = prime_factor(a);
  auto pfb = prime_factor(b);
  int ans = 1;
  for(auto pf: pfa){
    if(min(pf.second, pfb[pf.first])>0) ans++;
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
    string S;
    cin >> S;
    vector<bool>hantei(26);
    for(int i = 0; i < 26; i++) {
        hantei[i] = true;
    }
    for(int i = 0; i < S.size(); i++) {
        hantei[S[i]-'a'] = false;
    }
    for(int i = 0; i < 26; i++) {
        if(hantei[i]) {
            cout << (char)(i+'a') << endl;
            return 0;
        }
    } 
    cout << "None" << endl;
}

Measured memory_bytes: 512
"use strict";
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}

console.log(main());
function main(){
  var n = o.a();
  var s = o.m(n,1);
  var x = o.a(1);
  var ans = 0;
  var f = 0;
  for(var i = 0; i < n; i++){
    if(s[i][0] === x)f = 1, ans -= s[i][1];
    if(f === 0)continue;
    ans += +s[i][1];
  }
  return ans;
}

Measured memory_bytes: 21192
n, m = map(int, input().split())
bins = (m + 1) * [0]
for i in range(n):
    inputs = list(map(int, input().split()))
    for j in range(1, len(inputs)):
        bins[inputs[j]] += 1

ans = 0
for i in range(m + 1):
    if bins[i] == n:
        ans += 1
print(ans)


Measured memory_bytes: 3060
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

void solve() {
  int s, w;
  scan(s, w);
  if (s <= w) {
    print("unsafe");
  } else {
    print("safe");
  }
}

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


Measured memory_bytes: 3164
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>

#define rep(i,n) for(int i=0;i<(n);i++)

typedef long long ll;

using namespace std;



int main() {

	int N;
	cin >> N;
	vector<int> p(N);

	rep(i, N) {
		cin >> p.at(i);
	}
	sort(p.begin(), p.end());
	reverse(p.begin(), p.end());

	int total=p.at(0)/2;
	

	for (int i = 1; i < N;++i) {
		total += p.at(i);
	}

	cout << total << endl;


	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;

const int N=109;

int n,m,x,y;
char g[N][N];
int f[2][N][N][N];
int row[N][N],col[N][N];

inline void chkmax(int &a,int b){if(a<b)a=b;}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",g[i]+1);
		for(int j=1;j<=m;j++)
		{
			col[j][i]=col[j][i-1];
			row[i][j]=row[i][j-1];
			if(g[i][j]=='E')
				x=i,y=j;
			else if(g[i][j]=='o')
				row[i][j]++,col[j][i]++;
		}
	}

	for(int i=0;i<x;i++)
	{
		int fl=i&1;
		memset(f[fl],0,sizeof(f[fl]));
		for(int j=0;j<=n-x;j++)
			for(int k=0;k<y;k++)
				for(int l=0;l<=m-y;l++)
				{
					chkmax(f[fl][j][k][l],f[fl^1][j][k][l]+(x-i-1>j?row[x-i-1][min(y+l,m-k)]-row[x-i-1][max(y-k-1,l)]:0));
					chkmax(f[fl^1][j+1][k][l],f[fl^1][j][k][l]+(x+j+1<=n-i?row[x+j+1][min(y+l,m-k)]-row[x+j+1][max(y-k-1,l)]:0));
					chkmax(f[fl^1][j][k+1][l],f[fl^1][j][k][l]+(y-k-1>l?col[y-k-1][min(x+j,n-i)]-col[y-k-1][max(x-i-1,j)]:0));
					chkmax(f[fl^1][j][k][l+1],f[fl^1][j][k][l]+(y+l+1<=m-k?col[y+l+1][min(x+j,n-i)]-col[y+l+1][max(x-i-1,j)]:0));
				}
	}

	printf("%d\n",f[x-1&1][n-x][y-1][m-y]);
	return 0;
}


Measured memory_bytes: 10496
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define PN cout << endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (n-1); i >= (int)(m); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - (a)) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - (a)) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

/*
ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
*/

/*
vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}
*/

/*
ll ncr[100][100];
ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

ll npr[100][100]={};
ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

ll nHr(int n,int r){ret nCr(n+r-1,r);}
*/

///////////////////////////////////////////////////////////////////////////



int main(){
  
    string s[]  = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
    string a;
    cin >> a;
    rep(i,0,7){
	if(a == s[i]){
	    P(7 - i);
	}
    }
    return  0;
}


Measured memory_bytes: 256
/**
*    author:  souzai32
*    created: 13.08.2020 01:17:53
**/

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

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

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

int main() {

    long a,b;
    cin >> a >> b;
    long num=gcd(a,b);
    int count=1;

    for(long i=2; i*i<=num; i++){
        if(num%i!=0) continue;
        while(num%i==0){
            num/=i;
        }
        count++;
    }
    if(num!=1) count++;

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 3656
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include <climits>
using namespace std;

int main()
{
  long long int A, B, C, D;
  cin >> A >> B >> C >> D;
  long long int count = 0;
  long long int a, b;
  a = C;
  b = D;
  long long int x = C * D;

  if(a<b){
    long long int tmp = a;
    a = b;
    b = tmp;
  }
  long long int r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  long long int cb = x/b;

  long long int v_1, v_2, v_3;
  v_1 = (B / C - (A-1) / C);
  v_2 = (B / D - (A-1) / D);
  v_3 = (B / cb - (A-1) / cb);
  count = (B - (A-1)) - (v_1 + v_2 - v_3);
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 764
using System;

namespace _153232
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] ABC = Console.ReadLine().Split();
            int a = int.Parse(ABC[0]);
            int b = int.Parse(ABC[1]);
            if ((a + b) % 2 == 0) { Console.WriteLine(Math.Abs((a + b) / 2)); }
            else { Console.WriteLine("IMPOSSIBLE"); }
        }
    }
}


Measured memory_bytes: 13140
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
var R="qwertasdfgzxcvb".split("");
for(var i=0;i<Arr.length;i++){
   var str=Arr[i];
   if(str=="#")break;
   var arr=str.split("");
   var hand=(R.indexOf(arr.shift())!=-1)?0:1;
   var cnt=0;
   arr.forEach(function(v){
      var HAND=(R.indexOf(v)!=-1)?0:1;
      if(hand!=HAND){
      hand=HAND;
      cnt++;
      }
   });
   console.log(cnt);
}

Measured memory_bytes: 9672
#include<bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define endl "\n"
#define loop(i,s,e) for(int i=s;i<e;i++)
#define int long long
#define mp make_pair
#define pii pair<int,int>
#define mset(a,f)  memset(a , f , sizeof(a))
#define pb push_back
const int N = 2e6 + 6;
const int M = 1e9 + 7;
int A[N];
int n;

void solve()
{
	int a;
	cin >>a ;

	int k = a/500;
	a %= 500;
	int r = a/5;

	cout << 1000*k + 5*r;
}
 
int32_t main()
{
 
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
    

 	int t = 1;
 	// cin >> t;
 	while(t--)solve();
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using P = pair<ll,ll>;
constexpr ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REPS(i,n) for(ll (i)=1;(i)<=(n);(i)++)
#define RREP(i,n) for(ll (i)=(n-1);(i)>=0;(i)--)
#define RREPS(i,n) for(ll (i)=(n);(i)>0;(i)--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());

template<class T> inline void chmin(T& a, T b){
    if (a > b){
        a = b;
    }
}

template<class T> inline void chmax(T& a, T b){
    if (a < b){
        a = b;
    }
}

/* UnionFind */
struct UnionFind {
    vector<ll> par,rank,siz;

    UnionFind(ll N) : par(N),rank(N),siz(N) {
        REP(i,N){
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
        }
    }

    ll root(ll x) {
        return par[x] == x ? x : par[x] = root(par[x]);
    }

    void unite(ll x, ll y) {
        ll rx = root(x);
        ll ry = root(y);
        if (rx == ry) return;
        if(rank[rx] < rank[ry]){
            par[rx] = ry;
            siz[ry] += siz[rx];
        }else{
            par[ry] = rx;
            siz[rx] += siz[ry];
            if(rank[rx] == rank[ry])rank[rx]++;
        }
    }

    ll siza(ll x){
        return siz[x];
    }
};

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(12);
    ll N,M;
    cin >> N >> M;
    UnionFind uf(N);
    REP(i,M){
        ll A,B;
        cin >> A >> B;
        A--;
        B--;
        uf.unite(A,B);
    }
    ll ma = 0;
    REP(i,N){
        chmax(ma,uf.siza(i));
    }
    cout << ma << "\n";
}

Measured memory_bytes: 7944
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    def Find_Root(self,x):
        if self.root[x]<0:return x
        else:
            self.root[x]=self.Find_Root(self.root[x])
            return self.root[x]

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def size(self,x):
        return -self.root[self.Find_Root(x)]

    def members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(self.roots())


n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

UnionFind=UnionFind(n+1)
for a,b in AB:
    UnionFind.Unite(a,b)

ans=0
for i in range(1,n+1):
    ans=max(ans,UnionFind.size(i))
print(ans)

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

using namespace std;

#define INF 1e9

int field[5000][5],tmp[5000][5];

void down(){
  memset(tmp,0,sizeof(tmp));
  for(int j = 0 ; j < 5 ; j++){
    int p = 4999;
    for(int i = 4999 ; i >= 0 ; i--){
      if(field[i][j] == -1) continue;
      tmp[p--][j] = field[i][j];
    }
  }
  for(int i = 0 ; i < 5000 ; i++){
    for(int j = 0 ; j < 5 ; j++){
      field[i][j] = tmp[i][j];
    }
  }
}

void remove(){
  bool flg = false;
  for(int i = 0 ; i < 5000 ; i++){
    int cnt = 0;
    for(int j = 0 ; j < 5 ; j++,cnt++){
      if(!field[i][j]) break;
    }
    if(cnt == 5){
      flg = true;
      for(int j = 0 ; j < 5 ; j++){
        field[i][j] = -1;
      }
    }
  }
  
  if(flg){
    down();
  }
}

int main(){
  int N,d,p,q;

  while(cin >> N,N){
    memset(field,0,sizeof(field));
    for(int i = 0 ; i < N ; i++){
      cin >> d >> p >> q; q--;

      if(d == 1){
        int min = INF;
        for(int j = q ; j < p+q ; j++){
          for(int i = 0 ; i < 5000 ; i++){
            if(i == 4999 || field[i+1][j] == 1){
              min = std::min(min,i);
              break;
            }
          }
        }
        for(int j = q ; j < p+q ; j++){
          field[min][j] = 1;
        }
      }else{
        for(int i = 0 ; i < 5000 ; i++){
          if(i == 4999 || field[i+1][q] == 1){
            for(int j = 0 ; j < p ; j++){
              field[i-j][q] = 1;
            }
            break;
          }
        }
      }
      remove();
    }
    int ans = 0;
    for(int i = 0 ; i < 5000 ; i++){
      for(int j = 0 ; j < 5 ; j++){
        if(field[i][j] == 1) ans++;
      }
    }
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 1364
/*-- ILSH  --*/
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define pb push_back 
#define pop pop_back
#define mp make_pair
#define vii vector < int >
#define vll vector < ll > 
#define dt cout<<"HERE\n";
#define pii pair < int , int >
#define pll pair < ll , ll >
#define vpi vector < pll >
#define vpl vector < pll >
#define fi first
#define se second 
#define sz size 
#define len length 

const ll inf=1e18+1e17;
const ll mod =1e9+7;
//const ll mod = 998244353;

ll modInverse(ll a,ll m){ll m0=m;ll y=0,x=1;if(m == 1)return 0;while(a> 1){ll q=a/m;ll t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}  
ll powm(ll a,ll b){a=a%mod;ll res=1;while(b){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return (res%mod);}


const ll N =1e3+6;



void solve(){

	int n,m;
	cin>>n>>m;
	cout<<( n*( n-1)/2)+( m*(m-1))/2<<'\n';


}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie( NULL);
	// #ifndef ONLINE_JUDGE
	// 	cin.tie(NULL);
	// 	freopen ("INPUT.txt" , "r" , stdin);
	// 	freopen ("OUTPUT.txt", "w" , stdout);
	// #endif	
    ll t=1;
   // cin>>t;
    for (ll i=1;i<=t;i++){
    //	cout<<"Case #"<<i<<": ";
    	solve();
 	}
}

Measured memory_bytes: 3688
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, m;
string mp[N];
int f[N][N], g[N][N], u[N][N], d[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> mp[i];
    for (int i = 1; i < n; i++)
    {
        if (mp[i][0] == mp[i - 1][0])
            f[i][0] = 1, g[i][0] = 0;
        else
            f[i][0] = 0, g[i][0] = 1;
        for (int j = 1; j < m; j++)
        {
            if (mp[i][j] == mp[i - 1][j])
            {
                f[i][j] = f[i][j - 1] + 1;
                g[i][j] = 0;
            }
            else
            {
                f[i][j] = 0;
                g[i][j] = g[i][j - 1] + 1;
            }
        }
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            f[i][j] = max(f[i][j], g[i][j]);
    for (int j = 0; j < m; j++)
    {
        u[0][j] = 0;
        for (int i = 1; i < n; i++)
        {
            int k = i;
            while (k && f[i][j] <= f[k - 1][j])
                k = u[k - 1][j];
            u[i][j] = k;
        }
        d[n - 1][j] = n - 1;
        for (int i = n - 2; i >= 0; i--)
        {
            int k = i;
            while (k < n - 1 && f[i][j] <= f[k + 1][j])
                k = d[k + 1][j];
            d[i][j] = k;
        }
    }
    /*
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            printf("f(%d,%d) = %d\n", i, j, f[i][j]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            printf("u(%d,%d) = %d\n", i, j, u[i][j]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            printf("d(%d,%d) = %d\n", i, j, d[i][j]);
    */
    int ans = max(n, m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ans = max(ans, f[i][j] * (d[i][j] - u[i][j] + 2));
    printf("%d\n", ans);
    return 0;
}

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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = 1e9 + 100;
const long long LLINF = 2e18 + 129;
const long long MOD = 1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

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

    string s;
    cin >> s;

    if(s[0] == s.back() && s[0] == 'x'){
        cout << 'x' << endl;
    }else{
        cout << 'o' << endl;
    }

    return 0;
}


Measured memory_bytes: 3224
#include<iostream>
using namespace std;
int main(){
  int n;
  while(cin>>n,n){
    int min=1000000;
    for(int i=0;i*i<=n;i++)for(int j=0;j*j*j<=n;j++)if(j*j*j+i*i<=n&&min>i+j+n-j*j*j-i*i)min=i+j+n-j*j*j-i*i;
    cout<<min<<endl;
  }
  return 0;
}

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

using namespace std;

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

#define INF 2<<29
#define F first
#define S second

int main(){
  int n;
  int sum=0;
  int ansp;
  int p,d1,d2;
  while(1){
    scanf("%d",&n);
    if(n==0) break;
    sum=0;
    for(int i=0;i<n;i++){
      scanf("%d %d %d",&p,&d1,&d2);
      if(sum<d1+d2){
	ansp=p;
	sum=d1+d2;
      }
    }
    printf("%d %d\n",ansp,sum);
  }

  return (0);
}



Measured memory_bytes: 3140
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

template<ll MOD = 1000000007>
class ModInt {
    ll n;
    static constexpr ModInt pow(const ModInt x, ll p) {
        ModInt<MOD> ans = 1;
        for (ModInt<MOD> m = x; p > 0; p /= 2, m *= m) {
            if (p % 2) ans *= m;
        }
        return ans;
    }
    ModInt constexpr inverse() const {
        return ModInt::pow(*this, MOD - 2);
    }

public:
    ModInt()
        : n(0) {}
    ModInt(ll _n)
        : n(((_n % MOD) + MOD) % MOD) {}
    ModInt operator+=(const ModInt &m) {
        n += m.n;
        if (n >= MOD) n -= MOD;
        return *this;
    }
    ModInt operator-=(const ModInt &m) {
        n -= m.n;
        if (n < 0) n += MOD;
        return *this;
    }
    ModInt operator*=(const ModInt &m) {
        n *= m.n;
        if (n >= MOD) n %= MOD;
        return *this;
    }
    ModInt operator/=(const ModInt &m) {
        (*this) *= m.inverse();
        return *this;
    }
    friend ModInt operator+(ModInt t, const ModInt &m) {
        return t += m;
    }
    friend ModInt operator-(ModInt t, const ModInt &m) {
        return t -= m;
    }
    friend ModInt operator*(ModInt t, const ModInt &m) {
        return t *= m;
    }
    friend ModInt operator/(ModInt t, const ModInt &m) {
        return t /= m;
    }
    ModInt operator=(const ll l) {
        n = l % MOD;
        if (n < 0) n += MOD;
        return *this;
    }
    friend ostream &operator<<(ostream &out, const ModInt &m) {
        out << m.n;
        return out;
    }
    friend istream &operator>>(istream &in, ModInt &m) {
        ll l;
        in >> l;
        m = l;
        return in;
    }
};
using mint = ModInt<>;
mint operator"" _m(unsigned long long m) {
    return mint(m);
}

int SZ = 2000200;
vector<mint> fact(SZ, 1);

mint nCr(int n, int r) {
    return fact[n] / fact[r] / fact[n - r];
}

mint calc(int r, int c) {
    return (nCr(c + r + 2, r) * (c + 2) - r - 1) / (r + 1);
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    REP(i, 0, SZ - 1) {
        fact[i + 1] = fact[i] * (i + 1);
    }
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    cout << calc(r2, c2) - calc(r1 - 1, c2) - calc(r2, c1 - 1) + calc(r1 - 1, c1 - 1) << endl;
    return 0;
}


Measured memory_bytes: 15872
N,M = gets.split(' ').map(&:to_i)
@xy = M.times.map{ gets.split(' ').map(&:to_i) }

@xy.sort_by!{|x| x[0]}

@parent = Array.new(N+1,&:itself)
@rank = Array.new(N+1,0)
#puts @parent

def anc(x)
  #puts "x=#{x}"
  #puts "parent[2]=#{@parent[2]}"
  if @parent[x]==x
    return x
  else
    #puts "x=#{x}"
    x=anc(@parent[x])
  end
  return x
end


M.times do |i|
  x=@xy[i][0]
  y=@xy[i][1]
  x_can = anc(x)
  y_can = anc(y)
  #puts "x_can=#{x_can},y_can=#{y_can}"
=begin
  if x_can<y_can
    senzo=x_can
  else
    senzo=y_can
  end
=end
  if @rank[x_can]>=@rank[y_can]
    @parent[y_can]=x_can
    @rank[x_can]+=1 if @rank[x_can]==@rank[y_can]
  else
    @parent[x_can]=@parent[y_can]
  end
  #@parent[x]=senzo
  #@parent[y]=senzo
  #puts @parent
  #puts "aaa"
end
ans = 0
for i in 0..N-1
  cnt = N-i
  senzo = anc(cnt)
  @parent[senzo] = senzo
  if senzo==cnt
    ans+=1
  end
end
puts ans

#puts @parent


Measured memory_bytes: 12668