akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<string>
#include<vector>
using namespace std;
int main(void){
    int n,k;
    string x;
    cin>>n>>k>>x;
    if(x[k-1]=='A')
    {
        x[k-1]='a';
    }
    else if(x[k-1]=='B')
    {
        x[k-1]='b';
    }
    else
    {
        x[k-1]='c';
    }
    cout <<x<<endl;
    
    return 0;
}

Measured memory_bytes: 256
n=int(input())
l = list(map(int,input().split()))
q=int(input())
l1 = [list(map(int,input().split())) for _ in range(q)] #複数行複数入力を多重リストに
d={}
ans=0
for i in l:
    if  i in d:
        d[i]+=1
        ans+=i
    else:
        d[i]=1
        ans+=i
for i in l1:
    if i[0] not in d:
      print(ans)
    elif i[0] in d:
      ans+=i[1]*d[i[0]]-i[0]*d[i[0]]
      if i[1] in d:
        d[i[1]]+=d[i[0]]
      else:
        d[i[1]]=d[i[0]]
      d[i[0]]=0
      print(ans)


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

const double PI = 3.14159265358979323846;
//using namespace boost::multiprecision;
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 1e15;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

std::istream &operator>>(std::istream &in, set<int> &o) {
    ll a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
//const ll mod = 1e10;
typedef priority_queue<string, vector<string>, greater<string> > PQ_ASK;

int main() {
    int h, w, a, b;
    cin >> h >> w >> a >> b;

    vector<vector<int>> matrix(h, vector<int>(w, 0));

    rep(y, h) {
        rep(x, w) {
            if (y < b && x < a) {
                matrix[y][x] = 0;
            } else if (y < b) {
                matrix[y][x] = 1;
            } else if (x < a) {
                matrix[y][x] = 1;
            } else {
                matrix[y][x] = 0;
            }
        }
    }


    rep(y, h) {
        rep(x, w) {
            cout << matrix[y][x];
        }
        cout << endl;
    }
}


Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
//#include "library/debug.cpp"

struct RollingHash {
    ll base1;
    ll base2;
    ll mod1;
    ll mod2;
    vector<ll> hash1;
    vector<ll> hash2;
    vector<ll> pow1;
    vector<ll> pow2;

    RollingHash()
        : base1(1009), base2(1007), mod1(1000000007), mod2(1000000009) {}

    void init(vector<ll> s) {
        int n = s.size();

        hash1.assign(n + 1, 0);
        hash2.assign(n + 1, 0);
        pow1.assign(n + 1, 1);
        pow2.assign(n + 1, 1);

        for (int i = 0; i < n; i++) {
            hash1[i + 1] = (hash1[i] + s[i]) * base1 % mod1;
            hash2[i + 1] = (hash2[i] + s[i]) * base2 % mod2;
            pow1[i + 1] = pow1[i] * base1 % mod1;
            pow2[i + 1] = pow2[i] * base2 % mod2;
        }
    }

    pair<ll, ll> get(int l, int r) {
        ll t1 = ((hash1[r] - hash1[l] * pow1[r - l]) % mod1 + mod1) % mod1;
        ll t2 = ((hash2[r] - hash2[l] * pow2[r - l]) % mod2 + mod2) % mod2;
        return make_pair(t1, t2);
    }
};

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

    ll n;
    cin >> n;
    vector<ll> a(n), b(n), s(n), t(2 * n);
    vector<pair<ll, ll>> ans;
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, n) cin >> b[i];
    rep(i, 0, n) {
        s[i] = a[i] ^ a[(i + 1) % n];
        t[i] = t[i + n] = b[i] ^ b[(i + 1) % n];
    }
    RollingHash x, y;
    x.init(s);
    y.init(t);
    pair<ll, ll> sh = x.get(0, n);

    rep(i, 0, n) {
        if (sh == y.get(i, i + n)) {
            ans.emplace_back((n - i) % n, a[0] ^ b[i]);
        }
    }

    sort(ans.begin(), ans.end());
    for (auto p : ans) {
        cout << p.first << ' ' << p.second << endl;
    }

    return 0;
}


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

string convertToTitle(unsigned long long int A) {
    string ans = "";
    while(A){
        int x = (A%26?A%26:26) + 64;
        ans = (char)x + ans;
        
        if(x == 90){
            A = (A/26)-1;
        }
        else{
            A = A/26;
        }
    }
    return ans;
}

int main(){

    unsigned long long int n;
    cin>>n;

    string s = convertToTitle(n);
    transform(s.begin(), s.end(), s.begin(), ::tolower); 
    cout<<s;
}

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

