akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

int main() {
   ll n, k; cin >> n >> k;
   if(n==k){
      cout << 0 << endl;
      return 0;
   }

   ll ans = n;
   if(n>k){
      if(n%k==0){
         cout << 0 << endl;
         return 0;
      }

      ll tmp = n/k;
      ll tmp2 = n%k;
      dump(tmp);
      dump(tmp2);
      ans = min(tmp2, (ll)abs(tmp2-k));
   }
   else{
      ans = min(n, min((ll)abs(n-k), (ll)abs(k-n)));
   }

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


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
using namespace std;
int N, A, B, v[111], r[111], G[111][222];
int rec(int pos) {
	int ret = 0; v[pos] = 1;
	for (int i = 0; i < r[pos]; i++) {
		if (!v[G[pos][i]]) ret = max(ret, rec(G[pos][i]));
	}
	v[pos] = 0;
	return ret + 1;
}
int main() {
	while (scanf("%d", &N), N) {
		for (int i = 0; i < 100; i++) r[i] = 0;
		for (int i = 0; i < N; i++) {
			scanf("%d%d", &A, &B), A--, B--;
			G[A][r[A]++] = B, G[B][r[B]++] = A;
		}
		int ret = 0;
		for (int i = 0; i < 100; i++) ret = max(ret, rec(i));
		printf("%d\n", ret);
	}
	return 0;
}

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

int main() {
    int a, b, c, _a, _b, _c;
    cin >> a >> b >> c;
    if (a < b) {
        if (c < a) {
            _a = c;
            _b = a;
            _c = b;
        } else if (c < b) {
            _a = a;
            _b = c;
            _c = b;
        } else {
            _a = a;
            _b = b;
            _c = c;
        }
    } else {
        if (c < b) {
            _a = c;
            _b = b;
            _c = a;
        } else if (c < a) {
            _a = b;
            _b = c;
            _c = a;
        } else {
            _a = b;
            _b = a;
            _c = c;
        }
    }
    printf("%d %d %d\n", _a, _b, _c);
    return 0;
}

Measured memory_bytes: 3204
N = int(input())
s_list = [input() for i in range(N)]
M = int(input())
t_list = [input() for i in range(M)]
X = 0
for i in range(N):
	if s_list.count(s_list[i]) - t_list.count(s_list[i]) >= X:
		X = s_list.count(s_list[i]) - t_list.count(s_list[i])
print(X)

Measured memory_bytes: 3060
"use strict"

const main = arg => {
  arg = arg.trim().split("\n");

  const n = ~~(arg[0].split(" ")[0]);
  const m = ~~(arg[0].split(" ")[1]);

  const a = arg.slice(1, n + 1).map(n=>n.split(""));
  const b = arg.slice(n + 1, (n + 1) + (m + 1)).map(n=>n.split(""));

  let answer = false;

  const A = [];
  const B = [];

  for (let i=0; i<m; i++) {
    for (let j=0; j<m; j++) {
      A.push(i);
      B.push(j);
    }
  }
  
  for (let i=0; i<n; i++) {
    for (let j=0; j<n; j++) {
      
      for (let k=0, len=Math.pow(m, 2); k<len; k++) {
        const X = i + A[k];
        const Y = j + B[k];
        
        if (X < 0 || n <= X) break;
        if (Y < 0 || n <= Y) break;
        if (a[X][Y] !== b[A[k]][B[k]]) break;

        if (k === (len - 1)) answer = true;
      }
    }
  }

  console.log(answer ? "Yes" : "No");
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7640
import sys,math
from collections import deque,defaultdict
import operator as op
from functools import reduce
sys.setrecursionlimit(10**6) 

I=sys.stdin.readline

 #s="abcdefghijklmnopqrstuvwxyz"

"""
x_move=[-1,0,1,0,-1,1,1,-1]
y_move=[0,1,0,-1,1,1,-1,-1]
"""
def ii():
	return int(I().strip())
def li():
	return list(map(int,I().strip().split()))
def mi():
	return map(int,I().strip().split())

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


	
	

	

def main():
	n=ii()
	arr=li()
	cnt=0
	for i in range(n-1):
		if arr[i]>arr[i+1]:
			cnt+=arr[i]-arr[i+1]
			arr[i+1]=arr[i]





	print(cnt)

	


	
	
	
		







	












	
	
	





if __name__ == '__main__':
	main()

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

typedef long long ll;
typedef vector <ll> v_ll;
typedef vector <vector <ll> > vv_ll;
typedef vector < pair <ll,ll> > vp_ll;
typedef pair <ll,ll> p_ll;

ll N,M,K,X;
v_ll C;
ll MOD;

ll mod_inv(ll x,ll n){
  x%=n;
  if (x<0) x+=n;
  ll y = x,z = n-2;
  ll ret=1;
  while (z>0){
    if(z%2==1){
      ret*=y;
      ret%=n;
    }
    y*=y;
    y%=n;
    z/=2;
  }
  return ret;
}

v_ll mod_nck(ll n,ll nm){
  v_ll nck(n+1,0);
  nck[0]=1;
  for (ll i=1;i<=n;i++){
    nck[i]=(nck[i-1]*(n+1-i))%nm;
    nck[i]*=mod_inv(i,nm);
    nck[i]%=nm;
  }
  return nck;
}

int main(){
  cin >> N >> M >> K;
  X=N*M;
  MOD=1000000007;
  C=mod_nck(X-2,MOD);
  ll N2=0,M2=0;
  for(ll i=1;i<=M-1;i++){
    M2+=(i*(M-i));
    M2%=MOD;
  }
  for(ll i=1;i<=N-1;i++){
    N2+=(i*(N-i));
    N2%=MOD;
  }
  N2*=M;N2%=MOD;
  N2*=M;N2%=MOD;
  M2*=N;M2%=MOD;
  M2*=N;M2%=MOD;

  ll ans=N2+M2;
  ans%=MOD;

  ans *= C[K-2];
  ans%=MOD;
  cout << ans << endl;
}


Measured memory_bytes: 1792
class Node():
    def __init__(self, v):
        self.v = v
        self.parent = None
        self.children = []
        self.is_visited = False
    
    def add_child(self, node):
        self.children.append(node)
        node.parent = self


def construct_tree(node):
    start = -1 if node.v is None else node.v
    if node.v == 9:
        return
    for i in range(start + 1, 10):
        new_node = Node(i)
        node.add_child(new_node)
        construct_tree(new_node)

def reset_state(node):
    node.is_visited = False
    for child in node.children:
        reset_state(child)

def find_answer(node, n, s, cnt=0):
    node.is_visited = True
    
    depth, cur_sum = 0, 0
    cur = node
    while cur.parent is not None:
        cur_sum += cur.v
        depth += 1
        cur = cur.parent
    
    if cur_sum == s and depth == n:
        cnt += 1
   
    if depth < n:
        for child in node.children:
            if not child.is_visited:
                cnt = find_answer(child, n, s, cnt)
    
    return cnt

def solve():
    root = Node(None)
    construct_tree(root)
    
    while True:
        n, s = map(int, input().split())
        if n == 0 and s == 0:
            break
        
        count = find_answer(root, n, s)
        print(count)
        reset_state(root)

if __name__ == "__main__":
    solve()



Measured memory_bytes: 5772
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

int a, b, n, x, y;
set<P> se;
int dp[100][100];

int main(){
	while (cin >> a >> b&&a + b){
		cin >> n;
		REP(i, n){
			cin >> x >> y;
			x--; y--;
			se.insert(P(y, x));
		}
		dp[0][0] = 1;
		REP(i, b){
			REP(j, a){
				if (i + j == 0)continue;
				if (i == 0)dp[i][j] = dp[i][j - 1];
				else if (j == 0)dp[i][j] = dp[i - 1][j];
				else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				if (se.find(P(i, j)) != se.end()){
					dp[i][j] = 0;
				}
				//cout << dp[i][j] << " ";
			}
		}
		cout << dp[b - 1][a - 1] << endl;
		se.clear();
		REP(i, b)REP(j, a)dp[i][j]=0;
	}
}

Measured memory_bytes: 1200
#include <iostream>
#include <math.h>
#include <unordered_map>  
#define N 1000000
using namespace std;
unordered_map<int, int> mp;  
int arr[N];

//エラトステネスの篩
void Eratosthenes(){
	for(int i = 0; i < N; i++){
		arr[i] = 1;
	}
	for(int i = 2; i < sqrt(N); i++){
		if(arr[i]){
			for(int j = 0; i * (j + 2) < N; j++){
				arr[i *(j + 2)] = 0;
			}
		}
	}
int count=0;
for(int i = 2; i < N; i++){
		if(arr[i]){
int x= (i+1)/2;
if(arr[x]&&(i%2)==1){
		count++;
mp[i]=count;	
		}
}
	}
}



//素数
int main(void){
	Eratosthenes();
	int n;
cin >>n;
int l[n],q[n];
for(int i=0;i<n;i++){
cin >> l[i]>>q[i];
}
for(int i=0;i<n;i++){
int flag=1;
int x=l[i];
while(flag=1){
    auto itr = mp.find(x);  
    if( itr != mp.end() ) {
        break;
    } else {
       x++;
    }
}
flag=1;
int y=q[i];
while(flag=1){
    auto itr = mp.find(y);  
    if( itr != mp.end() ) {
break;
    } else {
       y--;
    }
}
cout<<mp[y]-mp[x]+1<<endl;
}

	return 0;
}

Measured memory_bytes: 5504
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

class Edge
{
public:
    int to, val;
    Edge(int to, int val){
        this->to = to;
        this->val = val;
    }
};

vector<vector<Edge> > edges;
vector<pair<int, long long> > a;
vector<bool> check;

const long long INF = LLONG_MAX / 2;

pair<long long, long long> solve(int curr, int prev)
{
    check[curr] = true;

    pair<long long, long long> ans(-INF, INF);
    if(a[curr].first == 1)
        ans.first = -a[curr].second + 1;
    else
        ans.second = a[curr].second - 1;

    for(const auto& e : edges[curr]){
        int next = e.to;
        if(check[next]){
            if(a[curr].first != a[next].first){
                if(e.val != a[curr].second + a[next].second)
                    return make_pair(1, 0);
            }
            else{
                long long x = e.val - a[curr].second - a[next].second;
                if(x % 2 != 0)
                    return make_pair(1, 0);
                ans.first = max(ans.first, x / 2 * a[curr].first);
                ans.second = min(ans.second, x / 2 * a[curr].first);
            }
        }
        else{
            a[next] = make_pair(-a[curr].first, e.val - a[curr].second);
            auto p = solve(next, curr);
            ans.first = max(ans.first, p.first);
            ans.second = min(ans.second, p.second);
        }
    }

    return ans;
}

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

    edges.assign(n, vector<Edge>());
    for(int i=0; i<m; ++i){
        int u, v, s;
        cin >> u >> v >> s;
        -- u;
        -- v;
        edges[u].push_back(Edge(v, s));
        edges[v].push_back(Edge(u, s));
    }

    a.assign(n, make_pair(1, 0));
    check.assign(n, false);
    auto ans = solve(0, -1);
    cout << max(0LL, ans.second - ans.first + 1) << endl;

    return 0;
}


Measured memory_bytes: 15104
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
vector<int> gr[1919];
int x[1919];
string out="POSSIBLE";
bool dp[2][5140];
pint dfs(int v){
	//cout<<v<<endl;
	if(gr[v].size()==0) return mp(x[v],0);
	int sum=0,n=gr[v].size(),ma=-1;
	vector<pint> p;
	rep(i,n){
		pint P=dfs(gr[v][i]);
		sum+=P.fi+P.se;
		assert(sum<=5000*1000);
		//cout<<v<<' '<<gr[v][i]<<' '<<P.fi<<' '<<P.se<<endl;
		p.pb(P);
	}
	memset(dp,false,sizeof(dp));dp[0][0]=true;
	rep(j,n){
		int now=j%2,ne=1-now;
		memset(dp[ne],false,sizeof(dp[ne]));
		rep(i,x[v]+1){
			if(!dp[now][i]) continue;
			if(i+p[j].fi<=x[v]) dp[ne][i+p[j].fi]=true;
			if(i+p[j].se<=x[v]) dp[ne][i+p[j].se]=true;
		}
	}
	rep(i,x[v]+1){
		if(dp[n%2][i]) ma=i;
	}
	if(ma<0){
		out="IMPOSSIBLE";
		return mp(0,0);
	}
	//cout<<v<<' '<<x[v]<<' '<<sum-ma<<endl;
	return mp(x[v],sum-ma);
}
int main()
{
	int n,p;
	cin>>n;
	rep(i,n-1){
		cin>>p;p--;gr[p].pb(i+1);
	}
	rep(i,n) cin>>x[i];
	dfs(0);
	cout<<out<<endl;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
typedef long long ll;
using namespace std;

int n;
int a[20];
int x[15][15];
bool y[15][15];

int ans=0;

void search(int depth,bool honest[]){
  if(depth!=n){
    honest[depth]=0;
    search(depth+1,honest);

    honest[depth]=1;
    search(depth+1,honest);
  }
  else{
    int i,j;

    for(i=0;i<n;i++){
      if(honest[i]==0){
        continue;
      }

      for(j=0;j<a[i];j++){
        if(honest[x[i][j]]!=y[i][j]){
          return;
        }
      }
    }

    int sum=0;
    for(i=0;i<n;i++){
      if(honest[i]){
        sum++;
      }
    }
    if(sum>ans){
      ans=sum;
    }
  }
}

int main(void){
  int i,j;

  cin>>n;
  for(i=0;i<n;i++){
    cin>>a[i];
    for(j=0;j<a[i];j++){
      cin>>x[i][j]>>y[i][j];
      x[i][j]--;
    }
  }

  bool b[15];
  search(0,b);

  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int H,W;
int main(){
  cin>>H>>W;
  vector<string> fi(H);
  for(int i=0;i<H;i++){
    cin>>fi[i];
  }
  vector<int> ans;
  int dx[4]={0,0,1,-1};
  int dy[4]={1,-1,0,0};
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      for(int k=0;k<H;k++){
        for(int l=0;l<W;l++){

          vector<vector<int>> dist(H,vector<int>(W,-1));
          using pir=pair<int,int>;
          queue<pir> que;

          if(fi[i][j]=='#')continue;
          dist[i][j]=0;
          que.push(pir(i,j));

          while(!que.empty()){
            auto v=que.front();
            que.pop();
            for(int i=0;i<4;i++){
              int nx=v.second+dx[i];
              int ny=v.first+dy[i];
              if(nx<0||nx>=W||ny<0||ny>=H)continue;
              if(fi[ny][nx]=='#')continue;
              if(dist[ny][nx]!=-1)continue;
              dist[ny][nx]=dist[v.first][v.second]+1;
              que.push(pir(ny,nx));
            }
          }
          if(fi[k][l]=='#')continue;
          ans.push_back(dist[k][l]);
        }
      }
    }
  }
    sort(ans.begin(),ans.end());
    reverse(ans.begin(),ans.end());
    cout<<ans[0]<<endl;
}

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

int main(){
  unsigned long long a,b,n;cin>>a>>b>>n;
  unsigned long long x = b-1;
  if(n<x) x=n;
  unsigned long long s=(unsigned long long)(a*x/b)-a*((unsigned long long)(x/b));
  cout << s << endl;
  return 0;
}  


Measured memory_bytes: 3632
#include<iostream>
#include<cmath>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(x,a) for(auto& (x):(a))
#define ALL(obj) (obj).begin(),(obj).end()
#define Yes(n) cout<<((n)?"Yes":"No")<<endl;
using namespace std;
using ll=long long;
const int INF=1e9;
const ll LINF=1e18;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
  ll N;
  ll minv=LINF;
  cin>>N;
  REP(i,5){
    ll a;
    cin>>a;
    minv = min(minv, a);
  }

  ll ans=N/minv;
  if(N%minv!=0) ++ans;
  ans+=4;

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

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

int main() {
  int N, K;
  std::cin >> N >> K;
  std::vector<int> stones(N+1);
  for(int i = 1; i < N+1; ++i) {
    std::cin >> stones[i];
  }
  std::vector<long> dp(N+1);
  dp[0] = INT_MAX;
  dp[1] = 0;
  for(int i = 2; i < N+1; ++i) {
      dp[i] = INT_MAX;
    for(int k = 1; k <= K; ++k) {
      if(i-k > 0) {
        dp[i] = std::min(dp[i], dp[i-k]+std::abs(stones[i-k]-stones[i]));
      } else {
        break;
      }
    }
  }
  std::cout << dp[N] << "\n";
  return 0;
}

Measured memory_bytes: 4248
#include <fstream>
#include <numeric>
#include <unordered_set>
#include <sstream>
#include <cassert>
#include <tuple>
#include <iomanip>
#include <random>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <chrono>
#include <stack>
#include <string>
#include <bitset>
#include <unordered_map>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>

#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x.size())
#define pb push_back
#define ll long long
#define int long long
#define pii pair <int, int>
#define print(x) for(auto it : x) cout << it << ' ';

using namespace std;

const int N = (int)(1e6) + 322;
const int MAXN = (int)(1e7) + 100;
const int inf = (int)(1e18) + 322;
const int mod = 998244353;
const double eps = 1e-6;
#define endl "\n" // remove



int a[N];

signed main () {
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    int n, m;cin >> n >> m;
    double sum = 0;

    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    sort(a + 1, a + n + 1, greater<int>());
    sum /= 4.0 * m;
    if (a[m] < sum) {
        cout << "No";
    }else {
        cout << "Yes";
    }


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define D(x) cout << #x << "=" << x <<endl; 
#define De(...)
#define pii pair<int,int>
#define mp make_pair<int,int>
using namespace std; 

int _; 

set<int> s;
int n,a[200050],ans=0;
bool vis[1000500];

inline void factor(int x)
{
	if(x == 1)
		return;
	for(int i=1;i*i <= x;i++)
		if(x%i == 0)
		{
			int si=s.size();
			s.insert(i);
			if(si == s.size())
			{
			//	D(x);
			//	D(i);
				ans++;
				return;
			} 
			else
				s.erase(i);
			if(i*i == x || i == 1) 
				continue;
			si=s.size();
			s.insert(x/i);
			if(si == s.size())
			{
			//	D(x);
			//	D(x/i);
				ans++;
				return;
			} 
			else
				s.erase(x/i);
		}
}

int main()
{
	//for(scanf("%d",&_);_;_--)
	memset(vis,0,sizeof(vis));
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int si=s.size();
		scanf("%d",a+i);
		s.insert(a[i]);
		if(si == s.size())
		{
			if(vis[a[i]]) 
				ans++;
			else
			{
				ans += 2; 
				vis[a[i]]=true;
			}
		} 
	}
	for(int i=0;i<n;i++)
		if(!vis[a[i]])
			factor(a[i]);
	printf("%d\n",n-ans);
	return 0;
}

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

int main(){
  char b;
  cin >> b;
  if(b=='A'){
    cout << 'T' << endl;
  }else if(b=='T'){
    cout << 'A' << endl;
  }else if(b=='C'){
    cout << 'G' << endl;
  }else if (b=='G'){
    cout << 'C' << endl;
  }
  return 0;
}


Measured memory_bytes: 256
N = int(input())
S = list(input())

W = [0]*(N+1)
E = [0]*(N+1)

for i in range(N):
    if S[i]=='W':
        W[i+1] = W[i]+1
    else:
        W[i+1] = W[i]
        
for i in reversed(range(N)):
    if S[i]=='E':
        E[i] = E[i+1] + 1
    else:
        E[i] = E[i+1]

INF = 1<<30
ans = INF

for i in range(N):
    res = W[i] + E[i+1]
    ans = min(ans,res)

print(ans)

Measured memory_bytes: 67696
#include<iostream>
#include<queue>
#include<limits>
// #include<bits/stdc++.h>
#include<algorithm>
#include<vector>
#include<cmath>
#include<math.h>
#include<iomanip>  
#include<deque> 
#include<stack>
#include<string> 
#include<string.h>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#define ll long long
#define tc(t)  while(t--)
#define V vector
#define Vp vector< pair<int,int> >
#define pb push_back
#define UM unordered_map
#define IT iterator
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define PQ priority_queue
#define _FI ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

 char ar[140000];
vector<ll> SieveOfEratosthenes(ll n) 
{ 
  vector<ll> result;
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
    int count=1;
    for (ll p=2; p*p<=n; p++) 
    { 
        if (prime[p] == true) 
        {  
            for (ll i=p*p; i<=n; i += p) 
                {
                  prime[i] = false; 
                }
            count++;
        } 
    } 
  
    for (ll p=2; p<=n; p++) 
       if (prime[p]) 
          {
            result.push_back(p);
          }
    return result;
}



vector<ll> Divisors (ll n)
{
  vector<ll> res;
  for(ll i=1;i<=sqrt(n);i++)
  {
    if(n%i==0)
    {
      if(n/i==i)
      {
        res.pb(i);
      }
      else
      {
        res.pb(i);
        res.pb(n/i);
      }
    }
  }

  return res;
}

int a[4][2]={ {1,0}, {1,-1}, {1,1}, {2,0} } ;
bool validPoint(int x,int y, int N)
{
    return (x>=0 && x<N && y>=0 && y<N);
}


 
int main()
{
  _FI 
  int n;
  cin>>n;
  if(n>=30)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  return 0;
}















Measured memory_bytes: 3096
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#include<string>
#include<memory.h>
#include<list>
#include<set>
using namespace std;

#define ll long long
#define vi vector<int>
#define vii vector<vi>
const int N = 200000 + 10;
int freq[26];
int main() {
	string a;
	cin >> a;
	for (int i = 0; i < a.size(); ++i) {
		freq[a[i] - 'a']++;
	}
	long long res = 1;
	for (int i = 0; i < a.size(); ++i) {
		for (int j = 0; j < 26; ++j) {
			if (a[i] - 'a' == j)
				continue;
			res += freq[j];
		}
		freq[a[i] - 'a']--;
	}
	cout << res << endl;
	return 0;
}


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

int main () {
  int n;
  string s;
  cin >> n >> s;
  int a=s.size();
  for (int i=0;i<s.size()-1;i++) {
    if (s[i]==s[i+1]) a--;
  }
  cout << a << endl;
  return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner stdIn = new Scanner(System.in);
        int a = stdIn.nextInt();
        int b = stdIn.nextInt();
        //int p = stdIn.nextInt();
        
        if(a >= 13){
            System.out.println(b);
        }else if(a >= 6){
            System.out.println(b / 2);
        }else{
            System.out.println(0);
        }
        
        //System.out.println();
    }
}


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

