akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

#define LEN 16010
#define SIZE 8000

bool in(int x)
{
    return 0 <= x && x < LEN;
}

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

    string s;
    cin >> s;
    int x, y;
    cin >> x >> y;
    x += SIZE, y += SIZE;
    int cnt = 0;
    vector<int> vx, vy;
    bool f = true;
    rep(i, s.size())
    {
        if (s[i] == 'F')
            cnt++;
        else
        {
            if (f)
                vx.push_back(cnt), f = false;
            else
                vy.push_back(cnt), f = true;
            cnt = 0;
        }
    }
    if (f)
        vx.push_back(cnt);
    else
        vy.push_back(cnt);
    bool dpx[LEN], dpy[LEN];
    rep(i, LEN) dpx[i] = dpy[i] = false;
    dpx[vx[0] + SIZE] = dpy[SIZE] = true;
    for (int i = 1; i < vx.size(); i++)
    {
        bool nxt[LEN];
        rep(j, LEN) nxt[j] = false;
        int len = vx[i];
        rep(j, LEN)
        {
            if (in(j - len))
                nxt[j] |= dpx[j - len];
            if (in(j + len))
                nxt[j] |= dpx[j + len];
        }
        rep(j, LEN) dpx[j] = nxt[j];
    }
    for (int i = 0; i < vy.size(); i++)
    {
        bool nxt[LEN];
        rep(j, LEN) nxt[j] = false;
        int len = vy[i];
        rep(j, LEN)
        {
            if (in(j - len))
                nxt[j] |= dpy[j - len];
            if (in(j + len))
                nxt[j] |= dpy[j + len];
        }
        rep(j, LEN) dpy[j] = nxt[j];
    }
    bool ans = dpx[x] && dpy[y];
    cout << (ans ? "Yes" : "No") << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long int
#define N 200000
#define f(i, a, b) for (ll i = (ll)a; i <= (ll)b; i++)
#define rf(i, a, b) for (ll i = (ll)a; i >= (ll)b; i--)
#define po pop_back
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define debug(x) cout << #x << " = " << x << endl
#define ub upper_bound
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define all(x) x.begin(), x.end()
#define PI 3.14159
#define cot cout.tie(0)
#define endl "\n"
using namespace std;
/**
        * @author :: Sawlani
        *
        */

const ll M = 1e9+7;
ll a[N+1]={0};
ll b[N+1];
int main()
{
        #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        #endif
        ll n,k;
        cin >> n >> k;

       
       f(i,1,n)
       {
          a[i]=i+a[i-1];
       }
       b[n]=n;
       rf(j,n-1,0)
       {
           b[j]=j+b[j+1];
       }
       
       ll ans=0;
       f(i,k,n+1)
       {
           ans=(ans%M+(b[n-i+1]%M-a[i-1]%M+M)%M)%M;
           ans=(ans+1)%M;
       }

       cout << ans;
}

Measured memory_bytes: 6764
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,w,t,r;
  a=0;w=0;t=0;r=0;
  cin >> n;
  vector<string>s(n);
  for(int i=0;i<n;i++){
    cin >> s.at(i);
  	if(s.at(i)=="AC"){
    	a++;
  	}else if(s.at(i)=="WA"){
    	w++;
  	}else if(s.at(i)=="TLE"){
    	t++;
  	}else{
    	r++;
  	}
  }
  cout << "AC x " << a << endl;
  cout << "WA x " << w << endl;
  cout << "TLE x " << t << endl;
  cout << "RE x " << r << endl;
}


Measured memory_bytes: 6400
main = do
  [r, d, x] <- map read . words <$> getLine
  putStrLn . unlines $ map show $ func 0 r d x

func :: Int -> Int -> Int -> Int -> [Int]
func 10 r d x = []
func n r d x = (r * x - d) : func (n + 1) r d (r * x - d)

Measured memory_bytes: 508
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int c[3][3];
  rep (i, 3) rep (j, 3) cin >> c[i][j];

  rep (a1, 100) {
    int b1 = c[0][0] - a1;
    int b2 = c[0][1] - a1;
    int b3 = c[0][2] - a1;
    int a2 = c[1][0] - b1;
    int a3 = c[2][0] - b1;
    if (a2 + b2 == c[1][1] && a2 + b3 == c[1][2] && a3 + b2 == c[2][1] && a3 + b3 == c[2][2]) {
      Yes;
      return 0;
    }
  }
  No;


  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define si(v) int(v.size())
