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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int q, h, s, d, n;
  cin >> q >> h >> s >> d >> n;
  if (q * 2 < h) h = q * 2;
  if (h * 2 < s) s = h * 2;
  if (s * 2 < d) d = s * 2;
  cout << (n / 2) * d + (n % 2) * s << '\n';
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define pb(a) push_back(a)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    int n,step[35] = {0};

    step[0] = 1;
    rep(i,30){
        step[i + 1]+=step[i];
        step[i + 2]+=step[i];
        step[i + 3]+=step[i];
    }

    while(cin >> n, n){
        step[n]+= 3649;
        cout << step[n] / 3650 << endl;
    }
}

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

// 0-indexed
template <class T>
struct BIT {
  int treesize;
  vector<T> lst;
  // constructor
  BIT(int newn = 0) : treesize(newn), lst(newn + 1, 0) {}
  // a_place += num
  void add(int place, T num) {
    ++place;
    while (place <= treesize) {
      lst[place] += num;
      place += place & -place;
    }
  }
  // sum between [0,place)
  T sum(int place) {
    T res = 0;
    while (place > 0) {
      res += lst[place];
      place -= place & -place;
    }
    return res;
  }
  // sum [l,r)
  T sum(int left, int right) { return sum(right) - sum(left); }
};

struct EulerTour {
  int n, root;
  vector<vector<int>> g;
  vector<int> in, out, lst;
  EulerTour(int n = 1, int _root = 0) : root(_root), g(n), in(n), out(n) {}
  EulerTour(const vector<vector<int>> &_g, const int _root = 0)
      : root(_root), g(_g), in(_g.size()), out(_g.size()) {
    build();
  }
  void add(int a, int b) {
    g[a].push_back(b);
    g[b].push_back(a);
  }
  void build() {
    int t = 0;
    lst.clear();
    dfs(root, -1, t);
  }
  void dfs(int now, int bf, int &t) {
    in[now] = t++;
    lst.push_back(now);
    for (auto &to : g[now])
      if (to != bf) {
        dfs(to, now, t);
        ++t;
        lst.push_back(now);
      }
    lst.push_back(now);
    ++t;
    out[now] = t;
  }
};

long long n;
vector<int> c;
vector<vector<int>> edge, col, memo;

void solve();

int main() {
  cin >> n;
  c.resize(n);
  edge.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> c[i];
    --c[i];
  }
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  solve();
  return 0;
}

void solve() {
  EulerTour et(edge);
  BIT<long long> bit(et.lst.size());
  col.resize(n);
  memo.resize(n);
  for (int i = 0; i < n; ++i) bit.add(et.in[i], 1);
  for (int i = 0; i < et.lst.size(); ++i) memo[et.lst[i]].push_back(i);
  for (int i = 0; i < n; ++i) col[c[i]].push_back(i);
  for (int i = 0; i < n; ++i) {
    long long res = n * (n + 1) / 2;
    using P = pair<int, int>;
    vector<P> v;
    map<int, int> mp;
    for (int node : col[i]) {
      bit.add(et.in[node], -1);
      mp[node] = 1;
      for (int id = 0; id < (int)memo[node].size() - 1; ++id)
        v.emplace_back(memo[node][id + 1], node);
    }
    sort(v.begin(), v.end());
    for (P p : v) {
      long long now = bit.sum(et.in[p.second], p.first);
      res -= now * (now + 1) / 2;
      mp[p.second] += now;
      bit.add(et.in[p.second], -now);
    }
    long long last = bit.sum(et.lst.size());
    res -= last * (last + 1) / 2;
    cout << res << endl;
    for (auto p : mp) bit.add(et.in[p.first], p.second);
  }
}


Measured memory_bytes: 71924
import math
A = [int(input()) for _ in range(5)]
B = 10
ans = 0
for i in range(5):
  if A[i] % 10 < B and A[i]%10 > 0:
    B = A[i] % 10
    ans = -10+B
for j in A:
  ans += math.ceil(j/10)*10
print(ans)


Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
  int a;cin >> a;bool ok = false;
  for(int i=1;i<=9;i++){
   for (int j=1;j<=9;j++){
     if (i*j==a) ok = true;
   }
  }
  cout << ((ok) ? "Yes":"No") << endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int N;
long long K;
vector<long long> A, F, S;

long long cost(long long x) {
    long long sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += max(0LL, (S[i]-x+F[i]-1)/F[i]);
    }
    return sum;
}