using pll=pair<long long,long long>;
int main(){
    int N;
    long long M;
    cin>>N>>M;
    vector<pll>v(N);
    for(int i=0;i<N;i++)cin>>v[i].first>>v[i].second;
    sort(v.begin(),v.end());

    long long res=0;
    for(int i=0;i<N&&M>0;i++){
        res+=v[i].first*min(M,v[i].second);
        M-=min(M,v[i].second);
    }
    cout<<res<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define re return
#define all(a) a.begin(),a.end()
#define int long long
using namespace std;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
signed main()
{
	int n;
	cin>>n;
	int ans=0;
	for (int i=1;i<=n;i++)  ans+=( i*(n/i)*(n/i+1)/2 );
	cout<<ans;
	re 0;
}


Measured memory_bytes: 3536
package main

import "fmt"

func main() {
	var H, W int
	fmt.Scan(&H, &W)
	if W < H {
		W, H = H, W
	}
	if H == 1 {
		fmt.Println(1)
		return
	}
	if H&1+W&1 == 2 {
		fmt.Println(W*(H-1)/2 + (W+1)/2)
	} else {
		fmt.Println(W * H / 2)
	}
}


Measured memory_bytes: 1768
#include<cstdio>
int main()
{
	long long n,m;
	scanf("%lld%lld",&n,&m);
	long long ans=m-n*2;
	if(ans<0)
	{
		printf("%lld\n",m/2);
		return 0;
	} 
	printf("%lld\n",n+ans/4);
}

Measured memory_bytes: 128
var a,b:array[0..2000000]of boolean;
    n,m,i,s,e:longint;
begin
  readln(n,m);
  for i:=1 to m do
  begin
    read(s,e);
    if s=1 then a[e]:=true;
    if e=n then b[s]:=true;
  end;
  for i:=1 to n do
    if a[i] and b[i] then
    begin
      writeln('POSSIBLE');
      halt;
    end;
  writeln('IMPOSSIBLE');
end.

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(false); cin.tie(NULL);
#define loop(i,n) for(int i=0;i<n;i++)
#define double long double
#define mod 1000000007
#define F first
#define S second
#define pb push_back

using namespace std;

signed main()
{
	fast;
	int test=1;
	// cin>>test;
	for(int index=0;index<test;index++)
	{
		int r;
		cin>>r;
		cout<<(double)2*3.141*r<<endl;
	}
}



Measured memory_bytes: 3800
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int mod = (int)1e9 + 7;
int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}
int mult(int a, int b) {
    return (1LL * a * b) % mod;
}
int sub(int a, int b) {
    int s = a -  b;
    if (s < 0) s += mod;
    return s;
}
const int maxN = 5005;
int dp[maxN][maxN];
int n;
int m;
int pw2[maxN];
string s;
int dpStart[maxN][maxN];
void upd(int& a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n;
    pw2[0] = 1;
    for (int i = 1; i <= n; i++) pw2[i] = mult(pw2[i - 1], 2);
    cin >> s;
    m = s.size();
    dpStart[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (!dpStart[i][j]) continue;
            int d = dpStart[i][j];
            if (j) {
                upd(dpStart[i + 1][j - 1], d);
            }
            else {
                upd(dpStart[i + 1][j], d);
            }
            d = sum(d, d);
            upd(dpStart[i + 1][j + 1], d);
        }
    }
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (!dp[i][j]) continue;
            int d = dp[i][j];
            if (j) {
                upd(dp[i + 1][j - 1], d);
            }
            upd(dp[i + 1][j + 1], d);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int ways = dpStart[i][0];
        // one good move
        int lft = n - i - 1;
        if (lft < m - 1) continue;
        int c = dp[lft][m - 1];
        if (!c) continue;
        int bck_space = (lft - (m - 1)) / 2;
        ans = sum(ans, mult(ways, mult(c, pw2[bck_space])));
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 194304
from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.appendleft((hn, wn, cnt))
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)


Measured memory_bytes: 247436
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;
 
priority_queue<pair<int, int> > q;
int n, m, d[1000001], a, b;
 
main(){
  scanf("%d%d", &n, &m);
  q.push(make_pair(0, -1));
  for(int i=0;i<m;i++){
    scanf("%d%d", &a, &b);
    d[a] += b;
    q.push(make_pair(d[a], -a));
    while(1){
      pair<int, int> p = q.top();
      if(p.first == d[-p.second]){
        printf("%d %d\n", -p.second, p.first);
        break;
      }
      q.pop();
    }
  }
}

