akhauriyash/Code-Regression huggingface dataset:
/*

A try towards peace

*/

#include <bits/stdc++.h>
using namespace std;
#define yo long long int
#define lo mp::cpp_int
#define pb push_back
#define pob pop_back
#define mp make_pair
#define endl "\n"
#define ce(x) cout << x <<"\n"
#define fill(s,v) memset(s,v,sizeof(s))
#define speed  { ios_base::sync_with_stdio(false); cin.tie(0); }
#define for2(i,a,b) for(yo i=a;i<b;i++)
#define for3(i,a,b) for(yo i=a;i<=b;i++)
#define for1(a,b) for(yo i=a;i<b;i++)
#define deb(x) cout<<#x<<" "<<x<<endl; 
#define INFINITE 1000000009
#define ull unsigned long long int
#define take(a,n) for(yo pp=0;pp<n;pp++) { cin>>a[pp]; }
#define take2(a,n) for(yo p=0;p<n;p++) { yo temp;cin>>temp;a.pb(temp); }
#define show(a,n) for(yo p=0;p<n;p++) cout<<a[p]<<" ";
#define _ <<" "<<
#define nl cout<<endl;
#define sq(x) ((x)*(x))
#define call(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ff first
#define ss second
#define lld long double
#define tc(tt) \
    yo tt;    \
    cin >> tt; \
    for (int _tt = 0; _tt < tt; _tt++) 
 
yo dx[] = {1, 0, -1, 0};
yo dy[] = {0, 1, 0, -1};
const yo N = 1000*1000+5;
const yo size = 1000*100*2+5;
const yo mod = 1000*1000*1000+7;
 
yo gcd(yo a, yo b){if(!b)return a;return gcd(b, a % b);} 
yo power_mod(yo x,yo y,yo p){yo res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;} 
yo lcm(yo a, yo b){return (a*b)/gcd(a, b);}
yo sumofdigits(yo n){yo out=0;while(n){out+=(n%10);n/=10;}return out;}
bool isPrime(yo n){if (n <= 1)  return false; if (n <= 3)  return true; if (n%2 == 0 || n%3 == 0) return false; for (yo i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return false;return true;} 
yo power(yo a,yo b){if(b==0)return 1;if(b&1)return a*power(a,b-1);yo res=power(a,b/2);return res*res;}
yo log(yo d){return log2(d);}
bool isPower(yo x, yo y){if(x==1) return (y==1); yo pow=1; while(pow<y) pow*=x; return(pow == y);}  
bool compare (const pair<yo,yo> &i,const pair<yo,yo> &j){return i.first < j.first;}
yo i,j;

lld polygonArea(lld X[], lld Y[], yo n) 
{   
    lld area = 0.0; 
    yo j = n - 1; 
    for (yo i = 0; i < n; i++) 
    { 
        area += (X[j] + X[i]) * (Y[j] - Y[i]); 
        j = i;  
    }    
    return abs(area); 
} 
bool prime[100200];
vector<yo> dp;
 
void SieveOfEratosthenes(yo n) 
{   
    for (yo p=2; p*p<=n; p++) 
    { 
        if (prime[p] == true) 
        { 
            for ( i=p*p; i<=n; i += p) 
                prime[i] = false;   
        } 
    } 
  
    for (yo p=2; p<=n; p++)  
       if (prime[p]) 
          dp.pb(p); 
} 

int main ()
{
    char c;
    cin>>c;

    cout<<char(c+1);
  nl



}
/*


200560490130



*/

Measured memory_bytes: 256
def is_equal(i,j,m):
    d = 0
    for k in range(m):
        if a[i+k][0][j:j+m] == b[k][0][::]:
            d = 0
        else:
            return False
    if d == 0:
        return True

n,m = map(int,input().split())
a = [0]*n
b = [0]*m
for i in range(n):
    a[i] = list(input().split())
for i in range(m):
    b[i] = list(input().split())

for i in range(n-m+1):
    ans = 0
    for j in range(n-m+1):
        if is_equal(i,j,m):
            ans =1
            break
    if ans == 1:
        break
if ans == 1:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
n = int(input())
l = []
for _ in range(n):
    a, b = map(int, input().split())
    l.append([a, b])

l.sort(key=lambda x: x[1])
time = 0
for w, t in l:
    time += w
    if t < time:
        print("No")
        exit()
else:
    print("Yes")


Measured memory_bytes: 38036
#include <bits/stdc++.h>
#define ll          long long int
#define uu          first
#define vv          second
#define pii         pair<int,int>
#define pll         pair<ll,ll>
#define INF         1e9
#define fastRead    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;

const int MAX = 1e5 + 5;
const ll MOD = 1e9 + 7;
ll dp[200][MAX];

int main()
{
    fastRead;
    int n, k;
    cin>>n>>k;
    vector<int>vec(n+1);
    ll tot = 0;
    for(int i =1 ; i <=n ; i++) cin>>vec[i], tot += vec[i];
    
    dp[0][0] = 1;
    for(int i = 1; i <=n ; i++ ) {
        
        vector<ll>pref(k+1);
        pref[0] = dp[i-1][0];
        
        for(int j =1 ; j <=k ; j++ ) pref[j] = (dp[i-1][j] + pref[j-1]) % MOD;
//        for(ll x : pref) cout<<x<<" ";
//        cout<<'\n';
        
        for(int j = 0 ; j <= k ; j++ ) {
            
            int frm = max(0, j - vec[i]), to = j;
            
            ll sum = pref[to];
            if(frm) sum = (sum - pref[frm-1] + MOD )%MOD;
//            cout<<j<<" "<<sum<<'\n';
            
            dp[i][j] = (dp[i][j] + sum + MOD) % MOD;
        }
    }
    cout<<dp[n][k]<<'\n';
    return 0;
}

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

typedef long long ll;

int main() {
    ll ans;
    ll N;
    cin >> N;
    ll ac = 0, wa = 0, tle = 0, re = 0;
    string input;
    for(int i = 0; i < N; i++) {
        cin >> input;
        if(input == "AC") {
            ac++;
        } else if (input == "WA") {
            wa++;
        } else if (input == "TLE") {
            tle++;
        } else if (input == "RE") {
            re++;
        }
    }

    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl;
    cout << "TLE x " << tle << endl;
    cout << "RE x " << re << endl;

    return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define l long long
#define c continue
using namespace std; 
int main(){l m=1e9+7,x,y,z=1,w=0,o,p,q,v[93],t[91][91][2],a,b;v[0]=1,v[1]=1;for(l i=2;i<93;i++)v[i]=v[i-1]+v[i-2];for(l i=2;i<91;i++){for(l j=1;j<i;j++){a=v[i],b=v[i+1];if(j==1){t[i][j-1][0]=a,t[i][j-1][1]=b,t[i][j][0]=b,t[i][j][1]=2*b-a;c;}t[i][j][0]=t[i-1][j-1][1],t[i][j][1]=t[i-1][j-1][1]+t[i-1][j-1][0];}}cin>>q;while(q--){cin>>x>>y;if(x>y)swap(x,y);if(y==1){cout<<"1 1\n";c;}for(l i=0;i<93;i++){if(v[i]>x||v[i+1]>y){z=i-1;break;}}cout<<z<<" ";if(z==1){cout<<x*y%m<<endl;c;}w=0;for(l j=0;j<z;j++){o=t[z][j][0],p=t[z][j][1];if(o>x||p>y)c;w+=(y-p)/o+1;w%=m;if(x>=p)w+=(x-p)/o+1;w%=m;}cout<<w<<"\n";}}

Measured memory_bytes: 4224
import sys
input = sys.stdin.readline

n, x, y = map(int, input().split())
x, y = x-1, y-1
cnt = [0] * (n - 1)

for i in range(n):
    for j in range(i+1, n):
        a = abs(j-i)
        b = abs(x-i) + abs(y-j) + 1
        c = abs(y-i) + abs(x-j) + 1
        cnt[min(a,b,c) - 1] += 1

print(*cnt, sep="\n")


Measured memory_bytes: 47580
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

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

    int n;
    cin >> n;
    int ans = 0;
    auto dfs = [&](auto&& self, ll x = 0, int a = 0, int b = 0, int c = 0) -> void {
        if(x > n)   return;
        if(a != 0 && b != 0 && c != 0)  ++ans;
        self(self, x * 10 + 3, a + 1, b, c);
        self(self, x * 10 + 5, a, b + 1, c);
        self(self, x * 10 + 7, a, b, c + 1);
    };
    dfs(dfs);
    cout << ans << endl;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    for (auto& e : d) cin >> e;

    int ans = 0;
    for (int i = 0; i + 1 < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ans += d[i] * d[j];
        }
    }

    cout << ans << endl;
}


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

