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

using namespace std;

int a[200000];
int b[200000];

int main() {

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(a, a + n);
	for (int i = 0; i < n; ++i) {
		if (a[n - 1] != b[i]) cout << a[n - 1] << '\n';
		else cout << a[n - 2] << '\n';
	}
	return 0;	
}

Measured memory_bytes: 3200
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define PR pair
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define REP(i, x, y)   for(int i = (int)(x); i <= (int)(y); i++)
#define FOR(i, x, y)   for(int i = (int)(x); i <  (int)(y); i++)
#define PER(i ,x, y)  for(int i = (int)(x); i >= (int)(y); i--)
#define CH	         ch = getchar()
#define Exit(...)    printf(__VA_ARGS__), exit(0)
#define dln()        fprintf(stderr,"\n")
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef double	  db;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI > VII;
typedef PR<int,int> PII;
typedef vector<PII> VPI;
const	int inf=2e9;
const	LL Inf=1e10;
const	int P=1e9+7;
const	int N=200005;

inline LL IN(){
	LL x = 0;
	int ch = 0, f = 0;
	for (CH; ch != -1 && (ch < 48 || ch > 57); CH) f = (ch == '-');
	for (; ch >= 48 && ch <= 57; CH) x = (x << 1) + (x << 3) + ch - '0';
	return f ? (-x) : x;
}
template<typename T> inline int chkmin(T &a, const T &b){if(b < a) return a = b, 1; return 0;}
template<typename T> inline int chkmax(T &a, const T &b){if(b > a) return a = b, 1; return 0;}

void renew(int &x, const int &y){
	x += y;
	if(x >= P) x -= P;
	if(x <  0) x += P;
}

int Pow(int x, int y, int p){
	int a = 1;
	for (; y; y >>= 1, x = (LL)x * x %p) if(y & 1) a=(LL)a * x%p;
	return a;
}

int n;
int mxd[N], sed[N], mad[N], gg[N], hev[N];
struct edge{
	int v, pre;
}e[N << 1]; int dex, adj[N];
int fa[N];

void dfs(int x){
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == fa[x]) continue;
		fa[v] = x;
		dfs(v);
		if(mxd[v] + 1 > mxd[x]){
			sed[x] = mxd[x];
			hev[x] = v;
			mxd[x] = mxd[v] + 1;
		}else
		if(mxd[v] + 1 > sed[x]){
			sed[x] = mxd[v] + 1;
		}
	}
}

void dp(int x){
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == fa[x]) continue;
		if(v == hev[x]){
			gg[v] = max(gg[x], sed[x]) + 1;
		}else{
			gg[v] = max(gg[x], mxd[x]) + 1;
		}
		dp(v);
	}
}

int hg[N], lo[N];
LL ans = 1;
char s[N];

void work(int x, int par){
	mad[x] = 0;
	if(s[x] == '1') lo[x] = 0; else lo[x] = 1 << 30;
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == par) continue;
		work(v, x);
		mad[x] = max(mad[x], mad[v] + 1);
		lo[x] = min(lo[x], lo[v] - 1);
	}
	hg[x] = min(mad[x] + 1, mxd[x] - 1);
	ans += max(0, hg[x] - lo[x] + 1);
	lo[x] = max(lo[x], hg[x] + 1);
	if(lo[x] == mxd[x]) lo[x] = 1 << 30;
}