#define len(v) int(v.length())
#define lob(v,n) lower_bound(all(v),n)
#define lobi(v,n) lower_bound(all(v),n) - v.begin()
#define upb(v,n) upper_bound(all(v),n)
#define upbi(v,n) upper_bound(all(v),n) - v.begin()
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vs = vector<string>;
using vc = vector<char>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vvp = vector<vector<pair<int,int>>>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;
template<typename T> bool chmax(T &a, T b) {if(a < b) {a = b;return 1;}return 0;}
template<typename T> bool chmin(T &a, T b) {if(a > b) {a = b;return 1;}return 0;}




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

    int H,W;
    cin >> H >> W;
    
    ve<ve<char>> G(H,ve<char>(W));
    rep(i,H) rep(j,W) cin >> G[i][j];
    
    int ans = 0;
    vi dh = {-1,1,0,0};
    vi dw = {0,0,-1,1};
    
    rep(si,H) rep(sj,W){
        
        if(G[si][sj] == '#') continue;
        
        vvi f(H,vi(W,-1));
        f[si][sj] = 0;
        queue<pii> q;
        q.push({si,sj});
        
        while (!q.empty()) {
            pii aa = q.front();
            q.pop();
            
            int nh = aa.fi, nw = aa.se;
            
            rep(k,4){
                nh = aa.fi + dh[k];
                nw = aa.se + dw[k];
                
                if(nh >= 0 && nh < H && nw >= 0 && nw < W){
                    if(G[nh][nw] == '.' && f[nh][nw] == -1){
                        f[nh][nw] = f[aa.fi][aa.se]+1;
                        q.push({nh,nw});
                        chmax(ans,f[nh][nw]);
                    }
                    
                }
            }
        }
        
        
    
    }
    
    
    cout << ans << endl;
    

    return 0;
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;
    c*=2;
    int ans=c*max(x,y);
    ans=min(ans,a*x+b*y);
    if(x-y>0)ans=min(ans,a*(x-y)+c*y);
    if(y-x>0)ans=min(ans,b*(y-x)+c*x);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 892
N, K = map(int, input().split())
a = [0] + list(map(int, input().split()))


if N == K:
	print(max(0, sum(a)))
else:
	imosW = [0]*(N+2)
	imosB = [0]*(N+2)
	for i in range(1, N+1):
		imosW[i] = max(0, a[i]) + imosW[i-1]
		imosB[i] = min(0, a[i]) + imosB[i-1]

	sepW = -1
	mini = int(1e18)
	for i in range(K, N + 1):
		if mini > imosW[i] - imosW[i-K]:
			mini = imosW[i] - imosW[i-K]
			sepW = (i-K, i)

	ansW = 0
	for i in range(1, N+1):
		if a[i] > 0 and not(i > sepW[0] and i <= sepW[1]):
			ansW += a[i]

	##
	sepB = -1
	maxm = int(-1e18)
	for i in range(K, N+1):
		if maxm < imosB[i] - imosB[i-K]:
			maxm = imosB[i] - imosB[i-K]
			sepB = (i-K, i)
	ansB = (imosB[sepB[1]] - imosB[sepB[0]]) + (imosW[sepB[1]] - imosW[sepB[0]])
	for i in range(1, N+1):
		if a[i] > 0 and not(i > sepB[0] and i <= sepB[1]):
			ansB += a[i]

	print(max(max(ansW, ansB), sum(a)))


