akhauriyash/Code-Regression huggingface dataset:
# @author 

import sys

class PIndependentSet:
    def solve(self):
        from collections import defaultdict
        MOD = 10 ** 9 + 7

        def dfs(s):
            st = [s]
            par = [-1] * n
            done = [0] * n
            o = []
            while st:
                u = st.pop()
                if done[u]: continue
                o.append(u)
                done[u] = 1
                for x in adj[u]:
                    par[x] = u
                    st.append(x)
            done = [0] * n
            o.reverse()
            for u in o:
                dp[u][0] = 1
                dp[u][1] = 1
                done[u] = 1
                for x in adj[u]:
                    if not done[x]:
                        continue
                    dp[u][0] = (dp[u][0] * dp[x][1]) % MOD
                    dp[u][1] = (dp[u][1] * (dp[x][0] + dp[x][1])) % MOD

        n = int(input())
        adj = defaultdict(list)

        for i in range(n - 1):
            x, y = [int(_) for _ in input().split()]
            x -= 1
            y -= 1
            adj[x].append(y)
            adj[y].append(x)

        dp = [[0, 0] for _ in range(n)]
        dfs(0)

        print((dp[0][0] + dp[0][1]) % MOD)

solver = PIndependentSet()
input = sys.stdin.readline

solver.solve()


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

int main() {
  int A, B;
  cin >> A >> B;
  
  if( A > 9 || B > 9){
     cout << -1 << endl;
  }
  if( A < 10 && B < 10){
     cout << A * B << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
    char a[101], b[101], c[101];
    int na,nb;
    for(int i = 0;i<101;++i){
        scanf("%c", &a[i]);
        if(a[i] == *" "){
            na = i-1;
            break;
        }
    }
    for(int i = 0;i<101;++i){
        scanf("%c", &b[i]);
        if(b[i] == *" "){
            nb = i-1;
            break;
        }
    }
    scanf("%s", c);
    if((a[na] == b[0]) && (b[nb] == c[0])) printf("YES\n");
    else printf("NO\n");
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define fr first
#define sc second
#define vec vector
#define ms multiset
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define int long long
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
const int inf = 1e9+7;
const int nmax = 500005;
const ll linf = LLONG_MAX;

int n , ca , cb;
vec < int > per , a , b;
int in;
int32_t main(){
    cin >> n;
    for(int i = 1; i <= n ; i++){
        cin >> in;
        a.pb(in);
    }
    for(int i = 1; i <= n ; i++){
        cin >> in;
        b.pb(in);
    }
    while(next_permutation(b.begin(),b.end()))cb++;
    while(next_permutation(a.begin(),a.end()))ca++;
    cout <<abs(ca - cb) << '\n';

}



Measured memory_bytes: 256
N,M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]

"""
なんかどこかのノードを軸にする（root扱いする）
a -> bまでの辺を1増やす = root -> a と、root -> b までの辺を1増やす。
全ての辺のコストが偶数なら、この足す処理が偶数回されてるはず。
間にどのノードが入るかとかあるけど、奇数回足される（奇数回出てくる）なら、ダメな気がする
少なくとも木ではあるのだから、あるaからあるbに行くときに必ずとおるrootがあるはずなので、これでいいんじゃなかろうか
"""

arr = [0] * N
for a,b in ab:
    arr[a-1] += 1
    arr[b-1] += 1

ans = "YES"
for n in arr:
    if n % 2 == 1:
        ans = "NO"

print(ans)

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

#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int a[3];
	for(int i = 0; i < 3; i++) 
		cin >> a[i];
	sort(a, a + 3);
	if(a[0] == a[1] && a[1] == 5) {
		if(a[2] == 7) {
			cout << "YES";
		} else {
			cout << "NO";
		}
	} else {
		cout << "NO";
	}

}


Measured memory_bytes: 256
#pragma comment (linker, "/STACK:256000000")

#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_NONSTDC_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <memory.h>
#include <sstream>
#include <cassert>
#include <ctime>
#include <complex>
#include <random>
#include <bitset>

using namespace std;

typedef unsigned int uint32;
typedef long long int64;
typedef unsigned long long uint64;
typedef long double ldouble;
typedef pair<int, int> pii;
typedef pair<int64, int64> pll;
typedef pair<uint64, uint64> puu;
typedef pair<pii, pii> piiii;

#define pb push_back
#define sq(x) ((x)*(x))
#define tmin(x,y,z) (min(min((x),(y)),(z)))
#define rand32() (((unsigned int)(rand()) << 16) | (unsigned int)(rand()))
#define rand64() (((unsigned int64)(rand32()) << 16) | (unsigned int64)(rand32()))
#define bit(mask, b) ((mask >> b) & 1)
#define biton(mask, bit) (mask | (((uint32)(1)) << bit))
#define bitoff(mask, bit) (mask & (~(((uint32)(1)) << bit)))
#define bitputon(mask, bit) (mask |= (((uint32)(1)) << bit))
#define bitputoff(mask, bit) (mask &= (~(((uint32)(1)) << bit)))
#define FAIL() (*((int*)(0)))++
#define INF ((int)(1e9) + 1337)
#define LINF ((int64)(1e18))
#define EPS 1e-13
#define PI (3.1415926535897932384626433832795)
#define y1 yy1
#define y0 yy0
#define j0 jj0
//#define MOD 1000000007LL
#define HMOD 1234567913LL
#define HMOD2 1000000007LL
#define HBASE 1000003
#define REV2 500000004


//#ifdef _MY_DEBUG
//    #define HMOD 1000000007
//    #define HBASE (1000003LL)
//#else
//    #define HMOD ((int64)(1e18) + 3LL)
//    #define HBASE (1000037LL)
//#endif
#define MAX 2000000000
mt19937 ggen;

int n;
int64 x;
int64 a[2010];
int64 dd[2010][2010];

inline int64 dist(int64 a, int64 b)
{
    if (b >= a)
        return b - a;
    else
        return b - a + n;
}

void solve()
{
    cin >> n >> x;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int64 ans = LINF;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            dd[i][dist(j, i)] = a[j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j < n; j++)
            dd[i][j] = min(dd[i][j], dd[i][j - 1]);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        int64 tans = x * i;
        for (int j = 0; j < n; j++)
        {
            tans += dd[j][i];
        }
        ans = min(ans, tans);
    }
    cout << ans;
}