typedef long long ll;

vector<ll>divisors_list(ll n)
{
    vector<ll>res;
    for (int i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            res.push_back(i);
            if((n/i)!=i)
                res.push_back(n/i);
        }
    }
    sort(res.begin(),res.end());
    return res;
}

int main()
{

    ll n,a,b,i,c=0;
    cin >> n;
    for(i=1; i<=n; i++)
    {
        if(i%2==0)continue;
        vector<ll>v=divisors_list(i);
        if(v.size()==8)c++;
    }
    cout << c << "\n";


    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <math.h>
#include <queue>
#include <stdio.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{
    int x;
    cin >> x;
    int y = -1;
    rep2(i,1,35)
    {
        int tmp = i*i;
        rep2(j,2,11)
        {
            if(tmp*i > x) break;
            tmp *= i;
        }
        if(tmp > x) continue;
        y = max(y,tmp);
    }
    cout << y << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <inttypes.h>

#define MOD_BY INT64_C(1000000007)

int64_t add(int64_t a, int64_t b) {
	return (a + b) % MOD_BY;
}

int64_t mul(int64_t a, int64_t b) {
	int64_t r = 0;
	while (b > 0) {
		if (b & 1) r = add(r, a);
		a = add(a, a);
		b >>= 1;
	}
	return r;
}

int main(void) {
	int64_t a, b, x;
	if (scanf("%" PRId64 "%" PRId64 "%" PRId64, &a, &b, &x) != 3) return 1;
	if (x < a) {
		printf("%" PRId64 "\n", x % MOD_BY);
	} else {
		int64_t yoryoku = x - a;
		int64_t koukan = yoryoku / (a - b) + 1;
		printf("%" PRId64 "\n", add(x, mul(b, koukan)));
	}
	return 0;
}



Measured memory_bytes: 2144
def bubble_sort(array, n):
    flag = True
    count = 0
    while flag:
        flag = False
        for j in range(n - 1, 0, -1):
            if array[j] < array[j - 1]:
                array[j], array[j - 1] = array[j - 1], array[j]
                flag = True
                count += 1
    return count


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    count = bubble_sort(a, n)
    print(*a)
    print(count)


if __name__ == '__main__':
    main()



Measured memory_bytes: 5612
#include <bits/stdc++.h>
using namespace std;
int n;
int main (){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1; i<10; i++){
	for (int j=1; j<10; j++){
		if (i*j==n){
			cout << "Yes";
			return 0;
		}
	}
}
cout << "No";
return 0;
}

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