int main(){
	scanf("%d", &n);
	REP(i, 1, n - 1){
		int x, y;
		scanf("%d%d", &x, &y);
		e[++dex] = (edge){y, adj[x]}; adj[x] = dex;
		e[++dex] = (edge){x, adj[y]}; adj[y] = dex;
	}
	dfs(1);
	dp(1);
	REP(i, 1, n) mxd[i] = max(mxd[i], gg[i]);
	int rt = min_element(mxd + 1, mxd + n + 1) - mxd;
	scanf("%s", s + 1);
	work(rt, 0);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 17792
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define vll vector<ll>
#define vvll vector<vll>
#define mll map<ll,ll>
#define f(i,m,n) for(i=m;i<n;i++)
#define ee endl
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define take(v,n) for(i=0;i<n;i++) cin>>v[i];
#define print(v,n) for(i=0;i<n;i++) cout<<v[i]<<" ";
#define NO() cout<<"NO"<<endl
#define YES() cout<<"YES"<<endl
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sot(v) sort(v.begin(),v.end());
#define PI 3.14159265   ;
ll mod =1000000007;
bool isPrime(int n)
{
	// Corner cases 
	if (n <= 1)  return false;
	if (n <= 3)  return true;

	// This is checked so that we can skip  
	// middle five numbers in below loop 
	if (n % 2 == 0 || n % 3 == 0) return false;

	for (int i = 5; i*i <= n; i = i + 6)
		if (n%i == 0 || n % (i + 2) == 0)
			return false;

	return true;
}

ll powe(ll x, ll y) {
	ll res = 1;
	while (y > 0) {
		if (y & 1) res =( res * x)%mod;
		y = y >> 1;
		x = (x * x)%mod;
	}
	return res;
}
struct hash_pair {
	template <class T1, class T2>
	size_t operator()(const pair<T1, T2>& p) const
	{
		auto hash1 = hash<T1>{}(p.first);
		auto hash2 = hash<T2>{}(p.second);
		return hash1 ^ hash2;
	}
};
vll d(1000001,1);
void cal()
{
	ll i,j,k;
	for(i=2;i<=1000000;i++)
	{
		for(j=i;j<=1000000;j+=i)
		d[j]++;
	}
}

void solve()
{
	ll i, x, y, j, k, h, n, w, k1, k2, q;
	cin>>n;
	ll ans=0;
	for(i=1;i<n;i++)
	{
		ans+=(d[i]);
	}
	cout<<ans<<ee;
}

int main() {
	cal();
	fast;
	ll i, j, l, k, t, n;
	t=1;
	for (i = 1; i <= t; i++)
	{
		// cout<<"Case #"<<i<<": ";
		solve();
	}
}
// 

Measured memory_bytes: 11000
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cassert>
using namespace std;

string S;

char step(char ch, int offset) {
    if (ch == '?') return 'A';
    return ((ch - 'A') + offset + 26*1000) % 26 + 'A';
}

pair<string, int> parse(int idx) {
    string res = "";
    while (idx < S.size()) {
        if (S[idx] == ']') {
            reverse(res.begin(), res.end());
            idx ++;
            break;
        }

        if (S[idx] == '[') {
            pair<string, int> sub = parse(idx+1);
            res += sub.first;
            idx = sub.second;
            continue;
        }

        int offset = 0;
        while (S[idx] == '+' || S[idx] == '-') {
            offset += (S[idx] == '+') ? 1 : -1;
            ++idx;
        }

        res += string(1, step(S[idx], offset));
        idx++;
    }

    return make_pair(res, idx);
}

void solve(){
    string res;
    pair<string, int> pr = parse(0);
    cout << pr.first << endl;
}

int main(){
    while(1){
        cin >> S;
        if (S == ".") break;
        solve();
    }
}



Measured memory_bytes: 3172
#include <cstdio>
#include <cstring>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)
using namespace std;

int n,a[2010];
bool flag[2010];
struct edge
{
    int v;
    edge *nxt;
} pool[4000100],*tp=pool,*fst[2010];
struct data
{
    int n,a[2010];
    void add(int x)
    {
        repd(i,n,1)
            a[i+1]=a[i];
        a[1]=x,++n;
    }
    void merge(data &b)
    {
        static int c[2010];
        int m=0;
        for (int i=1,j=1; i<=n || j<=b.n;)
            if (i<=n && (j>b.n || a[i]>b.a[j]))
                c[++m]=a[i++];
            else
                c[++m]=b.a[j++];
        memcpy(a,c,sizeof(a)),n=m;
    }
} f[2010],ans;

int gcd(int x,int y)
{
    for (int t; t=x%y; x=y,y=t);
    return y;
}

void dfs(int x)
{
    flag[x]=1;
    for (edge *i=fst[x]; i; i=i->nxt)
        if (!flag[i->v])
            dfs(i->v),f[x].merge(f[i->v]);
    f[x].add(x);
}

int main()
{
    scanf("%d",&n);
    repu(i,1,n)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    repu(i,1,n)
        repd(j,n,1)
            if (i!=j && gcd(a[i],a[j])>1)
                *tp=(edge){j,fst[i]},fst[i]=tp++;
    repu(i,1,n)
        if (!flag[i])
            dfs(i),ans.merge(f[i]);
    repu(i,1,n)
        printf("%d ",a[ans.a[i]]);
    return 0;
}

Measured memory_bytes: 57600
/*
    Mbak Sana Dong
    Mbak Chaeyoung Dong
*/
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int r,c;
char grid[202][202];
int dist[22][22];
int main()
{
    int n,i,j,k,x,y,ans,curr,temp,m;
    cin >> r >> c;
    getchar();
    vector<pair<int,int> > vi;
    for(i=1;i<=r;i++)
    {
        for(j=1;j<=c;j++)
        {
            scanf("%c",&grid[i][j]);
            vi.push_back({i,j});
        }
        getchar();
    }
    int sz = vi.size();
    int chaeng = 0;
    for(i=0;i<sz;i++)
    {
        x = vi[i].first;
        y = vi[i].second;
        if(grid[x][y] == '#') continue;
        for(j=i+1;j<sz;j++)
        {
            int endx = vi[j].first;
            int endy = vi[j].second;
            if(grid[endx][endy] == '#') continue;
            for(int a = 1; a <= r; a++)
                for(int b = 1; b <= c; b++)
                    dist[a][b] = 1e9;
            set<pair<int,pair<int,int> > > s;
            s.insert({0,{x,y}});
            dist[x][y] = 0;
            while(!s.empty())
            {
                if(dist[endx][endy] < 1e9) break;
                int now = (*s.begin()).first;
                int xx = (*s.begin()).second.first;
                int yy = (*s.begin()).second.second;
                s.erase(s.begin());
                if(xx + 1 <= r)
                {
                    if(grid[xx+1][yy] == '.')
                    {
                        if(dist[xx+1][yy] > now + 1)
                        {
                            dist[xx+1][yy] = now + 1;
                            s.insert({now+1, {xx+1,yy}});
                        }
                    }
                }
                if(xx - 1 > 0)
                {
                    if(grid[xx-1][yy] == '.')
                    {
                        if(dist[xx-1][yy] > now + 1)
                        {
                            dist[xx-1][yy] = now + 1;
                            s.insert({now+1, {xx-1,yy}});
                        }
                    }
                }

                if(yy + 1 <= c)
                {
                    if(grid[xx][yy+1] == '.')
                    {
                        if(dist[xx][yy+1] > now + 1)
                        {
                            dist[xx][yy+1] = now + 1;
                            s.insert({now+1, {xx,yy+1}});
                        }
                    }
                }
                if(yy - 1 > 0)
                {
                    if(grid[xx][yy-1] == '.')
                    {
                        if(dist[xx][yy-1] > now + 1)
                        {
                            dist[xx][yy-1] = now + 1;
                            s.insert({now+1, {xx,yy-1}});
                        }
                    }
                }
            }
            if(dist[endx][endy] != 1e9)
            {
                chaeng = max(chaeng, dist[endx][endy]);
            }
        }
    }
    cout << chaeng << endl;
    return 0;
}


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

int main()
{
    string s;
    cin >> s;
    s = s.substr(0, 4) + s.substr(5,2) + s.substr(8);
    if(s > "20190430")
        cout << "TBD" << endl;
    else
        cout << "Heisei" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;

int n;
int x[50], y[50];
map<pi, int> m;

int main() {
    cin >> n;
    rep(i,n) cin >> x[i] >> y[i];
    int ans = 0;
    rep(i,n) for (int j = i+1; j < n; j++) {
        int dx = x[i] - x[j], dy = y[i]-y[j];
        int cnt = 0;
        rep(k,n) {
            rep(l,n) {
                if (x[k]+dx == x[l] && y[k]+dy == y[l]) {
                    cnt++;
                }
            }
        }
        ans = max(ans, cnt);
    }
    cout << n-ans << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60;

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

long long int a[3][100001];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[0][i] >> a[1][i] >> a[2][i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (j == k) continue;
				chmax(dp[k][i + 1], dp[j][i] + a[k][i]);
			}
		}
	}
	long long res = 0;
	for (int i = 0; i < 3; i++) chmax(res, dp[i][n]);
	cout << res << endl;
}