long long binSearch(long long first, long long last, bool func(long long)) {
    long long len = last-first;
    while (len != 0) {
        long long half = len / 2;
        long long mid = first+half;
        if (func(mid)) {
            len -= half + 1;
            first = ++mid;
        } else {
            len = half;
        }
    }
    return first;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    A = vector<long long>(N);
    for (auto & a : A) cin >> a;
    F = vector<long long>(N);
    for (auto & f : F) cin >> f;
    sort(A.rbegin(), A.rend());
    sort(F.begin(), F.end());
    S = vector<long long>(N);
    for (int i = 0; i < N; ++i) {
        S[i] = A[i]*F[i];
    }
    auto condition = [](long long x) {
        return cost(x) > K;
    };
    long long ans = binSearch(0LL, 1e12, condition);
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#include <iomanip>
#include <cmath>

int main()
{
    double r;
    std::cin >> r;
    std::cout << std::fixed;
    std::cout << std::setprecision(5);
    std::cout << r * r * M_PI << ' '  << 2.0 * r * M_PI << std::endl;
    return 0;
}



Measured memory_bytes: 3300
#include <bits/stdc++.h>  
 
using namespace std;
 
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define repr(i, j) for(int i = j; i >= 0; --i)
#define INF (1 << 30)
#define MOD 1e9 + 7
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

struct Vector { double x; double y; };

Vector sub_vector(const Vector& a, const Vector& b) {
	Vector ret;
	ret.x = a.x - b.x;
	ret.y = a.y - b.y;
	return ret;
}

int main() {
	double ax, ay, bx, by, cx, cy, dx, dy;
	while(scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf", &ax,&ay,&bx,&by,&cx,&cy,&dx,&dy) != EOF) {
		Vector A, B, C, D;
		A.x = ax; A.y = ay;
		B.x = bx; B.y = by;
		C.x = cx; C.y = cy;
		D.x = dx; D.y = dy;

		Vector AB = sub_vector(B, A);
		Vector BD = sub_vector(D, B);
		Vector BC = sub_vector(C, B);
		Vector CD = sub_vector(D, C);
		Vector CA = sub_vector(A, C);
		Vector AD = sub_vector(D, A);

		double c1 = AB.x * BD.y - AB.y * BD.x;
		double c2 = BC.x * CD.y - BC.y * CD.x;
		double c3 = CA.x * AD.y - CA.y * AD.x;

		if((c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0)) printf("NO\n");
		else {
			Vector DA = sub_vector(A, D);
			Vector AC = sub_vector(C, A);
			Vector DC = sub_vector(C, D);
			c1 = AB.x * BC.y - AB.y * BC.x;
			c2 = BD.x * DC.y - BD.y * DC.x;
			c3 = DA.x * AC.y - DA.y * AC.x;
			if((c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0)) printf("NO\n");
			else {
				Vector AC = sub_vector(C, A);
				Vector CB = sub_vector(B, C);
				Vector DB = sub_vector(B, D);
				c1 = AC.x * CB.y - AC.y * CB.x;
				c2 = CD.x * DB.y - CD.y * DB.x;
				c3 = DA.x * AB.y - DA.y * AB.x;
				if((c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0)) printf("NO\n");
				else {
					Vector BA = sub_vector(A, B);
					c1 = BC.x * CA.y - BC.y * CA.x;
					c2 = CD.x * DA.y - CD.y * DA.x;
					c3 = DB.x * BA.y - DB.y * BA.x;
					if((c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0)) printf("NO\n");
					else printf("YES\n");
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3176
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,j,n) for(int i = j; i < n; i++)
#define rrep(i,j,n) for(int i = j-1; i >= n; i--)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
#define endl "\n"
using namespace std;

//constexpr int inf = 2147483647;
//constexpr int64_t inf64 = 9223372036854775807;
//constexpr int mod = 1e9+7;

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

  char a, b;
  cin >> a >> b;

  cout << (a == b ? "H" : "D") << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define EPS 1e-9
using namespace std;
typedef long long ll;
typedef pair<string, int>P;

int main() {
	double d, w, h;
	while (cin >> d >> w >> h, d) {
		double n; cin >> n;
		rep(i, n) {
			int r; cin >> r;
			if (r*2 > sqrt(d*d + w*w) || r*2 > sqrt(d*d + h*h) || r*2 > sqrt(w*w + h*h))
				puts("OK");
			else puts("NA");
		}
	}
}

Measured memory_bytes: 3180
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

LL mod = 1000000007;

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

  while(true){
    LL n, x;
    cin >> n >> x;
    if(n==0&&x==0){
      break;
    }

    LL cnt = 0;

    FOR(i,1,n+1){
      FOR(j, i + 1, n+1){
        FOR(k,j+1,n+1){
          if(i+j+k==x){
            cnt++;
          }
        }
      }
    }

    cout << cnt << endl;
  }
}



Measured memory_bytes: 3172
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

using namespace std;

int main() {
  int N, L;
  cin >> N >> L;
  int total = 0, minabs = abs(L), idx = 0;
  for (int i = 0; i < N; i++) {
    total += L + i;
    if (abs(L + i) < minabs) {
      minabs = abs(L + i);
      idx = i;
    }
  }
  cout << total - L - idx  << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s,t;
    cin >> s >> t;
    char a[s.size()],b[t.size()];
    for(int i=0;i<s.size();i++){
        a[i]=s.at(i);
    }
    for(int i=0;i<t.size();i++){
        b[i]=t.at(i);
    }
    sort(a,a+s.size());
    sort(b,b+t.size());
    string q,r;
    for(int i=0;i<s.size();i++){
        q += a[i];
    }
    for(int i=t.size()-1;0<=i;i--){
        r += b[i];
    }
    if(q<r) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define printYes() cout << "Yes" << endl;
#define printNo() cout << "No" << endl;
#define printVector(v) rep(i, v.size()) cout << v[i] << endl;

int main()
{
  int N;
  cin >> N;
  int SN = 0;
  int NN = N;
  while (NN != 0)
  {
    SN += NN % 10;
    NN /= 10;
  }

  if (N % SN == 0)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define sz(x) int(x.size())
#define pb push_back
#define int long long

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	int sum = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			for (int k = 1; k <= n; ++k)
				sum += __gcd(__gcd(i, j), k);
	cout << sum;
}

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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair

#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)

const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

bool isIn(int x, int y, int n, int m){
    return 0 <= x && x < n && 0 <= y && y < m;
}

int main(){
    int n;
    while(cin >> n, n){
        int w, h;
        cin >> w >> h;
        bool field[110][110];
        rep(i, 110)rep(j, 110) field[i][j] = false;
        rep(i, n){
            int x, y;
            cin >> x >> y;
            field[x-1][y-1] = true;
        }
        int s, t;
        cin >> s >> t;
        int ret = 0;
        rep(i, w-s+1)rep(j, h+t+1){
            int n = 0;
            rep(k, s)rep(l, t){
                if(field[i+k][j+l]) n++;
            }
            ret = max(ret, n);
        }
        cout << ret << endl;
    }
}

Measured memory_bytes: 1168
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

long long ncr(int n, int r) {
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}
ll mod(ll a,ll b,ll m){
    if(b==0)return 1;
    if(b%2==0){
        ll y =  mod(a,b/2,m);
        return (y*y)%m;
    }
    else{
        return ((a%m)*mod(a,b-1,m))%m;
    }
}

ll modinv(ll a,ll m){
return mod(a,m-2,m);
//works only for prime m.
//else calculate phi(m)-1.
}



int main()
{
    int n;
    cin>>n;
    int input[n+1][3];
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++)cin>>input[i][j];
    }
    //states of dp = what is important so far
    //day no. and last activity type
    int dp[n+1][3];
    dp[0][1]=dp[0][2]=dp[0][0]=0;
    dp[1][1]=input[1][1];
    dp[1][2]=input[1][2];
    dp[1][0]=input[1][0];
    for(int i=2;i<=n;i++){
        dp[i][0]=input[i][0]+max(dp[i-1][1],dp[i-1][2]);
    dp[i][1]=input[i][1]+max(dp[i-1][0],dp[i-1][2]);
    dp[i][2]=input[i][2]+max(dp[i-1][1],dp[i-1][0]);

    }
    int ans=-1;
    for(int i=0;i<3;i++){
          //  cout<<dp[n][i]<<endl;
        ans=max(ans,dp[n][i]);
    }
    cout<<ans<<endl;

    return 0;
}


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

int main() {
    int r,d,x,ans;
    //vector<int> vec(11);
    //vec.at(0) = x;

    cin >> r >> d >> x ;
    ans = x;
    //cout << ans << endl;

    for(int i=1; i<11; i++){
        //vec.at(i) = r*vec.at(i-1) - d;
        ans = (r*ans) - d;
        cout << ans << endl;
    }

}

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

#define x first
#define y second
#define int64 long long
#define MaxN 200000
#define Log 17

priority_queue <pair<int, pair<int, int>>> Queue;
int A[MaxN+1], B[MaxN+1], C[MaxN+1];
int rmq[2][Log+1][MaxN+1];
int P[MaxN+1];
int V[MaxN+1];
int N;

void Build(int l)
{
    int i, j;

    for(i = 1; i <= N; ++i)
    if(i % 2 == l) rmq[l][0][i] = i;

    for(i = 1; (1 << i) <= N; ++i)
        for(j = 1; j <= N - (1 << i) + 1; ++j)
            if(V[ rmq[l][i-1][j] ] < V[ rmq[l][i-1][j + (1 << i-1)] ]) rmq[l][i][j] = rmq[l][i-1][j];
            else rmq[l][i][j] = rmq[l][i-1][j + (1 << i-1)];
}

int getMin(int l, int a, int b)
{
    int k = P[b-a+1];

    if(V[ rmq[l][k][a] ] < V[ rmq[l][k][b - (1 << k) + 1] ]) return rmq[l][k][a];
    return rmq[l][k][b - (1 << k) + 1];
}

int main(){


    int i, x, y, st, dr, value;

    scanf("%d", &N);
    for(i = 1; i <= N; ++i) scanf("%d", &V[i]);
    for(i = 2; i <= N; ++i) P[i] = P[i/2] + 1;
    V[0] = N + 1;

    Build(0);
    Build(1);

    x = getMin(1, 1, N);
    Queue.push({-V[x], {1, N}});
    while(!Queue.empty())
    {
        st = Queue.top().y.x;
        dr = Queue.top().y.y;
        Queue.pop();

        x = getMin(st % 2, st, dr);
        y = getMin(dr % 2, x, dr);
        printf("%d %d ", V[x], V[y]);

        if(st < x){
            value = V[ getMin(st % 2, st, x - 1) ];
            Queue.push({-value, {st, x - 1}});
        }

        if(y - x > 1){
            value = V[ getMin(dr % 2, x + 1, y - 1) ];
            Queue.push({-value, {x + 1, y - 1}});
        }

        if(y < dr){
            value = V[ getMin(st % 2, y + 1, dr) ];
            Queue.push({-value, {y + 1, dr}});
        }
    }


return 0;
}


Measured memory_bytes: 32764
def max(a,b)
    return a < b ? b : a
end
def min(a,b) 
    return a = a > b ? b : a
end
N,K = gets.split.map(&:to_i)
x = gets.split.map(&:to_i)
ans = 1231231231
(N-K+1).times do |i|
    if x[i+K-1] < 0
        ans = min(ans, x[i].abs)
    elsif 0 < x[i]
        ans = min(ans, x[i+K-1].abs)
    else
        ans = min(ans,x[i].abs + (x[i+K-1]-x[i]).abs)
        ans = min(ans,x[i+K-1].abs + (x[i+K-1]-x[i]).abs)
    end
end
puts ans


Measured memory_bytes: 8460
# ABC108B - Ruined Square
x1, y1, x2, y2 = list(map(int, input().rstrip().split()))
d1 = x2 - x1
d2 = y2 - y1
    
x3 = x2 - d2
y3 = y2 + d1

x4 = x1 - d2
y4 = y1 + d1

print(x3, y3, x4, y4)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define M ((ll)1e12)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi acos(-1)
typedef long long ll;
using namespace std;


void solve()
{
   ll n;
   cin>>n;
   ll v=n/100;
   ll v1=n%100;
   v=v*5;
   if(v1<=v)
   cout<<1<<endl;
   else
   cout<<0<<endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	solve();
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <queue>
#include <vector>
using namespace std;

struct state { 
    int x, y, c, d;
    bool operator>(const state& rhs) const
    {
        return c > rhs.c;
    };

    bool operator<(const state& rhs) const
    {
        return c < rhs.c;
    };

    bool operator==(const state& rhs) const
    {
        return c == rhs.c;
    };
};

int cs[5], field[31][31];
        bool visited[31][31][4];
int main()
{
    int w, h;
    while(cin >> w >> h && w && h) {
        for(int i = 1; i <= h; i++)
            for(int j = 1; j <= w; j++)
                cin >> field[i][j];
        
        for(int i = 0; i < 4; i++)
            cin >> cs[i];
        

        for(int i = 0; i <= 30; i++)
            for(int j = 0; j <= 30; j++)
                fill(visited[i][j], visited[i][j] + 4, false);
        
        priority_queue<state, vector<state>, greater<state> > que;
        que.push((state){1, 1, 0, 1});
        
        int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
        while(!que.empty()) {
            state s = que.top(); que.pop();
            int x, y, c, d;
            x = s.x; y = s.y; c = s.c; d = s.d;
            if(visited[y][x][d])
                continue;

            visited[y][x][d] = true;

            if(x == w && y == h) {
                cout << c << endl;
                break;
            }

            for(int k = 0; k < 4; k++) {
                int nd = (d + k) % 4;
                int nx, ny, nc;
                nx = x + dx[nd];
                ny = y + dy[nd];
                if(k == field[y][x]) {
                    nc = c;
                } else {
                    nc = c + cs[k];
                }
                if(nx >= 1 && nx <= w && ny >= 1 && ny <= h)
                    que.push((state){nx, ny, nc, nd});
            }
        }
    }
}

Measured memory_bytes: 1044
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <iostream>
#include <math.h>
#include <time.h>
#include <unistd.h>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>

#ifndef ONLINE_JUDGE
	#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#else
	#define DEBUG(x) do {} while(0);
#endif

#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define FOR(i, A, N) for(int (i) = (A); (i) < (N); (i)++)
#define REP(i, N) for(int (i) = 0; (i) < (N); (i)++)

using namespace std;
typedef long long ll;
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

int n,m;
char S[5], T[5];

int main() {
	scanf("%s%s", S, T);
	int ans = 0;
	REP(i, 3) if(S[i] == T[i]) ans++;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int n,x1,x2,min,max;
    long long sum;
    scanf("%d %d",&n,&x1);
    min = x1;
    max = x1;
    sum = x1;
    for(int i = 2;n >= i;i++){
        scanf("%d",&x2);
        if(min >= x2){
            min = x2;
        }else{
            min = min;
        }
        if(max <= x2){
            max = x2;
        }else{
            max = max;
        }
        sum = sum + x2;
    }
    printf("%d %d %lld\n",min,max,sum);
    
    return 0;
}


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

using namespace std;

const int M = 1e5 + 5;
int n, t[M][3];
long long dp[M][3];

long long solve (int d, int a) {
    if (d >= n) return 0;
    long long &ret = dp[d][a];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i < 3; i++) {
        if (i != a) ret = max (ret, solve(d+1, i) + t[d+1][i]);
    }
    return ret;
}

int main () {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", &t[i][j]);
        }
    }
    memset(dp, -1, sizeof dp);
    long long ans = 0;
    for (int i = 0; i < 3; i++) ans = max (ans, solve (0, i)+t[0][i]);
    cout << ans;
}


Measured memory_bytes: 11520
#include <stdio.h>
#include <iostream>

#define abs(a) (a<0?-(a):a)
#define square(x) ((x)*(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(a,b) ((a!=b)?(a+=b,b=a-b,a-=b):0)
#define This
#define True true
#define False false
#define null Null


using namespace std;
int N;
void maxHeapify(int num[],int i){
	int left=2*i;
	int right=2*i+1;
	int largest;
	if(left<=N&&num[left]>num[i]){
		largest=left;	
	}else{
		largest=i;
	}
	if(right<=N&&num[right]>num[largest]){
		largest=right;
	}

	if(largest!=i){
		swap(num[i],num[largest]);
		maxHeapify(num,largest);
	}
}

void buildMaxHeap(int num[]){
	for(int i=N/2;i>=1;i--){
		maxHeapify(num,i);
	}

	for(int i=1;i<=N;i++){
		cout<<" "<<num[i];
	}
	cout<<endl;
}
int main(){
	int num[1000000];
	cin>>N;
	for(int i=1;i<=N;i++){
		cin>>num[i];
	}
	buildMaxHeap(num);
}



Measured memory_bytes: 4996
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut 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! {
        a: i32,
        b: i32,
        c: i32,
        d: i32,
        e: i32,
        k: i32,
    }

    if e - a <= k {
        println!("Yay!")
    } else {
        println!(":(")
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

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


using namespace std;

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

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


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

int main() {
    string s;cin>>s;
    int w;cin>>w;
    int j = 0;
    while(j*w<s.size()){
        cout<<s[j*w];
        j++;
    }
    cout<<endl;
    return 0;
}




Measured memory_bytes: 256
//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
   
    
    // cinを高速にするためのおまじない
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    /////////////////////
    // Write code below /
    /////////////////////
    int N;
    cin >> N;
    int s=N%10;
    for(int i=1;i<9;i++){
        int n=1;
        for(int j=0;j<i;j++){
            n*=10;
        }
        s+=N%(n*10)/n;
    }
    if(N%s==0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }

    
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void){
  int a,b,count=0;
  cin>>a>>b;
  for(int i=a;i<=b;i++){
  	int dumy[5],j;
    j=i;
    dumy[0]=j/10000;
    j%=10000;
    dumy[1]=j/1000;
    j%=1000;
    dumy[2]=j/100;
    j%=100;
    dumy[3]=j/10;
    j%=10;
    if(dumy[0]==j){
      if(dumy[1]==dumy[3]){
      	count+=1;
      }
    }
  }
  cout<<count<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 10000005
bool is_prime[NUM];

int main(){

	for(int i = 0; i < NUM; i++){
		is_prime[i] = true;
	}

	is_prime[0] = false;
	is_prime[2] = false;

	//偶数
	for(int i = 4; i < NUM; i += 2){
		is_prime[i] = false;
	}

	for(int i = 3; i < NUM; i += 2){
		if(!is_prime[i])continue;
		for(int k = 2*i; k < NUM; k += i){
			is_prime[k] = false;
		}
	}

	int N;

	scanf("%d",&N);

	if(N <= 2){
		printf("0\n");
		return 0;
	}

	int ans = 0;
	for(int i = 3; i <= N; i += 2){
		if(!is_prime[i])continue;
		if(is_prime[i+2]){
			ans++;
		}
	}

	ans *= 2;

	printf("%d\n",ans);

	return 0;
}



Measured memory_bytes: 13000
using System;

namespace B___Maximum_Sum
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var k = int.Parse(Console.ReadLine());
            var a = new int[3];
            for (var i = 0; i < 3; i++)
            {
                a[i] = int.Parse(input[i]);
            }
            var max = a[0];
            var total = 0;
            for (var i = 0; i < 3; i++)
            {
                max = Math.Max(max, a[i]);
                total += a[i];
            }
            var b = total - max;
            for (var i = 0; i < k; i++)
            {
                max *= 2;
            }
            Console.WriteLine(b+max);
        }
    }
}