int main()
{
    int n,m;
    cin>>n>>m;
    int arr[m+5]={0};
    for(int i=0;i<n;i++)
    {
        int q;
        cin>>q;
        while(q--)
        {
            int a;
            cin>>a;
            arr[a]++;
        }
    }

        int counter=0;
        for(int i=1;i<=m;i++)
        {
            if(arr[i]==n)counter++;
        }
        cout<<counter<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define dfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define mem(u, vis) memset(u, vis, sizeof(u))
#define ll long long
#define ull unsigned long long
#define MOD  1000000007
#define MAX  1e9
#define pb   push_back
#define F    first
#define S    second

bool check_product(long long a,long long b,long long c)
{
	if (a==0||b==0)
		return false;
	return (c/b<a);
}

signed main() {
	int t=1;
	//cin>>t;
	while(t--){
		ll n;
		cin>>n;
		ll a[n];
		ll p = 1e18;
		ll m = 1;
		bool f = false;
		rep(i,n){
			cin>>a[i];
			if(a[i]==0){
				m = 0;
			}
		}
		if(m==0){
			cout<<0;
			return 0;
		}
		rep(i,n){
			if(check_product(m,a[i],p)){
				f = true;
				break;
			}
			m *= a[i];
		}
		// cout<<m;
		if(m> p){
				f = true;
				// break;
			}
		if(f)cout<<-1;
		else cout<<m;
		
	}
	
}

Measured memory_bytes: 4420
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;

int main(){
    int n; cin >> n;
    vector<int> l(n);
    rep(i, n) {
        cin >> l[i];
    }
    sort(l.begin(),l.end());
    int sum = 0;
    for (int i = 0; i < n - 1; i++) {
        sum += l[i];
    }

    if(l[n -1] < sum) {
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
}
   

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

int gcd(int a, int b) {
  int r, tmp;
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

int main() {
  int N; cin >> N;
  int A[N]; for (int i = 0; i < N; ++i) cin >> A[i];
  int g = A[0];
  for (int i = 1; i < N; ++i) {
    g = gcd(g, A[i]);
  }
  cout << g << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

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

        long val = 0;
        int[] V=new int[N];
        int negCount = 0;
        int absMin = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            V[i]=sc.nextInt();
            if(V[i]<0){
                negCount++;
            }
            absMin=Math.min(absMin,Math.abs(V[i]));
            val +=Math.abs(V[i]);
        }

        if(negCount%2==0){
            System.out.println(val);
        }else{
            System.out.println(val - absMin*2);
        }

    }

}


Measured memory_bytes: 52212
#include <stdio.h>

int main(void)
{
  int a, b;
  scanf("%d %d", &a, &b);
  if ( a % 3 == 0 || b % 3 == 0 || (a+b) % 3 == 0 ) {
    puts("Possible");
  } else {
    puts("Impossible");
  }
  return 0;
}


Measured memory_bytes: 128
n,k=map(int,input().split())
import math
a=0
b=[]
c=0
d=[0 for i in range(n)]
for i in range(n,0,-1):
    while(True):
        if(pow(2,c)*i>=k):
            d[i-1]=c
            break
        c+=1
for i in range(n):
    a+=pow(2,d[0]-d[i])
print('{0:.10f}'.format(a/(pow(2,d[0])*n)))


Measured memory_bytes: 3864
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

	sort(x.begin(), x.end());
	sort(y.begin(), y.end());

	if (y[0] <= x[N - 1] || y[0] <= X || Y <= x[N - 1])cout << "War" << endl;
	else cout << "No War" << endl;


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <climits>
#include <memory>
#include <sstream>
#include <iomanip>

using namespace std;

int n, a, b, c;
int use[8] = { 0 };
int l[8] = { 0 };

int ans = INT_MAX;

void func(int num) {
	if (num == n) {
		int tmp_a = 0, tmp_b = 0, tmp_c = 0;
		int tmp_ans = 0;
		for (int i = 0; i < n;i++) {
			if (use[i] == 1) {
				if (tmp_a == 0) {
					tmp_a += l[i];
				}
				else {
					tmp_ans += 10;
					tmp_a += l[i];
				}
			}
			else if (use[i] == 2) {
				if (tmp_b == 0) {
					tmp_b += l[i];
				}
				else {
					tmp_ans += 10;
					tmp_b += l[i];
				}
			}
			else if (use[i] == 3) {
				if (tmp_c == 0) {
					tmp_c += l[i];
				}
				else {
					tmp_ans += 10;
					tmp_c += l[i];
				}
			}
		}
		if (tmp_a == 0 || tmp_b == 0 || tmp_c == 0)return;
		tmp_ans += abs(a - tmp_a) + abs(b - tmp_b) + abs(c - tmp_c);
		ans = min(ans, tmp_ans);
	}
	else {
		for (int i = 0; i < 4; i++) {
			use[num] = i;
			func(num + 1);
		}
	}
	return;
}

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

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

	func(0);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int n,m,x,y,j,p,ans;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		if(x>n-x+1)j=n-x+1;
		else j=x;
		if(y>n-y+1)p=n-y+1;
		else p=y;
		if(j>p){
			if(p%3==0)ans=3;
			else ans=p%3;
		}
		else{
			if(j%3==0)ans=3;
			else ans=j%3;
		}
		cout<<ans<<endl;
	}
}
		

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