Measured memory_bytes: 69228
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long> h(n+1);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    h[n]=10000000000;
    int ans = 0;
    int move = 0;
    for (int i = 0; i < n; i++) {
        if (h[i] >= h[i+1]) {
            move++;
        }
        else {
            ans = max(ans,move);
            move = 0;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>

int main(void)
{
	int n;
	int i, j, k;
	int a = 0, b = 0;
	int sum = 0;
	int min = 0;
	int count = 0;
	char str[10000][20];
	
	
	scanf("%d", &n);
	
	for(i = 0; i < n ; i++) {
		scanf("%s", str[i]);
		for(j = 0; j < strlen(str[i]) - 1; j++) {
			if( (str[i][j] == 'A') && (str[i][j + 1] == 'B') ) {
				sum++;
			}
		}
		if(str[i][strlen(str[i]) - 1] == 'A') {
			a++;
		}
		if(str[i][0] == 'B') {
			b++;
		}
		if( (str[i][strlen(str[i]) - 1] == 'A') && (str[i][0] == 'B') ) {
			count++;
		}
	}
	
	if(a > b) {
		min = b;
	} else {
		min = a;
	}
	if(a == count) {
		if(b == count) {
			if(min != 0) {
				min--;
			}
		}
	}
	
	printf("%d\n", sum + min);
	
	return 0;
}


Measured memory_bytes: 384
data =[
    [[0 for r in range(10)] for f in range(3)] for b in range(4)
]

#??\?????????????????????????????§????????????????????????????????????
count=int(input())
for c in range(count):
    b,f,r,v = [int(i) for i in input().split()]
    data[b-1][f-1][r-1] += v





for bi,b in enumerate(data):
    for f in b:
        for r in f:
            print(' {0}'.format(r),end='')

        print()
    if bi < 3:
        print('#'*20)

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

int main()
{
    int n;
    std::cin>>n;
    std::vector<int> v(n);
    int non_e = 0;
    int four = 0;
    for(int i=0;i<n;i++){
        std::cin>>v[i];
        if(v[i]%4==0)four++;
        if(v[i]%2==1)non_e++;
    }
    if(n%2==0)four--;
    std::cout<<(four+1>=non_e?"Yes":"No")<<std::endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
 
//#define DEBUG
 
bool is_integer( double x ){
  return std::floor(x)==x;
}

int main(void)
{
  ll N;
  int K;
  
  cin >> N >> K;
 
  double checkNum = (double)log((double)N)/(double)log((double)K);

  if( ceil(checkNum) == checkNum)
  {
    cout << checkNum +1;
  }
  else
  {
    cout << ceil(checkNum);
  }
  
  
  return 0;
} 

Measured memory_bytes: 512
/*http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A&lang=jp*/
#include<iostream>

using namespace std;

void println(int *a,int n){
    for(int i=0;i<n;i++){
        cout<<a[i];
        if(i<n-1){
            cout<<" ";
        }
    }
    cout<<endl;
}

int main()
{
    int n;
    int a[100];
    int count=0;
    bool flag= true;

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    while(flag == true){
        flag= false;
        for(int i=n-1;0<i;i--){
            if(a[i]<a[i-1]){
                int tmp=a[i];
                a[i]=a[i-1];
                a[i-1]=tmp;
                flag=true;
                count++;
            }
        }
    }
    println(a,n);
    cout<<count<<endl;
    return 0;
}

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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(lint i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(lint i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())

const int IINF = 1e9 + 10;
const lint LLINF = (lint)1e18 + 10;
const lint MOD = (lint)1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

struct city{
    lint p, y, id;

    bool operator<(const city & right) const {
        return y < right.y;
    }
};

int main(){
    lint n, m;
    cin >> n >> m;
    vector<city> c(m);
    rep(i, m){
        cin >> c[i].p >> c[i].y;
        c[i].id = i;
    }
    SORT(c);
    vector<lint> ans(m);
    vector<lint> tmp(n+1, 1);
    rep(i, m){
        city now = c[i];
        ans[now.id] = now.p * 1000000 + tmp[now.p];
        tmp[now.p]++;
    }
    rep(i, m){
        lint res = ans[i];
        res /= 1000000;
        lint cnt = 0;
        while(res > 0){
            cnt++;
            res /= 10;
        }
        rep(j, 6 - cnt){
            cout << 0;
        }
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 5376
import java.util.Scanner;

public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();

        if (x == 2 || y == 2) {
            System.out.println("No");
        } else {
            if (inGroup(x) && inGroup(y)){
                System.out.println("Yes");
            } else if (!inGroup(x) && !inGroup(y)){
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    private static boolean inGroup(int x){
        switch(x){
            case 4:
            case 6:
            case 9:
            case 11:
                return true;
            default:
                return false;
        }
    }
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// Use cout.flush() for interactive problems.
// Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
int main()
{
    she_told_me_dont_worry
    ll x;
    cin>>x;
    ll ans = (x/500)*1000;
    x %= 500;
    ans += (x/5)*5;
    cout<<ans<<endl;
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
#define all(x) x.begin(),x.end()
const int inf=0x3f3f3f3f;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	string S,T;
	bool flag=1;
	cin>>S>>T;
	for(int i=0;i<S.size();i++) flag&=(S[i]==T[i]);
	if(flag) cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
int main(){
    int n,x,y;
    scanf("%d%d",&x,&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&y);
        x-=y;
    }
    if (x<=0)printf("Yes");
    else printf("No");
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long mod = (int)(1e9+7), ans = 0;
		long[] arr = new long[n];
		for(int i = 0; i < n; ++i)
			arr[i] = sc.nextLong()%mod;
		long[] sum = new long[n];
		sum[n-1] = arr[n-1]%mod;

		for(int i = n-2; i >= 1; --i) {
			sum[i] = (sum[i+1]%mod+arr[i]%mod)%mod;
		}
		for(int i = 0; i <= n-2; ++i) {
			ans = (ans%mod + (arr[i]%mod * sum[i+1]%mod)%mod)%mod;
		}
		System.out.println(ans%mod);
	}
}

Measured memory_bytes: 51320
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200005,md=924844033;
int n,i,j,k,x,y,f[N],head[N],adj[N*2],nxt[N*2],size[N],ru[N],lmt,len,g[N*4],h[N*4],ome[N*4],rome[N*4],rt[N*4],inv[N*4],jc[N*4],rjc[N*4];
void dfs(int x,int dad)
{
	size[x]=1;
	for(int y=head[x];y;y=nxt[y])
		if(adj[y]!=dad)
		{
			dfs(adj[y],x);
			size[x]+=size[adj[y]];
			ru[size[adj[y]]]++;
		}
	ru[n-size[x]]++;
}
int pw(int a,int b)
{
	int rtn=1;
	while(b)
	{
		if(b&1)
			rtn=1ll*rtn*a%md;
		a=1ll*a*a%md;
		b>>=1;
	}
	return rtn;
}
void ntt(int a[N*4],bool t)
{
	for(int i=0;i<len;++i)
		if(i<rt[i])
			swap(a[i],a[rt[i]]);
	for(int l=2;l<=len;l<<=1)
	{
		int m=l>>1;
		for(int i=0;i<len;i+=l)
			for(int j=0;j<m;++j)
			{
				int w=1ll*(t?ome[len/l*j]:rome[len/l*j])*a[i+j+m]%md;
				a[i+j+m]=(a[i+j]-w+md)%md;
				a[i+j]=(a[i+j]+w)%md;
			}
	}
	if(!t)
		for(int i=0;i<len;++i)
			a[i]=1ll*a[i]*inv[len]%md;
}
int C(int n,int m)
{
	if(m>n)
		return 0;
	return 1ll*jc[n]*rjc[m]%md*rjc[n-m]%md;
}
int main()
{
	scanf("%d",&n);
	inv[1]=1;
	for(i=2;i<=n*4;++i)
		inv[i]=1ll*inv[md%i]*(md-md/i)%md;
	jc[0]=rjc[0]=1;
	for(i=1;i<=n*4;++i)
		jc[i]=1ll*jc[i-1]*i%md,rjc[i]=1ll*rjc[i-1]*inv[i]%md;
	for(i=1;i<n;++i)
	{
		scanf("%d%d",&j,&k);
		adj[i*2-1]=k;
		nxt[i*2-1]=head[j];
		head[j]=i*2-1;
		adj[i*2]=j;
		nxt[i*2]=head[k];
		head[k]=i*2;
	}
	dfs(1,-1);
	lmt=0;
	while((1<<lmt)<=2*n)
		++lmt;
	len=1<<lmt;
	for(i=0,x=pw(5,(md-1)/len),y=pw(x,md-2);i<len;++i)
	{
		if(i==0)
			ome[i]=rome[i]=1;
		else
			ome[i]=1ll*ome[i-1]*x%md,rome[i]=1ll*rome[i-1]*y%md;
		rt[i]=0;
		for(j=0;j<lmt;++j)
			if((1<<j)&i)
				rt[i]|=1<<(lmt-j-1);
	}
	for(i=1;i<=n;++i)
		g[i]=1ll*jc[i]*ru[i]%md;
	for(i=0;i<=n;++i)
		h[i]=rjc[n-i];
	ntt(g,true);
	ntt(h,true);
	for(i=0;i<len;++i)
		g[i]=1ll*g[i]*h[i]%md;
	ntt(g,false);
	for(i=1;i<=n;++i)
		f[i]=(1ll*C(n,i)*n%md-1ll*g[i+n]*rjc[i]%md+md)%md;
	for(i=1;i<=n;++i)
		printf("%d\n",f[i]);
	return 0;
}


Measured memory_bytes: 41344
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define all(c) begin(c), end(c)
#define range(i,a,b) for(int i = a; i < (int)(b); i++)
#define rep(i,b) range(i,0,b)
auto const inf = numeric_limits<int>::max() / 8;

using Capacity = int;

struct Dinic {
public:
    Dinic(int n_) : n(n_), g(n_) {}
    Capacity maximumFlow(int s_, int t_) {
        this->t = t_, this->s = s_;
        que.resize(n + 1);
        Capacity res = 0;
        while (levelize()) {
            prog.assign(n, 0);
            res += augment(s, inf);
        }
        return res;
    }
    void addEdge(int u, int v, Capacity c) {
        g[u].push_back({ u,v,c,0,(int)g[v].size() });
        g[v].push_back({ v,u,c,c,(int)g[u].size() - 1 });
    }

private:
    struct Edge {
        int src, dst;
        Capacity cap, flow;
        int rev;
    };
    vector<vector<Edge>> g;
    int n, s, t;
    vector<int> level, prog, que;
    bool levelize() {
        int l = 0, r = 0;
        level.assign(n, -1); 
        level[s] = 0; 
        que[r++] = s;
        while (l != r) {
            int v = que[l++]; 
            if (v == t) break;
            for (auto &e : g[v]) {
                int d = e.dst;
                if (level[d] == -1 && residue(e) != 0) {
                    level[d] = level[v] + 1;
                    que[r++] = d;
                }
            }
        }
        return level[t] != -1;
    }
    Capacity augment(int v, Capacity lim) {
        Capacity res = 0;
        if (v == t) return lim;
        for (int &i = prog[v]; i < (int)g[v].size(); i++) {
            if (lim == 0) break;
            auto &e = g[v][i];
            int d = e.dst;
            if (residue(e) == 0 || level[v] >= level[d]) continue;
            Capacity aug = augment(d, min(lim, residue(e)));
            e.flow += aug;
            reverse(e).flow -= aug;
            res += aug; 
            lim -= aug;
        }
        return res;
    }
    inline Capacity residue(const Edge& e) { return e.cap - e.flow; }
    inline Edge &reverse(const Edge &e) { return g[e.dst][e.rev]; }
};

int main() {
    int N, M;
    cin >> N >> M;
    Dinic g(N);
    rep(i, M) {
        int a, b, c;
        cin >> a >> b >> c;
        g.addEdge(a, b, c);
    }
    Dinic ek(g);
    cout << ek.maximumFlow(0, N - 1) << endl;
}

Measured memory_bytes: 3248
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <set>
using namespace std;

struct RollingHash {
	int n;
	const unsigned P = 1000000007U;
	vector<unsigned long long> pow, phash;
	template<typename T>
	RollingHash(const T& s, unsigned long long Q = 1) {
		n = s.size();
		pow.resize(n + 1); phash.resize(n + 1);
		pow[0] = Q; phash[0] = 0;
		for(int i = 0; i < n; i++) {
			pow[i + 1] = pow[i] * P;
			phash[i + 1] = s[i] + phash[i] * P;
		}
	}
	unsigned long long h(int i) const { return phash[i]; }
	unsigned long long h(int i, int j) const { return h(j) - h(i) * pow[j - i]; }
};

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

	int n, m;
	string s;
	cin >> n >> m >> s;

	RollingHash rh(s);

	set<unsigned long long> set;
	int l = 0, r = 0;
	for(int i = 0; i < m; i++) {
		string q;
		cin >> q;
		if(q == "L++") l++;
		if(q == "L--") l--;
		if(q == "R++") r++;
		if(q == "R--") r--;
		//cout << l + 1 << " " << r + 1 << " " << rh.h(l, r + 1) << endl;

		set.insert(rh.h(l, r + 1));
	}

	cout << set.size() << endl;
}

Measured memory_bytes: 21980
package main

import (
        "fmt"
        "sort"
)

func main() {
        var a [3]int
        fmt.Scanf("%d %d %d\n", &a[0], &a[1], &a[2])
        numeven := a[0]%2 + a[1]%2 + a[2]%2
        sort.Ints(a[:])

        cnt := 0
        if (numeven > 1 && a[2]%2 == 0) || (numeven <= 1 && a[2]%2 == 1) {
                for i := 0; i <= 1; i++ {
                        cnt += (a[2] - a[i]) / 2
                        a[i] = a[2] - (a[2]-a[i])%2
                }
        } else {
                for i := 0; i <= 1; i++ {
                        cnt += (a[2] - a[i] + 1) / 2
                        a[i] = a[2] + (a[2]-a[i])%2
                }
        }
        sort.Ints(a[:])

        if a[0] < a[2] {
                cnt++
        }
        fmt.Println(cnt)
}

Measured memory_bytes: 512
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>



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

using namespace std;
int a,b,c,d;
int k1,k2;
string s;

int main(){
  cin >> a >> b >> c;
  if(a+b>=c) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
int main() {
	int n;
	scanf("%d", &n);
	vector<int> X(n), Y(n), id(n);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &X[i], &Y[i]);
		id[i] = i;
	}
	vector<pair<int, pair<int, int>>> edges;
	sort(id.begin(), id.end(), [&](int a, int b) {
		return X[a] < X[b];
	});
	for (int i = 0; i + 1 < n; ++i) {
		edges.push_back({min(abs(X[id[i]] - X[id[i + 1]]), abs(Y[id[i]] - Y[id[i + 1]])), {id[i], id[i + 1]}});
	}
	sort(id.begin(), id.end(), [&](int a, int b) {
		return Y[a] < Y[b];
	});
	for (int i = 0; i + 1 < n; ++i) {
		edges.push_back({min(abs(X[id[i]] - X[id[i + 1]]), abs(Y[id[i]] - Y[id[i + 1]])), {id[i], id[i + 1]}});
	}
	sort(edges.begin(), edges.end());
	vector<int> par(n);
	iota(par.begin(), par.end(), 0);
	function<int(int)> getRoot = [&](int a) {
		if (par[a] == a) return a;
		return par[a] = getRoot(par[a]);
	};
	ll ans = 0;
	for (int i = 0; i < edges.size(); ++i) {
		int a, b;
		tie(a, b) = edges[i].second;
		int pa = getRoot(a), pb = getRoot(b);
		if (pa == pb) continue;
		par[pa] = pb;
		ans += edges[i].first;
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 6132
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000
int main(){
  unsigned short *A, *B;
  int C[VMAX+1];
  int n, i, j;

  scanf("%d", &n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);

  /* your code */
  for(i = 1 ;i<=n ;i++){
    scanf("%hd",&A[i]);
  }
  for(i = 0;i<=VMAX+1;i++){
    C[i] = 0;
  }
  for(j=1;j<=n;j++){
    C[A[j]] = C[A[j]]+1;
  }
  
  for(i = 1 ;i<=VMAX+1;i++){
    C[i] = C[i]+C[i-1];
  }
  for(j=n ;j>=1 ;j--){
    B[C[A[j]]] = A[j];
    C[A[j]] = C[A[j]]-1;
  }
  for(j = 1;j<n+1;j++){
    if(j ==n)
    printf("%d\n",B[j]);
    else printf("%d ",B[j]);
    }
  return 0;
}



Measured memory_bytes: 9624
import sys
import math
import copy
from typing import Tuple, List
input = sys.stdin.readline

def swap (A: List, i: int, j: int) -> None:
    temp = A [i]
    A [i] = A [j]
    A [j] = temp


def insertionSort(A, n, g):
    cnt = 0
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = v
    return cnt

def shellSort(A, n):
    cnt = 0
    g = []
    h = 1
    while h <= len(A):
        g.append(h)
        h = 3 * h + 1
    g.reverse()
    m = len(g)
    print(m)
    print(" ".join(map(str, g)))
    for i in range(m):
        cnt += insertionSort(A, n, g[i])
    print(cnt)


if __name__ == "__main__":
    n = int(input())
    A = []
    for i in range(n):
        A.append(int(input()))
    shellSort(A, len(A))
    for item in A:
        print(item)



Measured memory_bytes: 47116
object Main extends App{
  import scala.io.StdIn.readLine
  
  var str = readLine
  
  def readAGCT(x:String):String = {
  	if(x.isEmpty)return ""
    else if(x.startsWith("A")){return "A" + "" + readAGCT(x.tail)}
    else if(x.startsWith("C")){return "C" + "" + readAGCT(x.tail)}
    else if(x.startsWith("G")){return "G" + "" + readAGCT(x.tail)}
    else if(x.startsWith("T")){return "T" + "" + readAGCT(x.tail)}
    else return " " + readAGCT(x.tail)
  }
  if(readAGCT(str).split(" ").isEmpty)println("0")
  else println(readAGCT(str).split(" ").map(_.length).max.toString)
}

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

template <class T> using V = vector<T>;
template <class S, class T> using P = pair<S, T>;
template <class... T> using TP = tuple<T...>;

using ll = long long;
using db = double;
using ldb = long db;
using str = string;
using vll = V<ll>;
using vvll = V<V<ll>>;
using pll = P<ll,ll>;
using tpll = TP<ll,ll,ll>;
using vpll =V<pll>;
using vst = V<str>;
using vch = V<char>;

#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(b);i>(ll)(a);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) __lcm(a,b)
#define co(a) cout<<a<<endl
#define ci(a) cin>>a
#define pb(a) push_back(a)
#define pob pop_back()
#define mp make_pair
#define mt make_tuple
#define pbmp(a,b) push_back(mp(a,b))
#define subs(a,b) substr(a,b)
#define cfs(a) cout<<fixed<<setprecision(a)
#define INF 1e16
#define mod 1e9+7
//vvll v(n,vll(m)) n行m列
//A.erase(A.begin()+i) 配列Aのi番目を消せる
//std::binary_search(v.bgn,v.en,a);
//abs(a,b)   pow(a,n)  to_string  stoll
//auto Iter=lower_bound(v.bgn,v.en,a);
//lower//upper  co(*Iter)co(Iter-v.bgn);

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
void Comuse() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
#define comuse Comuse()
ll combi(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  ll n;
  cin>>n;
  vll v(n);
  FOR(i,0,n){
    cin>>v[i];
  }
  bool D=true;
  REV(v);
  FOR(i,1,n){
    if(v[i-1]+1<v[i]){
      D=false;
    }
    if(v[i-1]+1==v[i]){
      v[i]--;
    }
  }
  if(D){
    co("Yes");
  }
  else{
    co("No");
  }
}
      

Measured memory_bytes: 1024
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
////////////////////////////

int main(){fastio
    string s;cin>>s;
    rep(i,0,s.size()-1)cout<<"x";
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
#define gmul(x,y) x=mul(x,y)
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

map<string,int> m;

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	int cnt = 0;
	while(n--){
		string s;
		cin >> s;
		gmax(cnt,++m[s]);
	}
	for(auto p:m){
		if(p.second == cnt){
			cout << p.first << '\n';
		}
	}
}


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

int main()
{
    ll n,w;
    cin>>n>>w;
    ll dp[w+1]={};
    for(ll i=0;i<n;i++)
    {
        ll weight,value;
        cin>>weight>>value;
        for(ll j=w-weight;j>=0;j--)
        {
            dp[j+weight]=max(dp[j]+value,dp[j+weight]);
        }
    }
    ll ans=0;
    for(ll i=0;i<=w;i++)
        ans=max(ans,dp[i]);
    cout<<ans<<endl;
}

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

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define ALL(c) (c).begin(), (c).end()

template <typename T>
inline void assign_max(T& x, const T& value) {
    x = max(x, value);
}

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

    int R, C, K; cin >> R >> C >> K;
    map<pair<int, int>, int64_t> items;
    REP(i, K) {
        int r, c; int64_t v; cin >> r >> c >> v; --r; --c;
        items.insert({{r, c}, v});
    }

    vector dp(R+1, vector(C, vector(4, numeric_limits<int64_t>::min())));

    dp[0][0][0] = 0;
    REP(y, R+1) REP(x, C) REP(k, 4) {
        if (auto it = items.find({y, x}); k < 3 && it != items.end()) {
            // (y, x) にアイテムが存在し、拾うことが可能な場合
            int64_t value = it->second;
            if (y+1 < R+1)
                assign_max(dp[y+1][x][0], dp[y][x][k] + value);
            if (x+1 < C)
                assign_max(dp[y][x+1][k+1], dp[y][x][k] + value);
        }
        if (y+1 < R+1)
            assign_max(dp[y+1][x][0], dp[y][x][k]);
        if (x+1 < C)
            assign_max(dp[y][x+1][k], dp[y][x][k]);
    }

    cout << *max_element(ALL(dp[R][C-1])) << '\n';
}


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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1; 
    //cin >> t;
    for(int T = 0; T < t ; T++){
       ll n, ans = 0;
       cin >> n;
       ll a[n], b[n], cnt1[n] = {0}, cnt2[n] = {0};
       for(int i = 0; i < n; i++){
           cin >> a[i];
           b[i] = i - a[i];
           a[i] += i;
           if(b[i] >= 0)
                cnt1[b[i]]++;
           if(a[i] < n)
                cnt2[a[i]]++;
       }
       for(int i = 0; i < n; i++){
           ans += cnt1[i]*cnt2[i];
       }
       cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 9824
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        String[] s = S.split("");
        int min = 1000;
        for(int i=0; i<s.length-2; i++) {
            int n = Integer.parseInt(s[i]+s[i+1]+s[i+2]);
            if(sa(753, n) < min) min = sa(753, n);
        }
        System.out.println(min);
    }
    public static int sa(int a, int b) {
        if(a-b >= 0) return a-b;
        else return b-a;
    }
}


Measured memory_bytes: 22996
#include<bits/stdc++.h>
 
#define rep(i,n) for(ll i = 0;i < n;++i)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
typedef pair<int,int> P;
 
const int INF = 1001001001;
const long double PI = (acos(-1));
const int mod = 1e9+7;
const int vx[6] = {0,1,0,-1,1,-1};
const int vy[6] = {1,0,-1,0,1,1};




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

    ll n,k;
    cin >> n >> k;
    ll r,s,p;
    cin >> r >> s >> p;
    string t;
    cin >> t;
    ll ans = 0;
    for(ll i = 0;i < k;++i){
        string x;
        for(ll j = i;j < n;j+=k){
            if(j%k==i){
                x.push_back(t[j]);
            }
        }
        vector<vector<ll>> dp(x.size()+1,vector<ll> (3));
        rep(j,3){
            dp[0][j] = 0;
        }
        rep(j,x.size()){
            dp[j+1][0] = max(dp[j][1],dp[j][2]);
            dp[j+1][1] = max(dp[j][0],dp[j][2]);
            dp[j+1][2] = max(dp[j][0],dp[j][1]);
            if(x[j] == 'r'){
                dp[j+1][2] += p;
            }else if(x[j] == 's'){
                dp[j+1][0] += r;
            }else {
                dp[j+1][1] += s;
            }
        }
        ans += max(dp[x.size()][0],max(dp[x.size()][1],dp[x.size()][2]));
    }
    cout << ans << endl;

    cout << endl;
    return 0;
}


Measured memory_bytes: 5888
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        int q = Integer.parseInt(sc.next());

        k -= q;

        int[] score = new int[n];
        for (int i = 0; i < n; i++) {
            score[i] = k;
        }

        for (int i = 0; i < q; i++) {
            int t = Integer.parseInt(sc.next());
            score[t - 1] += 1;
        }

        for (int value : score) {
            if (value > 0) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }
}

Measured memory_bytes: 56924
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;


class Main{
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        float Sum = 0 ;
        int N = in.nextInt();
        int M = in.nextInt();
        ArrayList<Integer> A = new ArrayList<Integer>();
        for (int i = 0; i < N; i++) {
            A.add(in.nextInt());
            Sum += A.get(i);
        }
        float criteria = (Sum/(4*M)) ;
        int count = 0;
        for (int i = 0; i < N; i++) {
            if(A.get(i) >= criteria )
                count++;

        }

        if(count >= M)
            System.out.println("Yes");
        else
            System.out.println("No");






    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

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

using namespace std;

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

    set<char> st;
    for (int i = 0; i < n; ++i) {
        char ch;
        cin >> ch;
        st.insert(ch);
    }

    if (st.size() == 3) {
        cout << "Three" << endl;
    } else {
        cout << "Four" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
/*
ID: arthurc4
TASK: test
LANG: C++11
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

typedef vector<string> vs;
typedef vector<vs> vvs;

typedef vector<bool> vb;
typedef vector<vb> vvb;

typedef map<string,int> msi;
typedef map<int,int> mii;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll; // note 'single' ls

typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define REP(i, a, b) \
for (ll i = ll(a); i <= ll(b); i++)

#define REPb(j, d, c) \
for (int j = int(d); j >= int(c); j--)

#define pb \
push_back

#define ff \
first

#define ss \
second


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

// LL OR INT ???
// DELETED IFSTREAM ???
int main()
{
	//ifstream cin("input.txt");
	//ifstream cin("test.in");
	//ofstream cout("test.out");

	ll n, m;
	cin >> n >> m;

	string S;
	cin >> S;

	string T;
	cin >> T;

	REP(i, 0, n-1)
	{
		if(i*m % n == 0)
		{
			if(S[i] != T[(i*m)/n])
			{
				cout << "-1" << endl;
				return 0;
			}
		}
	}

	cout << (m*n)/gcd(m, n) << endl;

	return 0;
}

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

typedef long long ll;
typedef pair<int,int> pii;

long long MOD = 10000000000 + 7;
// modint
const ll mod = 1e9+7;
template< int mod >
struct ModInt {
  int x;
  ModInt() : x(0) {}
  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
      return *this;
  }
  ModInt &operator/=(const ModInt &p) {
    *this *= p.inv();
    return *this;
  }
  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
  bool operator==(const ModInt &p) const { return x == p.x; }
  bool operator!=(const ModInt &p) const { return x != p.x; }
    
  ModInt inv() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  
  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  
  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }
  
  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }
  
  static int get_mod() { return mod; }
};
 
using mint = ModInt<mod>;

int main(){
  cout << setprecision(10);
  int N; cin >> N;
  vector<ll> dig(60,0); // dig[i] :: iけた目が1の数 

  for(int i = 0; i < N; i++){
    ll tmp; cin >> tmp;

    int digit = 0;
    while(tmp > 0){
      ll x = tmp % 2;
      dig[digit] += x;
      tmp /= 2;
      digit++;
    }
  }

  mint ans = 0;
  for(int i = 0; i < 60; i++){
    mint tmp = dig[i] * (N-dig[i]);
    mint tmp2 = 2;
    tmp *= tmp2.pow(i);
    ans += tmp;
  }
  cout << ans << endl;

} 


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;


int solve(int N, vector<int>& h) {
    vector<int> v(N, 0);
    v[0] = 0;
    v[1] = abs(h[1] - h[0]);
    for (int i = 2; i < N; i++) {
        v[i] = min(v[i-2]+abs(h[i] - h[i-2]), v[i-1]+abs(h[i] - h[i-1]));
    }
    return v[N-1];
}


int main() {

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

    int minv = solve(N, h);
    cout << minv << endl;

    return 0;
}




Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(){
  int N, K;
  int a[5003];
  cin >> N >> K;
  for(int i = 0;i< N;i++){
    cin >> a[i];
  }
  sort(a, a + N);
  bool dp[5003]; // [和] = is, count
  fill(dp, dp + 5003, false);
  dp[0] = true;
  int okindex = N;
  for(int i = N - 1; i >= 0; i--){
    for(int j = 5000; j >= 0; j--){
      if(not dp[j]) continue;
      if(j + a[i] >= K){
        okindex = min((int)(lower_bound(a, a + N, K - j) - a), okindex);
      }else{
        dp[j + a[i]] |= dp[j];
      }
    }
  }
  cout << okindex << endl;
 
  return 0;
 
}

Measured memory_bytes: 256
a[3][1<<18],b[2],x,y,N[2][1<<18],i,j;main(n){scanf("%d",&n);for(;i<3;++i)for(j=0;j<n;++j){scanf("%d",&a[i][j]);--a[i][j];}for(j=0;j<n;++j){if(a[0][j]/3-a[1][j]/3||a[1][j]/3-a[2][j]/3||a[2][j]/3-a[0][j]/3||a[1][j]%3-1||a[1][j]/3-j&1){puts("No");return 0;}x=a[1][j]/3+1;while(x){b[j&1]-=N[j&1][x]%2;x-=x&-x;}b[j&1]+=j/2;y=a[2][j]/3+1;while(y<1<<18){++N[j&1][y];y+=y&-y;}if(a[0][j]%3)++b[1-j%2];}puts(b[0]&1|b[1]&1?"No":"Yes");}

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

using namespace std;

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)
#define DEBUG 1

lli abs2(lli a){
	if(a>=0)return a;
	else return -a;
}

lli length(lli x,lli y){
	return abs2(x)+abs2(y);
}

int main(){

	lli n;
	cin>>n;
	lli nowX=0;
	lli nowY=0;
	lli nowT=0;
	REP(i,n){
		lli nextX,nextY,nextT;
		cin>>nextT>>nextX>>nextY;
		lli diffT = nextT-nowT;
		lli diffXY = length(abs2(nextX-nowX),abs2(nextY-nowY));
		/* そもそもたどり着けない*/
		if(diffXY > diffT){
			cout<<"No"<<endl;
			return 0;
		}

		/*たどり着きはするが、ちょうどは無理*/
		if((diffT - diffXY)%2 == 1){
			cout<<"No"<<endl;
			return 0;
		}
		nowX = nextX;
		nowY = nextY;
		nowT = nextT;
	}

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

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

void dfs(bool c3, bool c5, bool c7, lint num){
  if(num > N) return;
  if(c3 && c5 && c7) ans++;
  dfs(true, c5, c7, 10 * num + 3);
  dfs(c3, true, c7, 10 * num + 5);
  dfs(c3, c5, true, 10 * num + 7);
}

signed main(){
  cin >> N;
  ans = 0;
  dfs(false, false, false, 0);
  cout << ans << endl;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

MOD = 10**9 + 7

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

def dijkstra(s):
    dist = z[:]
    dist[s] = 0
    heap = []
    heapq.heappush(heap, (0, s))
    
    while heap:
        dd, v = heapq.heappop(heap)
        dv = dist[v]
        if dv < dd:
            continue
        for i in path[v]:
            dvi = 1
            if dist[i] > dv + dvi:
                dist[i] = dv + dvi
                heapq.heappush(heap, (dist[i], i))
    return dist

n, m = ln()
X = ln()
Y = ln()
LX = len(X)
LY = len(Y)

for i in xrange(LX - 1, -1, -1):
    X[i] -= X[i - 1]

for i in xrange(LY - 1, -1, -1):
    Y[i] -= Y[i - 1]

for i in xrange(1, LX):
    X[i] *= i * (LX - i)

for i in xrange(1, LY):
    Y[i] *= i * (LY - i)

sum_x = 0
for i in xrange(1, LX):
    sum_x += X[i]
    sum_x %= MOD

sum_y = 0
for i in xrange(1, LY):
    sum_y += Y[i]
    sum_y %= MOD

print sum_x * sum_y % MOD


Measured memory_bytes: 51948
#include <stdio.h>

int main (void)
{
    char S[3], T[3];
    int i;
    int correct = 0;
    scanf("%s", S);
    scanf("%s", T);
    for (i = 0; i < 3; i++) {
        //printf("S=%c, T=%c\n", S[i],T[i]);
        if (S[i] == T[i]) {
            correct++;
        }
    }

    printf("%d", correct);
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"n,c=map(int,input().split())\n"
"d=[list(map(int,input().split()))for _ in range(c)]\n"
"l=[[i for i in[0]*c]for _ in range(3)]\n"
"for i in range(n):\n"
"  t=list(map(int,input().split()))\n"
"  for j in range(n):\n"
"    l[(i+j)%3][t[j]-1]+=1\n"
"a=10**18\n"
"for i in range(c):\n"
"  for j in range(c):\n"
"    for k in range(c):\n"
"      if i==j or j==k or k==i:continue\n"
"      a=min(a,sum(d[x][i]*l[0][x]+d[x][j]*l[1][x]+d[x][k]*l[2][x]for x in range(c)))\n"
"print(a)\n"
"\"";
  system(s);
  return 0;
}            

Measured memory_bytes: 3404