Measured memory_bytes: 4992
N, M, Q = map(int, input().split())

s = [[0] * (N+1) for _ in range(N+1)]
for _ in range(M):
    l, r = map(int, input().split())
    s[l][r] += 1

for i in range(1, N+1):
    for j in range(1, N+1):
        s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1]

for _ in range(Q):
    p, q = map(int, input().split())

    print(s[q][q] - s[q][p-1] -s[p-1][q] + s[p-1][p-1])


Measured memory_bytes: 18636
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
	int n,f=0,i=0;
	int a[100000];
	scanf("%d",&n);
	while(1)
	{
		if(n==0)break;
		if(n%(-2)==0)a[i]=0;
		else a[i]=1;
		n=(n-a[i])/(-2);
		i++;
	}
	if(i-1<0)printf("0");
	for(int j=i-1;j>=0;j--)
	{
		printf("%d",a[j]);
	}
	printf("\n");
	return 0;
}

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

int main(){
	string s;
	cin>>s;
	int X = s.size();
	string sl("");
	for (int i=0; i<X; i++){
		if(i%2==0){
			sl = sl + s[i];
		}else{
			continue;
		}
	}
	
	cout<<sl;
	return 0;
}

Measured memory_bytes: 640
<?php
fscanf(STDIN, "%d", $n);
$a = array_map("intval", explode(" ", fgets(STDIN)));

rsort($a);

for($i = 0; $i < floor($n / 2)*2; $i++){
    if($a[$i] != $n - floor($i / 2)*2 - 1){
        echo 0;exit;
    }
}
if($n & 1){
    if($a[$n-1] != 0){
        echo 0;exit;
    }
}

$mod = 10**9+7;
$p = 1;
for($i = 0; $i < floor($n / 2); $i++){
    $p*=2;
    $p%=$mod;
}
echo $p;


Measured memory_bytes: 16884
while   True:
    H,W=map(int,input().split())
    if (H==0 and W==0):
        break

    for i in range(H):
        for j in range(W):
            if i==0 or i==H-1 or j==0 or j==W-1:
                print("#", end="")
            else:
                print(".", end="")
        print()
    print()


Measured memory_bytes: 7004
use strict;
use warnings;
use utf8;

# 11:06

my ($N, $A, $B) = split /\s/, <STDIN>;


my $answer = 0;
for (my $i = 1; $i <= $N; $i++) {
    my $sum = 0;
    my $n = $i;

    while ($n > 0) {
        $sum += $n % 10;
        $n /= 10;
    }
    if ($A <= $sum and $sum <= $B) {
        $answer += $i;
    }
}

printf "%s\n", $answer;


Measured memory_bytes: 640
N = int(input())
A = list(map(int, input().split()))
if all([a==0 for a in A]):
  print(0)
  exit()

answer = []
posA = [i for i, a in enumerate(A) if a>0]
negA = [i for i, a in enumerate(A) if a<0]

if sum(A) >= 0:
  key = posA[0]
  for a in posA[1:]:
    answer.append([a, key]) #posA[0]に集める
  for a in negA:
    answer.append([key, a]) #これで全て非負
  for i in range(N-1):
    answer.append([i,i+1]) #非負のcumsumで広義単調増加

if sum(A) < 0:
  key = negA[0]
  for a in negA[1:]:
    answer.append([a, key]) #negA[0]に集める
  for a in posA:
    answer.append([key, a]) #これで全て非正
  for i in range(N-1,0,-1):
    answer.append([i,i-1]) #非負のcumsumで広義単調増加

print(len(answer))

for a in answer:
  print(' '.join(map(lambda x: str(x+1), a)))

Measured memory_bytes: 3064
#include <iostream>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;

// M x N matrix
#define M 22
#define N 22

// queue node used in BFS
struct Node
{
	// (x, y) represents matrix cell coordinates
	// dist represent its minimum distance from the source
	int x, y, dist;
};

// Below arrays details all 4 possible movements from a cell
int row[] = { -1, 0, 0, 1 };
int col[] = { 0, -1, 1, 0 };

// Function to check if it is possible to go to position (row, col)
// from current position. The function returns false if (row, col)
// is not a valid position or has value 0 or it is already visited
bool isValid(int mat[][N], bool visited[][N], int row, int col)
{
	return (row >= 0) && (row < M) && (col >= 0) && (col < N)
		&& mat[row][col] && !visited[row][col];
}