using namespace std;
 
/// ----------------------------- (Debug) ------------------------------
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...);
struct debug {
#ifndef ONLINE_JUDGE
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i));}
sim, class b dor(pair < b, c > d) {ris << "(" << d.first << ", " << d.second << ")";}
sim dor(rge<c> d) {*this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]";}
#else
sim dor(const c&) { ris; }
#endif
};
vector<char*> tokenizer(const char* args) {
	char *token = new char[111]; strcpy(token, args); token = strtok(token, ", ");
	vector<char*> v({token});
	while(token = strtok(NULL,", ")) v.push_back(token);
	return reverse(v.begin(), v.end()), v;
}
void debugg(vector<char*> args) { cerr << "\b\b "; }
template <typename Head, typename... Tail>
void debugg(vector<char*> args, Head H, Tail... T) {
	debug() << " [" << args.back() << ": " << H << "] ";
	args.pop_back(); debugg(args, T...);
}
#define harg(...) #__VA_ARGS__
#ifndef ONLINE_JUDGE
#define dbg(...) { debugg(tokenizer(harg(__VA_ARGS__, \b\t-->Line)), __VA_ARGS__, __LINE__); cerr << endl;}
#else
#define dbg(...) { }
#endif
/// -----------------------------------------------------------------------
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi; 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)    
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define print(x) cout << x << "\n";
#define REP(i,a,b) for(i=a;i<=b;i++)
#define RAP(i,a,b) for(i=a;i>=b;i--)
#define spa <<" "<<
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
ll mod=1e9+7;
const int MX=0x3f3f3f3f;

int main(){
	int n,k,i;
	cin>>n>>k;
	int a[n],mi=0;
	REP(i,0,n-1) cin>>a[i],mi=max(mi,a[i]);
	ll l=1,r=mi,mid,sum=0;
	int ans=0;
	while(l<r){
		mid=(l+r)/2;
		sum=0;
		REP(i,0,n-1) {
			sum+=a[i]/mid;
			if(a[i]%mid==0) sum--;
		}
		if(sum<=k) r=mid,ans=mid;
		else l=mid+1;
	}
	cout<<r;
  	return 0;
}

Measured memory_bytes: 4304
#include<iostream>
#include<algorithm>
#include<string>
#include<set>
using namespace std;
int n;
string rev(string str){
	string ans = "";
	for(int i = str.size() - 1;i >= 0;i--)ans += str[i];
	return ans;
}

string str;
void solve(){
	cin >> str;
	set<string> ans;
	for(int i = 1;i < str.size();i++){
		string tmp1, tmp2;
		for(int j = 0;j < str.size();j++){
			if(j < i)tmp1 += str[j];
			else tmp2 += str[j];
		}
		ans.insert(tmp1+tmp2);
		ans.insert(tmp2+tmp1);
		tmp1 = rev(tmp1);

		ans.insert(tmp1+tmp2);
		ans.insert(tmp2+tmp1);
		tmp2 = rev(tmp2);
		
		ans.insert(tmp1+tmp2);
		ans.insert(tmp2+tmp1);
		tmp1 = rev(tmp1);

		ans.insert(tmp1+tmp2);
		ans.insert(tmp2+tmp1);
		
	}
	cout << ans.size() << endl;
}

int main(){
	cin >> n;
	while(n--)solve();
	return 0;
}


Measured memory_bytes: 3248
# D
N = int(input())
lis = []
if N == 1:
    print(0)