#define TASK "substr"
int main()  
{
    //testgen(100000, 100000);// return 0;
    ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef _MY_DEBUG
    freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout);
#else
    //freopen(TASK ".in", "rt", stdin); freopen(TASK ".out", "wt", stdout);
#endif
    //stresstest(5, 7, 100); return 0;
    ggen = mt19937(13);

    //int start = clock();
    solve();

    return 0;
}

Measured memory_bytes: 31744
'''
.append(要素) リストに要素を追加
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
from functools import reduce
from operator import mul
from collections import Counter
import itertools
import fractions

t = [int(s) for s in stdin.readline().rstrip().split()]

if t[3] <= t[0]:
    print(t[3])
else:
    if t[3] <= t[0] + t[1]:
        print(t[0])
    else:
        if t[3] <= t[0] + t[1] + t[2]:
            print(t[0]-(t[3]-t[1]-t[0]))


Measured memory_bytes: 72680
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;
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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int A, B, C; cin >> A >> B >> C;
	int K; cin >> K;
	int cnt = 0;
	while (1) {
		if (B > A) {
			if (C > B)break;
			else {
				C *= 2;
				++cnt;
			}
		}
		else {
			B *= 2;
			++cnt;
		}
	}
	if (cnt <= K)cout << "Yes" << "\n";
	else cout << "No" << "\n";

	return 0;
}

Measured memory_bytes: 3636
def bs(l,key):
    left=0
    right=len(l)
    
    while left<right:
        mid=int((left+right)/2)

        if l[mid]==key:

            return  True
        elif key<l[mid]:
            right=mid
        else:
            left=mid+1
    
    return False
            


n1=int(input())
l1=list(map(int,input().split()))

n2=int(input())
l2=list(map(int,input().split()))

cnt=0

for x in l2:
    if bs(l1,x):
        cnt+=1

print(cnt)


Measured memory_bytes: 16712
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>

using namespace std;

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

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
    string s;
    cin >> s;
    int a, b;
    a  = atoi(s.substr(0, 2).c_str());
    b = atoi(s.substr(2, 2).c_str());

    if(a < 13 && b < 13 && a > 0 && b > 0) PRINT(AMBIGUOUS);
    else if(a < 13 && a > 0) PRINT(MMYY);
    else if(b < 13 && b > 0) PRINT(YYMM);
    else  PRINT(NA);
}


Measured memory_bytes: 256
var lines = [];
var readline = require('readline');

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (x) => {
    lines.push(x);
});

rl.on('close', () => {

    var A = Number(lines[0].split(" ")[0]);
    var B = Number(lines[0].split(" ")[1]);

    if (A <= 8 && B <= 8) {
        console.log("Yay!");
    }
    else{
        console.log(":(");
    }

})

Measured memory_bytes: 7756
//NAME-DEEPESH BHATT
//Institute-IIT Dhanbad
//MOTTO-THINK FIRST,CODE LATER

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1E9+7  ;
/*#define endl '\n'*/
#define pb push_back
#define mp make_pair

//Check for signed int overflow
// use __builtin_popcount(num) to calculate no.of setbits in num
//s.lower_bound() works in O(logn) whereas lower_bound(s.begin(),s.end(),x) works in O(n)

//Euclid's Algo
ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
//Extended Euclid's Algo
ll gcd_ex(ll a,ll b,ll&x,ll&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1;
    ll g=gcd_ex(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return g;
}
//Multiplicative Modulo Inv
ll multi_mod_inv(ll a,ll m){
    ll x,y;
    ll g=gcd_ex(a,m,x,y);
    if(g!=1){
        return -1;
    }
    x=(x%m+m)%m;
    return x;
}
//Mod division
ll mod_div(ll a,ll b,ll m){
    //(a/b)mod m?
    if(multi_mod_inv(b,m)!=-1){
        return (a%m*multi_mod_inv(b,m)%m)%m;
    }
    else{
        return -1;
    }
}
//lcm
ll lcm(ll a ,ll b)
{
    return a/gcd(a,b)*b;
}
//Binary Exponentiation
ll power(ll a,ll n){
    if (n == 0)
        return 1;
    ll p = power(a, n / 2);
    p = (p * p)%MOD;
    if (n % 2)
        return (p * a)%MOD;
    else
        return p%MOD;
}
//Euler Totient Function
ll phi[1000001]={0};
void euler_totient(ll n){
    for(ll i=0;i<=n;i++){
        phi[i]=i;
    }
    phi[1]=1;
    for(ll i=2;i<=n;i++){
        if(i==phi[i]){
            phi[i]=i-1;//For a prime number phi(p)=p-1
            for(ll j=2*i;j<=n;j+=i){
                phi[j]=phi[j]*(i-1)/i;
            }
        }
    }
}
/*void sieve(vector<ll>&is_prime){
    is_prime[0]=is_prime[1]=0;
    for(ll i=2;i*i<=1000000;i++){
        if(is_prime[i]){
            for(ll j=i*i;j<=1000000;j+=i){
                is_prime[j]=0;
            }
        }
    }
}*/
int32_t main()
{
    /*freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);*/
    ios_base::sync_with_stdio(false);    //for fast I/O operation
    cin.tie(nullptr);
    ll t=1;
    /*cin>>t;*/
    while(t--){
        ll n;
        cin>>n;
        /*vector<ll>is_prime(1000001,1);
        sieve(is_prime);*/
        vector<ll>ans(n,2);
        ans[1]=1;
        for(ll i=2;i*i<=n;i++){
            for(ll j=i*i;j<=n;j+=i){
                if(i==j/i)
                    ans[j]++;
                else{
                    ans[j]+=2;
                }
            }
        }
        ll sum=0;
        for(ll j=1;j<=n-1;j++){
            sum+=ans[j];
            /*cout<<ans[j]<<" ";*/
        }
        /*cout<<endl;*/
        cout<<sum<<endl;
    }
    return 0;
}

Measured memory_bytes: 11116
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define ms(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int MAXN=105;
const double EPS=1e-8;
const int INF=0x3f3f3f3f;
int c[MAXN*MAXN],e[MAXN][MAXN],H,W,n;

int main(){
	scanf("%d%d%d",&H,&W,&n);
	for(int i=1;i<=n;i++)	scanf("%d",&c[i]);
	ms(e,0);
	int k=1,now=0;
	for(int i=1;i<=H;i++){
		if(i%2==1){
			for(int j=1;j<=W;j++){
				e[i][j] = k;
				now++;
				if(now == c[k]){
					k++;
					now = 0;
				}
			}
		}else{
			for(int j=W;j>=1;j--){
				e[i][j] = k;
				now++;
				if(now == c[k]){
					k++;
					now = 0;
				}
			}
		}
	}
	for(int i=1;i<=H;i++){
		for(int j=1;j<=W;j++){
			if(j<W)	printf("%d ", e[i][j]);
			else printf("%d\n",e[i][j]);
		}
	}

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll N, M; cin >> N >> M;
    vvll v(1e5+1);
    rep(i, N) {
        ll a, b; cin >> a >> b;
        v[a].push_back(b);
    }

    priority_queue<ll> que;
    ll ans = 0;
    for (int i = 1; i <= M; i++) {
        for (ll x : v[i]) que.push(x);

        if (que.size()) ans += que.top(), que.pop();
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5632
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(c) (c).begin(), (c).end()
#define pb push_back
#define eb emplace_back
using namespace std;
const long long INF = 1LL<<60; // 仮想的な無限大の値;
using ll = long long;
using P  = pair<int, int>;
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
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 main()
{
    int N, M;
    cin >> N >> M;
    vi A(N);
    int sum = 0;
    rep(i, N) {
        cin >> A[i];
        sum += A[i];
    }
    sort(ALL(A));reverse(ALL(A));
    rep(i, M)
    {
        if(A[i]*4*M < sum)
        {
            cout << "No" << endl;return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

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

// @@ !! LIM(UnionFind)
// --> UnionFind
// ---- inserted library file UnionFind.cc

class UnionFind {
protected:
  int size;
  vector<int> _leader;
  vector<int> _rank;
  vector<int> _gsize;
  unordered_map<int, vector<int>> _groups;
  
public:
  UnionFind(int s);
  int leader(int i);
  int merge(int i, int j);
  int groupSize(int i);
  const unordered_map<int, vector<int>>& groups();
  const vector<int>& group(int i);
};

UnionFind::UnionFind(int s) {
  size = s;
  _leader = vector<int>(size);
  for (int i = 0; i < size; i++) { _leader.at(i) = i; }
  _rank = vector<int>(size, 1);
  _gsize = vector<int>(size, 1);
}

int UnionFind::leader(int i) {
  int cur = i;
  int nxt = _leader.at(cur);
  vector<int> seen;
  while (cur != nxt) {
    seen.push_back(cur);
    cur = nxt;
    nxt = _leader.at(cur);
  }
  for (auto j : seen) _leader.at(j) = cur;
  return cur;
}

int UnionFind::merge(int i0, int j0) {
  if (!_groups.empty()) {
    cerr << "merge() cannot be called after group() or groups()." << endl;
    exit(1);
  }
  int li = leader(i0);
  int lj = leader(j0);
  if (li == lj) return li;
  int ri = _rank.at(li);
  int rj = _rank.at(lj);
  int rep = li;
  int other = lj;
  if      (ri <  rj) swap(rep, other);
  else if (ri == rj) _rank.at(rep)++;
  _leader.at(other) = rep;
  _gsize.at(rep) += _gsize.at(other);
  return rep;
}

int UnionFind::groupSize(int i) {
  return _gsize.at(leader(i));
}

const unordered_map<int, vector<int>>& UnionFind::groups() {
  if (_groups.empty()) {
    for (int i = 0; i < size; i++) _groups[leader(i)].push_back(i);
  }
  return _groups;  
}

const vector<int>& UnionFind::group(int i) { return groups().at(leader(i)); }



// ---- end UnionFind.cc
// @@ !! LIM  -- end mark --

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N, Q; cin >> N >> Q;
  UnionFind uf(N);
  for (ll _q = 0; _q < Q; _q++) {
    ll t, u, v; cin >> t >> u >> v;
    if (t == 0) uf.merge(u, v);
    else {
      cout << (uf.leader(u) == uf.leader(v) ? 1 : 0) << "\n";
    }
  }


  return 0;
}



Measured memory_bytes: 5536
import java.io.*;

class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String line="";
while((line=br.readLine())!=null){
line=line.replaceAll("apple","?????????");
line=line.replaceAll("peach","apple");
line=line.replaceAll("?????????","peach");
System.out.println(line);
}
}
}

Measured memory_bytes: 16896
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main(int argc, char const* argv[])
{
  int i, input;
  vector<int> scores;

  for (i = 0; i < 5; i++) {
    cin >> input;
    if (input < 40) { input = 40; }
    scores.push_back(input);
  }

  cout << accumulate(scores.begin(), scores.end(), 0) / 5 << endl;

  return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
#define int long long
//template
void fin(int x,int y,int h){
  cout<<x<<" "<<y<<" "<<h<<endl;
  exit(0);
}
//main
signed main(){
  int N;cin>>N;
  std::vector<int> x(N),y(N),h(N);
  for(int i=0;i<N;i++)cin>>x[i]>>y[i]>>h[i];
  for(int cx=0;cx<=100;cx++){
    for(int cy=0;cy<=100;cy++){
      int H=-LINF,ok=1;
      for(int i=0;i<N;i++){
        if(h[i]==0)continue;
        if(H==-LINF)H=h[i]+abs(x[i]-cx)+abs(y[i]-cy);
        else if(H!=h[i]+abs(x[i]-cx)+abs(y[i]-cy))ok=0;
      }
      for(int i=0;i<N;i++){
        if(h[i])continue;
        if(H-abs(x[i]-cx)-abs(y[i]-cy)>0)ok=0;
      }
      if(ok&&H>0)fin(cx,cy,H);
    }
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include <algorithm>
#include<string.h>
#include <utility>
using namespace std;
int main(){
	int m;
	string in1,in2;
	int a[1000],b[1000],ans[1000];
	int f;
	int alen,blen,mlen;
	cin>>m;
	while(m--){
		for(int i=0;i<90;i++){
			a[i]=b[i]=ans[i]=0;
		}
		in1="";
		in2="";
		cin>>in1;
		cin>>in2;
		alen=in1.size();
		blen=in2.size();
		for(int i=0;i<alen;i++){
			a[alen-1-i]=in1[i]-'0';
		}
		for(int i=0;i<blen;i++){
			b[blen-1-i]=in2[i]-'0';
		}
		mlen=max(alen,blen);
		if(mlen>80){
			cout<<"overflow"<<endl;
			continue;
		}
		f=0;
		for(int i=0;i<mlen+1;i++){
			ans[i]=(a[i]+b[i]+f)%10;
			f=(a[i]+b[i]+f)/10;
		}
		if(ans[mlen]!=0){
			if(mlen>79){
				cout<<"overflow"<<endl;
				continue;
			}
			cout<<ans[mlen];
		}
		
		for(int i=0;i<mlen;i++){
			cout<<ans[mlen-1-i];
		}cout<<endl;
		
		
	}
	return 0;
}

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

using namespace std;

#define int long long

int n,m;
int dp1[111][111][3];
int dp2[111][111][111][3];

int dfs1(int A,int B,int d){
  if(n<A || n<B)return 0;
  if(B==n)return 1;
  if(dp1[A][B][d]!=-1)return dp1[A][B][d];
  
  int res=0;
  if(d==0){
    res += dfs1(A+1,B,0);
    if(A>B) res += dfs1(A,A,1);
  }
  if(d==1){
    res += dfs1(A,B+1,1);
    if(A<B) res += dfs1(B,B,0);
  }

  res %= 1000000;

  return dp1[A][B][d] = res;
  
}

int dfs2(int A,int B,int C,int d){
  if(n<A || n<B ||n<C)return 0;
  if(C==n)return 1;
  if(dp2[A][B][C][d]!=-1)return dp2[A][B][C][d];

  int res=0;
  if(d==0){
    if(A>B && A>C){
      int x = min(A-B,A-C)-1;
      res += dfs2(A,A,A,2) * x;
    }
    if(A>B){
      res += dfs2(A,A,C,1);
    }
    res += dfs2(A+1,B,C,0);
  }

  if(d==1){
    if(A<B) res += dfs2(B,B,C,0);
    res += dfs2(A,B+1,C,1);
    if(B>C) res += dfs2(A,B,B,2);
  }

  if(d==2){
    if(C>B && C>A){
      int x = min(C-B,C-A)-1;
      res += dfs2(C,C,C,0) * x;
    }
    if(C>B){
      res += dfs2(A,C,C,1);
    }
    res += dfs2(A,B,C+1,2);
  }

  res %= 1000000;

  return dp2[A][B][C][d] = res;
}

signed main(){
  cin>>n>>m;

  memset(dp1,-1,sizeof(dp1));
  memset(dp2,-1,sizeof(dp2));

  n++;

  if(m==1)cout<<dfs1(1,0,0)<<endl;
  else cout<<dfs2(1,0,0,0)<<endl;
}



Measured memory_bytes: 35452
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h> 
using namespace std;
 
typedef long long ll;
 
string int_to_string(int x) {
    stringstream ss;
	ss << x;
	string ni = ss.str();
	return ni;
}

int mod = 1e9 + 7;
ll power(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if(b & 1) {
			ans = (ans * a) % mod;
		}
		a = (a * a) % mod;
		b /= 2;
	}
	return ans;
}
 
int main() { 
	string s;
	cin >> s;
	int n = (int)s.size();
	//18171  81712114
	//18171
	vector<ll> m(2019);
	ll ans = 0;
	ll p = 1;
	ll x = 0;
	m[0] = 1;
	for (int i = n - 1; i >= 0; --i) {
		x += p * (s[i] - '0');
		ans += m[x % 2019];
		p = (p * 10) % 2019;
		m[x % 2019]++;
		x = x % 2019;
	}
	cout << ans;
}





	


Measured memory_bytes: 3700
#include <iostream>

using namespace std;

int main()
{
	int N, A, B;
  	cin >> N;
  
  	if (N == 1){
    	cout << "Hello World" << endl;
    } else if (N == 2){
    	cin >> A; cin >> B;
      	cout << A + B << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#define MN 6010

char c[MN], s[MN], t[MN], now[MN];
bool S[MN], T[MN], tmp[MN], used[MN];
int p[MN], n;
int qa[MN], ha = 0, ta = 0;
int qb[MN], hb = 0, tb = 0;

void Find(int l, int r)
{
	for(int i = 1; i <= n; i++) T[i] = 0, t[i] = '\0'; 
	for(int i = r; i >= l; i--)
	{
		if(c[i] == 'b') continue;
		used[i] = used[p[i]] = 1;
		int len = 0;
		for(int j = l; j <= r; j++) if(used[j]) now[++len] = c[j];
		int N = strlen(t + 1);
		int ok = N + 1;
		for(int j = 1; j <= N; j++) 
		{
			if(t[j] < now[j]) {ok = j; break;}
			if(t[j] > now[j]) {ok = 0; break;}
		}
		if(ok) 
		{
			for(int k = ok; k <= len; k++) t[k] = now[k], T[k] = 0;
			T[len] = 1;
		}
	}
}

int main()
{
	scanf("%d%s", &n, c + 1); n *= 2;
	int lst = 0, sum = 0, R = 0;
	for(int i = 1; i <= n; i++)
	{
		if(c[i] == 'a')
		{
			if(hb < tb) p[i] = qb[hb], p[qb[hb++]] = i;
			else qa[ta++] = i;
			sum--;
		}
		else
		{
			if(ha < ta) p[i] = qa[ha], p[qa[ha++]] = i;
			else qb[tb++] = i;
			sum++;
		}
		if(sum == 0)
		{
			if(c[i] == 'a')
			{
				Find(lst + 1, i); 
				int N = strlen(t + 1), len = strlen(s + 1), L = 0;
				memset(tmp, 0, sizeof(tmp)); tmp[N] = 1; 
				for(int j = 1; j <= len; j++)
				{
					if(S[j])
					{
						bool ok = N + 1;
						for(int k = 1; k <= N; k++)
						{
							if(t[k] < (L + k > j ? t[L + k - j] : s[L + k])) {ok = k; break;}
							if(t[k] > (L + k > j ? t[L + k - j] : s[L + k])) {ok = 0; break;}
							tmp[L + k] |= (L + k > j ? T[L + k - j] : S[L + k]);
						}
						if(ok)
						{
							for(int k = L + ok; k <= j + N; k++)
								tmp[k] = (k > j ? T[k - j] : S[k]);
							L = j;
						}
					}
				}
				for(int j = L + 1; j <= L + N; j++) s[j] = t[j - L];
				for(int j = L + N + 1; j <= n; j++) s[j] = '\0';
				memcpy(S, tmp, sizeof(tmp));
				R = i;
			}
			lst = i;
		}
	}
	int len = strlen(s + 1);
	for(int i = R + 1; i <= n; i++)
	{
		if(c[i] == 'a') s[++len] = 'a', s[++len] = 'b', i = p[i];
	}
	printf("%s", s + 1);
}

Measured memory_bytes: 384
H,W = (int(x) for x in input().split())
table = [[str(i) for i in input().split()] for m in range(H)]

a = '#'
for j in range(0,W+1):
    a += '#'
print(a)
for i in range(0,H):
    table[i].insert(0,'#')
    table[i].append('#')
    print("".join(table[i]))
print(a)


Measured memory_bytes: 3060
#include<iostream>

using namespace std;

//max
#define N 1000010

int main(){

  int num,num2,i,count=0;
  int n[N],q;
  int left,right,mid;
  //load number
  cin >>num;
  //load data
  for(i=0;i<num;i++){
    cin >>n[i];
  }

  //load number
  cin >>num2;
 

  

  //load data
  for(i=0;i<num2;i++){
    cin >>q;
    //do left <-0 right <- num
    left=0;
    right=num;
    //binary search and count
    while(left<right){
      mid=(left+right)/2;
      if(n[mid]==q){
	count++;
	break;
      }
      else if(n[mid]<q){
	left=mid+1;
      }
      else{
	right=mid;
      }
    }
  }
  //print count
  cout <<count<<endl;
  
  return 0;
 
}

Measured memory_bytes: 1224
#include<iostream>
#include<cmath>

using namespace std;

int main()
{
	long long K,A,B;

	cin >> K >> A >> B;

	if(K < A+1 || A+2 >= B)
	{
		cout << K+1 << endl;
		return 0;
	}

	long long x = (K - (A+1));
	long long y = x/2;

	long long ans = B + (B - A)*y + x%2;

	cout << ans << endl;

	return 0;
}

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

using namespace std;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;


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

    auto f = [&]{
        i64 a, b, c, d;
        cin >> a >> b >> c >> d;

        // 補充が間に合わない、最初に買えない
        if(b > d || a < b)
            return false;

        i64 gcd = __gcd(b, d);

        // 最初に落ちるまでシミュレーションした時の余り
        i64 mod = a % gcd;

        if(c < mod)
            return false;

        // c以下でmodが一定の中で最大になるような値
        i64 ma = ((c - mod) / gcd) * gcd + mod;

        i64 mi = ma - b + gcd;

        return mi >= 0;
    };

    for(int i = 0; i < n; ++i){
        cout << (f() ? "Yes" : "No") << endl;
    }
}


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

#pragma warning(disable:4996)
using namespace std;
using ld = long double;
ld eps=1e-9;

int answer=-1e9;
vector<int> dfs(const vector<vector<int>>&edges, 
	const vector<int>&scores,
	const int now, const int from) {
	vector<int>ans(3,-1e9);
	ans[0]=scores[now];
	for (auto e : edges[now]) {
		if (e != from) {
			auto v = dfs(edges,scores, e, now);
			vector<int>nextans(ans);
			for (int l = 0; l < 3; ++l) {
				for (int r = 0; r < 3; ++r) {
					if (l + r <= 2) {
						if (r == 0) {
							nextans[l + r] = max(nextans[l + r],
								ans[l] + v[r] - 2);
							if (l + r + 1 <= 2)nextans[l + r + 1] = max(nextans[l + r + 1],
								ans[l] + v[r] - 1);
						}
						else if (r == 1) {
							nextans[l + r] = max(nextans[l + r],
								ans[l] + v[r] - 1);

						}
						else {
							nextans[l + r] = max(nextans[l + r],
								ans[l] + v[r] - 2);
						}
					}
					
				}
			}
			ans=nextans;
		}
	}
	for (auto a : ans) {
		answer=max(answer,a);
	}
	return ans;
}
int main() {
	int N;cin>>N;
	vector<vector<int>>edges(N);
	vector<int>scores(N);
	for (int i = 0; i < N; ++i) {
		int a;cin>>a;
		scores[i]=a;

	}
	for (int i = 0; i < N - 1; ++i) {
		int a,b;cin>>a>>b;a--;b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	auto v=dfs(edges,scores,0,-1);
	cout<<answer<<endl;
	return 0;
}


Measured memory_bytes: 27440
from collections import defaultdict as dd
from collections import Counter
import math
N = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return Counter(fct)

fact_list = [dd(int) for _ in range(N)]
dic = dd(int)
for i,val in enumerate(a):
    tmp = factorize(val)
    for k,v in tmp.items():
        dic[k] = max(dic[k], v)

lcm = 1
for k,v in dic.items():
    lcm = (lcm*pow(k,v,MOD))%MOD
res = 0
for val in a:
    res = (res+pow(val, MOD-2, MOD))%MOD
res = (res*lcm)%MOD
print(res)


Measured memory_bytes: 7736
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
using namespace std;

void solve(){
  int x, a, b; cin >> x >> a >> b;
  if(b <= a) cout << "delicious\n";
  else if((b - a) <= x) cout << "safe\n";
  else cout << "dangerous\n";
  return;
}

int main(){
  solve();
  return 0;
}


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

int main() {
  ll a,b,v,w,t;
  cin >> a >> v;
  cin >> b >> w;
  cin >> t;
  if(a<b){
    if(a+v*t>=b+w*t)
    cout << "YES" << endl;
    else
    cout << "NO" << endl;
  }
  else{
    if(a-v*t<=b-w*t)
    cout << "YES" << endl;
    else
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
bool d[51][51];
int a,b,s,_x,_y,dx[8]={0,-1,-1,-1,0,1,1,1},dy[8]={1,1,0,-1,-1,-1,0,1};
#define r(z,x) for(int z=0;z<x;z++)
void bfs(int x,int y){
	if(0>x||x>=b||0>y||y>=a)return;
	d[x][y]=0;
	r(i,8)if(d[_x=x+dx[i]][_y=y+dy[i]])bfs(_x,_y);
}
int main(){
	while(cin>>a>>b,a||b){
		s=0;
		r(i,b)r(j,a)cin>>d[i][j];
		r(i,b)r(j,a)if(d[i][j])bfs(i,j),s++;
		cout<<s<<endl;
	}
}

Measured memory_bytes: 3136
# -*- coding: utf-8 -*-
N = int(input())

#
lim = 10 ** 5
candidates = [True for _ in range(lim)]
candidates[0], candidates[1] = False, False
for i in range(lim):
    if candidates[i]:
        for j in range(i*2, lim, i):
            candidates[j] = False

#
nums = []
for i in range(lim):
    if candidates[i]:
        if i % 5 == 1:
            nums.append(i)

print(*nums[:N])

Measured memory_bytes: 44784
import std.algorithm;
import std.array;
import std.bigint;
import std.conv;
import std.stdio;
import std.string;

void main(){
    foreach(i; 0..readln.chomp.to!int){
        string a = readln.chomp, b = readln.chomp;
        if(a.length > 80 || b.length > 80)
            writeln("overflow");
        else{
            BigInt d = BigInt(a) + BigInt(b);
            if(d.to!string.length > 80)
                writeln("overflow");
            else
                writeln(d);
        }
    }
}

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

using namespace std;

#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll, V, greater<ll>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;

ll N, Q;

//通常
struct UnionFind {
    V par, rank;
    UnionFind(int size) { init(size); }
    void init(int size) {
        REP(i, size) {
            par.push_back(i);
            rank.push_back(0);
        }
    }
    int root(int x) {
        if(par[x] == x)
            return x;
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(rank[x] < rank[y]) {
            swap(x, y);
        } else {
            if(rank[x] == rank[y]) rank[x]++;
        }
        par[y] = x;
    }
    bool same(int x, int y) { return root(x) == root(y); }
};

signed main() {
    cin >> N >> Q;
    auto uf = UnionFind(N);
    REP(i, Q) {
        LCIN(c, x, y);
        if(c) {
            cout << (uf.same(x, y) ? 1 : 0) << "\n";
        } else {
            uf.unite(x, y);
        }
    }
    return 0;
}



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

#define REP(i, n) for(int i = 0; i < (int) (n); i++)
#define ALL(v) (v).begin(), (v).end()
#define INF 1e9

using namespace std;

struct v{
  int id, cost;
  bool operator<(const v &x)const{
    if(cost < x.cost) return true;
    else return false;
  }
};

int main(){
  int w, h;
  while(cin >> w >> h and w + h){
    vector<vector<int> > Edges(w * h);
    vector<int> costs(w * h);
    priority_queue<v> vertices;
    int clif;
    REP(i, h){
      if(i != 0){
        REP(j, w){
          cin >> clif;
          if(!clif) { Edges[w*(i-1)+j].push_back(w*i+j); Edges[w*i+j].push_back(w*(i-1)+j); }
        }
      }
      REP(j, w-1){
        cin >> clif;
        if(!clif) { Edges[w*i+j].push_back(w*i+j+1); Edges[w*i+j+1].push_back(w*i+j); }
      }
    }
    REP(i, h) REP(j, w) costs[i*w+j] = INF;
    vertices.push({0, 1});
    costs[0] = 1;
    while(!vertices.empty()){
      v target = vertices.top();
      vertices.pop();
      REP(i, Edges[target.id].size()){
        if(costs[Edges[target.id][i]] > costs[target.id] + 1){
          costs[Edges[target.id][i]] = costs[target.id] + 1;
          vertices.push({Edges[target.id][i], costs[target.id] + 1});
        }
      }
    }
    cout << (costs[w*h-1] == INF ? 0 : costs[w*h-1]) << endl;
  }
  return 0;
}

Measured memory_bytes: 3204
# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;

# define FO_OPEN 0
# define RG register
# define ST static

int n, q;
ll add[M], st[M], s[M], cur;
int stn=0;

int main() {
	FO_OPEN ? freopen(".in", "r", stdin), freopen(".out", "w", stdout) : 0;
	scanf("%d%d", &n, &q);
	st[++stn] = n;
	for (int i=1; i<=q; ++i) {
		scanf("%lld", &cur);
		while(stn && st[stn] >= cur) --stn;
		st[++stn] = cur; 
	}
	
	add[stn] = 1;
	for (int i=stn; i; --i) {
		if(!add[i]) continue;
		ll x = st[i];
		while(1) {
			int pos = upper_bound(st+1, st+i, x) - st - 1;
			if(!pos) break;
			add[pos] += add[i] * (x/st[pos]);
			x = x % st[pos];
		}
		s[x] += add[i];
	}
	
	for (int i=n; i; --i) 
		s[i] += s[i+1];
	for (int i=1; i<=n; ++i)
		printf("%lld\n", s[i]);
	return 0;
}





Measured memory_bytes: 10624
import scala.io.StdIn

object Main extends App {
  val s: String = StdIn.readLine()
  val n = s.length

  val a: Boolean = s == s.reverse
  val b: Boolean = s.slice(0, (n-1)/2) == s.slice(0, (n-1)/2).reverse
  val c: Boolean = s.slice((n+3)/2-1, n) ==  s.slice((n+3)/2-1, n).reverse
  println(if(a&&b&&c) "Yes" else "No")
}

Measured memory_bytes: 27180
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int n , a[N] , b[N];
multiset< pair<int , int> > L , R;

int main() {
    scanf("%d" , &n);
    for (int i = 0 ; i < n ; ++ i) {
        scanf("%d%d" , a + i , b + i);
    }
    long long res = 0;
    for (int dir = 0 ; dir < 2 ; ++ dir) {
        L.clear();
        R.clear();
        for (int i = 0 ; i < n ; ++ i) {
            R.insert(make_pair(a[i] , b[i]));
            L.insert(make_pair(b[i] , a[i]));
        }

        int cur = 0, l , r;
        long long sum = 0;

        while (!L.empty()) {
            auto it = *L.begin();
            l = it.second , r = it.first;
            //cout << l << ' ' << r << endl;
            L.erase(L.find(make_pair(r , l)));
            R.erase(R.find(make_pair(l , r)));

            if (cur < l) {
                sum += l - cur;
                cur = l;
            } else if (cur > r) {
                sum += cur - r;
                cur = r;
            }

            if (L.empty()) break;
            it = *R.rbegin();
            l = it.first , r = it.second;
            //cout << l << ' ' << r << endl;
            L.erase(L.find(make_pair(r , l)));
            R.erase(R.find(make_pair(l , r)));

            if (cur < l) {
                sum += l - cur;
                cur = l;
            } else if (cur > r) {
                sum += cur - r;
                cur = r;
            }
        }
        //cout << sum + abs(cur) << endl;
        res = max(res, sum + abs(cur));
        for (int i = 0 ; i < n ; ++ i) {
            a[i] = -a[i];
            b[i] = -b[i];
            swap(a[i] , b[i]);
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 12416
s = sorted(list(input()))
t = sorted(list(input()))[::-1]
            
for S, T in zip(s, t):
    if S < T:
        print('Yes')
        exit()
    elif S > T:
        print('No')
        exit()
    else:
        continue

print('Yes' if len(s) < len(t) else 'No')

Measured memory_bytes: 9040
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

struct UnionFind {
  vector<int> d;
  UnionFind(int n) : d(n, -1) {}
  int root(int x) {
    if(d[x] < 0) return x;
    return d[x] = root(d[x]);
  }
  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if(x == y) return false;
    if(d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return root(x) == root(y); }
  int size(int x) { return -d[root(x)]; }
};

int main() {
  int n, m;
  cin >> n >> m;
  vi a(m), b(m);
  rep(i, m) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }
  int ans = 0;
  rep(i, m) {
    UnionFind uf(n);
    rep(j, m) if(j != i) uf.unite(a[j], b[j]);
    if(!uf.same(a[i], b[i])) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
#define mod 1000000007
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define pr std::pair<int,int>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
int f[2][72][72],t;
//f[i][j][k]
//i:上次选的lenb；j:r段数；k:∑b
char S[72];
int to[72],pre[72],Sr[72],fact[1010],ifact[1010];
int C(int n,int m){return 1ll*fact[n]*ifact[n-m]%mod*ifact[m]%mod;}
int Ins(int n,int m){
	if(!m)return 1;
	if(!n)return 0;
	return C(n+m-1,n-1);
}
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	int n=gi(),K=gi(),m=0;
	scanf("%s",S+1);
	for(int i=1;i<=K;++i)Sr[i]=Sr[i-1]+(S[i]=='r');
	for(int i=1,j=1;i<=K;++i)
		if(S[i]=='r'){
			while(j<=K&&(j<=i||S[j]=='r'))++j;
			to[++m]=K-j;if(j>K)to[m]=-1e9;++j;
			pre[m]=Sr[std::min(j,K)-1];
		}
	fact[0]=1;for(int i=1;i<=1000;++i)fact[i]=1ll*fact[i-1]*i%mod;
	ifact[1000]=pow(fact[1000],mod-2);for(int i=1000;i;--i)ifact[i-1]=1ll*ifact[i]*i%mod;
	int ans=1;
	for(int d=1;d<=m&&d<=n;++d){
		for(int o0=0;o0<=m;++o0){
			memset(f,0,sizeof f);
			f[t][o0][0]=ifact[o0];
			for(int i=1;i<=n;++i){
				memset(f[!t],0,sizeof f[!t]);
				for(int j=0;j<=d;++j)
					for(int k=0;k<=n;++k)
						if(f[t][j][k])
							for(int o=0,nj=j,nk=k;nj<=d&&nk<=n;++o,++nj,nk+=i){
								if(o&&to[d-nj+1]-std::max(0,d-pre[d-nj+1])-(nj-1-o0)<nk-nj+o0)break;
								inc(f[!t][nj][nk],1ll*ifact[o]%mod*f[t][j][k]%mod);
							}
				t^=1;
			}
			for(int k=0;k<=n;++k)
				if(f[t][d][k]){
					int res=0;
					for(int p=d-1;p<=n-k*2+d-o0*2;++p)
						inc(res,1ll*f[t][d][k]*Ins(d+1,p-d+1)%mod*Ins(k*2+d,n-k*2+d-p-o0*2)%mod);
					inc(ans,res=1ll*fact[d]*res%mod);
					//fprintf(stderr,"%d %d %d %d %d\n",o0,d,k,f[t][d][k],res);
				}
		}
	}
	printf("%d\n",ans);
	return 0;
}


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

using namespace std;

int main(void) {
  long long q, h, s, d, n;
  cin >> q >> h >> s >> d >> n;
  n *= 4;

  bool dflag = (d < 8 * q) && (d < 4 * h) && (d < 2 * s);
  bool sflag = (s < 4 * q) && (s < 2 * h);
  bool hflag = h < 2 * q;

  int tmp = 0;
  if(dflag) {
    tmp += 4;
  }
  if(sflag) {
    tmp += 2;
  }
  if(hflag) {
    tmp += 1;
  }

  long long ans = 0;
  switch(tmp) {
  case 0:
    ans += n * q;
    break;
  case 1:
    ans += n / 2 * h;
    n = n % 2;
    ans += n * q;
    break;
  case 2:
    ans += n / 4 * s;
    n = n % 4;
    ans += n * q;
    break;
  case 3:
    ans += n / 4 * s;
    n = n % 4;
    ans += n / 2 * h;
    n = n % 2;
    ans += n * q;
    break;
  case 4:
    ans += n / 8 * d;
    n = n % 8;
    ans += n * q;
    break;
  case 5:
    ans += n / 8 * d;
    n = n % 8;
    ans += n / 2 * h;
    n = n % 2;
    ans += n * q;
    break;
  case 6:
    ans += n / 8 * d;
    n = n % 8;
    ans += n / 4 * s;
    n = n % 4;
    ans += n * q;
    break;
  case 7:
    ans += n / 8 * d;
    n = n % 8;
    ans += n / 4 * s;
    n = n % 4;
    ans += n / 2 * h;
    n = n % 2;
    ans += n * q;
    break;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
const stdin = require('fs').readFileSync('/dev/stdin', 'utf8')

const [n, m] = stdin
  .split('\n')[0]
  .split(' ')
  .map(Number)

const [, ..._ks] = stdin.trim().split('\n')
let ks = _ks.map(e => e.split(' ').map(Number))
const p = ks.pop()

const ans = _ => {
  const bulbs = Array(m).fill(null)

  ks.map(([k, ..._s], i) => {
    const s = _s.map(e => e - 1)

    let switches = Array(n).fill(0)

    s.forEach(v => {
      switches[v] = 1
    })

    bulbs[i] = switches
  })

  let sum = 0
  for (let i = 0; i < 1 << n; i++) {
    let iStr = i.toString(2)
    let filler = ''
    for (let j = 0; j < n - iStr.length; j++) {
      filler += '0'
    }
    const iArr = (filler + iStr).split('').map(Number)

    const bulbSwitchOnCounts = bulbs.map(b=>{
      return b.filter((e,i)=>{
        return iArr[i] & e
      }).length
    })

    const onBulbs = bulbSwitchOnCounts.filter((e,i)=>{
      return e%2 === p[i]
    }).length

    sum += onBulbs === m ? 1 : 0
  }

  console.log(sum)
}

ans()


Measured memory_bytes: 10516
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define CK(N, A, B) (A <= N && N < B)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = (b - 1); a <= i; i--)
#define F first
#define S second
#define ll long long

const int INF = 1e9;
const long long LLINF = 1e18;

using namespace std;

int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int dy8[] = {0,1,1,1,0,-1,-1,-1};
int dx8[] = {1,1,0,-1,-1,-1,0,1};

/*==================================================*/
/*variable*/

/*==================================================*/
/*function*/


/*==================================================*/

int main() {
    string S;
    cin>>S;

    set<char> xv, yv;

    REP(i,0,S.size()){
        if(S[i] == 'N' || S[i] == 'S'){
            yv.insert(S[i]);
        }else{
            xv.insert(S[i]);
        }
    }

    if(xv.size() % 2 == 0 && yv.size() % 2 == 0){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

    return 0;
}


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

int formula(const string& s, int& p)
{
  if (s[p] == '(') {
    ++p;
    int lhs = formula(s, p);
    char op = s[p++];
    int rhs = formula(s, p);
    ++p;
    if (op == '*') {
      if (lhs == 0 || rhs == 0)
	return 0;
      else if (lhs == 2 && rhs == 2)
	return 2;
      else
	return 1;
    } else {
      if (lhs == 2 || rhs == 2)
	return 2;
      else if (lhs == 0 && rhs == 0)
	return 0;
      else
	return 1;
    }
  } else if (s[p] == '-') {
    ++p;
    return 2 - formula(s, p);
  } else {
    return s[p++] - '0';
  }
}

int main()
{
  string s;
  while (cin >> s) {
    if (s == ".")
      break;

    int ans = 0;
    for (int P = 0; P <= 2; ++P) {
      string exp1 = s;
      while (exp1.find_first_of("P") != string::npos)
	exp1[exp1.find_first_of("P")] = ('0' + P);
      for (int Q = 0; Q <= 2; ++Q) {
	string exp2 = exp1;
	while (exp2.find_first_of("Q") != string::npos)
	  exp2[exp2.find_first_of("Q")] = ('0' + Q);
	for (int R = 0; R <= 2; ++R) {
	  string exp3 = exp2;
	  while (exp3.find_first_of("R") != string::npos)
	    exp3[exp3.find_first_of("R")] = ('0' + R);
	  int p = 0;
	  if (formula(exp3, p) == 2)
	    ++ans;
	}
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 0
// Author: πα

#include <bits/stdc++.h>
using namespace std;

#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define long int64_t

const int N = 1e5 + 5, M = 105;
bool dp[N];
int a[M];

int main()
{
    FastIO;
    int n, i, j, k;
    cin >> n >> k;
    for(i = 0; i < n; ++i)
        cin >> a[i];
    for(i = 0; i <= k; ++i)
        for(j = 0; j < n; ++j)
            if(i >= a[j])
                dp[i] |= !dp[i-a[j]];
    cout << (dp[k] ? "First" : "Second");
    return 0;
}


Measured memory_bytes: 384
D=int(input())
clist=list(map(int,input().split()))
smat=[[int(x) for x in input().split()] for _ in range(D)]
#print(clist)
#print(smat)
all_maxc=max(clist)

index_set=set(range(26))
for d in range(D):
  max_index=-1
  max_sd=-1
  for i in index_set:
    if max_sd<smat[d][i]:
      max_index=i
      max_sd=smat[d][i]
      
  max_index2=-1
  max_sd2=-1
  for i in range(26):
    if max_sd2<smat[d][i]:
      max_index2=i
      max_sd2=smat[d][i]
      
  if max_index==max_index2:
    print(max_index+1)
    index_set.remove(max_index)
  else:
    if max_sd2>4*max_sd:
      print(max_index2+1)
    else:
      print(max_index+1)
      index_set.remove(max_index)      
      
  if not index_set:
    index_set=set(range(26))
  else:
    max_c=0
    for i in index_set:
      max_c=max(max_c,clist[i])
    if max_c<10*(365-d)*all_maxc//365:
      index_set=set(range(26))

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





int main() {

	string s;
	cin >> s;

	if (s == "AAA" || s == "BBB") cout << "No" << endl;
	else cout << "Yes"<<endl;


}

Measured memory_bytes: 256