// Find Shortest Possible Route in a matrix mat from source
// cell (i, j) to destination cell (x, y)
int BFS(int mat[][N], int i, int j, int x, int y)
{
	// construct a matrix to keep track of visited cells
	bool visited[M][N];

	// initially all cells are unvisited
	memset(visited, false, sizeof visited);

	// create an empty queue
	queue<Node> q;

	// mark source cell as visited and enqueue the source node
	visited[i][j] = true;
	q.push({i, j, 0});

	// stores length of longest path from source to destination
	int min_dist = INT_MAX;

	// run till queue is not empty
	while (!q.empty())
	{
		// pop front node from queue and process it
		Node node = q.front();
		q.pop();

		// (i, j) represents current cell and dist stores its
		// minimum distance from the source
		int i = node.x, j = node.y, dist = node.dist;

		// if destination is found, update min_dist and stop
		if (i == x && j == y)
		{
			min_dist = dist;
			break;
		}

		// check for all 4 possible movements from current cell
		// and enqueue each valid movement
		for (int k = 0; k < 4; k++)
		{
			// check if it is possible to go to position
			// (i + row[k], j + col[k]) from current position
			if (isValid(mat, visited, i + row[k], j + col[k]))
			{
				// mark next cell as visited and enqueue it
				visited[i + row[k]][j + col[k]] = true;
				q.push({ i + row[k], j + col[k], dist + 1 });
			}
		}
	}

    return min_dist;
}

int main()
{
    int mat[M][N];
    memset(mat, 0, sizeof(mat));
    int r,c;
    cin >> r >> c;
    char cc;
    for(int i = 0 ; i < r;++i)
    {
        for(int j = 0 ; j < c;++j)
        {
           cin >> cc;
           if(cc == '.')
           {
               mat[i][j] = 1;
           }
           else
           {
               mat[i][j] = 0;
           }
        }
    }
    int max_ans = 0;
    for(int i = 0 ; i < r;++i)
    {
        for(int j = 0 ; j < c;++j)
        {
            for(int k = 0 ; k < r;++k)
            {
                for(int m = 0 ; m < c ;++m)
                {
                    if(mat[i][j] == 1 && mat[k][m] == 1)
                    {
                        int dist = BFS(mat, i,j, k, m);

                        if (dist != INT_MAX && dist > max_ans)
                            max_ans = dist;
                    }
                }
            }
        }
    }
    cout << max_ans << endl;


    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    ll n; cin >> n;

    
    map<ll,ll> mp;
    ll input = n;

    for(ll i=2;i*i<=input;i++){
        if(input % i == 0){
            while(input % i == 0){
                input /= i;
                mp[i]++;
            }
        }
    }
    if(input != 1) mp[input]++;

    ll ans = 0;

    map<ll,ll>::iterator it;
    for(it=mp.begin();it!=mp.end();it++){
        ans += (sqrt(1+8*it->second)-1)/2;
    }

    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3684
#include <bits/stdc++.h>
using namespace std;
int digit(long n)
{
  int count = 0;
  while(n != 0){
    n /= 10;
    count++;
  }
  return count;
}

int main(void)
{
  long n, k = 0, a;
  cin >> n;
  while(k * k <= n) k++;
  for(;k >= 1; k--){
    if(n % k == 0){
      a = n / k;
      break;
    }
  }
  cout << digit(a) << endl;
  return 0;
}

Measured memory_bytes: 256
/******************
*  Author: BD747  *
******************/
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<vector>
#include<bits/stdc++.h>
using namespace std;

int cl[100005];
int lst[100005];
vector<int> eds[100005];
int n,m,q;

void dfs1(int v,int d,int c){
	if(!cl[v])
		cl[v]=c;
	if(lst[v]>=d)
		return;
	lst[v]=d;
	if(d==0)
		return;
	for(int u=0;u<eds[v].size();u++)
		dfs1(eds[v][u],d-1,c);
}

vector<int> vv,dd,cc;

int main(){

	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		--a;--b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	cin>>q;
	for(int i=0;i<q;i++){
		int v,d,c;
		cin>>v>>d>>c;
		--v;
		vv.push_back(v);
		dd.push_back(d);
		cc.push_back(c);
	}
	reverse(vv.begin(),vv.end());
	reverse(dd.begin(),dd.end());
	reverse(cc.begin(),cc.end());
	for(int i=0;i<q;i++){
		int v,d,c;
		v=vv[i];
		d=dd[i];
		c=cc[i];
		dfs1(v,d,c);
	}
	for(int i=0;i<n;i++){
		cout<<cl[i]<<endl;
	}

	return 0;
}


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

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

using namespace std;

using ll = long long;

int mod(int x, int m) {
    if (x > 0) {
        return x % m;
    } else {
        int r = (-x) % m;
        return r ? m - r : 0;
    }
}

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

    int N, L, T;
    cin >> N >> L >> T;
    vector<int> X(N), W(N);
    REP(i, N) {
        cin >> X[i] >> W[i];
    }

    ll cnt = 0; // アリ 0 がすり抜ける回数。
    REP(i, N) {
        if (W[i] != W[0]) {
            int d;
            if (W[0] == 1 && W[i] == 2) {
                d = X[i] - X[0];
            } else if (W[0] == 2 && W[i] == 1) {
                d = L - (X[i] - X[0]);
            }
            if (2 * T >= d) {
                cnt += 1 + (2 * T - d) / L;
            }
        }
    }
    int k;
    int Yk;
    if (W[0] == 1) {
        k = mod(cnt, N);
        Yk = mod(X[0] + T, L);
    } else if (W[0] == 2) {
        k = mod(-cnt, N);
        Yk = mod(X[0] - T, L);
    }

    vector<int> Y(N);
    REP(i, N) {
        if (W[i] == 1) {
            Y[i] = mod(X[i] + T, L);
        } else if (W[i] == 2) {
            Y[i] = mod(X[i] - T, L);
        }
    }
    sort(Y.begin(), Y.end());

    int l = lower_bound(Y.begin(), Y.end(), Yk) - Y.begin();
    int l1;
    if (W[0] == 1) {
        l1 = mod(l + 1, N);
    } else if (W[0] == 2) {
        l1 = mod(l - 1, N);
    }
    if (Y[l] == Y[l1]) {
        l = l1;
    }

    REP(i, N) {
        cout << Y[mod(i + l - k, N)] << '\n';
    }
    cout << flush;
    
    return 0;
}


