akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(0); cin.tie(); cout.tie();

#define MAXX 500005
#define PI 3.14159265358979323846264338327950
#define F first
#define S second
#define ll  int
#define mod  1000000007



int main()
{
	FAST;
	ll a, b, c;
	ll k;
	cin >> a >> b >> c >> k;
	ll ans = 0;
	while(b <= a){
		b *= 2;
		ans ++;
	}
	while(c <= b){
		c *= 2;
		ans ++;
	}
	if(k >= ans){
		cout << "Yes";
		return 0;
	}
	cout << "No";
	
}

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

int main(){
  int A,B;
  cin >> A >> B;
  int n= max(A,B)-min(A,B);
  
  if(n==0){
    cout << 0;
  }
  else if(n==1){
    cout << "IMPOSSIBLE" << endl;
  }
  else{
    
    int s=0;
    for(int i=0;i<n;i++){
      if(s == 0){
        s=1;
      }
      else{
        s=0;
      }
    }
    if(s==0){
      cout << (A+B)/2 << endl;
    }
    else{
      cout << "IMPOSSIBLE" << endl;
    }
  }
}

Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]

#奇数項を正にする
oddS = (A[0] if A[0] > 0 else 1)
oddtotal = (0 if A[0] > 0 else 1 - A[0])
for i in range(1, N):
    if oddS > 0:
        if oddS + A[i] < 0: oddS += A[i]
        else:
            oddtotal += abs(-1 - (oddS + A[i]))
            oddS = -1
    elif oddS < 0:
        if oddS + A[i] > 0: oddS += A[i]
        else: 
            oddtotal += 1 - (oddS + A[i])
            oddS = 1

#偶数項を正にする
eS = (A[0] if A[0] < 0 else -1)
etotal = (0 if A[0] < 0 else A[0] + 1)
for i in range(1, N):
    if eS > 0:
        if eS + A[i] < 0: eS += A[i]
        else:
            etotal += abs(-1 - (eS + A[i]))
            eS = -1
    elif eS < 0:
        if eS + A[i] > 0: eS += A[i]
        else: 
            etotal += 1 - (eS + A[i])
            eS = 1

print(min(oddtotal, etotal))