int main() 
{
    int A,B;
    cin>>A>>B;

    if (A+B==3)
    {
        cout<<"3"<<endl;
    }

    if(A+B==4)
    {
        cout<<"2"<<endl;
    }

    if(A+B==5)
    {
        cout<<"1"<<endl;
    }



    return 0;
}


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

int main() {
    string s;
    cin >> s;
    int ans = 0, dir = 0;
    for (char c : s) {
        if (c == 'R') ++dir;
        else --dir;

        if (dir == 4) {
            ++ans;
            dir = 0;
        }
        else if (dir == -4) dir = 0;
    }
    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 3200
#include <stdio.h>
int main(void)
{
	int n,i,j,v,k;
	scanf("%d", &n);
	int A[n];
	for(i=0;i<n;i++)
	{
		scanf("%d",&A[i]);//配列の中身の入力
	}
	for(i=0;i<n;i++)
	{
		v=A[i];
		j=i-1;
		while(j>=0 && A[j]>v)
		{
			A[j+1] = A[j];
			j--;
		}
			A[j+1]=v;
		for(k=0;k<n;k++)
			{
				printf("%d",A[k]);
				if(k==n-1)
				{
					break;
				}
				printf(" ");
			}
			printf("\n");
	}	
}


Measured memory_bytes: 2092
s = list(map(int,input().split()))
a = s[0]
b = s[1]
c = s[2]
d = s[3]

if abs(b-a) <= d  and abs(c-b) <= d:
    print("Yes")
elif abs(c-a) <= d:
    print("Yes")
else:
    print("No")

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

int main()
{
    int n;
    int a, b;
    long long ans(0);
    int dif(0);
    int hmin(1e9);
    cin >> n;

    while (n--) {
        cin >> a >> b;
        if (a != b)
            dif = 1;
        ans += a;
        if (a > b)
            hmin = min(hmin, b);
    }

    if (!dif) {
        cout << 0;
        return 0;
    }
    ans -= hmin;

    cout << ans << '\n';
    return 0;
}


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

int main(void){
    int a, b, c;
    cin >> a >> b >> c;
    int sum = a+b+c;
    if(sum == 17)
        cout << "YES" << endl;
    else
    {
            cout << "NO" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        a: usize
    }
    let ans = n * n - a;
    println!("{}", ans);
}


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

int binary(int bina){
    int ans = 0;
    for (int i = 0; bina>0 ; i++)
    {
        ans = ans+(bina%2)*pow(10,i);
        bina = bina/2;
    }
    return ans;
}

string binary_to_string(int bin, int n) {
	int size = to_string(bin).size();
	string s = string(n - size, '0');
	s += to_string(bin);
	return s;
}


signed main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> connectedSwitch(m);
	for (int i = 0; i < m; ++i) {
		int k;
		cin >> k;
		for (int j = 0; j < k; ++j) {
			int s;
			cin >> s;
			connectedSwitch[i].push_back(s - 1);
		}
	}

	vector<int> p(m);
	for (auto &e : p) cin >> e;

	int N = pow(2, n);
	int ans = 0;

	for (int i = 0; i < N; ++i) {
		string s = binary_to_string(binary(i), n);
		bool flag = true;
		for (int j = 0; j < m; ++j) {
			int cnt = 0;
			for (auto e : connectedSwitch[j]) {
				if (s[e] == '1') cnt++;
			}
			if (cnt % 2 != p[j]) flag = false;
		}
		if (flag) ans++;
	}

	cout << ans << endl;



}


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