Measured memory_bytes: 4512
#include<iostream>
#include<string>
#include<utility>
#include<vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin >> N;
	int t;
	string s;
	vector<pair<string, int>>a(N);
	string X;
	int ans = 0;
	for (int i = 0; i < N; i++){
		cin >> s >> t;
		a[i] = make_pair(s, t);
	}
	cin >> X;
	for (int i = N - 1; i > 0; i--){
		if (X == a[i].first) {
			break;
		}
		ans += a[i].second;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int k = sc.nextInt();
        int max1 = Math.min(a + k - 1, b);
        for (int i = a; i <= max1; i++) {
            System.out.println(i);
        }
        
        int min2 = Math.max(max1 + 1, b - k + 1);
        for (int i = min2; i <= b; i++) {
            System.out.println(i);
        }
    }
}


Measured memory_bytes: 22612
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

//begin( Union-Find )//

const int MAX_N = 10000000;


//親の番号
int par[MAX_N];
//ノードの高さ
int rk[MAX_N];

//n要素で初期化
void init(int n) {
  for (int i = 0; i < n; i++) {
    par[i] = i;
    rk[i] = 0;
  }
}

//木の根を求める
int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

//xとyの属する集合を併合
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;
  
  if (rk[x] < rk[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rk[x] == rk[y]) rk[x]++;
  }
}

//xとyが同じ集合に属するか否か
bool same(int x, int y) {
  return find(x) == find(y);
}

//end( Union-Find )//

int main() {
  int N, K, L;
  cin >> N >> K >> L;
  
  init(2 * N);
  
  for (int i = 0; i < K; i++) {
    int p, q;
    cin >> p >> q;
    unite(p-1+N, q-1+N);
  }
  
  for(int i = 0; i < L; i++) {
    int r, s;
    cin >> r >> s;
    unite(r-1, s-1);
  }
  
  vector<P> v;
  for (int i = 0; i < N; i++) {
    v.push_back(P(find(i), find(i + N)));
  }
  
  sort(v.begin(), v.end());
  
  int ans[N];
  
  for (int i = 0; i < N; i++) {
    int lower;
    
    int lb = 0;
    int ub = N;
    while (ub - lb > 1) {
      int mid = (lb + ub)/2;
      if (v.at(mid) < P(find(i), find(i+N))) {
        lb = mid;
      } else {
        ub = mid;
      }
    }
    if (v.at(lb) == P(find(i), find(i+N))) {
      lower = -1;
    } else {
      lower = lb;
    }
    
    
    
    int upper;
    
    lb = 0;
    ub = N;
    while (ub - lb > 1) {
      int mid = (lb + ub)/2;
      if (v.at(mid) <= P(find(i), find(i+N))) {
        lb = mid;
      } else {
        ub = mid;
      }
    }
    upper = lb;
    
    ans[i] = upper - lower;
  }
  
  for (int i = 0; i < N; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
}

Measured memory_bytes: 6768
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

ll fastPow(ll x, ll n)
{
    ll res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

ll fac[11234567];
void combInit(int mx)
{
    fac[0] = 0;
    fac[1] = 1;
    for (int i = 2; i <= mx; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
    }
}

ll modDiv(ll a, ll b)
{
    return a * fastPow(b, MOD - 2) % MOD;
}

ll comb(ll a, ll b)
{
    if (b == 0)
        return 1;
    if (a < b)
        return 0;
    if (a <= 0 || b < 0)
        return 0;
    if (a == b)
        return 1;

    ll p, c;

    c = modDiv(fac[a], fac[a - b]);
    p = fac[b];

    ll res = modDiv(c, p);

    return res;
}

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

    combInit(11234560);

    int x, y;

    cin >> x >> y;

    for (int i = 0; i <= 1e6 * 2; i += 2)
    {
        int sum = i + i / 2;

        if (x + y != sum)
            continue;

        if (x <= i && y <= i)
        {
            int ke = i / 2;

            int r = i - x;

            cout << comb(ke, r) << endl;
            return 0;
        }
    }

    cout << 0 << endl;
    return 0;

    return 0;
}

Measured memory_bytes: 88064
#include <iostream>

using namespace std;
#include <string>
typedef long long int ll;
#include <algorithm>
#include <stack>
#include <vector>
#include <array>


int main(){

  int N;
  cin >>N;
  vector<string> S;
  for(int i=0;i<N;i++){
    string s;cin >> s;
    sort(s.begin(),s.end());
    S.push_back(s);
  }
  sort(S.begin(),S.end());
  ll count = 0;
  string si;
  string sj;
  vector<int> same_map(N,0);
  ll count_ = 1;
  for(int i=0;i<N-1;i++){
    si=S[i];sj=S[i+1];
    if(si==sj){
      count_ += 1;
    }else{
      count += count_*(count_-1)/2;
      count_ = 1;
    }
  }
  count += count_*(count_-1)/2;

  cout << count<<endl;



  return 0;
}


Measured memory_bytes: 6132
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <numeric>
#include <math.h>

#define user spaesk
#define pi acos(-1)
#define lli long long int
#define ld long double
#define ff first
#define ss second
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

lli n;
lli a[307];

ld cache[307][307][307];
bool vis[307][307][307];
lli f[4];

ld dp(lli a, lli b, lli c) {

    if(a < 0 || b < 0 || c < 0)
        return 0;

    if(a == 0 and b == 0 and c == 0)
        return 0;

    ld &ans = cache[a][b][c];

    if(ans != -1)
        return ans ;

    ans = (ld)n + a * dp(a - 1, b, c) + b * dp(a + 1, b - 1, c) + c * dp(a, b + 1, c - 1);
    ans /= (a + b + c);

    return ans ;
}

void solve()
{

    cout<<fixed<<setprecision(10);
    cin>>n;
    for(int i = 1; i <= n; i ++) {
        cin>>a[i];
        f[a[i]] ++;
    }

    for(int i = 0; i <= 303; i ++) {
        for(int j = 0; j <= 303; j ++) {
            for(int k = 0; k <= 303; k ++) {
                cache[i][j][k] = -1;
            }
        }
    }

    ld ans = dp(f[1], f[2], f[3]);

    cout<<ans;

    cout<<'\n';
    return ;
}

/*
*/

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

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



Measured memory_bytes: 450944
N , Y = map(int,input().split())

for i in range(N+1):
    x = i
    for y in range(9):
        z = N - x - y
        if z < 0 :
            break
        if 10000*x + 5000*y + 1000*z == Y:
            print(x,y,z)
            quit()
print(-1,-1,-1)


Measured memory_bytes: 2940
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var t = Console.ReadLine();

            var dp = new int[s.Length + 1, t.Length + 1];
            for (var i = 0; i < s.Length; i++)
            {
                for (var j = 0; j < t.Length; j++)
                {
                    if (s[i] == t[j])
                        dp[i + 1, j + 1] = dp[i, j] + 1;
                    else
                        dp[i + 1, j + 1] = Math.Max(dp[i, j + 1], dp[i + 1, j]);
                }
            }

            var ans = "";
            int x = s.Length - 1, y = t.Length - 1;
            while (x >= 0 && y >= 0)
            {
                if (s[x] == t[y])
                {
                    ans += s[x];
                    x--;
                    y--;
                }
                else
                {
                    if (dp[x, y + 1] > dp[x + 1, y])
                        x--;
                    else
                        y--;
                }
            }

            Console.WriteLine(new string(ans.Reverse().ToArray()));
        }
    }
}