Measured memory_bytes: 5840
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a; cin >> a;
	if(a % 2)
	{
		cout << "0";
		return 0;
	}
	long long ans = 0;
	int m = 0;
	long long tmp = 1;
	for(int i=1; i <= 25; i++)
		tmp *= 5;
	long long cnt[100] = {0};
	for(long long i=10; i <= a; i *= 5)
	{
		ans += a / i;	
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <bitset>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef long long LL;

typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<string, int> PSI;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const LL MOD = 1e9+7; 
//vector <vector<int>> x(20, vector<int> (20)), y(20,vector<int> (20));
/*int counter_1 (int x) {
    if(x == 0) return 0;
    return counter_1(x >> 1) + (x & 1);
}*/

//int Counter(int x)
/*int factorial(int n) {
    if (n > 0) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}*/
/*bool pairCompare(const P& firstElof, const P& secondElof)
{
    return firstElof.second > secondElof.second;
}*/


/*long nCr(int n, int r)
{
       if(n==r) return dp[n][r] = 1;
       if(r==0) return dp[n][r] = 1;
       if(r==1) return dp[n][r] = n;
       if(dp[n][r]) return dp[n][r];
       return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}*/

int main(){
  int n, k, r, s, p;
  string t;
  cin >> n >> k >> r >> s >> p >> t;
  LL ans=0;
  vector<char> cnt(n);
  REP(i, k){
      cnt[i]=t[i];
  }
  FOR(i, k, n){
      if(t[i]==cnt[i-k]){
          cnt[i]='n';
      }else cnt[i]=t[i];
  }
  REP(i, n){
      if(cnt[i]=='r') ans+=p;
      else if(cnt[i]=='s') ans+=r;
      else if(cnt[i]=='p') ans+=s;
  }


  
  
  cout << ans << endl;

    
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define inv(n, a) for(int i = 0; i < n; i++) cin >> a[i]
#define MOD 1000000007
#define INF 1e7
#define LINF 1e15
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
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; }

// 'a' = 97 'z' = 122 => 'a' = 0 'z' = 25

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    inv(n, a); inv(n, b); inv(n, c);
    sort(a.begin(), a.end()); sort(c.begin(), c.end());
    ll ans = 0;
    rep(j, n){
        auto it_a = lower_bound(a.begin(), a.end(), b[j]);
        ll i = it_a - a.begin();
        auto it_c = upper_bound(c.begin(), c.end(), b[j]);
        ll k = c.end() - it_c;
        ans += i*k;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
int main(void) {
	int A,B,C,D;
	cin >> A >> B >> C >> D;

	const int lower = max(A,C);
	const int upper = min(B,D);

	cout << max(0,upper-lower) << endl;

	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
 
#include <bits/stdc++.h>
 
#define int ll
//#define double long double
#define endl '\n'
#define all(C) (C).begin(), (C).end()
#define rall(C) (C).rbegin(), (C).rend()
#define mp make_pair 
#define pb emplace_back
#define dbg(x) cerr << #x << " : " << x << endl
//#define PI 3.141592653589
 
using namespace std;
        
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair <int, int>;
using pld = pair <ld, ld>;
        
/* 
const ll MAX_MEM = 25e7;
char MEM[MAX_MEM];
ll MEM_POS = 0;
void* operator new(size_t x)
{
    auto ret = MEM + MEM_POS;
    MEM_POS += x;
    assert(MEM_POS < MAX_MEM);
    return ret;
}
void operator delete(void*)
{}
*/
        
template <class T>
istream& operator>> (istream &in, vector <T> &a)
{
    for (auto &i : a)
        in >> i;
    return in;
}
        
template <class T> 
ostream& operator<< (ostream &out, vector <T> a)
{
    for (auto &i : a)
        out << i << ' ';
    return out;
}
        
template <class T, class U>
istream& operator>> (istream &in, pair <T, U> &p)
{
    in >> p.first >> p.second;
    return in;
}
        
template <class T, class U>
ostream& operator<< (ostream &out, pair <T, U> p)
{
    out << p.first << " " << p.second << " ";
    return out;
}
        
inline void Start()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //freopen("lol.in", "r", stdin);
    //freopen("lol.out", "w", stdout);
}

signed main()
{
    Start();
    int n, q;
    cin >> n >> q;
    vector <int> a(q);
    cin >> a;
    a.insert(a.begin(), n);
    stack <int> st;
    for (int i = 0; i < q + 1; ++i)
    {
        while (!st.empty() && st.top() >= a[i])
            st.pop();
        st.emplace(a[i]);
    }
    vector <int> b;
    while (!st.empty())
        b.pb(st.top()), st.pop();
    reverse(all(b));
    q = b.size();
    vector <int> t(q);
    t[q - 1] = 1;
    a.assign(n, 0);
    for (int i = q - 1; i >= 0; --i)
    {
        int x = b[i];
        while (true)
        {
            int pos = partition_point(all(b), [&] (int y) {return (x == b[i] ? y < x : (y <= x));}) - b.begin();
            if (pos == 0)
                break;
            --pos;
            t[pos] += t[i] * (x / b[pos]);
            x %= b[pos];
        }
        a[0] += t[i];
        a[x] -= t[i];
    }
    for (int i = 1; i < n; ++i)
        a[i] += a[i - 1];
    for (auto &i : a)
        cout << i << endl;
    return 0;
}
 


Measured memory_bytes: 5104
#include <stdio.h>
//sukhan
 int main(void){
 int a, b, c;

 scanf("%d%d%d", &a, &b, &c);

 int ispoor = 0;
 if (a == b && b != c) ispoor = 1;
 if (b == c && c != a) ispoor = 1;
 if (c == a && a != b) ispoor = 1;

 if (ispoor) {
 puts("Yes");
 } else {
 puts("No");
 }

 return 0;
}

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

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    int ans = 0;
    for (int i = 0; i + 3 <= n; i++) {
        if (s.substr(i, 3) == "ABC") ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import math
n,x = map(int,input().split())
X = list(map(int,input().split()))
diff = []
for i in range(n):
	diff.append(abs(X[i]-x))
res = diff[0]
for i in range(1,n):
	res = math.gcd(res, diff[i])
print(res)




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

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

#define REPS(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (int i = (a); i >= n; --i)
#define DEP(i, n) DEPS(i, n, 0)

#define vint(v, n) vector<int> v(n); REP(i,n) cin >> v[i];
#define vvint(v, w, n) vector<int> v(n); vector<int> w(n); REP(i,n) cin >> v[i] >> w[i];
#define vlint(v, n) vector<ll int> v(n); REP(i,n) cin >> v[i];
#define vdouble(v, n) vector<double> v(n); REP(i,n) cin >> v[i];
#define vvdoube(v, n1, n2) vector<vector<double> > v(n1, vector<double>(n2, 0)); REP(i,n1) REP(j,n1) cin >> v[i][j];
#define string(x) string x; cin >> x;
#define vstring(v, n) vector<string> v(n); REP(i,n){string a; std::cin >> a; v.push_back(a); }

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).begin(), (v).end(), std::greater<int>()
#define len(v) (v).length()
#define FIND(s, n) (s.find(n) != s.end())
#define SORT(a) sort(all(a))

static const string abet("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
static const long long int MOD = 1000000007;
static const double PI=3.1415926535897932;
static const int INF = 0x3f3f3f3f;
static const int INFTY = (1 << 29);
static const long long LINFTY = (1LL << 32);

static const int dy4[]={0, 0, 1, -1};
static const int dx4[]={1, -1, 0, 0};
static const int dx8[] = {1, 1, 1, 0, 0, -1, -1, -1};
static const int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
  int R1, R2;
  cin >> R1 >> R2;

  double R3 = R1*R2*1.0/(R1+R2);
  printf("%.6lf", R3);
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	char a, b, c = 0, d, e;
	cin >> a >> b;
	if (a == b) {
		cout << '=' << endl;
	}
	else if (a > b) {
		cout << '>' << endl;
	}
	else {
		cout << '<' << endl;
	}
	cin >> e;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
int dy[]={1,-1,0,0};
int dx[]={0,0,1,-1};


int main(){
    ll N;
    cin>>N;
    for(int h=1;h<=3500;h++){
        for(int n=h;n<=3500;n++){
            double w=(double)N*h*n/(4.0*h*n-N*(h+n));
            if(w==ceil(w)&&w>0&&w<=3500){
                cout<<h<<" "<<n<<" "<<w<<endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
	int n,i,j;
	
	scanf("%d",&n);
	char s[n+1],a[n+1],b[2*n];
	scanf("%s%s",s,a);
	for( i=0,j=0;i<n;i++,j++)
	{
		b[j]=s[i];
		j++;
		b[j]=a[i];
	}
	for(i=0;i<(2*n);i++)
	printf("%c",b[i]);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;
const int INFTY = (1 << 21); // 2097152
// const ll INFTY = (1LL << 60);

#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)

class Point{
public:
	double x, y;
	Point(double x=0, double y=0):x(x), y(y){}

	Point operator + (Point p){ return Point(x + p.x, y + p.y); }
	Point operator - (Point p){ return Point(x - p.x, y - p.y); }
	Point operator * (double a){ return Point(a * x, a * y); }
	Point operator / (double a){ return Point(x / a, y / a); }

	double abs() { return sqrt(norm()); }
	double norm() { return x * x + y * y;}
	bool operator < (const Point &p) const {
		// first x, second y
		return x != p.x ? x < p.x : y < p.y;
	}

	bool operator == (const Point &p) const{
		return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
	}
};

typedef Point Vector;

struct Segment{
public:
	Point p1, p2;
	Segment(Point p1, Point p2){
		this->p1 = p1;
		this->p2 = p2;
	}
};

double dot(Vector a, Vector b){
	//|a||b|cos(theta)
	return a.x * b.x + a.y * b.y;
}
double cross(Vector a, Vector b){
	//|a||b|cos(theta)
	return a.x * b.y - a.y * b.x;
}

// Orthogonal
bool isOrthogonal(Vector a, Vector b){
	return equals(dot(a, b), 0.0);
}
bool isOrthogonal(Point a1, Point a2, Point b1, Point b2){
	return isOrthogonal(a1 - a2, b1- b2);
}

// Orthogonal
bool isParallel(Vector a, Vector b){
	return equals(cross(a, b), 0.0);
}
bool isParallel(Point a1, Point a2, Point b1, Point b2){
	return isParallel(a1 - a2, b1- b2);
}

// ???p????????????s???????????????????????????
Point project(Segment s, Point p){
	// ??\??????????????????
	// t = |hypo|cos??
	// cos?? = dot(hypo,base)/|hypo||base|
	// project = s.p1 + base/|base| * t
	Vector base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / base.norm();
	return s.p1 + base * r;
}

int Q;
Point p1, p2;

int main() {
	cin >> p1.x >> p1.y >> p2.x >> p2.y;
	cin >> Q;

	rep(i, Q){
		Point pp;
		cin >> pp.x >> pp.y;
		Point pr = project(Segment(p1, p2), pp);
		fprintf(stdout, "%.10f %.10f\n", pr.x, pr.y);
	}
}

Measured memory_bytes: 3216
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#include <stack>

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

string S;
ll N,K,A,B;
ll H[100001];
ll ans;
vector<ll> E[100001];
bool found = false;
ll V[1000001];
 


int main(){
    cin >> N;
    K = 2*sqrt(sqrt((N+4)/5));
    for(ll i=1;i<=K;i++){
        for(ll j=-K;j<=K;j++){
            if(i*i*i*i*i-j*j*j*j*j==N){
                found = true;
                A = i;
                B = j;
                break;
            }
            
        }
        if(found){
            break;
        }
    }
    cout << A << " " << B << endl;
    
}


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

const int N=1000000005;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--)
    {
        int n;
        cin>>n;
        if(n%1000==0)
            cout<<"0"<<endl;
        else
            cout<<1000-n%1000<<endl;
    }
    return 0;
}


Measured memory_bytes: 3644
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

init_score = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] > a[j]:
            init_score += 1

ans = 0

second_score = 0
for i in range(n):
    for j in range(n):
        if a[i] > a[j]:
            second_score += 1

ans += (init_score * k) % mod
ans += (second_score * (k - 1)  * k // 2) % mod
print(ans % mod)


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

using namespace std;

int main(){
	int n;

	int arr[9] = {111,222,333,444,555,666,777,888,999};

	cin >> n;

	int i = 0;

	while(i < 9){
		if(n <= arr[i]){
			cout << arr[i] << endl;
			break;
		} else
			i++;
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

const long long INF = 100000000;
const long long MOD = 1000000007;

std::vector<bool> IsPrime;

void sieve(size_t max)
{
  if (max + 1 > IsPrime.size())
  {                                // resizeで要素数が減らないように
    IsPrime.resize(max + 1, true); // IsPrimeに必要な要素数を確保
  }
  IsPrime[0] = false; // 0は素数ではない
  IsPrime[1] = false; // 1は素数ではない

  for (size_t i = 2; i * i <= max; ++i)     // 0からsqrt(max)まで調べる
    if (IsPrime[i])                         // iが素数ならば
      for (size_t j = 2; i * j <= max; ++j) // (max以下の)iの倍数は
        IsPrime[i * j] = false;             // 素数ではない
}

class Pointer{
public:
  long long p;
  long long w;
};

int main()
{
  long long N, K;
  cin >> N >> K;
  vector<long long> l;
  for (int i = 0; i < N;i++){
    long long a;
    cin >> a;
    l.push_back(a);
  }
  sort(l.begin(), l.end(),greater<long long>());

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


Measured memory_bytes: 256
#include <iostream>
#include <valarray>
//#include "../cxx-prettyprint/prettyprint.hpp"

int main() {
    int N;
    std::cin >> N;

    std::valarray<int> A(N);
    std::valarray<long> B(N);
    for (int i = 0; i < N; i ++) {
        std::cin >> A[i];
        B[i] = A[i] - (i + 1);
    }

    std::sort(std::begin(B), std::end(B));
    long b = B[N / 2];
    std::cout << abs(B - b).sum() << std::endl;
}


Measured memory_bytes: 2560
// https://atcoder.jp/contests/abc113/tasks/abc113_a
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x, y;
    cin >> x >> y;
    cout << x + y / 2 << endl;

    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

# In[2]:


L,R,D = input().split()


# In[3]:


count= 0


# In[4]:


for i in range(int(L),int(R)+1):
    if i % int(D) ==0:
        count+=1
print(count)


# In[ ]:






Measured memory_bytes: 9020
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i=0;
		while(true){
			i++;
			int k = Integer.parseInt(br.readLine());
			if(k == 0){break;}
			System.out.println("Case "+i+": "+k);
		}
	}

}

Measured memory_bytes: 31604
program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;
var
  l,r,a,h,w,i,j,count,x,y,sw,m,n,b,c,soeji,sum,max,k,t:Integer;
  //l:array of Integer;
  s,s123,s1,s2,s3:string;
  tf:Boolean;
  //nyu:TStringList;
begin
  try
    { TODO -oUser -cConsole Main : ここにコードを記述してください }
    Readln(n);
    Readln(a);

    Writeln(n*n-a);
    Readln;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.


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

using namespace std;

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

#define F first
#define S second
#define PB push_back
#define MK make_pair
#define REP(i, a, b) for (int i=a; i < b; i++)


bool sort_by(vi c, vi d){
	return c.S < d.S;
}

int main() {
	int N, M;
	cin >> N;
	int problems[N];
	int all = 0;
	REP(i, 0, N){
		cin >> problems[i];
		all += problems[i];
	}
	cin >> M;
	int p, x;
	REP(i, 0, M){
		cin >> p >> x;
		cout << all - problems[p-1] + x << endl;
	}
	

}


Measured memory_bytes: 256
from decimal import Decimal, ROUND_UP

l = [int(input()) for i in range(5)]
rl = []

for i in range(len(l)):
    rl.append(int(Decimal(str(l[i])).quantize(Decimal('1E1'), rounding=ROUND_UP)))

ans = []
for j in range(len(rl)):
    num = sum(rl) - rl[j] + l[j]
    ans.append(num)

print(min(ans))

Measured memory_bytes: 9960
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) {if (a > b) { a = b; return true; } return false; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    ll a, b, c, d;
    cin>>a>>b>>c>>d;

    ll cn = b / c - (a - 1) / c;
    ll dn = b / d - (a - 1) / d;
    ll g = __gcd(c, d);
    ll l = c / g * d;
    ll ln = b / l - (a - 1) / l;
    cout<<(b - a + 1) - (cn + dn - ln)<<endl;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int h = sc.nextInt();
		int w = sc.nextInt();
		System.out.println((H-h)*(W-w));
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<string> S(N);
  int64_t M = 0, A = 0, R = 0, C = 0, H = 0;
  for (int i = 0; i < N; i++) {
    cin >> S.at(i);
    if (S.at(i).at(0) =='M') {
      M++;
    }
    if (S.at(i).at(0) =='A') {
      A++;
    }
    if (S.at(i).at(0) =='R') {
      R++;
    }
    if (S.at(i).at(0) =='C') {
      C++;
    }
    if (S.at(i).at(0) =='H') {
      H++;
    }    
  }
  int64_t ans = 0;
  ans += (M * A * R);
  ans += (M * A * C);
  ans += (M * A * H);
  ans += (M * R * C);
  ans += (M * R * H);
  ans += (M * C * H);
  ans += (A * R * C);
  ans += (A * R * H);
  ans += (A * C * H);
  ans += (R * C * H);
  cout << ans << endl;
}

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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
struct UnionFind {
	std::vector<int> data;
	UnionFind (int size) : data(size, -1) {}
	bool unite(int x, int y) {
		x = root(x);
		y = root(y);
		if (x != y) {
			if (data[y] < data[x]) std::swap(x, y);
			data[x] += data[y];
			data[y] = x;
		}
		return x != y;
	}
	bool same(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
	bool connected() { return size(0) == (int) data.size(); }
};


int main() {
	int n = ri();
	int m = ri();
	int k = ri();
	UnionFind uni(n);
	std::vector<int> friends[n];
	for (int i = 0; i < m; i++) {
		int a = ri() - 1;
		int b = ri() - 1;
		uni.unite(a, b);
		friends[a].push_back(b);
		friends[b].push_back(a);
	}
	std::vector<int> block[n];
	for (int i = 0; i < k; i++) {
		int a = ri() - 1;
		int b = ri() - 1;
		block[a].push_back(b);
		block[b].push_back(a);
	}
	for (int i = 0; i < n; i++) {
		if (i) printf(" ");
		int res = uni.size(i) - 1;
		for (auto j : block[i]) if (uni.same(i, j)) res--;
		for (auto j : friends[i]) if (uni.same(i, j)) res--;
		printf("%d", res);
	}
	puts("");
	return 0;
}


Measured memory_bytes: 12152
import java.math.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			int a = cin.nextInt();
			int b = cin.nextInt();
			if(b>=a)
				System.out.println(a);
			else 
				System.out.println(a-1);
		}
	}
}


Measured memory_bytes: 21844
N = int(input())
t = [0]
x = [0]
y = [0]
for _ in range(N):
    T, X, Y = map(int, input().split())
    t.append(T)
    x.append(X)
    y.append(Y)
    
bool = True
for i in range(N):
    dt = t[i+1]-t[i]
    dist = abs(x[i+1]-x[i])+abs(y[i+1]-y[i])
    if dt < dist:
        bool = False
    elif dist%2 != dt%2:
        bool = False
        
if bool == True:
    print('Yes')
else:
    print('No')

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

int main(){
    int N;
    int d[100];
    int cnt =0;
    int ind[101] = {0};
    cin >> N;
    for (int i = 0; i < N ;i++ ) cin >> d[i];

    for (int i = 0; i < N ;i++){
        ind[d[i]]++;
    }

    for (int i = 1; i <= 100 ;i++){
        if(ind[i] != 0){
            cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

int main()
{
	ll H, W;
	cin >> H >> W;

	if (H == 1 || W == 1)
	{
		cout << 1 << endl;
		return 0;
	}

	ll count = H * (W / 2);
	if (W % 2 == 1)
	{
		count += H / 2;
		if (H % 2 == 1)
		{
			count += 1;
		}
	}

	cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;


template <class K, class V>
struct RadixHeapULL {
    static constexpr int bit_length = sizeof(K)*8;
    K last;
    size_t sz, cnt;
    RadixHeapULL() : last(0), sz(0), cnt(0) {}
    array<vector<pair<K, V>>, bit_length> v;
    static inline int bsr(int x){
        return x ? bit_length-__builtin_clzll(x) : 0;
    }
    static inline int bsr(ll x){
        return x ? bit_length-__builtin_clzll(x) : 0;
    }
    void emplace(K x, V val){
        sz++;
        v[bsr(x^last)].emplace_back(x, val);
    }

    void pull() {
        if(cnt < v[0].size()) return;;
        int i = 1;
        while(v[i].empty()) i++;
        last = min_element(v[i].begin(),v[i].end())->first;
        for (auto &&x : v[i]) v[bsr(x.first ^ last)].push_back(x);
        v[i].clear();
    }

    pair<K, V> top() {
        pull();
        return v[0][cnt];
    }

    void pop() {
        pull();
        sz--;
        cnt++;
    }

    size_t size() const { return sz; }
    bool empty() const { return !sz; }
};
struct heap_element {
    unsigned long long key;
    int val;
    heap_element(unsigned long long key, int val) : key(key), val(val) {};
    heap_element() : key(0), val(0) {};
};

template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;

int main() {
    int n, m, l;
    cin >> n >> m >> l;
    using P = pair<int, int>;
    vector<vector<P>> G(n);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--; b--;
        if(c <= l){
            G[a].emplace_back(b, c);
            G[b].emplace_back(a, c);
        }
    }
    constexpr ll max = ((ll)INF<int> << 31) + INF<int>;
    vector<vector<ll>> ans(n, vector<ll>(n, max));
    for (int i = 0; i < n; ++i) {
        ans[i][i] = 0;
        RadixHeapULL<ll, int> Q;
        Q.emplace(0, i);
        ll mask = (1LL << 31)-1;
        while(!Q.empty()){
            ll p; int x;
            tie(p, x) = Q.top(); Q.pop();
            if(ans[i][x] < p) continue;
            for (auto &&e : G[x]) {
                auto cost2 = p + e.second;
                if((cost2 & mask) > l){
                    cost2 = (((p >> 31) + 1) << 31) + e.second;
                }
                if(ans[i][e.first] <= cost2) continue;
                ans[i][e.first] = cost2;
                Q.emplace(ans[i][e.first], e.first);
            }
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        cout << ((ans[s][t] >> 31) == (INF<int>) ? -1 : ans[s][t] >> 31) << "\n";
    }
    return 0;
}

Measured memory_bytes: 4772
/* インクルードなど */
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    string s, t;
    int tmp;
    cin >> s >> t;
    int ans = t.length();
    for (int i = 0; i <= s.length() - t.length(); i++) {
        tmp = 0;
        for (int j = 0; j < t.length(); j++) {
            if (t[j] != s[i+j]) tmp++;
        }
        ans = min(tmp, ans);
    }
    cout << ans << endl;
}

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

int main(){
  int N, K, ret;
  int l[55];
  cin >> N >> K;
  for(int i = 0; i<N; i++)cin >> l[i];
  sort(l,l+N,greater<int>());
  for(int i = 0; i< K; i++)ret += l[i];
  cout<< ret << endl;
}


Measured memory_bytes: 256
/*
    ->->->->-> Vora Mahammasasim <-<-<-<-<-
*/
#include<bits/stdc++.h>
#include<stdio.h>
#define Quick std :: ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define pb emplace_back
#define Mod 1000000007
#define all(a) a.begin(),a.end()
#define ps(a) partial_sum(all(a),a.begin())
using namespace std;

signed main(){

    Quick;
    int n,x,t;
    cin>>n>>x>>t;
    cout<<(n%x == 0 ? n/x : n/x + 1) * t<<'\n';
}



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

int main(){
  while(true){
    int n,x;
    cin>>n>>x;
    if (n == 0) break;
    int an=0;
    for(int i=1;i<=n-2;i++) {
      for(int j=i+1;j<=n-1;j++) {
        int k = x-i-j;
        if (j+1 <= k && k <= n) an++;
      }
    }
    cout<<an<<endl;
  }
}


Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
typedef long long ll;
typedef long double  ld;
#define pii pair<ll,ll> 
#define vi vector< ll > 
#define vvi vector< vi > 
#define vpi vector< pii > 
#define vvpi vector< vpi > 
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define test(t) ll t;cin>>t;while(t--)
#define mem(a,b) memset(a,b,sizeof(a))
#define inn freopen("input.txt", "r", stdin)
#define outt freopen("output.txt", "w", stdout)
#define all(arr) arr.begin(),arr.end()
#define fr(i,n) for(ll i=0;i<(n);++i)
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define remin(a,b) (a=min((a),(b)))
#define remax(a,b) (a=max((a),(b)))
ll power(ll x,ll y){ll res = 1;while(y){if(y&1) res = (res*x)%mod;y=y/2,x=(x*x)%mod;}return res%mod;}
ll n;
string s;
ll dp[200001][2];
ll func(ll index,ll open,ll x)
{
    if(index==2*n)
    {
        return x==0;
    }
    ll &ret =dp[index][open];
    if(ret!=-1)
        return ret;
    ret = 0;
    if(s[index]=='B')
    {
        if(open%2)
            ret = func(index+1,!open,x-1)*x;
        else
            ret = func(index+1,!open,x+1);
    }
    else
    {
        if(open%2==0)
            ret = func(index+1,!open,x-1)*x;
        else
            ret = func(index+1,!open,x+1);    
    }
    return ret%mod;

}
signed main()
{
    fast;
    cin>>n;
    ll x = 1;
    ll i;
    for(i=2;i<=n;i++)
        x = (x*i)%mod;
    cin>>s;
    mem(dp,-1);
    cout<<(func(0,0,0)*x)%mod;
}

Measured memory_bytes: 10004
//$g++ -std=c++11 Template.cpp 

//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iomanip>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

priority_queue<int> q_descending;
priority_queue<int, vector<int>, greater<int> > q_ascending;

int a[100001];
int b[100001];
int c[100001];
int dp[100001][5];

void PRINT(int n, int m){
  
  cout << "----" << endl;
  REP(i, n) {
    REP(j, m) {cout << dp[i][j] << " ";}
    cout << "\n";
  }
  cout << "----" << endl;
}

int
main(void){  
  ios_base::sync_with_stdio(false);

  int n;  
  cin >> n;

  REP(i, n) cin >> a[i] >> b[i] >> c[i];

  REP(i, n) REP(j, 3) dp[i][j] = 0;

  dp[0][0] = a[0];
  dp[0][1] = b[0];
  dp[0][2] = c[0];

  //PRINT(n, 3);
  
  // j = 0,1,2 -> a, b, c
  REP(i, n){
    REP(j, 3){
      /*
      if(j == 0) dp[i+1][j] = max(max(dp[i][1]+a[i+1], dp[i][1]+c[i+1]), max(dp[i][2]+a[i+1], dp[i][2]+b[i+1]));
      else if(j == 1) dp[i+1][j] = max(max(dp[i][0]+b[i+1], dp[i][0]+c[i+1]), max(dp[i][2]+a[i+1], dp[i][2]+b[i+1]));
      else dp[i+1][j] = max(max(dp[i][0]+b[i+1], dp[i][0]+c[i+1]), max(dp[i][1]+a[i+1], dp[i][1]+c[i+1]));
      */

      if(j == 0) dp[i+1][j] = max(dp[i][1], dp[i][2]) + a[i+1];
      else if(j == 1) dp[i+1][j] = max(dp[i][0], dp[i][2]) + b[i+1];
      else dp[i+1][j] = max(dp[i][0], dp[i][1]) + c[i+1];
    }
    //PRINT(n, 3);    
  }
  //dp[i+k] = min(dp[i+k], dp[i+j]+abs(h[i+j]-h[i+k]));      
  
  cout << max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2])) << endl;
  
  return 0;
}


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

int main(){
  int n,d,count=0;
  cin>>n>>d;
  int num[n][d],base[126];
  for(int i=1;i<127;i++){
    base[i-1]=i*i;
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<d;j++){
    cin>>num[i][j];
    }
  }
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      int sum=0;
      for(int k=0;k<d;k++){
        sum+=(num[i][k]-num[j][k])*(num[i][k]-num[j][k]);
      }
      for(int j=0;j<126;j++){
        if(sum==base[j]) count++;
        else if(sum<base[j]) break;
      }
    }
  }
  cout<<count<<endl;
}

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

 double pi=3.14159265358979323846;

 