else:
    n = N
    while n % 2 == 0:
        lis.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            lis.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        lis.append(n)
    
    cnt = 0
    for i in range(1, len(lis)):
        if lis[i] == lis[i-1]:
            cnt +=1
            lis.append(lis[i] ** cnt)
        else:
            cnt = 0
    
    set_lis = set(lis)
    sorted_set = sorted(set_lis)
    
    ans = 0
    for i in range(len(sorted_set)):
        if N % sorted_set[i] == 0:
            N //= sorted_set[i]
            ans += 1 
    print(ans)

Measured memory_bytes: 9248
//#include <boost/multiprecision/cpp_dec_float.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <algorithm>
#include <bitset>
#include <iomanip>
using namespace std;
//namespace mp = boost::multiprecision;
//using llll = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
//using Real = mp::number<mp::cpp_dec_float<1024>>;
using ll = long long;
const double EPS = 1e-10;
const ll MOD = 7+(1e+9);

ll pow_ans(ll x, int n) {
  ll res=1;
  while (n>0) {
    if (n & 1) res=res*x%MOD;
    x=x*x%MOD;
    n>>=1;
  }
  return res;
}

int main(){
  //cout<<fixed<<setprecision(10);
  ll n,k,ans=0;
  cin>>n>>k;
  vector<ll>v(n,0);
  for(ll i=0;i<n;i++){
    cin>>v[i];
  }
  if(n==1){
    cout<<0<<endl;
    return 0;
  }
  sort(v.begin(),v.end());
  ll t=1;
  for(ll i=k-1;i<n;i++){
    ans=(ans+MOD+t*(v[i]-v[n-i-1])%MOD)%MOD;
    ans=(ans+MOD)%MOD;
    t=t*(i+1)%MOD;
    t=t*pow_ans(i-k+2,MOD-2)%MOD;
  }
  while(ans<0){
    ans=(ans+MOD)%MOD;
  }
  cout<<ans<<endl;

}


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

int main() {
  int N; cin>>N;
  int K; cin>>K;
  vector<int> h(N);
  for (int i = 0; i < N; i++) cin>>h[i];

  int sum = 0;
  for (int i = 0; i < N; i++) {
    if (h[i] >= K) sum++;
  }
  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 640
import numpy as np

N = int(input())
plans = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * (N + 1) for _ in range(3)]

for j in range(N):
    for i_1 in range(3):
        for i_2 in range(3):
            if i_1 == i_2:
                continue
            dp[i_2][j+1] = max(dp[i_2][j+1], dp[i_1][j] + plans[j][i_2])

ans = np.array(dp)
print(ans[:, N].max())

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

const int N = 330, inf = 2e9;
typedef long long ll;

ll dist[N][N], dp[N][N];

int main()  
{
	int n, m, l;
	cin >> n >> m >> l;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			dist[i][j] = inf;
			dp[i][j] = inf;
		}
	for (int i = 0; i < m; i++)
	{
		int v, u, w;
		cin >> v >> u >> w;
		v--, u--;
		if(w > l)
			continue;
		dist[v][u] = w, dist[u][v] = w;
	}
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if(i == j)
				continue;
			if(dist[i][j] <= l)
				dp[i][j] = 1;
		}
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
	int q;
	cin >> q;
	while(q--)
	{
		int v, u;
		cin >> v >> u;
		v--, u--;
		if(dp[v][u] == inf)
			cout << -1 << "\n";
		else
			cout << dp[v][u] - 1 << "\n";
	}
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

const ll MOD = 1000000007LL; // = 10^9 + 7
const double PI = 3.14159265358979;

void solve()
{
  ll h, w, m, hin, win;
  cin >> h >> w >> m;
  vector<ll> ah(h + 1, 0);
  vector<ll> aw(w + 1, 0);
  vector<P> input(m);
  set<ll> hash;
  for(int i = 0; i < m; ++i)
  {
    cin >> hin >> win;
    ah[hin]++;
    aw[win]++;
    input[i] = P(hin, win);
    hash.insert((hin << 32LL) + win);
  }
  ll ah_max_ind = distance(ah.begin(), max_element(ah.begin(), ah.end()));
  ll aw_max_ind = distance(aw.begin(), max_element(aw.begin(), aw.end()));

  vector<ll> ah_ind;
  vector<ll> aw_ind;
  for(int i = 0; i <= h; ++i)
  {
    if (ah[i] == ah[ah_max_ind])
    {
      ah_ind.emplace_back(i);
    }
  }
  for(int i = 0; i <= w; ++i)
  {
    if (aw[i] == aw[aw_max_ind])
    {
      aw_ind.emplace_back(i);
    }
  }

  ll ans = ah[ah_max_ind] + aw[aw_max_ind];
  for(const auto& ih : ah_ind) for(const auto& iw : aw_ind)
  {
    if (hash.find( (ih << 32LL) + iw ) == hash.end())
    {
      cout << ans;
      return;
    }
  }

  if (hash.find( (ah_max_ind << 32LL) + aw_max_ind ) != hash.end()) ans--;
  if (m - ah[ah_max_ind] == 1) ans = m;
  if (m - aw[aw_max_ind] == 1) ans = m;

  cout << ans << endl;
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 34996
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include <algorithm> // sort
#include <map> // pair
using namespace std;


int main(){
  long long n;
  cin >> n;
  pair<long long,long long> p[n];
  long long x;
  long long a[n];
  for(long long i=0;i<n;i++){
    cin >> x;
    p[i].first = x;
    a[i]=0;
    if(x >= 0){
      p[i].second=1;
    }else{
      p[i].second=0;
    }
  }
  sort(p,p+n);
  long long count=0;
  for(long long i=0;i<n;i++){
    if(i == 0){
      if(p[i].first > 0){
        count += -p[i].first;
      }else{
        count += abs(p[i].first);
      }
    }else if(i == n-1 &&p[i].first<0){
      count -= abs(p[i].first);
    }else{
      count += abs(p[i].first);
    }
  }
  cout <<count<<endl;
  x=p[0].first;
  for(long long i=0;i<n-2;i++){
    if(!(p[n-i-2].first > 0) ^ (x < p[n-i-1].first)){
      cout << x << " " << p[n-i-1].first << endl;
      x -=p[n-i-1].first;
    }else{
      cout << p[n-i-1].first << " " << x << endl;
      x =p[n-i-1].first-x;
    }
  }
  if(x > 0){
    cout << x << " " << p[1].first << endl;
  }else{
    cout << p[1].first << " " << x << endl;
  }
}


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

typedef long long ll;
const ll MOD = 1000000007;

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<vector<int> > dp(n, vector<int>(k + 1));
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    // fill the bottom most row first
    for (int j = 0; j <= k; j++) {
        if (j <= a[n - 1])
            dp[n - 1][j] = 1;
        else
            dp[n - 1][j] = 0;
    }
    // start fillin subsequent rows
    for (int i = n - 2; i >= 0; i--) {
        ll sum = 0;
        // init sum
        for (int j = 0; j <= a[i]; j++) {
            sum += (ll)dp[i + 1][j];
            dp[i][j] = sum % MOD;
        }
        // window slide
        for (int j = a[i] + 1; j <= k; j++) {
            sum += (ll)dp[i + 1][j];
            sum -= (ll)dp[i + 1][j - a[i] - 1];
            dp[i][j] = sum % MOD;
        }
    }

    cout << dp[0][k] << endl;
}

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