Measured memory_bytes: 50132
def mul(a,b):
    mod=10**9+7 
    return ((a%mod)*(b%mod))%mod
def solve(n,k):
    mod=10**9+7
    i=n-k+2
    s=0
    for j in range(k,n+2):
        #print("Hello")
        s=(s%mod+mul(i-1,j)+1)%mod
        i-=1
    return s
n,k=map(int,input().split())
mod=10**9+7
print(solve(n,k)%mod)


Measured memory_bytes: 9200
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

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

  map<string, int> m;
  for (int i = 0; i < n; ++i) {
    string tmp;
    cin >> tmp;
    auto itr = m.find(tmp);
    if (itr != m.end())
      ++m[tmp];
    else
      m[tmp] = 1;
  }

  int vmax = 0;
  for (auto &v : m) {
    if (vmax < v.second)
      vmax = v.second;
  }

  vector<string> vec;
  for (auto &v : m) {
    if (v.second == vmax)
      vec.push_back(v.first);
  }

  sort(vec.begin(), vec.end());
  for (auto &v : vec)
    cout << v << endl;
}

Measured memory_bytes: 27636
using System;
using System.Collections.Generic;
using System.Linq;

namespace C {
    class Program {
        static void Main (string[] args) {
            var NM = Console.ReadLine ().Split (' ').Select (c => int.Parse (c)).ToList ();
            var N = NM[0];
            var M = NM[1];
            var ABs = new List<List<long>> ();
            foreach (var i in Enumerable.Range (0, N)) {
                ABs.Add (Console.ReadLine ().Split (' ').Select (c => long.Parse (c)).ToList ());
            }
            var sortedABs = ABs.OrderBy (AB => AB[0]).ToList ();

            var boughtNum = 0L;
            var sumYen = 0L;
            foreach (var i in Enumerable.Range (0, N)) {
                var needNum = M - boughtNum;
                var A = sortedABs[i][0];
                var B = sortedABs[i][1];
                if (needNum <= B) {
                    sumYen += needNum * A;
                    break;
                } else {
                    sumYen += B * A;
                    boughtNum += B;
                }
            }
            Console.WriteLine (sumYen);
        }
    }
}

Measured memory_bytes: 34800
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")

#define rep(i,n) for(int i=0;i<n;i++)
const long long MOD = 1000000007;