Measured memory_bytes: 11092
N = int(input())
lsA = [0]+list(map(int,input().split()))
lsA2 = [int(lsA[i]) - i for i in range(1,N+1)]
lsA2.sort()
if N % 2 == 1:
    b = lsA2[N//2]
else:
    b = (lsA2[N//2-1] + lsA2[N//2])//2
ans = 0
for i in range(N):
    ans += abs(lsA2[i]-b)
print(ans)

Measured memory_bytes: 30792
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int> PI;
#define MAX 99999999
int main(){
    int n;
    while(cin>>n,n) {
        vi v(n);rep(i,n)cin>>v[i];
        sort(v.begin(), v.end());
        int ans=INF;
        for(int j=0; j<n-1;j++) ans=min(abs(v[j]-v[j+1]),ans);
        cout<<ans<<endl;
    }
}

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

#define pb push_back

using namespace std;

const int N = 2e5;

int n, q;

int a[N + 5], used[N + 5], add[N + 5];

vector <int> g[N + 5];

void dfs (int v = 1, int w = 0) {
	used[v] = true;
	w += add[v];
	a[v] = w;
	for (auto to : g[v]) {
		if (!used[to]) {
			dfs (to, w);
		}
	}
}

int main () {
	ios_base::sync_with_stdio (0), cin.tie (0), cout.tie (0);
	cin >> n >> q;
	for (int i = 1;i < n;i ++) {
		int l, r;
		cin >> l >> r;
		g[l].pb (r);
		g[r].pb (l);
	}
	for (int i = 1;i <= q;i ++) {
		int p, x;
		cin >> p >> x;
		add[p] += x;
	}dfs ();
	for (int i = 1;i <= n;i ++) {
		cout << a[i] << ' ';
	}
}


Measured memory_bytes: 21888
n=int(input())
a=[0]+list(map(int,input().split()))+[0]
total=0
for i in range(1,n+2):
    total+=abs(a[i]-a[i-1])
for i in range(1,n+1):
    ans=total-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1])
    print(ans)

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

int main() {
  int64_t a, b, c = 1;
  cin >> a >> b;
  rep(i, a-1) c *= (b-1);
  c *= b;
  cout << c << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <iostream>

using namespace std;

vector<int> po; 
long long int N;
long long int a;
long long int C;

int main(){
	scanf("%lld",&N);
	po.push_back(-1);
	for(int i=0;i<N;i++){
		scanf("%lld",&a);
		po.push_back(a);
	}

	for(int i=1;i<=N;i++){
		if(po[po[i]]==i)C++;
	}	
	
	
	printf("%lld\n",C/2);
	return 0;
}

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

int main() {
  long N;
  cin >> N;
  long min_dig = 15;
  for (long i = 1; i <= N; i++) {
    if (i > N / i) {break;}
    long num = N / i, digits = 0;
    if (i * num == N) {
      while (num != 0) {
        num /= 10;
        digits++;
      }
      if (digits < min_dig) min_dig = digits;
    }
  }
  cout << min_dig << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string>
int main(void)
{
	int N, i;
	int sum = 0;
	std::cin >> N;
	for (i = 1; i <= N; i++)
	{
		sum += 800;
		if (i % 15 == 0)
		{
			sum -= 200;
		}
	}
	std::cout << sum;
	

	return 0;
}
	

		
	

Measured memory_bytes: 256
#include<stdio.h>
#define N 100

int main(){
  int n, p[N+1], m[N+1][N+1], i, j, l, k;

  scanf("%d",&n);

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

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

  printf("%d\n",m[1][n]);

  return 0;
}



Measured memory_bytes: 2104
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        switch (S) {
            case "SUN":
                System.out.println(7);
                break;
            case "MON":
                System.out.println(6);
                break;
            case "TUE":
                System.out.println(5);
                break;
            case "WED":
                System.out.println(4);
                break;
            case "THU":
                System.out.println(3);
                break;
            case "FRI":
                System.out.println(2);
                break;
            case "SAT":
                System.out.println(1);
                break;
        }
    
    }
}


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

int main(void)
{
	long  int N,M;
	int not_one;
	long ans = 0;
	scanf("%ld %ld", &N, &M);
	if (N == 1 || M == 1) {
		if (N == M) {
			printf("1\n");
			return 0;
		}
		if (N == 1)not_one = M;
		else not_one = N;
		ans += not_one - 2;
	}
	else {
		ans += (N - 2)*(M - 2);
	}
	printf("%ld", ans);

	return 0;
}


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

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    int t = M * 1900 + (N - M) * 100;
    int p = 1 << M;
    int ans = t * p;
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
// 2014/07/29 Tazoe

#include <iostream>
#include <string>
using namespace std;

int main()
{
	while(true){
		string s;
		cin >> s;

		if(s=="-")
			break;

		int m;
		cin >> m;

		for(int i=0; i<m; i++){
			int h;
			cin >> h;

			string s1 = s.substr(0, h);
			string s2 = s.substr(h);

			s = s2+s1;
		}

		cout << s << endl;
	}

	return 0;
}

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

typedef vector<int> vi;
typedef pair<int, int> pi;

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

#define pb push_back
#define mp make_pair
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, b, e) for (int i = (b); i <= (int)(e); i++)
#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUGA(a) cout << #a << ": "; for (const auto& v: (a)) cout << v << endl

