akhauriyash/Code-Regression huggingface dataset:
unittest
{
	assert( [ "3200", "pink" ].parse.expand.solve == "pink" );
	assert( [ "3199", "pink" ].parse.expand.solve == "red" );
	assert( [ "4049", "red" ].parse.expand.solve == "red" );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto a = input.front.to!( long );
	input.popFront;
	auto s = input.front;
	return tuple( a, s );
}

auto solve( long a, string s )
{
	return ( 3200 <= a ) ? s : "red";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define pb push_back
#define log(x,b) (log(b)/log(x))
#define rep(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int mod=1e9;

int32_t main()
{
    int n,m;
    cin>>n>>m;
    int x[50],y[50],a[50],b[50],res[50]={0};
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=n;i++){
        int men=mod;
        for(int j=1;j<=m;j++){
            int dist=abs(x[i]-a[j])+abs(y[i]-b[j]);
            if(dist<men){
                men=dist;
                res[i]=j;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<res[i]<<endl;
    }


    return 0;
}


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

int main() {
  int l, r;
  cin >> l >> r;
  int com;
  int ans = 2019;
  if((r-l)>2019){
    cout << 0 << endl;
    return 0;
  }
  
  for(int i=l; i < r; i++){
    for(int j=i+1; j < r+1; j++){
      com = ((i%2019) * (j%2019)) % 2019;
      ans = min(ans, com);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

int check(string S){
    int ret = 0;
    rep(i,S.size()-1){
        if(S[i]=='R'&&S[i+1]=='R')ret++;
    }
    for(int i=S.size()-1;i>0;i--){
        if(S[i]=='L'&&S[i-1]=='L')ret++;
    }
    return ret;
}

int main(){
    int N;cin >> N;
    int K;cin >> K;
    string S;cin >> S;
    
    int cnt = 0;
    if(S[0]=='L'){
        rep(i,N-1){
            if(S[i]=='L'&&S[i+1]=='R')cnt++;
        }
    }else{
        rep(i,N-1){
            if(S[i]=='R'&&S[i+1]=='L')cnt++;
        }
    }
    int res = (K>=cnt)?N-1:check(S)+2*K;
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <cmath>
#include <sstream>
#include <istream>
#include <iomanip>
#include <typeinfo>
#include <stack>
#include <map>

using namespace std;
typedef long long int ll;

int main(){

    string s1, s2, s3;
    cin >> s1 >> s2 >> s3;

    cout << s1[0] << s2[1] << s3[2] << endl;

} 

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr int INFI = 1000000007;
const int mod = 1000000007;

int main(){
  int N;
  cin >> N;
  vector<vector<int>> A(N,vector<int> (N,0));
  for(int i=0; i<N; i++){
    int a;
    cin >> a;
    for(int j=0; j<a; j++){
      int x,y;
      cin >> x >> y;
      x--;
      if(y == 1){
        A[i][x] = 2;
      }
      if(y == 0){
        A[i][x] = 1;
      }
    }
  }
  int ans=0;
  for(int bit=0; bit<(1<<N); bit++){
    vector<int> h(N,0);
    bool can=true;
    for(int i=0; i<N; i++){
      if(bit & (1<<i)){
        h[i] = 2;
      }else{
        h[i] = 1;
      }
    }
    for(int i=0; i<N; i++){
      if(bit & (1<<i)){
        for(int j=0; j<N; j++){
          if(A[i][j] == 1){
            if(h[j]==1){
              h[j] = 1;
            }else{
              can = false;
            }
          }
          if(A[i][j] == 2){
            if(h[j]==2){
              h[j] = 2;
            }else{
              can = false;
            }
          }
        }
      }
    }
    if(can){
      ans = max(ans,__builtin_popcount(bit));
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int x;
	int tx;
	int sx = 0;
	scanf("%d", &x);
	tx = x;
	do {
		sx += tx % 10;
		tx /= 10;
	} while (tx != 0);
	
	if (x % sx == 0)
		puts("Yes");
	else
		puts("No");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define pb push_back
#define sc1(n) scanf("%lld",&n)
#define sc2(a,b) scanf("%lld%lld",&a,&b)
#define sc3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define MX 100000
using namespace std;

typedef long long int ll;
typedef unsigned long long ul;

ll arr[100005][3];
ll dp[100005][3];
ll n,k;

int main()
{
    sc1(n);
    for(ll i=1; i<=n; i++)
    {
        for(ll j=0;j<3;j++)
        {
            sc1(arr[i][j]);
        }
    }
    dp[1][0]=arr[1][0];
    dp[1][1]=arr[1][1];
    dp[1][2]=arr[1][2];
    for(ll i=2; i<=n; i++)
    {
        dp[i][0]=arr[i][0]+max(dp[i-1][1],dp[i-1][2]);
        dp[i][1]=arr[i][1]+max(dp[i-1][0],dp[i-1][2]);
        dp[i][2]=arr[i][2]+max(dp[i-1][0],dp[i-1][1]);
    }
    ll ans=max(dp[n][0],max(dp[n][1],dp[n][2]));
    printf("%lld\n",ans);
    return 0;
}


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

int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a + b == c + d) {
    cout << "Balanced" << endl;
  }
  else if (a + b > c + d) {
    cout << "Left" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
from itertools import product

n, m = [int(x) for x in input().split()]

a = [input() for x in range(n)]
b = [input() for x in range(m)]
ret = 'No'

for i, j in product(range(n - m + 1), range(n - m + 1)):
    if all([a[i + k][j:m + j] == x for k, x in enumerate(b)]):
        ret = 'Yes'
        break
print(ret)


Measured memory_bytes: 3064
#include <iostream>

int main(void){
  int n;
  std::cin >> n;
  int *c = new int[n];
  int *v = new int[n];
  int sum = 0;
  for(int i = 0; i < n; i++)
    std::cin >> c[i];
  for(int i = 0; i < n; i++)
    std::cin >> v[i];

  for(int i = 0; i < n; i++){
    if(c[i] > v[i]){
      sum += c[i] - v[i];
    }
  }
  std::cout << sum << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
const int inf = 1e18 + 7;
const int N = 1e6 + 7;
const int md = 1e9 + 7;
void sol() {
  int n;
  string s;
  cin >> n;
  cin >> s;
  int L = s.length();
  if(L <= n) {
    cout << s << "\n";
  }
  else {
    string res;
    for(int i=0; i<n; i++) {
      res += s[i];
    }
    res += "...";
    cout << res << '\n';
  }
}

int32_t main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T = 1;
  //cin >> T; 
  for(int t = 1; t <= T; t++) {
    //cout << "Case #" << t << ": ";
    sol();
  }
  return 0;
}


Measured memory_bytes: 3616
import heapq

def main():
    n = int(input())
    s = list(map(int, input().split()))

    # 中央値より左・右の管理
    l=[]
    r=[]
    heapq.heapify(l)
    heapq.heapify(r)
    lenl=0
    lenr=0
    # 中央値
    x = s[1]

    # b含めた答え
    ans = s[2]

    for i in range(n-1):
        q = list(map(int,input().split()))
        if q[0]==1:
            ans += q[2]
            if (lenl+lenr)%2==0:
                lenr+=1
                ans+=abs(x-q[1])
                if x<=q[1]:
                    heapq.heappush(r,q[1])
                else:
                    heapq.heappush(l,-q[1])
                    heapq.heappush(r,x)
                    x = -heapq.heappop(l)
            else:
                lenl+=1
                if x<q[1]:
                    heapq.heappush(l,-x)
                    heapq.heappush(r,q[1])
                    x=heapq.heappop(r)
                else:
                    heapq.heappush(l,-q[1])
                ans+=abs(x-q[1])
        if q[0]==2:
            print(x, ans)
if __name__=="__main__":
    main()

Measured memory_bytes: 89176
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int m, d;
	cin >> m >> d;
	int cnt = 0;
	for (int i = 1; i <= m; ++i) {
		for (int j = 22; j <= d; ++j) {
			if ((j % 10) * (j / 10) == i && j % 10 >= 2 && j / 10 >= 2)
				++cnt;
		}
	}
	cout << cnt << '\n';
	return 0;
}

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

int main(){

    string s;
    cin >> s;

    int n = s.length();
    string che[4] = {"dream", "dreamer", "erase", "eraser"};

    int flag = 0;
    for(int i = n - 1; i >= 0; i--){
        flag = 0;
        for(int j = 0; j < 4; j++){
            if(j == 0){
                if(i - 4 >= 0 && che[j] == s.substr(i - 4, 5)){
                    i -= 4;
                    flag = 1;
                    break;
                }
            }else if(j == 1){
                if(i - 6 >= 0 && che[j] == s.substr(i - 6, 7)){
                    i -= 6;
                    flag = 1;
                    break;
                }
            }else if(j == 2){
                if(i - 4 >= 0 && che[j] == s.substr(i - 4, 5)){
                    i -= 4;
                    flag = 1;
                    break;
                }
            }else{
                if(i - 4 >= 0 && che[j] == s.substr(i - 5, 6)){
                    i -= 5;
                    flag = 1;
                    break;
                }
            }
        }

        if(flag == 0){
            break;
        }
    }

    if(flag == 0){
        cout << "NO" << endl;
    }else{
        cout << "YES" << endl;
    }
}

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

long long count_inv(vector<int> &C, int l, int r){
  if(r - l == 1) return 0;
  int m = (l+r)/2;
  long long ret = count_inv(C,l,m) + count_inv(C,m,r);
  vector<int> L, R;
  for(int i = l; i < r; ++i){
    if(i < m) L.push_back(C[i]);
    else R.push_back(C[i]);
  }
  int N = L.size(), M = R.size(), cur = l, j = 0;
  for(int i = 0; i < N; ++i){
    while(j < M and R[j] < L[i]) C[cur++] = R[j++];
    ret += j;
    C[cur++] = L[i];
  }
  return ret;
}

int main(){
  long long N;
  cin >> N;
  vector<long long> A(N);
  for(int i = 0; i < N; ++i) cin >> A[i];
  vector<long long> B = A;
  sort(B.begin(), B.end());
  long long ok = -1, ng = N;
  while(ng - ok > 1){
    long long m = (ok + ng)/2, b = B[m];
    vector<int> C(N+1,0);
    for(int i = 0; i < N; ++i){
      if(A[i] >= b) C[i+1] = 1;
      else C[i+1] = -1;
    }
    for(int i = 1; i < N; ++i) C[i] += C[i-1];
    long long inv = count_inv(C,0,N+1);
    // cerr << "b = " << b << endl;
    // cerr << "C : "; for(int i = 0; i <= N; ++i) cerr << C[i] << " "; cerr << endl;
    // cerr << inv << endl;
    if(inv <= N*(N+1)/4) ok = m;
    else ng = m;
  }
  //cerr << ok << endl;
  cout << B[ok] << endl;
  return 0;
}


Measured memory_bytes: 2904
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define sz(v) (int)v.size()
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;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

class UnionFind {
    vector<int> parent;

    public:
        UnionFind(int size) {
            parent = vector<int>(size, -1);
        }

        int find(int x) {
            if (parent[x] < 0) {
                // parent itself
                return x;
            } else {
                return parent[x] = find(parent[x]);
            }
        }

        bool unite(int x, int y) {
            int rX, rY;
            if ((rX = find(x)) == (rY = find(y))) {
                // already united
                return false;
            }
            if (size(rX) < size(rY)) {
                int tmp = rX;
                rX = rY;
                rY = tmp;
            }
            parent[rX] += parent[rY];
            parent[rY] = rX;
            return true;
        }

        int size(int x) {
            return -parent[find(x)];
        }

        bool is_same(int x, int y) {
            return find(x) == find(y);
        }

        int component_count() {
            int c = 0;
            for (const int x : parent) {
                if (x < 0) {
                    c++;
                }
            }
            return c;
        }
};

void solve() {
    ll n, m;
    cin >> n >> m;
    vector<int> a(m);
    vector<int> b(m);
    REP(i, m) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    reverse(ALL(a));
    reverse(ALL(b));
    UnionFind uf(n);
    vector<ll> ans(m + 1);
    ans[0] = n * (n - 1) / 2;
    REP1(i, m) {
        bool b0 = uf.is_same(a[i - 1], b[i - 1]);
        ll b1 = uf.size(a[i - 1]);
        ll b2 = uf.size(b[i - 1]);
        uf.unite(a[i - 1], b[i - 1]);
        if (b0) ans[i] = ans[i - 1];
        else ans[i] = ans[i - 1] - (b1 * b2);
    }
    reverse(ALL(ans));
    REP1(i, m) cout << ans[i] << EOL;
}



Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(N) (N.begin(),N.end())
#define de cout << "debug" << endl;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, sum=0, A, B;
  cin >> N;
  string ans="Yes";
  vector<pair<int,int>> v;
  REP(i,N) {
    cin >> A >> B;
    v.pb({B,A});
  }
  sort ALL(v);
  REP(i,N) {
    sum+=v[i].second;
    if(sum>v[i].first) {
      ans="No";
      break;
    }
  }
  cout << ans << endl;
}

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

using namespace std;

void LCS(string s, string t)
{
	int n = s.length();
	int m = t.length();

	vector<vector<int>> dp(n + 1, vector<int>(m + 1));

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			if (i == 0 || j == 0)
			{
				dp[i][j] = 0;
			}
			else if (s[i - 1] == t[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

	int index = dp[n][m];
	vector<char> res(index);

	int i = n;
	int j = m;

	while (i > 0 && j > 0)
	{
		if (s[i - 1] == t[j - 1])
		{
			res[index - 1] = s[i - 1];
			i--;
			j--;
			index--;
		}
		else if (dp[i - 1][j] > dp[i][j - 1])
		{
			i--;
		}
		else
		{
			j--;
		}
	}

	for (char x : res)
	{
		cout << x;
	}
	cout << endl;
}

int main()
{
	string s, t;
	cin >> s >> t;

	LCS(s, t);
}

Measured memory_bytes: 35584
N,A,B,C = map(int,input().split())
l = [int(input()) for n in range(N)]
inf = 10 ** 18

def dfs(cur,a,b,c):
    if cur == N:
        if min(a,b,c) > 0:
            return abs(A-a)+abs(B-b)+abs(C-c)-30
        else:
            return inf

    res0 = dfs(cur+1,a,b,c)
    res1 = dfs(cur+1,a+l[cur],b,c)+10
    res2 = dfs(cur+1,a,b+l[cur],c)+10
    res3 = dfs(cur+1,a,b,c+l[cur])+10
    return min(res0,res1,res2,res3)
print(dfs(0,0,0,0))

Measured memory_bytes: 9152
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define dump(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
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 yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }

int main() {
    int a1, a2, a3; cin >> a1 >> a2 >> a3;
    int a12 = abs(a1 - a2);
    int a23 = abs(a2 - a3);
    int a13 = abs(a1 - a3);
    int ans = min({a12 + a23, a13 + a23, a23 + a13, a12 + a13});
    cout << ans << endl;
    return 0;
}


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

namespace AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            Console.WriteLine(
                Enumerable.Range(1, n).Aggregate((long)1, (a, b) => a * b));
        }
    }
}

Measured memory_bytes: 5808
#include <iostream>
#include <iomanip>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define sz(c) ((int)(c).size())

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
//const int MAX=;



int main(){
	int N;
	cin>>N;
	cout<<(N-2)*180<<endl;
}

Measured memory_bytes: 256
n=int(input())
t0=0
x0=0
y0=0
def num_abs(num):
    return abs(num)
ans=0
for i in range(n):
    t,x,y=map(int,input().split())
    numx=num_abs(x-x0)
    numy=num_abs(y-y0)
    numt=t-t0
    if numx+numy>numt or (numt-(numx+numy))%2==1:
        ans=1
        break
    t0=t
    x0=x
    y0=y
if ans==1:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 3064
M,K=map(int,input().split())
if M==1 and K==1:
    print(-1)
elif M==1 and K==0:
    print(0,0,1,1)
elif K<=(2**M-1):
    r = list(range(2**M))
    r = r[:K]+r[K+1:]
    ans = [K]+r+[K]+r[::-1]
    print(*ans)
else:
    print(-1)

Measured memory_bytes: 16240
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
  int N;
  cin >> N;
  map<string,int> mp;
  for (int i = 0; i < N; i++)
  {
    string S;
    cin >> S;
    mp[S]++;
    //cout << "plus:" << mp[S] << endl;
  }
  
  int M;
  cin >> M;
  for (int i = 0; i < M; i++)
  {
    string S;
    cin >> S;
    mp[S]--;
    //cout << "minus:" << mp[S] << endl;
  }
  
  int ans = 0;
  for (auto x:mp)
  {
    ans = max(ans, x.second);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	long long a,b,x;
	cin>>a>>b>>x;

	if(a%x==0)
		cout<<(b/x)-(a/x)+1<<endl;
	else
		cout<<(b/x)-(a/x+1)+1<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h> 
        using namespace std; 
        #define int long long
        # define pii pair<int,int>
        const int maxn=1e6+5;
        signed main() { 
            #ifndef ONLINE_JUDGE
            freopen("input.txt","r",stdin);
            freopen("output.txt","w",stdout);
            #endif
            ios::sync_with_stdio(0);
            cin.tie(0);
            int n;
            cin>>n;
            int arr[n];
            for(int i=0;i<n;i++)
            {
                cin>>arr[i];
                if(arr[i]==0)
                {
                    cout<<"0";
                    return 0;
                }
            }
            int prod=1;
            for(int i=0;i<n;i++)
            {
                if(arr[i]<=(int)1e18/prod)
                    prod*=arr[i];
                else
                    {
                        cout<<-1;
                        return 0;
                    }
            }
            cout<<prod;
        } 

Measured memory_bytes: 4372
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
using Pair = pair<ll,pair<int,int>>;
#define pq priority_queue<Pair, vector<Pair>, greater<Pair>> 
const ll mod=1000000007;
//const ll mod=998244353;
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる


//—————————————UnionFind木   UF uf(n);——————————————————————

struct UF {
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    UF(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void reset(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    bool unite(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool same(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

//—————————————————————————————————————————————————


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

  int n,m;
  cin>>n>>m;

  vector<vector<int>> p(m);
  rep(i,n){
    int k;
    cin>>k;
    rep(j,k){
      int l;
      cin>>l;
      l--;
      p[l].pb(i);
    }
  }

  UF uf(n);

  rep(i,m){
    int s=p[i].size();
    repo(j,s){
      uf.unite(p[i][j-1],p[i][j]);
    }
  }

  cout << (uf.size(0)==n?"YES":"NO") << endl;
}

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

int f(int x) {
  if (x%2 == 0) return x/2;
  else return 3*x + 1;
}

int main() {
  int s,ans;
  cin >> s;
  vector<int> a(1000005);
  vector<int> dp(1000005);
  a[1] = s;
  dp[s]++;

  for (int i = 2; i < 1000005; i++) {
    a[i] = f(a[i-1]);
    if (dp[a[i]] != 0) {
      ans = i;
      break;
    }
    else dp[a[i]]++;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 11172
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

const int MAX_N=2e6+10;
 
ll gcd(ll a, ll b){
    return b == 0LL ? a : gcd(b, a%b);
}
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
ll extgcd(ll a, ll b, ll &x, ll &y){
    ll g = a;
    x = 1LL;
    y = 0LL;
    if(b != 0) g = extgcd(b, a%b, y, x), y-= (a/b)*x;
    return g;
}
ll fact[MAX_N], ifact[MAX_N];
ll mod_inverse(int a){
    ll x, y;
    extgcd(a, MOD, x, y);
    return(MOD+x%MOD)%MOD;
}
 
void makeFact(){
    fact[0]=ifact[0] = 1LL;
    for(int i = 1; i < MAX_N; i++){
        fact[i] = fact[i-1]*i%MOD;
        ifact[i] = mod_inverse(fact[i]);
    }
}
 
ll c(int n, int r){
    if(n < 0 || r < 0 || r > n) return 0;
    if(r > n / 2) r = n-r;
    return fact[n]*ifact[n-r]%MOD*ifact[r]%MOD;
}



int main(){
    makeFact();
    
    ll x, y;
    cin >> x >> y;
    if((x+y)%3 != 0) {
        cout << 0 << endl;
        return 0;
    }
    ll k = (x+y)/3;
    x -= k;
    y -= k;
    if(x < 0 || y < 0) {
        cout << 0 << endl;
        return 0;
    }
    cout << c(x+y, x) << endl;
    return 0;
}

Measured memory_bytes: 31488
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) max_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)

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

    ll X, Y; cin >> X >> Y;
    int ans = 1;
    while(Y >= X*2) {
        X *= 2;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use {
   proconio::{fastout, input, marker::*},
   std::cmp::*,
   std::collections::*,
};

fn main() {
   input! {
      a: usize,
      b: usize,
      c: usize,
      d: usize,
      e: usize,
      f: usize,
   }

   let mut w = BTreeSet::new();
   for i in 0.. {
      if 100 * a * i > f {
         break;
      }
      for j in 0.. {
         if 100 * (a * i + b * j) > f {
            break;
         }
         w.insert(a * i + b * j);
      }
   }

   let mut s = BTreeSet::new();
   for i in 0.. {
      if c * i > f {
         break;
      }
      for j in 0.. {
         if c * i + d * j > f {
            break;
         }
         s.insert(c * i + d * j);
      }
   }

   let mut ans = (100 * a, 0);
   for &w in w.iter() {
      if w * 100 > f {
         break;
      }
      let lim = min(w * e, f - 100 * w);
      if let Some(&s) = s.range(..=lim).rev().next() {
         let tot = 100 * w + s;
         if ans.1 * tot < ans.0 * s {
            ans = (tot, s);
         }
      }
   }
   println!("{} {}", ans.0, ans.1);
}


Measured memory_bytes: 2120
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int uma,umi,vma,vmi;

int da(int u,int v){
    int l1,l2;
    l1 = max(uma-u,vma-v);
    l2 = max(u-umi,v-vmi);
    return min(l1,l2);
}

int db(int u,int v){
    int l1,l2;
    l1 = max(uma-u,v-vmi);
    l2 = max(u-umi,vma-v);
    return min(l1,l2);
}

int main(){
    int n,x,y,a,b;
    int u[100010],v[100010];
    
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> x >> y;
        u[i] = x+y;
        v[i] = x-y;
        if(i == 0){
            uma = u[i];
            umi = u[i];
            vma = v[i];
            vmi = v[i];
        }
        uma = max(uma,u[i]);
        umi = min(umi,u[i]);
        vma = max(vma,v[i]);
        vmi = min(vmi,v[i]);
    }
    
    a = 0;
    b = 0;
    for(int i=0;i<n;i++){
        a = max(a,da(u[i],v[i]));
        b = max(b,db(u[i],v[i]));
    }
    cout << min(a,b) << endl;
    
    return(0);
}


Measured memory_bytes: 3872
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
// #define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};
 
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; }
 
struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};
 

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Timer TM;

    ll n;
    string s,t;
    cin>>n>>s>>t;
    rep(i,n){
        cout<<s[i]<<t[i];
    }
    cout<<endl;
    return 0;
}

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

int main(){
    int count = 0;
    string W,word;
    
    cin >> W;

    while(1){
        cin >> word;

        if (word == "END_OF_TEXT"){
            break;
        }

        for (int  i = 0; i < word.size(); i++){
            if('A' <= word[i] && word[i] <= 'Z'){
                word[i] += 32; 
            }
        }

        if (word == W){
            count++;
        }
    }

    cout << count << endl;
    
    return 0;
}


Measured memory_bytes: 3136
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use std::cmp::*;
use std::collections::*;
use std::mem::*;

fn main() {
    let (r, w, e) = (std::io::stdin(), std::io::stdout(), std::io::stderr());
    let mut io = IO::new(r.lock(), w.lock(), e.lock());

    let n: usize = io.read();
    let mut a = io.readn::<i64>(n);

    let smlst = a.iter().min_by_key(|&x| x.abs()).unwrap().abs();
    let mcnt = a.iter().filter(|&x| *x < 0i64).count();
    let sm = a.iter().fold(0, |sum, x| sum + x.abs());
    io.writeln(sm - if mcnt % 2 == 1 { smlst * 2 } else { 0 });
}

static MOD: i64 = 1000000007;
// IO
use std::io::*;
struct IO<R: Read, W: Write, E: Write> {
    Read: R,
    Write: BufWriter<W>,
    Error: BufWriter<E>,
}
impl<R: Read, W: Write, E: Write> IO<R, W, E> {
    fn new(r: R, w: W, e: E) -> IO<R, W, E> {
        IO {
            Read: r,
            Write: BufWriter::new(w),
            Error: BufWriter::new(e),
        }
    }
    fn read<T>(&mut self) -> T
    where
        T: std::str::FromStr,
    {
        let next: String = self
            .Read
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();
        next.parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
    fn readn<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read::<T>()).collect::<Vec<_>>()
    }
    fn readmat<T: std::str::FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
        (0..n).map(|_| self.readn(m)).collect()
    }
    fn write<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
    }
    fn writeln<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
        self.Write.write(b"\n");
    }
    fn debug<S: std::fmt::Debug>(&mut self, val: S) {
        writeln!(self.Error, "(debug) {:?}", &val);
    }
    fn debug2<S: std::fmt::Debug, T: std::fmt::Debug>(&mut self, val1: S, val2: T) {
        writeln!(self.Error, "(debug2) {:?} -> {:?}", val1, val2);
    }
    fn debug3<S: std::fmt::Debug, T: std::fmt::Debug, U: std::fmt::Debug>(
        &mut self,
        val1: S,
        val2: T,
        val3: U,
    ) {
        writeln!(
            self.Error,
            "(debug3) {:?} -> {:?} -> {:?}",
            val1, val2, val3
        );
    }
}


Measured memory_bytes: 4352
// ######      ###      #######    #######    ##     #     #####        ###     ##### //
// #     #    #   #          #        #       # #    #    #     #      #   #     ###  //
// #     #   #     #        #         #       #  #   #   #       #    #     #    ###  //
// ######   #########      #          #       #   #  #   #           #########    #   //
// #     #  #       #     #           #       #    # #   #    ####   #       #    #   //
// #     #  #       #    #            #       #     ##   #    #  #   #       #        //
// ######   #       #   #######    #######    #      #    #####  #   #       #    #   //

// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define ain(a,n) for(ll i=0;i<(n);++i)	cin>>(a)[i];
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define loop(i,n) for(ll i=0;i<(n);++i)
#define FOR(i,a,b) for(ll i=(a);i<=(b);++i)
#define FORD(i,a,b) for(ll i=(a);i>=(b);--i)
#define cases ll T=0;cin>>T;while(T--)
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define END "\n"
#define pb push_back
#define go(c,itr) for(auto itr=(c).begin(); itr!=(c).end(); ++itr)
#define back(c,itr) for(auto itr=(c).rbegin(); itr!=(c).rend(); ++itr)
#define PI 3.14159265359
#define inf 9e18
#define MOD 1000000007
#define MODU 998244353
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MAXN 2005
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const ll N = 1e9;
ll binexp(ll a, ll b, ll m) {
	a %= m;
	ll res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return res;
}
void task(bool flag)
{
	if (flag)
		cout << "YES\n";
	else
		cout << "NO\n";
}
ll lcm(ll a, ll b)
{
	return ((1LL * a * b) / (__gcd(a, b)));
}

signed main() {

	fast
	// cases
	{
		ll x, n;
		cin >> x >> n;
		vl a(n);
		unordered_map<ll, ll> pres;
		loop(i, n)	cin >> a[i] , ++pres[a[i]];
		ll ans = 1, diff = inf;
		if (!a.empty())
		{
			FORD(i, x, 0)
			{
				if (pres[i] == 0)
				{
					if (abs(i - x) < diff)
					{
						ans = i;
						diff = abs(i - x);
					}
				}
			}
			ll i = x, ans2 = inf, diff2 = inf;
			while (1)
			{
				if (pres[i] == 0)
				{
					ans2 = i;
					diff2 = abs(i - x);
					break;
				}
				++i;
			}
			// cout << diff2 << " " << diff << END;
			if (diff2 < diff)
				ans = ans2;
		}
		else
			ans = x;
		cout << ans << END;
	}



	return 0;
}

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

int main() {
  int A,B,Num,Sum,dig5,dig4,dig3,dig2,dig1;
  cin >> A;
  cin >> B;
  Sum = 0;
  
  for (int i=A; i <= B; i++){
    if( i % 10 == i / 10000 && (i / 10) % 10 == (i / 1000) % 10)
      Sum += 1;
  }
  cout << Sum << endl;
}


Measured memory_bytes: 3632
import sys
sys.setrecursionlimit(20000)

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

sizes = [1] * (n + 1)
nums = [1] * (n + 1)
for i in range(1, (n + 1)):
  sizes[i] = 2 * sizes[i - 1] + 3
  nums[i] = 2 * nums[i - 1] + 1

def f(m, y):
  if m == 0:
    return 1
  if sizes[m] - 1 <= y:
    return nums[m]
  ret = 0
  y -= 1
  if y > 0:
    ret += f(m - 1, min(y, sizes[m - 1]))
    y -= sizes[m - 1]
  if y > 0:
    ret += 1
    y -= 1
  if y > 0:
    ret += f(m - 1, min(y, sizes[m - 1]))
  return ret

print(f(n, x))

Measured memory_bytes: 3064
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

alias P = Tuple!(size_t, "x", size_t, "y");

void main()
{
    auto hw = readln.split.to!(int[]);
    auto H = hw[0];
    auto W = hw[1];

    char[][] AS;
    AS.length = H;
    foreach (i; 0..H) {
        AS[i] = readln.chomp.to!(char[]);
    }

    int[][] BS;
    BS.length = H;
    foreach (ref bs; BS) {
        bs.length = W;
        bs[] = -1;
    }

    P[] ps;

    foreach (y, as; AS) {
        foreach (x, c; as) {
            if (c == '#') {
                ps ~= P(x, y);
            }
        }
    }

    int t;
    while (!ps.empty) {
        P[] nps;
        foreach (p; ps) {
            if (BS[p.y][p.x] != -1) continue;
            BS[p.y][p.x] = t;
            foreach (xy; [[1, 0], [0, 1], [-1, 0], [0, -1]]) {
                auto x = p.x + xy[0];
                auto y = p.y + xy[1];
                if (x < 0 || x >= W || y < 0 || y >= H) continue;
                nps ~= P(x, y);
            }
        }
        ps = nps;
        ++t;
    }

    auto r = int.min;
    foreach (bs; BS) foreach (b; bs) r = max(r, b);
    writeln(r);
}

Measured memory_bytes: 197500
<?php
  list($s) = explode(" ", trim(fgets(STDIN)));
  list($k) = explode(" ", trim(fgets(STDIN)));
  $n=strlen($s);

  $cnt1=0;
  for($i=0;$i<$n;$i++){
    if($s[$i]=='1'){
      $cnt1++;
    }else{
    break;
    }
  }

  if($k <= $cnt1){
    echo "1";
  }else{
    echo $s[$cnt1];
  }

Measured memory_bytes: 15980
#include <stdio.h>

int main(void)
{
	int N,M,A[100000],i,a=0,x=0;

	scanf("%d%d",&N,&M);
	for(i=0;i<M;i++){
		scanf("%d",&A[i]);
	}
	for(i=0;i<M;i++){
		a += A[i];
	}
	x = N-a;
	if(x >= 0) printf("%d\n",x);
	else printf("-1\n");
	return 0;
}



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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = (int)1e9;
const ll  inf = (ll)1e18;
const int mod = 1000000007;
const int MAX_N = 100010;



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

	int n;
	string s;
	cin >> n >> s;

	ll r = 0, g = 0, b = 0;

	rep(i, n) {
		if (s[i] == 'R') r++;
		else if (s[i] == 'G') g++;
		else b++;
	}

	ll ans = r * g * b;

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int k = 2 * j - i;
			if (k < n && s[i] != s[j] && s[j] != s[k] && s[k] != s[i]) {
				ans--;
			}
		}
	}

	out(ans);

	return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>

typedef long long ll;

int main() {

	ll N;

	scanf("%lld",&N);

	ll i;

	ll ans = 1ll;

	for (i = 1ll; i <= N; i++) {
		ans *= i;
		ans %= 1000000007;
	}
	printf("%lld\n",ans);

	return 0;
}

Measured memory_bytes: 128
#include<vector>
#include<complex>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

typedef vector<P> G;

struct C {
  P p; double r;
  //C(const P &p, double r) : p(p), r(r) { }
};
P projection(const L &l, const P &p) {
  double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);
  return l[0] + t*(l[0]-l[1]);
}

bool intersectSP(const L &s, const P &p) {
  return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // triangle inequality
}

bool inner(P &p, C &c){
	return norm(p-c.p)<(c.r)*(c.r)+EPS;
}
int main(){
	int m,n;
	double t1, t2, t3, t4;
	while(cin>>n,n){
		C wall[n];
		rep(i,n)cin>>t1>>t2>>t3,wall[i].p=P(t1,t2),wall[i].r=t3;
		cin>>m;
		rep(i,m){
			cin>>t1>>t2>>t3>>t4;
			P t=P(t1,t2),s=P(t3,t4),h,tmp;
			L l(t,s);
			bool danger=1;
			rep(j,n){
				h=projection(l,wall[j].p);
				if(intersectSP(l,h)){
					tmp=norm(t-wall[j].p)>norm(s-wall[j].p)?t:s;
					danger=danger&&(inner(tmp,wall[j])==inner(h,wall[j]));
				}else{
					danger=danger&&(inner(t,wall[j])==inner(s,wall[j]));
				}
			}
			cout<<(danger?"Danger":"Safe")<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 0
//inlclude before define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
#include<assert.h>
//#include<deque>
#include<iomanip>
#include<set>
#include<tuple>
#include<map>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef pair<int, int> P1;
typedef long long int ll;

//define
#define INF 1e9
#define NUM 1000000007
#define all(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);i++)
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))

int main() {
	int n, k;
	cin >> n >> k;
	ll ans = 0;
	ll a = n / k;
	if (k % 2 == 0) {
		ans = a * a * a;
		if (n%k >= k / 2) {
			a++;
		}
		ans += a * a * a;
	} else {
		ans = a * a * a;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
s = input()
t = input()
dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

hassame = False
for i, s_ in enumerate(s):
    if hassame or s_ == t[0]: dp[i+1][1]=1; hassame=True
hassame = False
for i, t_ in enumerate(t):
    if hassame or t_ == s[0]: dp[1][i+1]=1; hassame=True

lcs = 0
for i, s_ in enumerate(s):
    if i==0: continue
    for j, t_ in enumerate(t):
        if j==0: continue
        if s_!=t_:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        else:
            dp[i+1][j+1] = dp[i][j]+1
        lcs = max(lcs, dp[i+1][j+1])

ans = ''
i, j = len(s), len(t)
while 0<i and 0<j:
        if s[i-1] == t[j-1]: ans+=s[i-1]; i-=1; j-=1
        else:
            if dp[i-1][j] > dp[i][j-1]: i-=1
            else: j-=1
print(ans[::-1])


for i in range(len(s)):
    dp+=s[i]

Measured memory_bytes: 114268
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;


int f(map<int, int> d, int key) {
    return (d.find(key) != d.end() ? d[key] : INT_MIN);
}


int main() {
//    cout << setprecision(30);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n, k;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = 0;

    for (int i = 0; i <= min(n, k); i++) {
        for (int j = 0; i + j <= min(n, k); j++) {
            int ii = i, jj = j;
            set<int> just;
            int ind = 0, t = 0;
            while (ii--) {
                if (a[ind] < 0) just.insert(a[ind]);
                t += a[ind++];
            }
            ind = n - 1;
            while (jj--) {
                if (a[ind] < 0) just.insert(a[ind]);
                t += a[ind--];
            }

            auto it = just.begin();
            int rem = min((int) just.size(), k - i - j);
            while (rem--) {
                t -= *it;
                it++;
            }
            ans = max(ans, t);


        }
    }

    cout << ans;

}


Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int main()
{
    int n,a,b,t,ans=0;
    scanf("%d%d%d\n",&n,&a,&b);
    for(int i=0;i<n;i++)
    {
        scanf("%d\n",&t);
        if(b<=t||t<a)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
import java.util.*;
public class Main {
	//BFSで解く
	public static void main(String[] args) {
		int dx[] = {-1, 0, 1, 0};
		int dy[] = {0, -1, 0, 1};
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		char field[][] = new char[H][W];
		for(int i=0;i<H;i++) {
			String tmp = sc.next();
			for(int j=0;j<W;j++) {
				field[i][j]=tmp.charAt(j);
			}	
		}
		sc.close();
		
		Queue<Point> q = new ArrayDeque<Point>();
		q.add(new Point(0,0));
		
		int dist[][] = new int[H][W];
		for(int t[]:dist) Arrays.fill(t, Integer.MAX_VALUE);
		
		dist[0][0]=0;
		
		while(!q.isEmpty()) {
			Point now = q.poll();
			for(int i=0;i<4;i++) {
				int x = now.x;
				int y = now.y;
				int d = dist[x][y];
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(0<=nx&&nx<H&&0<=ny&&ny<W&&field[nx][ny]=='.') {
					if(dist[nx][ny]!=Integer.MAX_VALUE)continue;
					dist[nx][ny]=dist[x][y]+1;
					q.offer(new Point(nx,ny));
				}else {
					continue;
				}
			}
		}
		
		int ans = 0;
		
		int white = 0;
		for(int i=0;i<H;i++) {
			for(int j=0;j<W;j++) {
				if(field[i][j]=='.')white++;
			}
		}
		
		if(dist[H-1][W-1]==Integer.MAX_VALUE)ans = -1;
		else ans = white - (dist[H-1][W-1]+1);
		
		System.out.println(ans);
//		//debug:distの表示　
//		for(int i=0;i<H;i++) {
//			for(int j=0;j<W;j++) {
//				if(dist[i][j]==Integer.MAX_VALUE)System.out.print('#' + " ");
//				else System.out.print(dist[i][j]+" ");
//			}	
//			System.out.println();
//		}
	
	}
}

class Point{
	int x;
	int y;
	
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
	
}

Measured memory_bytes: 23764
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
#include<queue>
#include<functional>
#include<stack>
#include<iomanip>

using namespace std;

#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPL(i,a,n) for(ll i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define SORTVG(v) sort(v.begin(),v.end(),greater<>())
#define SORTV(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef tuple<int,int,bool> Tb;
typedef pair<int,int> Pii;
typedef vector<int> Vi;

template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}
template<class T> void YesNo(T& a) {if(a){cout << "Yes" << ENT;}else{cout << "No" << ENT;}}
template<class T> void YESNO(T& a) {if(a){cout << "YES" << ENT;}else{cout << "NO" << ENT;}}

vector<string> split(string s, string delim) {
    vector<string> res;
    int pos = 0;
    while(true) {
        int found = (int)s.find(delim, pos);
        if(found >= 0) {
            res.push_back(s.substr(pos, found - pos));
        }
        else {
            res.push_back(s.substr(pos));
            break;
        }
        pos = found + (int)delim.size();
    }
    return res;
}

int atcoder(){
    ll n;
    cin>>n;
    REP(i,0,3501){
        REP(j,0,3501){
            if(4*i*j-n*i-n*j>0 && (n*i*j)%(4*i*j-n*i-n*j)==0){
                cout<<i<<" "<<j<<" "<<(n*i*j)/(4*i*j-n*i-n*j)<<ENT;
                return 0;
            }
        }
    }
    return 0;
}


signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    atcoder();
    return 0;
}




Measured memory_bytes: 256