int h,w; 
int main(){
  cin >> h >> w; cin.ignore();
  int ans = 0;
  rep(i,h){
    string s; getline(cin,s);
    rep(j,w){
      if(s.at(j) == '#') ans++;
    }
  }
  if(ans == h+w-1 ){
    cout << "Possible\n";
  }else{
    cout << "Impossible\n";
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int A, B, C, D; cin >> A >> B >> C >> D;
  if(A+B > C+D){
    cout << "Left" << endl;
  }else if(A+B == C+D){
    cout << "Balanced" << endl;
  }else{
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int main() {
  long long a,b,c,d;
  cin >> a >> b >> c >> d;
  long long num1=max(c,d),num2=min(c,d),temp=num1%num2;
  while(temp!=0) {
    num1=num2;
    num2=temp;
    temp=num1%num2;
  }
    
  long long nc=b/c-(a+c-1)/c+1;
  long long nd=b/d-(a+d-1)/d+1;
  long long ncd=b/(c*d/num2)-(a+c*d/num2-1)/(c*d/num2)+1;
  //cout << nc << nd << ncd << endl;
  cout << b-a+1-nc-nd+ncd << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <unordered_set>

int main() {
	std::string s;
	std::cin >> s;

	if (s.size() % 2 == 0) {
		std::cout << "No" << std::endl;
		return 0;
	}
	
	std::unordered_set<std::string> searched;
	std::stack<std::string> st;
	st.push(s);

	while (!st.empty()) {
		std::string node = st.top(); st.pop();
		if (node == "ABC") {
			std::cout << "Yes" << std::endl;
			return 0;
		}
		if (node.find("ABC") == -1) continue;

		for (int i = 0; i < 3; i++) {
			std::string ss("");
			bool isOk = true;
			for (int j = 0; j < node.size(); j++) {
				if (j + 2 < node.size() && node[j] == 'A' && node[j + 1] == 'B' && node[j + 2] == 'C') {
					ss += 'A' + i;
					j += 2;
				}
				else if (node[j] == 'A' + i) isOk = false;
				else ss += node[j];
			}
			if (isOk && searched.find(ss) == searched.end()) {
				st.push(ss);
				searched.insert(ss);
			}
		}
	}
	std::cout << "No" << std::endl;
	return 0;
}

Measured memory_bytes: 15448
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <set>
#include <cmath>

typedef long long ll;

using namespace std;

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

    ll min;
    cin >> min;

    ll ans = -1 * min;

    for(int i = 0; i < n - 1; i++){
        ll x;
        cin >> x;
        ll new_ans = x - min;

        if(new_ans > ans){
            ans = new_ans;
        }

        if(x < min){
            min = x;       
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3104
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) c.begin(), c.end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

const ll mod = 1e9 + 7;
ll dp[310][310][310];

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<P, int> > a(m);
    REP(i,m){
        cin >> a[i].first.second >> a[i].first.first >> a[i].second;
    }
    sort(ALL(a));
    VI l(m), r(m), x(m);
    REP(i,m){
        l[i] = a[i].first.second - 1;
        r[i] = a[i].first.first - 1;
        x[i] = a[i].second;
    }

    dp[1][0][0] = dp[0][1][0] = dp[0][0][1] = 1;
    int p = 0;
    REP(i,n){
        REP(x,i+1) REP(y,i+1){
            (dp[i+1][x][y] += dp[i][x][y]) %= mod;
            (dp[i][i+1][y] += dp[i][x][y]) %= mod;
            (dp[i][x][i+1] += dp[i][x][y]) %= mod;

            (dp[x][i+1][y] += dp[x][i][y]) %= mod;
            (dp[i+1][i][y] += dp[x][i][y]) %= mod;
            (dp[x][i][i+1] += dp[x][i][y]) %= mod;

            (dp[x][y][i+1] += dp[x][y][i]) %= mod;
            (dp[i+1][y][i] += dp[x][y][i]) %= mod;
            (dp[x][i+1][i] += dp[x][y][i]) %= mod;
        }
        while (p < m && r[p] == i){
            REP(a,i+1) REP(b,i+1){
                if (x[p] == 1 && (a > l[p] || b > l[p])){
                    dp[i+1][a][b] = dp[a][i+1][b] = dp[a][b][i+1] = 0;
                }
                if (x[p] == 2 && !((a > l[p]) ^ (b > l[p]))){
                    dp[i+1][a][b] = dp[a][i+1][b] = dp[a][b][i+1] = 0;
                }
                if (x[p] == 3 && (a <= l[p] || b <= l[p])){
                    dp[i+1][a][b] = dp[a][i+1][b] = dp[a][b][i+1] = 0;
                }
            }
            p++;
        }
    }

    ll ans = 0;
    REP(i,n) REP(j,n){
        ans = (ans + dp[i][j][n] + dp[i][n][j] + dp[n][i][j]) % mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 227584
#include<cstdio>
#include<iostream>
#include<cstring>
#define RG register
using namespace std;
char ss[10];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%s",ss);
	if(strlen(ss)==2) cout<<ss;
	else printf("%c%c%c",ss[2],ss[1],ss[0]);
//	fclose(stdin); fclose(stdout);
	return 0;
}


Measured memory_bytes: 256
require "matrix"
include Math

def position(l, ratio)
  θ = (ratio + 1/4r) * 2 * PI
  Matrix[[cos(θ), sin(θ)], [-sin(θ), cos(θ)]] * Vector[0, l]
end

a, b, h, m = gets.split.map(&:to_i)

vh = position(a, (h + Rational(m, 60)) / 12)
vm = position(b, Rational(m, 60))

puts (vh - vm).norm

Measured memory_bytes: 15552
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int count = 0;
		for (int i = 0; i < N; i++) {
			if (K <= sc.nextInt()) {
				count++;
			}
		}
		System.out.println(count);
	}
}

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

int main() {

	int d, n; cin >> d >> n;
	int ans;
	if (d == 0) {
		if (n < 100) ans = n;
		else ans = 101;
	}
	else if (d == 1) {
		if (n < 100) ans = n * 100;
		else ans = 101 * 100;
	}	
	else {
		if (n < 100) ans = n * 100 * 100;
		else ans = 101 * 100 * 100;
	}
	cout << ans << endl;
	return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  string s; cin >> s;
  vector<string> ans;
  REP(i, s.size()) {
    if(s[i] == '0') ans.push_back("0");
    if(s[i] == '1') ans.push_back("1");
    if(s[i] == 'B') if(!ans.empty()) ans.pop_back();
  }
  REP(i, ans.size()) cout << ans[i];
  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}


signed main() {
    int H, W;
    cin >> H >> W;
    vvi c(10, vi(10, 0));
    vvi A(H, vi(W, 0));
    rep(i, 10) rep(j, 10) cin >> c[i][j];
    rep(i, H) rep(j, W) cin >> A[i][j];
    
    //ワーシャルフロイド法によりすべての数の最小変換コストを算出する
    //k:経由する頂点　i:出発地点　j:行先
    rep(k, 10) rep(i, 10) rep(j, 10) {
        c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
    }

    int res = 0;
    rep(i, H) rep(j, W) {
        if(A[i][j] != -1) res += c[A[i][j]][1];
    }
    
    cout << res << endl;
    return 0;
}

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

using namespace std;

int main()
{
    int n;
    while (scanf("%d", &n) && n){
        
        int b[64] = {0};
        
        for (int i = 0; i < n; i++){
            int x;
            scanf("%d", &x);
            for (int j = 0; j < x; j++){
                int t;
                scanf("%d", &t);
                b[i] |= 1 << (t - 1);
            }
        }
        
        for (int i = 0; i < 30; i++){
            int st = 1 << i;
            
            for (int j = 0; j < 30; j++){
                for (int k = 0; k < n; k++){
                    if (st & b[k]){
                        for (int l = 1; l <= (st & b[k]); l <<= 1){
                            st |= (b[k] & l);
                        }
                    }
                }
            }
            
            bool ok = true;
            for (int j = 0; j < n; j++){
                if (!(st & b[j])) ok = false;
            }
            if (ok){
                printf("%d\n", i + 1);
                goto OK;
            }
        }
        
        printf("-1\n");
        
        OK:;
    }
    
    return (0);
}

Measured memory_bytes: 1196
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main(){
  ll a,b;cin>>a>>b;
  string s;cin>>s;
  if(s[a]!='-'){
    cout<<"No"<<endl;
    return 0;
  }
  ll count=0;
  rep(i,s.size()){
    if(s[i]!='-')count++;
  }
  if(count==a+b){
    cout<<"Yes"<<endl;
    return 0;
  }
  cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int inf = 1000000000;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
const ll mod = 1e9+7;

ll powmod(ll x,ll y){
  if(y == 0){
    return 1;
  }
  if(y == 1){
    return x%mod;
  }
  if(y%2 == 0){
    return (powmod(x,y/2)*powmod(x,y/2))%mod;
  }
  else{
    return ((x%mod)*((powmod(x,y/2)*powmod(x,y/2)%mod)))%mod;
  }
}

int main(){
    ll n;
    cin >> n;
    ll a = powmod(10,n);
    ll b = powmod(9,n);
    b = (b*2)%mod;
    ll c = powmod(8,n);
    ll d;
    if((a-b)%mod< 0){
        d = (a-b)%mod+(1e9+7);
    }
    else{
        d = (a-b)%mod;
    }
    cout << (d+c)%mod << endl;
    //cout << mod << endl;
}

Measured memory_bytes: 3604
from math import sqrt
from sys import stdin, stdout
readline = stdin.readline
write = stdout.write
while 1:
    n = int(readline())
    if n == 0:
        break
    C = [map(int, readline().split()) for i in xrange(n)]
    P = [[C[0][:2]]]
    # calculate intersections of the circles
    for i in xrange(n-1):
        x0, y0, r0 = C[i]
        x1, y1, r1 = C[i+1]
        rr = (x1 - x0)**2 + (y1 - y0)**2; rd = sqrt(rr)
        rc = (r0**2 + rr - r1**2) / (2 * rd); rs = sqrt(4*r0**2*rr - (r0**2 + rr - r1**2)**2) / (2 * rd)
        ex = (x1 - x0) / rd; ey = (y1 - y0) / rd
        bx = x0 + ex * rc; by = y0 + ey * rc
        P.append([(bx + ey * rs, by - ex * rs), (bx - ey * rs, by + ex * rs)])
    P.append([C[-1][:2]])

    def calc((x0, y0), (x1, y1)):
        return sqrt((x1 - x0)**2 + (y1 - y0)**2)
    def cross((x0, y0), (x1, y1), (x2, y2)):
        return (x1-x0) * (y2-y0) - (x2-x0) * (y1-y0)
    INF = 10**18
    dist = {(0, 0): 0}
    for i in xrange(n):
        for j, (x, y) in enumerate(P[i]):
            left = p_left = None; right = p_right = None
            d = dist[i, j]
            for k in xrange(i+1, n):
                lp, rp = P[k]
                # update left and right
                if left is None or cross((x, y), left, lp) >= 0:
                    left = lp
                if right is None or cross((x, y), rp, right) >= 0:
                    right = rp
                # check if left <= right
                if cross((x, y), left, right) < 0:
                    break

                # propagate cost from P[i][j] to P[k][0] or P[k][1] if possible
                if p_left != left:
                    dist[k, 0] = min(dist.get((k, 0), INF), d + calc((x, y), left))
                    p_left = left
                if p_right != right:
                    dist[k, 1] = min(dist.get((k, 1), INF), d + calc((x, y), right))
                    p_right = right
            else:
                # P[i][j] -> goal
                gp = P[n][0]
                # check if left <= goal <= right
                if (left is None and right is None) or (cross((x, y), left, gp) >= 0 and cross((x, y), gp, right) >= 0):
                    dist[n, 0] = min(dist.get((n, 0), INF), d + calc((x, y), gp))
    write("%.06f\n" % dist[n, 0])

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

using namespace std;

int main(){
  int a = 0, b = 0;
  cin >> a >> b;
  
  if ((a * b) % 2 == 0){
    cout << "Even" << endl;
  }
  else {
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;

int main(void) {
	int c = 0;
	string s, a;
	cin >> s;
	while(s != "") {
		c = 0;
		a = s[0];
		//cout << a << endl;
		c++;
		s = s.substr(1);
		//cout << "new s = " << s << endl;
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == a[0]) {
				c++;
				if(i > 0) {
					//cout << s.substr(0, i) << " " << s.substr(i+1) << endl;
					s = s.substr(0, i) + s.substr(i+1);
					//cout << "new s' = " << s << endl;
				} else {
					s = s.substr(1);
					//cout << "new s'' = " << s << endl;
				}
				i--;
			}
		}
		//cout << c << endl;
		if(c%2) {
			cout << "No\n";
			return 0;
		}
	}

	cout << "Yes\n";
	return 0;
}


Measured memory_bytes: 256