void solve(long long N, std::vector<long long> a){
    long long sum = 0;  // xor sum
    for (int i = 0; i < N; i++) {
        sum ^= a[i];
    }
    for (int i = 0; i < N; i++) {
        cout << (sum ^ a[i]) << (i == N - 1 ? "\n" : " ");
    }
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&a[i]);
    }
    solve(N, std::move(a));
    return 0;
}


Measured memory_bytes: 4920
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{

  public static void main(String[] args) throws IOException
  {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in), 1);
    String s = r.readLine();
    String[] sl = s.split("[\\s]+");
    int a = Integer.parseInt(sl[0]);
    int b = Integer.parseInt(sl[1]);
    s = r.readLine();

    String ans = "Yes";

    int i;

    for(i = 0; i < a; i++)
    {
      //System.out.println(s.charAt(i));
      if(!('0' <= s.charAt(i) && s.charAt(i) <= '9'))
      {
        ans = "No";
      }
    }

    //System.out.println(s.charAt(i));
    if(s.charAt(i) != '-')
    {
      ans = "No";
    }


    for(i++; i < a + b + 1; i++)
    {
      //System.out.println(s.charAt(i));
      if(!('0' <= s.charAt(i) && s.charAt(i) <= '9'))
      {
        ans = "No";
      }
    }

    System.out.println(ans);
  }

}