int main(){
    int t=1;
    //cin>>t;
    while(t--){
        int n;
        cin>>n;
        int r=n%10;
        if(r==2 || r==4||  r==5 || r==7 || r==9) cout<<"hon"<<endl;
        else if(r==3) cout<<"bon"<<endl;
        else cout<<"pon"<<endl;
    }


    
}

Measured memory_bytes: 3596
#include <cstdio>
#include <iostream>

using namespace std;

void call(int n) {
  for (int i = 1; i <= n; i++) {
    int x = i;

    if (x % 3 == 0) {
      cout << " " << i;
    } else {
      while (x != 0) {
        if (x % 10 == 3) {
          cout << " " << i;
          break;
        }

        x /= 10;
      }
    }
  }

  cout << endl;
}

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

  call(n);

  return 0;
}


Measured memory_bytes: 3108
N=int(input())
D=list(map(int, input().split()))
if D[0]!=0:
    print(0)
    exit()
if 0 in D[1:]:
    print(0)
    exit()
D=sorted(D)
p=998244353
edge=[0]*(N)

ans=1
for i in range(N):
    d=D[i]
    if i==0:
        if d==0:
            edge[0]+=1
            continue
        else:
            print(0)
            exit()
    if d==0:
        print(0)
        exit()
    if edge[d-1]==0:
        print(0)
        exit()
    else:
        edge[d]+=1
        ans*=edge[d-1]
        ans%=p

print(ans%p)


Measured memory_bytes: 87012
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
n_max=2*(10**6+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

def f(x,y):
  return comb(x+y+2,y+1)-1

print((f(r2,c2)-f(r2,c1-1)-f(r1-1,c2)+f(r1-1,c1-1))%mod)


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

using namespace std;
using ll = long long;
    
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

    
int main() {
    int n,k;
    cin >> n >> k;
    
    int l[k], r[k];
    vector<mint> dp(n+1);
    vector<mint> dp_sum(n+1);

    for(int i=0; i<k; i++){
        cin >> l[i] >> r[i];
    }

    dp[1] = 1;
    dp_sum[1] = 1;
    for(int i=2; i<=n; i++){
        for(int j=0; j<k; j++){
            int li = i - l[j];
            int ri = i - r[j];
            if(li < 0) continue;
            ri = max(ri, 1);
            dp[i] += dp_sum[li] - dp_sum[ri-1];
        }
        dp_sum[i] = dp[i] + dp_sum[i-1];
    }
    
    cout << dp[n] << endl;
}

Measured memory_bytes: 6332