Measured memory_bytes: 14332
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define f(i,j,n) for(int i=j;j<n;i++)
int main() {
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    while(1) {
        c = c - b;
        a = a - d;
        if(c <= 0) {
            cout<<"Yes"<<endl;
            break;
        }
        if(a <= 0) {
            cout<<"No"<<endl;
            break;
        }
    
    }
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>

using namespace std;

typedef long long ll;

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

int main() {
    string s; cin >> s;
    map<char, int> m;
    for(int i = 0; i < 4; ++i) ++m[s[i]];
    if (m.size() == 2 && m[s[0]] == 2) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<cstdio>

using namespace std;

int main() {
	long double x1, x2, y1, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	double a = sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
	printf("%lf\n", a);
	return 0;
}


Measured memory_bytes: 3280
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define VSORT(v) sort(v.begin(), v.end())
#define DVSORT(v) sort(v.begin(), v.end(),greater<int>())
#define SORT(v, n) sort(v, v+n)
#define DSORT(v,n) sort(v, v+n,greater<int>())
#define vi vector<int>
#define pb push_back
#define P pair<int,int>
 
template <class T> void chmin(T&a,const T&b) { a = min(a,b); }
template <class T> void chmax(T&a,const T&b) { a = max(a,b); }
 
void print(){cout<<endl;}
template <class Head, class... Tail>
void print(Head&& h,Tail&&... t){ 
	if(sizeof...(t)==0)
		cout<<h;
	else
		cout<<h<<' ';
	print(move(t)...);
}
 
const double EPS =1e-9;
const long INF =2147483647;//32bit 2*1e+9
const long MOD =1e+9+7;
#define PI 3.14159265258979
 
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

int main(void){
	int N;
	ll A[100005],B[100005],counter=0;
	cin>>N;
	REP(i,N) cin>>A[i]>>B[i];

	RREP(i,N){
		A[i]+=counter;
		if(A[i]%B[i]!=0) counter+=(B[i]-(A[i]%B[i]));
	}
	print(counter);
}


Measured memory_bytes: 1792
N,a,b=(int(x) for x in input().split())

num_char = (int(N /(a+b)))
num_joyo = (N %(a+b))
result = 0

if num_joyo <= a:
    result = num_char*a + (num_joyo)
else:
    result = num_char*a + a
    
print(result)

Measured memory_bytes: 3064
N,M = list(map(int,input().split()))

MAXN = 2*(10**5)+10
p = 10**9+7
MOD = p
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

def prime(X):
    pf={}
    m=X
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    return pf

pf = prime(M)
powers = list(pf.values())

out = 1
for power in powers:
    out = out*nCr(power+N-1,power)%p

print(out)

Measured memory_bytes: 79488
from sys import stdin

N = int(stdin.readline().rstrip())
ans = ''

if N == 0:
    print(0)
    exit()

while N != 0:
    if N % 2 == 1:
        N -= 1
        ans += '1'
    else:
        ans += '0'
    N //= -2

print(ans[::-1])

Measured memory_bytes: 38384
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <thread>
#include <tuple>
#include <limits>
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> init(n);
  for (int i = 0; i < n; i++) cin >> init[i];
  vector<int> state(n);
  for (int i = 0; i < n; i++) cin >> state[i];
  priority_queue<pair<int, int>> pq;
  vector<int> visit(n);
  for (int i = 0; i < n; i++) {
    pq.emplace(state[i], i);
    visit[i] = 1;
  }
  long long ans = 0;
  while (!pq.empty()) {
    auto last = pq.top(); pq.pop();
    int val = last.first, ind = last.second;
    visit[ind] = 0;

    if (val == init[ind]) continue;
    if (val < init[ind]) { ans = -1; break; }
    int lind = (ind + (n - 1)) % n, rind = (ind + 1) % n;
    int left = state[lind];
    int right = state[rind];
    int add = left + right;
    int rem = val - init[ind];
    if (rem < add) { continue; }
    ans += rem / add;
    state[ind] = val - add*(rem / add);
    if (visit[lind] == 0) { pq.emplace(state[lind], lind); visit[lind] = 1; }
    pq.emplace(state[ind], ind); visit[ind] = 1;
    if (visit[rind] == 0) { pq.emplace(state[rind], rind); visit[rind] = 1; }
  }
  if (state != init) ans = -1;
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 5748
mod = 10 ** 9 + 7
def ExtGCD(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = ExtGCD(b, a % b)
        x -= (a // b) * y
        return d, y, x
def ModInv(a, mod):
    return ExtGCD(a, mod)[1] % mod
def ModComb(n, k, mod):
    if n < k or n < 0 or k < 0:
        return 0
    elif n == 0 or k == 0:
        return 1
    q, a = 1, 1
    for i in range(n-k+1, n+1):
        q = (q * i) % mod
    for i in range(2, k+1):
        a = (a * i) % mod
    return int(q * ModInv(a, mod) % mod)
s = int(input())
digit = s // 3
ans = 0
for i in range(1, digit + 1):
    ans += ModComb(s-2*i-1, i - 1, mod)
print(ans % mod)

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

typedef long long ll;
ll MOD=1000000000 + 7;

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}


int main(){
    cout << setprecision(10);

    int N;
    cin >> N;
    ll h_max_a[N], h_min_a[N];
    ll h_max_b[N], h_min_b[N];
    ll h_max[N], h_min[N];

    ll now_max_h = 0;
    for(int i = 0; i < N; i++){
        ll h;
        cin >> h;
        if(now_max_h < h){
            h_max_a[i] = h;
            h_min_a[i] = h;
            now_max_h = h;
        } else { 
            h_max_a[i] = now_max_h;
            h_min_a[i] = 1;
        }
    }
    vector<ll> b_input(N);
    for(int i = 0; i < N; i++){
        cin >> b_input.at(i);
    }
    reverse(b_input.begin(), b_input.end());
    
    now_max_h = 0;
    for(int i = 0; i < N; i++){
        ll h;
        h = b_input[i];
        if(now_max_h < h){
            h_max_b[N-1-i] = h;
            h_min_b[N-1-i] = h;
            now_max_h = h;
        } else { 
            h_max_b[N-1-i] = now_max_h;
            h_min_b[N-1-i] = 1;
        }
    }

    ll ans = 1;
    bool flg = true;
    for(int i = 0; i < N; i++){
        h_max[i] = min(h_max_a[i], h_max_b[i]);
        h_min[i] = max(h_min_a[i], h_min_b[i]);
        if(h_max[i] < h_min[i]){
            flg = false;
            break;
        }
    }

    if(flg){
        for(int i = 0; i < N; i++){
            ans *= h_max[i] - h_min[i] + 1;
            ans %= MOD;
        }
    } else { 
        ans = 0;
    }
    cout << ans << endl;


}


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

const int mod = 1000000007;
 int dp[100005][2];

int main() {
  string s;
  cin >> s;
  int n = s.size();
  dp[0][0] = 1;
  // dp[0][1] = 0;
  rep(i,n) {
    { // a+b = 0
      if (s[i] == '0') {
        dp[i+1][0] = dp[i][0];
        dp[i+1][1] = dp[i][1];
      } else {
        dp[i+1][1] = (dp[i][0] + dp[i][1]) % mod;
      }
    }
    { // a+b = 1
      if (s[i] == '0') {
        (dp[i+1][1] += dp[i][1]*2 % mod) %= mod;
      } else {
        (dp[i+1][0] += dp[i][0]*2 % mod) %= mod;
        (dp[i+1][1] += dp[i][1]*2 % mod) %= mod;
      }
    }
  }
  int ans = (dp[n][0]+dp[n][1]) % mod;
  cout << ans << endl;
  // rep(i,n)cout<<dp[i+1][0];
  // cout << endl;
  // rep(i,n)cout << dp[i+1][1];
  // cout << endl;
  // cout << dp[0][1] << endl;
  return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 2e3 + 5, MAXM = 2e6 + 5, BOUND = 2e5, MOD = 10000, INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0), eps = 1e-6;
#define mid l + ((r-l)>>1)
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define lc(x) c[x][0]
#define rc(x) c[x][1]
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
char gdffsaw;
#define G gdffsaw=getchar()
#define GO G;while(gdffsaw<'-')G
#define in(z) GO;z=gdffsaw&15;G;while(gdffsaw>'-')z*=10,z+=gdffsaw&15,G
int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
	while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
int n, m, b[MAXN], a[MAXN], c;
int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> c;
	rep(i, 1, m) {
		cin >> b[i];
	}
	int ans = 0;
	rep(i, 1, n) {
		int sum = 0;
		rep(j, 1, m) {
			cin >> a[j];
			sum += a[j] * b[j];
		}
		if (sum + c > 0)ans++;
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <utility>
#include <assert.h>
using namespace std;

typedef unsigned long long ull;
typedef signed long long ll;
#define INF (1LL << 62)

int main(int argc, char* argv[])
{
	for (;;) {
		ll n, s;
		cin >> n >> s;
		if (cin.fail()) break;

		auto solve = [n, s]() -> ll {
			auto test = [n, s](ll b) {
				ll rr = 0;
				ll nn = n;
				while (nn) {
					rr += nn % b;
					nn /= b;
				}
				return rr == s;
			};

			if (n == s) return n + 1;

			ll sqrt_n = (ll) floor(sqrt(n));
			for (ll b = 2; b <= sqrt_n; b++) {
				if (test(b)) {
					return b;
				}
			}

			ll result = INF;
			for (ll p = 1; p <= sqrt_n; p++) {
				ll b = (n - s) / p + 1;
				if (b > 1 && test(b)) {
					result = min(result, b);
				}
			}

			return result == INF ? -1 : result;
		};

		printf("%lld\n", solve());
	}

	return 0;
}


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

struct FenwickTree{
  vector<int> f;
  void init(int n){
      f.assign(n+1, 0);
  }
  void update(int p, int val){
      for(int i=p; i< f.size(); i+= i&(-i)) f[i] += val;
  }
  int get(int p){
      if(p==0) return 0;
      return f[p] + get(p-(p&(-p)));
  }
};

const int MAXN = 1E6+2;
const int MOD = 1E9+7;
FenwickTree fen;

int n, k;
vector<int> a(MAXN);
int C1 =0 , C2 = 0;

void compress(){
    vector<int> id(n+1), val(n+1, 0);
    iota(id.begin()+1, id.begin()+n+1, 1);
    sort(id.begin()+1, id.begin()+n+1, [&](int x, int y){
        if(a[x] == a[y]) return x < y;
        return a[x] < a[y];
    });
    val[id[1]] = 1; 
    for(int i=2; i<= n; ++i){
        if(a[id[i]] == a[id[i-1]]) val[id[i]] = val[id[i-1]];
        else val[id[i]] = val[id[i-1]]+1;
    }
    for(int i=1; i<= n; ++i) a[id[i]] = val[id[i]];
}

int count(int o){
    if(o==0) return 0;
    if(o&1) return (count(o-1) + C1 + (o-1)*C2)%MOD;
    else return ((2*count(o>>1)%MOD) + (((o*o/4)%MOD)*C2)%MOD)%MOD;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
   // freopen("DUP.INP", "r", stdin);
    //freopen("DUP.OUT", "w", stdout);
    cin >> n >> k;
    for(int i=1; i<= n; ++i){
        cin >> a[i];
    }
    compress();
    fen.init(n);
    for(int i=n; i>= 1; --i){
        C1 += fen.get(a[i]-1);
        C1 %= MOD;
        fen.update(a[i], 1);
    }
    for(int i=1; i<= n; ++i){
      C2 += fen.get(a[i]-1);
      C2 %= MOD;
    } 
    cout << count(k);
}


Measured memory_bytes: 8064
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

import math
import string
import fractions
import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop

# from itertools import accumulate
# from collections import deque
import random


def main():
    n = int(input())
    dict={}
    for i in range(n):
        name, score= input().split()
        if not(name in dict):
            dict[name]=[((int(score),i+1))]
        else:
            dict[name].append((int(score),i+1))
            dict[name].sort(reverse=True)
    eprint(dict)
    ll=list(dict.items())
    eprint(ll)
    ll.sort()
    eprint(ll)
    for x in ll:
        for y in x[1]:
            print(y[1])
        
if __name__ == '__main__':
    main()


Measured memory_bytes: 65388
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const int INF = 1e9;
const int MOD = 1000000007;

int main() {
  int n, x;
  cin >> n >> x;
  vector<int>l(n);
  rep(i,n) cin >> l[i];
  vector<int>s(n+1);
  s[0]=0;
  rep(i,n) s[i+1]=s[i]+l[i];
  rep(i,n+1){
    if(s[i]>x){
      cout << i << endl;
      return 0;
    }
  }
  cout << n+1 << endl;
  
}

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

using namespace std;
int main()
{
	int N,M,X,Y,x[110],y[110],max = -1,min =100000000;
	cin >> N >> M >> X >> Y;
	for(int i=0; i<N; i++){
		cin >>x[i];
		if(max < x[i])
			max = x[i];
	}
	for(int i=0; i<M; i++){
		cin >> y[i];
		if(y[i] < min)
			min = y[i];
	}
	
	if(max < min && X < min && max < Y){
		cout << "No War" << endl;
	}else{
		cout << "War" << endl;
	}
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <deque>
#include <iomanip>
#include <queue>
using namespace std;
#define rep(i,n) for (ll i=0;i<n;i++)
#define REP(i,n) for (ll i=1;i<=n;i++)
#define PI 3.1415926535897932384626433832795028841971693993751058209749445923078160628620899
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9 + 7;
const ll INF = 1000000000000000;

string S;

ll W (ll N) {
	return N * (N + 1) / 2;
}

int main() {
	cin >> S;
	ll N = S.size();
	ll ans[500010] = { 0 };
	ll nowL = 0;
	ll nowP = 0;
	ll sum = 0;
	rep(i, N + 1) {
		if (i == 0) {
			if (S[0] == '<') ans[0] = 0;
			else {
				nowL = 1;
				nowP = 0;
			}
		}
		else if (i == N) {
			if (S[N - 1] == '>') {
				if (nowL >= nowP) sum += W(nowL);
				else {
					sum += nowP;
					sum += W(nowL - 1);
				}
			}
			else {
				ans[N] = ans[N - 1] + 1;
				sum += ans[N];
			}
		}
		else {
			if (S[i - 1] == '>' && S[i] == '<') {
				ans[i] = 0;
				if (nowL >= nowP) sum += nowL*(nowL+1)/2;
				else {
					sum += nowP;
					sum += nowL*(nowL - 1)/2;
				}
				nowL = 0;
				nowP = 0;
			}
			else if (S[i - 1] == '<' && S[i] == '<') {
				ans[i] = ans[i - 1] + 1;
				sum += ans[i];
			}
			else if (S[i - 1] == '>' && S[i] == '>') {
				nowL++;
			}
			else {
				nowP = ans[i - 1] + 1;
				nowL = 1;
			}
		}
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 4740
#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int w,h,x,y,r;
	scanf("%d",&w);
	scanf("%d",&h);
	scanf("%d",&x);
	scanf("%d",&y);
	scanf("%d",&r);

	if(x-r<0 || y-r<0 || x+r>w || y+r>h)printf("No\n");
	else printf("Yes\n");

	return EXIT_SUCCESS;
}

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

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
	
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;

int main(){
    //freopen("in.txt", "r", stdin);

    int n, m, a, b;
    cin>>n>>m;
    vector<pair<int, int> > jobs(n);

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

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

    ll reward = 0;
    multiset<int> s;
    int j = 0;
    for (int day=m-1;day>=0;day--){
        for (;j<n;++j){
            if (jobs[j].first <= m-day){
                s.insert(-jobs[j].second);
            }
            else break;
        }
        if (!s.empty()){
            multiset<int>::iterator it = s.begin();
            reward += -(*it);
            s.erase(it);
        }
    }
    cout<<reward<<endl;

    return 0;
}

Measured memory_bytes: 5632
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define INF INT_MAX
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int main(){
   cin.tie(0);
   ios::sync_with_stdio(false);
   int r,x,d;
   cin>>r>>d>>x;
   FOR(i,10){
     x=r*x-d;
     cout<<x<<endl;
   }
   return 0;
}


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

using ll = long long;
using pii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;

template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

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

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define debug(x) cerr << #x << ": " << x << endl;
#define int ll

const ll mod = 1e9 + 7;
const ll inf = (1LL << 50);

long double dp[301][301][301];
long double ans = 0;

long double rec(int i, int j, int k, int NN) {
    int N = i + j * 2 + k * 3;
    if (i < 0 or j < 0 or k < 0 or i > NN or j > NN or k > NN) return 0;
    if (dp[i][j][k] >= 0) return dp[i][j][k];
    long double ret = 0;
    ret += rec(i + 1, j, k, NN) * (long double)(i + 1) / (long double)(i + j + k + 1);
    ret += rec(i - 1, j + 1, k, NN) * (long double)(j + 1) / (long double)(i + j + k);
    ret += rec(i, j - 1, k + 1, NN) * (long double)(k + 1) / (long double)(i + j + k);
    ans += (long double)NN / (long double)(i + j + k) * ret;
    // cout << i << " " << j << " " << k << " " << ret << " " << (long double)NN / (long double)(i + j + k) * ret << endl;
    return dp[i][j][k] = ret;
}

void solve(long long N, std::vector<long long> a) {
    memset(dp, -1, sizeof(dp[0][0][0]) * 301 * 301 * 301);

    {
        vi n(4, 0);
        rep(i, N) n[a[i]]++;
        // cout << n[1] << " " << n[2] << " " << n[3] << endl;
        dp[n[1]][n[2]][n[3]] = 1.0;
    }

    rec(1, 0, 0, N);
    cout << ans + 1 << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    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: 426752
from collections import defaultdict

n, m = map(int, input().split())
ps = []
for _ in range(m):
    ps.append(input().split())

sub_st = defaultdict(list)
for p, s in ps:
    sub_st[p].append(s)

solved = 0
error = 0
for k, v in sub_st.items():
    temp_error = 0
    for history in v:
        if 'AC' in history:
            error += temp_error
            solved += 1
            break
        temp_error += 1

print(solved, error)


Measured memory_bytes: 51388
local h,w=io.read("n","n","l")
local a={}
local dist={}
for i=1,h do
    local input=io.read()
    a[i]={}
    dist[i]={}
    for j=1,w do
        a[i][j]=input:byte(j)
        dist[i][j]=-1
    end
end

local que={}
for i=1,h do
    for j=1,w do
        if a[i][j]==35 then
            dist[i][j]=0
            table.insert(que,{i,j})
        end
    end
end

local di={1,0,-1,0}
local dj={0,1,0,-1}
local l=1
while que[l] do
    local i=que[l][1]
    local j=que[l][2]
    for k=1,4 do
        local ni=i+di[k]
        local nj=j+dj[k]
        if dist[ni] and dist[ni][nj] and dist[ni][nj]==-1 then
            dist[ni][nj]=dist[i][j]+1
            table.insert(que,{ni,nj})
        end 
    end
    l=l+1
end

local max=0
for i=1,h do
    for j=1,w do
        max=math.max(max,dist[i][j])
    end
end
print(max)

Measured memory_bytes: 89372
def main():
    A=[]
    box=[]
    q=int(input())
    for i in range(q):
        query=input()
        if query.isdigit():
            A.pop(-1)
        else:
            que,num=map(int,query.split())
            if que==0:
                A.append(num)
            elif que==1:
                box.append(A[num])

    for a in box:
        print(a)

if __name__=='__main__':
    main()



Measured memory_bytes: 13364
#include<stdio.h>
#include<string.h>
typedef struct qs{
  char c;
  int n;
  int h;
}Q;
 
int main(void){
  int n,i,count=0;
  Q q[100000];
 
  scanf("%d",&n);
 
  for(i=0;i<n;i++)
    q[i].h=i;
  for(i=0;i<n;i++)
    scanf(" %c %d",&q[i].c,&q[i].n);
 
  Quicksort(&q[0],0,n-1);
 
  for(i=1;i<n;i++)
    if(q[i-1].n==q[i].n && q[i-1].h>q[i].h)
      count++;
 
  if(count>0)
    printf("Not stable\n");
 
  else
    printf("Stable\n");
 
  for(i=0;i<n;i++)
    printf("%c %d\n",q[i].c,q[i].n);
 
  return 0;
}
int Partition(Q *A,int p,int r){
  int i,x,j,tmp1;
  char tmp2;
  x = A[r].n;
    
  i = p-1;
  for(j = p;j <= r-1;j++){
    if(A[j].n <= x){
      i = i + 1;
      tmp1=A[i].n;
      A[i].n=A[j].n;
      A[j].n=tmp1;
      tmp2=A[i].c;
      A[i].c=A[j].c;
      A[j].c=tmp2;
      tmp1=A[i].h;
      A[i].h=A[j].h;
      A[j].h=tmp1;
    }
  }
  tmp1=A[i+1].n;
  A[i+1].n=A[r].n;
  A[r].n=tmp1;
  tmp2=A[i+1].c;
  A[i+1].c=A[r].c;
  A[r].c=tmp2;
  tmp1=A[i+1].h;
  A[i+1].h=A[r].h;
  A[r].h=tmp1;
  return i+1;
}
void Quicksort(Q *A,int p,int r){
  int q;
  if(p < r){
    q = Partition(A, p, r);
    Quicksort(A, p, q-1);
    Quicksort(A, q+1, r);
  }
}

Measured memory_bytes: 1776
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int l;
	cin>>l;
	int n=0,r=1;
	while(r<=l){
		r*=2;
		n++;
	}
	vector<vector<Pi>> g(n);
	rep(i,n-1){
		g[i].push_back(Pi(i+1,0));
		g[i].push_back(Pi(i+1,1<<i));
	}
	int ret=l-(1<<(n-1));
	int x=(1<<(n-1));
	rep(i,n-1){
		if(ret & (1<<i)){
			g[i].push_back(Pi(n-1,x));
			x+=(1<<i);
		}
	}	
	int m=0;
	rep(i,n){
		m+=g[i].size();
	}
	cout<<n<<' '<<m<<endl;
	rep(i,n-1){
		rep(j,g[i].size()){
			cout<<i+1<<' '<<g[i][j].fi+1<<' '<<g[i][j].se<<endl;
		}
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <regex>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;

vector<string> dfs(string s, ll depth, vector<char> symbol)
{
    vector<string> ret;
    if (depth == 0)
    {
        ret.push_back(s);
        return ret;
    }

    for (ll i = 0; i < symbol.size(); i++)
    {
        auto vec = dfs(s + symbol[i], depth - 1, symbol);
        for (auto &&e : vec)
        {
            ret.push_back(e);
        }
    }
    return ret;
}

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

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

    string ans;
    if (A >= B) {
        ans = "delicious";
    } else if (X >= (B - A)) {
        ans = "safe";
    } else {
        ans = "dangerous";
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var value = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
           Console.WriteLine(value[0] + value[1] / 2);
            
        }

        
    }
}


Measured memory_bytes: 13268
N = int(input())
A = ([int(input()) for n in range(N)])
sorted_A = sorted(A)
max_ = sorted_A[len(A)-1]
semi_max = sorted_A[len(A)-2]


for i in range(N):
    if(A[i]==max_):
        print(semi_max)
    else:
        print(max_)

Measured memory_bytes: 14112
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<25);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int d[2][100100],u[100100],v[100100];

vector<int> g[100100];
queue<int> q;

int main(void){
	int n,a[2],i,k,s,t,ans=-INF;
	cin >> n >> a[0] >> a[1]; --a[0]; --a[1];
	fill(d[0],d[2],INF);
	for(i=1; i<n; ++i){
		cin >> u[i] >> v[i];
		--u[i]; --v[i];
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	for(k=0; k<2; ++k){
		q.push(a[k]);
		d[k][a[k]] = 0;
		while(!q.empty()){
			s = q.front();
			q.pop();
			for(i=(g[s].l_ength()-1); i>=0; --i){
				t = g[s][i];
				if(d[k][t] > d[k][s] + 1){
					d[k][t] = d[k][s] + 1;
					q.push(t);
				}
			}
		}
	}
	for(i=0; i<n; ++i){
		if(d[0][i] < d[1][i]){
			ans = max(ans,d[1][i]);
		}
	}
	cout << (ans-1) << endl;
	return 0;
}



Measured memory_bytes: 7424
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9;
const int mod = 1e9+7;

vector<int> fac(300001); //n!(mod M)
vector<int> ifac(300001); //k!^{M-2} (mod M)

long long fpow(long long a,long long n){
  long long ret=1;
  if(n==1) return a;
  if(n%2==0) {
      ret = fpow(a*a%mod, n/2) %mod ;
  }else {
      ret = (a%mod)*fpow(a*a%mod, n/2) %mod;
  }
  return ret %mod;
}
int comb(int a, int b){ //aCbをmod計算
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    int tmp = ifac[a-b]* ifac[b] % mod;
    return tmp * fac[a] % mod;
}
const int D = 60;
int to[D][MX];


signed main(){
    string s;
    cin >> s;
    bool f = true;
    if(s[0]!='A') f = false;
    if(count(s.begin()+2, s.end() - 1, 'C') != 1) f = false;
    for(char c: s) {
        if(c != 'A' && c != 'C' && isupper(c)) f = false;
    }
    if(f) cout << "AC" << endl;
    else cout << "WA" << endl;
}

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

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

int a[3010][3010];
ll dp[3010][3010][4];

int main(){
  int R,C,K;
  cin>>R>>C>>K;
  rep(i,K){
    int r,c,v; cin>>r>>c>>v;
    a[r-1][c-1]=v;
  }
  for(int i=0; i<R; ++i){
    for(int j=0; j<C; ++j){
      for(int k=2; k>=0; --k){
        chmax(dp[i][j][k+1],dp[i][j][k]+a[i][j]);
      }
      rep(k,4){
        chmax(dp[i+1][j][0],dp[i][j][k]);
        chmax(dp[i][j+1][k],dp[i][j][k]);
      }
    }
  }
  ll ans=0;
  rep(i,4)chmax(ans,dp[R-1][C-1][i]);
  cout<<ans<<endl;
}

Measured memory_bytes: 321120
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

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

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
    
    int a, b;
    char s[max];
    int cnt=0;
    
    scanf("%d%d%s", &a, &b, s);
    
    for (int i=0; i<a; i++) {
        if (s[i]>='0'&&s[i]<='9') {
            cnt++;
        }
    }
    for (int i=a+1; i<a+b+1; i++) {
        if (s[i]>='0'&&s[i]<='9') {
            cnt++;
        }
    }
    if (s[a]=='-') {
        cnt++;
    }
    
    if (cnt==a+b+1) {
        printf("Yes");
    } else {
        printf("No");
    }
    
    return 0;
}


Measured memory_bytes: 1736
#include "bits/stdc++.h"
using namespace std;


int main() {
	int a, b; cin >> a >> b;
	vector<int>v{ 1868,1912,1926,1989 };
	vector<char>c{ 'M','T','S','H' };
	if (a == 0) {
		auto it = std::upper_bound(v.begin(), v.end(), b);
		assert(it != v.begin());
		int k = it - v.begin() - 1;
		cout << c[k] << (b - v[k] + 1) << endl;
	}
	else {
		cout << v[a - 1] + b - 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3124
#include <iostream>
#include <vector>

using namespace std;

long long d[100001];
bool visited[100001];
vector<vector<pair<int, int>>> es(100001);

void dfs(int v) {
	visited[v] = true;
	for (auto &p : es[v]) {
		if (visited[p.first]) continue;
		d[p.first] = d[v] + p.second;
		dfs(p.first);
	}
}


int main(int argc, char *argv[]) {
	int N;
	cin >> N;

	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		es[a].push_back(make_pair(b, c));
		es[b].push_back(make_pair(a, c));
	}

	int Q, K;
	cin >> Q >> K;

	dfs(K);

	for (int i = 0; i < Q; i++) {
		int x, y;
		cin >> x >> y;
		cout << d[x] + d[y] << endl;
	}

	return 0;
}

Measured memory_bytes: 11904
#include "bits/stdc++.h"
using namespace std;

const int N=3e3+20,MOD=998244353;

int n,s,x,dp[N][N],ans;

int main()
{
	cin>>n>>s;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		memcpy(dp[i],dp[i-1],sizeof(dp[0]));
		dp[i][x]=(dp[i][x]+i)%MOD;
		for(int j=0;j+x<=s;j++)
			dp[i][j+x]=(dp[i][j+x]+dp[i-1][j])%MOD;
		ans=(dp[i][s]+ans)%MOD;
	}
	cout<<ans;
}

Measured memory_bytes: 35584
#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 is_month(string s) {
  int x = stoi(s);
  return 0 < x and x <= 12;
}

int main() {
  string S;
  cin >> S;
  bool x1 = is_month(S.substr(0, 2));
  bool x2 = is_month(S.substr(2, 2));
  string ret;
  if (x1 and x2) ret = "AMBIGUOUS";
  else if (x1) ret = "MMYY";
  else if (x2) ret = "YYMM";
  else ret = "NA";
  cout << ret << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cassert>
using namespace std;
const int dx[4]={0,-1,0,1};
const int dy[4]={1,0,-1,0};
const char dir[4]={'r','u','l','d'};
const int N=4;
const int N2=16;
const int LIMIT=45;
int MDT[N2][N2];
struct Puzzle
{	
	int f[N2],space;
	int MD;
};
Puzzle state;
int limit;
int path[LIMIT];
int getALLMD(Puzzle pz)
{
	int sum=0;
	
	for(int i=0;i<N2;i++)
	{
		if(pz.f[i]==N2);
		else sum+=MDT[i][pz.f[i]-1];
	}
	
	return sum;
}
int check(int x,int y)
{
	if(x<0||y<0||x>=N||y>=N)return 0;
	return 1;
}
int dfs(int depth,int prev)
{
	if(state.MD==0)return 1;
	if(depth+state.MD>limit)return 0;
	
	int sx=state.space/N;
	int sy=state.space%N;
	
	Puzzle tmp;
	
	for(int r=0;r<4;r++)
	{
		int tx=sx+dx[r];
		int ty=sy+dy[r];
		
		if(!check(tx,ty))continue;
		if(max(prev,r)-min(prev,r)==2)continue;
		
		tmp=state;
		
		int nt,ns;
		nt=tx*N+ty;
		ns=sx*N+sy;
		state.MD-=MDT[nt][state.f[nt]-1];
		state.MD+=MDT[ns][state.f[nt]-1];
		
		swap(state.f[tx*N+ty],state.f[sx*N+sy]);
		state.space=tx*N+ty;
		if(dfs(depth+1,r))
		{
			path[depth]=r;
			return 1;
		}
		state=tmp;
	}
	return 0;
}
string iterative_deepening(Puzzle in)
{
	in.MD=getALLMD(in);
	
	for(limit=in.MD;limit<=LIMIT;limit++)
	{
		state=in;
		if(dfs(0,-100))
		{
			string ans="";
			
			for(int i=0;i<limit;i++)
				ans+=dir[path[i]];
			return ans;
		}
    }
}
int main()
{
	for(int i=0;i<N2;i++)
	   for(int j=0;j<N2;j++)
	       MDT[i][j]=abs(i/N-j/N)+abs(i%N-j%N);
	
	Puzzle in;
	
	for(int i=0;i<N2;i++)
	{
		cin>>in.f[i];
		
		if(in.f[i]==0)
		{
			in.f[i]=N2;
			in.space=i;
		}
	}
	
	string ans=iterative_deepening(in);
	
	cout<<ans.size()<<endl;
	return 0;
}

Measured memory_bytes: 3216
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int ctoi(char c) {return c-'0';}// char to int
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}//MAX
int lcm(ll a,ll b){return a*b/gcd(a,b);}//MIN
 
int  main(){
string s;
cin >> s;
if(s=="keyence"){cout<<"YES"<<endl;return 0;}
int n = s.size();
for(int i=0;i<n;i++){
    for(int j=i;j<n;j++){
        string t;
        for(int k=0;k<n;k++){
            if(i<=k&&k<=j)continue;
            else t+=s.at(k);
        }
        if(t=="keyence"){cout<<"YES"<<endl;return 0; }
    }

    }
    cout <<"NO"<<endl; return 0;
}

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

const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;
int x[N], y[N];
char op[N][2];
int n;
vector<pair<int, char> > v1[N << 1];
vector<pair<int, char> > v2[N << 1];

void Rotate() {
	for(int i = 1; i <= n; i++) {
		int xx = y[i], yy = 200000 - x[i];
		char ch = op[i][0];
		if(ch == 'U') ch = 'R';
		else if(ch == 'R') ch = 'D';
		else if(ch == 'D') ch = 'L';
		else ch = 'U';
		x[i] = xx, y[i] = yy, op[i][0] = ch;
	}
}

int cacl1() {
	for(int i = 0; i < N * 2; i++) v1[i].clear();
	int res = inf;
	for(int i = 1; i <= n; i++) {
		if(!(op[i][0] == 'R' || op[i][0] == 'U')) continue;
		v1[x[i] + y[i]].push_back({x[i], op[i][0]});
	}
	for(int i = 0; i < N * 2; i++) {
		sort(v1[i].begin(), v1[i].end());
		for(int j = 0; j < (int)v1[i].size() - 1; j++) {
			if(!(v1[i][j].second == 'R' && v1[i][j + 1].second == 'U')) continue;
			res = min(res, v1[i][j + 1].first - v1[i][j].first);
		}
	}
	if(res == inf) return inf;
	return res * 10;
}

int cacl2() {
	for(int i = 0; i < N * 2; i++) v2[i].clear();
	int res = inf;
	for(int i = 1; i <= n; i++) {
		if(!(op[i][0] == 'R' || op[i][0] == 'L')) continue;
		v2[y[i]].push_back({x[i], op[i][0]});
	}
	for(int i = 0; i < N * 2; i++) {
		sort(v2[i].begin(), v2[i].end());
		for(int j = 0; j < (int)v2[i].size() - 1; j++) {
			if(!(v2[i][j].second == 'R' && v2[i][j + 1].second == 'L')) continue;
			res = min(res, v2[i][j + 1].first - v2[i][j].first);
		}
	}
	if(res == inf) return inf;
	return res * 5;
}

void solve() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d%d%s", &x[i], &y[i], &op[i]);
	}
	int res = inf;

	for(int i = 1; i <= 4; i++) {
		res = min(res, cacl1());
		res = min(res, cacl2());
		Rotate();
	}
	if(res == inf) puts("SAFE");
	else printf("%d\n", res);
}

int main() {
//    freopen("in.txt", "r", stdin);
	solve();
	return 0;
}


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

int main() {
	int D;
	cin >> D;
	D = 25 - D;
	string S = "Christmas";
	rep(i, D){
		S += " Eve";
	}
	cout << S << endl;
	return 0;
}


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

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

  for (int i = 0; i < N; i++) {
    cin >> color;
    if (color == "Y") {
      cout << "Four" << endl;
      break;
    }
    
    if (i == N - 1 && color != "Y") {
      cout << "Three" << endl;
    }
  }
}



Measured memory_bytes: 256
// inputに入力データ全体が入る
function Main(input) {
    // 1行目がinput[0], 2行目がinput[1], …に入る
    input = input.split("\n");
    tmp = input[1].split(" ");
    //文字列から10進数に変換するときはparseIntを使います
    var human = parseInt(input[0], 10);
    var day = parseInt(tmp[0], 10);
    var kekka = parseInt(tmp[1], 10);
    for (var i = 1;i <= human;i++) {
        if (day % input[i+1] == 0) {
            kekka += day / input[i+1];
        } else {
            var a = day / parseInt(input[i + 1], 10) ;
            kekka += Math.floor(a) + 1;
        }
    }
    //出力
    console.log(kekka);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
from __future__ import print_function

import sys

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction
from math import gcd
# fractions.gcd() を用いること
# math.log2()はatcoderでは対応していない．留意せよ．

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def lcm(n, m):
    return int(n * m / gcd(n, m))


def coprimize(p, q):
    common = fractions.gcd(p, q)
    return (p // common, q // common)


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


def find_gcd(list_l):
    x = reduce(gcd, list_l)
    return x


def main():
    k = int(input().strip())
    ans=0
    for i in range(1,k+1):
        for j in range(1,k+1):
            for k in range(1,k+1):
                ans += find_gcd([i,j,k])
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 79284
#include <iostream>
using namespace std;
int n, c, mx;
string s;
int main() {
	cin>>n>>s;
	for(int i=0; s[i]; i++) {
		if(s[i]=='I') c++, mx = max(mx, c);
		else c--;
	}
	cout<<mx;
	return 0;
}

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

using namespace std;

#define ll long long

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

const int mod = 998244353;

bool m[2 * 2000000 + 1];

int main(){

	cin.tie(0);
	cin.sync_with_stdio(0);

	#ifdef Cyborg101
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

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

	int a[n], b[n];

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

	ll res = 0;
	for(int i = 0; i < n; ++i){
		if((a[i] | k) == k)
			res += b[i];
	}

	int cur = k;
	while(cur){
		int lsb = cur & -cur;
		cur ^= lsb; //remove lsb
		cur |= lsb - 1; // add whatever we can < lsb
		ll here = 0;
		for(int i = 0; i < n; ++i){
			if((a[i] | cur) == cur)
				here += b[i];
		}
		res = max(here, res);
		cur ^= lsb - 1;
	}

	cout << res << endl;

	return 0;
	
}

Measured memory_bytes: 1024
# https://atcoder.jp/contests/abc103/tasks/abc103_d
# D - Islands War

n, m = list(map(int, input().split()))
ab_list = []

for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))

# 区間が被っている場合は、一括で分けられる
# 区間が被っていない場合は、個別に分ける必要がある
# 区間が被っている個数を数えればよいはず

# 最小の区間を調べる
# bの1個前なら絶対切れる
ab_list = sorted(ab_list, key=lambda x: (x[1]))
# print(ab_list)
i = 0
count = 0

while i < len(ab_list):
    count += 1

    a, b = ab_list[i]
    diff_index = 1
    end_index = b

    debug_list = [(a, b)]

    if (i + diff_index) >= len(ab_list):
        break

    # 次の区間について
    while ab_list[i + diff_index][0] < end_index:
        # debug_list.append(ab_list[i + diff_index])

        diff_index += 1

        if (i + diff_index) >= len(ab_list):
            break

        # if ab_list[i + diff_index][1] < end_index:
        #     end_index = ab_list[i + diff_index][1]

    # print('==========')
    # print(debug_list)

    i = i + diff_index

print(count)


Measured memory_bytes: 19072
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define CHMAX(a,b) a = max(a,b)
#define CHMIN(a,b) a = min(a,b)
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define e1 first
#define e2 second
#define newline putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;
const VI dx = {1, 0, -1, 0};
const VI dy = {0, 1, 0, -1};

map<ll, ll> mp;

int main()
{
    int n, q;
    ll cnt = 0ll;
    cin>>n;
    REP(i,n) {
        ll a;
        cin>>a;
        cnt += a;
        mp[a]++;
    }
    VLL ans;
    cin>>q;
    REP(i,q) {
        ll b, c;
        cin>>b>>c;
        cnt = cnt - b * mp[b] + c * mp[b];
        ans.push_back(cnt);
        mp[c] += mp[b];
        mp.erase(b);
    }

    REPALL(i,ans)
        cout<<ans[i]<<endl;

    return 0;
}


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

int main(){
    long long N, x; cin >> N >> x;
    vector<int> a(N);
    for (int i=0; i<N; i++){
        cin >> a.at(i);
    }
    long long count=0;
    for (int i=0; i<N-1; i++){
        if(i==0 && a.at(i)>x){
            count+=a.at(i)-x;
            a.at(i)=x;
        } 
        if (a.at(i)+a.at(i+1)>x){
            count+=a.at(i)+a.at(i+1)-x;
            a.at(i+1)-=a.at(i)+a.at(i+1)-x;
        }
        
    }
    cout  << count << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<limits>
#include<string.h>
#include<vector>
#include<stack>
#include<queue>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int nn=n/2+1;
    int k=1000;
    int n0,n1,n2;
    for (int i = 1; i <= nn; i++)
    {
        n0=i;
        n1=n-i;
        n2=0;
        n2+=n0%10;
        n2+=n1%10;
        n0=n0/10;
        n1=n1/10;
        n2+=n0%10;
        n2+=n1%10;
        n0=n0/10;
        n1=n1/10;
        n2+=n0%10;
        n2+=n1%10;
        n0=n0/10;
        n1=n1/10;
        n2+=n0%10;
        n2+=n1%10;
        n0=n0/10;
        n1=n1/10;
        n2+=n0%10;
        n2+=n1%10;
        n0=n0/10;
        n1=n1/10;
        n2+=n0%10;
        n2+=n1%10;
        if(n2<k){
            k=n2;
        }


    }
    cout<<k<<endl;
    
    

    


    return 0;
}

Measured memory_bytes: 3600
# -*- coding: utf-8 -*-

import math

sht = [[0,0,0] for _ in range(3)]

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

for i in range(n):
    b=int(input())
    for j in range(3):
        if a[j].count(b)>0:
            sht[j][a[j].index(b)]=1

ans="No"

for i in range(3):
    if sht[i][0]==sht[i][1]==sht[i][2]==1:
        ans="Yes"
    elif sht[0][i]==sht[1][i]==sht[2][i]==1:
        ans="Yes"
if sht[0][0]==sht[1][1]==sht[2][2]==1:
    ans="Yes"
elif sht[0][2]==sht[1][1]==sht[2][0]==1:
    ans="Yes"

print(ans)


Measured memory_bytes: 3064
def main():
    K,S  = map(int,(input().split()))
    cnt = 0

    for X in range(K+1):
        for Y in range(K+1):
            Z = S - X - Y
            if 0 <= Z and Z<=K :
                cnt+=1
    
    print(cnt)






if __name__ == '__main__':
    main()


Measured memory_bytes: 40940
#include<iostream>
#include<algorithm>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

int const NMAX = 2e3;
int L[NMAX], N;

int main() {
  std::cin >> N;
  for(int i = 0; i < N; ++i) std::cin >> L[i];
  std::sort(L, L+N);
  int ans = 0;
  for(int i = 0; i < N-2; ++i) {
    for(int j = i+1, k= i+2; j < N-1; j++) {
      k = std::max(k, j+1);
      while(k < N && L[i]+L[j] > L[k]) ++k;
      ans += k - (j+1);
    }
  }
  fin(ans);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k,a[55],ans=0;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=n-k+1;i<=n;i++)
		ans+=a[i];
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256