int main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL);

  int n, t, a;
  cin >> n >> t >> a;
  int ans = 0;
  double best = INT_MAX;
  for (int i = 0; i < n; ++i) {
    int h;
    cin >> h;
    double temp = t - h * 0.006;
    double diff = abs(a - temp);
    if (diff < best) {
      ans = i + 1;
      best = diff;
    }
  }
  cout << ans << "\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,f[5010][5010],p=1e9+7;
char s[5010];
ll ksm(ll x,ll y){
	ll xlh=1;
	while(y){
		if(y&1)xlh=xlh*x%p;
		x=x*x%p;
		y/=2;
	}
	return xlh;
}
int main(){
	ll i,j;
	scanf("%lld",&n);
	scanf("%s",s+1);
	m=strlen(s+1);
	f[0][0]=1;
	for(i=0;i<n;i++)
	 for(j=0;j<=i;j++){
	 //	printf("%lld %lld %lld\n",i,j,f[i][j]);
	 	f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*2)%p;
	 	f[i+1][max(j-1,0ll)]=(f[i+1][max(j-1,0ll)]+f[i][j])%p;
	 }
	//for(i=0;i<=n;i++)printf("%lld ",f[n][i]);puts("");
	printf("%lld",f[n][m]*ksm(ksm(2,m),p-2)%p);
}

Measured memory_bytes: 194304
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << endl
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
int dx8[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy8[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int dx4[4] = {1, 0, -1, 0};
int dy4[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 io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;

//ここでのポイントは重複問題なんだけど、どうにも一次元ではできなさそうなとき2次元にできないか考えて二次元累積和をする

int main() {
 
     int N, M, Q;
     cin >> N >> M >> Q;
 
     vector<vector<int>> B(N + 1, vector<int>(N + 1, 0));//二次元累積和,AとSを一緒にしている
     for (int i = 0; i < M; i++) {
         int L, R;
         cin >> L >> R;
         B[L][R]++;
     }
 
     for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) B[i + 1][j + 1] += B[i][j + 1] + B[i + 1][j] - B[i][j];
     //L,Rは座標なのに対し、p,qは[p,q]x[p.q]のように二次元の範囲をとる
     for (int i = 0; i < Q; i++) {
         int p, q;
         cin >> p >> q;
         int ans = B[q][q] - B[p - 1][q] - B[q][p - 1] + B[p - 1][p - 1];
         cout << ans << endl;
     }
 
     return 0;
 }


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

#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T> struct BinaryIndexTree{
    int n;
    vector<T> bit; 
    vector<T> org;

    BinaryIndexTree(int si): bit(si+1), org(si+1) { n = si; }; 

    void add(int idx, T v){
        org[++idx] += v;
        for(int i = idx;i <= n;i+=i&-i) bit[i] += v;
    }

    void update(int idx, T v){
        T vv = v - org[++idx];
        org[idx] = v;
        for(int i = idx;i <= n;i+=i&-i) bit[i] += vv;
    }

    T sum(int a){
        T ret = 0;
        for(int i = a;i > 0;i-=i&-i) ret += bit[i];
        return ret;
    }

    T sum(int l, int r) { return sum(r)-sum(l); }; 
};

int a[500010];
int r[500010] = {};
int ans[500010];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;

	for(int i = 0;i < n;i++){
		cin >> a[i];
	}
	memset(r, -1, sizeof(r));

	vector<vector<pair<pair<int, int>, int>>> vec(n);
	for(int i = 0;i < q;i++){
		int l, r;
		cin >> l >> r;
		l--; r--;
		vec[r].push_back({{l, r}, i});
	}

	BinaryIndexTree<int> bit(n);
	for(int i = 0;i < n;i++){
		if(r[a[i]] != -1) bit.add(r[a[i]], -1);
		r[a[i]] = i;
		bit.add(r[a[i]], 1);
		for(int j = 0;j < vec[i].size();j++){
			ans[vec[i][j].second] = bit.sum(vec[i][j].first.first, i+1);
		}
	}

	for(int i = 0;i < q;i++){
		cout << ans[i] << endl;
	}

	return 0;
}


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

using namespace std;

struct UF {
  vector<int> data;
  UF(int n):data(n, -1){}
  int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); }
  int size(int x) { return -data[find(x)]; }
  bool same(int x, int y) { return find(x) == find(y); }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }
};

struct edge {
  int u, v;
  edge(){}
  edge(int u, int v):u(u), v(v){}
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<edge> es;
  for(int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    es.emplace_back(--a, --b);
  }
  reverse(es.begin(), es.end());
  vector<long long> ans;
  UF uf(n);
  for(edge& e : es) {
    if(uf.same(e.u, e.v)) {
      ans.push_back(0);
    } else {
      long long sz_u = uf.size(e.u);
      long long sz_v = uf.size(e.v);
      ans.push_back(sz_u*sz_v);
      uf.unite(e.u, e.v);
    }
  }
  reverse(ans.begin(), ans.end());
  partial_sum(ans.begin(), ans.end(), ans.begin());
  for(long long a : ans) cout << a << endl;