int H, W;
string S[2005];

int row[2005][2005];
int col[2005][2005];

signed main() {
    cin >> H >> W;
    REP(i, H) cin >> S[i];

    REP(i, H) {
        int pos = 0;
        int cnt = 0;
        REP(j, W) {
            if (S[i][j] == '.') {
                cnt++;
                if (j == W-1) {
                    REP2(k, pos, j) row[i][k] = cnt;
                }
            } else {
                REP2(k, pos, j - 1) row[i][k] = cnt;
                row[i][j] = 0;
                pos = j + 1;
                cnt = 0;
            }
        }
    }
    REP(j, W) {
        int pos = 0;
        int cnt = 0;
        REP(i, H) {
            if (S[i][j] == '.') {
                cnt++;
                if (i == H-1) {
                    REP2(k, pos, i) col[k][j] = cnt;
                }
            } else {
                REP2(k, pos, i - 1) col[k][j] = cnt;
                col[i][j] = 0;
                pos = i + 1;
                cnt = 0;
            }
        }
    }

    int ans = 0;
    REP(i, H) {
        REP(j, W) {
            ans = max(ans, col[i][j] + row[i][j] - 1);
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 35712
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1000000007;
const llint big=(llint)(2.19e15)+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
using pli=pair<llint,int>;
using daic=priority_queue<pli,vector<pli>,greater<pli>>;
int main(void){
	int n;cin>>n;
	string str;cin>>str;
	//11111111111101
	//daaaaaaaaaaabX
	//10111111111111
	//deffffffffffff
	int ap=-mod,bp=-mod,dp=-mod,ep=-mod,fp=-mod;
	int ans=0;
	for(int i=0;i<n;i++){
		int A=-mod,B=-mod,D=-mod,E=-mod,F=-mod;
		if(str[i]=='1'){
			maxeq(D,ans);
			maxeq(A,dp+1);
			maxeq(A,ap+1);
			maxeq(ans,bp+1);
			maxeq(F,fp+1);
			maxeq(F,ep+1);
			maxeq(ans,F);
		}else{
			maxeq(B,ap);
			maxeq(E,dp);
		}
		ap=A;bp=B;dp=D;ep=E;fp=F;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 900
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define MAX 100000
void inarray(int a[], int n){
    for(int i = 0; i < n; i++) cin >> a[i];
}

int main(){
    int k,a,b; cin >> k >> a >> b;
    if(k * (b/k) >= a) cout << "OK" << endl;
    else cout << "NG" << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
 
typedef vector<int> vi;;
typedef vector<ll> vll;

#define l() length()
#define sz() size()
 
#define b() begin()
#define e() end()
#define all(x) x.begin(), x.end()
 
#define pb(i) push_back(i)
#define PB() pop_back()
 
 
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define Fi first
#define Se second
 
const int maxx=1e6+9;
 
// Happy Coding!


vi findRange(int tax,double rate){
    int l=round(tax/rate);
    int r=round((tax+1)/rate);
    cout<<l<<" "<<r<<endl;
    return {l,r};
}

void solve(){
    
    int a,b;
    cin>>a>>b;
    
    int f=1;
    for(int i=0;i<1100;i++){
        // cout<<i*0.08<<" "<<i*0.1<<endl;
        if(int(i*0.08)==a && int(i*0.1)==b){
            cout<<i<<endl;
            f=0;
            break;
        }
    }
    if(f){
        cout<<-1<<endl;
    }
}





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

Measured memory_bytes: 3668
import java.util.Scanner;

public class Main {

    public static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
//        int n = Integer.parseInt(sc.next());
        String s = sc.next();
        int max = 0;
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'R') {
                cnt++;
                if (max < cnt) {
                    max = cnt;
                }
            } else {
                cnt = 0;
            }
        }
        System.out.println(max);
    }
}

Measured memory_bytes: 35676
#include <stdio.h>

int main(){
  int a, b;  scanf("%d%d", &a, &b);

  for(int i=13; i<1010; i++){
    if((int)(i*0.08) == a && (int)(i*0.1) == b){
      printf("%d\n", i);
      return 0;
    }
  }
  
  printf("-1\n");
  return 0;
}


Measured memory_bytes: 128
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7


X, Y = MI()

w = [0, 300000, 200000, 100000]
ans = 0
ans += w[X] if X <= 3 else 0
ans += w[Y] if Y <= 3 else 0
if X == 1 and Y == 1:
    ans += 400000
print(ans)


Measured memory_bytes: 38452
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [list(input()) for _ in range(n)]
#a = [input() for _ in range(n)]

x,y = map(int, input().split())

print(x+y//2)


Measured memory_bytes: 9036
#include<bits/stdc++.h>
using namespace std;
int main() 
  {
  int s, w;
  cin>>w;
  set<string> st;
  string ar[w];
  for(int i=0;i<w;i++)
    cin>>ar[i];
  for(int i=0;i<w;i++)
    st.insert(ar[i]);
  cout<<st.size();
  return 0;
  }


Measured memory_bytes: 25456
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9+7;

int main(void){

    string S; cin>>S;
    vector<int> A(4);
    for (int i = 0; i < 4; ++i) {
        A[i] = (int)(S[i]-'0');
    }

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                int sum=0;
                sum = A[0] + (i?A[1]:-A[1]) + (j?A[2]:-A[2]) + (k?A[3]:-A[3]);
                char op1 = i?'+':'-';
                char op2 = j?'+':'-';
                char op3 = k?'+':'-';
                if(sum==7){
                    cout<<A[0]<<op1<<A[1]<<op2<<A[2]<<op3<<A[3]<<"=7"<<endl;
                    return 0;
                }
            }
        }
    }

    return 0;
}

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

int main() {
  string T, S;
  cin >> S >> T;
  int ans = 10000;
  rep(i, S.size() - T.size() + 1) {
    int count = T.size();
    rep(j, T.size()) if (S.at(i + j) == T.at(j)) count--;
    ans = min(ans, count);
  }
  cout << ans;
}


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

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int n,k;
int main(){
    cin>>n>>k;
    vector<int> height(n);
    rep(i,n)cin>>height.at(i);
    vector<ll> cost(n+10000);
    rep(i,n+1)cost.at(i)=INF;
    cost.at(0)=0;
    rep(i,n){
        for(int j=1;j<=k;j++){
        if(((i-j)>=0))chmin(cost.at(i),cost.at(i-j)+abs(height.at(i)-height.at(i-j)));
        }
    }
    cout<<cost.at(n-1)<<endl;
    return 0;
}




Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=998244353;

int N;
char buf[114514];
LL dp[4145][4145];
int R[2145];
int B[2145];

int main() {
  scanf("%s", buf);
  N = strlen(buf);
  reps(i, 1, N+1) {
    R[i] = R[i-1];
    B[i] = B[i-1];
    if (buf[i-1] == '0') R[i] += 2;
    else if (buf[i-1] == '2') B[i] += 2;
    else if (buf[i-1] == '1') {
      R[i]++;
      B[i]++;
    } else assert(0);
  }

  dp[0][0] = 1;
  reps(i, 1, 2*N+1) {
    rep(a, i) {
      LL v = dp[i-1][a];
      int b = i-1 - a;

      int t = min(i, N);
      int rrem = R[t]-a;
      if (rrem > 0) {
        dp[i][a+1] += v;
        dp[i][a+1] %= MOD;
      }

      int brem = B[t]-b;
      if (brem > 0) {
        dp[i][a] += v;
        dp[i][a] %= MOD;
      }
    }
  }

  LL ans = 0;
  rep(i, 2*N+1) {
    ans += dp[2*N][i];
    ans %= MOD;
  }
  printf("%lld\n", ans);
}


Measured memory_bytes: 129536
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	
	int N;
	long double ans;
	
	cin>>N;
	
	for(int i = 0; i < N; i++){
		int A;
		
		cin>>A;
		
		ans += 1.0/A;
	}
	
	cout<<1/ans<<endl;
	return 0;
}

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

int main()
{
    int a, b;
    bool flag;
    while(~scanf("%d%d", &a, &b)) {
        if(a % 3 == 0 || b % 3 == 0 || (a+b)%3 == 0)
            flag = true;
        else
            flag = false;
        printf("%s\n", flag?"Possible":"Impossible");
    }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast","no-stack-protector","unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx")
//#include<bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;
#define F(i,L,R) for(int i=L;i<R;++i)
#define FE(i,L,R) for(int i=L;i<=R;++i)
#define getI(a) scanf("%d", &a)
#define getII(a,b) scanf("%d%d", &a, &b)
#define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define VgetI(n) int (n); scanf("%d",&(n))
#define VgetII(n,m) int (n),(m); scanf("%d %d",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k))
#define debug(x) cout<<(#x)<<"="<<x<<"\n";
#define qq cout<<"QQ\n";
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
#define ll long long
#define INF 2000000000
int main(){
	int x;
	while(~getI(x)){
		ll ans=x/500;
		ans*=1000;
		x%=500;
		ans+=(x/5*5);
		printf("%lld\n",ans);
	}
}


Measured memory_bytes: 256