Measured memory_bytes: 22740
function parseInt(x) parse(Int, x) end
parseMap(x::Array{SubString{String}, 1}) = map(parseInt, x)

function main()
	n, m = parseMap(split(readline()))
	x = [Int64[] for i in 1:n]
	for i in 1:m
		a, b = parseMap(split(readline()))
		push!(x[a], b)
		push!(x[b], a)
	end
	flg = 0
	for i in 2:n-1
		if 1 in x[i] && n in x[i]
			print("POSSIBLE")
			flg = 1
			break
		end
	end
	if flg == 0
		print("IMPOSSIBLE")
	end
end

main()

Measured memory_bytes: 159792
import sys
n,m,k=map(int,input().split())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))

salist=[]
sblist=[]

tmp=0
for a in alist:
    tmp+=a
    salist.append(tmp)
tmp=0
for b in blist:
    tmp+=b
    sblist.append(tmp)

outlist=set()
outlist.add(0)
bnow=m
while bnow > 0:
    if sblist[bnow-1] > k:
        bnow -= 1
    else:
        outlist.add(bnow)
        break

for i,sa in enumerate(salist):
    if sa > k:
        break
    while sa + sblist[bnow-1] > k and bnow > 0:
        bnow -= 1
    outlist.add(i+1+bnow)