  return 0;
}


Measured memory_bytes: 3444
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using std::min;
using std::abs;

const int MAXN=1005,MAXW=5005;
int n;
int he[MAXN],w[MAXN],blk[MAXN],wht[MAXN];

struct line{
	int to,nex;
	line(int to=0,int nex=0):to(to),nex(nex){}
}ed[MAXN];

inline void addE(int u,int v){
	static int cnt=0;
	ed[++cnt]=line(v,he[u]);
	he[u]=cnt;
}

bool treeDP(int u){
	static int tmp[MAXN];
	static bool can[MAXW];
	for(int i=he[u];i;i=ed[i].nex){
		if(!treeDP(ed[i].to)) return false;
	}
	if(!he[u]){
		blk[u]=w[u];
		return true;
	}
	int need=w[u],sum=0;
	tmp[0]=0;
	for(int i=he[u],v;i;i=ed[i].nex){
		v=ed[i].to;
		need-=min(blk[v],wht[v]);
		if(need<0) return false;
		tmp[++tmp[0]]=abs(blk[v]-wht[v]);
		sum+=blk[v]+wht[v];
	}
	memset(can,false,sizeof(can));
	can[0]=true;
	for(int i=1;i<=tmp[0];++i){
		for(int j=MAXW-1;j>=tmp[i];--j)
			can[j]|=can[j-tmp[i]];
	}
	for(int i=need;i>=0;--i){
		if(can[i]){
			need-=i;
			break;
		}
	}
	blk[u]=w[u],wht[u]=sum-blk[u]+need;
	return true;
}

int main(){
	scanf("%d",&n);
	for(int i=2,fa;i<=n;++i){
		scanf("%d",&fa);
		addE(fa,i);
	}
	for(int i=1;i<=n;++i)
 		scanf("%d",&w[i]);
	if(treeDP(1)) printf("POSSIBLE");
	else printf("IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define llt long long int
#define M 1000000007
#define yesno(f) if(f){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define forr(j,n,k) for(int i=j;i<=n;i=i+k)
#define fori() for(int i=0;i<n;i++)
#define ford() for(int i=n-1;i>=0;i--)
#define MAX INT_MAX
#define MIN INT_MIN
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int main() {
    fastIO;
    int t=1;
  //  cin>>t;
    while(--t>=0)
    {
      int n,x,T,b,c;
      cin>>n>>x>>T;
     // int arr[n];
     // fori(){
      //    cin>>arr[i];
     // }
      llt temp=n/x;
      temp=temp*T;
      if(n%x==0)
      cout<<temp<<endl;
      else
      cout<<temp+T<<endl;
      
      
    }
      
	return 0;
}

Measured memory_bytes: 3688
#include <bits/stdc++.h>
using namespace std;
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;}
const long long INFLL = 1LL<<60;
const int INF = 1<<28;
const long long MOD =1000000000+7;

int main()
{
	int a,b;

	cin >>a>>b;

	cout <<max(a+b,max(a-b,a*b))<<endl;
}


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

int table[1000];
int bisect_right(int x,int a[],int left,int right){
    int mid;
    right++;
    while (left < right) {
        mid = (left + right) / 2;
        if (a[mid] <= x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}


int counter(int i) {
    if (i == 0) {
        return 0;
    }
    return bisect_right(i,table,0,39) - 1;
    
}

void solve(long long N, int *ans ){
    int cnt = 0;
    while (N % 2 == 0) {
        cnt++;
        N /= 2;
    }
    *ans += counter(cnt);
    int now = 3;
    cnt = 0;
    while ((long long)now * now <= N) {
        while (N % now == 0) {
            cnt++;
            N /= now;
        }
        *ans += counter(cnt);
        cnt = 0;
        now += 2;
    }
    if (N != 1) {
        *ans += counter(1);
    }
}



int main(void){
    long long N;
    scanf("%lld", &N);
    for (int i = 0; i < 40; i++) {
        table[i] = i * (i + 1) / 2;
    }
    int ans = 0;
    solve(N, &ans);
    printf("%d\n",ans);
    return 0;
}



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

#define ll long long
#define pb push_back
#define vi vector<int>
#define sz(a) (int((a).size()))
#define mp make_pair
#define f first
#define s second
#define pii pair<int, int>

using namespace std;

const int N = 200200;
int n;
int a[N];
int cnt[2][N];
int ans;
int k1, k2, k3, k4;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		cnt[i & 1][a[i]]++;
	}
	
	int mx1 = 0, mx2 = 0, val1 = 0, val2 = 0;
	for (int i = 1; i < N; i++) {
		if (cnt[0][i] >= mx1) {
			mx2 = mx1;
			mx1 = cnt[0][i];
			val2 = val1;
			val1 = i;
		} else if (cnt[0][i] > mx2) {
			mx2 = cnt[0][i];
			val2 = i;
		}
	}
	k1 = n / 2 - mx1;
	k2 = n / 2 - mx2;
		
	int mx3 = 0, mx4 = 0, val3 = 0, val4 = 0;
	
	for (int i = 1; i < N; i++) {
		if (cnt[1][i] >= mx3) {
			mx4 = mx3;
			mx3 = cnt[1][i];
			val4 = val3;
			val3 = i;
		} else if (cnt[1][i] > mx4) {
			mx4 = cnt[1][i];
			val4 = i;
		}
	}
	k3 = (n + 1) / 2 - mx3;
	k4 = (n + 1) / 2 - mx4;
	
	/*cerr << mx1 << " " << val1 << "  " << k1 << endl;
	cerr << mx2 << " " << val2 << "  " << k2 << endl;
	cerr << mx3 << " " << val3 << "  " << k3 << endl;
	cerr << mx4 << " " << val4 << "  " << k4 << endl;
	*/
	
	int ans = 0;
	
	if (val1 != val3) {
		ans = k1 + k3;
	} else {
		ans = min(k1 + k4, k2 + k3);
	}
	
	cout << ans << endl;
	
		
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {
  int j,k,N,cnt=0;
  cin>>N;
  int L[N];
  
  for(int i=0;i<N;i++) cin>>L[i];
  sort(L,L+N);
  for(int i=0;i<N-2;i++){
    for(j=i+1;j<N-1;j++){
      for(k=j+1;k<N;k++){
        if(L[i]+L[j]>L[k]) cnt++;
      }
    }
  }
  cout<<cnt<<endl;
}	


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long

ll burger(ll L,ll X,pair<ll,ll> Lburg[]){
  ll ans;
  if(L==0)ans=1;
  else{
    if(X==1){
      ans=0;
    }else if(X<Lburg[L-1].first+2){
      ans=burger(L-1,X-1,Lburg);
    }else if(X==Lburg[L-1].first+2){
      ans=Lburg[L-1].second+1;
    }else if(X<2*Lburg[L-1].first+3){
      ans=Lburg[L-1].second+1+burger(L-1,X-Lburg[L-1].first-2,Lburg);
    }else if(X==2*Lburg[L-1].first+3){
      ans=2*Lburg[L-1].second+1;
    }
  }
  return ans;
}

int main(){
    ll N,X;
    cin >> N >>X;
    pair<ll,ll> Lburg[N+1];
    Lburg[0].first=1;
    Lburg[0].second=1;
    ll i;
    for(i=1;i<=N;i++){
      Lburg[i].first=2*Lburg[i-1].first+3;
      Lburg[i].second=2*Lburg[i-1].second+1;
    }
    cout << burger(N,X,Lburg);
    return 0;
}


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

int n;
int a[3];
vector<int> yaku;

int main() {
	int i, j;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> a[i];
	
	for (i = 1; i * i <= a[0]; i++) { if (a[0] % i == 0) { yaku.push_back(i); yaku.push_back(a[0] / i); } }
	sort(yaku.begin(), yaku.end());
	
	for (i = 0; i < yaku.size(); i++) {
		for (j = 0; j < 3; j++) {
			if (a[j] % yaku[i] != 0) { break; }
		}
		if (j == 3) cout << yaku[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 3160
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int MAXN = 410;
const int MAXM = 100010;

int n, m, a[MAXM], b[MAXM];

void input() {
	scanf( "%d%d", &n, &m );
	for( int i = 0; i < m; ++i )
		scanf( "%d%d", a+i, b+i );
}

int f[MAXN][MAXN] = {0}, ok[MAXN];
bool check( int a, int b ) {
	for( int i = 1; i <= n; ++i )
		if( f[a][i] && f[b][i] ) return false;
	return true;
}
void solve() {
	for( int i = 1; i <= n; ++i ) {
		ok[i] = 1, f[i][i] = 1;
		for( int j = m-1; j >= 0; --j ) {
			int x = a[j], y = b[j];
			if( f[i][x] && f[i][y] ) {
				ok[i] = 0; break;
			}
			if( !f[i][x] && !f[i][y] ) continue;
			f[i][x] = f[i][y] = 1;
		}
	}
	int ans = 0;
	for( int i = 1; i <= n; ++i )
		for( int j = i+1; j <= n; ++j )
			if( ok[i] && ok[j] && check(i,j) )
				++ans;
	printf( "%d\n", ans );
}

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


Measured memory_bytes: 1536
import java.util.Scanner;

public class Main {
    public void main(Scanner sc) {
        int n[] = new int[9];
        for (int i = 0; i < 9; i++) {
            n[i] = sc.nextInt();
        }

        if (!check(n[0] - n[1], n[3] - n[4], n[6] - n[7])
            || !check(n[1] - n[2], n[4] - n[5], n[7] - n[8])
            || !check(n[0] - n[3], n[1] - n[4], n[2] - n[5])
            || !check(n[3] - n[6], n[4] - n[7], n[5] - n[8])) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }

    }

    private boolean check(int sa1, int sa2, int sa3) {
        return (sa1 == sa2) && (sa2 == sa3) && (sa3 == sa1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        new Main().main(sc);
        sc.close();
    }
}


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

int main()
{
	int a[1000000],v=0;
	cin>>a[0];
	
	for(int i=1;;i++){
		if(a[i-1]%2) a[i]=3*a[i-1]+1;
		else a[i]=a[i-1]/2;
		for(int j=0;j<i;j++){
			if(a[i]==a[j]){
				v=i;
				break;
			}
		}
		if(v) break;
	}
	
	cout<<v+1<<endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <deque>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <stack>
#include <queue>
#include <functional>
#include <climits>
#include <bitset>
#include <random>
#include <tuple>
#include <initializer_list>
#include <fstream>

int main() {
	std::vector<int> team(4); for (auto& t : team) std::cin >> t;
	std::sort(team.begin(), team.end());
	std::cout << std::abs(team[0] + team[3] - team[1] - team[2]) << std::endl;
}


Measured memory_bytes: 3164
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int x,a,b;
	cin>>x>>a>>b;
	int a1=abs(x-a);
	int b1=abs(x-b);
	if(a1<b1)
		cout<<'A';
	else
		cout<<'B';
	
	return 0;
}

Measured memory_bytes: 256
import java.math.BigInteger

fun main(args: Array<String>) {
    val (n, p) = readLine()!!.split(" ").map { it.toLong() }
    println(solve(n, p))
}

fun solve(n: Long, p: Long): Long {
    if (n >= 60) return 1
    if (n == 1L) return p
    var max = 1L
    var x = 1L
    while (true) {
        if (BigInteger.valueOf(x).pow(n.toInt()) > BigInteger.valueOf(p)) {
            break
        }
        val xp = BigInteger.valueOf(x).pow(n.toInt()).toLong()
        if (p % xp == 0L) {
            max = x
        }
        x++
    }
    return max
}


Measured memory_bytes: 114968
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 998244353;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
string S;

void solve() {
	cin >> N;
	cin >> S;
	int r = 0;
	int b = 0;
	int g = 0;
	int rb = 0;
	int bg = 0;
	int gr = 0;
	int place = 0;

	ll res = 1;
	rep(i, 0, 3 * N) {
		if(S[i] == 'R') {
			if(bg) MUL(res, bg--);
			else if(b) {
				MUL(res, b--); rb++;
			}
			else if(g) {
				MUL(res, g--); gr++;
			}
			else {
				MUL(res, N - place);
				place++; r++;
			}
		}
		else if(S[i] == 'G') {
			if(rb) MUL(res, rb--);
			else if(b) {
				MUL(res, b--); bg++;
			}
			else if(r) {
				MUL(res, r--); gr++;
			}
			else {
				MUL(res, N - place);
				place++; g++;
			}
		}
		else {
			if(gr) MUL(res, gr--);
			else if(g) {
				MUL(res, g--); bg++;
			}
			else if(r) {
				MUL(res, r--); rb++;
			}
			else {
				MUL(res, N - place);
				place++; b++;
			}
		}
	}
	cout << res << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



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

int main()
{
    int x, n;
    cin >> x >> n;
    if (n == 0)
    {
        cout << x << endl;
    }
    else
    {
        vector<int> p;
        vector<int> ans;
        int ans1=1000,ans2=1000;
        for (int i = 0; i < n; i++)
        {
            int a;
            cin >> a;
            p.push_back(a);
        }
        for(int i=x;;i--){
            bool flag=true;
            for(int j=0;j<n;j++){
                if(p[j]==i){
                    flag=false;
                }
            }
            if(flag==true){
                ans1=i;break;
            }
        }
        for(int i=x;;i++){
            bool flag=true;
            for(int j=0;j<n;j++){
                if(p[j]==i){
                    flag=false;
                }
            }
            if(flag==true){
                ans2=i;break;
            }
        }
        cout<<((abs(ans1-x)<=abs(ans2-x))?ans1:ans2)<<endl;
    }
}


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

//UURDDL LUUURRDRDDDLLU


int main(){
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    tx -= sx;
    ty -= sy;

    for(int i = 0; i < ty; i++)
    {
        cout << 'U';
    }
    for(int i = 0; i < tx; i++)
    {
        cout << 'R';
    }
    for(int i = 0; i < ty; i++)
    {
        cout << 'D';
    }
    for(int i = 0; i < tx; i++)
    {
        cout << 'L';
    }


    cout << 'L';
    for(int i = 0; i < ty+1; i++)
    {
        cout << 'U';
    }
    for(int i = 0; i < tx+1; i++)
    {
        cout << 'R';
    }
    cout << 'D';

    cout << 'R';
    for(int i = 0; i < ty+1; i++)
    {
        cout << 'D';
    }
    for(int i = 0; i < tx+1; i++)
    {
        cout << 'L';
    }
    cout << 'U';

    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
l = sum(B)-sum(A)
c = 0
for k in range(N):
    if A[k]>B[k]:
        c -= A[k]-B[k]
    elif A[k]<B[k]:
        c += (B[k]-A[k])//2

print("Yes" if 0<=c else "No")


Measured memory_bytes: 4596
#pragma GCC optimize("Ofast",3,"inline")
#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define m_p make_pair
#define y1 ygftgfgcdtfgxffgx
#define y2 yfdsesgvtyghftfvv
#define x1 xvyr6cf6fgcfgf676
#define x2 xcr6rfc5r66y6r6fr
#define up_bound upper_bound
#define low_bound lower_bound
#define next_per next_permutation
#define pb push_back
#define i_to_s to_string
typedef priority_queue<int> p_queue;
typedef priority_queue<int, vector<int>, greater<int> > min_p_queue;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int mon[20]={31,28,31,30,31,30,31,31,30,31,30,31};
ll gcd(ll x,ll y){return ((y==0)?x:gcd(y,x%y));}
const int maxn=2e5+5;
int n,nxt[maxn][26],f[maxn];
string s;
int main(){
	cin>>s;s=' '+s;n=s.size()-1;
	memset(nxt,-1,sizeof(nxt));
	for(int i=n;i>0;i--)
		for(int j=0;j<26;j++)
			nxt[i][j]=(s[i]==j+'a'?i:nxt[i+1][j]);
	memset(f,0x3f,sizeof(f));
	for(int i=n;i>0;i--){
		for(int j=0;j<26;j++){
			if(nxt[i][j]==-1){f[i]=1;break;}
			f[i]=min(f[i],f[nxt[i][j]+1]+1);
		}
	}
	int len=f[1],pos=1;
	while(len--){
		if(!len)for(int i=0;i<26;i++)
				if(nxt[pos][i]==-1)return 0*putchar(i+'a');
		for(int i=0;i<26;i++)
			if(f[pos]==f[nxt[pos][i]+1]+1){
				pos=nxt[pos][i]+1;
				putchar(i+'a');break;
			}
	}
	return 0;
}

Measured memory_bytes: 21696
#include <bits/stdc++.h>
using namespace std;
int main() {

bool ok=true;
char s[100001];

cin>>s;

for (char z='a';z<='z';z++)
    if (!strchr(s,z)){cout<<z;ok=false; break;}

    if (ok)cout<<"None";
    return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++) 
#define ll long long
#define ld long double
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define swapll(x, y) { ll tmp = x; x = y; y = x; }

int main()
{
  int n;
cin >> n;
	vector<string> list;
    vector<int> nums;
  list.push_back("a");
  nums.push_back(1);
  
  rep(i, n - 1)
  {
    vector<string> next;
    vector<int> nextnums;
    rep(x, list.size())
    {
      string s = list[x];
      rep(nn, nums[x])
      {
        next.push_back(s + string(1, 'a' + nn));
        nextnums.push_back(nums[x]);
      }
      next.push_back(s + string(1, 'a' + nums[x]));
      nextnums.push_back(nums[x] + 1);
    }
    
    list = next;
    nums = nextnums;
  }
  
  for(auto s = list.begin(); s != list.end(); ++s)
  {
      cout << fixed << (*s) << endl;
  }
	return 0;
}

Measured memory_bytes: 9500
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <set>
#include <map>
#include <cassert>
#include <fstream>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
unsigned long long mod = 1e9 + 7;
unsigned long long base = 998244353;

vector<vector<int>> g;
vector<long long> vv;
vector<bool> c;
void dfs(int v, long long value)
{
    if (c[v])
    {
        return;
    }
    c[v] = 1;
    vv[v] += value;
    for (int i = 0; i < g[v].size(); ++i)
    {
        dfs(g[v][i], vv[v]);
    }
}

int main() {
    

    
    int n, q;
    cin >> n >> q;
    g = vector<vector<int>>(n, vector<int>());

    for (int i = 0; i < n - 1; ++i)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vv = vector<long long>(n);
    c = vector<bool>(n);
    for (int i = 0; i < q; ++i)
    {
        int p, x;
        cin >> p >> x;
        p--;
        vv[p] += x;
    }
    
    dfs(0, 0);
    
    for (int i = 0; i < n; ++i)
    {
        if (i == n - 1)
        {
            cout << vv[i] << endl;
            return 0;
        }
        cout << vv[i] << " ";
    }
    
    return 0;
}

Measured memory_bytes: 21120
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

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

        ll ans = 0;

        if(A >= B)
        {
                ans += A;
                --A;
        }
        else if(B > A)
        {
                ans += B;
                --B;
        }

        if(A >= B)
        {
                ans += A;
                --A;
        }
        else if(B > A)
        {
                ans += B;
                --B;
        }

        cout << ans << endl;

        return 0;
}

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

int main(){
    int n,m;
    cin >> n >> m;
    int a,b;
    map<int,int> ans;
    for (int i = 0;i < m;i++){
        cin >> a >> b;
        ans[a] += 1;
        ans[b] += 1;
    }
    for (int i = 1;i <= n;i++){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{

    int a,i,j,b,temp,k,s=0,d;
    scanf("%d %d",&a,&d);
    int c[a];
    for(i=0;i<a;i++){
        scanf("%d",&c[i]);
    }
    for(j=0;j<a-1;j++){
        for(b=0;b<a-1;b++){
            if(c[b]<c[b+1]){
                temp=c[b+1];
                c[b+1]=c[b];
                c[b]=temp;
            }
        }
    }
    for(k=0;k<d;k++){
    s+=c[k];
    }
    printf("%d",s);

return 0;
}



Measured memory_bytes: 128
class FactMod:

    def __init__(self, n, mod):
        self.mod = mod
        self.f = [1] * (n + 1)
        for i in range(1, n + 1):
            self.f[i] = self.f[i - 1] * i % mod

        self.inv = [pow(self.f[-1], mod - 2, mod)]
        for i in reversed(range(1, n + 1)):
            self.inv.append(self.inv[-1] * i % mod)
        self.inv.reverse()

    def fact(self, n):
        """
        :return: n!
        """
        return self.f[n]

    def comb(self, n, r):
        """
        :return: nCr
        """
        return self.f[n] * self.inv[n - r] * self.inv[r] % self.mod

N, M, K = map(int, input().split())
mod = 10 ** 9 + 7

NM = N * M
fa = [1] * (NM + 1)

for i in range(1, NM + 1):
    fa[i] = (fa[i - 1] * i) % mod

ans = 0
for i in range(1, N):
    ans += (i * M * M * (N - i)) % mod
    ans %= mod

for i in range(1, M):
    ans += (i * N * N *(M-i)) % mod
    ans %= mod

factmod = FactMod(NM-2, mod)
ans *= factmod.comb(NM-2, K-2)
ans %= mod
print(ans)


Measured memory_bytes: 26796
main :: IO ()
main = do
    a <- fmap read getLine
    b <- fmap read getLine
    c <- fmap read getLine
    x <- fmap read getLine
    putStrLn $ show $ fsuru a b c x

    --　まずは重ためにコードを書いてしまう。


fsuru :: Int->Int->Int->Int->Int
fsuru a b c x = if a>=0 then
                    gsuru (x - 500*a) b c + fsuru (a-1) b c x
                else 0 
                    -- a以下の全ての値でやる

gsuru :: Int -> Int-> Int->Int
gsuru x2 b c =  if b >= 0 then
                    hsuru (x2 - 100*b) c + gsuru x2 (b-1) c
                else 0
                    -- aを固定してb以下ですべてやる

hsuru :: Int -> Int -> Int
hsuru x3 c = if x3 - 50*c >0 || x3<0 then 0
             else 1
             -- ここで削りきれるならTrue 削りきれないならFalse



-- この形にすると少なくともリストは使わない


Measured memory_bytes: 508
#include<iostream>
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include<algorithm>
#include<math.h>
#include"boost/algorithm/string.hpp"

using namespace std;


int main(){


	/*Q2*/

	/*Q3*/

	/*Q1*/

	int a, b;
	cin >> a >> b;

	if (a == b){
		cout << a + b;
	}
	else{
		if (a < b){
			cout << b * 2 - 1;
		}
		else{
			cout <<  a * 2 - 1;
		}
	}

	return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
S = []
for i in range(M):
  ks = list(map(int, input().split()))
  S.append(sum(1<<(s-1) for s in ks[1:]))

p = list(map(int, input().split()))

ans = 0
for state in range(2**N):
  on = True
  for m in range(M):
    on = bin(S[m] & state).count('1') % 2 == p[m]
    if not on:
      break
  
  ans += on

print(ans)

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

int main(){
	int N , K , answer = 1 ;
  	cin >> N >> K;
  	for (int i = 0 ; i < N ; i ++){
    	if (answer * 2 < answer + K){
          	answer *=  2;
        }else{
        	answer = answer + K;
        }
    }
  	cout << answer << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  string YABAI, WAYO;
  int A, B, C = 0, D, E, F, G;
  
  cin >> YABAI >> WAYO;
  A = YABAI.size();
  
  for(int YUNI = 0;YUNI < A; YUNI ++){
    if(YABAI.at(YUNI) != WAYO.at(YUNI)){
      C ++;
    }
  }
    
  cout << C << endl;
}


Measured memory_bytes: 3920