print(max(outlist))


Measured memory_bytes: 58528
import sys
import collections
import math

N = int(input())
A = [int(x) for x in input().split()]

L = [0] * N

for i in range(N):
    if i == 0:
        L[i] = A[i]
    else:
        L[i] = A[i] + L[i - 1]

min_diff = 10**20
for i in range(N-1):
    s = L[i]
    a = L[N-1] - L[i]
    diff = abs(a-s)
    min_diff = min(min_diff, diff)

print(min_diff)

sys.exit(0)


Measured memory_bytes: 25324
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

# n = int(input())
# a, b = map(int, input().split())
# s = input()


s = input()
now = s[0]
ans = 0
for c in s:
	if c != now:
		now = c
		ans += 1
print(ans)


Measured memory_bytes: 39920
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int d,n;
	cin>>d>>n;
	if(d==0)
		if(n==100)
			cout<<101;
		else
	   		cout<<n;
	else if(d==1)
	    if(n==100)
			cout<<101*100;
		else
	   		cout<<n*100;
	else if(d==2)
	    if(n==100)
			cout<<101*10000;
		else
	   		cout<<n*10000;
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define g(a, b) __gcd((a), (b))
#define l(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T, class U>T rem(T a, U b) { return a - b*floor(a/b); }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
    string tmp;
    cin >> tmp;
    deque<char> deq(all(tmp));

    ll Q;
    cin >> Q;
    ll rev = 0;
    ll revcnt = 0;

    rep(i, 0, Q) {
        ll t, f;
        char c;
        cin >> t;
        if (t == 1) {
            rev ^= 1;
            revcnt++;
        } else {
            cin >> f >> c;
            if (! rev) {
                if (f == 1) {
                    deq.push_front(c);
                } else {
                    deq.push_back(c);
                }
            } else {
                if (f == 1) {
                    deq.push_back(c);
                } else {
                    deq.push_front(c);
                }
            }
        }
    }
    
    string S(all(deq));

    if (revcnt % 2 == 1) {
        reverse(all(S));
    }

    cout << S << endl;
}



Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define INF 9223372036854775807
#define pairint pair<int,int>
signed main(){
  int x=0,y=0,z=0,w=0,n=0,m=0;
  string s;
  std::cin >> x;
  std::vector<int> v(x);
  rep(i,x){
    std::cin >> y;
    if(i==0){
      z=y;
      n++;
    }else if(z>y){
      z=y;
      n++;
    }
  }
  std::cout << n << '\n';
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef pair<double,ll> pdl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<pdd> vdd;
typedef vector<pdi> vdi;
typedef vector<pdl> vdl;
typedef vector<string> vs;
#define fi first
#define se second
const ll INFLL=LLONG_MAX;
const int INF=INT_MAX;
const ll MAXLL=0x3f3f3f3f3f3f3f3f;
const int MAX=0x3f3f3f3f;
const ll MOD=1000000007;
const ll mod=998244353;
#define eb emplace_back
#define emp emplace
#define mp(a,b) make_pair(a,b)
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T> >;
template<class T>
void sort(vector<T>& v){
	sort(v.begin(),v.end());
}
template <class T, class U>
void sort(vector<T>& v,U func){
	sort(v.begin(),v.end(),func);
}
template<class T>
void rsort(vector<T>& v){
	sort(v.rbegin(),v.rend());
}
template <class T>
int lb_index(vector<T>& v,T k){
	return lower_bound(v.begin(),v.end(),k)-v.begin();
}
template <class T>
int ub_index(vector<T>& v,T k){
	return upper_bound(v.begin(),v.end(),k)-v.begin();
}
template<class T>
bool is_sorted(vector<T>& v){
	return is_sorted(v.begin(),v.end());
}
template<class T>
bool sorted(vector<T>& v){
	return is_sorted(v);
}
void precompute(){

	return;
}
void solve(){
	int n;
	cin>>n;
	vl v(n),p(n);
	cin>>p[0];
	map<ll,int>m;
	ll ans=0;
	m[0]=1;
	ans+=m[p[0]]++;
	for(int i=1;i<n;i++){
		cin>>p[i];
		p[i]+=p[i-1];
		ans+=m[p[i]]++;
	}
	cout<<ans;
	return;
}

int main(){
	ios::sync_with_stdio(0);
	int numberofsubtestcases=1;
//	cin>>numberofsubtestcases;
	precompute();
	for(int looping=1;looping<=numberofsubtestcases;looping++){
//		cout<<"Case #"<<looping<<": ";
		solve();
	}
	return 0;
}




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

#define inf 0x3f3f3f3f
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector <ull> vu;
typedef vector <vector <int>> vvi;
typedef pair <int, int> pi;
typedef vector <pair <int, int>> vpi;

int a, b, c, d;

void read() {
  cin >> a >> b >> c >> d;
}

void solve() {
  cout << min ({a + c, a + d, b + c, b + d});
}

int main() {
  ios :: sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  //cin >> t;           // PLEASE REMOVE IT IF NEEDED
  while(t) {
    --t;
    read();
    solve();
  }
  return 0;
}


Measured memory_bytes: 256
//
// Created by yuu on 2019-06-20.
//
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>

using namespace std;
int L;
int getMin(string str){
    vector<int>aa;
    for (int i = 0; i < L; ++i) {
        aa.push_back((int)str[i]-'0');
    }

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

    int ret = 0;
    for (int i = 0; i < L; ++i) {
        ret += aa[i] * pow(10, (L-1)-i);
    }

    return  ret;
}


int getBig(string str){
    vector<int>aa;
    for (int i = 0; i < L; ++i) {
        aa.push_back((int)str[i]-'0');
    }

    sort(aa.begin(), aa.end(), greater<int>());

    int ret = 0;
    for (int i = 0; i < L; ++i) {
        ret += aa[i] * pow(10, (L-1)-i);
    }

    return  ret;
}

int main(void){

    while (1){
        int hoge;
        cin>>hoge>>L;
        if(hoge==0 &&L==0){
            break;
        }

        map<string, int> a;

        string A = to_string(hoge);
        a[A] = 0;

        while (A.size() < L){
            A += '0';
        }
       // cout<<A<<endl;
        int count = 1;
        while(1){
            int big = getBig(A);
            int min = getMin(A);

            int temp = big - min;
            if(temp == 0){
                A = "0";
            }else{
                A = to_string(temp);
            }

            //cout<<A<<endl;

            if(a.count(A) == 1){
                cout<<a[A]<<" "<<temp<<" "<<count- a[A]<<endl;
                break;
            }
            a[A] = count;
            if(A.size() < L){
                while (A.size() < L){
                    A += '0';
                }
            }
           //cout<<A<<endl;

            count ++;


        }


    }

    return 0;
}



Measured memory_bytes: 3376
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()

int dw[] = { 1, -1, 0, 0 };
int dh[] = { 0, 0, 1, -1 };

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<int, int, int> triple;
typedef double D;

int main(int argc, char** argv) {
  int H, W;
  cin >> H >> W;
  vector<string> A(H);
  rep(i, H) {
    cin >> A[i];
  }

  // For Debug
  // rep(i, H) {
  //   cout << A[i] << endl;
  // }
  queue<triple> q;
  rep(h, H) {
    rep(w, W) {
      if (A[h][w] == '#') {
        q.emplace(h, w, 0);
      }
    }
  }

  int ans = 0;
  while (q.size() > 0) {
    int h, w, d;
    tie(h, w, d) = q.front(); q.pop();
    rep(i, 4) {
      int nh = h + dh[i];
      int nw = w + dw[i];

      if (nh < 0 || nh > H-1 || nw < 0 || nw > W-1) { continue; }
      if (A[nh][nw] == '#') { continue; }

      A[nh][nw] = '#';
      q.emplace(nh, nw, d + 1);
      ans = max(ans, d + 1);
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 13456